root-tree.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448
  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 "ctree.h"
  19. #include "transaction.h"
  20. #include "disk-io.h"
  21. #include "print-tree.h"
  22. /*
  23. * lookup the root with the highest offset for a given objectid. The key we do
  24. * find is copied into 'key'. If we find something return 0, otherwise 1, < 0
  25. * on error.
  26. */
  27. int btrfs_find_last_root(struct btrfs_root *root, u64 objectid,
  28. struct btrfs_root_item *item, struct btrfs_key *key)
  29. {
  30. struct btrfs_path *path;
  31. struct btrfs_key search_key;
  32. struct btrfs_key found_key;
  33. struct extent_buffer *l;
  34. int ret;
  35. int slot;
  36. search_key.objectid = objectid;
  37. search_key.type = BTRFS_ROOT_ITEM_KEY;
  38. search_key.offset = (u64)-1;
  39. path = btrfs_alloc_path();
  40. if (!path)
  41. return -ENOMEM;
  42. ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
  43. if (ret < 0)
  44. goto out;
  45. BUG_ON(ret == 0);
  46. if (path->slots[0] == 0) {
  47. ret = 1;
  48. goto out;
  49. }
  50. l = path->nodes[0];
  51. slot = path->slots[0] - 1;
  52. btrfs_item_key_to_cpu(l, &found_key, slot);
  53. if (found_key.objectid != objectid ||
  54. found_key.type != BTRFS_ROOT_ITEM_KEY) {
  55. ret = 1;
  56. goto out;
  57. }
  58. if (item)
  59. read_extent_buffer(l, item, btrfs_item_ptr_offset(l, slot),
  60. sizeof(*item));
  61. if (key)
  62. memcpy(key, &found_key, sizeof(found_key));
  63. ret = 0;
  64. out:
  65. btrfs_free_path(path);
  66. return ret;
  67. }
  68. void btrfs_set_root_node(struct btrfs_root_item *item,
  69. struct extent_buffer *node)
  70. {
  71. btrfs_set_root_bytenr(item, node->start);
  72. btrfs_set_root_level(item, btrfs_header_level(node));
  73. btrfs_set_root_generation(item, btrfs_header_generation(node));
  74. }
  75. /*
  76. * copy the data in 'item' into the btree
  77. */
  78. int btrfs_update_root(struct btrfs_trans_handle *trans, struct btrfs_root
  79. *root, struct btrfs_key *key, struct btrfs_root_item
  80. *item)
  81. {
  82. struct btrfs_path *path;
  83. struct extent_buffer *l;
  84. int ret;
  85. int slot;
  86. unsigned long ptr;
  87. path = btrfs_alloc_path();
  88. if (!path)
  89. return -ENOMEM;
  90. ret = btrfs_search_slot(trans, root, key, path, 0, 1);
  91. if (ret < 0)
  92. goto out;
  93. if (ret != 0) {
  94. btrfs_print_leaf(root, path->nodes[0]);
  95. printk(KERN_CRIT "unable to update root key %llu %u %llu\n",
  96. (unsigned long long)key->objectid, key->type,
  97. (unsigned long long)key->offset);
  98. BUG_ON(1);
  99. }
  100. l = path->nodes[0];
  101. slot = path->slots[0];
  102. ptr = btrfs_item_ptr_offset(l, slot);
  103. write_extent_buffer(l, item, ptr, sizeof(*item));
  104. btrfs_mark_buffer_dirty(path->nodes[0]);
  105. out:
  106. btrfs_free_path(path);
  107. return ret;
  108. }
  109. int btrfs_insert_root(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  110. struct btrfs_key *key, struct btrfs_root_item *item)
  111. {
  112. return btrfs_insert_item(trans, root, key, item, sizeof(*item));
  113. }
  114. /*
  115. * at mount time we want to find all the old transaction snapshots that were in
  116. * the process of being deleted if we crashed. This is any root item with an
  117. * offset lower than the latest root. They need to be queued for deletion to
  118. * finish what was happening when we crashed.
  119. */
  120. int btrfs_find_dead_roots(struct btrfs_root *root, u64 objectid)
  121. {
  122. struct btrfs_root *dead_root;
  123. struct btrfs_root_item *ri;
  124. struct btrfs_key key;
  125. struct btrfs_key found_key;
  126. struct btrfs_path *path;
  127. int ret;
  128. u32 nritems;
  129. struct extent_buffer *leaf;
  130. int slot;
  131. key.objectid = objectid;
  132. btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
  133. key.offset = 0;
  134. path = btrfs_alloc_path();
  135. if (!path)
  136. return -ENOMEM;
  137. again:
  138. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  139. if (ret < 0)
  140. goto err;
  141. while (1) {
  142. leaf = path->nodes[0];
  143. nritems = btrfs_header_nritems(leaf);
  144. slot = path->slots[0];
  145. if (slot >= nritems) {
  146. ret = btrfs_next_leaf(root, path);
  147. if (ret)
  148. break;
  149. leaf = path->nodes[0];
  150. nritems = btrfs_header_nritems(leaf);
  151. slot = path->slots[0];
  152. }
  153. btrfs_item_key_to_cpu(leaf, &key, slot);
  154. if (btrfs_key_type(&key) != BTRFS_ROOT_ITEM_KEY)
  155. goto next;
  156. if (key.objectid < objectid)
  157. goto next;
  158. if (key.objectid > objectid)
  159. break;
  160. ri = btrfs_item_ptr(leaf, slot, struct btrfs_root_item);
  161. if (btrfs_disk_root_refs(leaf, ri) != 0)
  162. goto next;
  163. memcpy(&found_key, &key, sizeof(key));
  164. key.offset++;
  165. btrfs_release_path(path);
  166. dead_root =
  167. btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
  168. &found_key);
  169. if (IS_ERR(dead_root)) {
  170. ret = PTR_ERR(dead_root);
  171. goto err;
  172. }
  173. ret = btrfs_add_dead_root(dead_root);
  174. if (ret)
  175. goto err;
  176. goto again;
  177. next:
  178. slot++;
  179. path->slots[0]++;
  180. }
  181. ret = 0;
  182. err:
  183. btrfs_free_path(path);
  184. return ret;
  185. }
  186. int btrfs_find_orphan_roots(struct btrfs_root *tree_root)
  187. {
  188. struct extent_buffer *leaf;
  189. struct btrfs_path *path;
  190. struct btrfs_key key;
  191. struct btrfs_key root_key;
  192. struct btrfs_root *root;
  193. int err = 0;
  194. int ret;
  195. path = btrfs_alloc_path();
  196. if (!path)
  197. return -ENOMEM;
  198. key.objectid = BTRFS_ORPHAN_OBJECTID;
  199. key.type = BTRFS_ORPHAN_ITEM_KEY;
  200. key.offset = 0;
  201. root_key.type = BTRFS_ROOT_ITEM_KEY;
  202. root_key.offset = (u64)-1;
  203. while (1) {
  204. ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0);
  205. if (ret < 0) {
  206. err = ret;
  207. break;
  208. }
  209. leaf = path->nodes[0];
  210. if (path->slots[0] >= btrfs_header_nritems(leaf)) {
  211. ret = btrfs_next_leaf(tree_root, path);
  212. if (ret < 0)
  213. err = ret;
  214. if (ret != 0)
  215. break;
  216. leaf = path->nodes[0];
  217. }
  218. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  219. btrfs_release_path(path);
  220. if (key.objectid != BTRFS_ORPHAN_OBJECTID ||
  221. key.type != BTRFS_ORPHAN_ITEM_KEY)
  222. break;
  223. root_key.objectid = key.offset;
  224. key.offset++;
  225. root = btrfs_read_fs_root_no_name(tree_root->fs_info,
  226. &root_key);
  227. if (!IS_ERR(root))
  228. continue;
  229. ret = PTR_ERR(root);
  230. if (ret != -ENOENT) {
  231. err = ret;
  232. break;
  233. }
  234. ret = btrfs_find_dead_roots(tree_root, root_key.objectid);
  235. if (ret) {
  236. err = ret;
  237. break;
  238. }
  239. }
  240. btrfs_free_path(path);
  241. return err;
  242. }
  243. /* drop the root item for 'key' from 'root' */
  244. int btrfs_del_root(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  245. struct btrfs_key *key)
  246. {
  247. struct btrfs_path *path;
  248. int ret;
  249. struct btrfs_root_item *ri;
  250. struct extent_buffer *leaf;
  251. path = btrfs_alloc_path();
  252. if (!path)
  253. return -ENOMEM;
  254. ret = btrfs_search_slot(trans, root, key, path, -1, 1);
  255. if (ret < 0)
  256. goto out;
  257. BUG_ON(ret != 0);
  258. leaf = path->nodes[0];
  259. ri = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_item);
  260. ret = btrfs_del_item(trans, root, path);
  261. out:
  262. btrfs_free_path(path);
  263. return ret;
  264. }
  265. int btrfs_del_root_ref(struct btrfs_trans_handle *trans,
  266. struct btrfs_root *tree_root,
  267. u64 root_id, u64 ref_id, u64 dirid, u64 *sequence,
  268. const char *name, int name_len)
  269. {
  270. struct btrfs_path *path;
  271. struct btrfs_root_ref *ref;
  272. struct extent_buffer *leaf;
  273. struct btrfs_key key;
  274. unsigned long ptr;
  275. int err = 0;
  276. int ret;
  277. path = btrfs_alloc_path();
  278. if (!path)
  279. return -ENOMEM;
  280. key.objectid = root_id;
  281. key.type = BTRFS_ROOT_BACKREF_KEY;
  282. key.offset = ref_id;
  283. again:
  284. ret = btrfs_search_slot(trans, tree_root, &key, path, -1, 1);
  285. BUG_ON(ret < 0);
  286. if (ret == 0) {
  287. leaf = path->nodes[0];
  288. ref = btrfs_item_ptr(leaf, path->slots[0],
  289. struct btrfs_root_ref);
  290. WARN_ON(btrfs_root_ref_dirid(leaf, ref) != dirid);
  291. WARN_ON(btrfs_root_ref_name_len(leaf, ref) != name_len);
  292. ptr = (unsigned long)(ref + 1);
  293. WARN_ON(memcmp_extent_buffer(leaf, name, ptr, name_len));
  294. *sequence = btrfs_root_ref_sequence(leaf, ref);
  295. ret = btrfs_del_item(trans, tree_root, path);
  296. if (ret) {
  297. err = ret;
  298. goto out;
  299. }
  300. } else
  301. err = -ENOENT;
  302. if (key.type == BTRFS_ROOT_BACKREF_KEY) {
  303. btrfs_release_path(path);
  304. key.objectid = ref_id;
  305. key.type = BTRFS_ROOT_REF_KEY;
  306. key.offset = root_id;
  307. goto again;
  308. }
  309. out:
  310. btrfs_free_path(path);
  311. return err;
  312. }
  313. int btrfs_find_root_ref(struct btrfs_root *tree_root,
  314. struct btrfs_path *path,
  315. u64 root_id, u64 ref_id)
  316. {
  317. struct btrfs_key key;
  318. int ret;
  319. key.objectid = root_id;
  320. key.type = BTRFS_ROOT_REF_KEY;
  321. key.offset = ref_id;
  322. ret = btrfs_search_slot(NULL, tree_root, &key, path, 0, 0);
  323. return ret;
  324. }
  325. /*
  326. * add a btrfs_root_ref item. type is either BTRFS_ROOT_REF_KEY
  327. * or BTRFS_ROOT_BACKREF_KEY.
  328. *
  329. * The dirid, sequence, name and name_len refer to the directory entry
  330. * that is referencing the root.
  331. *
  332. * For a forward ref, the root_id is the id of the tree referencing
  333. * the root and ref_id is the id of the subvol or snapshot.
  334. *
  335. * For a back ref the root_id is the id of the subvol or snapshot and
  336. * ref_id is the id of the tree referencing it.
  337. */
  338. int btrfs_add_root_ref(struct btrfs_trans_handle *trans,
  339. struct btrfs_root *tree_root,
  340. u64 root_id, u64 ref_id, u64 dirid, u64 sequence,
  341. const char *name, int name_len)
  342. {
  343. struct btrfs_key key;
  344. int ret;
  345. struct btrfs_path *path;
  346. struct btrfs_root_ref *ref;
  347. struct extent_buffer *leaf;
  348. unsigned long ptr;
  349. path = btrfs_alloc_path();
  350. if (!path)
  351. return -ENOMEM;
  352. key.objectid = root_id;
  353. key.type = BTRFS_ROOT_BACKREF_KEY;
  354. key.offset = ref_id;
  355. again:
  356. ret = btrfs_insert_empty_item(trans, tree_root, path, &key,
  357. sizeof(*ref) + name_len);
  358. BUG_ON(ret);
  359. leaf = path->nodes[0];
  360. ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_root_ref);
  361. btrfs_set_root_ref_dirid(leaf, ref, dirid);
  362. btrfs_set_root_ref_sequence(leaf, ref, sequence);
  363. btrfs_set_root_ref_name_len(leaf, ref, name_len);
  364. ptr = (unsigned long)(ref + 1);
  365. write_extent_buffer(leaf, name, ptr, name_len);
  366. btrfs_mark_buffer_dirty(leaf);
  367. if (key.type == BTRFS_ROOT_BACKREF_KEY) {
  368. btrfs_release_path(path);
  369. key.objectid = ref_id;
  370. key.type = BTRFS_ROOT_REF_KEY;
  371. key.offset = root_id;
  372. goto again;
  373. }
  374. btrfs_free_path(path);
  375. return 0;
  376. }
  377. /*
  378. * Old btrfs forgets to init root_item->flags and root_item->byte_limit
  379. * for subvolumes. To work around this problem, we steal a bit from
  380. * root_item->inode_item->flags, and use it to indicate if those fields
  381. * have been properly initialized.
  382. */
  383. void btrfs_check_and_init_root_item(struct btrfs_root_item *root_item)
  384. {
  385. u64 inode_flags = le64_to_cpu(root_item->inode.flags);
  386. if (!(inode_flags & BTRFS_INODE_ROOT_ITEM_INIT)) {
  387. inode_flags |= BTRFS_INODE_ROOT_ITEM_INIT;
  388. root_item->inode.flags = cpu_to_le64(inode_flags);
  389. root_item->flags = 0;
  390. root_item->byte_limit = 0;
  391. }
  392. }