extent-tree.c 72 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809
  1. /*
  2. * Copyright (C) 2007 Oracle. All rights reserved.
  3. *
  4. * This program is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU General Public
  6. * License v2 as published by the Free Software Foundation.
  7. *
  8. * This program is distributed in the hope that it will be useful,
  9. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. * General Public License for more details.
  12. *
  13. * You should have received a copy of the GNU General Public
  14. * License along with this program; if not, write to the
  15. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16. * Boston, MA 021110-1307, USA.
  17. */
  18. #include <linux/sched.h>
  19. #include <linux/pagemap.h>
  20. #include "hash.h"
  21. #include "crc32c.h"
  22. #include "ctree.h"
  23. #include "disk-io.h"
  24. #include "print-tree.h"
  25. #include "transaction.h"
  26. #include "volumes.h"
  27. #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
  28. #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  29. #define BLOCK_GROUP_SYSTEM EXTENT_NEW
  30. #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  31. static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  32. btrfs_root *extent_root);
  33. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  34. btrfs_root *extent_root);
  35. static int cache_block_group(struct btrfs_root *root,
  36. struct btrfs_block_group_cache *block_group)
  37. {
  38. struct btrfs_path *path;
  39. int ret;
  40. struct btrfs_key key;
  41. struct extent_buffer *leaf;
  42. struct extent_io_tree *free_space_cache;
  43. int slot;
  44. u64 last = 0;
  45. u64 hole_size;
  46. u64 first_free;
  47. int found = 0;
  48. if (!block_group)
  49. return 0;
  50. root = root->fs_info->extent_root;
  51. free_space_cache = &root->fs_info->free_space_cache;
  52. if (block_group->cached)
  53. return 0;
  54. path = btrfs_alloc_path();
  55. if (!path)
  56. return -ENOMEM;
  57. path->reada = 2;
  58. first_free = block_group->key.objectid;
  59. key.objectid = block_group->key.objectid;
  60. key.offset = 0;
  61. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  62. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  63. if (ret < 0)
  64. return ret;
  65. ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  66. if (ret < 0)
  67. return ret;
  68. if (ret == 0) {
  69. leaf = path->nodes[0];
  70. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  71. if (key.objectid + key.offset > first_free)
  72. first_free = key.objectid + key.offset;
  73. }
  74. while(1) {
  75. leaf = path->nodes[0];
  76. slot = path->slots[0];
  77. if (slot >= btrfs_header_nritems(leaf)) {
  78. ret = btrfs_next_leaf(root, path);
  79. if (ret < 0)
  80. goto err;
  81. if (ret == 0) {
  82. continue;
  83. } else {
  84. break;
  85. }
  86. }
  87. btrfs_item_key_to_cpu(leaf, &key, slot);
  88. if (key.objectid < block_group->key.objectid) {
  89. goto next;
  90. }
  91. if (key.objectid >= block_group->key.objectid +
  92. block_group->key.offset) {
  93. break;
  94. }
  95. if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
  96. if (!found) {
  97. last = first_free;
  98. found = 1;
  99. }
  100. if (key.objectid > last) {
  101. hole_size = key.objectid - last;
  102. set_extent_dirty(free_space_cache, last,
  103. last + hole_size - 1,
  104. GFP_NOFS);
  105. }
  106. last = key.objectid + key.offset;
  107. }
  108. next:
  109. path->slots[0]++;
  110. }
  111. if (!found)
  112. last = first_free;
  113. if (block_group->key.objectid +
  114. block_group->key.offset > last) {
  115. hole_size = block_group->key.objectid +
  116. block_group->key.offset - last;
  117. set_extent_dirty(free_space_cache, last,
  118. last + hole_size - 1, GFP_NOFS);
  119. }
  120. block_group->cached = 1;
  121. err:
  122. btrfs_free_path(path);
  123. return 0;
  124. }
  125. struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
  126. btrfs_fs_info *info,
  127. u64 bytenr)
  128. {
  129. struct extent_io_tree *block_group_cache;
  130. struct btrfs_block_group_cache *block_group = NULL;
  131. u64 ptr;
  132. u64 start;
  133. u64 end;
  134. int ret;
  135. block_group_cache = &info->block_group_cache;
  136. ret = find_first_extent_bit(block_group_cache,
  137. bytenr, &start, &end,
  138. BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
  139. BLOCK_GROUP_SYSTEM);
  140. if (ret) {
  141. return NULL;
  142. }
  143. ret = get_state_private(block_group_cache, start, &ptr);
  144. if (ret)
  145. return NULL;
  146. block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  147. if (block_group->key.objectid <= bytenr && bytenr <
  148. block_group->key.objectid + block_group->key.offset)
  149. return block_group;
  150. return NULL;
  151. }
  152. static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  153. {
  154. return (cache->flags & bits) == bits;
  155. }
  156. static int noinline find_search_start(struct btrfs_root *root,
  157. struct btrfs_block_group_cache **cache_ret,
  158. u64 *start_ret, int num, int data)
  159. {
  160. int ret;
  161. struct btrfs_block_group_cache *cache = *cache_ret;
  162. struct extent_io_tree *free_space_cache;
  163. struct extent_state *state;
  164. u64 last;
  165. u64 start = 0;
  166. u64 cache_miss = 0;
  167. u64 total_fs_bytes;
  168. u64 search_start = *start_ret;
  169. int wrapped = 0;
  170. if (!cache)
  171. goto out;
  172. total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
  173. free_space_cache = &root->fs_info->free_space_cache;
  174. again:
  175. ret = cache_block_group(root, cache);
  176. if (ret)
  177. goto out;
  178. last = max(search_start, cache->key.objectid);
  179. if (!block_group_bits(cache, data) || cache->ro) {
  180. goto new_group;
  181. }
  182. spin_lock_irq(&free_space_cache->lock);
  183. state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
  184. while(1) {
  185. if (!state) {
  186. if (!cache_miss)
  187. cache_miss = last;
  188. spin_unlock_irq(&free_space_cache->lock);
  189. goto new_group;
  190. }
  191. start = max(last, state->start);
  192. last = state->end + 1;
  193. if (last - start < num) {
  194. if (last == cache->key.objectid + cache->key.offset)
  195. cache_miss = start;
  196. do {
  197. state = extent_state_next(state);
  198. } while(state && !(state->state & EXTENT_DIRTY));
  199. continue;
  200. }
  201. spin_unlock_irq(&free_space_cache->lock);
  202. if (cache->ro)
  203. goto new_group;
  204. if (start + num > cache->key.objectid + cache->key.offset)
  205. goto new_group;
  206. if (start + num > total_fs_bytes)
  207. goto new_group;
  208. if (!block_group_bits(cache, data)) {
  209. printk("block group bits don't match %Lu %d\n", cache->flags, data);
  210. }
  211. *start_ret = start;
  212. return 0;
  213. }
  214. out:
  215. cache = btrfs_lookup_block_group(root->fs_info, search_start);
  216. if (!cache) {
  217. printk("Unable to find block group for %Lu\n", search_start);
  218. WARN_ON(1);
  219. }
  220. return -ENOSPC;
  221. new_group:
  222. last = cache->key.objectid + cache->key.offset;
  223. wrapped:
  224. cache = btrfs_lookup_block_group(root->fs_info, last);
  225. if (!cache || cache->key.objectid >= total_fs_bytes) {
  226. no_cache:
  227. if (!wrapped) {
  228. wrapped = 1;
  229. last = search_start;
  230. goto wrapped;
  231. }
  232. goto out;
  233. }
  234. if (cache_miss && !cache->cached) {
  235. cache_block_group(root, cache);
  236. last = cache_miss;
  237. cache = btrfs_lookup_block_group(root->fs_info, last);
  238. }
  239. cache = btrfs_find_block_group(root, cache, last, data, 0);
  240. if (!cache)
  241. goto no_cache;
  242. *cache_ret = cache;
  243. cache_miss = 0;
  244. goto again;
  245. }
  246. static u64 div_factor(u64 num, int factor)
  247. {
  248. if (factor == 10)
  249. return num;
  250. num *= factor;
  251. do_div(num, 10);
  252. return num;
  253. }
  254. static int block_group_state_bits(u64 flags)
  255. {
  256. int bits = 0;
  257. if (flags & BTRFS_BLOCK_GROUP_DATA)
  258. bits |= BLOCK_GROUP_DATA;
  259. if (flags & BTRFS_BLOCK_GROUP_METADATA)
  260. bits |= BLOCK_GROUP_METADATA;
  261. if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  262. bits |= BLOCK_GROUP_SYSTEM;
  263. return bits;
  264. }
  265. struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
  266. struct btrfs_block_group_cache
  267. *hint, u64 search_start,
  268. int data, int owner)
  269. {
  270. struct btrfs_block_group_cache *cache;
  271. struct extent_io_tree *block_group_cache;
  272. struct btrfs_block_group_cache *found_group = NULL;
  273. struct btrfs_fs_info *info = root->fs_info;
  274. u64 used;
  275. u64 last = 0;
  276. u64 hint_last;
  277. u64 start;
  278. u64 end;
  279. u64 free_check;
  280. u64 ptr;
  281. u64 total_fs_bytes;
  282. int bit;
  283. int ret;
  284. int full_search = 0;
  285. int factor = 10;
  286. block_group_cache = &info->block_group_cache;
  287. total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
  288. if (!owner)
  289. factor = 10;
  290. bit = block_group_state_bits(data);
  291. if (search_start && search_start < total_fs_bytes) {
  292. struct btrfs_block_group_cache *shint;
  293. shint = btrfs_lookup_block_group(info, search_start);
  294. if (shint && block_group_bits(shint, data) && !shint->ro) {
  295. used = btrfs_block_group_used(&shint->item);
  296. if (used + shint->pinned <
  297. div_factor(shint->key.offset, factor)) {
  298. return shint;
  299. }
  300. }
  301. }
  302. if (hint && !hint->ro && block_group_bits(hint, data) &&
  303. hint->key.objectid < total_fs_bytes) {
  304. used = btrfs_block_group_used(&hint->item);
  305. if (used + hint->pinned <
  306. div_factor(hint->key.offset, factor)) {
  307. return hint;
  308. }
  309. last = hint->key.objectid + hint->key.offset;
  310. hint_last = last;
  311. } else {
  312. if (hint)
  313. hint_last = max(hint->key.objectid, search_start);
  314. else
  315. hint_last = search_start;
  316. if (hint_last >= total_fs_bytes)
  317. hint_last = search_start;
  318. last = hint_last;
  319. }
  320. again:
  321. while(1) {
  322. ret = find_first_extent_bit(block_group_cache, last,
  323. &start, &end, bit);
  324. if (ret)
  325. break;
  326. ret = get_state_private(block_group_cache, start, &ptr);
  327. if (ret)
  328. break;
  329. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  330. last = cache->key.objectid + cache->key.offset;
  331. used = btrfs_block_group_used(&cache->item);
  332. if (cache->key.objectid > total_fs_bytes)
  333. break;
  334. if (!cache->ro && block_group_bits(cache, data)) {
  335. if (full_search)
  336. free_check = cache->key.offset;
  337. else
  338. free_check = div_factor(cache->key.offset,
  339. factor);
  340. if (used + cache->pinned < free_check) {
  341. found_group = cache;
  342. goto found;
  343. }
  344. }
  345. cond_resched();
  346. }
  347. if (!full_search) {
  348. last = search_start;
  349. full_search = 1;
  350. goto again;
  351. }
  352. found:
  353. return found_group;
  354. }
  355. static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
  356. u64 owner, u64 owner_offset)
  357. {
  358. u32 high_crc = ~(u32)0;
  359. u32 low_crc = ~(u32)0;
  360. __le64 lenum;
  361. lenum = cpu_to_le64(root_objectid);
  362. high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
  363. lenum = cpu_to_le64(ref_generation);
  364. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  365. if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
  366. lenum = cpu_to_le64(owner);
  367. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  368. lenum = cpu_to_le64(owner_offset);
  369. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  370. }
  371. return ((u64)high_crc << 32) | (u64)low_crc;
  372. }
  373. static int match_extent_ref(struct extent_buffer *leaf,
  374. struct btrfs_extent_ref *disk_ref,
  375. struct btrfs_extent_ref *cpu_ref)
  376. {
  377. int ret;
  378. int len;
  379. if (cpu_ref->objectid)
  380. len = sizeof(*cpu_ref);
  381. else
  382. len = 2 * sizeof(u64);
  383. ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
  384. len);
  385. return ret == 0;
  386. }
  387. static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
  388. struct btrfs_root *root,
  389. struct btrfs_path *path, u64 bytenr,
  390. u64 root_objectid,
  391. u64 ref_generation, u64 owner,
  392. u64 owner_offset, int del)
  393. {
  394. u64 hash;
  395. struct btrfs_key key;
  396. struct btrfs_key found_key;
  397. struct btrfs_extent_ref ref;
  398. struct extent_buffer *leaf;
  399. struct btrfs_extent_ref *disk_ref;
  400. int ret;
  401. int ret2;
  402. btrfs_set_stack_ref_root(&ref, root_objectid);
  403. btrfs_set_stack_ref_generation(&ref, ref_generation);
  404. btrfs_set_stack_ref_objectid(&ref, owner);
  405. btrfs_set_stack_ref_offset(&ref, owner_offset);
  406. hash = hash_extent_ref(root_objectid, ref_generation, owner,
  407. owner_offset);
  408. key.offset = hash;
  409. key.objectid = bytenr;
  410. key.type = BTRFS_EXTENT_REF_KEY;
  411. while (1) {
  412. ret = btrfs_search_slot(trans, root, &key, path,
  413. del ? -1 : 0, del);
  414. if (ret < 0)
  415. goto out;
  416. leaf = path->nodes[0];
  417. if (ret != 0) {
  418. u32 nritems = btrfs_header_nritems(leaf);
  419. if (path->slots[0] >= nritems) {
  420. ret2 = btrfs_next_leaf(root, path);
  421. if (ret2)
  422. goto out;
  423. leaf = path->nodes[0];
  424. }
  425. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  426. if (found_key.objectid != bytenr ||
  427. found_key.type != BTRFS_EXTENT_REF_KEY)
  428. goto out;
  429. key.offset = found_key.offset;
  430. if (del) {
  431. btrfs_release_path(root, path);
  432. continue;
  433. }
  434. }
  435. disk_ref = btrfs_item_ptr(path->nodes[0],
  436. path->slots[0],
  437. struct btrfs_extent_ref);
  438. if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
  439. ret = 0;
  440. goto out;
  441. }
  442. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  443. key.offset = found_key.offset + 1;
  444. btrfs_release_path(root, path);
  445. }
  446. out:
  447. return ret;
  448. }
  449. /*
  450. * Back reference rules. Back refs have three main goals:
  451. *
  452. * 1) differentiate between all holders of references to an extent so that
  453. * when a reference is dropped we can make sure it was a valid reference
  454. * before freeing the extent.
  455. *
  456. * 2) Provide enough information to quickly find the holders of an extent
  457. * if we notice a given block is corrupted or bad.
  458. *
  459. * 3) Make it easy to migrate blocks for FS shrinking or storage pool
  460. * maintenance. This is actually the same as #2, but with a slightly
  461. * different use case.
  462. *
  463. * File extents can be referenced by:
  464. *
  465. * - multiple snapshots, subvolumes, or different generations in one subvol
  466. * - different files inside a single subvolume (in theory, not implemented yet)
  467. * - different offsets inside a file (bookend extents in file.c)
  468. *
  469. * The extent ref structure has fields for:
  470. *
  471. * - Objectid of the subvolume root
  472. * - Generation number of the tree holding the reference
  473. * - objectid of the file holding the reference
  474. * - offset in the file corresponding to the key holding the reference
  475. *
  476. * When a file extent is allocated the fields are filled in:
  477. * (root_key.objectid, trans->transid, inode objectid, offset in file)
  478. *
  479. * When a leaf is cow'd new references are added for every file extent found
  480. * in the leaf. It looks the same as the create case, but trans->transid
  481. * will be different when the block is cow'd.
  482. *
  483. * (root_key.objectid, trans->transid, inode objectid, offset in file)
  484. *
  485. * When a file extent is removed either during snapshot deletion or file
  486. * truncation, the corresponding back reference is found
  487. * by searching for:
  488. *
  489. * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
  490. * inode objectid, offset in file)
  491. *
  492. * Btree extents can be referenced by:
  493. *
  494. * - Different subvolumes
  495. * - Different generations of the same subvolume
  496. *
  497. * Storing sufficient information for a full reverse mapping of a btree
  498. * block would require storing the lowest key of the block in the backref,
  499. * and it would require updating that lowest key either before write out or
  500. * every time it changed. Instead, the objectid of the lowest key is stored
  501. * along with the level of the tree block. This provides a hint
  502. * about where in the btree the block can be found. Searches through the
  503. * btree only need to look for a pointer to that block, so they stop one
  504. * level higher than the level recorded in the backref.
  505. *
  506. * Some btrees do not do reference counting on their extents. These
  507. * include the extent tree and the tree of tree roots. Backrefs for these
  508. * trees always have a generation of zero.
  509. *
  510. * When a tree block is created, back references are inserted:
  511. *
  512. * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
  513. *
  514. * When a tree block is cow'd in a reference counted root,
  515. * new back references are added for all the blocks it points to.
  516. * These are of the form (trans->transid will have increased since creation):
  517. *
  518. * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
  519. *
  520. * Because the lowest_key_objectid and the level are just hints
  521. * they are not used when backrefs are deleted. When a backref is deleted:
  522. *
  523. * if backref was for a tree root:
  524. * root_objectid = root->root_key.objectid
  525. * else
  526. * root_objectid = btrfs_header_owner(parent)
  527. *
  528. * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
  529. *
  530. * Back Reference Key hashing:
  531. *
  532. * Back references have four fields, each 64 bits long. Unfortunately,
  533. * This is hashed into a single 64 bit number and placed into the key offset.
  534. * The key objectid corresponds to the first byte in the extent, and the
  535. * key type is set to BTRFS_EXTENT_REF_KEY
  536. */
  537. int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
  538. struct btrfs_root *root,
  539. struct btrfs_path *path, u64 bytenr,
  540. u64 root_objectid, u64 ref_generation,
  541. u64 owner, u64 owner_offset)
  542. {
  543. u64 hash;
  544. struct btrfs_key key;
  545. struct btrfs_extent_ref ref;
  546. struct btrfs_extent_ref *disk_ref;
  547. int ret;
  548. btrfs_set_stack_ref_root(&ref, root_objectid);
  549. btrfs_set_stack_ref_generation(&ref, ref_generation);
  550. btrfs_set_stack_ref_objectid(&ref, owner);
  551. btrfs_set_stack_ref_offset(&ref, owner_offset);
  552. hash = hash_extent_ref(root_objectid, ref_generation, owner,
  553. owner_offset);
  554. key.offset = hash;
  555. key.objectid = bytenr;
  556. key.type = BTRFS_EXTENT_REF_KEY;
  557. ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
  558. while (ret == -EEXIST) {
  559. disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  560. struct btrfs_extent_ref);
  561. if (match_extent_ref(path->nodes[0], disk_ref, &ref))
  562. goto out;
  563. key.offset++;
  564. btrfs_release_path(root, path);
  565. ret = btrfs_insert_empty_item(trans, root, path, &key,
  566. sizeof(ref));
  567. }
  568. if (ret)
  569. goto out;
  570. disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  571. struct btrfs_extent_ref);
  572. write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
  573. sizeof(ref));
  574. btrfs_mark_buffer_dirty(path->nodes[0]);
  575. out:
  576. btrfs_release_path(root, path);
  577. return ret;
  578. }
  579. int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  580. struct btrfs_root *root,
  581. u64 bytenr, u64 num_bytes,
  582. u64 root_objectid, u64 ref_generation,
  583. u64 owner, u64 owner_offset)
  584. {
  585. struct btrfs_path *path;
  586. int ret;
  587. struct btrfs_key key;
  588. struct extent_buffer *l;
  589. struct btrfs_extent_item *item;
  590. u32 refs;
  591. WARN_ON(num_bytes < root->sectorsize);
  592. path = btrfs_alloc_path();
  593. if (!path)
  594. return -ENOMEM;
  595. path->reada = 1;
  596. key.objectid = bytenr;
  597. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  598. key.offset = num_bytes;
  599. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  600. 0, 1);
  601. if (ret < 0)
  602. return ret;
  603. if (ret != 0) {
  604. BUG();
  605. }
  606. BUG_ON(ret != 0);
  607. l = path->nodes[0];
  608. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  609. refs = btrfs_extent_refs(l, item);
  610. btrfs_set_extent_refs(l, item, refs + 1);
  611. btrfs_mark_buffer_dirty(path->nodes[0]);
  612. btrfs_release_path(root->fs_info->extent_root, path);
  613. path->reada = 1;
  614. ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
  615. path, bytenr, root_objectid,
  616. ref_generation, owner, owner_offset);
  617. BUG_ON(ret);
  618. finish_current_insert(trans, root->fs_info->extent_root);
  619. del_pending_extents(trans, root->fs_info->extent_root);
  620. btrfs_free_path(path);
  621. return 0;
  622. }
  623. int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
  624. struct btrfs_root *root)
  625. {
  626. finish_current_insert(trans, root->fs_info->extent_root);
  627. del_pending_extents(trans, root->fs_info->extent_root);
  628. return 0;
  629. }
  630. static int lookup_extent_ref(struct btrfs_trans_handle *trans,
  631. struct btrfs_root *root, u64 bytenr,
  632. u64 num_bytes, u32 *refs)
  633. {
  634. struct btrfs_path *path;
  635. int ret;
  636. struct btrfs_key key;
  637. struct extent_buffer *l;
  638. struct btrfs_extent_item *item;
  639. WARN_ON(num_bytes < root->sectorsize);
  640. path = btrfs_alloc_path();
  641. path->reada = 1;
  642. key.objectid = bytenr;
  643. key.offset = num_bytes;
  644. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  645. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  646. 0, 0);
  647. if (ret < 0)
  648. goto out;
  649. if (ret != 0) {
  650. btrfs_print_leaf(root, path->nodes[0]);
  651. printk("failed to find block number %Lu\n", bytenr);
  652. BUG();
  653. }
  654. l = path->nodes[0];
  655. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  656. *refs = btrfs_extent_refs(l, item);
  657. out:
  658. btrfs_free_path(path);
  659. return 0;
  660. }
  661. u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
  662. struct btrfs_path *count_path,
  663. u64 first_extent)
  664. {
  665. struct btrfs_root *extent_root = root->fs_info->extent_root;
  666. struct btrfs_path *path;
  667. u64 bytenr;
  668. u64 found_objectid;
  669. u64 root_objectid = root->root_key.objectid;
  670. u32 total_count = 0;
  671. u32 cur_count;
  672. u32 nritems;
  673. int ret;
  674. struct btrfs_key key;
  675. struct btrfs_key found_key;
  676. struct extent_buffer *l;
  677. struct btrfs_extent_item *item;
  678. struct btrfs_extent_ref *ref_item;
  679. int level = -1;
  680. path = btrfs_alloc_path();
  681. again:
  682. if (level == -1)
  683. bytenr = first_extent;
  684. else
  685. bytenr = count_path->nodes[level]->start;
  686. cur_count = 0;
  687. key.objectid = bytenr;
  688. key.offset = 0;
  689. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  690. ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
  691. if (ret < 0)
  692. goto out;
  693. BUG_ON(ret == 0);
  694. l = path->nodes[0];
  695. btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
  696. if (found_key.objectid != bytenr ||
  697. found_key.type != BTRFS_EXTENT_ITEM_KEY) {
  698. goto out;
  699. }
  700. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  701. while (1) {
  702. l = path->nodes[0];
  703. nritems = btrfs_header_nritems(l);
  704. if (path->slots[0] >= nritems) {
  705. ret = btrfs_next_leaf(extent_root, path);
  706. if (ret == 0)
  707. continue;
  708. break;
  709. }
  710. btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
  711. if (found_key.objectid != bytenr)
  712. break;
  713. if (found_key.type != BTRFS_EXTENT_REF_KEY) {
  714. path->slots[0]++;
  715. continue;
  716. }
  717. cur_count++;
  718. ref_item = btrfs_item_ptr(l, path->slots[0],
  719. struct btrfs_extent_ref);
  720. found_objectid = btrfs_ref_root(l, ref_item);
  721. if (found_objectid != root_objectid) {
  722. total_count = 2;
  723. goto out;
  724. }
  725. total_count = 1;
  726. path->slots[0]++;
  727. }
  728. if (cur_count == 0) {
  729. total_count = 0;
  730. goto out;
  731. }
  732. if (level >= 0 && root->node == count_path->nodes[level])
  733. goto out;
  734. level++;
  735. btrfs_release_path(root, path);
  736. goto again;
  737. out:
  738. btrfs_free_path(path);
  739. return total_count;
  740. }
  741. int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
  742. struct btrfs_root *root, u64 owner_objectid)
  743. {
  744. u64 generation;
  745. u64 key_objectid;
  746. u64 level;
  747. u32 nritems;
  748. struct btrfs_disk_key disk_key;
  749. level = btrfs_header_level(root->node);
  750. generation = trans->transid;
  751. nritems = btrfs_header_nritems(root->node);
  752. if (nritems > 0) {
  753. if (level == 0)
  754. btrfs_item_key(root->node, &disk_key, 0);
  755. else
  756. btrfs_node_key(root->node, &disk_key, 0);
  757. key_objectid = btrfs_disk_key_objectid(&disk_key);
  758. } else {
  759. key_objectid = 0;
  760. }
  761. return btrfs_inc_extent_ref(trans, root, root->node->start,
  762. root->node->len, owner_objectid,
  763. generation, level, key_objectid);
  764. }
  765. int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  766. struct extent_buffer *buf)
  767. {
  768. u64 bytenr;
  769. u32 nritems;
  770. struct btrfs_key key;
  771. struct btrfs_file_extent_item *fi;
  772. int i;
  773. int level;
  774. int ret;
  775. int faili;
  776. if (!root->ref_cows)
  777. return 0;
  778. level = btrfs_header_level(buf);
  779. nritems = btrfs_header_nritems(buf);
  780. for (i = 0; i < nritems; i++) {
  781. if (level == 0) {
  782. u64 disk_bytenr;
  783. btrfs_item_key_to_cpu(buf, &key, i);
  784. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  785. continue;
  786. fi = btrfs_item_ptr(buf, i,
  787. struct btrfs_file_extent_item);
  788. if (btrfs_file_extent_type(buf, fi) ==
  789. BTRFS_FILE_EXTENT_INLINE)
  790. continue;
  791. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  792. if (disk_bytenr == 0)
  793. continue;
  794. ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
  795. btrfs_file_extent_disk_num_bytes(buf, fi),
  796. root->root_key.objectid, trans->transid,
  797. key.objectid, key.offset);
  798. if (ret) {
  799. faili = i;
  800. goto fail;
  801. }
  802. } else {
  803. bytenr = btrfs_node_blockptr(buf, i);
  804. btrfs_node_key_to_cpu(buf, &key, i);
  805. ret = btrfs_inc_extent_ref(trans, root, bytenr,
  806. btrfs_level_size(root, level - 1),
  807. root->root_key.objectid,
  808. trans->transid,
  809. level - 1, key.objectid);
  810. if (ret) {
  811. faili = i;
  812. goto fail;
  813. }
  814. }
  815. }
  816. return 0;
  817. fail:
  818. WARN_ON(1);
  819. #if 0
  820. for (i =0; i < faili; i++) {
  821. if (level == 0) {
  822. u64 disk_bytenr;
  823. btrfs_item_key_to_cpu(buf, &key, i);
  824. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  825. continue;
  826. fi = btrfs_item_ptr(buf, i,
  827. struct btrfs_file_extent_item);
  828. if (btrfs_file_extent_type(buf, fi) ==
  829. BTRFS_FILE_EXTENT_INLINE)
  830. continue;
  831. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  832. if (disk_bytenr == 0)
  833. continue;
  834. err = btrfs_free_extent(trans, root, disk_bytenr,
  835. btrfs_file_extent_disk_num_bytes(buf,
  836. fi), 0);
  837. BUG_ON(err);
  838. } else {
  839. bytenr = btrfs_node_blockptr(buf, i);
  840. err = btrfs_free_extent(trans, root, bytenr,
  841. btrfs_level_size(root, level - 1), 0);
  842. BUG_ON(err);
  843. }
  844. }
  845. #endif
  846. return ret;
  847. }
  848. static int write_one_cache_group(struct btrfs_trans_handle *trans,
  849. struct btrfs_root *root,
  850. struct btrfs_path *path,
  851. struct btrfs_block_group_cache *cache)
  852. {
  853. int ret;
  854. int pending_ret;
  855. struct btrfs_root *extent_root = root->fs_info->extent_root;
  856. unsigned long bi;
  857. struct extent_buffer *leaf;
  858. ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
  859. if (ret < 0)
  860. goto fail;
  861. BUG_ON(ret);
  862. leaf = path->nodes[0];
  863. bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
  864. write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
  865. btrfs_mark_buffer_dirty(leaf);
  866. btrfs_release_path(extent_root, path);
  867. fail:
  868. finish_current_insert(trans, extent_root);
  869. pending_ret = del_pending_extents(trans, extent_root);
  870. if (ret)
  871. return ret;
  872. if (pending_ret)
  873. return pending_ret;
  874. return 0;
  875. }
  876. int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
  877. struct btrfs_root *root)
  878. {
  879. struct extent_io_tree *block_group_cache;
  880. struct btrfs_block_group_cache *cache;
  881. int ret;
  882. int err = 0;
  883. int werr = 0;
  884. struct btrfs_path *path;
  885. u64 last = 0;
  886. u64 start;
  887. u64 end;
  888. u64 ptr;
  889. block_group_cache = &root->fs_info->block_group_cache;
  890. path = btrfs_alloc_path();
  891. if (!path)
  892. return -ENOMEM;
  893. while(1) {
  894. ret = find_first_extent_bit(block_group_cache, last,
  895. &start, &end, BLOCK_GROUP_DIRTY);
  896. if (ret)
  897. break;
  898. last = end + 1;
  899. ret = get_state_private(block_group_cache, start, &ptr);
  900. if (ret)
  901. break;
  902. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  903. err = write_one_cache_group(trans, root,
  904. path, cache);
  905. /*
  906. * if we fail to write the cache group, we want
  907. * to keep it marked dirty in hopes that a later
  908. * write will work
  909. */
  910. if (err) {
  911. werr = err;
  912. continue;
  913. }
  914. clear_extent_bits(block_group_cache, start, end,
  915. BLOCK_GROUP_DIRTY, GFP_NOFS);
  916. }
  917. btrfs_free_path(path);
  918. return werr;
  919. }
  920. static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
  921. u64 flags)
  922. {
  923. struct list_head *head = &info->space_info;
  924. struct list_head *cur;
  925. struct btrfs_space_info *found;
  926. list_for_each(cur, head) {
  927. found = list_entry(cur, struct btrfs_space_info, list);
  928. if (found->flags == flags)
  929. return found;
  930. }
  931. return NULL;
  932. }
  933. static int update_space_info(struct btrfs_fs_info *info, u64 flags,
  934. u64 total_bytes, u64 bytes_used,
  935. struct btrfs_space_info **space_info)
  936. {
  937. struct btrfs_space_info *found;
  938. found = __find_space_info(info, flags);
  939. if (found) {
  940. found->total_bytes += total_bytes;
  941. found->bytes_used += bytes_used;
  942. found->full = 0;
  943. WARN_ON(found->total_bytes < found->bytes_used);
  944. *space_info = found;
  945. return 0;
  946. }
  947. found = kmalloc(sizeof(*found), GFP_NOFS);
  948. if (!found)
  949. return -ENOMEM;
  950. list_add(&found->list, &info->space_info);
  951. found->flags = flags;
  952. found->total_bytes = total_bytes;
  953. found->bytes_used = bytes_used;
  954. found->bytes_pinned = 0;
  955. found->full = 0;
  956. *space_info = found;
  957. return 0;
  958. }
  959. static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
  960. {
  961. u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
  962. BTRFS_BLOCK_GROUP_RAID1 |
  963. BTRFS_BLOCK_GROUP_RAID10 |
  964. BTRFS_BLOCK_GROUP_DUP);
  965. if (extra_flags) {
  966. if (flags & BTRFS_BLOCK_GROUP_DATA)
  967. fs_info->avail_data_alloc_bits |= extra_flags;
  968. if (flags & BTRFS_BLOCK_GROUP_METADATA)
  969. fs_info->avail_metadata_alloc_bits |= extra_flags;
  970. if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  971. fs_info->avail_system_alloc_bits |= extra_flags;
  972. }
  973. }
  974. static int do_chunk_alloc(struct btrfs_trans_handle *trans,
  975. struct btrfs_root *extent_root, u64 alloc_bytes,
  976. u64 flags)
  977. {
  978. struct btrfs_space_info *space_info;
  979. u64 thresh;
  980. u64 start;
  981. u64 num_bytes;
  982. int ret;
  983. space_info = __find_space_info(extent_root->fs_info, flags);
  984. if (!space_info) {
  985. ret = update_space_info(extent_root->fs_info, flags,
  986. 0, 0, &space_info);
  987. BUG_ON(ret);
  988. }
  989. BUG_ON(!space_info);
  990. if (space_info->full)
  991. return 0;
  992. thresh = div_factor(space_info->total_bytes, 6);
  993. if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
  994. thresh)
  995. return 0;
  996. ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
  997. if (ret == -ENOSPC) {
  998. printk("space info full %Lu\n", flags);
  999. space_info->full = 1;
  1000. return 0;
  1001. }
  1002. BUG_ON(ret);
  1003. ret = btrfs_make_block_group(trans, extent_root, 0, flags,
  1004. BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
  1005. BUG_ON(ret);
  1006. return 0;
  1007. }
  1008. static int update_block_group(struct btrfs_trans_handle *trans,
  1009. struct btrfs_root *root,
  1010. u64 bytenr, u64 num_bytes, int alloc,
  1011. int mark_free)
  1012. {
  1013. struct btrfs_block_group_cache *cache;
  1014. struct btrfs_fs_info *info = root->fs_info;
  1015. u64 total = num_bytes;
  1016. u64 old_val;
  1017. u64 byte_in_group;
  1018. u64 start;
  1019. u64 end;
  1020. while(total) {
  1021. cache = btrfs_lookup_block_group(info, bytenr);
  1022. if (!cache) {
  1023. return -1;
  1024. }
  1025. byte_in_group = bytenr - cache->key.objectid;
  1026. WARN_ON(byte_in_group > cache->key.offset);
  1027. start = cache->key.objectid;
  1028. end = start + cache->key.offset - 1;
  1029. set_extent_bits(&info->block_group_cache, start, end,
  1030. BLOCK_GROUP_DIRTY, GFP_NOFS);
  1031. old_val = btrfs_block_group_used(&cache->item);
  1032. num_bytes = min(total, cache->key.offset - byte_in_group);
  1033. if (alloc) {
  1034. old_val += num_bytes;
  1035. cache->space_info->bytes_used += num_bytes;
  1036. } else {
  1037. old_val -= num_bytes;
  1038. cache->space_info->bytes_used -= num_bytes;
  1039. if (mark_free) {
  1040. set_extent_dirty(&info->free_space_cache,
  1041. bytenr, bytenr + num_bytes - 1,
  1042. GFP_NOFS);
  1043. }
  1044. }
  1045. btrfs_set_block_group_used(&cache->item, old_val);
  1046. total -= num_bytes;
  1047. bytenr += num_bytes;
  1048. }
  1049. return 0;
  1050. }
  1051. static int update_pinned_extents(struct btrfs_root *root,
  1052. u64 bytenr, u64 num, int pin)
  1053. {
  1054. u64 len;
  1055. struct btrfs_block_group_cache *cache;
  1056. struct btrfs_fs_info *fs_info = root->fs_info;
  1057. if (pin) {
  1058. set_extent_dirty(&fs_info->pinned_extents,
  1059. bytenr, bytenr + num - 1, GFP_NOFS);
  1060. } else {
  1061. clear_extent_dirty(&fs_info->pinned_extents,
  1062. bytenr, bytenr + num - 1, GFP_NOFS);
  1063. }
  1064. while (num > 0) {
  1065. cache = btrfs_lookup_block_group(fs_info, bytenr);
  1066. WARN_ON(!cache);
  1067. len = min(num, cache->key.offset -
  1068. (bytenr - cache->key.objectid));
  1069. if (pin) {
  1070. cache->pinned += len;
  1071. cache->space_info->bytes_pinned += len;
  1072. fs_info->total_pinned += len;
  1073. } else {
  1074. cache->pinned -= len;
  1075. cache->space_info->bytes_pinned -= len;
  1076. fs_info->total_pinned -= len;
  1077. }
  1078. bytenr += len;
  1079. num -= len;
  1080. }
  1081. return 0;
  1082. }
  1083. int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
  1084. {
  1085. u64 last = 0;
  1086. u64 start;
  1087. u64 end;
  1088. struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
  1089. int ret;
  1090. while(1) {
  1091. ret = find_first_extent_bit(pinned_extents, last,
  1092. &start, &end, EXTENT_DIRTY);
  1093. if (ret)
  1094. break;
  1095. set_extent_dirty(copy, start, end, GFP_NOFS);
  1096. last = end + 1;
  1097. }
  1098. return 0;
  1099. }
  1100. int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
  1101. struct btrfs_root *root,
  1102. struct extent_io_tree *unpin)
  1103. {
  1104. u64 start;
  1105. u64 end;
  1106. int ret;
  1107. struct extent_io_tree *free_space_cache;
  1108. free_space_cache = &root->fs_info->free_space_cache;
  1109. while(1) {
  1110. ret = find_first_extent_bit(unpin, 0, &start, &end,
  1111. EXTENT_DIRTY);
  1112. if (ret)
  1113. break;
  1114. update_pinned_extents(root, start, end + 1 - start, 0);
  1115. clear_extent_dirty(unpin, start, end, GFP_NOFS);
  1116. set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
  1117. }
  1118. return 0;
  1119. }
  1120. static int finish_current_insert(struct btrfs_trans_handle *trans,
  1121. struct btrfs_root *extent_root)
  1122. {
  1123. u64 start;
  1124. u64 end;
  1125. struct btrfs_fs_info *info = extent_root->fs_info;
  1126. struct extent_buffer *eb;
  1127. struct btrfs_path *path;
  1128. struct btrfs_key ins;
  1129. struct btrfs_disk_key first;
  1130. struct btrfs_extent_item extent_item;
  1131. int ret;
  1132. int level;
  1133. int err = 0;
  1134. btrfs_set_stack_extent_refs(&extent_item, 1);
  1135. btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
  1136. path = btrfs_alloc_path();
  1137. while(1) {
  1138. ret = find_first_extent_bit(&info->extent_ins, 0, &start,
  1139. &end, EXTENT_LOCKED);
  1140. if (ret)
  1141. break;
  1142. ins.objectid = start;
  1143. ins.offset = end + 1 - start;
  1144. err = btrfs_insert_item(trans, extent_root, &ins,
  1145. &extent_item, sizeof(extent_item));
  1146. clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
  1147. GFP_NOFS);
  1148. eb = read_tree_block(extent_root, ins.objectid, ins.offset);
  1149. level = btrfs_header_level(eb);
  1150. if (level == 0) {
  1151. btrfs_item_key(eb, &first, 0);
  1152. } else {
  1153. btrfs_node_key(eb, &first, 0);
  1154. }
  1155. err = btrfs_insert_extent_backref(trans, extent_root, path,
  1156. start, extent_root->root_key.objectid,
  1157. 0, level,
  1158. btrfs_disk_key_objectid(&first));
  1159. BUG_ON(err);
  1160. free_extent_buffer(eb);
  1161. }
  1162. btrfs_free_path(path);
  1163. return 0;
  1164. }
  1165. static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
  1166. int pending)
  1167. {
  1168. int err = 0;
  1169. struct extent_buffer *buf;
  1170. if (!pending) {
  1171. buf = btrfs_find_tree_block(root, bytenr, num_bytes);
  1172. if (buf) {
  1173. if (btrfs_buffer_uptodate(buf)) {
  1174. u64 transid =
  1175. root->fs_info->running_transaction->transid;
  1176. u64 header_transid =
  1177. btrfs_header_generation(buf);
  1178. if (header_transid == transid &&
  1179. !btrfs_header_flag(buf,
  1180. BTRFS_HEADER_FLAG_WRITTEN)) {
  1181. clean_tree_block(NULL, root, buf);
  1182. free_extent_buffer(buf);
  1183. return 1;
  1184. }
  1185. }
  1186. free_extent_buffer(buf);
  1187. }
  1188. update_pinned_extents(root, bytenr, num_bytes, 1);
  1189. } else {
  1190. set_extent_bits(&root->fs_info->pending_del,
  1191. bytenr, bytenr + num_bytes - 1,
  1192. EXTENT_LOCKED, GFP_NOFS);
  1193. }
  1194. BUG_ON(err < 0);
  1195. return 0;
  1196. }
  1197. /*
  1198. * remove an extent from the root, returns 0 on success
  1199. */
  1200. static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  1201. *root, u64 bytenr, u64 num_bytes,
  1202. u64 root_objectid, u64 ref_generation,
  1203. u64 owner_objectid, u64 owner_offset, int pin,
  1204. int mark_free)
  1205. {
  1206. struct btrfs_path *path;
  1207. struct btrfs_key key;
  1208. struct btrfs_fs_info *info = root->fs_info;
  1209. struct btrfs_root *extent_root = info->extent_root;
  1210. struct extent_buffer *leaf;
  1211. int ret;
  1212. int extent_slot = 0;
  1213. int found_extent = 0;
  1214. int num_to_del = 1;
  1215. struct btrfs_extent_item *ei;
  1216. u32 refs;
  1217. key.objectid = bytenr;
  1218. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  1219. key.offset = num_bytes;
  1220. path = btrfs_alloc_path();
  1221. if (!path)
  1222. return -ENOMEM;
  1223. path->reada = 1;
  1224. ret = lookup_extent_backref(trans, extent_root, path,
  1225. bytenr, root_objectid,
  1226. ref_generation,
  1227. owner_objectid, owner_offset, 1);
  1228. if (ret == 0) {
  1229. struct btrfs_key found_key;
  1230. extent_slot = path->slots[0];
  1231. while(extent_slot > 0) {
  1232. extent_slot--;
  1233. btrfs_item_key_to_cpu(path->nodes[0], &found_key,
  1234. extent_slot);
  1235. if (found_key.objectid != bytenr)
  1236. break;
  1237. if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
  1238. found_key.offset == num_bytes) {
  1239. found_extent = 1;
  1240. break;
  1241. }
  1242. if (path->slots[0] - extent_slot > 5)
  1243. break;
  1244. }
  1245. if (!found_extent)
  1246. ret = btrfs_del_item(trans, extent_root, path);
  1247. } else {
  1248. btrfs_print_leaf(extent_root, path->nodes[0]);
  1249. WARN_ON(1);
  1250. printk("Unable to find ref byte nr %Lu root %Lu "
  1251. " gen %Lu owner %Lu offset %Lu\n", bytenr,
  1252. root_objectid, ref_generation, owner_objectid,
  1253. owner_offset);
  1254. }
  1255. if (!found_extent) {
  1256. btrfs_release_path(extent_root, path);
  1257. ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
  1258. if (ret < 0)
  1259. return ret;
  1260. BUG_ON(ret);
  1261. extent_slot = path->slots[0];
  1262. }
  1263. leaf = path->nodes[0];
  1264. ei = btrfs_item_ptr(leaf, extent_slot,
  1265. struct btrfs_extent_item);
  1266. refs = btrfs_extent_refs(leaf, ei);
  1267. BUG_ON(refs == 0);
  1268. refs -= 1;
  1269. btrfs_set_extent_refs(leaf, ei, refs);
  1270. btrfs_mark_buffer_dirty(leaf);
  1271. if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
  1272. /* if the back ref and the extent are next to each other
  1273. * they get deleted below in one shot
  1274. */
  1275. path->slots[0] = extent_slot;
  1276. num_to_del = 2;
  1277. } else if (found_extent) {
  1278. /* otherwise delete the extent back ref */
  1279. ret = btrfs_del_item(trans, extent_root, path);
  1280. BUG_ON(ret);
  1281. /* if refs are 0, we need to setup the path for deletion */
  1282. if (refs == 0) {
  1283. btrfs_release_path(extent_root, path);
  1284. ret = btrfs_search_slot(trans, extent_root, &key, path,
  1285. -1, 1);
  1286. if (ret < 0)
  1287. return ret;
  1288. BUG_ON(ret);
  1289. }
  1290. }
  1291. if (refs == 0) {
  1292. u64 super_used;
  1293. u64 root_used;
  1294. if (pin) {
  1295. ret = pin_down_bytes(root, bytenr, num_bytes, 0);
  1296. if (ret > 0)
  1297. mark_free = 1;
  1298. BUG_ON(ret < 0);
  1299. }
  1300. /* block accounting for super block */
  1301. super_used = btrfs_super_bytes_used(&info->super_copy);
  1302. btrfs_set_super_bytes_used(&info->super_copy,
  1303. super_used - num_bytes);
  1304. /* block accounting for root item */
  1305. root_used = btrfs_root_used(&root->root_item);
  1306. btrfs_set_root_used(&root->root_item,
  1307. root_used - num_bytes);
  1308. ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
  1309. num_to_del);
  1310. if (ret) {
  1311. return ret;
  1312. }
  1313. ret = update_block_group(trans, root, bytenr, num_bytes, 0,
  1314. mark_free);
  1315. BUG_ON(ret);
  1316. }
  1317. btrfs_free_path(path);
  1318. finish_current_insert(trans, extent_root);
  1319. return ret;
  1320. }
  1321. /*
  1322. * find all the blocks marked as pending in the radix tree and remove
  1323. * them from the extent map
  1324. */
  1325. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  1326. btrfs_root *extent_root)
  1327. {
  1328. int ret;
  1329. int err = 0;
  1330. u64 start;
  1331. u64 end;
  1332. struct extent_io_tree *pending_del;
  1333. struct extent_io_tree *pinned_extents;
  1334. pending_del = &extent_root->fs_info->pending_del;
  1335. pinned_extents = &extent_root->fs_info->pinned_extents;
  1336. while(1) {
  1337. ret = find_first_extent_bit(pending_del, 0, &start, &end,
  1338. EXTENT_LOCKED);
  1339. if (ret)
  1340. break;
  1341. update_pinned_extents(extent_root, start, end + 1 - start, 1);
  1342. clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
  1343. GFP_NOFS);
  1344. ret = __free_extent(trans, extent_root,
  1345. start, end + 1 - start,
  1346. extent_root->root_key.objectid,
  1347. 0, 0, 0, 0, 0);
  1348. if (ret)
  1349. err = ret;
  1350. }
  1351. return err;
  1352. }
  1353. /*
  1354. * remove an extent from the root, returns 0 on success
  1355. */
  1356. int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  1357. *root, u64 bytenr, u64 num_bytes,
  1358. u64 root_objectid, u64 ref_generation,
  1359. u64 owner_objectid, u64 owner_offset, int pin)
  1360. {
  1361. struct btrfs_root *extent_root = root->fs_info->extent_root;
  1362. int pending_ret;
  1363. int ret;
  1364. WARN_ON(num_bytes < root->sectorsize);
  1365. if (!root->ref_cows)
  1366. ref_generation = 0;
  1367. if (root == extent_root) {
  1368. pin_down_bytes(root, bytenr, num_bytes, 1);
  1369. return 0;
  1370. }
  1371. ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
  1372. ref_generation, owner_objectid, owner_offset,
  1373. pin, pin == 0);
  1374. pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
  1375. return ret ? ret : pending_ret;
  1376. }
  1377. static u64 stripe_align(struct btrfs_root *root, u64 val)
  1378. {
  1379. u64 mask = ((u64)root->stripesize - 1);
  1380. u64 ret = (val + mask) & ~mask;
  1381. return ret;
  1382. }
  1383. /*
  1384. * walks the btree of allocated extents and find a hole of a given size.
  1385. * The key ins is changed to record the hole:
  1386. * ins->objectid == block start
  1387. * ins->flags = BTRFS_EXTENT_ITEM_KEY
  1388. * ins->offset == number of blocks
  1389. * Any available blocks before search_start are skipped.
  1390. */
  1391. static int noinline find_free_extent(struct btrfs_trans_handle *trans,
  1392. struct btrfs_root *orig_root,
  1393. u64 num_bytes, u64 empty_size,
  1394. u64 search_start, u64 search_end,
  1395. u64 hint_byte, struct btrfs_key *ins,
  1396. u64 exclude_start, u64 exclude_nr,
  1397. int data)
  1398. {
  1399. int ret;
  1400. u64 orig_search_start = search_start;
  1401. struct btrfs_root * root = orig_root->fs_info->extent_root;
  1402. struct btrfs_fs_info *info = root->fs_info;
  1403. u64 total_needed = num_bytes;
  1404. u64 *last_ptr = NULL;
  1405. struct btrfs_block_group_cache *block_group;
  1406. int full_scan = 0;
  1407. int wrapped = 0;
  1408. int empty_cluster = 2 * 1024 * 1024;
  1409. WARN_ON(num_bytes < root->sectorsize);
  1410. btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
  1411. if (data & BTRFS_BLOCK_GROUP_METADATA) {
  1412. last_ptr = &root->fs_info->last_alloc;
  1413. empty_cluster = 256 * 1024;
  1414. }
  1415. if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
  1416. last_ptr = &root->fs_info->last_data_alloc;
  1417. }
  1418. if (last_ptr) {
  1419. if (*last_ptr)
  1420. hint_byte = *last_ptr;
  1421. else {
  1422. empty_size += empty_cluster;
  1423. }
  1424. }
  1425. if (search_end == (u64)-1)
  1426. search_end = btrfs_super_total_bytes(&info->super_copy);
  1427. if (hint_byte) {
  1428. block_group = btrfs_lookup_block_group(info, hint_byte);
  1429. if (!block_group)
  1430. hint_byte = search_start;
  1431. block_group = btrfs_find_block_group(root, block_group,
  1432. hint_byte, data, 1);
  1433. if (last_ptr && *last_ptr == 0 && block_group)
  1434. hint_byte = block_group->key.objectid;
  1435. } else {
  1436. block_group = btrfs_find_block_group(root,
  1437. trans->block_group,
  1438. search_start, data, 1);
  1439. }
  1440. search_start = max(search_start, hint_byte);
  1441. total_needed += empty_size;
  1442. check_failed:
  1443. if (!block_group) {
  1444. block_group = btrfs_lookup_block_group(info, search_start);
  1445. if (!block_group)
  1446. block_group = btrfs_lookup_block_group(info,
  1447. orig_search_start);
  1448. }
  1449. ret = find_search_start(root, &block_group, &search_start,
  1450. total_needed, data);
  1451. if (ret == -ENOSPC && last_ptr && *last_ptr) {
  1452. *last_ptr = 0;
  1453. block_group = btrfs_lookup_block_group(info,
  1454. orig_search_start);
  1455. search_start = orig_search_start;
  1456. ret = find_search_start(root, &block_group, &search_start,
  1457. total_needed, data);
  1458. }
  1459. if (ret == -ENOSPC)
  1460. goto enospc;
  1461. if (ret)
  1462. goto error;
  1463. if (last_ptr && *last_ptr && search_start != *last_ptr) {
  1464. *last_ptr = 0;
  1465. if (!empty_size) {
  1466. empty_size += empty_cluster;
  1467. total_needed += empty_size;
  1468. }
  1469. block_group = btrfs_lookup_block_group(info,
  1470. orig_search_start);
  1471. search_start = orig_search_start;
  1472. ret = find_search_start(root, &block_group,
  1473. &search_start, total_needed, data);
  1474. if (ret == -ENOSPC)
  1475. goto enospc;
  1476. if (ret)
  1477. goto error;
  1478. }
  1479. search_start = stripe_align(root, search_start);
  1480. ins->objectid = search_start;
  1481. ins->offset = num_bytes;
  1482. if (ins->objectid + num_bytes >= search_end)
  1483. goto enospc;
  1484. if (ins->objectid + num_bytes >
  1485. block_group->key.objectid + block_group->key.offset) {
  1486. search_start = block_group->key.objectid +
  1487. block_group->key.offset;
  1488. goto new_group;
  1489. }
  1490. if (test_range_bit(&info->extent_ins, ins->objectid,
  1491. ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
  1492. search_start = ins->objectid + num_bytes;
  1493. goto new_group;
  1494. }
  1495. if (test_range_bit(&info->pinned_extents, ins->objectid,
  1496. ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
  1497. search_start = ins->objectid + num_bytes;
  1498. goto new_group;
  1499. }
  1500. if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
  1501. ins->objectid < exclude_start + exclude_nr)) {
  1502. search_start = exclude_start + exclude_nr;
  1503. goto new_group;
  1504. }
  1505. if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
  1506. block_group = btrfs_lookup_block_group(info, ins->objectid);
  1507. if (block_group)
  1508. trans->block_group = block_group;
  1509. }
  1510. ins->offset = num_bytes;
  1511. if (last_ptr) {
  1512. *last_ptr = ins->objectid + ins->offset;
  1513. if (*last_ptr ==
  1514. btrfs_super_total_bytes(&root->fs_info->super_copy)) {
  1515. *last_ptr = 0;
  1516. }
  1517. }
  1518. return 0;
  1519. new_group:
  1520. if (search_start + num_bytes >= search_end) {
  1521. enospc:
  1522. search_start = orig_search_start;
  1523. if (full_scan) {
  1524. ret = -ENOSPC;
  1525. goto error;
  1526. }
  1527. if (wrapped) {
  1528. if (!full_scan)
  1529. total_needed -= empty_size;
  1530. full_scan = 1;
  1531. } else
  1532. wrapped = 1;
  1533. }
  1534. block_group = btrfs_lookup_block_group(info, search_start);
  1535. cond_resched();
  1536. block_group = btrfs_find_block_group(root, block_group,
  1537. search_start, data, 0);
  1538. goto check_failed;
  1539. error:
  1540. return ret;
  1541. }
  1542. /*
  1543. * finds a free extent and does all the dirty work required for allocation
  1544. * returns the key for the extent through ins, and a tree buffer for
  1545. * the first block of the extent through buf.
  1546. *
  1547. * returns 0 if everything worked, non-zero otherwise.
  1548. */
  1549. int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
  1550. struct btrfs_root *root,
  1551. u64 num_bytes, u64 min_alloc_size,
  1552. u64 root_objectid, u64 ref_generation,
  1553. u64 owner, u64 owner_offset,
  1554. u64 empty_size, u64 hint_byte,
  1555. u64 search_end, struct btrfs_key *ins, int data)
  1556. {
  1557. int ret;
  1558. int pending_ret;
  1559. u64 super_used;
  1560. u64 root_used;
  1561. u64 search_start = 0;
  1562. u64 alloc_profile;
  1563. u32 sizes[2];
  1564. struct btrfs_fs_info *info = root->fs_info;
  1565. struct btrfs_root *extent_root = info->extent_root;
  1566. struct btrfs_extent_item *extent_item;
  1567. struct btrfs_extent_ref *ref;
  1568. struct btrfs_path *path;
  1569. struct btrfs_key keys[2];
  1570. if (data) {
  1571. alloc_profile = info->avail_data_alloc_bits &
  1572. info->data_alloc_profile;
  1573. data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
  1574. } else if (root == root->fs_info->chunk_root) {
  1575. alloc_profile = info->avail_system_alloc_bits &
  1576. info->system_alloc_profile;
  1577. data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
  1578. } else {
  1579. alloc_profile = info->avail_metadata_alloc_bits &
  1580. info->metadata_alloc_profile;
  1581. data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
  1582. }
  1583. again:
  1584. if (root->ref_cows) {
  1585. if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
  1586. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  1587. 2 * 1024 * 1024,
  1588. BTRFS_BLOCK_GROUP_METADATA |
  1589. (info->metadata_alloc_profile &
  1590. info->avail_metadata_alloc_bits));
  1591. BUG_ON(ret);
  1592. }
  1593. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  1594. num_bytes + 2 * 1024 * 1024, data);
  1595. BUG_ON(ret);
  1596. }
  1597. WARN_ON(num_bytes < root->sectorsize);
  1598. ret = find_free_extent(trans, root, num_bytes, empty_size,
  1599. search_start, search_end, hint_byte, ins,
  1600. trans->alloc_exclude_start,
  1601. trans->alloc_exclude_nr, data);
  1602. if (ret == -ENOSPC && num_bytes > min_alloc_size) {
  1603. num_bytes = num_bytes >> 1;
  1604. num_bytes = max(num_bytes, min_alloc_size);
  1605. goto again;
  1606. }
  1607. BUG_ON(ret);
  1608. if (ret)
  1609. return ret;
  1610. /* block accounting for super block */
  1611. super_used = btrfs_super_bytes_used(&info->super_copy);
  1612. btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
  1613. /* block accounting for root item */
  1614. root_used = btrfs_root_used(&root->root_item);
  1615. btrfs_set_root_used(&root->root_item, root_used + num_bytes);
  1616. clear_extent_dirty(&root->fs_info->free_space_cache,
  1617. ins->objectid, ins->objectid + ins->offset - 1,
  1618. GFP_NOFS);
  1619. if (root == extent_root) {
  1620. set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
  1621. ins->objectid + ins->offset - 1,
  1622. EXTENT_LOCKED, GFP_NOFS);
  1623. goto update_block;
  1624. }
  1625. WARN_ON(trans->alloc_exclude_nr);
  1626. trans->alloc_exclude_start = ins->objectid;
  1627. trans->alloc_exclude_nr = ins->offset;
  1628. memcpy(&keys[0], ins, sizeof(*ins));
  1629. keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
  1630. owner, owner_offset);
  1631. keys[1].objectid = ins->objectid;
  1632. keys[1].type = BTRFS_EXTENT_REF_KEY;
  1633. sizes[0] = sizeof(*extent_item);
  1634. sizes[1] = sizeof(*ref);
  1635. path = btrfs_alloc_path();
  1636. BUG_ON(!path);
  1637. ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
  1638. sizes, 2);
  1639. BUG_ON(ret);
  1640. extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
  1641. struct btrfs_extent_item);
  1642. btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
  1643. ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
  1644. struct btrfs_extent_ref);
  1645. btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
  1646. btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
  1647. btrfs_set_ref_objectid(path->nodes[0], ref, owner);
  1648. btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
  1649. btrfs_mark_buffer_dirty(path->nodes[0]);
  1650. trans->alloc_exclude_start = 0;
  1651. trans->alloc_exclude_nr = 0;
  1652. btrfs_free_path(path);
  1653. finish_current_insert(trans, extent_root);
  1654. pending_ret = del_pending_extents(trans, extent_root);
  1655. if (ret) {
  1656. return ret;
  1657. }
  1658. if (pending_ret) {
  1659. return pending_ret;
  1660. }
  1661. update_block:
  1662. ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
  1663. if (ret) {
  1664. printk("update block group failed for %Lu %Lu\n",
  1665. ins->objectid, ins->offset);
  1666. BUG();
  1667. }
  1668. return 0;
  1669. }
  1670. /*
  1671. * helper function to allocate a block for a given tree
  1672. * returns the tree buffer or NULL.
  1673. */
  1674. struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  1675. struct btrfs_root *root,
  1676. u32 blocksize,
  1677. u64 root_objectid, u64 hint,
  1678. u64 empty_size)
  1679. {
  1680. u64 ref_generation;
  1681. if (root->ref_cows)
  1682. ref_generation = trans->transid;
  1683. else
  1684. ref_generation = 0;
  1685. return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
  1686. ref_generation, 0, 0, hint, empty_size);
  1687. }
  1688. /*
  1689. * helper function to allocate a block for a given tree
  1690. * returns the tree buffer or NULL.
  1691. */
  1692. struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  1693. struct btrfs_root *root,
  1694. u32 blocksize,
  1695. u64 root_objectid,
  1696. u64 ref_generation,
  1697. u64 first_objectid,
  1698. int level,
  1699. u64 hint,
  1700. u64 empty_size)
  1701. {
  1702. struct btrfs_key ins;
  1703. int ret;
  1704. struct extent_buffer *buf;
  1705. ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
  1706. root_objectid, ref_generation,
  1707. level, first_objectid, empty_size, hint,
  1708. (u64)-1, &ins, 0);
  1709. if (ret) {
  1710. BUG_ON(ret > 0);
  1711. return ERR_PTR(ret);
  1712. }
  1713. buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
  1714. if (!buf) {
  1715. btrfs_free_extent(trans, root, ins.objectid, blocksize,
  1716. root->root_key.objectid, ref_generation,
  1717. 0, 0, 0);
  1718. return ERR_PTR(-ENOMEM);
  1719. }
  1720. btrfs_set_header_generation(buf, trans->transid);
  1721. clean_tree_block(trans, root, buf);
  1722. btrfs_set_buffer_uptodate(buf);
  1723. if (PageDirty(buf->first_page)) {
  1724. printk("page %lu dirty\n", buf->first_page->index);
  1725. WARN_ON(1);
  1726. }
  1727. set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
  1728. buf->start + buf->len - 1, GFP_NOFS);
  1729. if (!btrfs_test_opt(root, SSD))
  1730. btrfs_set_buffer_defrag(buf);
  1731. trans->blocks_used++;
  1732. return buf;
  1733. }
  1734. static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
  1735. struct btrfs_root *root,
  1736. struct extent_buffer *leaf)
  1737. {
  1738. u64 leaf_owner;
  1739. u64 leaf_generation;
  1740. struct btrfs_key key;
  1741. struct btrfs_file_extent_item *fi;
  1742. int i;
  1743. int nritems;
  1744. int ret;
  1745. BUG_ON(!btrfs_is_leaf(leaf));
  1746. nritems = btrfs_header_nritems(leaf);
  1747. leaf_owner = btrfs_header_owner(leaf);
  1748. leaf_generation = btrfs_header_generation(leaf);
  1749. for (i = 0; i < nritems; i++) {
  1750. u64 disk_bytenr;
  1751. btrfs_item_key_to_cpu(leaf, &key, i);
  1752. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  1753. continue;
  1754. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  1755. if (btrfs_file_extent_type(leaf, fi) ==
  1756. BTRFS_FILE_EXTENT_INLINE)
  1757. continue;
  1758. /*
  1759. * FIXME make sure to insert a trans record that
  1760. * repeats the snapshot del on crash
  1761. */
  1762. disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
  1763. if (disk_bytenr == 0)
  1764. continue;
  1765. ret = btrfs_free_extent(trans, root, disk_bytenr,
  1766. btrfs_file_extent_disk_num_bytes(leaf, fi),
  1767. leaf_owner, leaf_generation,
  1768. key.objectid, key.offset, 0);
  1769. BUG_ON(ret);
  1770. }
  1771. return 0;
  1772. }
  1773. static void noinline reada_walk_down(struct btrfs_root *root,
  1774. struct extent_buffer *node,
  1775. int slot)
  1776. {
  1777. u64 bytenr;
  1778. u64 last = 0;
  1779. u32 nritems;
  1780. u32 refs;
  1781. u32 blocksize;
  1782. int ret;
  1783. int i;
  1784. int level;
  1785. int skipped = 0;
  1786. nritems = btrfs_header_nritems(node);
  1787. level = btrfs_header_level(node);
  1788. if (level)
  1789. return;
  1790. for (i = slot; i < nritems && skipped < 32; i++) {
  1791. bytenr = btrfs_node_blockptr(node, i);
  1792. if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
  1793. (last > bytenr && last - bytenr > 32 * 1024))) {
  1794. skipped++;
  1795. continue;
  1796. }
  1797. blocksize = btrfs_level_size(root, level - 1);
  1798. if (i != slot) {
  1799. ret = lookup_extent_ref(NULL, root, bytenr,
  1800. blocksize, &refs);
  1801. BUG_ON(ret);
  1802. if (refs != 1) {
  1803. skipped++;
  1804. continue;
  1805. }
  1806. }
  1807. mutex_unlock(&root->fs_info->fs_mutex);
  1808. ret = readahead_tree_block(root, bytenr, blocksize);
  1809. last = bytenr + blocksize;
  1810. cond_resched();
  1811. mutex_lock(&root->fs_info->fs_mutex);
  1812. if (ret)
  1813. break;
  1814. }
  1815. }
  1816. /*
  1817. * helper function for drop_snapshot, this walks down the tree dropping ref
  1818. * counts as it goes.
  1819. */
  1820. static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
  1821. struct btrfs_root *root,
  1822. struct btrfs_path *path, int *level)
  1823. {
  1824. u64 root_owner;
  1825. u64 root_gen;
  1826. u64 bytenr;
  1827. struct extent_buffer *next;
  1828. struct extent_buffer *cur;
  1829. struct extent_buffer *parent;
  1830. u32 blocksize;
  1831. int ret;
  1832. u32 refs;
  1833. WARN_ON(*level < 0);
  1834. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1835. ret = lookup_extent_ref(trans, root,
  1836. path->nodes[*level]->start,
  1837. path->nodes[*level]->len, &refs);
  1838. BUG_ON(ret);
  1839. if (refs > 1)
  1840. goto out;
  1841. /*
  1842. * walk down to the last node level and free all the leaves
  1843. */
  1844. while(*level >= 0) {
  1845. WARN_ON(*level < 0);
  1846. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1847. cur = path->nodes[*level];
  1848. if (btrfs_header_level(cur) != *level)
  1849. WARN_ON(1);
  1850. if (path->slots[*level] >=
  1851. btrfs_header_nritems(cur))
  1852. break;
  1853. if (*level == 0) {
  1854. ret = drop_leaf_ref(trans, root, cur);
  1855. BUG_ON(ret);
  1856. break;
  1857. }
  1858. bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  1859. blocksize = btrfs_level_size(root, *level - 1);
  1860. ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
  1861. BUG_ON(ret);
  1862. if (refs != 1) {
  1863. parent = path->nodes[*level];
  1864. root_owner = btrfs_header_owner(parent);
  1865. root_gen = btrfs_header_generation(parent);
  1866. path->slots[*level]++;
  1867. ret = btrfs_free_extent(trans, root, bytenr,
  1868. blocksize, root_owner,
  1869. root_gen, 0, 0, 1);
  1870. BUG_ON(ret);
  1871. continue;
  1872. }
  1873. next = btrfs_find_tree_block(root, bytenr, blocksize);
  1874. if (!next || !btrfs_buffer_uptodate(next)) {
  1875. free_extent_buffer(next);
  1876. reada_walk_down(root, cur, path->slots[*level]);
  1877. mutex_unlock(&root->fs_info->fs_mutex);
  1878. next = read_tree_block(root, bytenr, blocksize);
  1879. mutex_lock(&root->fs_info->fs_mutex);
  1880. /* we've dropped the lock, double check */
  1881. ret = lookup_extent_ref(trans, root, bytenr,
  1882. blocksize, &refs);
  1883. BUG_ON(ret);
  1884. if (refs != 1) {
  1885. parent = path->nodes[*level];
  1886. root_owner = btrfs_header_owner(parent);
  1887. root_gen = btrfs_header_generation(parent);
  1888. path->slots[*level]++;
  1889. free_extent_buffer(next);
  1890. ret = btrfs_free_extent(trans, root, bytenr,
  1891. blocksize,
  1892. root_owner,
  1893. root_gen, 0, 0, 1);
  1894. BUG_ON(ret);
  1895. continue;
  1896. }
  1897. } else if (next) {
  1898. btrfs_verify_block_csum(root, next);
  1899. }
  1900. WARN_ON(*level <= 0);
  1901. if (path->nodes[*level-1])
  1902. free_extent_buffer(path->nodes[*level-1]);
  1903. path->nodes[*level-1] = next;
  1904. *level = btrfs_header_level(next);
  1905. path->slots[*level] = 0;
  1906. }
  1907. out:
  1908. WARN_ON(*level < 0);
  1909. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1910. if (path->nodes[*level] == root->node) {
  1911. root_owner = root->root_key.objectid;
  1912. parent = path->nodes[*level];
  1913. } else {
  1914. parent = path->nodes[*level + 1];
  1915. root_owner = btrfs_header_owner(parent);
  1916. }
  1917. root_gen = btrfs_header_generation(parent);
  1918. ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
  1919. path->nodes[*level]->len,
  1920. root_owner, root_gen, 0, 0, 1);
  1921. free_extent_buffer(path->nodes[*level]);
  1922. path->nodes[*level] = NULL;
  1923. *level += 1;
  1924. BUG_ON(ret);
  1925. return 0;
  1926. }
  1927. /*
  1928. * helper for dropping snapshots. This walks back up the tree in the path
  1929. * to find the first node higher up where we haven't yet gone through
  1930. * all the slots
  1931. */
  1932. static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
  1933. struct btrfs_root *root,
  1934. struct btrfs_path *path, int *level)
  1935. {
  1936. u64 root_owner;
  1937. u64 root_gen;
  1938. struct btrfs_root_item *root_item = &root->root_item;
  1939. int i;
  1940. int slot;
  1941. int ret;
  1942. for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
  1943. slot = path->slots[i];
  1944. if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
  1945. struct extent_buffer *node;
  1946. struct btrfs_disk_key disk_key;
  1947. node = path->nodes[i];
  1948. path->slots[i]++;
  1949. *level = i;
  1950. WARN_ON(*level == 0);
  1951. btrfs_node_key(node, &disk_key, path->slots[i]);
  1952. memcpy(&root_item->drop_progress,
  1953. &disk_key, sizeof(disk_key));
  1954. root_item->drop_level = i;
  1955. return 0;
  1956. } else {
  1957. if (path->nodes[*level] == root->node) {
  1958. root_owner = root->root_key.objectid;
  1959. root_gen =
  1960. btrfs_header_generation(path->nodes[*level]);
  1961. } else {
  1962. struct extent_buffer *node;
  1963. node = path->nodes[*level + 1];
  1964. root_owner = btrfs_header_owner(node);
  1965. root_gen = btrfs_header_generation(node);
  1966. }
  1967. ret = btrfs_free_extent(trans, root,
  1968. path->nodes[*level]->start,
  1969. path->nodes[*level]->len,
  1970. root_owner, root_gen, 0, 0, 1);
  1971. BUG_ON(ret);
  1972. free_extent_buffer(path->nodes[*level]);
  1973. path->nodes[*level] = NULL;
  1974. *level = i + 1;
  1975. }
  1976. }
  1977. return 1;
  1978. }
  1979. /*
  1980. * drop the reference count on the tree rooted at 'snap'. This traverses
  1981. * the tree freeing any blocks that have a ref count of zero after being
  1982. * decremented.
  1983. */
  1984. int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
  1985. *root)
  1986. {
  1987. int ret = 0;
  1988. int wret;
  1989. int level;
  1990. struct btrfs_path *path;
  1991. int i;
  1992. int orig_level;
  1993. struct btrfs_root_item *root_item = &root->root_item;
  1994. path = btrfs_alloc_path();
  1995. BUG_ON(!path);
  1996. level = btrfs_header_level(root->node);
  1997. orig_level = level;
  1998. if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
  1999. path->nodes[level] = root->node;
  2000. extent_buffer_get(root->node);
  2001. path->slots[level] = 0;
  2002. } else {
  2003. struct btrfs_key key;
  2004. struct btrfs_disk_key found_key;
  2005. struct extent_buffer *node;
  2006. btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
  2007. level = root_item->drop_level;
  2008. path->lowest_level = level;
  2009. wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2010. if (wret < 0) {
  2011. ret = wret;
  2012. goto out;
  2013. }
  2014. node = path->nodes[level];
  2015. btrfs_node_key(node, &found_key, path->slots[level]);
  2016. WARN_ON(memcmp(&found_key, &root_item->drop_progress,
  2017. sizeof(found_key)));
  2018. }
  2019. while(1) {
  2020. wret = walk_down_tree(trans, root, path, &level);
  2021. if (wret > 0)
  2022. break;
  2023. if (wret < 0)
  2024. ret = wret;
  2025. wret = walk_up_tree(trans, root, path, &level);
  2026. if (wret > 0)
  2027. break;
  2028. if (wret < 0)
  2029. ret = wret;
  2030. ret = -EAGAIN;
  2031. break;
  2032. }
  2033. for (i = 0; i <= orig_level; i++) {
  2034. if (path->nodes[i]) {
  2035. free_extent_buffer(path->nodes[i]);
  2036. path->nodes[i] = NULL;
  2037. }
  2038. }
  2039. out:
  2040. btrfs_free_path(path);
  2041. return ret;
  2042. }
  2043. int btrfs_free_block_groups(struct btrfs_fs_info *info)
  2044. {
  2045. u64 start;
  2046. u64 end;
  2047. u64 ptr;
  2048. int ret;
  2049. while(1) {
  2050. ret = find_first_extent_bit(&info->block_group_cache, 0,
  2051. &start, &end, (unsigned int)-1);
  2052. if (ret)
  2053. break;
  2054. ret = get_state_private(&info->block_group_cache, start, &ptr);
  2055. if (!ret)
  2056. kfree((void *)(unsigned long)ptr);
  2057. clear_extent_bits(&info->block_group_cache, start,
  2058. end, (unsigned int)-1, GFP_NOFS);
  2059. }
  2060. while(1) {
  2061. ret = find_first_extent_bit(&info->free_space_cache, 0,
  2062. &start, &end, EXTENT_DIRTY);
  2063. if (ret)
  2064. break;
  2065. clear_extent_dirty(&info->free_space_cache, start,
  2066. end, GFP_NOFS);
  2067. }
  2068. return 0;
  2069. }
  2070. static unsigned long calc_ra(unsigned long start, unsigned long last,
  2071. unsigned long nr)
  2072. {
  2073. return min(last, start + nr - 1);
  2074. }
  2075. static int noinline relocate_inode_pages(struct inode *inode, u64 start,
  2076. u64 len)
  2077. {
  2078. u64 page_start;
  2079. u64 page_end;
  2080. u64 delalloc_start;
  2081. u64 existing_delalloc;
  2082. unsigned long last_index;
  2083. unsigned long i;
  2084. struct page *page;
  2085. struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
  2086. struct file_ra_state *ra;
  2087. unsigned long total_read = 0;
  2088. unsigned long ra_pages;
  2089. ra = kzalloc(sizeof(*ra), GFP_NOFS);
  2090. mutex_lock(&inode->i_mutex);
  2091. i = start >> PAGE_CACHE_SHIFT;
  2092. last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
  2093. ra_pages = BTRFS_I(inode)->root->fs_info->bdi.ra_pages;
  2094. file_ra_state_init(ra, inode->i_mapping);
  2095. kfree(ra);
  2096. for (; i <= last_index; i++) {
  2097. if (total_read % ra_pages == 0) {
  2098. btrfs_force_ra(inode->i_mapping, ra, NULL, i,
  2099. calc_ra(i, last_index, ra_pages));
  2100. }
  2101. total_read++;
  2102. page = grab_cache_page(inode->i_mapping, i);
  2103. if (!page)
  2104. goto out_unlock;
  2105. if (!PageUptodate(page)) {
  2106. btrfs_readpage(NULL, page);
  2107. lock_page(page);
  2108. if (!PageUptodate(page)) {
  2109. unlock_page(page);
  2110. page_cache_release(page);
  2111. goto out_unlock;
  2112. }
  2113. }
  2114. page_start = (u64)page->index << PAGE_CACHE_SHIFT;
  2115. page_end = page_start + PAGE_CACHE_SIZE - 1;
  2116. lock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2117. delalloc_start = page_start;
  2118. existing_delalloc = count_range_bits(io_tree,
  2119. &delalloc_start, page_end,
  2120. PAGE_CACHE_SIZE, EXTENT_DELALLOC);
  2121. set_extent_delalloc(io_tree, page_start,
  2122. page_end, GFP_NOFS);
  2123. unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2124. set_page_dirty(page);
  2125. unlock_page(page);
  2126. page_cache_release(page);
  2127. }
  2128. out_unlock:
  2129. mutex_unlock(&inode->i_mutex);
  2130. return 0;
  2131. }
  2132. /*
  2133. * note, this releases the path
  2134. */
  2135. static int noinline relocate_one_reference(struct btrfs_root *extent_root,
  2136. struct btrfs_path *path,
  2137. struct btrfs_key *extent_key)
  2138. {
  2139. struct inode *inode;
  2140. struct btrfs_root *found_root;
  2141. struct btrfs_key *root_location;
  2142. struct btrfs_extent_ref *ref;
  2143. u64 ref_root;
  2144. u64 ref_gen;
  2145. u64 ref_objectid;
  2146. u64 ref_offset;
  2147. int ret;
  2148. ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  2149. struct btrfs_extent_ref);
  2150. ref_root = btrfs_ref_root(path->nodes[0], ref);
  2151. ref_gen = btrfs_ref_generation(path->nodes[0], ref);
  2152. ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
  2153. ref_offset = btrfs_ref_offset(path->nodes[0], ref);
  2154. btrfs_release_path(extent_root, path);
  2155. root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
  2156. root_location->objectid = ref_root;
  2157. if (ref_gen == 0)
  2158. root_location->offset = 0;
  2159. else
  2160. root_location->offset = (u64)-1;
  2161. root_location->type = BTRFS_ROOT_ITEM_KEY;
  2162. found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
  2163. root_location);
  2164. BUG_ON(!found_root);
  2165. kfree(root_location);
  2166. if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
  2167. mutex_unlock(&extent_root->fs_info->fs_mutex);
  2168. inode = btrfs_iget_locked(extent_root->fs_info->sb,
  2169. ref_objectid, found_root);
  2170. if (inode->i_state & I_NEW) {
  2171. /* the inode and parent dir are two different roots */
  2172. BTRFS_I(inode)->root = found_root;
  2173. BTRFS_I(inode)->location.objectid = ref_objectid;
  2174. BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
  2175. BTRFS_I(inode)->location.offset = 0;
  2176. btrfs_read_locked_inode(inode);
  2177. unlock_new_inode(inode);
  2178. }
  2179. /* this can happen if the reference is not against
  2180. * the latest version of the tree root
  2181. */
  2182. if (is_bad_inode(inode)) {
  2183. mutex_lock(&extent_root->fs_info->fs_mutex);
  2184. goto out;
  2185. }
  2186. relocate_inode_pages(inode, ref_offset, extent_key->offset);
  2187. /* FIXME, data=ordered will help get rid of this */
  2188. filemap_fdatawrite(inode->i_mapping);
  2189. iput(inode);
  2190. mutex_lock(&extent_root->fs_info->fs_mutex);
  2191. } else {
  2192. struct btrfs_trans_handle *trans;
  2193. struct btrfs_key found_key;
  2194. struct extent_buffer *eb;
  2195. int level;
  2196. int i;
  2197. trans = btrfs_start_transaction(found_root, 1);
  2198. eb = read_tree_block(found_root, extent_key->objectid,
  2199. extent_key->offset);
  2200. level = btrfs_header_level(eb);
  2201. if (level == 0)
  2202. btrfs_item_key_to_cpu(eb, &found_key, 0);
  2203. else
  2204. btrfs_node_key_to_cpu(eb, &found_key, 0);
  2205. free_extent_buffer(eb);
  2206. path->lowest_level = level;
  2207. path->reada = 2;
  2208. ret = btrfs_search_slot(trans, found_root, &found_key, path,
  2209. 0, 1);
  2210. path->lowest_level = 0;
  2211. for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  2212. if (!path->nodes[i])
  2213. break;
  2214. free_extent_buffer(path->nodes[i]);
  2215. path->nodes[i] = NULL;
  2216. }
  2217. btrfs_release_path(found_root, path);
  2218. btrfs_end_transaction(trans, found_root);
  2219. }
  2220. out:
  2221. return 0;
  2222. }
  2223. static int noinline relocate_one_extent(struct btrfs_root *extent_root,
  2224. struct btrfs_path *path,
  2225. struct btrfs_key *extent_key)
  2226. {
  2227. struct btrfs_key key;
  2228. struct btrfs_key found_key;
  2229. struct extent_buffer *leaf;
  2230. u32 nritems;
  2231. u32 item_size;
  2232. int ret = 0;
  2233. key.objectid = extent_key->objectid;
  2234. key.type = BTRFS_EXTENT_REF_KEY;
  2235. key.offset = 0;
  2236. while(1) {
  2237. ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
  2238. if (ret < 0)
  2239. goto out;
  2240. ret = 0;
  2241. leaf = path->nodes[0];
  2242. nritems = btrfs_header_nritems(leaf);
  2243. if (path->slots[0] == nritems)
  2244. goto out;
  2245. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2246. if (found_key.objectid != extent_key->objectid)
  2247. break;
  2248. if (found_key.type != BTRFS_EXTENT_REF_KEY)
  2249. break;
  2250. key.offset = found_key.offset + 1;
  2251. item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  2252. ret = relocate_one_reference(extent_root, path, extent_key);
  2253. if (ret)
  2254. goto out;
  2255. }
  2256. ret = 0;
  2257. out:
  2258. btrfs_release_path(extent_root, path);
  2259. return ret;
  2260. }
  2261. int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 shrink_start)
  2262. {
  2263. struct btrfs_trans_handle *trans;
  2264. struct btrfs_root *tree_root = root->fs_info->tree_root;
  2265. struct btrfs_path *path;
  2266. u64 cur_byte;
  2267. u64 total_found;
  2268. u64 shrink_last_byte;
  2269. struct btrfs_block_group_cache *shrink_block_group;
  2270. struct btrfs_fs_info *info = root->fs_info;
  2271. struct btrfs_key key;
  2272. struct btrfs_key found_key;
  2273. struct extent_buffer *leaf;
  2274. u32 nritems;
  2275. int ret;
  2276. int progress = 0;
  2277. shrink_block_group = btrfs_lookup_block_group(root->fs_info,
  2278. shrink_start);
  2279. BUG_ON(!shrink_block_group);
  2280. shrink_last_byte = shrink_start + shrink_block_group->key.offset;
  2281. shrink_block_group->space_info->total_bytes -=
  2282. shrink_block_group->key.offset;
  2283. printk("shrink_extent_tree %Lu -> %Lu type %Lu\n", shrink_start, shrink_last_byte, shrink_block_group->flags);
  2284. path = btrfs_alloc_path();
  2285. root = root->fs_info->extent_root;
  2286. path->reada = 2;
  2287. again:
  2288. trans = btrfs_start_transaction(root, 1);
  2289. do_chunk_alloc(trans, root->fs_info->extent_root,
  2290. btrfs_block_group_used(&shrink_block_group->item) +
  2291. 2 * 1024 * 1024, shrink_block_group->flags);
  2292. btrfs_end_transaction(trans, root);
  2293. shrink_block_group->ro = 1;
  2294. total_found = 0;
  2295. key.objectid = shrink_start;
  2296. key.offset = 0;
  2297. key.type = 0;
  2298. cur_byte = key.objectid;
  2299. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2300. if (ret < 0)
  2301. goto out;
  2302. ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  2303. if (ret < 0)
  2304. goto out;
  2305. if (ret == 0) {
  2306. leaf = path->nodes[0];
  2307. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2308. if (found_key.objectid + found_key.offset > shrink_start &&
  2309. found_key.objectid < shrink_last_byte) {
  2310. cur_byte = found_key.objectid;
  2311. key.objectid = cur_byte;
  2312. }
  2313. }
  2314. btrfs_release_path(root, path);
  2315. while(1) {
  2316. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2317. if (ret < 0)
  2318. goto out;
  2319. leaf = path->nodes[0];
  2320. nritems = btrfs_header_nritems(leaf);
  2321. next:
  2322. if (path->slots[0] >= nritems) {
  2323. ret = btrfs_next_leaf(root, path);
  2324. if (ret < 0)
  2325. goto out;
  2326. if (ret == 1) {
  2327. ret = 0;
  2328. break;
  2329. }
  2330. leaf = path->nodes[0];
  2331. nritems = btrfs_header_nritems(leaf);
  2332. }
  2333. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2334. if (found_key.objectid >= shrink_last_byte)
  2335. break;
  2336. if (progress && need_resched()) {
  2337. memcpy(&key, &found_key, sizeof(key));
  2338. mutex_unlock(&root->fs_info->fs_mutex);
  2339. cond_resched();
  2340. mutex_lock(&root->fs_info->fs_mutex);
  2341. btrfs_release_path(root, path);
  2342. btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2343. progress = 0;
  2344. goto next;
  2345. }
  2346. progress = 1;
  2347. if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
  2348. found_key.objectid + found_key.offset <= cur_byte) {
  2349. path->slots[0]++;
  2350. goto next;
  2351. }
  2352. total_found++;
  2353. cur_byte = found_key.objectid + found_key.offset;
  2354. key.objectid = cur_byte;
  2355. btrfs_release_path(root, path);
  2356. ret = relocate_one_extent(root, path, &found_key);
  2357. }
  2358. btrfs_release_path(root, path);
  2359. if (total_found > 0) {
  2360. trans = btrfs_start_transaction(tree_root, 1);
  2361. btrfs_commit_transaction(trans, tree_root);
  2362. mutex_unlock(&root->fs_info->fs_mutex);
  2363. btrfs_clean_old_snapshots(tree_root);
  2364. mutex_lock(&root->fs_info->fs_mutex);
  2365. trans = btrfs_start_transaction(tree_root, 1);
  2366. btrfs_commit_transaction(trans, tree_root);
  2367. goto again;
  2368. }
  2369. /*
  2370. * we've freed all the extents, now remove the block
  2371. * group item from the tree
  2372. */
  2373. trans = btrfs_start_transaction(root, 1);
  2374. memcpy(&key, &shrink_block_group->key, sizeof(key));
  2375. ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  2376. if (ret > 0)
  2377. ret = -EIO;
  2378. if (ret < 0)
  2379. goto out;
  2380. leaf = path->nodes[0];
  2381. nritems = btrfs_header_nritems(leaf);
  2382. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2383. kfree(shrink_block_group);
  2384. clear_extent_bits(&info->block_group_cache, found_key.objectid,
  2385. found_key.objectid + found_key.offset - 1,
  2386. (unsigned int)-1, GFP_NOFS);
  2387. btrfs_del_item(trans, root, path);
  2388. clear_extent_dirty(&info->free_space_cache,
  2389. shrink_start, shrink_last_byte - 1,
  2390. GFP_NOFS);
  2391. btrfs_commit_transaction(trans, root);
  2392. out:
  2393. btrfs_free_path(path);
  2394. return ret;
  2395. }
  2396. int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
  2397. struct btrfs_key *key)
  2398. {
  2399. int ret;
  2400. struct btrfs_key found_key;
  2401. struct extent_buffer *leaf;
  2402. int slot;
  2403. ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
  2404. if (ret < 0)
  2405. return ret;
  2406. while(1) {
  2407. slot = path->slots[0];
  2408. leaf = path->nodes[0];
  2409. if (slot >= btrfs_header_nritems(leaf)) {
  2410. ret = btrfs_next_leaf(root, path);
  2411. if (ret == 0)
  2412. continue;
  2413. if (ret < 0)
  2414. goto error;
  2415. break;
  2416. }
  2417. btrfs_item_key_to_cpu(leaf, &found_key, slot);
  2418. if (found_key.objectid >= key->objectid &&
  2419. found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
  2420. return 0;
  2421. path->slots[0]++;
  2422. }
  2423. ret = -ENOENT;
  2424. error:
  2425. return ret;
  2426. }
  2427. int btrfs_read_block_groups(struct btrfs_root *root)
  2428. {
  2429. struct btrfs_path *path;
  2430. int ret;
  2431. int bit;
  2432. struct btrfs_block_group_cache *cache;
  2433. struct btrfs_fs_info *info = root->fs_info;
  2434. struct btrfs_space_info *space_info;
  2435. struct extent_io_tree *block_group_cache;
  2436. struct btrfs_key key;
  2437. struct btrfs_key found_key;
  2438. struct extent_buffer *leaf;
  2439. block_group_cache = &info->block_group_cache;
  2440. root = info->extent_root;
  2441. key.objectid = 0;
  2442. key.offset = 0;
  2443. btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  2444. path = btrfs_alloc_path();
  2445. if (!path)
  2446. return -ENOMEM;
  2447. while(1) {
  2448. ret = find_first_block_group(root, path, &key);
  2449. if (ret > 0) {
  2450. ret = 0;
  2451. goto error;
  2452. }
  2453. if (ret != 0)
  2454. goto error;
  2455. leaf = path->nodes[0];
  2456. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2457. cache = kzalloc(sizeof(*cache), GFP_NOFS);
  2458. if (!cache) {
  2459. ret = -ENOMEM;
  2460. break;
  2461. }
  2462. read_extent_buffer(leaf, &cache->item,
  2463. btrfs_item_ptr_offset(leaf, path->slots[0]),
  2464. sizeof(cache->item));
  2465. memcpy(&cache->key, &found_key, sizeof(found_key));
  2466. key.objectid = found_key.objectid + found_key.offset;
  2467. btrfs_release_path(root, path);
  2468. cache->flags = btrfs_block_group_flags(&cache->item);
  2469. bit = 0;
  2470. if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
  2471. bit = BLOCK_GROUP_DATA;
  2472. } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
  2473. bit = BLOCK_GROUP_SYSTEM;
  2474. } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
  2475. bit = BLOCK_GROUP_METADATA;
  2476. }
  2477. set_avail_alloc_bits(info, cache->flags);
  2478. ret = update_space_info(info, cache->flags, found_key.offset,
  2479. btrfs_block_group_used(&cache->item),
  2480. &space_info);
  2481. BUG_ON(ret);
  2482. cache->space_info = space_info;
  2483. /* use EXTENT_LOCKED to prevent merging */
  2484. set_extent_bits(block_group_cache, found_key.objectid,
  2485. found_key.objectid + found_key.offset - 1,
  2486. bit | EXTENT_LOCKED, GFP_NOFS);
  2487. set_state_private(block_group_cache, found_key.objectid,
  2488. (unsigned long)cache);
  2489. if (key.objectid >=
  2490. btrfs_super_total_bytes(&info->super_copy))
  2491. break;
  2492. }
  2493. ret = 0;
  2494. error:
  2495. btrfs_free_path(path);
  2496. return ret;
  2497. }
  2498. int btrfs_make_block_group(struct btrfs_trans_handle *trans,
  2499. struct btrfs_root *root, u64 bytes_used,
  2500. u64 type, u64 chunk_objectid, u64 chunk_offset,
  2501. u64 size)
  2502. {
  2503. int ret;
  2504. int bit = 0;
  2505. struct btrfs_root *extent_root;
  2506. struct btrfs_block_group_cache *cache;
  2507. struct extent_io_tree *block_group_cache;
  2508. extent_root = root->fs_info->extent_root;
  2509. block_group_cache = &root->fs_info->block_group_cache;
  2510. cache = kzalloc(sizeof(*cache), GFP_NOFS);
  2511. BUG_ON(!cache);
  2512. cache->key.objectid = chunk_offset;
  2513. cache->key.offset = size;
  2514. btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  2515. memset(&cache->item, 0, sizeof(cache->item));
  2516. btrfs_set_block_group_used(&cache->item, bytes_used);
  2517. btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
  2518. cache->flags = type;
  2519. btrfs_set_block_group_flags(&cache->item, type);
  2520. ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
  2521. &cache->space_info);
  2522. BUG_ON(ret);
  2523. bit = block_group_state_bits(type);
  2524. set_extent_bits(block_group_cache, chunk_offset,
  2525. chunk_offset + size - 1,
  2526. bit | EXTENT_LOCKED, GFP_NOFS);
  2527. set_state_private(block_group_cache, chunk_offset,
  2528. (unsigned long)cache);
  2529. ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
  2530. sizeof(cache->item));
  2531. BUG_ON(ret);
  2532. finish_current_insert(trans, extent_root);
  2533. ret = del_pending_extents(trans, extent_root);
  2534. BUG_ON(ret);
  2535. set_avail_alloc_bits(extent_root->fs_info, type);
  2536. return 0;
  2537. }