ordered-data.c 6.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257
  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/gfp.h>
  19. #include <linux/slab.h>
  20. #include "ctree.h"
  21. #include "transaction.h"
  22. #include "btrfs_inode.h"
  23. struct tree_entry {
  24. u64 root_objectid;
  25. u64 objectid;
  26. struct rb_node rb_node;
  27. };
  28. /*
  29. * returns > 0 if entry passed (root, objectid) is > entry,
  30. * < 0 if (root, objectid) < entry and zero if they are equal
  31. */
  32. static int comp_entry(struct tree_entry *entry, u64 root_objectid,
  33. u64 objectid)
  34. {
  35. if (root_objectid < entry->root_objectid)
  36. return -1;
  37. if (root_objectid > entry->root_objectid)
  38. return 1;
  39. if (objectid < entry->objectid)
  40. return -1;
  41. if (objectid > entry->objectid)
  42. return 1;
  43. return 0;
  44. }
  45. static struct rb_node *tree_insert(struct rb_root *root, u64 root_objectid,
  46. u64 objectid, struct rb_node *node)
  47. {
  48. struct rb_node ** p = &root->rb_node;
  49. struct rb_node * parent = NULL;
  50. struct tree_entry *entry;
  51. int comp;
  52. while(*p) {
  53. parent = *p;
  54. entry = rb_entry(parent, struct tree_entry, rb_node);
  55. comp = comp_entry(entry, root_objectid, objectid);
  56. if (comp < 0)
  57. p = &(*p)->rb_left;
  58. else if (comp > 0)
  59. p = &(*p)->rb_right;
  60. else
  61. return parent;
  62. }
  63. rb_link_node(node, parent, p);
  64. rb_insert_color(node, root);
  65. return NULL;
  66. }
  67. static struct rb_node *__tree_search(struct rb_root *root, u64 root_objectid,
  68. u64 objectid, struct rb_node **prev_ret)
  69. {
  70. struct rb_node * n = root->rb_node;
  71. struct rb_node *prev = NULL;
  72. struct tree_entry *entry;
  73. struct tree_entry *prev_entry = NULL;
  74. int comp;
  75. while(n) {
  76. entry = rb_entry(n, struct tree_entry, rb_node);
  77. prev = n;
  78. prev_entry = entry;
  79. comp = comp_entry(entry, root_objectid, objectid);
  80. if (comp < 0)
  81. n = n->rb_left;
  82. else if (comp > 0)
  83. n = n->rb_right;
  84. else
  85. return n;
  86. }
  87. if (!prev_ret)
  88. return NULL;
  89. while(prev && comp_entry(prev_entry, root_objectid, objectid) >= 0) {
  90. prev = rb_next(prev);
  91. prev_entry = rb_entry(prev, struct tree_entry, rb_node);
  92. }
  93. *prev_ret = prev;
  94. return NULL;
  95. }
  96. static inline struct rb_node *tree_search(struct rb_root *root,
  97. u64 root_objectid, u64 objectid)
  98. {
  99. struct rb_node *prev;
  100. struct rb_node *ret;
  101. ret = __tree_search(root, root_objectid, objectid, &prev);
  102. if (!ret)
  103. return prev;
  104. return ret;
  105. }
  106. int btrfs_add_ordered_inode(struct inode *inode)
  107. {
  108. struct btrfs_root *root = BTRFS_I(inode)->root;
  109. u64 root_objectid = root->root_key.objectid;
  110. u64 transid = root->fs_info->running_transaction->transid;
  111. struct tree_entry *entry;
  112. struct rb_node *node;
  113. struct btrfs_ordered_inode_tree *tree;
  114. if (transid <= BTRFS_I(inode)->ordered_trans)
  115. return 0;
  116. tree = &root->fs_info->running_transaction->ordered_inode_tree;
  117. read_lock(&tree->lock);
  118. node = __tree_search(&tree->tree, root_objectid, inode->i_ino, NULL);
  119. read_unlock(&tree->lock);
  120. if (node) {
  121. return 0;
  122. }
  123. entry = kmalloc(sizeof(*entry), GFP_NOFS);
  124. if (!entry)
  125. return -ENOMEM;
  126. write_lock(&tree->lock);
  127. entry->objectid = inode->i_ino;
  128. entry->root_objectid = root_objectid;
  129. node = tree_insert(&tree->tree, root_objectid,
  130. inode->i_ino, &entry->rb_node);
  131. BTRFS_I(inode)->ordered_trans = transid;
  132. write_unlock(&tree->lock);
  133. if (node)
  134. kfree(entry);
  135. return 0;
  136. }
  137. int btrfs_find_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
  138. u64 *root_objectid, u64 *objectid)
  139. {
  140. struct tree_entry *entry;
  141. struct rb_node *node;
  142. write_lock(&tree->lock);
  143. node = tree_search(&tree->tree, *root_objectid, *objectid);
  144. if (!node) {
  145. write_unlock(&tree->lock);
  146. return 0;
  147. }
  148. entry = rb_entry(node, struct tree_entry, rb_node);
  149. while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
  150. node = rb_next(node);
  151. if (!node)
  152. break;
  153. entry = rb_entry(node, struct tree_entry, rb_node);
  154. }
  155. if (!node) {
  156. write_unlock(&tree->lock);
  157. return 0;
  158. }
  159. *root_objectid = entry->root_objectid;
  160. *objectid = entry->objectid;
  161. write_unlock(&tree->lock);
  162. return 1;
  163. }
  164. int btrfs_find_del_first_ordered_inode(struct btrfs_ordered_inode_tree *tree,
  165. u64 *root_objectid, u64 *objectid)
  166. {
  167. struct tree_entry *entry;
  168. struct rb_node *node;
  169. write_lock(&tree->lock);
  170. node = tree_search(&tree->tree, *root_objectid, *objectid);
  171. if (!node) {
  172. write_unlock(&tree->lock);
  173. return 0;
  174. }
  175. entry = rb_entry(node, struct tree_entry, rb_node);
  176. while(comp_entry(entry, *root_objectid, *objectid) >= 0) {
  177. node = rb_next(node);
  178. if (!node)
  179. break;
  180. entry = rb_entry(node, struct tree_entry, rb_node);
  181. }
  182. if (!node) {
  183. write_unlock(&tree->lock);
  184. return 0;
  185. }
  186. *root_objectid = entry->root_objectid;
  187. *objectid = entry->objectid;
  188. rb_erase(node, &tree->tree);
  189. write_unlock(&tree->lock);
  190. kfree(entry);
  191. return 1;
  192. }
  193. static int __btrfs_del_ordered_inode(struct btrfs_ordered_inode_tree *tree,
  194. u64 root_objectid, u64 objectid)
  195. {
  196. struct tree_entry *entry;
  197. struct rb_node *node;
  198. struct rb_node *prev;
  199. write_lock(&tree->lock);
  200. node = __tree_search(&tree->tree, root_objectid, objectid, &prev);
  201. if (!node) {
  202. write_unlock(&tree->lock);
  203. return 0;
  204. }
  205. rb_erase(node, &tree->tree);
  206. write_unlock(&tree->lock);
  207. entry = rb_entry(node, struct tree_entry, rb_node);
  208. kfree(entry);
  209. return 1;
  210. }
  211. int btrfs_del_ordered_inode(struct inode *inode)
  212. {
  213. struct btrfs_root *root = BTRFS_I(inode)->root;
  214. u64 root_objectid = root->root_key.objectid;
  215. spin_lock(&root->fs_info->new_trans_lock);
  216. if (root->fs_info->running_transaction) {
  217. struct btrfs_ordered_inode_tree *tree;
  218. tree = &root->fs_info->running_transaction->ordered_inode_tree;
  219. __btrfs_del_ordered_inode(tree, root_objectid, inode->i_ino);
  220. }
  221. spin_unlock(&root->fs_info->new_trans_lock);
  222. return 0;
  223. }