extent-tree.c 38 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553
  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 "ctree.h"
  20. #include "disk-io.h"
  21. #include "print-tree.h"
  22. #include "transaction.h"
  23. #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
  24. #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  25. #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  26. static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  27. btrfs_root *extent_root);
  28. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  29. btrfs_root *extent_root);
  30. static int cache_block_group(struct btrfs_root *root,
  31. struct btrfs_block_group_cache *block_group)
  32. {
  33. struct btrfs_path *path;
  34. int ret;
  35. struct btrfs_key key;
  36. struct extent_buffer *leaf;
  37. struct extent_map_tree *free_space_cache;
  38. int slot;
  39. u64 last = 0;
  40. u64 hole_size;
  41. u64 first_free;
  42. int found = 0;
  43. root = root->fs_info->extent_root;
  44. free_space_cache = &root->fs_info->free_space_cache;
  45. if (block_group->cached)
  46. return 0;
  47. path = btrfs_alloc_path();
  48. if (!path)
  49. return -ENOMEM;
  50. path->reada = 2;
  51. first_free = block_group->key.objectid;
  52. key.objectid = block_group->key.objectid;
  53. key.offset = 0;
  54. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  55. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  56. if (ret < 0)
  57. return ret;
  58. if (ret && path->slots[0] > 0)
  59. path->slots[0]--;
  60. while(1) {
  61. leaf = path->nodes[0];
  62. slot = path->slots[0];
  63. if (slot >= btrfs_header_nritems(leaf)) {
  64. ret = btrfs_next_leaf(root, path);
  65. if (ret < 0)
  66. goto err;
  67. if (ret == 0) {
  68. continue;
  69. } else {
  70. break;
  71. }
  72. }
  73. btrfs_item_key_to_cpu(leaf, &key, slot);
  74. if (key.objectid < block_group->key.objectid) {
  75. if (key.objectid + key.offset > first_free)
  76. first_free = key.objectid + key.offset;
  77. goto next;
  78. }
  79. if (key.objectid >= block_group->key.objectid +
  80. block_group->key.offset) {
  81. break;
  82. }
  83. if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
  84. if (!found) {
  85. last = first_free;
  86. found = 1;
  87. }
  88. if (key.objectid > last) {
  89. hole_size = key.objectid - last;
  90. set_extent_dirty(free_space_cache, last,
  91. last + hole_size - 1,
  92. GFP_NOFS);
  93. }
  94. last = key.objectid + key.offset;
  95. }
  96. next:
  97. path->slots[0]++;
  98. }
  99. if (!found)
  100. last = first_free;
  101. if (block_group->key.objectid +
  102. block_group->key.offset > last) {
  103. hole_size = block_group->key.objectid +
  104. block_group->key.offset - last;
  105. set_extent_dirty(free_space_cache, last,
  106. last + hole_size - 1, GFP_NOFS);
  107. }
  108. block_group->cached = 1;
  109. err:
  110. btrfs_free_path(path);
  111. return 0;
  112. }
  113. struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
  114. btrfs_fs_info *info,
  115. u64 bytenr)
  116. {
  117. struct extent_map_tree *block_group_cache;
  118. struct btrfs_block_group_cache *block_group = NULL;
  119. u64 ptr;
  120. u64 start;
  121. u64 end;
  122. int ret;
  123. block_group_cache = &info->block_group_cache;
  124. ret = find_first_extent_bit(block_group_cache,
  125. bytenr, &start, &end,
  126. BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA);
  127. if (ret) {
  128. return NULL;
  129. }
  130. ret = get_state_private(block_group_cache, start, &ptr);
  131. if (ret)
  132. return NULL;
  133. block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  134. if (block_group->key.objectid <= bytenr && bytenr <=
  135. block_group->key.objectid + block_group->key.offset)
  136. return block_group;
  137. return NULL;
  138. }
  139. static u64 find_search_start(struct btrfs_root *root,
  140. struct btrfs_block_group_cache **cache_ret,
  141. u64 search_start, int num, int data)
  142. {
  143. int ret;
  144. struct btrfs_block_group_cache *cache = *cache_ret;
  145. u64 last;
  146. u64 start = 0;
  147. u64 end = 0;
  148. again:
  149. ret = cache_block_group(root, cache);
  150. if (ret)
  151. goto out;
  152. last = max(search_start, cache->key.objectid);
  153. while(1) {
  154. ret = find_first_extent_bit(&root->fs_info->free_space_cache,
  155. last, &start, &end, EXTENT_DIRTY);
  156. if (ret) {
  157. goto new_group;
  158. }
  159. start = max(last, start);
  160. last = end + 1;
  161. if (end + 1 - start < num)
  162. continue;
  163. if (start + num >= cache->key.objectid + cache->key.offset)
  164. goto new_group;
  165. return start;
  166. }
  167. out:
  168. return search_start;
  169. new_group:
  170. last = cache->key.objectid + cache->key.offset;
  171. cache = btrfs_lookup_block_group(root->fs_info, last);
  172. if (!cache) {
  173. return search_start;
  174. }
  175. cache = btrfs_find_block_group(root, cache, last, data, 0);
  176. *cache_ret = cache;
  177. goto again;
  178. }
  179. static u64 div_factor(u64 num, int factor)
  180. {
  181. num *= factor;
  182. do_div(num, 10);
  183. return num;
  184. }
  185. struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
  186. struct btrfs_block_group_cache
  187. *hint, u64 search_start,
  188. int data, int owner)
  189. {
  190. struct btrfs_block_group_cache *cache;
  191. struct extent_map_tree *block_group_cache;
  192. struct btrfs_block_group_cache *found_group = NULL;
  193. struct btrfs_fs_info *info = root->fs_info;
  194. u64 used;
  195. u64 last = 0;
  196. u64 hint_last;
  197. u64 start;
  198. u64 end;
  199. u64 free_check;
  200. u64 ptr;
  201. int bit;
  202. int ret;
  203. int full_search = 0;
  204. int factor = 8;
  205. int data_swap = 0;
  206. block_group_cache = &info->block_group_cache;
  207. if (!owner)
  208. factor = 5;
  209. if (data)
  210. bit = BLOCK_GROUP_DATA;
  211. else
  212. bit = BLOCK_GROUP_METADATA;
  213. if (search_start) {
  214. struct btrfs_block_group_cache *shint;
  215. shint = btrfs_lookup_block_group(info, search_start);
  216. if (shint && shint->data == data) {
  217. used = btrfs_block_group_used(&shint->item);
  218. if (used < div_factor(shint->key.offset, factor)) {
  219. return shint;
  220. }
  221. }
  222. }
  223. if (hint && hint->data == data) {
  224. used = btrfs_block_group_used(&hint->item);
  225. if (used < div_factor(hint->key.offset, factor)) {
  226. return hint;
  227. }
  228. last = hint->key.objectid + hint->key.offset;
  229. hint_last = last;
  230. } else {
  231. if (hint)
  232. hint_last = max(hint->key.objectid, search_start);
  233. else
  234. hint_last = search_start;
  235. last = hint_last;
  236. }
  237. again:
  238. while(1) {
  239. ret = find_first_extent_bit(block_group_cache, last,
  240. &start, &end, bit);
  241. if (ret)
  242. break;
  243. ret = get_state_private(block_group_cache, start, &ptr);
  244. if (ret)
  245. break;
  246. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  247. last = cache->key.objectid + cache->key.offset;
  248. used = btrfs_block_group_used(&cache->item);
  249. if (full_search)
  250. free_check = cache->key.offset;
  251. else
  252. free_check = div_factor(cache->key.offset, factor);
  253. if (used < free_check) {
  254. found_group = cache;
  255. goto found;
  256. }
  257. cond_resched();
  258. }
  259. if (!full_search) {
  260. last = search_start;
  261. full_search = 1;
  262. goto again;
  263. }
  264. if (!data_swap) {
  265. data_swap = 1;
  266. bit = BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA;
  267. last = search_start;
  268. goto again;
  269. }
  270. found:
  271. return found_group;
  272. }
  273. int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  274. struct btrfs_root *root,
  275. u64 bytenr, u64 num_bytes)
  276. {
  277. struct btrfs_path *path;
  278. int ret;
  279. struct btrfs_key key;
  280. struct extent_buffer *l;
  281. struct btrfs_extent_item *item;
  282. u32 refs;
  283. WARN_ON(num_bytes < root->sectorsize);
  284. path = btrfs_alloc_path();
  285. if (!path)
  286. return -ENOMEM;
  287. key.objectid = bytenr;
  288. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  289. key.offset = num_bytes;
  290. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  291. 0, 1);
  292. if (ret < 0)
  293. return ret;
  294. if (ret != 0) {
  295. BUG();
  296. }
  297. BUG_ON(ret != 0);
  298. l = path->nodes[0];
  299. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  300. refs = btrfs_extent_refs(l, item);
  301. btrfs_set_extent_refs(l, item, refs + 1);
  302. btrfs_mark_buffer_dirty(path->nodes[0]);
  303. btrfs_release_path(root->fs_info->extent_root, path);
  304. btrfs_free_path(path);
  305. finish_current_insert(trans, root->fs_info->extent_root);
  306. del_pending_extents(trans, root->fs_info->extent_root);
  307. return 0;
  308. }
  309. int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
  310. struct btrfs_root *root)
  311. {
  312. finish_current_insert(trans, root->fs_info->extent_root);
  313. del_pending_extents(trans, root->fs_info->extent_root);
  314. return 0;
  315. }
  316. static int lookup_extent_ref(struct btrfs_trans_handle *trans,
  317. struct btrfs_root *root, u64 bytenr,
  318. u64 num_bytes, u32 *refs)
  319. {
  320. struct btrfs_path *path;
  321. int ret;
  322. struct btrfs_key key;
  323. struct extent_buffer *l;
  324. struct btrfs_extent_item *item;
  325. WARN_ON(num_bytes < root->sectorsize);
  326. path = btrfs_alloc_path();
  327. key.objectid = bytenr;
  328. key.offset = num_bytes;
  329. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  330. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  331. 0, 0);
  332. if (ret < 0)
  333. goto out;
  334. if (ret != 0) {
  335. btrfs_print_leaf(root, path->nodes[0]);
  336. printk("failed to find block number %Lu\n", bytenr);
  337. BUG();
  338. }
  339. l = path->nodes[0];
  340. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  341. *refs = btrfs_extent_refs(l, item);
  342. out:
  343. btrfs_free_path(path);
  344. return 0;
  345. }
  346. int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
  347. struct btrfs_root *root)
  348. {
  349. return btrfs_inc_extent_ref(trans, root, root->node->start,
  350. root->node->len);
  351. }
  352. int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  353. struct extent_buffer *buf)
  354. {
  355. u64 bytenr;
  356. u32 nritems;
  357. struct btrfs_key key;
  358. struct btrfs_file_extent_item *fi;
  359. int i;
  360. int level;
  361. int ret;
  362. int faili;
  363. int err;
  364. if (!root->ref_cows)
  365. return 0;
  366. level = btrfs_header_level(buf);
  367. nritems = btrfs_header_nritems(buf);
  368. for (i = 0; i < nritems; i++) {
  369. if (level == 0) {
  370. u64 disk_bytenr;
  371. btrfs_item_key_to_cpu(buf, &key, i);
  372. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  373. continue;
  374. fi = btrfs_item_ptr(buf, i,
  375. struct btrfs_file_extent_item);
  376. if (btrfs_file_extent_type(buf, fi) ==
  377. BTRFS_FILE_EXTENT_INLINE)
  378. continue;
  379. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  380. if (disk_bytenr == 0)
  381. continue;
  382. ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
  383. btrfs_file_extent_disk_num_bytes(buf, fi));
  384. if (ret) {
  385. faili = i;
  386. goto fail;
  387. }
  388. } else {
  389. bytenr = btrfs_node_blockptr(buf, i);
  390. ret = btrfs_inc_extent_ref(trans, root, bytenr,
  391. btrfs_level_size(root, level - 1));
  392. if (ret) {
  393. faili = i;
  394. goto fail;
  395. }
  396. }
  397. }
  398. return 0;
  399. fail:
  400. WARN_ON(1);
  401. for (i =0; i < faili; i++) {
  402. if (level == 0) {
  403. u64 disk_bytenr;
  404. btrfs_item_key_to_cpu(buf, &key, i);
  405. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  406. continue;
  407. fi = btrfs_item_ptr(buf, i,
  408. struct btrfs_file_extent_item);
  409. if (btrfs_file_extent_type(buf, fi) ==
  410. BTRFS_FILE_EXTENT_INLINE)
  411. continue;
  412. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  413. if (disk_bytenr == 0)
  414. continue;
  415. err = btrfs_free_extent(trans, root, disk_bytenr,
  416. btrfs_file_extent_disk_num_bytes(buf,
  417. fi), 0);
  418. BUG_ON(err);
  419. } else {
  420. bytenr = btrfs_node_blockptr(buf, i);
  421. err = btrfs_free_extent(trans, root, bytenr,
  422. btrfs_level_size(root, level - 1), 0);
  423. BUG_ON(err);
  424. }
  425. }
  426. return ret;
  427. }
  428. static int write_one_cache_group(struct btrfs_trans_handle *trans,
  429. struct btrfs_root *root,
  430. struct btrfs_path *path,
  431. struct btrfs_block_group_cache *cache)
  432. {
  433. int ret;
  434. int pending_ret;
  435. struct btrfs_root *extent_root = root->fs_info->extent_root;
  436. unsigned long bi;
  437. struct extent_buffer *leaf;
  438. ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
  439. if (ret < 0)
  440. goto fail;
  441. BUG_ON(ret);
  442. leaf = path->nodes[0];
  443. bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
  444. write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
  445. btrfs_mark_buffer_dirty(leaf);
  446. btrfs_release_path(extent_root, path);
  447. fail:
  448. finish_current_insert(trans, extent_root);
  449. pending_ret = del_pending_extents(trans, extent_root);
  450. if (ret)
  451. return ret;
  452. if (pending_ret)
  453. return pending_ret;
  454. return 0;
  455. }
  456. int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
  457. struct btrfs_root *root)
  458. {
  459. struct extent_map_tree *block_group_cache;
  460. struct btrfs_block_group_cache *cache;
  461. int ret;
  462. int err = 0;
  463. int werr = 0;
  464. struct btrfs_path *path;
  465. u64 last = 0;
  466. u64 start;
  467. u64 end;
  468. u64 ptr;
  469. block_group_cache = &root->fs_info->block_group_cache;
  470. path = btrfs_alloc_path();
  471. if (!path)
  472. return -ENOMEM;
  473. while(1) {
  474. ret = find_first_extent_bit(block_group_cache, last,
  475. &start, &end, BLOCK_GROUP_DIRTY);
  476. if (ret)
  477. break;
  478. last = end + 1;
  479. ret = get_state_private(block_group_cache, start, &ptr);
  480. if (ret)
  481. break;
  482. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  483. err = write_one_cache_group(trans, root,
  484. path, cache);
  485. /*
  486. * if we fail to write the cache group, we want
  487. * to keep it marked dirty in hopes that a later
  488. * write will work
  489. */
  490. if (err) {
  491. werr = err;
  492. continue;
  493. }
  494. clear_extent_bits(block_group_cache, start, end,
  495. BLOCK_GROUP_DIRTY, GFP_NOFS);
  496. }
  497. btrfs_free_path(path);
  498. return werr;
  499. }
  500. static int update_block_group(struct btrfs_trans_handle *trans,
  501. struct btrfs_root *root,
  502. u64 bytenr, u64 num_bytes, int alloc,
  503. int mark_free, int data)
  504. {
  505. struct btrfs_block_group_cache *cache;
  506. struct btrfs_fs_info *info = root->fs_info;
  507. u64 total = num_bytes;
  508. u64 old_val;
  509. u64 byte_in_group;
  510. u64 start;
  511. u64 end;
  512. while(total) {
  513. cache = btrfs_lookup_block_group(info, bytenr);
  514. if (!cache) {
  515. return -1;
  516. }
  517. byte_in_group = bytenr - cache->key.objectid;
  518. WARN_ON(byte_in_group > cache->key.offset);
  519. start = cache->key.objectid;
  520. end = start + cache->key.offset - 1;
  521. set_extent_bits(&info->block_group_cache, start, end,
  522. BLOCK_GROUP_DIRTY, GFP_NOFS);
  523. old_val = btrfs_block_group_used(&cache->item);
  524. num_bytes = min(total, cache->key.offset - byte_in_group);
  525. if (alloc) {
  526. if (cache->data != data &&
  527. old_val < (cache->key.offset >> 1)) {
  528. int bit_to_clear;
  529. int bit_to_set;
  530. cache->data = data;
  531. if (data) {
  532. bit_to_clear = BLOCK_GROUP_DATA;
  533. bit_to_set = BLOCK_GROUP_METADATA;
  534. cache->item.flags |=
  535. BTRFS_BLOCK_GROUP_DATA;
  536. } else {
  537. bit_to_clear = BLOCK_GROUP_METADATA;
  538. bit_to_set = BLOCK_GROUP_DATA;
  539. cache->item.flags &=
  540. ~BTRFS_BLOCK_GROUP_DATA;
  541. }
  542. clear_extent_bits(&info->block_group_cache,
  543. start, end, bit_to_clear,
  544. GFP_NOFS);
  545. set_extent_bits(&info->block_group_cache,
  546. start, end, bit_to_set,
  547. GFP_NOFS);
  548. }
  549. old_val += num_bytes;
  550. } else {
  551. old_val -= num_bytes;
  552. if (mark_free) {
  553. set_extent_dirty(&info->free_space_cache,
  554. bytenr, bytenr + num_bytes - 1,
  555. GFP_NOFS);
  556. }
  557. }
  558. btrfs_set_block_group_used(&cache->item, old_val);
  559. total -= num_bytes;
  560. bytenr += num_bytes;
  561. }
  562. return 0;
  563. }
  564. int btrfs_copy_pinned(struct btrfs_root *root, struct extent_map_tree *copy)
  565. {
  566. u64 last = 0;
  567. u64 start;
  568. u64 end;
  569. struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
  570. int ret;
  571. while(1) {
  572. ret = find_first_extent_bit(pinned_extents, last,
  573. &start, &end, EXTENT_DIRTY);
  574. if (ret)
  575. break;
  576. set_extent_dirty(copy, start, end, GFP_NOFS);
  577. last = end + 1;
  578. }
  579. return 0;
  580. }
  581. int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
  582. struct btrfs_root *root,
  583. struct extent_map_tree *unpin)
  584. {
  585. u64 start;
  586. u64 end;
  587. int ret;
  588. struct extent_map_tree *pinned_extents = &root->fs_info->pinned_extents;
  589. struct extent_map_tree *free_space_cache;
  590. free_space_cache = &root->fs_info->free_space_cache;
  591. while(1) {
  592. ret = find_first_extent_bit(unpin, 0, &start, &end,
  593. EXTENT_DIRTY);
  594. if (ret)
  595. break;
  596. clear_extent_dirty(pinned_extents, start, end,
  597. GFP_NOFS);
  598. clear_extent_dirty(unpin, start, end, GFP_NOFS);
  599. set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
  600. }
  601. return 0;
  602. }
  603. static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  604. btrfs_root *extent_root)
  605. {
  606. struct btrfs_key ins;
  607. struct btrfs_extent_item extent_item;
  608. int ret;
  609. int err = 0;
  610. u64 start;
  611. u64 end;
  612. struct btrfs_fs_info *info = extent_root->fs_info;
  613. btrfs_set_stack_extent_refs(&extent_item, 1);
  614. btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
  615. btrfs_set_stack_extent_owner(&extent_item,
  616. extent_root->root_key.objectid);
  617. while(1) {
  618. ret = find_first_extent_bit(&info->extent_ins, 0, &start,
  619. &end, EXTENT_LOCKED);
  620. if (ret)
  621. break;
  622. ins.objectid = start;
  623. ins.offset = end + 1 - start;
  624. err = btrfs_insert_item(trans, extent_root, &ins,
  625. &extent_item, sizeof(extent_item));
  626. clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
  627. GFP_NOFS);
  628. }
  629. return 0;
  630. }
  631. static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
  632. int pending)
  633. {
  634. int err = 0;
  635. struct extent_buffer *buf;
  636. if (!pending) {
  637. buf = btrfs_find_tree_block(root, bytenr, num_bytes);
  638. if (buf) {
  639. if (btrfs_buffer_uptodate(buf)) {
  640. u64 transid =
  641. root->fs_info->running_transaction->transid;
  642. if (btrfs_header_generation(buf) == transid) {
  643. free_extent_buffer(buf);
  644. return 0;
  645. }
  646. }
  647. free_extent_buffer(buf);
  648. }
  649. set_extent_dirty(&root->fs_info->pinned_extents,
  650. bytenr, bytenr + num_bytes - 1, GFP_NOFS);
  651. } else {
  652. set_extent_bits(&root->fs_info->pending_del,
  653. bytenr, bytenr + num_bytes - 1,
  654. EXTENT_LOCKED, GFP_NOFS);
  655. }
  656. BUG_ON(err < 0);
  657. return 0;
  658. }
  659. /*
  660. * remove an extent from the root, returns 0 on success
  661. */
  662. static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  663. *root, u64 bytenr, u64 num_bytes, int pin,
  664. int mark_free)
  665. {
  666. struct btrfs_path *path;
  667. struct btrfs_key key;
  668. struct btrfs_fs_info *info = root->fs_info;
  669. struct btrfs_root *extent_root = info->extent_root;
  670. struct extent_buffer *leaf;
  671. int ret;
  672. struct btrfs_extent_item *ei;
  673. u32 refs;
  674. key.objectid = bytenr;
  675. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  676. key.offset = num_bytes;
  677. path = btrfs_alloc_path();
  678. if (!path)
  679. return -ENOMEM;
  680. ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
  681. if (ret < 0)
  682. return ret;
  683. BUG_ON(ret);
  684. leaf = path->nodes[0];
  685. ei = btrfs_item_ptr(leaf, path->slots[0],
  686. struct btrfs_extent_item);
  687. refs = btrfs_extent_refs(leaf, ei);
  688. BUG_ON(refs == 0);
  689. refs -= 1;
  690. btrfs_set_extent_refs(leaf, ei, refs);
  691. btrfs_mark_buffer_dirty(leaf);
  692. if (refs == 0) {
  693. u64 super_used;
  694. u64 root_used;
  695. if (pin) {
  696. ret = pin_down_bytes(root, bytenr, num_bytes, 0);
  697. BUG_ON(ret);
  698. }
  699. /* block accounting for super block */
  700. super_used = btrfs_super_bytes_used(&info->super_copy);
  701. btrfs_set_super_bytes_used(&info->super_copy,
  702. super_used - num_bytes);
  703. /* block accounting for root item */
  704. root_used = btrfs_root_used(&root->root_item);
  705. btrfs_set_root_used(&root->root_item,
  706. root_used - num_bytes);
  707. ret = btrfs_del_item(trans, extent_root, path);
  708. if (ret) {
  709. return ret;
  710. }
  711. ret = update_block_group(trans, root, bytenr, num_bytes, 0,
  712. mark_free, 0);
  713. BUG_ON(ret);
  714. }
  715. btrfs_free_path(path);
  716. finish_current_insert(trans, extent_root);
  717. return ret;
  718. }
  719. /*
  720. * find all the blocks marked as pending in the radix tree and remove
  721. * them from the extent map
  722. */
  723. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  724. btrfs_root *extent_root)
  725. {
  726. int ret;
  727. int err = 0;
  728. u64 start;
  729. u64 end;
  730. struct extent_map_tree *pending_del;
  731. struct extent_map_tree *pinned_extents;
  732. pending_del = &extent_root->fs_info->pending_del;
  733. pinned_extents = &extent_root->fs_info->pinned_extents;
  734. while(1) {
  735. ret = find_first_extent_bit(pending_del, 0, &start, &end,
  736. EXTENT_LOCKED);
  737. if (ret)
  738. break;
  739. set_extent_dirty(pinned_extents, start, end, GFP_NOFS);
  740. clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
  741. GFP_NOFS);
  742. ret = __free_extent(trans, extent_root,
  743. start, end + 1 - start, 0, 0);
  744. if (ret)
  745. err = ret;
  746. }
  747. return err;
  748. }
  749. /*
  750. * remove an extent from the root, returns 0 on success
  751. */
  752. int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  753. *root, u64 bytenr, u64 num_bytes, int pin)
  754. {
  755. struct btrfs_root *extent_root = root->fs_info->extent_root;
  756. int pending_ret;
  757. int ret;
  758. WARN_ON(num_bytes < root->sectorsize);
  759. if (root == extent_root) {
  760. pin_down_bytes(root, bytenr, num_bytes, 1);
  761. return 0;
  762. }
  763. ret = __free_extent(trans, root, bytenr, num_bytes, pin, pin == 0);
  764. pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
  765. return ret ? ret : pending_ret;
  766. }
  767. /*
  768. * walks the btree of allocated extents and find a hole of a given size.
  769. * The key ins is changed to record the hole:
  770. * ins->objectid == block start
  771. * ins->flags = BTRFS_EXTENT_ITEM_KEY
  772. * ins->offset == number of blocks
  773. * Any available blocks before search_start are skipped.
  774. */
  775. static int find_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  776. *orig_root, u64 num_bytes, u64 empty_size,
  777. u64 search_start, u64 search_end, u64 hint_byte,
  778. struct btrfs_key *ins, u64 exclude_start,
  779. u64 exclude_nr, int data)
  780. {
  781. struct btrfs_path *path;
  782. struct btrfs_key key;
  783. int ret;
  784. u64 hole_size = 0;
  785. int slot = 0;
  786. u64 last_byte = 0;
  787. u64 orig_search_start = search_start;
  788. int start_found;
  789. struct extent_buffer *l;
  790. struct btrfs_root * root = orig_root->fs_info->extent_root;
  791. struct btrfs_fs_info *info = root->fs_info;
  792. u64 total_needed = num_bytes;
  793. int level;
  794. struct btrfs_block_group_cache *block_group;
  795. int full_scan = 0;
  796. int wrapped = 0;
  797. WARN_ON(num_bytes < root->sectorsize);
  798. btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
  799. level = btrfs_header_level(root->node);
  800. if (search_end == (u64)-1)
  801. search_end = btrfs_super_total_bytes(&info->super_copy);
  802. if (hint_byte) {
  803. block_group = btrfs_lookup_block_group(info, hint_byte);
  804. block_group = btrfs_find_block_group(root, block_group,
  805. hint_byte, data, 1);
  806. } else {
  807. block_group = btrfs_find_block_group(root,
  808. trans->block_group, 0,
  809. data, 1);
  810. }
  811. total_needed += empty_size;
  812. path = btrfs_alloc_path();
  813. check_failed:
  814. search_start = find_search_start(root, &block_group,
  815. search_start, total_needed, data);
  816. btrfs_init_path(path);
  817. ins->objectid = search_start;
  818. ins->offset = 0;
  819. start_found = 0;
  820. path->reada = 2;
  821. ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
  822. if (ret < 0)
  823. goto error;
  824. if (path->slots[0] > 0) {
  825. path->slots[0]--;
  826. }
  827. l = path->nodes[0];
  828. btrfs_item_key_to_cpu(l, &key, path->slots[0]);
  829. /*
  830. * a rare case, go back one key if we hit a block group item
  831. * instead of an extent item
  832. */
  833. if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY &&
  834. key.objectid + key.offset >= search_start) {
  835. ins->objectid = key.objectid;
  836. ins->offset = key.offset - 1;
  837. btrfs_release_path(root, path);
  838. ret = btrfs_search_slot(trans, root, ins, path, 0, 0);
  839. if (ret < 0)
  840. goto error;
  841. if (path->slots[0] > 0) {
  842. path->slots[0]--;
  843. }
  844. }
  845. while (1) {
  846. l = path->nodes[0];
  847. slot = path->slots[0];
  848. if (slot >= btrfs_header_nritems(l)) {
  849. ret = btrfs_next_leaf(root, path);
  850. if (ret == 0)
  851. continue;
  852. if (ret < 0)
  853. goto error;
  854. search_start = max(search_start,
  855. block_group->key.objectid);
  856. if (!start_found) {
  857. ins->objectid = search_start;
  858. ins->offset = search_end - search_start;
  859. start_found = 1;
  860. goto check_pending;
  861. }
  862. ins->objectid = last_byte > search_start ?
  863. last_byte : search_start;
  864. ins->offset = search_end - ins->objectid;
  865. BUG_ON(ins->objectid >= search_end);
  866. goto check_pending;
  867. }
  868. btrfs_item_key_to_cpu(l, &key, slot);
  869. if (key.objectid >= search_start && key.objectid > last_byte &&
  870. start_found) {
  871. if (last_byte < search_start)
  872. last_byte = search_start;
  873. hole_size = key.objectid - last_byte;
  874. if (hole_size >= num_bytes) {
  875. ins->objectid = last_byte;
  876. ins->offset = hole_size;
  877. goto check_pending;
  878. }
  879. }
  880. if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY) {
  881. if (!start_found) {
  882. last_byte = key.objectid;
  883. start_found = 1;
  884. }
  885. goto next;
  886. }
  887. start_found = 1;
  888. last_byte = key.objectid + key.offset;
  889. if (!full_scan && last_byte >= block_group->key.objectid +
  890. block_group->key.offset) {
  891. btrfs_release_path(root, path);
  892. search_start = block_group->key.objectid +
  893. block_group->key.offset;
  894. goto new_group;
  895. }
  896. next:
  897. path->slots[0]++;
  898. cond_resched();
  899. }
  900. check_pending:
  901. /* we have to make sure we didn't find an extent that has already
  902. * been allocated by the map tree or the original allocation
  903. */
  904. btrfs_release_path(root, path);
  905. BUG_ON(ins->objectid < search_start);
  906. if (ins->objectid + num_bytes >= search_end)
  907. goto enospc;
  908. if (!full_scan && ins->objectid + num_bytes >= block_group->
  909. key.objectid + block_group->key.offset) {
  910. search_start = block_group->key.objectid +
  911. block_group->key.offset;
  912. goto new_group;
  913. }
  914. if (test_range_bit(&info->extent_ins, ins->objectid,
  915. ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
  916. search_start = ins->objectid + num_bytes;
  917. goto new_group;
  918. }
  919. if (test_range_bit(&info->pinned_extents, ins->objectid,
  920. ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
  921. search_start = ins->objectid + num_bytes;
  922. goto new_group;
  923. }
  924. if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
  925. ins->objectid < exclude_start + exclude_nr)) {
  926. search_start = exclude_start + exclude_nr;
  927. goto new_group;
  928. }
  929. if (!data) {
  930. block_group = btrfs_lookup_block_group(info, ins->objectid);
  931. if (block_group)
  932. trans->block_group = block_group;
  933. }
  934. ins->offset = num_bytes;
  935. btrfs_free_path(path);
  936. return 0;
  937. new_group:
  938. if (search_start + num_bytes >= search_end) {
  939. enospc:
  940. search_start = orig_search_start;
  941. if (full_scan) {
  942. ret = -ENOSPC;
  943. goto error;
  944. }
  945. if (wrapped) {
  946. if (!full_scan)
  947. total_needed -= empty_size;
  948. full_scan = 1;
  949. } else
  950. wrapped = 1;
  951. }
  952. block_group = btrfs_lookup_block_group(info, search_start);
  953. cond_resched();
  954. if (!full_scan)
  955. block_group = btrfs_find_block_group(root, block_group,
  956. search_start, data, 0);
  957. goto check_failed;
  958. error:
  959. btrfs_release_path(root, path);
  960. btrfs_free_path(path);
  961. return ret;
  962. }
  963. /*
  964. * finds a free extent and does all the dirty work required for allocation
  965. * returns the key for the extent through ins, and a tree buffer for
  966. * the first block of the extent through buf.
  967. *
  968. * returns 0 if everything worked, non-zero otherwise.
  969. */
  970. int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
  971. struct btrfs_root *root, u64 owner,
  972. u64 num_bytes, u64 empty_size, u64 hint_byte,
  973. u64 search_end, struct btrfs_key *ins, int data)
  974. {
  975. int ret;
  976. int pending_ret;
  977. u64 super_used, root_used;
  978. u64 search_start = 0;
  979. struct btrfs_fs_info *info = root->fs_info;
  980. struct btrfs_root *extent_root = info->extent_root;
  981. struct btrfs_extent_item extent_item;
  982. btrfs_set_stack_extent_refs(&extent_item, 1);
  983. btrfs_set_stack_extent_owner(&extent_item, owner);
  984. WARN_ON(num_bytes < root->sectorsize);
  985. ret = find_free_extent(trans, root, num_bytes, empty_size,
  986. search_start, search_end, hint_byte, ins,
  987. trans->alloc_exclude_start,
  988. trans->alloc_exclude_nr, data);
  989. BUG_ON(ret);
  990. if (ret)
  991. return ret;
  992. /* block accounting for super block */
  993. super_used = btrfs_super_bytes_used(&info->super_copy);
  994. btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
  995. /* block accounting for root item */
  996. root_used = btrfs_root_used(&root->root_item);
  997. btrfs_set_root_used(&root->root_item, root_used + num_bytes);
  998. clear_extent_dirty(&root->fs_info->free_space_cache,
  999. ins->objectid, ins->objectid + ins->offset - 1,
  1000. GFP_NOFS);
  1001. if (root == extent_root) {
  1002. set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
  1003. ins->objectid + ins->offset - 1,
  1004. EXTENT_LOCKED, GFP_NOFS);
  1005. WARN_ON(data == 1);
  1006. goto update_block;
  1007. }
  1008. WARN_ON(trans->alloc_exclude_nr);
  1009. trans->alloc_exclude_start = ins->objectid;
  1010. trans->alloc_exclude_nr = ins->offset;
  1011. ret = btrfs_insert_item(trans, extent_root, ins, &extent_item,
  1012. sizeof(extent_item));
  1013. trans->alloc_exclude_start = 0;
  1014. trans->alloc_exclude_nr = 0;
  1015. BUG_ON(ret);
  1016. finish_current_insert(trans, extent_root);
  1017. pending_ret = del_pending_extents(trans, extent_root);
  1018. if (ret) {
  1019. return ret;
  1020. }
  1021. if (pending_ret) {
  1022. return pending_ret;
  1023. }
  1024. update_block:
  1025. ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0,
  1026. data);
  1027. BUG_ON(ret);
  1028. return 0;
  1029. }
  1030. /*
  1031. * helper function to allocate a block for a given tree
  1032. * returns the tree buffer or NULL.
  1033. */
  1034. struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  1035. struct btrfs_root *root,
  1036. u32 blocksize, u64 hint,
  1037. u64 empty_size)
  1038. {
  1039. struct btrfs_key ins;
  1040. int ret;
  1041. struct extent_buffer *buf;
  1042. ret = btrfs_alloc_extent(trans, root, root->root_key.objectid,
  1043. blocksize, empty_size, hint,
  1044. (u64)-1, &ins, 0);
  1045. if (ret) {
  1046. BUG_ON(ret > 0);
  1047. return ERR_PTR(ret);
  1048. }
  1049. buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
  1050. if (!buf) {
  1051. btrfs_free_extent(trans, root, ins.objectid, blocksize, 0);
  1052. return ERR_PTR(-ENOMEM);
  1053. }
  1054. btrfs_set_buffer_uptodate(buf);
  1055. set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
  1056. buf->start + buf->len - 1, GFP_NOFS);
  1057. set_extent_bits(&BTRFS_I(root->fs_info->btree_inode)->extent_tree,
  1058. buf->start, buf->start + buf->len - 1,
  1059. EXTENT_CSUM, GFP_NOFS);
  1060. buf->flags |= EXTENT_CSUM;
  1061. btrfs_set_buffer_defrag(buf);
  1062. trans->blocks_used++;
  1063. return buf;
  1064. }
  1065. static int drop_leaf_ref(struct btrfs_trans_handle *trans,
  1066. struct btrfs_root *root, struct extent_buffer *leaf)
  1067. {
  1068. struct btrfs_key key;
  1069. struct btrfs_file_extent_item *fi;
  1070. int i;
  1071. int nritems;
  1072. int ret;
  1073. BUG_ON(!btrfs_is_leaf(leaf));
  1074. nritems = btrfs_header_nritems(leaf);
  1075. for (i = 0; i < nritems; i++) {
  1076. u64 disk_bytenr;
  1077. btrfs_item_key_to_cpu(leaf, &key, i);
  1078. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  1079. continue;
  1080. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  1081. if (btrfs_file_extent_type(leaf, fi) ==
  1082. BTRFS_FILE_EXTENT_INLINE)
  1083. continue;
  1084. /*
  1085. * FIXME make sure to insert a trans record that
  1086. * repeats the snapshot del on crash
  1087. */
  1088. disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
  1089. if (disk_bytenr == 0)
  1090. continue;
  1091. ret = btrfs_free_extent(trans, root, disk_bytenr,
  1092. btrfs_file_extent_disk_num_bytes(leaf, fi), 0);
  1093. BUG_ON(ret);
  1094. }
  1095. return 0;
  1096. }
  1097. static void reada_walk_down(struct btrfs_root *root,
  1098. struct extent_buffer *node)
  1099. {
  1100. int i;
  1101. u32 nritems;
  1102. u64 bytenr;
  1103. int ret;
  1104. u32 refs;
  1105. int level;
  1106. u32 blocksize;
  1107. nritems = btrfs_header_nritems(node);
  1108. level = btrfs_header_level(node);
  1109. for (i = 0; i < nritems; i++) {
  1110. bytenr = btrfs_node_blockptr(node, i);
  1111. blocksize = btrfs_level_size(root, level - 1);
  1112. ret = lookup_extent_ref(NULL, root, bytenr, blocksize, &refs);
  1113. BUG_ON(ret);
  1114. if (refs != 1)
  1115. continue;
  1116. mutex_unlock(&root->fs_info->fs_mutex);
  1117. ret = readahead_tree_block(root, bytenr, blocksize);
  1118. cond_resched();
  1119. mutex_lock(&root->fs_info->fs_mutex);
  1120. if (ret)
  1121. break;
  1122. }
  1123. }
  1124. /*
  1125. * helper function for drop_snapshot, this walks down the tree dropping ref
  1126. * counts as it goes.
  1127. */
  1128. static int walk_down_tree(struct btrfs_trans_handle *trans, struct btrfs_root
  1129. *root, struct btrfs_path *path, int *level)
  1130. {
  1131. struct extent_buffer *next;
  1132. struct extent_buffer *cur;
  1133. u64 bytenr;
  1134. u32 blocksize;
  1135. int ret;
  1136. u32 refs;
  1137. WARN_ON(*level < 0);
  1138. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1139. ret = lookup_extent_ref(trans, root,
  1140. path->nodes[*level]->start,
  1141. path->nodes[*level]->len, &refs);
  1142. BUG_ON(ret);
  1143. if (refs > 1)
  1144. goto out;
  1145. /*
  1146. * walk down to the last node level and free all the leaves
  1147. */
  1148. while(*level >= 0) {
  1149. WARN_ON(*level < 0);
  1150. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1151. cur = path->nodes[*level];
  1152. if (*level > 0 && path->slots[*level] == 0)
  1153. reada_walk_down(root, cur);
  1154. if (btrfs_header_level(cur) != *level)
  1155. WARN_ON(1);
  1156. if (path->slots[*level] >=
  1157. btrfs_header_nritems(cur))
  1158. break;
  1159. if (*level == 0) {
  1160. ret = drop_leaf_ref(trans, root, cur);
  1161. BUG_ON(ret);
  1162. break;
  1163. }
  1164. bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  1165. blocksize = btrfs_level_size(root, *level - 1);
  1166. ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
  1167. BUG_ON(ret);
  1168. if (refs != 1) {
  1169. path->slots[*level]++;
  1170. ret = btrfs_free_extent(trans, root, bytenr,
  1171. blocksize, 1);
  1172. BUG_ON(ret);
  1173. continue;
  1174. }
  1175. next = btrfs_find_tree_block(root, bytenr, blocksize);
  1176. if (!next || !btrfs_buffer_uptodate(next)) {
  1177. free_extent_buffer(next);
  1178. mutex_unlock(&root->fs_info->fs_mutex);
  1179. next = read_tree_block(root, bytenr, blocksize);
  1180. mutex_lock(&root->fs_info->fs_mutex);
  1181. /* we dropped the lock, check one more time */
  1182. ret = lookup_extent_ref(trans, root, bytenr,
  1183. blocksize, &refs);
  1184. BUG_ON(ret);
  1185. if (refs != 1) {
  1186. path->slots[*level]++;
  1187. free_extent_buffer(next);
  1188. ret = btrfs_free_extent(trans, root,
  1189. bytenr, blocksize, 1);
  1190. BUG_ON(ret);
  1191. continue;
  1192. }
  1193. }
  1194. WARN_ON(*level <= 0);
  1195. if (path->nodes[*level-1])
  1196. free_extent_buffer(path->nodes[*level-1]);
  1197. path->nodes[*level-1] = next;
  1198. *level = btrfs_header_level(next);
  1199. path->slots[*level] = 0;
  1200. }
  1201. out:
  1202. WARN_ON(*level < 0);
  1203. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1204. ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
  1205. path->nodes[*level]->len, 1);
  1206. free_extent_buffer(path->nodes[*level]);
  1207. path->nodes[*level] = NULL;
  1208. *level += 1;
  1209. BUG_ON(ret);
  1210. return 0;
  1211. }
  1212. /*
  1213. * helper for dropping snapshots. This walks back up the tree in the path
  1214. * to find the first node higher up where we haven't yet gone through
  1215. * all the slots
  1216. */
  1217. static int walk_up_tree(struct btrfs_trans_handle *trans, struct btrfs_root
  1218. *root, struct btrfs_path *path, int *level)
  1219. {
  1220. int i;
  1221. int slot;
  1222. int ret;
  1223. struct btrfs_root_item *root_item = &root->root_item;
  1224. for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
  1225. slot = path->slots[i];
  1226. if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
  1227. struct extent_buffer *node;
  1228. struct btrfs_disk_key disk_key;
  1229. node = path->nodes[i];
  1230. path->slots[i]++;
  1231. *level = i;
  1232. WARN_ON(*level == 0);
  1233. btrfs_node_key(node, &disk_key, path->slots[i]);
  1234. memcpy(&root_item->drop_progress,
  1235. &disk_key, sizeof(disk_key));
  1236. root_item->drop_level = i;
  1237. return 0;
  1238. } else {
  1239. ret = btrfs_free_extent(trans, root,
  1240. path->nodes[*level]->start,
  1241. path->nodes[*level]->len, 1);
  1242. BUG_ON(ret);
  1243. free_extent_buffer(path->nodes[*level]);
  1244. path->nodes[*level] = NULL;
  1245. *level = i + 1;
  1246. }
  1247. }
  1248. return 1;
  1249. }
  1250. /*
  1251. * drop the reference count on the tree rooted at 'snap'. This traverses
  1252. * the tree freeing any blocks that have a ref count of zero after being
  1253. * decremented.
  1254. */
  1255. int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
  1256. *root)
  1257. {
  1258. int ret = 0;
  1259. int wret;
  1260. int level;
  1261. struct btrfs_path *path;
  1262. int i;
  1263. int orig_level;
  1264. struct btrfs_root_item *root_item = &root->root_item;
  1265. path = btrfs_alloc_path();
  1266. BUG_ON(!path);
  1267. level = btrfs_header_level(root->node);
  1268. orig_level = level;
  1269. if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
  1270. path->nodes[level] = root->node;
  1271. extent_buffer_get(root->node);
  1272. path->slots[level] = 0;
  1273. } else {
  1274. struct btrfs_key key;
  1275. struct btrfs_disk_key found_key;
  1276. struct extent_buffer *node;
  1277. btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
  1278. level = root_item->drop_level;
  1279. path->lowest_level = level;
  1280. wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  1281. if (wret < 0) {
  1282. ret = wret;
  1283. goto out;
  1284. }
  1285. node = path->nodes[level];
  1286. btrfs_node_key(node, &found_key, path->slots[level]);
  1287. WARN_ON(memcmp(&found_key, &root_item->drop_progress,
  1288. sizeof(found_key)));
  1289. }
  1290. while(1) {
  1291. wret = walk_down_tree(trans, root, path, &level);
  1292. if (wret > 0)
  1293. break;
  1294. if (wret < 0)
  1295. ret = wret;
  1296. wret = walk_up_tree(trans, root, path, &level);
  1297. if (wret > 0)
  1298. break;
  1299. if (wret < 0)
  1300. ret = wret;
  1301. ret = -EAGAIN;
  1302. break;
  1303. }
  1304. for (i = 0; i <= orig_level; i++) {
  1305. if (path->nodes[i]) {
  1306. free_extent_buffer(path->nodes[i]);
  1307. path->nodes[i] = NULL;
  1308. }
  1309. }
  1310. out:
  1311. btrfs_free_path(path);
  1312. return ret;
  1313. }
  1314. int btrfs_free_block_groups(struct btrfs_fs_info *info)
  1315. {
  1316. u64 start;
  1317. u64 end;
  1318. int ret;
  1319. while(1) {
  1320. ret = find_first_extent_bit(&info->block_group_cache, 0,
  1321. &start, &end, (unsigned int)-1);
  1322. if (ret)
  1323. break;
  1324. clear_extent_bits(&info->block_group_cache, start,
  1325. end, (unsigned int)-1, GFP_NOFS);
  1326. }
  1327. while(1) {
  1328. ret = find_first_extent_bit(&info->free_space_cache, 0,
  1329. &start, &end, EXTENT_DIRTY);
  1330. if (ret)
  1331. break;
  1332. clear_extent_dirty(&info->free_space_cache, start,
  1333. end, GFP_NOFS);
  1334. }
  1335. return 0;
  1336. }
  1337. int btrfs_read_block_groups(struct btrfs_root *root)
  1338. {
  1339. struct btrfs_path *path;
  1340. int ret;
  1341. int err = 0;
  1342. int bit;
  1343. struct btrfs_block_group_cache *cache;
  1344. struct btrfs_fs_info *info = root->fs_info;
  1345. struct extent_map_tree *block_group_cache;
  1346. struct btrfs_key key;
  1347. struct btrfs_key found_key;
  1348. struct extent_buffer *leaf;
  1349. block_group_cache = &info->block_group_cache;
  1350. root = info->extent_root;
  1351. key.objectid = 0;
  1352. key.offset = BTRFS_BLOCK_GROUP_SIZE;
  1353. btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  1354. path = btrfs_alloc_path();
  1355. if (!path)
  1356. return -ENOMEM;
  1357. while(1) {
  1358. ret = btrfs_search_slot(NULL, info->extent_root,
  1359. &key, path, 0, 0);
  1360. if (ret != 0) {
  1361. err = ret;
  1362. break;
  1363. }
  1364. leaf = path->nodes[0];
  1365. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  1366. cache = kmalloc(sizeof(*cache), GFP_NOFS);
  1367. if (!cache) {
  1368. err = -1;
  1369. break;
  1370. }
  1371. read_extent_buffer(leaf, &cache->item,
  1372. btrfs_item_ptr_offset(leaf, path->slots[0]),
  1373. sizeof(cache->item));
  1374. memcpy(&cache->key, &found_key, sizeof(found_key));
  1375. cache->cached = 0;
  1376. key.objectid = found_key.objectid + found_key.offset;
  1377. btrfs_release_path(root, path);
  1378. if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
  1379. bit = BLOCK_GROUP_DATA;
  1380. cache->data = 1;
  1381. } else {
  1382. bit = BLOCK_GROUP_METADATA;
  1383. cache->data = 0;
  1384. }
  1385. /* use EXTENT_LOCKED to prevent merging */
  1386. set_extent_bits(block_group_cache, found_key.objectid,
  1387. found_key.objectid + found_key.offset - 1,
  1388. bit | EXTENT_LOCKED, GFP_NOFS);
  1389. set_state_private(block_group_cache, found_key.objectid,
  1390. (unsigned long)cache);
  1391. if (key.objectid >=
  1392. btrfs_super_total_bytes(&info->super_copy))
  1393. break;
  1394. }
  1395. btrfs_free_path(path);
  1396. return 0;
  1397. }