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