extent-cache.c 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * Crossported from the same named file of btrfs-progs.
  4. *
  5. * Minor modification to include headers.
  6. */
  7. #include <linux/kernel.h>
  8. #include <linux/rbtree.h>
  9. #include <linux/errno.h>
  10. #include <linux/bug.h>
  11. #include <stdlib.h>
  12. #include "extent-cache.h"
  13. #include "common/rbtree-utils.h"
  14. struct cache_extent_search_range {
  15. u64 objectid;
  16. u64 start;
  17. u64 size;
  18. };
  19. static int cache_tree_comp_range(struct rb_node *node, void *data)
  20. {
  21. struct cache_extent *entry;
  22. struct cache_extent_search_range *range;
  23. range = (struct cache_extent_search_range *)data;
  24. entry = rb_entry(node, struct cache_extent, rb_node);
  25. if (entry->start + entry->size <= range->start)
  26. return 1;
  27. else if (range->start + range->size <= entry->start)
  28. return -1;
  29. else
  30. return 0;
  31. }
  32. static int cache_tree_comp_nodes(struct rb_node *node1, struct rb_node *node2)
  33. {
  34. struct cache_extent *entry;
  35. struct cache_extent_search_range range;
  36. entry = rb_entry(node2, struct cache_extent, rb_node);
  37. range.start = entry->start;
  38. range.size = entry->size;
  39. return cache_tree_comp_range(node1, (void *)&range);
  40. }
  41. static int cache_tree_comp_range2(struct rb_node *node, void *data)
  42. {
  43. struct cache_extent *entry;
  44. struct cache_extent_search_range *range;
  45. range = (struct cache_extent_search_range *)data;
  46. entry = rb_entry(node, struct cache_extent, rb_node);
  47. if (entry->objectid < range->objectid)
  48. return 1;
  49. else if (entry->objectid > range->objectid)
  50. return -1;
  51. else if (entry->start + entry->size <= range->start)
  52. return 1;
  53. else if (range->start + range->size <= entry->start)
  54. return -1;
  55. else
  56. return 0;
  57. }
  58. static int cache_tree_comp_nodes2(struct rb_node *node1, struct rb_node *node2)
  59. {
  60. struct cache_extent *entry;
  61. struct cache_extent_search_range range;
  62. entry = rb_entry(node2, struct cache_extent, rb_node);
  63. range.objectid = entry->objectid;
  64. range.start = entry->start;
  65. range.size = entry->size;
  66. return cache_tree_comp_range2(node1, (void *)&range);
  67. }
  68. void cache_tree_init(struct cache_tree *tree)
  69. {
  70. tree->root = RB_ROOT;
  71. }
  72. static struct cache_extent *alloc_cache_extent(u64 start, u64 size)
  73. {
  74. struct cache_extent *pe = malloc(sizeof(*pe));
  75. if (!pe)
  76. return pe;
  77. pe->objectid = 0;
  78. pe->start = start;
  79. pe->size = size;
  80. return pe;
  81. }
  82. int add_cache_extent(struct cache_tree *tree, u64 start, u64 size)
  83. {
  84. struct cache_extent *pe = alloc_cache_extent(start, size);
  85. int ret;
  86. if (!pe)
  87. return -ENOMEM;
  88. ret = insert_cache_extent(tree, pe);
  89. if (ret)
  90. free(pe);
  91. return ret;
  92. }
  93. int insert_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
  94. {
  95. return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes);
  96. }
  97. int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe)
  98. {
  99. return rb_insert(&tree->root, &pe->rb_node, cache_tree_comp_nodes2);
  100. }
  101. struct cache_extent *lookup_cache_extent(struct cache_tree *tree,
  102. u64 start, u64 size)
  103. {
  104. struct rb_node *node;
  105. struct cache_extent *entry;
  106. struct cache_extent_search_range range;
  107. range.start = start;
  108. range.size = size;
  109. node = rb_search(&tree->root, &range, cache_tree_comp_range, NULL);
  110. if (!node)
  111. return NULL;
  112. entry = rb_entry(node, struct cache_extent, rb_node);
  113. return entry;
  114. }
  115. struct cache_extent *lookup_cache_extent2(struct cache_tree *tree,
  116. u64 objectid, u64 start, u64 size)
  117. {
  118. struct rb_node *node;
  119. struct cache_extent *entry;
  120. struct cache_extent_search_range range;
  121. range.objectid = objectid;
  122. range.start = start;
  123. range.size = size;
  124. node = rb_search(&tree->root, &range, cache_tree_comp_range2, NULL);
  125. if (!node)
  126. return NULL;
  127. entry = rb_entry(node, struct cache_extent, rb_node);
  128. return entry;
  129. }
  130. struct cache_extent *search_cache_extent(struct cache_tree *tree, u64 start)
  131. {
  132. struct rb_node *next;
  133. struct rb_node *node;
  134. struct cache_extent *entry;
  135. struct cache_extent_search_range range;
  136. range.start = start;
  137. range.size = 1;
  138. node = rb_search(&tree->root, &range, cache_tree_comp_range, &next);
  139. if (!node)
  140. node = next;
  141. if (!node)
  142. return NULL;
  143. entry = rb_entry(node, struct cache_extent, rb_node);
  144. return entry;
  145. }
  146. struct cache_extent *search_cache_extent2(struct cache_tree *tree,
  147. u64 objectid, u64 start)
  148. {
  149. struct rb_node *next;
  150. struct rb_node *node;
  151. struct cache_extent *entry;
  152. struct cache_extent_search_range range;
  153. range.objectid = objectid;
  154. range.start = start;
  155. range.size = 1;
  156. node = rb_search(&tree->root, &range, cache_tree_comp_range2, &next);
  157. if (!node)
  158. node = next;
  159. if (!node)
  160. return NULL;
  161. entry = rb_entry(node, struct cache_extent, rb_node);
  162. return entry;
  163. }
  164. struct cache_extent *first_cache_extent(struct cache_tree *tree)
  165. {
  166. struct rb_node *node = rb_first(&tree->root);
  167. if (!node)
  168. return NULL;
  169. return rb_entry(node, struct cache_extent, rb_node);
  170. }
  171. struct cache_extent *last_cache_extent(struct cache_tree *tree)
  172. {
  173. struct rb_node *node = rb_last(&tree->root);
  174. if (!node)
  175. return NULL;
  176. return rb_entry(node, struct cache_extent, rb_node);
  177. }
  178. struct cache_extent *prev_cache_extent(struct cache_extent *pe)
  179. {
  180. struct rb_node *node = rb_prev(&pe->rb_node);
  181. if (!node)
  182. return NULL;
  183. return rb_entry(node, struct cache_extent, rb_node);
  184. }
  185. struct cache_extent *next_cache_extent(struct cache_extent *pe)
  186. {
  187. struct rb_node *node = rb_next(&pe->rb_node);
  188. if (!node)
  189. return NULL;
  190. return rb_entry(node, struct cache_extent, rb_node);
  191. }
  192. void remove_cache_extent(struct cache_tree *tree, struct cache_extent *pe)
  193. {
  194. rb_erase(&pe->rb_node, &tree->root);
  195. }
  196. void cache_tree_free_extents(struct cache_tree *tree,
  197. free_cache_extent free_func)
  198. {
  199. struct cache_extent *ce;
  200. while ((ce = first_cache_extent(tree))) {
  201. remove_cache_extent(tree, ce);
  202. free_func(ce);
  203. }
  204. }
  205. static void free_extent_cache(struct cache_extent *pe)
  206. {
  207. free(pe);
  208. }
  209. void free_extent_cache_tree(struct cache_tree *tree)
  210. {
  211. cache_tree_free_extents(tree, free_extent_cache);
  212. }
  213. int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size)
  214. {
  215. struct cache_extent *cache;
  216. struct cache_extent *next = NULL;
  217. struct cache_extent *prev = NULL;
  218. int next_merged = 0;
  219. int prev_merged = 0;
  220. int ret = 0;
  221. if (cache_tree_empty(tree))
  222. goto insert;
  223. cache = search_cache_extent(tree, start);
  224. if (!cache) {
  225. /*
  226. * Either the tree is completely empty, or the no range after
  227. * start.
  228. * Either way, the last cache_extent should be prev.
  229. */
  230. prev = last_cache_extent(tree);
  231. } else if (start <= cache->start) {
  232. next = cache;
  233. prev = prev_cache_extent(cache);
  234. } else {
  235. prev = cache;
  236. next = next_cache_extent(cache);
  237. }
  238. /*
  239. * Ensure the range to be inserted won't cover with existings
  240. * Or we will need extra loop to do merge
  241. */
  242. BUG_ON(next && start + size > next->start);
  243. BUG_ON(prev && prev->start + prev->size > start);
  244. if (next && start + size == next->start) {
  245. next_merged = 1;
  246. next->size = next->start + next->size - start;
  247. next->start = start;
  248. }
  249. if (prev && prev->start + prev->size == start) {
  250. prev_merged = 1;
  251. if (next_merged) {
  252. next->size = next->start + next->size - prev->start;
  253. next->start = prev->start;
  254. remove_cache_extent(tree, prev);
  255. free(prev);
  256. } else {
  257. prev->size = start + size - prev->start;
  258. }
  259. }
  260. insert:
  261. if (!prev_merged && !next_merged)
  262. ret = add_cache_extent(tree, start, size);
  263. return ret;
  264. }