extent-tree.c 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "kerncompat.h"
  4. #include "radix-tree.h"
  5. #include "ctree.h"
  6. #include "disk-io.h"
  7. #include "print-tree.h"
  8. static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
  9. u64 search_start, u64 search_end,
  10. struct btrfs_key *ins);
  11. static int finish_current_insert(struct ctree_root *extent_root);
  12. static int run_pending(struct ctree_root *extent_root);
  13. /*
  14. * pending extents are blocks that we're trying to allocate in the extent
  15. * map while trying to grow the map because of other allocations. To avoid
  16. * recursing, they are tagged in the radix tree and cleaned up after
  17. * other allocations are done. The pending tag is also used in the same
  18. * manner for deletes.
  19. */
  20. #define CTREE_EXTENT_PENDING_DEL 0
  21. static int inc_block_ref(struct ctree_root *root, u64 blocknr)
  22. {
  23. struct ctree_path path;
  24. int ret;
  25. struct btrfs_key key;
  26. struct leaf *l;
  27. struct extent_item *item;
  28. struct btrfs_key ins;
  29. u32 refs;
  30. find_free_extent(root->extent_root, 0, 0, (u64)-1, &ins);
  31. init_path(&path);
  32. key.objectid = blocknr;
  33. key.flags = 0;
  34. key.offset = 1;
  35. ret = search_slot(root->extent_root, &key, &path, 0, 1);
  36. if (ret != 0)
  37. BUG();
  38. BUG_ON(ret != 0);
  39. l = &path.nodes[0]->leaf;
  40. item = (struct extent_item *)(l->data + btrfs_item_offset(l->items +
  41. path.slots[0]));
  42. refs = btrfs_extent_refs(item);
  43. btrfs_set_extent_refs(item, refs + 1);
  44. BUG_ON(list_empty(&path.nodes[0]->dirty));
  45. release_path(root->extent_root, &path);
  46. finish_current_insert(root->extent_root);
  47. run_pending(root->extent_root);
  48. return 0;
  49. }
  50. static int lookup_block_ref(struct ctree_root *root, u64 blocknr, u32 *refs)
  51. {
  52. struct ctree_path path;
  53. int ret;
  54. struct btrfs_key key;
  55. struct leaf *l;
  56. struct extent_item *item;
  57. init_path(&path);
  58. key.objectid = blocknr;
  59. key.flags = 0;
  60. key.offset = 1;
  61. ret = search_slot(root->extent_root, &key, &path, 0, 0);
  62. if (ret != 0)
  63. BUG();
  64. l = &path.nodes[0]->leaf;
  65. item = (struct extent_item *)(l->data +
  66. btrfs_item_offset(l->items +
  67. path.slots[0]));
  68. *refs = btrfs_extent_refs(item);
  69. release_path(root->extent_root, &path);
  70. return 0;
  71. }
  72. int btrfs_inc_ref(struct ctree_root *root, struct tree_buffer *buf)
  73. {
  74. u64 blocknr;
  75. int i;
  76. if (root == root->extent_root)
  77. return 0;
  78. if (btrfs_is_leaf(&buf->node))
  79. return 0;
  80. for (i = 0; i < btrfs_header_nritems(&buf->node.header); i++) {
  81. blocknr = btrfs_node_blockptr(&buf->node, i);
  82. inc_block_ref(root, blocknr);
  83. }
  84. return 0;
  85. }
  86. int btrfs_finish_extent_commit(struct ctree_root *root)
  87. {
  88. struct ctree_root *extent_root = root->extent_root;
  89. unsigned long gang[8];
  90. int ret;
  91. int i;
  92. while(1) {
  93. ret = radix_tree_gang_lookup(&extent_root->pinned_radix,
  94. (void **)gang, 0,
  95. ARRAY_SIZE(gang));
  96. if (!ret)
  97. break;
  98. for (i = 0; i < ret; i++) {
  99. radix_tree_delete(&extent_root->pinned_radix, gang[i]);
  100. }
  101. }
  102. extent_root->last_insert.objectid = 0;
  103. extent_root->last_insert.offset = 0;
  104. return 0;
  105. }
  106. static int finish_current_insert(struct ctree_root *extent_root)
  107. {
  108. struct btrfs_key ins;
  109. struct extent_item extent_item;
  110. int i;
  111. int ret;
  112. btrfs_set_extent_refs(&extent_item, 1);
  113. btrfs_set_extent_owner(&extent_item,
  114. btrfs_header_parentid(&extent_root->node->node.header));
  115. ins.offset = 1;
  116. ins.flags = 0;
  117. for (i = 0; i < extent_root->current_insert.flags; i++) {
  118. ins.objectid = extent_root->current_insert.objectid + i;
  119. ret = insert_item(extent_root, &ins, &extent_item,
  120. sizeof(extent_item));
  121. BUG_ON(ret);
  122. }
  123. extent_root->current_insert.offset = 0;
  124. return 0;
  125. }
  126. /*
  127. * remove an extent from the root, returns 0 on success
  128. */
  129. int __free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
  130. {
  131. struct ctree_path path;
  132. struct btrfs_key key;
  133. struct ctree_root *extent_root = root->extent_root;
  134. int ret;
  135. struct btrfs_item *item;
  136. struct extent_item *ei;
  137. struct btrfs_key ins;
  138. u32 refs;
  139. key.objectid = blocknr;
  140. key.flags = 0;
  141. key.offset = num_blocks;
  142. find_free_extent(root, 0, 0, (u64)-1, &ins);
  143. init_path(&path);
  144. ret = search_slot(extent_root, &key, &path, -1, 1);
  145. if (ret) {
  146. printf("failed to find %Lu\n", key.objectid);
  147. print_tree(extent_root, extent_root->node);
  148. printf("failed to find %Lu\n", key.objectid);
  149. BUG();
  150. }
  151. item = path.nodes[0]->leaf.items + path.slots[0];
  152. ei = (struct extent_item *)(path.nodes[0]->leaf.data +
  153. btrfs_item_offset(item));
  154. BUG_ON(ei->refs == 0);
  155. refs = btrfs_extent_refs(ei) - 1;
  156. btrfs_set_extent_refs(ei, refs);
  157. if (refs == 0) {
  158. if (root == extent_root) {
  159. int err;
  160. radix_tree_preload(GFP_KERNEL);
  161. err = radix_tree_insert(&extent_root->pinned_radix,
  162. blocknr, (void *)blocknr);
  163. BUG_ON(err);
  164. radix_tree_preload_end();
  165. }
  166. ret = del_item(extent_root, &path);
  167. if (root != extent_root &&
  168. extent_root->last_insert.objectid < blocknr)
  169. extent_root->last_insert.objectid = blocknr;
  170. if (ret)
  171. BUG();
  172. }
  173. release_path(extent_root, &path);
  174. finish_current_insert(extent_root);
  175. return ret;
  176. }
  177. /*
  178. * find all the blocks marked as pending in the radix tree and remove
  179. * them from the extent map
  180. */
  181. static int del_pending_extents(struct ctree_root *extent_root)
  182. {
  183. int ret;
  184. struct tree_buffer *gang[4];
  185. int i;
  186. while(1) {
  187. ret = radix_tree_gang_lookup_tag(&extent_root->cache_radix,
  188. (void **)gang, 0,
  189. ARRAY_SIZE(gang),
  190. CTREE_EXTENT_PENDING_DEL);
  191. if (!ret)
  192. break;
  193. for (i = 0; i < ret; i++) {
  194. ret = __free_extent(extent_root, gang[i]->blocknr, 1);
  195. radix_tree_tag_clear(&extent_root->cache_radix,
  196. gang[i]->blocknr,
  197. CTREE_EXTENT_PENDING_DEL);
  198. tree_block_release(extent_root, gang[i]);
  199. }
  200. }
  201. return 0;
  202. }
  203. static int run_pending(struct ctree_root *extent_root)
  204. {
  205. while(radix_tree_tagged(&extent_root->cache_radix,
  206. CTREE_EXTENT_PENDING_DEL))
  207. del_pending_extents(extent_root);
  208. return 0;
  209. }
  210. /*
  211. * remove an extent from the root, returns 0 on success
  212. */
  213. int free_extent(struct ctree_root *root, u64 blocknr, u64 num_blocks)
  214. {
  215. struct btrfs_key key;
  216. struct ctree_root *extent_root = root->extent_root;
  217. struct tree_buffer *t;
  218. int pending_ret;
  219. int ret;
  220. if (root == extent_root) {
  221. t = find_tree_block(root, blocknr);
  222. radix_tree_tag_set(&root->cache_radix, blocknr,
  223. CTREE_EXTENT_PENDING_DEL);
  224. return 0;
  225. }
  226. key.objectid = blocknr;
  227. key.flags = 0;
  228. key.offset = num_blocks;
  229. ret = __free_extent(root, blocknr, num_blocks);
  230. pending_ret = run_pending(root->extent_root);
  231. return ret ? ret : pending_ret;
  232. }
  233. /*
  234. * walks the btree of allocated extents and find a hole of a given size.
  235. * The key ins is changed to record the hole:
  236. * ins->objectid == block start
  237. * ins->flags = 0
  238. * ins->offset == number of blocks
  239. * Any available blocks before search_start are skipped.
  240. */
  241. static int find_free_extent(struct ctree_root *orig_root, u64 num_blocks,
  242. u64 search_start, u64 search_end,
  243. struct btrfs_key *ins)
  244. {
  245. struct ctree_path path;
  246. struct btrfs_key key;
  247. int ret;
  248. u64 hole_size = 0;
  249. int slot = 0;
  250. u64 last_block;
  251. u64 test_block;
  252. int start_found;
  253. struct leaf *l;
  254. struct ctree_root * root = orig_root->extent_root;
  255. int total_needed = num_blocks;
  256. total_needed += (btrfs_header_level(&root->node->node.header) + 1) * 3;
  257. if (root->last_insert.objectid > search_start)
  258. search_start = root->last_insert.objectid;
  259. check_failed:
  260. init_path(&path);
  261. ins->objectid = search_start;
  262. ins->offset = 0;
  263. ins->flags = 0;
  264. start_found = 0;
  265. ret = search_slot(root, ins, &path, 0, 0);
  266. if (ret < 0)
  267. goto error;
  268. if (path.slots[0] > 0)
  269. path.slots[0]--;
  270. while (1) {
  271. l = &path.nodes[0]->leaf;
  272. slot = path.slots[0];
  273. if (slot >= btrfs_header_nritems(&l->header)) {
  274. ret = next_leaf(root, &path);
  275. if (ret == 0)
  276. continue;
  277. if (ret < 0)
  278. goto error;
  279. if (!start_found) {
  280. ins->objectid = search_start;
  281. ins->offset = (u64)-1;
  282. start_found = 1;
  283. goto check_pending;
  284. }
  285. ins->objectid = last_block > search_start ?
  286. last_block : search_start;
  287. ins->offset = (u64)-1;
  288. goto check_pending;
  289. }
  290. btrfs_disk_key_to_cpu(&key, &l->items[slot].key);
  291. if (key.objectid >= search_start) {
  292. if (start_found) {
  293. if (last_block < search_start)
  294. last_block = search_start;
  295. hole_size = key.objectid - last_block;
  296. if (hole_size > total_needed) {
  297. ins->objectid = last_block;
  298. ins->offset = hole_size;
  299. goto check_pending;
  300. }
  301. }
  302. }
  303. start_found = 1;
  304. last_block = key.objectid + key.offset;
  305. path.slots[0]++;
  306. }
  307. // FIXME -ENOSPC
  308. check_pending:
  309. /* we have to make sure we didn't find an extent that has already
  310. * been allocated by the map tree or the original allocation
  311. */
  312. release_path(root, &path);
  313. BUG_ON(ins->objectid < search_start);
  314. for (test_block = ins->objectid;
  315. test_block < ins->objectid + total_needed; test_block++) {
  316. if (radix_tree_lookup(&root->pinned_radix, test_block)) {
  317. search_start = test_block + 1;
  318. goto check_failed;
  319. }
  320. }
  321. BUG_ON(root->current_insert.offset);
  322. root->current_insert.offset = total_needed - num_blocks;
  323. root->current_insert.objectid = ins->objectid + num_blocks;
  324. root->current_insert.flags = 0;
  325. root->last_insert.objectid = ins->objectid;
  326. ins->offset = num_blocks;
  327. return 0;
  328. error:
  329. release_path(root, &path);
  330. return ret;
  331. }
  332. /*
  333. * finds a free extent and does all the dirty work required for allocation
  334. * returns the key for the extent through ins, and a tree buffer for
  335. * the first block of the extent through buf.
  336. *
  337. * returns 0 if everything worked, non-zero otherwise.
  338. */
  339. int alloc_extent(struct ctree_root *root, u64 num_blocks, u64 search_start,
  340. u64 search_end, u64 owner, struct btrfs_key *ins)
  341. {
  342. int ret;
  343. int pending_ret;
  344. struct ctree_root *extent_root = root->extent_root;
  345. struct extent_item extent_item;
  346. btrfs_set_extent_refs(&extent_item, 1);
  347. btrfs_set_extent_owner(&extent_item, owner);
  348. if (root == extent_root) {
  349. BUG_ON(extent_root->current_insert.offset == 0);
  350. BUG_ON(num_blocks != 1);
  351. BUG_ON(extent_root->current_insert.flags ==
  352. extent_root->current_insert.offset);
  353. ins->offset = 1;
  354. ins->objectid = extent_root->current_insert.objectid +
  355. extent_root->current_insert.flags++;
  356. return 0;
  357. }
  358. ret = find_free_extent(root, num_blocks, search_start,
  359. search_end, ins);
  360. if (ret)
  361. return ret;
  362. ret = insert_item(extent_root, ins, &extent_item,
  363. sizeof(extent_item));
  364. finish_current_insert(extent_root);
  365. pending_ret = run_pending(extent_root);
  366. if (ret)
  367. return ret;
  368. if (pending_ret)
  369. return pending_ret;
  370. return 0;
  371. }
  372. /*
  373. * helper function to allocate a block for a given tree
  374. * returns the tree buffer or NULL.
  375. */
  376. struct tree_buffer *alloc_free_block(struct ctree_root *root)
  377. {
  378. struct btrfs_key ins;
  379. int ret;
  380. struct tree_buffer *buf;
  381. ret = alloc_extent(root, 1, 0, (unsigned long)-1,
  382. btrfs_header_parentid(&root->node->node.header),
  383. &ins);
  384. if (ret) {
  385. BUG();
  386. return NULL;
  387. }
  388. buf = find_tree_block(root, ins.objectid);
  389. dirty_tree_block(root, buf);
  390. return buf;
  391. }
  392. int walk_down_tree(struct ctree_root *root, struct ctree_path *path, int *level)
  393. {
  394. struct tree_buffer *next;
  395. struct tree_buffer *cur;
  396. u64 blocknr;
  397. int ret;
  398. u32 refs;
  399. ret = lookup_block_ref(root, path->nodes[*level]->blocknr, &refs);
  400. BUG_ON(ret);
  401. if (refs > 1)
  402. goto out;
  403. while(*level > 0) {
  404. cur = path->nodes[*level];
  405. if (path->slots[*level] >=
  406. btrfs_header_nritems(&cur->node.header))
  407. break;
  408. blocknr = btrfs_node_blockptr(&cur->node, path->slots[*level]);
  409. ret = lookup_block_ref(root, blocknr, &refs);
  410. if (refs != 1 || *level == 1) {
  411. path->slots[*level]++;
  412. ret = free_extent(root, blocknr, 1);
  413. BUG_ON(ret);
  414. continue;
  415. }
  416. BUG_ON(ret);
  417. next = read_tree_block(root, blocknr);
  418. if (path->nodes[*level-1])
  419. tree_block_release(root, path->nodes[*level-1]);
  420. path->nodes[*level-1] = next;
  421. *level = btrfs_header_level(&next->node.header);
  422. path->slots[*level] = 0;
  423. }
  424. out:
  425. ret = free_extent(root, path->nodes[*level]->blocknr, 1);
  426. tree_block_release(root, path->nodes[*level]);
  427. path->nodes[*level] = NULL;
  428. *level += 1;
  429. BUG_ON(ret);
  430. return 0;
  431. }
  432. int walk_up_tree(struct ctree_root *root, struct ctree_path *path, int *level)
  433. {
  434. int i;
  435. int slot;
  436. int ret;
  437. for(i = *level; i < MAX_LEVEL - 1 && path->nodes[i]; i++) {
  438. slot = path->slots[i];
  439. if (slot <
  440. btrfs_header_nritems(&path->nodes[i]->node.header)- 1) {
  441. path->slots[i]++;
  442. *level = i;
  443. return 0;
  444. } else {
  445. ret = free_extent(root,
  446. path->nodes[*level]->blocknr, 1);
  447. tree_block_release(root, path->nodes[*level]);
  448. path->nodes[*level] = NULL;
  449. *level = i + 1;
  450. BUG_ON(ret);
  451. }
  452. }
  453. return 1;
  454. }
  455. int btrfs_drop_snapshot(struct ctree_root *root, struct tree_buffer *snap)
  456. {
  457. int ret;
  458. int level;
  459. struct ctree_path path;
  460. int i;
  461. int orig_level;
  462. init_path(&path);
  463. level = btrfs_header_level(&snap->node.header);
  464. orig_level = level;
  465. path.nodes[level] = snap;
  466. path.slots[level] = 0;
  467. while(1) {
  468. ret = walk_down_tree(root, &path, &level);
  469. if (ret > 0)
  470. break;
  471. ret = walk_up_tree(root, &path, &level);
  472. if (ret > 0)
  473. break;
  474. }
  475. for (i = 0; i <= orig_level; i++) {
  476. if (path.nodes[i]) {
  477. tree_block_release(root, path.nodes[i]);
  478. }
  479. }
  480. return 0;
  481. }