ordered-data.c 6.5 KB

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