btrfs: replace btrfs_set_lock_blocking_rw with appropriate helpers
[sfrench/cifs-2.6.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  * @root: the root we are making this modification from.
674  * @bytenr: the bytenr we are modifying.
675  * @num_bytes: number of bytes.
676  * @parent: the parent bytenr.
677  * @ref_root: the original root owner of the bytenr.
678  * @owner: level in the case of metadata, inode in the case of data.
679  * @offset: 0 for metadata, file offset for data.
680  * @action: the action that we are doing, this is the same as the delayed ref
681  *      action.
682  *
683  * This will add an action item to the given bytenr and do sanity checks to make
684  * sure we haven't messed something up.  If we are making a new allocation and
685  * this block entry has history we will delete all previous actions as long as
686  * our sanity checks pass as they are no longer needed.
687  */
688 int btrfs_ref_tree_mod(struct btrfs_root *root, u64 bytenr, u64 num_bytes,
689                        u64 parent, u64 ref_root, u64 owner, u64 offset,
690                        int action)
691 {
692         struct btrfs_fs_info *fs_info = root->fs_info;
693         struct ref_entry *ref = NULL, *exist;
694         struct ref_action *ra = NULL;
695         struct block_entry *be = NULL;
696         struct root_entry *re = NULL;
697         int ret = 0;
698         bool metadata = owner < BTRFS_FIRST_FREE_OBJECTID;
699
700         if (!btrfs_test_opt(root->fs_info, REF_VERIFY))
701                 return 0;
702
703         ref = kzalloc(sizeof(struct ref_entry), GFP_NOFS);
704         ra = kmalloc(sizeof(struct ref_action), GFP_NOFS);
705         if (!ra || !ref) {
706                 kfree(ref);
707                 kfree(ra);
708                 ret = -ENOMEM;
709                 goto out;
710         }
711
712         if (parent) {
713                 ref->parent = parent;
714         } else {
715                 ref->root_objectid = ref_root;
716                 ref->owner = owner;
717                 ref->offset = offset;
718         }
719         ref->num_refs = (action == BTRFS_DROP_DELAYED_REF) ? -1 : 1;
720
721         memcpy(&ra->ref, ref, sizeof(struct ref_entry));
722         /*
723          * Save the extra info from the delayed ref in the ref action to make it
724          * easier to figure out what is happening.  The real ref's we add to the
725          * ref tree need to reflect what we save on disk so it matches any
726          * on-disk refs we pre-loaded.
727          */
728         ra->ref.owner = owner;
729         ra->ref.offset = offset;
730         ra->ref.root_objectid = ref_root;
731         __save_stack_trace(ra);
732
733         INIT_LIST_HEAD(&ra->list);
734         ra->action = action;
735         ra->root = root->root_key.objectid;
736
737         /*
738          * This is an allocation, preallocate the block_entry in case we haven't
739          * used it before.
740          */
741         ret = -EINVAL;
742         if (action == BTRFS_ADD_DELAYED_EXTENT) {
743                 /*
744                  * For subvol_create we'll just pass in whatever the parent root
745                  * is and the new root objectid, so let's not treat the passed
746                  * in root as if it really has a ref for this bytenr.
747                  */
748                 be = add_block_entry(root->fs_info, bytenr, num_bytes, ref_root);
749                 if (IS_ERR(be)) {
750                         kfree(ra);
751                         ret = PTR_ERR(be);
752                         goto out;
753                 }
754                 be->num_refs++;
755                 if (metadata)
756                         be->metadata = 1;
757
758                 if (be->num_refs != 1) {
759                         btrfs_err(fs_info,
760                         "re-allocated a block that still has references to it!");
761                         dump_block_entry(fs_info, be);
762                         dump_ref_action(fs_info, ra);
763                         goto out_unlock;
764                 }
765
766                 while (!list_empty(&be->actions)) {
767                         struct ref_action *tmp;
768
769                         tmp = list_first_entry(&be->actions, struct ref_action,
770                                                list);
771                         list_del(&tmp->list);
772                         kfree(tmp);
773                 }
774         } else {
775                 struct root_entry *tmp;
776
777                 if (!parent) {
778                         re = kmalloc(sizeof(struct root_entry), GFP_NOFS);
779                         if (!re) {
780                                 kfree(ref);
781                                 kfree(ra);
782                                 ret = -ENOMEM;
783                                 goto out;
784                         }
785                         /*
786                          * This is the root that is modifying us, so it's the
787                          * one we want to lookup below when we modify the
788                          * re->num_refs.
789                          */
790                         ref_root = root->root_key.objectid;
791                         re->root_objectid = root->root_key.objectid;
792                         re->num_refs = 0;
793                 }
794
795                 spin_lock(&root->fs_info->ref_verify_lock);
796                 be = lookup_block_entry(&root->fs_info->block_tree, bytenr);
797                 if (!be) {
798                         btrfs_err(fs_info,
799 "trying to do action %d to bytenr %llu num_bytes %llu but there is no existing entry!",
800                                   action, (unsigned long long)bytenr,
801                                   (unsigned long long)num_bytes);
802                         dump_ref_action(fs_info, ra);
803                         kfree(ref);
804                         kfree(ra);
805                         goto out_unlock;
806                 }
807
808                 if (!parent) {
809                         tmp = insert_root_entry(&be->roots, re);
810                         if (tmp) {
811                                 kfree(re);
812                                 re = tmp;
813                         }
814                 }
815         }
816
817         exist = insert_ref_entry(&be->refs, ref);
818         if (exist) {
819                 if (action == BTRFS_DROP_DELAYED_REF) {
820                         if (exist->num_refs == 0) {
821                                 btrfs_err(fs_info,
822 "dropping a ref for a existing root that doesn't have a ref on the block");
823                                 dump_block_entry(fs_info, be);
824                                 dump_ref_action(fs_info, ra);
825                                 kfree(ra);
826                                 goto out_unlock;
827                         }
828                         exist->num_refs--;
829                         if (exist->num_refs == 0) {
830                                 rb_erase(&exist->node, &be->refs);
831                                 kfree(exist);
832                         }
833                 } else if (!be->metadata) {
834                         exist->num_refs++;
835                 } else {
836                         btrfs_err(fs_info,
837 "attempting to add another ref for an existing ref on a tree block");
838                         dump_block_entry(fs_info, be);
839                         dump_ref_action(fs_info, ra);
840                         kfree(ra);
841                         goto out_unlock;
842                 }
843                 kfree(ref);
844         } else {
845                 if (action == BTRFS_DROP_DELAYED_REF) {
846                         btrfs_err(fs_info,
847 "dropping a ref for a root that doesn't have a ref on the block");
848                         dump_block_entry(fs_info, be);
849                         dump_ref_action(fs_info, ra);
850                         kfree(ra);
851                         goto out_unlock;
852                 }
853         }
854
855         if (!parent && !re) {
856                 re = lookup_root_entry(&be->roots, ref_root);
857                 if (!re) {
858                         /*
859                          * This shouldn't happen because we will add our re
860                          * above when we lookup the be with !parent, but just in
861                          * case catch this case so we don't panic because I
862                          * didn't think of some other corner case.
863                          */
864                         btrfs_err(fs_info, "failed to find root %llu for %llu",
865                                   root->root_key.objectid, be->bytenr);
866                         dump_block_entry(fs_info, be);
867                         dump_ref_action(fs_info, ra);
868                         kfree(ra);
869                         goto out_unlock;
870                 }
871         }
872         if (action == BTRFS_DROP_DELAYED_REF) {
873                 if (re)
874                         re->num_refs--;
875                 be->num_refs--;
876         } else if (action == BTRFS_ADD_DELAYED_REF) {
877                 be->num_refs++;
878                 if (re)
879                         re->num_refs++;
880         }
881         list_add_tail(&ra->list, &be->actions);
882         ret = 0;
883 out_unlock:
884         spin_unlock(&root->fs_info->ref_verify_lock);
885 out:
886         if (ret)
887                 btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
888         return ret;
889 }
890
891 /* Free up the ref cache */
892 void btrfs_free_ref_cache(struct btrfs_fs_info *fs_info)
893 {
894         struct block_entry *be;
895         struct rb_node *n;
896
897         if (!btrfs_test_opt(fs_info, REF_VERIFY))
898                 return;
899
900         spin_lock(&fs_info->ref_verify_lock);
901         while ((n = rb_first(&fs_info->block_tree))) {
902                 be = rb_entry(n, struct block_entry, node);
903                 rb_erase(&be->node, &fs_info->block_tree);
904                 free_block_entry(be);
905                 cond_resched_lock(&fs_info->ref_verify_lock);
906         }
907         spin_unlock(&fs_info->ref_verify_lock);
908 }
909
910 void btrfs_free_ref_tree_range(struct btrfs_fs_info *fs_info, u64 start,
911                                u64 len)
912 {
913         struct block_entry *be = NULL, *entry;
914         struct rb_node *n;
915
916         if (!btrfs_test_opt(fs_info, REF_VERIFY))
917                 return;
918
919         spin_lock(&fs_info->ref_verify_lock);
920         n = fs_info->block_tree.rb_node;
921         while (n) {
922                 entry = rb_entry(n, struct block_entry, node);
923                 if (entry->bytenr < start) {
924                         n = n->rb_right;
925                 } else if (entry->bytenr > start) {
926                         n = n->rb_left;
927                 } else {
928                         be = entry;
929                         break;
930                 }
931                 /* We want to get as close to start as possible */
932                 if (be == NULL ||
933                     (entry->bytenr < start && be->bytenr > start) ||
934                     (entry->bytenr < start && entry->bytenr > be->bytenr))
935                         be = entry;
936         }
937
938         /*
939          * Could have an empty block group, maybe have something to check for
940          * this case to verify we were actually empty?
941          */
942         if (!be) {
943                 spin_unlock(&fs_info->ref_verify_lock);
944                 return;
945         }
946
947         n = &be->node;
948         while (n) {
949                 be = rb_entry(n, struct block_entry, node);
950                 n = rb_next(n);
951                 if (be->bytenr < start && be->bytenr + be->len > start) {
952                         btrfs_err(fs_info,
953                                 "block entry overlaps a block group [%llu,%llu]!",
954                                 start, len);
955                         dump_block_entry(fs_info, be);
956                         continue;
957                 }
958                 if (be->bytenr < start)
959                         continue;
960                 if (be->bytenr >= start + len)
961                         break;
962                 if (be->bytenr + be->len > start + len) {
963                         btrfs_err(fs_info,
964                                 "block entry overlaps a block group [%llu,%llu]!",
965                                 start, len);
966                         dump_block_entry(fs_info, be);
967                 }
968                 rb_erase(&be->node, &fs_info->block_tree);
969                 free_block_entry(be);
970         }
971         spin_unlock(&fs_info->ref_verify_lock);
972 }
973
974 /* Walk down all roots and build the ref tree, meant to be called at mount */
975 int btrfs_build_ref_tree(struct btrfs_fs_info *fs_info)
976 {
977         struct btrfs_path *path;
978         struct extent_buffer *eb;
979         u64 bytenr = 0, num_bytes = 0;
980         int ret, level;
981
982         if (!btrfs_test_opt(fs_info, REF_VERIFY))
983                 return 0;
984
985         path = btrfs_alloc_path();
986         if (!path)
987                 return -ENOMEM;
988
989         eb = btrfs_read_lock_root_node(fs_info->extent_root);
990         btrfs_set_lock_blocking_read(eb);
991         level = btrfs_header_level(eb);
992         path->nodes[level] = eb;
993         path->slots[level] = 0;
994         path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
995
996         while (1) {
997                 /*
998                  * We have to keep track of the bytenr/num_bytes we last hit
999                  * because we could have run out of space for an inline ref, and
1000                  * would have had to added a ref key item which may appear on a
1001                  * different leaf from the original extent item.
1002                  */
1003                 ret = walk_down_tree(fs_info->extent_root, path, level,
1004                                      &bytenr, &num_bytes);
1005                 if (ret)
1006                         break;
1007                 ret = walk_up_tree(path, &level);
1008                 if (ret < 0)
1009                         break;
1010                 if (ret > 0) {
1011                         ret = 0;
1012                         break;
1013                 }
1014         }
1015         if (ret) {
1016                 btrfs_clear_opt(fs_info->mount_opt, REF_VERIFY);
1017                 btrfs_free_ref_cache(fs_info);
1018         }
1019         btrfs_free_path(path);
1020         return ret;
1021 }