ref-verify.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2014 Facebook. All rights reserved.
  4. */
  5. #include <linux/sched.h>
  6. #include <linux/stacktrace.h>
  7. #include "ctree.h"
  8. #include "disk-io.h"
  9. #include "locking.h"
  10. #include "delayed-ref.h"
  11. #include "ref-verify.h"
  12. /*
  13. * Used to keep track the roots and number of refs each root has for a given
  14. * bytenr. This just tracks the number of direct references, no shared
  15. * references.
  16. */
  17. struct root_entry {
  18. u64 root_objectid;
  19. u64 num_refs;
  20. struct rb_node node;
  21. };
  22. /*
  23. * These are meant to represent what should exist in the extent tree, these can
  24. * be used to verify the extent tree is consistent as these should all match
  25. * what the extent tree says.
  26. */
  27. struct ref_entry {
  28. u64 root_objectid;
  29. u64 parent;
  30. u64 owner;
  31. u64 offset;
  32. u64 num_refs;
  33. struct rb_node node;
  34. };
  35. #define MAX_TRACE 16
  36. /*
  37. * Whenever we add/remove a reference we record the action. The action maps
  38. * back to the delayed ref action. We hold the ref we are changing in the
  39. * action so we can account for the history properly, and we record the root we
  40. * were called with since it could be different from ref_root. We also store
  41. * stack traces because that's how I roll.
  42. */
  43. struct ref_action {
  44. int action;
  45. u64 root;
  46. struct ref_entry ref;
  47. struct list_head list;
  48. unsigned long trace[MAX_TRACE];
  49. unsigned int trace_len;
  50. };
  51. /*
  52. * One of these for every block we reference, it holds the roots and references
  53. * to it as well as all of the ref actions that have occurred to it. We never
  54. * free it until we unmount the file system in order to make sure re-allocations
  55. * are happening properly.
  56. */
  57. struct block_entry {
  58. u64 bytenr;
  59. u64 len;
  60. u64 num_refs;
  61. int metadata;
  62. int from_disk;
  63. struct rb_root roots;
  64. struct rb_root refs;
  65. struct rb_node node;
  66. struct list_head actions;
  67. };
  68. static struct block_entry *insert_block_entry(struct rb_root *root,
  69. struct block_entry *be)
  70. {
  71. struct rb_node **p = &root->rb_node;
  72. struct rb_node *parent_node = NULL;
  73. struct block_entry *entry;
  74. while (*p) {
  75. parent_node = *p;
  76. entry = rb_entry(parent_node, struct block_entry, node);
  77. if (entry->bytenr > be->bytenr)
  78. p = &(*p)->rb_left;
  79. else if (entry->bytenr < be->bytenr)
  80. p = &(*p)->rb_right;
  81. else
  82. return entry;
  83. }
  84. rb_link_node(&be->node, parent_node, p);
  85. rb_insert_color(&be->node, root);
  86. return NULL;
  87. }
  88. static struct block_entry *lookup_block_entry(struct rb_root *root, u64 bytenr)
  89. {
  90. struct rb_node *n;
  91. struct block_entry *entry = NULL;
  92. n = root->rb_node;
  93. while (n) {
  94. entry = rb_entry(n, struct block_entry, node);
  95. if (entry->bytenr < bytenr)
  96. n = n->rb_right;
  97. else if (entry->bytenr > bytenr)
  98. n = n->rb_left;
  99. else
  100. return entry;
  101. }
  102. return NULL;
  103. }
  104. static struct root_entry *insert_root_entry(struct rb_root *root,
  105. struct root_entry *re)
  106. {
  107. struct rb_node **p = &root->rb_node;
  108. struct rb_node *parent_node = NULL;
  109. struct root_entry *entry;
  110. while (*p) {
  111. parent_node = *p;
  112. entry = rb_entry(parent_node, struct root_entry, node);
  113. if (entry->root_objectid > re->root_objectid)
  114. p = &(*p)->rb_left;
  115. else if (entry->root_objectid < re->root_objectid)
  116. p = &(*p)->rb_right;
  117. else
  118. return entry;
  119. }
  120. rb_link_node(&re->node, parent_node, p);
  121. rb_insert_color(&re->node, root);
  122. return NULL;
  123. }
  124. static int comp_refs(struct ref_entry *ref1, struct ref_entry *ref2)
  125. {
  126. if (ref1->root_objectid < ref2->root_objectid)
  127. return -1;
  128. if (ref1->root_objectid > ref2->root_objectid)
  129. return 1;
  130. if (ref1->parent < ref2->parent)
  131. return -1;
  132. if (ref1->parent > ref2->parent)
  133. return 1;
  134. if (ref1->owner < ref2->owner)
  135. return -1;
  136. if (ref1->owner > ref2->owner)
  137. return 1;
  138. if (ref1->offset < ref2->offset)
  139. return -1;
  140. if (ref1->offset > ref2->offset)
  141. return 1;
  142. return 0;
  143. }
  144. static struct ref_entry *insert_ref_entry(struct rb_root *root,
  145. struct ref_entry *ref)
  146. {
  147. struct rb_node **p = &root->rb_node;
  148. struct rb_node *parent_node = NULL;
  149. struct ref_entry *entry;
  150. int cmp;
  151. while (*p) {
  152. parent_node = *p;
  153. entry = rb_entry(parent_node, struct ref_entry, node);
  154. cmp = comp_refs(entry, ref);
  155. if (cmp > 0)
  156. p = &(*p)->rb_left;
  157. else if (cmp < 0)
  158. p = &(*p)->rb_right;
  159. else
  160. return entry;
  161. }
  162. rb_link_node(&ref->node, parent_node, p);
  163. rb_insert_color(&ref->node, root);
  164. return NULL;
  165. }
  166. static struct root_entry *lookup_root_entry(struct rb_root *root, u64 objectid)
  167. {
  168. struct rb_node *n;
  169. struct root_entry *entry = NULL;
  170. n = root->rb_node;
  171. while (n) {
  172. entry = rb_entry(n, struct root_entry, node);
  173. if (entry->root_objectid < objectid)
  174. n = n->rb_right;
  175. else if (entry->root_objectid > objectid)
  176. n = n->rb_left;
  177. else
  178. return entry;
  179. }
  180. return NULL;
  181. }
  182. #ifdef CONFIG_STACKTRACE
  183. static void __save_stack_trace(struct ref_action *ra)
  184. {
  185. ra->trace_len = stack_trace_save(ra->trace, MAX_TRACE, 2);
  186. }
  187. static void __print_stack_trace(struct btrfs_fs_info *fs_info,
  188. struct ref_action *ra)
  189. {
  190. if (ra->trace_len == 0) {
  191. btrfs_err(fs_info, " ref-verify: no stacktrace");
  192. return;
  193. }
  194. stack_trace_print(ra->trace, ra->trace_len, 2);
  195. }
  196. #else
  197. static inline void __save_stack_trace(struct ref_action *ra)
  198. {
  199. }
  200. static inline void __print_stack_trace(struct btrfs_fs_info *fs_info,
  201. struct ref_action *ra)
  202. {
  203. btrfs_err(fs_info, " ref-verify: no stacktrace support");
  204. }
  205. #endif
  206. static void free_block_entry(struct block_entry *be)
  207. {
  208. struct root_entry *re;
  209. struct ref_entry *ref;
  210. struct ref_action *ra;
  211. struct rb_node *n;
  212. while ((n = rb_first(&be->roots))) {
  213. re = rb_entry(n, struct root_entry, node);
  214. rb_erase(&re->node, &be->roots);
  215. kfree(re);
  216. }
  217. while((n = rb_first(&be->refs))) {
  218. ref = rb_entry(n, struct ref_entry, node);
  219. rb_erase(&ref->node, &be->refs);
  220. kfree(ref);
  221. }
  222. while (!list_empty(&be->actions)) {
  223. ra = list_first_entry(&be->actions, struct ref_action,
  224. list);
  225. list_del(&ra->list);
  226. kfree(ra);
  227. }
  228. kfree(be);
  229. }
  230. static struct block_entry *add_block_entry(struct btrfs_fs_info *fs_info,
  231. u64 bytenr, u64 len,
  232. u64 root_objectid)
  233. {
  234. struct block_entry *be = NULL, *exist;
  235. struct root_entry *re = NULL;
  236. re = kzalloc(sizeof(struct root_entry), GFP_NOFS);
  237. be = kzalloc(sizeof(struct block_entry), GFP_NOFS);
  238. if (!be || !re) {
  239. kfree(re);
  240. kfree(be);
  241. return ERR_PTR(-ENOMEM);
  242. }
  243. be->bytenr = bytenr;
  244. be->len = len;
  245. re->root_objectid = root_objectid;
  246. re->num_refs = 0;
  247. spin_lock(&fs_info->ref_verify_lock);
  248. exist = insert_block_entry(&fs_info->block_tree, be);
  249. if (exist) {
  250. if (root_objectid) {
  251. struct root_entry *exist_re;
  252. exist_re = insert_root_entry(&exist->roots, re);
  253. if (exist_re)
  254. kfree(re);
  255. } else {
  256. kfree(re);
  257. }
  258. kfree(be);
  259. return exist;
  260. }
  261. be->num_refs = 0;
  262. be->metadata = 0;
  263. be->from_disk = 0;
  264. be->roots = RB_ROOT;
  265. be->refs = RB_ROOT;
  266. INIT_LIST_HEAD(&be->actions);
  267. if (root_objectid)
  268. insert_root_entry(&be->roots, re);
  269. else
  270. kfree(re);
  271. return be;
  272. }
  273. static int add_tree_block(struct btrfs_fs_info *fs_info, u64 ref_root,
  274. u64 parent, u64 bytenr, int level)
  275. {
  276. struct block_entry *be;
  277. struct root_entry *re;
  278. struct ref_entry *ref = NULL, *exist;
  279. ref = kmalloc(sizeof(struct ref_entry), GFP_NOFS);
  280. if (!ref)
  281. return -ENOMEM;
  282. if (parent)
  283. ref->root_objectid = 0;
  284. else
  285. ref->root_objectid = ref_root;
  286. ref->parent = parent;
  287. ref->owner = level;
  288. ref->offset = 0;
  289. ref->num_refs = 1;
  290. be = add_block_entry(fs_info, bytenr, fs_info->nodesize, ref_root);
  291. if (IS_ERR(be)) {
  292. kfree(ref);
  293. return PTR_ERR(be);
  294. }
  295. be->num_refs++;
  296. be->from_disk = 1;
  297. be->metadata = 1;
  298. if (!parent) {
  299. ASSERT(ref_root);
  300. re = lookup_root_entry(&be->roots, ref_root);
  301. ASSERT(re);
  302. re->num_refs++;
  303. }
  304. exist = insert_ref_entry(&be->refs, ref);
  305. if (exist) {
  306. exist->num_refs++;
  307. kfree(ref);
  308. }
  309. spin_unlock(&fs_info->ref_verify_lock);
  310. return 0;
  311. }
  312. static int add_shared_data_ref(struct btrfs_fs_info *fs_info,
  313. u64 parent, u32 num_refs, u64 bytenr,
  314. u64 num_bytes)
  315. {
  316. struct block_entry *be;
  317. struct ref_entry *ref;
  318. ref = kzalloc(sizeof(struct ref_entry), GFP_NOFS);
  319. if (!ref)
  320. return -ENOMEM;
  321. be = add_block_entry(fs_info, bytenr, num_bytes, 0);
  322. if (IS_ERR(be)) {
  323. kfree(ref);
  324. return PTR_ERR(be);
  325. }
  326. be->num_refs += num_refs;
  327. ref->parent = parent;
  328. ref->num_refs = num_refs;
  329. if (insert_ref_entry(&be->refs, ref)) {
  330. spin_unlock(&fs_info->ref_verify_lock);
  331. btrfs_err(fs_info, "existing shared ref when reading from disk?");
  332. kfree(ref);
  333. return -EINVAL;
  334. }
  335. spin_unlock(&fs_info->ref_verify_lock);
  336. return 0;
  337. }
  338. static int add_extent_data_ref(struct btrfs_fs_info *fs_info,
  339. struct extent_buffer *leaf,
  340. struct btrfs_extent_data_ref *dref,
  341. u64 bytenr, u64 num_bytes)
  342. {
  343. struct block_entry *be;
  344. struct ref_entry *ref;
  345. struct root_entry *re;
  346. u64 ref_root = btrfs_extent_data_ref_root(leaf, dref);
  347. u64 owner = btrfs_extent_data_ref_objectid(leaf, dref);
  348. u64 offset = btrfs_extent_data_ref_offset(leaf, dref);
  349. u32 num_refs = btrfs_extent_data_ref_count(leaf, dref);
  350. ref = kzalloc(sizeof(struct ref_entry), GFP_NOFS);
  351. if (!ref)
  352. return -ENOMEM;
  353. be = add_block_entry(fs_info, bytenr, num_bytes, ref_root);
  354. if (IS_ERR(be)) {
  355. kfree(ref);
  356. return PTR_ERR(be);
  357. }
  358. be->num_refs += num_refs;
  359. ref->parent = 0;
  360. ref->owner = owner;
  361. ref->root_objectid = ref_root;
  362. ref->offset = offset;
  363. ref->num_refs = num_refs;
  364. if (insert_ref_entry(&be->refs, ref)) {
  365. spin_unlock(&fs_info->ref_verify_lock);
  366. btrfs_err(fs_info, "existing ref when reading from disk?");
  367. kfree(ref);
  368. return -EINVAL;
  369. }
  370. re = lookup_root_entry(&be->roots, ref_root);
  371. if (!re) {
  372. spin_unlock(&fs_info->ref_verify_lock);
  373. btrfs_err(fs_info, "missing root in new block entry?");
  374. return -EINVAL;
  375. }
  376. re->num_refs += num_refs;
  377. spin_unlock(&fs_info->ref_verify_lock);
  378. return 0;
  379. }
  380. static int process_extent_item(struct btrfs_fs_info *fs_info,
  381. struct btrfs_path *path, struct btrfs_key *key,
  382. int slot, int *tree_block_level)
  383. {
  384. struct btrfs_extent_item *ei;
  385. struct btrfs_extent_inline_ref *iref;
  386. struct btrfs_extent_data_ref *dref;
  387. struct btrfs_shared_data_ref *sref;
  388. struct extent_buffer *leaf = path->nodes[0];
  389. u32 item_size = btrfs_item_size(leaf, slot);
  390. unsigned long end, ptr;
  391. u64 offset, flags, count;
  392. int type, ret;
  393. ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
  394. flags = btrfs_extent_flags(leaf, ei);
  395. if ((key->type == BTRFS_EXTENT_ITEM_KEY) &&
  396. flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
  397. struct btrfs_tree_block_info *info;
  398. info = (struct btrfs_tree_block_info *)(ei + 1);
  399. *tree_block_level = btrfs_tree_block_level(leaf, info);
  400. iref = (struct btrfs_extent_inline_ref *)(info + 1);
  401. } else {
  402. if (key->type == BTRFS_METADATA_ITEM_KEY)
  403. *tree_block_level = key->offset;
  404. iref = (struct btrfs_extent_inline_ref *)(ei + 1);
  405. }
  406. ptr = (unsigned long)iref;
  407. end = (unsigned long)ei + item_size;
  408. while (ptr < end) {
  409. iref = (struct btrfs_extent_inline_ref *)ptr;
  410. type = btrfs_extent_inline_ref_type(leaf, iref);
  411. offset = btrfs_extent_inline_ref_offset(leaf, iref);
  412. switch (type) {
  413. case BTRFS_TREE_BLOCK_REF_KEY:
  414. ret = add_tree_block(fs_info, offset, 0, key->objectid,
  415. *tree_block_level);
  416. break;
  417. case BTRFS_SHARED_BLOCK_REF_KEY:
  418. ret = add_tree_block(fs_info, 0, offset, key->objectid,
  419. *tree_block_level);
  420. break;
  421. case BTRFS_EXTENT_DATA_REF_KEY:
  422. dref = (struct btrfs_extent_data_ref *)(&iref->offset);
  423. ret = add_extent_data_ref(fs_info, leaf, dref,
  424. key->objectid, key->offset);
  425. break;
  426. case BTRFS_SHARED_DATA_REF_KEY:
  427. sref = (struct btrfs_shared_data_ref *)(iref + 1);
  428. count = btrfs_shared_data_ref_count(leaf, sref);
  429. ret = add_shared_data_ref(fs_info, offset, count,
  430. key->objectid, key->offset);
  431. break;
  432. default:
  433. btrfs_err(fs_info, "invalid key type in iref");
  434. ret = -EINVAL;
  435. break;
  436. }
  437. if (ret)
  438. break;
  439. ptr += btrfs_extent_inline_ref_size(type);
  440. }
  441. return ret;
  442. }
  443. static int process_leaf(struct btrfs_root *root,
  444. struct btrfs_path *path, u64 *bytenr, u64 *num_bytes,
  445. int *tree_block_level)
  446. {
  447. struct btrfs_fs_info *fs_info = root->fs_info;
  448. struct extent_buffer *leaf = path->nodes[0];
  449. struct btrfs_extent_data_ref *dref;
  450. struct btrfs_shared_data_ref *sref;
  451. u32 count;
  452. int i = 0, ret = 0;
  453. struct btrfs_key key;
  454. int nritems = btrfs_header_nritems(leaf);
  455. for (i = 0; i < nritems; i++) {
  456. btrfs_item_key_to_cpu(leaf, &key, i);
  457. switch (key.type) {
  458. case BTRFS_EXTENT_ITEM_KEY:
  459. *num_bytes = key.offset;
  460. fallthrough;
  461. case BTRFS_METADATA_ITEM_KEY:
  462. *bytenr = key.objectid;
  463. ret = process_extent_item(fs_info, path, &key, i,
  464. tree_block_level);
  465. break;
  466. case BTRFS_TREE_BLOCK_REF_KEY:
  467. ret = add_tree_block(fs_info, key.offset, 0,
  468. key.objectid, *tree_block_level);
  469. break;
  470. case BTRFS_SHARED_BLOCK_REF_KEY:
  471. ret = add_tree_block(fs_info, 0, key.offset,
  472. key.objectid, *tree_block_level);
  473. break;
  474. case BTRFS_EXTENT_DATA_REF_KEY:
  475. dref = btrfs_item_ptr(leaf, i,
  476. struct btrfs_extent_data_ref);
  477. ret = add_extent_data_ref(fs_info, leaf, dref, *bytenr,
  478. *num_bytes);
  479. break;
  480. case BTRFS_SHARED_DATA_REF_KEY:
  481. sref = btrfs_item_ptr(leaf, i,
  482. struct btrfs_shared_data_ref);
  483. count = btrfs_shared_data_ref_count(leaf, sref);
  484. ret = add_shared_data_ref(fs_info, key.offset, count,
  485. *bytenr, *num_bytes);
  486. break;
  487. default:
  488. break;
  489. }
  490. if (ret)
  491. break;
  492. }
  493. return ret;
  494. }
  495. /* Walk down to the leaf from the given level */
  496. static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
  497. int level, u64 *bytenr, u64 *num_bytes,
  498. int *tree_block_level)
  499. {
  500. struct extent_buffer *eb;
  501. int ret = 0;
  502. while (level >= 0) {
  503. if (level) {
  504. eb = btrfs_read_node_slot(path->nodes[level],
  505. path->slots[level]);
  506. if (IS_ERR(eb))
  507. return PTR_ERR(eb);
  508. btrfs_tree_read_lock(eb);
  509. path->nodes[level-1] = eb;
  510. path->slots[level-1] = 0;
  511. path->locks[level-1] = BTRFS_READ_LOCK;
  512. } else {
  513. ret = process_leaf(root, path, bytenr, num_bytes,
  514. tree_block_level);
  515. if (ret)
  516. break;
  517. }
  518. level--;
  519. }
  520. return ret;
  521. }
  522. /* Walk up to the next node that needs to be processed */
  523. static int walk_up_tree(struct btrfs_path *path, int *level)
  524. {
  525. int l;
  526. for (l = 0; l < BTRFS_MAX_LEVEL; l++) {
  527. if (!path->nodes[l])
  528. continue;
  529. if (l) {
  530. path->slots[l]++;
  531. if (path->slots[l] <
  532. btrfs_header_nritems(path->nodes[l])) {
  533. *level = l;
  534. return 0;
  535. }
  536. }
  537. btrfs_tree_unlock_rw(path->nodes[l], path->locks[l]);
  538. free_extent_buffer(path->nodes[l]);
  539. path->nodes[l] = NULL;
  540. path->slots[l] = 0;
  541. path->locks[l] = 0;
  542. }
  543. return 1;
  544. }
  545. static void dump_ref_action(struct btrfs_fs_info *fs_info,
  546. struct ref_action *ra)
  547. {
  548. btrfs_err(fs_info,
  549. " Ref action %d, root %llu, ref_root %llu, parent %llu, owner %llu, offset %llu, num_refs %llu",
  550. ra->action, ra->root, ra->ref.root_objectid, ra->ref.parent,
  551. ra->ref.owner, ra->ref.offset, ra->ref.num_refs);
  552. __print_stack_trace(fs_info, ra);
  553. }
  554. /*
  555. * Dumps all the information from the block entry to printk, it's going to be
  556. * awesome.
  557. */
  558. static void dump_block_entry(struct btrfs_fs_info *fs_info,
  559. struct block_entry *be)
  560. {
  561. struct ref_entry *ref;
  562. struct root_entry *re;
  563. struct ref_action *ra;
  564. struct rb_node *n;
  565. btrfs_err(fs_info,
  566. "dumping block entry [%llu %llu], num_refs %llu, metadata %d, from disk %d",
  567. be->bytenr, be->len, be->num_refs, be->metadata,
  568. be->from_disk);
  569. for (n = rb_first(&be->refs); n; n = rb_next(n)) {
  570. ref = rb_entry(n, struct ref_entry, node);
  571. btrfs_err(fs_info,
  572. " ref root %llu, parent %llu, owner %llu, offset %llu, num_refs %llu",
  573. ref->root_objectid, ref->parent, ref->owner,
  574. ref->offset, ref->num_refs);
  575. }
  576. for (n = rb_first(&be->roots); n; n = rb_next(n)) {
  577. re = rb_entry(n, struct root_entry, node);
  578. btrfs_err(fs_info, " root entry %llu, num_refs %llu",
  579. re->root_objectid, re->num_refs);
  580. }
  581. list_for_each_entry(ra, &be->actions, list)
  582. dump_ref_action(fs_info, ra);
  583. }
  584. /*
  585. * btrfs_ref_tree_mod: called when we modify a ref for a bytenr
  586. *
  587. * This will add an action item to the given bytenr and do sanity checks to make
  588. * sure we haven't messed something up. If we are making a new allocation and
  589. * this block entry has history we will delete all previous actions as long as
  590. * our sanity checks pass as they are no longer needed.
  591. */
  592. int btrfs_ref_tree_mod(struct btrfs_fs_info *fs_info,
  593. struct btrfs_ref *generic_ref)
  594. {
  595. struct ref_entry *ref = NULL, *exist;
  596. struct ref_action *ra = NULL;
  597. struct block_entry *be = NULL;
  598. struct root_entry *re = NULL;
  599. int action = generic_ref->action;
  600. int ret = 0;
  601. bool metadata;
  602. u64 bytenr = generic_ref->bytenr;
  603. u64 num_bytes = generic_ref->len;
  604. u64 parent = generic_ref->parent;
  605. u64 ref_root = 0;
  606. u64 owner = 0;
  607. u64 offset = 0;
  608. if (!btrfs_test_opt(fs_info, REF_VERIFY))
  609. return 0;
  610. if (generic_ref->type == BTRFS_REF_METADATA) {
  611. if (!parent)
  612. ref_root = generic_ref->tree_ref.owning_root;
  613. owner = generic_ref->tree_ref.level;
  614. } else if (!parent) {
  615. ref_root = generic_ref->data_ref.owning_root;
  616. owner = generic_ref->data_ref.ino;
  617. offset = generic_ref->data_ref.offset;
  618. }
  619. metadata = owner < BTRFS_FIRST_FREE_OBJECTID;
  620. ref = kzalloc(sizeof(struct ref_entry), GFP_NOFS);
  621. ra = kmalloc(sizeof(struct ref_action), GFP_NOFS);
  622. if (!ra || !ref) {
  623. kfree(ref);
  624. kfree(ra);
  625. ret = -ENOMEM;
  626. goto out;
  627. }
  628. ref->parent = parent;
  629. ref->owner = owner;
  630. ref->root_objectid = ref_root;
  631. ref->offset = offset;
  632. ref->num_refs = (action == BTRFS_DROP_DELAYED_REF) ? -1 : 1;
  633. memcpy(&ra->ref, ref, sizeof(struct ref_entry));
  634. /*
  635. * Save the extra info from the delayed ref in the ref action to make it
  636. * easier to figure out what is happening. The real ref's we add to the
  637. * ref tree need to reflect what we save on disk so it matches any
  638. * on-disk refs we pre-loaded.
  639. */
  640. ra->ref.owner = owner;
  641. ra->ref.offset = offset;
  642. ra->ref.root_objectid = ref_root;
  643. __save_stack_trace(ra);
  644. INIT_LIST_HEAD(&ra->list);
  645. ra->action = action;
  646. ra->root = generic_ref->real_root;
  647. /*
  648. * This is an allocation, preallocate the block_entry in case we haven't
  649. * used it before.
  650. */
  651. ret = -EINVAL;
  652. if (action == BTRFS_ADD_DELAYED_EXTENT) {
  653. /*
  654. * For subvol_create we'll just pass in whatever the parent root
  655. * is and the new root objectid, so let's not treat the passed
  656. * in root as if it really has a ref for this bytenr.
  657. */
  658. be = add_block_entry(fs_info, bytenr, num_bytes, ref_root);
  659. if (IS_ERR(be)) {
  660. kfree(ref);
  661. kfree(ra);
  662. ret = PTR_ERR(be);
  663. goto out;
  664. }
  665. be->num_refs++;
  666. if (metadata)
  667. be->metadata = 1;
  668. if (be->num_refs != 1) {
  669. btrfs_err(fs_info,
  670. "re-allocated a block that still has references to it!");
  671. dump_block_entry(fs_info, be);
  672. dump_ref_action(fs_info, ra);
  673. kfree(ref);
  674. kfree(ra);
  675. goto out_unlock;
  676. }
  677. while (!list_empty(&be->actions)) {
  678. struct ref_action *tmp;
  679. tmp = list_first_entry(&be->actions, struct ref_action,
  680. list);
  681. list_del(&tmp->list);
  682. kfree(tmp);
  683. }
  684. } else {
  685. struct root_entry *tmp;
  686. if (!parent) {
  687. re = kmalloc(sizeof(struct root_entry), GFP_NOFS);
  688. if (!re) {
  689. kfree(ref);
  690. kfree(ra);
  691. ret = -ENOMEM;
  692. goto out;
  693. }
  694. /*
  695. * This is the root that is modifying us, so it's the
  696. * one we want to lookup below when we modify the
  697. * re->num_refs.
  698. */
  699. ref_root = generic_ref->real_root;
  700. re->root_objectid = generic_ref->real_root;
  701. re->num_refs = 0;
  702. }
  703. spin_lock(&fs_info->ref_verify_lock);
  704. be = lookup_block_entry(&fs_info->block_tree, bytenr);
  705. if (!be) {
  706. btrfs_err(fs_info,
  707. "trying to do action %d to bytenr %llu num_bytes %llu but there is no existing entry!",
  708. action, bytenr, num_bytes);
  709. dump_ref_action(fs_info, ra);
  710. kfree(ref);
  711. kfree(ra);
  712. kfree(re);
  713. goto out_unlock;
  714. } else if (be->num_refs == 0) {
  715. btrfs_err(fs_info,
  716. "trying to do action %d for a bytenr that has 0 total references",
  717. action);
  718. dump_block_entry(fs_info, be);
  719. dump_ref_action(fs_info, ra);
  720. kfree(ref);
  721. kfree(ra);
  722. kfree(re);
  723. goto out_unlock;
  724. }
  725. if (!parent) {
  726. tmp = insert_root_entry(&be->roots, re);
  727. if (tmp) {
  728. kfree(re);
  729. re = tmp;
  730. }
  731. }
  732. }
  733. exist = insert_ref_entry(&be->refs, ref);
  734. if (exist) {
  735. if (action == BTRFS_DROP_DELAYED_REF) {
  736. if (exist->num_refs == 0) {
  737. btrfs_err(fs_info,
  738. "dropping a ref for a existing root that doesn't have a ref on the block");
  739. dump_block_entry(fs_info, be);
  740. dump_ref_action(fs_info, ra);
  741. kfree(ref);
  742. kfree(ra);
  743. goto out_unlock;
  744. }
  745. exist->num_refs--;
  746. if (exist->num_refs == 0) {
  747. rb_erase(&exist->node, &be->refs);
  748. kfree(exist);
  749. }
  750. } else if (!be->metadata) {
  751. exist->num_refs++;
  752. } else {
  753. btrfs_err(fs_info,
  754. "attempting to add another ref for an existing ref on a tree block");
  755. dump_block_entry(fs_info, be);
  756. dump_ref_action(fs_info, ra);
  757. kfree(ref);
  758. kfree(ra);
  759. goto out_unlock;
  760. }
  761. kfree(ref);
  762. } else {
  763. if (action == BTRFS_DROP_DELAYED_REF) {
  764. btrfs_err(fs_info,
  765. "dropping a ref for a root that doesn't have a ref on the block");
  766. dump_block_entry(fs_info, be);
  767. dump_ref_action(fs_info, ra);
  768. kfree(ref);
  769. kfree(ra);
  770. goto out_unlock;
  771. }
  772. }
  773. if (!parent && !re) {
  774. re = lookup_root_entry(&be->roots, ref_root);
  775. if (!re) {
  776. /*
  777. * This shouldn't happen because we will add our re
  778. * above when we lookup the be with !parent, but just in
  779. * case catch this case so we don't panic because I
  780. * didn't think of some other corner case.
  781. */
  782. btrfs_err(fs_info, "failed to find root %llu for %llu",
  783. generic_ref->real_root, be->bytenr);
  784. dump_block_entry(fs_info, be);
  785. dump_ref_action(fs_info, ra);
  786. kfree(ra);
  787. goto out_unlock;
  788. }
  789. }
  790. if (action == BTRFS_DROP_DELAYED_REF) {
  791. if (re)
  792. re->num_refs--;
  793. be->num_refs--;
  794. } else if (action == BTRFS_ADD_DELAYED_REF) {
  795. be->num_refs++;
  796. if (re)
  797. re->num_refs++;
  798. }
  799. list_add_tail(&ra->list, &be->actions);
  800. ret = 0;
  801. out_unlock:
  802. spin_unlock(&fs_info->ref_verify_lock);
  803. out:
  804. if (ret)
  805. btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
  806. return ret;
  807. }
  808. /* Free up the ref cache */
  809. void btrfs_free_ref_cache(struct btrfs_fs_info *fs_info)
  810. {
  811. struct block_entry *be;
  812. struct rb_node *n;
  813. if (!btrfs_test_opt(fs_info, REF_VERIFY))
  814. return;
  815. spin_lock(&fs_info->ref_verify_lock);
  816. while ((n = rb_first(&fs_info->block_tree))) {
  817. be = rb_entry(n, struct block_entry, node);
  818. rb_erase(&be->node, &fs_info->block_tree);
  819. free_block_entry(be);
  820. cond_resched_lock(&fs_info->ref_verify_lock);
  821. }
  822. spin_unlock(&fs_info->ref_verify_lock);
  823. }
  824. void btrfs_free_ref_tree_range(struct btrfs_fs_info *fs_info, u64 start,
  825. u64 len)
  826. {
  827. struct block_entry *be = NULL, *entry;
  828. struct rb_node *n;
  829. if (!btrfs_test_opt(fs_info, REF_VERIFY))
  830. return;
  831. spin_lock(&fs_info->ref_verify_lock);
  832. n = fs_info->block_tree.rb_node;
  833. while (n) {
  834. entry = rb_entry(n, struct block_entry, node);
  835. if (entry->bytenr < start) {
  836. n = n->rb_right;
  837. } else if (entry->bytenr > start) {
  838. n = n->rb_left;
  839. } else {
  840. be = entry;
  841. break;
  842. }
  843. /* We want to get as close to start as possible */
  844. if (be == NULL ||
  845. (entry->bytenr < start && be->bytenr > start) ||
  846. (entry->bytenr < start && entry->bytenr > be->bytenr))
  847. be = entry;
  848. }
  849. /*
  850. * Could have an empty block group, maybe have something to check for
  851. * this case to verify we were actually empty?
  852. */
  853. if (!be) {
  854. spin_unlock(&fs_info->ref_verify_lock);
  855. return;
  856. }
  857. n = &be->node;
  858. while (n) {
  859. be = rb_entry(n, struct block_entry, node);
  860. n = rb_next(n);
  861. if (be->bytenr < start && be->bytenr + be->len > start) {
  862. btrfs_err(fs_info,
  863. "block entry overlaps a block group [%llu,%llu]!",
  864. start, len);
  865. dump_block_entry(fs_info, be);
  866. continue;
  867. }
  868. if (be->bytenr < start)
  869. continue;
  870. if (be->bytenr >= start + len)
  871. break;
  872. if (be->bytenr + be->len > start + len) {
  873. btrfs_err(fs_info,
  874. "block entry overlaps a block group [%llu,%llu]!",
  875. start, len);
  876. dump_block_entry(fs_info, be);
  877. }
  878. rb_erase(&be->node, &fs_info->block_tree);
  879. free_block_entry(be);
  880. }
  881. spin_unlock(&fs_info->ref_verify_lock);
  882. }
  883. /* Walk down all roots and build the ref tree, meant to be called at mount */
  884. int btrfs_build_ref_tree(struct btrfs_fs_info *fs_info)
  885. {
  886. struct btrfs_root *extent_root;
  887. struct btrfs_path *path;
  888. struct extent_buffer *eb;
  889. int tree_block_level = 0;
  890. u64 bytenr = 0, num_bytes = 0;
  891. int ret, level;
  892. if (!btrfs_test_opt(fs_info, REF_VERIFY))
  893. return 0;
  894. path = btrfs_alloc_path();
  895. if (!path)
  896. return -ENOMEM;
  897. extent_root = btrfs_extent_root(fs_info, 0);
  898. eb = btrfs_read_lock_root_node(extent_root);
  899. level = btrfs_header_level(eb);
  900. path->nodes[level] = eb;
  901. path->slots[level] = 0;
  902. path->locks[level] = BTRFS_READ_LOCK;
  903. while (1) {
  904. /*
  905. * We have to keep track of the bytenr/num_bytes we last hit
  906. * because we could have run out of space for an inline ref, and
  907. * would have had to added a ref key item which may appear on a
  908. * different leaf from the original extent item.
  909. */
  910. ret = walk_down_tree(extent_root, path, level,
  911. &bytenr, &num_bytes, &tree_block_level);
  912. if (ret)
  913. break;
  914. ret = walk_up_tree(path, &level);
  915. if (ret < 0)
  916. break;
  917. if (ret > 0) {
  918. ret = 0;
  919. break;
  920. }
  921. }
  922. if (ret) {
  923. btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
  924. btrfs_free_ref_cache(fs_info);
  925. }
  926. btrfs_free_path(path);
  927. return ret;
  928. }