extent-tree.c 68 KB

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