btrfs: start readahead also in seed devices
[linux-2.6-microblaze.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 that's 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 occurred 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                 }
301                 kfree(be);
302                 return exist;
303         }
304
305         be->num_refs = 0;
306         be->metadata = 0;
307         be->from_disk = 0;
308         be->roots = RB_ROOT;
309         be->refs = RB_ROOT;
310         INIT_LIST_HEAD(&be->actions);
311         if (root_objectid)
312                 insert_root_entry(&be->roots, re);
313         else
314                 kfree(re);
315         return be;
316 }
317
318 static int add_tree_block(struct btrfs_fs_info *fs_info, u64 ref_root,
319                           u64 parent, u64 bytenr, int level)
320 {
321         struct block_entry *be;
322         struct root_entry *re;
323         struct ref_entry *ref = NULL, *exist;
324
325         ref = kmalloc(sizeof(struct ref_entry), GFP_KERNEL);
326         if (!ref)
327                 return -ENOMEM;
328
329         if (parent)
330                 ref->root_objectid = 0;
331         else
332                 ref->root_objectid = ref_root;
333         ref->parent = parent;
334         ref->owner = level;
335         ref->offset = 0;
336         ref->num_refs = 1;
337
338         be = add_block_entry(fs_info, bytenr, fs_info->nodesize, ref_root);
339         if (IS_ERR(be)) {
340                 kfree(ref);
341                 return PTR_ERR(be);
342         }
343         be->num_refs++;
344         be->from_disk = 1;
345         be->metadata = 1;
346
347         if (!parent) {
348                 ASSERT(ref_root);
349                 re = lookup_root_entry(&be->roots, ref_root);
350                 ASSERT(re);
351                 re->num_refs++;
352         }
353         exist = insert_ref_entry(&be->refs, ref);
354         if (exist) {
355                 exist->num_refs++;
356                 kfree(ref);
357         }
358         spin_unlock(&fs_info->ref_verify_lock);
359
360         return 0;
361 }
362
363 static int add_shared_data_ref(struct btrfs_fs_info *fs_info,
364                                u64 parent, u32 num_refs, u64 bytenr,
365                                u64 num_bytes)
366 {
367         struct block_entry *be;
368         struct ref_entry *ref;
369
370         ref = kzalloc(sizeof(struct ref_entry), GFP_KERNEL);
371         if (!ref)
372                 return -ENOMEM;
373         be = add_block_entry(fs_info, bytenr, num_bytes, 0);
374         if (IS_ERR(be)) {
375                 kfree(ref);
376                 return PTR_ERR(be);
377         }
378         be->num_refs += num_refs;
379
380         ref->parent = parent;
381         ref->num_refs = num_refs;
382         if (insert_ref_entry(&be->refs, ref)) {
383                 spin_unlock(&fs_info->ref_verify_lock);
384                 btrfs_err(fs_info, "existing shared ref when reading from disk?");
385                 kfree(ref);
386                 return -EINVAL;
387         }
388         spin_unlock(&fs_info->ref_verify_lock);
389         return 0;
390 }
391
392 static int add_extent_data_ref(struct btrfs_fs_info *fs_info,
393                                struct extent_buffer *leaf,
394                                struct btrfs_extent_data_ref *dref,
395                                u64 bytenr, u64 num_bytes)
396 {
397         struct block_entry *be;
398         struct ref_entry *ref;
399         struct root_entry *re;
400         u64 ref_root = btrfs_extent_data_ref_root(leaf, dref);
401         u64 owner = btrfs_extent_data_ref_objectid(leaf, dref);
402         u64 offset = btrfs_extent_data_ref_offset(leaf, dref);
403         u32 num_refs = btrfs_extent_data_ref_count(leaf, dref);
404
405         ref = kzalloc(sizeof(struct ref_entry), GFP_KERNEL);
406         if (!ref)
407                 return -ENOMEM;
408         be = add_block_entry(fs_info, bytenr, num_bytes, ref_root);
409         if (IS_ERR(be)) {
410                 kfree(ref);
411                 return PTR_ERR(be);
412         }
413         be->num_refs += num_refs;
414
415         ref->parent = 0;
416         ref->owner = owner;
417         ref->root_objectid = ref_root;
418         ref->offset = offset;
419         ref->num_refs = num_refs;
420         if (insert_ref_entry(&be->refs, ref)) {
421                 spin_unlock(&fs_info->ref_verify_lock);
422                 btrfs_err(fs_info, "existing ref when reading from disk?");
423                 kfree(ref);
424                 return -EINVAL;
425         }
426
427         re = lookup_root_entry(&be->roots, ref_root);
428         if (!re) {
429                 spin_unlock(&fs_info->ref_verify_lock);
430                 btrfs_err(fs_info, "missing root in new block entry?");
431                 return -EINVAL;
432         }
433         re->num_refs += num_refs;
434         spin_unlock(&fs_info->ref_verify_lock);
435         return 0;
436 }
437
438 static int process_extent_item(struct btrfs_fs_info *fs_info,
439                                struct btrfs_path *path, struct btrfs_key *key,
440                                int slot, int *tree_block_level)
441 {
442         struct btrfs_extent_item *ei;
443         struct btrfs_extent_inline_ref *iref;
444         struct btrfs_extent_data_ref *dref;
445         struct btrfs_shared_data_ref *sref;
446         struct extent_buffer *leaf = path->nodes[0];
447         u32 item_size = btrfs_item_size_nr(leaf, slot);
448         unsigned long end, ptr;
449         u64 offset, flags, count;
450         int type, ret;
451
452         ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
453         flags = btrfs_extent_flags(leaf, ei);
454
455         if ((key->type == BTRFS_EXTENT_ITEM_KEY) &&
456             flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
457                 struct btrfs_tree_block_info *info;
458
459                 info = (struct btrfs_tree_block_info *)(ei + 1);
460                 *tree_block_level = btrfs_tree_block_level(leaf, info);
461                 iref = (struct btrfs_extent_inline_ref *)(info + 1);
462         } else {
463                 if (key->type == BTRFS_METADATA_ITEM_KEY)
464                         *tree_block_level = key->offset;
465                 iref = (struct btrfs_extent_inline_ref *)(ei + 1);
466         }
467
468         ptr = (unsigned long)iref;
469         end = (unsigned long)ei + item_size;
470         while (ptr < end) {
471                 iref = (struct btrfs_extent_inline_ref *)ptr;
472                 type = btrfs_extent_inline_ref_type(leaf, iref);
473                 offset = btrfs_extent_inline_ref_offset(leaf, iref);
474                 switch (type) {
475                 case BTRFS_TREE_BLOCK_REF_KEY:
476                         ret = add_tree_block(fs_info, offset, 0, key->objectid,
477                                              *tree_block_level);
478                         break;
479                 case BTRFS_SHARED_BLOCK_REF_KEY:
480                         ret = add_tree_block(fs_info, 0, offset, key->objectid,
481                                              *tree_block_level);
482                         break;
483                 case BTRFS_EXTENT_DATA_REF_KEY:
484                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
485                         ret = add_extent_data_ref(fs_info, leaf, dref,
486                                                   key->objectid, key->offset);
487                         break;
488                 case BTRFS_SHARED_DATA_REF_KEY:
489                         sref = (struct btrfs_shared_data_ref *)(iref + 1);
490                         count = btrfs_shared_data_ref_count(leaf, sref);
491                         ret = add_shared_data_ref(fs_info, offset, count,
492                                                   key->objectid, key->offset);
493                         break;
494                 default:
495                         btrfs_err(fs_info, "invalid key type in iref");
496                         ret = -EINVAL;
497                         break;
498                 }
499                 if (ret)
500                         break;
501                 ptr += btrfs_extent_inline_ref_size(type);
502         }
503         return ret;
504 }
505
506 static int process_leaf(struct btrfs_root *root,
507                         struct btrfs_path *path, u64 *bytenr, u64 *num_bytes)
508 {
509         struct btrfs_fs_info *fs_info = root->fs_info;
510         struct extent_buffer *leaf = path->nodes[0];
511         struct btrfs_extent_data_ref *dref;
512         struct btrfs_shared_data_ref *sref;
513         u32 count;
514         int i = 0, tree_block_level = 0, ret;
515         struct btrfs_key key;
516         int nritems = btrfs_header_nritems(leaf);
517
518         for (i = 0; i < nritems; i++) {
519                 btrfs_item_key_to_cpu(leaf, &key, i);
520                 switch (key.type) {
521                 case BTRFS_EXTENT_ITEM_KEY:
522                         *num_bytes = key.offset;
523                 case BTRFS_METADATA_ITEM_KEY:
524                         *bytenr = key.objectid;
525                         ret = process_extent_item(fs_info, path, &key, i,
526                                                   &tree_block_level);
527                         break;
528                 case BTRFS_TREE_BLOCK_REF_KEY:
529                         ret = add_tree_block(fs_info, key.offset, 0,
530                                              key.objectid, tree_block_level);
531                         break;
532                 case BTRFS_SHARED_BLOCK_REF_KEY:
533                         ret = add_tree_block(fs_info, 0, key.offset,
534                                              key.objectid, tree_block_level);
535                         break;
536                 case BTRFS_EXTENT_DATA_REF_KEY:
537                         dref = btrfs_item_ptr(leaf, i,
538                                               struct btrfs_extent_data_ref);
539                         ret = add_extent_data_ref(fs_info, leaf, dref, *bytenr,
540                                                   *num_bytes);
541                         break;
542                 case BTRFS_SHARED_DATA_REF_KEY:
543                         sref = btrfs_item_ptr(leaf, i,
544                                               struct btrfs_shared_data_ref);
545                         count = btrfs_shared_data_ref_count(leaf, sref);
546                         ret = add_shared_data_ref(fs_info, key.offset, count,
547                                                   *bytenr, *num_bytes);
548                         break;
549                 default:
550                         break;
551                 }
552                 if (ret)
553                         break;
554         }
555         return ret;
556 }
557
558 /* Walk down to the leaf from the given level */
559 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
560                           int level, u64 *bytenr, u64 *num_bytes)
561 {
562         struct btrfs_fs_info *fs_info = root->fs_info;
563         struct extent_buffer *eb;
564         u64 block_bytenr, gen;
565         int ret = 0;
566
567         while (level >= 0) {
568                 if (level) {
569                         struct btrfs_key first_key;
570
571                         block_bytenr = btrfs_node_blockptr(path->nodes[level],
572                                                            path->slots[level]);
573                         gen = btrfs_node_ptr_generation(path->nodes[level],
574                                                         path->slots[level]);
575                         btrfs_node_key_to_cpu(path->nodes[level], &first_key,
576                                               path->slots[level]);
577                         eb = read_tree_block(fs_info, block_bytenr, gen,
578                                              level - 1, &first_key);
579                         if (IS_ERR(eb))
580                                 return PTR_ERR(eb);
581                         if (!extent_buffer_uptodate(eb)) {
582                                 free_extent_buffer(eb);
583                                 return -EIO;
584                         }
585                         btrfs_tree_read_lock(eb);
586                         btrfs_set_lock_blocking_read(eb);
587                         path->nodes[level-1] = eb;
588                         path->slots[level-1] = 0;
589                         path->locks[level-1] = BTRFS_READ_LOCK_BLOCKING;
590                 } else {
591                         ret = process_leaf(root, path, bytenr, num_bytes);
592                         if (ret)
593                                 break;
594                 }
595                 level--;
596         }
597         return ret;
598 }
599
600 /* Walk up to the next node that needs to be processed */
601 static int walk_up_tree(struct btrfs_path *path, int *level)
602 {
603         int l;
604
605         for (l = 0; l < BTRFS_MAX_LEVEL; l++) {
606                 if (!path->nodes[l])
607                         continue;
608                 if (l) {
609                         path->slots[l]++;
610                         if (path->slots[l] <
611                             btrfs_header_nritems(path->nodes[l])) {
612                                 *level = l;
613                                 return 0;
614                         }
615                 }
616                 btrfs_tree_unlock_rw(path->nodes[l], path->locks[l]);
617                 free_extent_buffer(path->nodes[l]);
618                 path->nodes[l] = NULL;
619                 path->slots[l] = 0;
620                 path->locks[l] = 0;
621         }
622
623         return 1;
624 }
625
626 static void dump_ref_action(struct btrfs_fs_info *fs_info,
627                             struct ref_action *ra)
628 {
629         btrfs_err(fs_info,
630 "  Ref action %d, root %llu, ref_root %llu, parent %llu, owner %llu, offset %llu, num_refs %llu",
631                   ra->action, ra->root, ra->ref.root_objectid, ra->ref.parent,
632                   ra->ref.owner, ra->ref.offset, ra->ref.num_refs);
633         __print_stack_trace(fs_info, ra);
634 }
635
636 /*
637  * Dumps all the information from the block entry to printk, it's going to be
638  * awesome.
639  */
640 static void dump_block_entry(struct btrfs_fs_info *fs_info,
641                              struct block_entry *be)
642 {
643         struct ref_entry *ref;
644         struct root_entry *re;
645         struct ref_action *ra;
646         struct rb_node *n;
647
648         btrfs_err(fs_info,
649 "dumping block entry [%llu %llu], num_refs %llu, metadata %d, from disk %d",
650                   be->bytenr, be->len, be->num_refs, be->metadata,
651                   be->from_disk);
652
653         for (n = rb_first(&be->refs); n; n = rb_next(n)) {
654                 ref = rb_entry(n, struct ref_entry, node);
655                 btrfs_err(fs_info,
656 "  ref root %llu, parent %llu, owner %llu, offset %llu, num_refs %llu",
657                           ref->root_objectid, ref->parent, ref->owner,
658                           ref->offset, ref->num_refs);
659         }
660
661         for (n = rb_first(&be->roots); n; n = rb_next(n)) {
662                 re = rb_entry(n, struct root_entry, node);
663                 btrfs_err(fs_info, "  root entry %llu, num_refs %llu",
664                           re->root_objectid, re->num_refs);
665         }
666
667         list_for_each_entry(ra, &be->actions, list)
668                 dump_ref_action(fs_info, ra);
669 }
670
671 /*
672  * btrfs_ref_tree_mod: called when we modify a ref for a bytenr
673  *
674  * This will add an action item to the given bytenr and do sanity checks to make
675  * sure we haven't messed something up.  If we are making a new allocation and
676  * this block entry has history we will delete all previous actions as long as
677  * our sanity checks pass as they are no longer needed.
678  */
679 int btrfs_ref_tree_mod(struct btrfs_fs_info *fs_info,
680                        struct btrfs_ref *generic_ref)
681 {
682         struct ref_entry *ref = NULL, *exist;
683         struct ref_action *ra = NULL;
684         struct block_entry *be = NULL;
685         struct root_entry *re = NULL;
686         int action = generic_ref->action;
687         int ret = 0;
688         bool metadata;
689         u64 bytenr = generic_ref->bytenr;
690         u64 num_bytes = generic_ref->len;
691         u64 parent = generic_ref->parent;
692         u64 ref_root;
693         u64 owner;
694         u64 offset;
695
696         if (!btrfs_test_opt(fs_info, REF_VERIFY))
697                 return 0;
698
699         if (generic_ref->type == BTRFS_REF_METADATA) {
700                 ref_root = generic_ref->tree_ref.root;
701                 owner = generic_ref->tree_ref.level;
702                 offset = 0;
703         } else {
704                 ref_root = generic_ref->data_ref.ref_root;
705                 owner = generic_ref->data_ref.ino;
706                 offset = generic_ref->data_ref.offset;
707         }
708         metadata = owner < BTRFS_FIRST_FREE_OBJECTID;
709
710         ref = kzalloc(sizeof(struct ref_entry), GFP_NOFS);
711         ra = kmalloc(sizeof(struct ref_action), GFP_NOFS);
712         if (!ra || !ref) {
713                 kfree(ref);
714                 kfree(ra);
715                 ret = -ENOMEM;
716                 goto out;
717         }
718
719         if (parent) {
720                 ref->parent = parent;
721         } else {
722                 ref->root_objectid = ref_root;
723                 ref->owner = owner;
724                 ref->offset = offset;
725         }
726         ref->num_refs = (action == BTRFS_DROP_DELAYED_REF) ? -1 : 1;
727
728         memcpy(&ra->ref, ref, sizeof(struct ref_entry));
729         /*
730          * Save the extra info from the delayed ref in the ref action to make it
731          * easier to figure out what is happening.  The real ref's we add to the
732          * ref tree need to reflect what we save on disk so it matches any
733          * on-disk refs we pre-loaded.
734          */
735         ra->ref.owner = owner;
736         ra->ref.offset = offset;
737         ra->ref.root_objectid = ref_root;
738         __save_stack_trace(ra);
739
740         INIT_LIST_HEAD(&ra->list);
741         ra->action = action;
742         ra->root = generic_ref->real_root;
743
744         /*
745          * This is an allocation, preallocate the block_entry in case we haven't
746          * used it before.
747          */
748         ret = -EINVAL;
749         if (action == BTRFS_ADD_DELAYED_EXTENT) {
750                 /*
751                  * For subvol_create we'll just pass in whatever the parent root
752                  * is and the new root objectid, so let's not treat the passed
753                  * in root as if it really has a ref for this bytenr.
754                  */
755                 be = add_block_entry(fs_info, bytenr, num_bytes, ref_root);
756                 if (IS_ERR(be)) {
757                         kfree(ra);
758                         ret = PTR_ERR(be);
759                         goto out;
760                 }
761                 be->num_refs++;
762                 if (metadata)
763                         be->metadata = 1;
764
765                 if (be->num_refs != 1) {
766                         btrfs_err(fs_info,
767                         "re-allocated a block that still has references to it!");
768                         dump_block_entry(fs_info, be);
769                         dump_ref_action(fs_info, ra);
770                         goto out_unlock;
771                 }
772
773                 while (!list_empty(&be->actions)) {
774                         struct ref_action *tmp;
775
776                         tmp = list_first_entry(&be->actions, struct ref_action,
777                                                list);
778                         list_del(&tmp->list);
779                         kfree(tmp);
780                 }
781         } else {
782                 struct root_entry *tmp;
783
784                 if (!parent) {
785                         re = kmalloc(sizeof(struct root_entry), GFP_NOFS);
786                         if (!re) {
787                                 kfree(ref);
788                                 kfree(ra);
789                                 ret = -ENOMEM;
790                                 goto out;
791                         }
792                         /*
793                          * This is the root that is modifying us, so it's the
794                          * one we want to lookup below when we modify the
795                          * re->num_refs.
796                          */
797                         ref_root = generic_ref->real_root;
798                         re->root_objectid = generic_ref->real_root;
799                         re->num_refs = 0;
800                 }
801
802                 spin_lock(&fs_info->ref_verify_lock);
803                 be = lookup_block_entry(&fs_info->block_tree, bytenr);
804                 if (!be) {
805                         btrfs_err(fs_info,
806 "trying to do action %d to bytenr %llu num_bytes %llu but there is no existing entry!",
807                                   action, (unsigned long long)bytenr,
808                                   (unsigned long long)num_bytes);
809                         dump_ref_action(fs_info, ra);
810                         kfree(ref);
811                         kfree(ra);
812                         goto out_unlock;
813                 }
814
815                 if (!parent) {
816                         tmp = insert_root_entry(&be->roots, re);
817                         if (tmp) {
818                                 kfree(re);
819                                 re = tmp;
820                         }
821                 }
822         }
823
824         exist = insert_ref_entry(&be->refs, ref);
825         if (exist) {
826                 if (action == BTRFS_DROP_DELAYED_REF) {
827                         if (exist->num_refs == 0) {
828                                 btrfs_err(fs_info,
829 "dropping a ref for a existing root that doesn't have a ref on the block");
830                                 dump_block_entry(fs_info, be);
831                                 dump_ref_action(fs_info, ra);
832                                 kfree(ra);
833                                 goto out_unlock;
834                         }
835                         exist->num_refs--;
836                         if (exist->num_refs == 0) {
837                                 rb_erase(&exist->node, &be->refs);
838                                 kfree(exist);
839                         }
840                 } else if (!be->metadata) {
841                         exist->num_refs++;
842                 } else {
843                         btrfs_err(fs_info,
844 "attempting to add another ref for an existing ref on a tree block");
845                         dump_block_entry(fs_info, be);
846                         dump_ref_action(fs_info, ra);
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(ra);
858                         goto out_unlock;
859                 }
860         }
861
862         if (!parent && !re) {
863                 re = lookup_root_entry(&be->roots, ref_root);
864                 if (!re) {
865                         /*
866                          * This shouldn't happen because we will add our re
867                          * above when we lookup the be with !parent, but just in
868                          * case catch this case so we don't panic because I
869                          * didn't think of some other corner case.
870                          */
871                         btrfs_err(fs_info, "failed to find root %llu for %llu",
872                                   generic_ref->real_root, be->bytenr);
873                         dump_block_entry(fs_info, be);
874                         dump_ref_action(fs_info, ra);
875                         kfree(ra);
876                         goto out_unlock;
877                 }
878         }
879         if (action == BTRFS_DROP_DELAYED_REF) {
880                 if (re)
881                         re->num_refs--;
882                 be->num_refs--;
883         } else if (action == BTRFS_ADD_DELAYED_REF) {
884                 be->num_refs++;
885                 if (re)
886                         re->num_refs++;
887         }
888         list_add_tail(&ra->list, &be->actions);
889         ret = 0;
890 out_unlock:
891         spin_unlock(&fs_info->ref_verify_lock);
892 out:
893         if (ret)
894                 btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
895         return ret;
896 }
897
898 /* Free up the ref cache */
899 void btrfs_free_ref_cache(struct btrfs_fs_info *fs_info)
900 {
901         struct block_entry *be;
902         struct rb_node *n;
903
904         if (!btrfs_test_opt(fs_info, REF_VERIFY))
905                 return;
906
907         spin_lock(&fs_info->ref_verify_lock);
908         while ((n = rb_first(&fs_info->block_tree))) {
909                 be = rb_entry(n, struct block_entry, node);
910                 rb_erase(&be->node, &fs_info->block_tree);
911                 free_block_entry(be);
912                 cond_resched_lock(&fs_info->ref_verify_lock);
913         }
914         spin_unlock(&fs_info->ref_verify_lock);
915 }
916
917 void btrfs_free_ref_tree_range(struct btrfs_fs_info *fs_info, u64 start,
918                                u64 len)
919 {
920         struct block_entry *be = NULL, *entry;
921         struct rb_node *n;
922
923         if (!btrfs_test_opt(fs_info, REF_VERIFY))
924                 return;
925
926         spin_lock(&fs_info->ref_verify_lock);
927         n = fs_info->block_tree.rb_node;
928         while (n) {
929                 entry = rb_entry(n, struct block_entry, node);
930                 if (entry->bytenr < start) {
931                         n = n->rb_right;
932                 } else if (entry->bytenr > start) {
933                         n = n->rb_left;
934                 } else {
935                         be = entry;
936                         break;
937                 }
938                 /* We want to get as close to start as possible */
939                 if (be == NULL ||
940                     (entry->bytenr < start && be->bytenr > start) ||
941                     (entry->bytenr < start && entry->bytenr > be->bytenr))
942                         be = entry;
943         }
944
945         /*
946          * Could have an empty block group, maybe have something to check for
947          * this case to verify we were actually empty?
948          */
949         if (!be) {
950                 spin_unlock(&fs_info->ref_verify_lock);
951                 return;
952         }
953
954         n = &be->node;
955         while (n) {
956                 be = rb_entry(n, struct block_entry, node);
957                 n = rb_next(n);
958                 if (be->bytenr < start && be->bytenr + be->len > start) {
959                         btrfs_err(fs_info,
960                                 "block entry overlaps a block group [%llu,%llu]!",
961                                 start, len);
962                         dump_block_entry(fs_info, be);
963                         continue;
964                 }
965                 if (be->bytenr < start)
966                         continue;
967                 if (be->bytenr >= start + len)
968                         break;
969                 if (be->bytenr + be->len > start + len) {
970                         btrfs_err(fs_info,
971                                 "block entry overlaps a block group [%llu,%llu]!",
972                                 start, len);
973                         dump_block_entry(fs_info, be);
974                 }
975                 rb_erase(&be->node, &fs_info->block_tree);
976                 free_block_entry(be);
977         }
978         spin_unlock(&fs_info->ref_verify_lock);
979 }
980
981 /* Walk down all roots and build the ref tree, meant to be called at mount */
982 int btrfs_build_ref_tree(struct btrfs_fs_info *fs_info)
983 {
984         struct btrfs_path *path;
985         struct extent_buffer *eb;
986         u64 bytenr = 0, num_bytes = 0;
987         int ret, level;
988
989         if (!btrfs_test_opt(fs_info, REF_VERIFY))
990                 return 0;
991
992         path = btrfs_alloc_path();
993         if (!path)
994                 return -ENOMEM;
995
996         eb = btrfs_read_lock_root_node(fs_info->extent_root);
997         btrfs_set_lock_blocking_read(eb);
998         level = btrfs_header_level(eb);
999         path->nodes[level] = eb;
1000         path->slots[level] = 0;
1001         path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
1002
1003         while (1) {
1004                 /*
1005                  * We have to keep track of the bytenr/num_bytes we last hit
1006                  * because we could have run out of space for an inline ref, and
1007                  * would have had to added a ref key item which may appear on a
1008                  * different leaf from the original extent item.
1009                  */
1010                 ret = walk_down_tree(fs_info->extent_root, path, level,
1011                                      &bytenr, &num_bytes);
1012                 if (ret)
1013                         break;
1014                 ret = walk_up_tree(path, &level);
1015                 if (ret < 0)
1016                         break;
1017                 if (ret > 0) {
1018                         ret = 0;
1019                         break;
1020                 }
1021         }
1022         if (ret) {
1023                 btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
1024                 btrfs_free_ref_cache(fs_info);
1025         }
1026         btrfs_free_path(path);
1027         return ret;
1028 }