extent_map.c 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284
  1. #include <linux/err.h>
  2. #include <linux/gfp.h>
  3. #include <linux/slab.h>
  4. #include <linux/module.h>
  5. #include <linux/spinlock.h>
  6. #include <linux/version.h>
  7. #include <linux/hardirq.h>
  8. #include "extent_map.h"
  9. /* temporary define until extent_map moves out of btrfs */
  10. struct kmem_cache *btrfs_cache_create(const char *name, size_t size,
  11. unsigned long extra_flags,
  12. void (*ctor)(void *, struct kmem_cache *,
  13. unsigned long));
  14. static struct kmem_cache *extent_map_cache;
  15. int __init extent_map_init(void)
  16. {
  17. extent_map_cache = btrfs_cache_create("extent_map",
  18. sizeof(struct extent_map), 0,
  19. NULL);
  20. if (!extent_map_cache)
  21. return -ENOMEM;
  22. return 0;
  23. }
  24. void extent_map_exit(void)
  25. {
  26. if (extent_map_cache)
  27. kmem_cache_destroy(extent_map_cache);
  28. }
  29. void extent_map_tree_init(struct extent_map_tree *tree, gfp_t mask)
  30. {
  31. tree->map.rb_node = NULL;
  32. tree->last = NULL;
  33. spin_lock_init(&tree->lock);
  34. }
  35. EXPORT_SYMBOL(extent_map_tree_init);
  36. struct extent_map *alloc_extent_map(gfp_t mask)
  37. {
  38. struct extent_map *em;
  39. em = kmem_cache_alloc(extent_map_cache, mask);
  40. if (!em || IS_ERR(em))
  41. return em;
  42. em->in_tree = 0;
  43. em->flags = 0;
  44. atomic_set(&em->refs, 1);
  45. return em;
  46. }
  47. EXPORT_SYMBOL(alloc_extent_map);
  48. void free_extent_map(struct extent_map *em)
  49. {
  50. if (!em)
  51. return;
  52. WARN_ON(atomic_read(&em->refs) == 0);
  53. if (atomic_dec_and_test(&em->refs)) {
  54. WARN_ON(em->in_tree);
  55. kmem_cache_free(extent_map_cache, em);
  56. }
  57. }
  58. EXPORT_SYMBOL(free_extent_map);
  59. static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
  60. struct rb_node *node)
  61. {
  62. struct rb_node ** p = &root->rb_node;
  63. struct rb_node * parent = NULL;
  64. struct extent_map *entry;
  65. while(*p) {
  66. parent = *p;
  67. entry = rb_entry(parent, struct extent_map, rb_node);
  68. WARN_ON(!entry->in_tree);
  69. if (offset < entry->start)
  70. p = &(*p)->rb_left;
  71. else if (offset >= extent_map_end(entry))
  72. p = &(*p)->rb_right;
  73. else
  74. return parent;
  75. }
  76. entry = rb_entry(node, struct extent_map, rb_node);
  77. entry->in_tree = 1;
  78. rb_link_node(node, parent, p);
  79. rb_insert_color(node, root);
  80. return NULL;
  81. }
  82. static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
  83. struct rb_node **prev_ret,
  84. struct rb_node **next_ret)
  85. {
  86. struct rb_node * n = root->rb_node;
  87. struct rb_node *prev = NULL;
  88. struct rb_node *orig_prev = NULL;
  89. struct extent_map *entry;
  90. struct extent_map *prev_entry = NULL;
  91. while(n) {
  92. entry = rb_entry(n, struct extent_map, rb_node);
  93. prev = n;
  94. prev_entry = entry;
  95. WARN_ON(!entry->in_tree);
  96. if (offset < entry->start)
  97. n = n->rb_left;
  98. else if (offset >= extent_map_end(entry))
  99. n = n->rb_right;
  100. else
  101. return n;
  102. }
  103. if (prev_ret) {
  104. orig_prev = prev;
  105. while(prev && offset >= extent_map_end(prev_entry)) {
  106. prev = rb_next(prev);
  107. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  108. }
  109. *prev_ret = prev;
  110. prev = orig_prev;
  111. }
  112. if (next_ret) {
  113. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  114. while(prev && offset < prev_entry->start) {
  115. prev = rb_prev(prev);
  116. prev_entry = rb_entry(prev, struct extent_map, rb_node);
  117. }
  118. *next_ret = prev;
  119. }
  120. return NULL;
  121. }
  122. static inline struct rb_node *tree_search(struct rb_root *root, u64 offset)
  123. {
  124. struct rb_node *prev;
  125. struct rb_node *ret;
  126. ret = __tree_search(root, offset, &prev, NULL);
  127. if (!ret)
  128. return prev;
  129. return ret;
  130. }
  131. static int mergable_maps(struct extent_map *prev, struct extent_map *next)
  132. {
  133. if (extent_map_end(prev) == next->start &&
  134. prev->flags == next->flags &&
  135. prev->bdev == next->bdev &&
  136. ((next->block_start == EXTENT_MAP_HOLE &&
  137. prev->block_start == EXTENT_MAP_HOLE) ||
  138. (next->block_start == EXTENT_MAP_INLINE &&
  139. prev->block_start == EXTENT_MAP_INLINE) ||
  140. (next->block_start == EXTENT_MAP_DELALLOC &&
  141. prev->block_start == EXTENT_MAP_DELALLOC) ||
  142. (next->block_start < EXTENT_MAP_LAST_BYTE - 1 &&
  143. next->block_start == extent_map_block_end(prev)))) {
  144. return 1;
  145. }
  146. return 0;
  147. }
  148. /*
  149. * add_extent_mapping tries a simple forward/backward merge with existing
  150. * mappings. The extent_map struct passed in will be inserted into
  151. * the tree directly (no copies made, just a reference taken).
  152. */
  153. int add_extent_mapping(struct extent_map_tree *tree,
  154. struct extent_map *em)
  155. {
  156. int ret = 0;
  157. struct extent_map *merge = NULL;
  158. struct rb_node *rb;
  159. rb = tree_insert(&tree->map, em->start, &em->rb_node);
  160. if (rb) {
  161. merge = rb_entry(rb, struct extent_map, rb_node);
  162. ret = -EEXIST;
  163. goto out;
  164. }
  165. atomic_inc(&em->refs);
  166. if (em->start != 0) {
  167. rb = rb_prev(&em->rb_node);
  168. if (rb)
  169. merge = rb_entry(rb, struct extent_map, rb_node);
  170. if (rb && mergable_maps(merge, em)) {
  171. em->start = merge->start;
  172. em->len += merge->len;
  173. em->block_start = merge->block_start;
  174. merge->in_tree = 0;
  175. rb_erase(&merge->rb_node, &tree->map);
  176. free_extent_map(merge);
  177. }
  178. }
  179. rb = rb_next(&em->rb_node);
  180. if (rb)
  181. merge = rb_entry(rb, struct extent_map, rb_node);
  182. if (rb && mergable_maps(em, merge)) {
  183. em->len += merge->len;
  184. rb_erase(&merge->rb_node, &tree->map);
  185. merge->in_tree = 0;
  186. free_extent_map(merge);
  187. }
  188. tree->last = em;
  189. out:
  190. return ret;
  191. }
  192. EXPORT_SYMBOL(add_extent_mapping);
  193. static u64 range_end(u64 start, u64 len)
  194. {
  195. if (start + len < start)
  196. return (u64)-1;
  197. return start + len;
  198. }
  199. /*
  200. * lookup_extent_mapping returns the first extent_map struct in the
  201. * tree that intersects the [start, len] range. There may
  202. * be additional objects in the tree that intersect, so check the object
  203. * returned carefully to make sure you don't need additional lookups.
  204. */
  205. struct extent_map *lookup_extent_mapping(struct extent_map_tree *tree,
  206. u64 start, u64 len)
  207. {
  208. struct extent_map *em;
  209. struct rb_node *rb_node;
  210. struct rb_node *prev = NULL; struct rb_node *next = NULL; u64 end = range_end(start, len); em = tree->last; if (em && end > em->start && start < extent_map_end(em)) goto found;
  211. rb_node = __tree_search(&tree->map, start, &prev, &next);
  212. if (!rb_node && prev) {
  213. em = rb_entry(prev, struct extent_map, rb_node);
  214. if (end > em->start && start < extent_map_end(em))
  215. goto found;
  216. }
  217. if (!rb_node && next) {
  218. em = rb_entry(next, struct extent_map, rb_node);
  219. if (end > em->start && start < extent_map_end(em))
  220. goto found;
  221. }
  222. if (!rb_node) {
  223. em = NULL;
  224. goto out;
  225. }
  226. if (IS_ERR(rb_node)) {
  227. em = ERR_PTR(PTR_ERR(rb_node));
  228. goto out;
  229. }
  230. em = rb_entry(rb_node, struct extent_map, rb_node);
  231. if (end > em->start && start < extent_map_end(em))
  232. goto found;
  233. em = NULL;
  234. goto out;
  235. found:
  236. atomic_inc(&em->refs);
  237. tree->last = em;
  238. out:
  239. return em;
  240. }
  241. EXPORT_SYMBOL(lookup_extent_mapping);
  242. /*
  243. * removes an extent_map struct from the tree. No reference counts are
  244. * dropped, and no checks are done to see if the range is in use
  245. */
  246. int remove_extent_mapping(struct extent_map_tree *tree, struct extent_map *em)
  247. {
  248. int ret = 0;
  249. rb_erase(&em->rb_node, &tree->map);
  250. em->in_tree = 0;
  251. if (tree->last == em)
  252. tree->last = NULL;
  253. return ret;
  254. }
  255. EXPORT_SYMBOL(remove_extent_mapping);