extent-tree.c 38 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555
  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_METADATA;
  533. bit_to_set = BLOCK_GROUP_DATA;
  534. cache->item.flags |=
  535. BTRFS_BLOCK_GROUP_DATA;
  536. } else {
  537. bit_to_clear = BLOCK_GROUP_DATA;
  538. bit_to_set = BLOCK_GROUP_METADATA;
  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. u64 ptr;
  1319. int ret;
  1320. while(1) {
  1321. ret = find_first_extent_bit(&info->block_group_cache, 0,
  1322. &start, &end, (unsigned int)-1);
  1323. if (ret)
  1324. break;
  1325. ret = get_state_private(&info->block_group_cache, start, &ptr);
  1326. if (!ret)
  1327. kfree((void *)(unsigned long)ptr);
  1328. clear_extent_bits(&info->block_group_cache, start,
  1329. end, (unsigned int)-1, GFP_NOFS);
  1330. }
  1331. while(1) {
  1332. ret = find_first_extent_bit(&info->free_space_cache, 0,
  1333. &start, &end, EXTENT_DIRTY);
  1334. if (ret)
  1335. break;
  1336. clear_extent_dirty(&info->free_space_cache, start,
  1337. end, GFP_NOFS);
  1338. }
  1339. return 0;
  1340. }
  1341. int btrfs_read_block_groups(struct btrfs_root *root)
  1342. {
  1343. struct btrfs_path *path;
  1344. int ret;
  1345. int err = 0;
  1346. int bit;
  1347. struct btrfs_block_group_cache *cache;
  1348. struct btrfs_fs_info *info = root->fs_info;
  1349. struct extent_map_tree *block_group_cache;
  1350. struct btrfs_key key;
  1351. struct btrfs_key found_key;
  1352. struct extent_buffer *leaf;
  1353. block_group_cache = &info->block_group_cache;
  1354. root = info->extent_root;
  1355. key.objectid = 0;
  1356. key.offset = BTRFS_BLOCK_GROUP_SIZE;
  1357. btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  1358. path = btrfs_alloc_path();
  1359. if (!path)
  1360. return -ENOMEM;
  1361. while(1) {
  1362. ret = btrfs_search_slot(NULL, info->extent_root,
  1363. &key, path, 0, 0);
  1364. if (ret != 0) {
  1365. err = ret;
  1366. break;
  1367. }
  1368. leaf = path->nodes[0];
  1369. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  1370. cache = kmalloc(sizeof(*cache), GFP_NOFS);
  1371. if (!cache) {
  1372. err = -1;
  1373. break;
  1374. }
  1375. read_extent_buffer(leaf, &cache->item,
  1376. btrfs_item_ptr_offset(leaf, path->slots[0]),
  1377. sizeof(cache->item));
  1378. memcpy(&cache->key, &found_key, sizeof(found_key));
  1379. cache->cached = 0;
  1380. key.objectid = found_key.objectid + found_key.offset;
  1381. btrfs_release_path(root, path);
  1382. if (cache->item.flags & BTRFS_BLOCK_GROUP_DATA) {
  1383. bit = BLOCK_GROUP_DATA;
  1384. cache->data = 1;
  1385. } else {
  1386. bit = BLOCK_GROUP_METADATA;
  1387. cache->data = 0;
  1388. }
  1389. /* use EXTENT_LOCKED to prevent merging */
  1390. set_extent_bits(block_group_cache, found_key.objectid,
  1391. found_key.objectid + found_key.offset - 1,
  1392. bit | EXTENT_LOCKED, GFP_NOFS);
  1393. set_state_private(block_group_cache, found_key.objectid,
  1394. (unsigned long)cache);
  1395. if (key.objectid >=
  1396. btrfs_super_total_bytes(&info->super_copy))
  1397. break;
  1398. }
  1399. btrfs_free_path(path);
  1400. return 0;
  1401. }