extent_map.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650
  1. // SPDX-License-Identifier: GPL-2.0
  2. #include <linux/err.h>
  3. #include <linux/slab.h>
  4. #include <linux/spinlock.h>
  5. #include "ctree.h"
  6. #include "volumes.h"
  7. #include "extent_map.h"
  8. #include "compression.h"
  9. static struct kmem_cache *extent_map_cache;
  10. int __init extent_map_init(void)
  11. {
  12. extent_map_cache = kmem_cache_create("btrfs_extent_map",
  13. sizeof(struct extent_map), 0,
  14. SLAB_MEM_SPREAD, NULL);
  15. if (!extent_map_cache)
  16. return -ENOMEM;
  17. return 0;
  18. }
  19. void __cold extent_map_exit(void)
  20. {
  21. kmem_cache_destroy(extent_map_cache);
  22. }
  23. /**
  24. * extent_map_tree_init - initialize extent map tree
  25. * @tree: tree to initialize
  26. *
  27. * Initialize the extent tree @tree. Should be called for each new inode
  28. * or other user of the extent_map interface.
  29. */
  30. void extent_map_tree_init(struct extent_map_tree *tree)
  31. {
  32. tree->map = RB_ROOT_CACHED;
  33. INIT_LIST_HEAD(&tree->modified_extents);
  34. rwlock_init(&tree->lock);
  35. }
  36. /**
  37. * alloc_extent_map - allocate new extent map structure
  38. *
  39. * Allocate a new extent_map structure. The new structure is
  40. * returned with a reference count of one and needs to be
  41. * freed using free_extent_map()
  42. */
  43. struct extent_map *alloc_extent_map(void)
  44. {
  45. struct extent_map *em;
  46. em = kmem_cache_zalloc(extent_map_cache, GFP_NOFS);
  47. if (!em)
  48. return NULL;
  49. RB_CLEAR_NODE(&em->rb_node);
  50. em->flags = 0;
  51. em->compress_type = BTRFS_COMPRESS_NONE;
  52. em->generation = 0;
  53. refcount_set(&em->refs, 1);
  54. INIT_LIST_HEAD(&em->list);
  55. return em;
  56. }
  57. /**
  58. * free_extent_map - drop reference count of an extent_map
  59. * @em: extent map being released
  60. *
  61. * Drops the reference out on @em by one and free the structure
  62. * if the reference count hits zero.
  63. */
  64. void free_extent_map(struct extent_map *em)
  65. {
  66. if (!em)
  67. return;
  68. WARN_ON(refcount_read(&em->refs) == 0);
  69. if (refcount_dec_and_test(&em->refs)) {
  70. WARN_ON(extent_map_in_tree(em));
  71. WARN_ON(!list_empty(&em->list));
  72. if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
  73. kfree(em->map_lookup);
  74. kmem_cache_free(extent_map_cache, em);
  75. }
  76. }
  77. /* simple helper to do math around the end of an extent, handling wrap */
  78. static u64 range_end(u64 start, u64 len)
  79. {
  80. if (start + len < start)
  81. return (u64)-1;
  82. return start + len;
  83. }
  84. static int tree_insert(struct rb_root_cached *root, struct extent_map *em)
  85. {
  86. struct rb_node **p = &root->rb_root.rb_node;
  87. struct rb_node *parent = NULL;
  88. struct extent_map *entry = NULL;
  89. struct rb_node *orig_parent = NULL;
  90. u64 end = range_end(em->start, em->len);
  91. bool leftmost = true;
  92. while (*p) {
  93. parent = *p;
  94. entry = rb_entry(parent, struct extent_map, rb_node);
  95. if (em->start < entry->start) {
  96. p = &(*p)->rb_left;
  97. } else if (em->start >= extent_map_end(entry)) {
  98. p = &(*p)->rb_right;
  99. leftmost = false;
  100. } else {
  101. return -EEXIST;
  102. }
  103. }
  104. orig_parent = parent;
  105. while (parent && em->start >= extent_map_end(entry)) {
  106. parent = rb_next(parent);
  107. entry = rb_entry(parent, struct extent_map, rb_node);
  108. }
  109. if (parent)
  110. if (end > entry->start && em->start < extent_map_end(entry))
  111. return -EEXIST;
  112. parent = orig_parent;
  113. entry = rb_entry(parent, struct extent_map, rb_node);
  114. while (parent && em->start < entry->start) {
  115. parent = rb_prev(parent);
  116. entry = rb_entry(parent, struct extent_map, rb_node);
  117. }
  118. if (parent)
  119. if (end > entry->start && em->start < extent_map_end(entry))
  120. return -EEXIST;
  121. rb_link_node(&em->rb_node, orig_parent, p);
  122. rb_insert_color_cached(&em->rb_node, root, leftmost);
  123. return 0;
  124. }
  125. /*
  126. * search through the tree for an extent_map with a given offset. If
  127. * it can't be found, try to find some neighboring extents
  128. */
  129. static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
  130. struct rb_node **prev_ret,
  131. struct rb_node **next_ret)
  132. {
  133. struct rb_node *n = root->rb_node;
  134. struct rb_node *prev = NULL;
  135. struct rb_node *orig_prev = NULL;
  136. struct extent_map *entry;
  137. struct extent_map *prev_entry = NULL;
  138. while (n) {
  139. entry = rb_entry(n, struct extent_map, rb_node);
  140. prev = n;
  141. prev_entry = entry;
  142. if (offset < entry->start)
  143. n = n->rb_left;
  144. else if (offset >= extent_map_end(entry))
  145. n = n->rb_right;
  146. else
  147. return n;
  148. }
  149. if (prev_ret) {
  150. orig_prev = prev;
  151. while (prev && offset >= extent_map_end(prev_entry)) {
  152. prev = rb_next(prev);
  153. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  154. }
  155. *prev_ret = prev;
  156. prev = orig_prev;
  157. }
  158. if (next_ret) {
  159. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  160. while (prev && offset < prev_entry->start) {
  161. prev = rb_prev(prev);
  162. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  163. }
  164. *next_ret = prev;
  165. }
  166. return NULL;
  167. }
  168. /* check to see if two extent_map structs are adjacent and safe to merge */
  169. static int mergable_maps(struct extent_map *prev, struct extent_map *next)
  170. {
  171. if (test_bit(EXTENT_FLAG_PINNED, &prev->flags))
  172. return 0;
  173. /*
  174. * don't merge compressed extents, we need to know their
  175. * actual size
  176. */
  177. if (test_bit(EXTENT_FLAG_COMPRESSED, &prev->flags))
  178. return 0;
  179. if (test_bit(EXTENT_FLAG_LOGGING, &prev->flags) ||
  180. test_bit(EXTENT_FLAG_LOGGING, &next->flags))
  181. return 0;
  182. /*
  183. * We don't want to merge stuff that hasn't been written to the log yet
  184. * since it may not reflect exactly what is on disk, and that would be
  185. * bad.
  186. */
  187. if (!list_empty(&prev->list) || !list_empty(&next->list))
  188. return 0;
  189. ASSERT(next->block_start != EXTENT_MAP_DELALLOC &&
  190. prev->block_start != EXTENT_MAP_DELALLOC);
  191. if (prev->map_lookup || next->map_lookup)
  192. ASSERT(test_bit(EXTENT_FLAG_FS_MAPPING, &prev->flags) &&
  193. test_bit(EXTENT_FLAG_FS_MAPPING, &next->flags));
  194. if (extent_map_end(prev) == next->start &&
  195. prev->flags == next->flags &&
  196. prev->map_lookup == next->map_lookup &&
  197. ((next->block_start == EXTENT_MAP_HOLE &&
  198. prev->block_start == EXTENT_MAP_HOLE) ||
  199. (next->block_start == EXTENT_MAP_INLINE &&
  200. prev->block_start == EXTENT_MAP_INLINE) ||
  201. (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
  202. next->block_start == extent_map_block_end(prev)))) {
  203. return 1;
  204. }
  205. return 0;
  206. }
  207. static void try_merge_map(struct extent_map_tree *tree, struct extent_map *em)
  208. {
  209. struct extent_map *merge = NULL;
  210. struct rb_node *rb;
  211. /*
  212. * We can't modify an extent map that is in the tree and that is being
  213. * used by another task, as it can cause that other task to see it in
  214. * inconsistent state during the merging. We always have 1 reference for
  215. * the tree and 1 for this task (which is unpinning the extent map or
  216. * clearing the logging flag), so anything > 2 means it's being used by
  217. * other tasks too.
  218. */
  219. if (refcount_read(&em->refs) > 2)
  220. return;
  221. if (em->start != 0) {
  222. rb = rb_prev(&em->rb_node);
  223. if (rb)
  224. merge = rb_entry(rb, struct extent_map, rb_node);
  225. if (rb && mergable_maps(merge, em)) {
  226. em->start = merge->start;
  227. em->orig_start = merge->orig_start;
  228. em->len += merge->len;
  229. em->block_len += merge->block_len;
  230. em->block_start = merge->block_start;
  231. em->mod_len = (em->mod_len + em->mod_start) - merge->mod_start;
  232. em->mod_start = merge->mod_start;
  233. em->generation = max(em->generation, merge->generation);
  234. rb_erase_cached(&merge->rb_node, &tree->map);
  235. RB_CLEAR_NODE(&merge->rb_node);
  236. free_extent_map(merge);
  237. }
  238. }
  239. rb = rb_next(&em->rb_node);
  240. if (rb)
  241. merge = rb_entry(rb, struct extent_map, rb_node);
  242. if (rb && mergable_maps(em, merge)) {
  243. em->len += merge->len;
  244. em->block_len += merge->block_len;
  245. rb_erase_cached(&merge->rb_node, &tree->map);
  246. RB_CLEAR_NODE(&merge->rb_node);
  247. em->mod_len = (merge->mod_start + merge->mod_len) - em->mod_start;
  248. em->generation = max(em->generation, merge->generation);
  249. free_extent_map(merge);
  250. }
  251. }
  252. /**
  253. * unpin_extent_cache - unpin an extent from the cache
  254. * @tree: tree to unpin the extent in
  255. * @start: logical offset in the file
  256. * @len: length of the extent
  257. * @gen: generation that this extent has been modified in
  258. *
  259. * Called after an extent has been written to disk properly. Set the generation
  260. * to the generation that actually added the file item to the inode so we know
  261. * we need to sync this extent when we call fsync().
  262. */
  263. int unpin_extent_cache(struct extent_map_tree *tree, u64 start, u64 len,
  264. u64 gen)
  265. {
  266. int ret = 0;
  267. struct extent_map *em;
  268. bool prealloc = false;
  269. write_lock(&tree->lock);
  270. em = lookup_extent_mapping(tree, start, len);
  271. WARN_ON(!em || em->start != start);
  272. if (!em)
  273. goto out;
  274. em->generation = gen;
  275. clear_bit(EXTENT_FLAG_PINNED, &em->flags);
  276. em->mod_start = em->start;
  277. em->mod_len = em->len;
  278. if (test_bit(EXTENT_FLAG_FILLING, &em->flags)) {
  279. prealloc = true;
  280. clear_bit(EXTENT_FLAG_FILLING, &em->flags);
  281. }
  282. try_merge_map(tree, em);
  283. if (prealloc) {
  284. em->mod_start = em->start;
  285. em->mod_len = em->len;
  286. }
  287. free_extent_map(em);
  288. out:
  289. write_unlock(&tree->lock);
  290. return ret;
  291. }
  292. void clear_em_logging(struct extent_map_tree *tree, struct extent_map *em)
  293. {
  294. clear_bit(EXTENT_FLAG_LOGGING, &em->flags);
  295. if (extent_map_in_tree(em))
  296. try_merge_map(tree, em);
  297. }
  298. static inline void setup_extent_mapping(struct extent_map_tree *tree,
  299. struct extent_map *em,
  300. int modified)
  301. {
  302. refcount_inc(&em->refs);
  303. em->mod_start = em->start;
  304. em->mod_len = em->len;
  305. if (modified)
  306. list_move(&em->list, &tree->modified_extents);
  307. else
  308. try_merge_map(tree, em);
  309. }
  310. static void extent_map_device_set_bits(struct extent_map *em, unsigned bits)
  311. {
  312. struct map_lookup *map = em->map_lookup;
  313. u64 stripe_size = em->orig_block_len;
  314. int i;
  315. for (i = 0; i < map->num_stripes; i++) {
  316. struct btrfs_bio_stripe *stripe = &map->stripes[i];
  317. struct btrfs_device *device = stripe->dev;
  318. set_extent_bits_nowait(&device->alloc_state, stripe->physical,
  319. stripe->physical + stripe_size - 1, bits);
  320. }
  321. }
  322. static void extent_map_device_clear_bits(struct extent_map *em, unsigned bits)
  323. {
  324. struct map_lookup *map = em->map_lookup;
  325. u64 stripe_size = em->orig_block_len;
  326. int i;
  327. for (i = 0; i < map->num_stripes; i++) {
  328. struct btrfs_bio_stripe *stripe = &map->stripes[i];
  329. struct btrfs_device *device = stripe->dev;
  330. __clear_extent_bit(&device->alloc_state, stripe->physical,
  331. stripe->physical + stripe_size - 1, bits,
  332. 0, 0, NULL, GFP_NOWAIT, NULL);
  333. }
  334. }
  335. /**
  336. * add_extent_mapping - add new extent map to the extent tree
  337. * @tree: tree to insert new map in
  338. * @em: map to insert
  339. *
  340. * Insert @em into @tree or perform a simple forward/backward merge with
  341. * existing mappings. The extent_map struct passed in will be inserted
  342. * into the tree directly, with an additional reference taken, or a
  343. * reference dropped if the merge attempt was successful.
  344. */
  345. int add_extent_mapping(struct extent_map_tree *tree,
  346. struct extent_map *em, int modified)
  347. {
  348. int ret = 0;
  349. lockdep_assert_held_write(&tree->lock);
  350. ret = tree_insert(&tree->map, em);
  351. if (ret)
  352. goto out;
  353. setup_extent_mapping(tree, em, modified);
  354. if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags)) {
  355. extent_map_device_set_bits(em, CHUNK_ALLOCATED);
  356. extent_map_device_clear_bits(em, CHUNK_TRIMMED);
  357. }
  358. out:
  359. return ret;
  360. }
  361. static struct extent_map *
  362. __lookup_extent_mapping(struct extent_map_tree *tree,
  363. u64 start, u64 len, int strict)
  364. {
  365. struct extent_map *em;
  366. struct rb_node *rb_node;
  367. struct rb_node *prev = NULL;
  368. struct rb_node *next = NULL;
  369. u64 end = range_end(start, len);
  370. rb_node = __tree_search(&tree->map.rb_root, start, &prev, &next);
  371. if (!rb_node) {
  372. if (prev)
  373. rb_node = prev;
  374. else if (next)
  375. rb_node = next;
  376. else
  377. return NULL;
  378. }
  379. em = rb_entry(rb_node, struct extent_map, rb_node);
  380. if (strict && !(end > em->start && start < extent_map_end(em)))
  381. return NULL;
  382. refcount_inc(&em->refs);
  383. return em;
  384. }
  385. /**
  386. * lookup_extent_mapping - lookup extent_map
  387. * @tree: tree to lookup in
  388. * @start: byte offset to start the search
  389. * @len: length of the lookup range
  390. *
  391. * Find and return the first extent_map struct in @tree that intersects the
  392. * [start, len] range. There may be additional objects in the tree that
  393. * intersect, so check the object returned carefully to make sure that no
  394. * additional lookups are needed.
  395. */
  396. struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
  397. u64 start, u64 len)
  398. {
  399. return __lookup_extent_mapping(tree, start, len, 1);
  400. }
  401. /**
  402. * search_extent_mapping - find a nearby extent map
  403. * @tree: tree to lookup in
  404. * @start: byte offset to start the search
  405. * @len: length of the lookup range
  406. *
  407. * Find and return the first extent_map struct in @tree that intersects the
  408. * [start, len] range.
  409. *
  410. * If one can't be found, any nearby extent may be returned
  411. */
  412. struct extent_map *search_extent_mapping(struct extent_map_tree *tree,
  413. u64 start, u64 len)
  414. {
  415. return __lookup_extent_mapping(tree, start, len, 0);
  416. }
  417. /**
  418. * remove_extent_mapping - removes an extent_map from the extent tree
  419. * @tree: extent tree to remove from
  420. * @em: extent map being removed
  421. *
  422. * Removes @em from @tree. No reference counts are dropped, and no checks
  423. * are done to see if the range is in use
  424. */
  425. void remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
  426. {
  427. WARN_ON(test_bit(EXTENT_FLAG_PINNED, &em->flags));
  428. rb_erase_cached(&em->rb_node, &tree->map);
  429. if (!test_bit(EXTENT_FLAG_LOGGING, &em->flags))
  430. list_del_init(&em->list);
  431. if (test_bit(EXTENT_FLAG_FS_MAPPING, &em->flags))
  432. extent_map_device_clear_bits(em, CHUNK_ALLOCATED);
  433. RB_CLEAR_NODE(&em->rb_node);
  434. }
  435. void replace_extent_mapping(struct extent_map_tree *tree,
  436. struct extent_map *cur,
  437. struct extent_map *new,
  438. int modified)
  439. {
  440. WARN_ON(test_bit(EXTENT_FLAG_PINNED, &cur->flags));
  441. ASSERT(extent_map_in_tree(cur));
  442. if (!test_bit(EXTENT_FLAG_LOGGING, &cur->flags))
  443. list_del_init(&cur->list);
  444. rb_replace_node_cached(&cur->rb_node, &new->rb_node, &tree->map);
  445. RB_CLEAR_NODE(&cur->rb_node);
  446. setup_extent_mapping(tree, new, modified);
  447. }
  448. static struct extent_map *next_extent_map(struct extent_map *em)
  449. {
  450. struct rb_node *next;
  451. next = rb_next(&em->rb_node);
  452. if (!next)
  453. return NULL;
  454. return container_of(next, struct extent_map, rb_node);
  455. }
  456. static struct extent_map *prev_extent_map(struct extent_map *em)
  457. {
  458. struct rb_node *prev;
  459. prev = rb_prev(&em->rb_node);
  460. if (!prev)
  461. return NULL;
  462. return container_of(prev, struct extent_map, rb_node);
  463. }
  464. /*
  465. * Helper for btrfs_get_extent. Given an existing extent in the tree,
  466. * the existing extent is the nearest extent to map_start,
  467. * and an extent that you want to insert, deal with overlap and insert
  468. * the best fitted new extent into the tree.
  469. */
  470. static noinline int merge_extent_mapping(struct extent_map_tree *em_tree,
  471. struct extent_map *existing,
  472. struct extent_map *em,
  473. u64 map_start)
  474. {
  475. struct extent_map *prev;
  476. struct extent_map *next;
  477. u64 start;
  478. u64 end;
  479. u64 start_diff;
  480. BUG_ON(map_start < em->start || map_start >= extent_map_end(em));
  481. if (existing->start > map_start) {
  482. next = existing;
  483. prev = prev_extent_map(next);
  484. } else {
  485. prev = existing;
  486. next = next_extent_map(prev);
  487. }
  488. start = prev ? extent_map_end(prev) : em->start;
  489. start = max_t(u64, start, em->start);
  490. end = next ? next->start : extent_map_end(em);
  491. end = min_t(u64, end, extent_map_end(em));
  492. start_diff = start - em->start;
  493. em->start = start;
  494. em->len = end - start;
  495. if (em->block_start < EXTENT_MAP_LAST_BYTE &&
  496. !test_bit(EXTENT_FLAG_COMPRESSED, &em->flags)) {
  497. em->block_start += start_diff;
  498. em->block_len = em->len;
  499. }
  500. return add_extent_mapping(em_tree, em, 0);
  501. }
  502. /**
  503. * btrfs_add_extent_mapping - add extent mapping into em_tree
  504. * @fs_info - used for tracepoint
  505. * @em_tree - the extent tree into which we want to insert the extent mapping
  506. * @em_in - extent we are inserting
  507. * @start - start of the logical range btrfs_get_extent() is requesting
  508. * @len - length of the logical range btrfs_get_extent() is requesting
  509. *
  510. * Note that @em_in's range may be different from [start, start+len),
  511. * but they must be overlapped.
  512. *
  513. * Insert @em_in into @em_tree. In case there is an overlapping range, handle
  514. * the -EEXIST by either:
  515. * a) Returning the existing extent in @em_in if @start is within the
  516. * existing em.
  517. * b) Merge the existing extent with @em_in passed in.
  518. *
  519. * Return 0 on success, otherwise -EEXIST.
  520. *
  521. */
  522. int btrfs_add_extent_mapping(struct btrfs_fs_info *fs_info,
  523. struct extent_map_tree *em_tree,
  524. struct extent_map **em_in, u64 start, u64 len)
  525. {
  526. int ret;
  527. struct extent_map *em = *em_in;
  528. ret = add_extent_mapping(em_tree, em, 0);
  529. /* it is possible that someone inserted the extent into the tree
  530. * while we had the lock dropped. It is also possible that
  531. * an overlapping map exists in the tree
  532. */
  533. if (ret == -EEXIST) {
  534. struct extent_map *existing;
  535. ret = 0;
  536. existing = search_extent_mapping(em_tree, start, len);
  537. trace_btrfs_handle_em_exist(fs_info, existing, em, start, len);
  538. /*
  539. * existing will always be non-NULL, since there must be
  540. * extent causing the -EEXIST.
  541. */
  542. if (start >= existing->start &&
  543. start < extent_map_end(existing)) {
  544. free_extent_map(em);
  545. *em_in = existing;
  546. ret = 0;
  547. } else {
  548. u64 orig_start = em->start;
  549. u64 orig_len = em->len;
  550. /*
  551. * The existing extent map is the one nearest to
  552. * the [start, start + len) range which overlaps
  553. */
  554. ret = merge_extent_mapping(em_tree, existing,
  555. em, start);
  556. if (ret) {
  557. free_extent_map(em);
  558. *em_in = NULL;
  559. WARN_ONCE(ret,
  560. "unexpected error %d: merge existing(start %llu len %llu) with em(start %llu len %llu)\n",
  561. ret, existing->start, existing->len,
  562. orig_start, orig_len);
  563. }
  564. free_extent_map(existing);
  565. }
  566. }
  567. ASSERT(ret == 0 || ret == -EEXIST);
  568. return ret;
  569. }