2
* Copyright (c) 2000 Silicon Graphics, Inc. All Rights Reserved.
4
* This program is free software; you can redistribute it and/or modify it
5
* under the terms of version 2 of the GNU General Public License as
6
* published by the Free Software Foundation.
8
* This program is distributed in the hope that it would be useful, but
9
* WITHOUT ANY WARRANTY; without even the implied warranty of
10
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
12
* Further, this software is distributed without any warranty that it is
13
* free of the rightful claim of any third person regarding infringement
14
* or the like. Any license provided herein, whether implied or
15
* otherwise, applies only to this software file. Patent licenses, if
16
* any, provided herein do not apply to combinations of this program with
17
* other software, or any other product whatsoever.
19
* You should have received a copy of the GNU General Public License along
20
* with this program; if not, write the Free Software Foundation, Inc., 59
21
* Temple Place - Suite 330, Boston MA 02111-1307, USA.
23
* Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
24
* Mountain View, CA 94043, or:
28
* For further information regarding this notice, see:
30
* http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
39
#include "err_protos.h"
41
#define ALLOC_NUM_EXTS 100
44
* paranoia -- account for any weird padding, 64/32-bit alignment, etc.
46
typedef struct extent_alloc_rec {
48
extent_tree_node_t extents[ALLOC_NUM_EXTS];
51
typedef struct rt_extent_alloc_rec {
53
rt_extent_tree_node_t extents[ALLOC_NUM_EXTS];
54
} rt_extent_alloc_rec_t;
57
* note: there are 4 sets of incore things handled here:
58
* block bitmaps, extent trees, uncertain inode list,
59
* and inode tree. The tree-based code uses the AVL
60
* tree package used by the IRIX kernel VM code
61
* (sys/avl.h). The inode list code uses the same records
62
* as the inode tree code for convenience. The bitmaps
63
* and bitmap operators are mostly macros defined in incore.h.
64
* There are one of everything per AG except for extent
65
* trees. There's one duplicate extent tree, one bno and
66
* one bcnt extent tree per AG. Not all of the above exist
67
* through all phases. The duplicate extent tree gets trashed
68
* at the end of phase 4. The bno/bcnt trees don't appear until
69
* phase 5. The uncertain inode list goes away at the end of
70
* phase 3. The inode tree and bno/bnct trees go away after phase 5.
72
typedef struct ext_flist_s {
73
extent_tree_node_t *list;
77
static ext_flist_t ext_flist;
79
typedef struct rt_ext_flist_s {
80
rt_extent_tree_node_t *list;
84
static rt_ext_flist_t rt_ext_flist;
86
static avl64tree_desc_t *rt_ext_tree_ptr; /* dup extent tree for rt */
88
static avltree_desc_t **extent_tree_ptrs; /* array of extent tree ptrs */
89
/* one per ag for dups */
90
static avltree_desc_t **extent_bno_ptrs; /*
91
* array of extent tree ptrs
92
* one per ag for free extents
93
* sorted by starting block
96
static avltree_desc_t **extent_bcnt_ptrs; /*
97
* array of extent tree ptrs
98
* one per ag for free extents
103
* list of allocated "blocks" for easy freeing later
105
static ba_rec_t *ba_list;
106
static ba_rec_t *rt_ba_list;
109
* extent tree stuff is avl trees of duplicate extents,
110
* sorted in order by block number. there is one tree per ag.
113
static extent_tree_node_t *
114
mk_extent_tree_nodes(xfs_agblock_t new_startblock,
115
xfs_extlen_t new_blockcount, extent_state_t new_state)
118
extent_tree_node_t *new;
119
extent_alloc_rec_t *rec;
121
if (ext_flist.cnt == 0) {
122
ASSERT(ext_flist.list == NULL);
124
if ((rec = malloc(sizeof(extent_alloc_rec_t))) == NULL)
125
do_error("couldn't allocate new extent descriptors.\n");
127
record_allocation(&rec->alloc_rec, ba_list);
129
new = &rec->extents[0];
131
for (i = 0; i < ALLOC_NUM_EXTS; i++) {
132
new->avl_node.avl_nextino = (avlnode_t *)
134
ext_flist.list = new;
140
ASSERT(ext_flist.list != NULL);
142
new = ext_flist.list;
143
ext_flist.list = (extent_tree_node_t *) new->avl_node.avl_nextino;
145
new->avl_node.avl_nextino = NULL;
147
/* initialize node */
149
new->ex_startblock = new_startblock;
150
new->ex_blockcount = new_blockcount;
151
new->ex_state = new_state;
158
release_extent_tree_node(extent_tree_node_t *node)
160
node->avl_node.avl_nextino = (avlnode_t *) ext_flist.list;
161
ext_flist.list = node;
168
* routines to recycle all nodes in a tree. it walks the tree
169
* and puts all nodes back on the free list so the nodes can be
170
* reused. the duplicate and bno/bcnt extent trees for each AG
171
* are recycled after they're no longer needed to save memory
174
release_extent_tree(avltree_desc_t *tree)
176
extent_tree_node_t *ext;
177
extent_tree_node_t *tmp;
178
extent_tree_node_t *lext;
179
extent_tree_node_t *ltmp;
181
if (tree->avl_firstino == NULL)
184
ext = (extent_tree_node_t *) tree->avl_firstino;
186
while (ext != NULL) {
187
tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino;
190
* ext->next is guaranteed to be set only in bcnt trees
192
if (ext->next != NULL) {
194
while (lext != NULL) {
196
release_extent_tree_node(lext);
201
release_extent_tree_node(ext);
205
tree->avl_root = tree->avl_firstino = NULL;
211
* top-level (visible) routines
214
release_dup_extent_tree(xfs_agnumber_t agno)
216
release_extent_tree(extent_tree_ptrs[agno]);
222
release_agbno_extent_tree(xfs_agnumber_t agno)
224
release_extent_tree(extent_bno_ptrs[agno]);
230
release_agbcnt_extent_tree(xfs_agnumber_t agno)
232
release_extent_tree(extent_bcnt_ptrs[agno]);
238
* the next 4 routines manage the trees of free extents -- 2 trees
239
* per AG. The first tree is sorted by block number. The second
240
* tree is sorted by extent size. This is the bno tree.
243
add_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
244
xfs_extlen_t blockcount)
246
extent_tree_node_t *ext;
248
ASSERT(extent_bno_ptrs != NULL);
249
ASSERT(extent_bno_ptrs[agno] != NULL);
251
ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE);
253
if (avl_insert(extent_bno_ptrs[agno], (avlnode_t *) ext) == NULL) {
254
do_error("xfs_repair: duplicate bno extent range\n");
259
findfirst_bno_extent(xfs_agnumber_t agno)
261
ASSERT(extent_bno_ptrs != NULL);
262
ASSERT(extent_bno_ptrs[agno] != NULL);
264
return((extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino);
268
find_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock)
270
ASSERT(extent_bno_ptrs != NULL);
271
ASSERT(extent_bno_ptrs[agno] != NULL);
273
return((extent_tree_node_t *) avl_find(extent_bno_ptrs[agno],
278
* delete a node that's in the tree (pointer obtained by a find routine)
281
get_bno_extent(xfs_agnumber_t agno, extent_tree_node_t *ext)
283
ASSERT(extent_bno_ptrs != NULL);
284
ASSERT(extent_bno_ptrs[agno] != NULL);
286
avl_delete(extent_bno_ptrs[agno], &ext->avl_node);
292
* normalizing constant for bcnt size -> address conversion (see avl ops)
293
* used by the AVL tree code to convert sizes and must be used when
294
* doing an AVL search in the tree (e.g. avl_findrange(s))
296
#define MAXBCNT 0xFFFFFFFF
297
#define BCNT_ADDR(cnt) ((unsigned int) MAXBCNT - (cnt))
300
* the next 4 routines manage the trees of free extents -- 2 trees
301
* per AG. The first tree is sorted by block number. The second
302
* tree is sorted by extent size. This is the bcnt tree.
305
add_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
306
xfs_extlen_t blockcount)
308
extent_tree_node_t *ext, *prev, *current, *top;
309
xfs_agblock_t tmp_startblock;
310
xfs_extlen_t tmp_blockcount;
311
extent_state_t tmp_state;
313
ASSERT(extent_bcnt_ptrs != NULL);
314
ASSERT(extent_bcnt_ptrs[agno] != NULL);
316
ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE);
318
ASSERT(ext->next == NULL);
321
fprintf(stderr, "adding bcnt: agno = %d, start = %u, count = %u\n",
322
agno, startblock, blockcount);
324
if ((current = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno],
325
blockcount)) != NULL) {
327
* avl tree code doesn't handle dups so insert
328
* onto linked list in increasing startblock order
330
top = prev = current;
331
while (current != NULL &&
332
startblock > current->ex_startblock) {
334
current = current->next;
337
if (top == current) {
340
* swap the values of to-be-inserted element
341
* and the values of the head of the list.
342
* then insert as the 2nd element on the list.
344
* see the comment in get_bcnt_extent()
345
* as to why we have to do this.
347
tmp_startblock = top->ex_startblock;
348
tmp_blockcount = top->ex_blockcount;
349
tmp_state = top->ex_state;
351
top->ex_startblock = ext->ex_startblock;
352
top->ex_blockcount = ext->ex_blockcount;
353
top->ex_state = ext->ex_state;
355
ext->ex_startblock = tmp_startblock;
356
ext->ex_blockcount = tmp_blockcount;
357
ext->ex_state = tmp_state;
369
if (avl_insert(extent_bcnt_ptrs[agno], (avlnode_t *) ext) == NULL) {
370
do_error("xfs_repair: duplicate bno extent range\n");
377
findfirst_bcnt_extent(xfs_agnumber_t agno)
379
ASSERT(extent_bcnt_ptrs != NULL);
380
ASSERT(extent_bcnt_ptrs[agno] != NULL);
382
return((extent_tree_node_t *) extent_bcnt_ptrs[agno]->avl_firstino);
386
findbiggest_bcnt_extent(xfs_agnumber_t agno)
388
extern avlnode_t *avl_lastino(avlnode_t *root);
390
ASSERT(extent_bcnt_ptrs != NULL);
391
ASSERT(extent_bcnt_ptrs[agno] != NULL);
393
return((extent_tree_node_t *) avl_lastino(extent_bcnt_ptrs[agno]->avl_root));
397
findnext_bcnt_extent(xfs_agnumber_t agno, extent_tree_node_t *ext)
401
if (ext->next != NULL) {
402
ASSERT(ext->ex_blockcount == ext->next->ex_blockcount);
403
ASSERT(ext->ex_startblock < ext->next->ex_startblock);
407
* have to look at the top of the list to get the
408
* correct avl_nextino pointer since that pointer
409
* is maintained and altered by the AVL code.
411
nextino = avl_find(extent_bcnt_ptrs[agno], ext->ex_blockcount);
412
ASSERT(nextino != NULL);
413
if (nextino->avl_nextino != NULL) {
414
ASSERT(ext->ex_blockcount < ((extent_tree_node_t *)
415
nextino->avl_nextino)->ex_blockcount);
417
return((extent_tree_node_t *) nextino->avl_nextino);
422
* this is meant to be called after you walk the bno tree to
423
* determine exactly which extent you want (so you'll know the
424
* desired value for startblock when you call this routine).
427
get_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
428
xfs_extlen_t blockcount)
430
extent_tree_node_t *ext, *prev, *top;
431
xfs_agblock_t tmp_startblock;
432
xfs_extlen_t tmp_blockcount;
433
extent_state_t tmp_state;
436
ASSERT(extent_bcnt_ptrs != NULL);
437
ASSERT(extent_bcnt_ptrs[agno] != NULL);
439
if ((ext = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno],
440
blockcount)) == NULL)
445
if (ext->next != NULL) {
447
* pull it off the list
449
while (ext != NULL && startblock != ext->ex_startblock) {
456
* this node is linked into the tree so we
457
* swap the core values so we can delete
458
* the next item on the list instead of
459
* the head of the list. This is because
460
* the rest of the tree undoubtedly has
461
* pointers to the piece of memory that
462
* is the head of the list so pulling
463
* the item out of the list and hence
464
* the avl tree would be a bad idea.
466
* (cheaper than the alternative, a tree
467
* delete of this node followed by a tree
468
* insert of the next node on the list).
470
tmp_startblock = ext->next->ex_startblock;
471
tmp_blockcount = ext->next->ex_blockcount;
472
tmp_state = ext->next->ex_state;
474
ext->next->ex_startblock = ext->ex_startblock;
475
ext->next->ex_blockcount = ext->ex_blockcount;
476
ext->next->ex_state = ext->ex_state;
478
ext->ex_startblock = tmp_startblock;
479
ext->ex_blockcount = tmp_blockcount;
480
ext->ex_state = tmp_state;
486
* now, a simple list deletion
488
prev->next = ext->next;
492
* no list, just one node. simply delete
494
avl_delete(extent_bcnt_ptrs[agno], &ext->avl_node);
497
ASSERT(ext->ex_startblock == startblock);
498
ASSERT(ext->ex_blockcount == blockcount);
503
* the next 2 routines manage the trees of duplicate extents -- 1 tree
507
add_dup_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
508
xfs_extlen_t blockcount)
510
extent_tree_node_t *first, *last, *ext, *next_ext;
511
xfs_agblock_t new_startblock;
512
xfs_extlen_t new_blockcount;
514
ASSERT(agno < glob_agcount);
517
fprintf(stderr, "Adding dup extent - %d/%d %d\n", agno, startblock, blockcount);
519
avl_findranges(extent_tree_ptrs[agno], startblock - 1,
520
startblock + blockcount + 1,
521
(avlnode_t **) &first, (avlnode_t **) &last);
523
* find adjacent and overlapping extent blocks
525
if (first == NULL && last == NULL) {
526
/* nothing, just make and insert new extent */
528
ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_MULT);
530
if (avl_insert(extent_tree_ptrs[agno],
531
(avlnode_t *) ext) == NULL) {
532
do_error("xfs_repair: duplicate extent range\n");
538
ASSERT(first != NULL && last != NULL);
541
* find the new composite range, delete old extent nodes
544
new_startblock = startblock;
545
new_blockcount = blockcount;
548
ext != (extent_tree_node_t *) last->avl_node.avl_nextino;
551
* preserve the next inorder node
553
next_ext = (extent_tree_node_t *) ext->avl_node.avl_nextino;
555
* just bail if the new extent is contained within an old one
557
if (ext->ex_startblock <= startblock &&
558
ext->ex_blockcount >= blockcount)
561
* now check for overlaps and adjacent extents
563
if (ext->ex_startblock + ext->ex_blockcount >= startblock
564
|| ext->ex_startblock <= startblock + blockcount) {
566
if (ext->ex_startblock < new_startblock)
567
new_startblock = ext->ex_startblock;
569
if (ext->ex_startblock + ext->ex_blockcount >
570
new_startblock + new_blockcount)
571
new_blockcount = ext->ex_startblock +
575
avl_delete(extent_tree_ptrs[agno], (avlnode_t *) ext);
580
ext = mk_extent_tree_nodes(new_startblock, new_blockcount, XR_E_MULT);
582
if (avl_insert(extent_tree_ptrs[agno], (avlnode_t *) ext) == NULL) {
583
do_error("xfs_repair: duplicate extent range\n");
590
* returns 1 if block is a dup, 0 if not
594
search_dup_extent(xfs_mount_t *mp, xfs_agnumber_t agno, xfs_agblock_t agbno)
596
ASSERT(agno < glob_agcount);
598
if (avl_findrange(extent_tree_ptrs[agno], agbno) != NULL)
604
static __psunsigned_t
605
avl_ext_start(avlnode_t *node)
607
return((__psunsigned_t)
608
((extent_tree_node_t *) node)->ex_startblock);
611
static __psunsigned_t
612
avl_ext_end(avlnode_t *node)
614
return((__psunsigned_t) (
615
((extent_tree_node_t *) node)->ex_startblock +
616
((extent_tree_node_t *) node)->ex_blockcount));
620
* convert size to an address for the AVL tree code -- the bigger the size,
621
* the lower the address so the biggest extent will be first in the tree
623
static __psunsigned_t
624
avl_ext_bcnt_start(avlnode_t *node)
627
return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *)
628
node)->ex_blockcount)));
630
return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount);
633
static __psunsigned_t
634
avl_ext_bcnt_end(avlnode_t *node)
637
return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *)
638
node)->ex_blockcount)));
640
return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount);
643
avlops_t avl_extent_bcnt_tree_ops = {
648
avlops_t avl_extent_tree_ops = {
654
* for real-time extents -- have to dup code since realtime extent
655
* startblocks can be 64-bit values.
657
static rt_extent_tree_node_t *
658
mk_rt_extent_tree_nodes(xfs_drtbno_t new_startblock,
659
xfs_extlen_t new_blockcount, extent_state_t new_state)
662
rt_extent_tree_node_t *new;
663
rt_extent_alloc_rec_t *rec;
665
if (rt_ext_flist.cnt == 0) {
666
ASSERT(rt_ext_flist.list == NULL);
668
if ((rec = malloc(sizeof(rt_extent_alloc_rec_t))) == NULL)
669
do_error("couldn't allocate new extent descriptors.\n");
671
record_allocation(&rec->alloc_rec, rt_ba_list);
673
new = &rec->extents[0];
675
for (i = 0; i < ALLOC_NUM_EXTS; i++) {
676
new->avl_node.avl_nextino = (avlnode_t *)
678
rt_ext_flist.list = new;
684
ASSERT(rt_ext_flist.list != NULL);
686
new = rt_ext_flist.list;
687
rt_ext_flist.list = (rt_extent_tree_node_t *) new->avl_node.avl_nextino;
689
new->avl_node.avl_nextino = NULL;
691
/* initialize node */
693
new->rt_startblock = new_startblock;
694
new->rt_blockcount = new_blockcount;
695
new->rt_state = new_state;
702
release_rt_extent_tree_node(rt_extent_tree_node_t *node)
704
node->avl_node.avl_nextino = (avlnode_t *) rt_ext_flist.list;
705
rt_ext_flist.list = node;
712
release_rt_extent_tree()
714
extent_tree_node_t *ext;
715
extent_tree_node_t *tmp;
716
extent_tree_node_t *lext;
717
extent_tree_node_t *ltmp;
718
avl64tree_desc_t *tree;
720
tree = rt_extent_tree_ptr;
722
if (tree->avl_firstino == NULL)
725
ext = (extent_tree_node_t *) tree->avl_firstino;
727
while (ext != NULL) {
728
tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino;
729
release_rt_extent_tree_node(ext);
733
tree->avl_root = tree->avl_firstino = NULL;
740
* don't need release functions for realtime tree teardown
741
* since we only have one tree, not one per AG
745
free_rt_dup_extent_tree(xfs_mount_t *mp)
747
ASSERT(mp->m_sb.sb_rblocks != 0);
749
free_allocations(rt_ba_list);
750
free(rt_ext_tree_ptr);
753
rt_ext_tree_ptr = NULL;
759
* add a duplicate real-time extent
762
add_rt_dup_extent(xfs_drtbno_t startblock, xfs_extlen_t blockcount)
764
rt_extent_tree_node_t *first, *last, *ext, *next_ext;
765
xfs_drtbno_t new_startblock;
766
xfs_extlen_t new_blockcount;
768
avl64_findranges(rt_ext_tree_ptr, startblock - 1,
769
startblock + blockcount + 1,
770
(avl64node_t **) &first, (avl64node_t **) &last);
772
* find adjacent and overlapping extent blocks
774
if (first == NULL && last == NULL) {
775
/* nothing, just make and insert new extent */
777
ext = mk_rt_extent_tree_nodes(startblock,
778
blockcount, XR_E_MULT);
780
if (avl64_insert(rt_ext_tree_ptr,
781
(avl64node_t *) ext) == NULL) {
782
do_error("xfs_repair: duplicate extent range\n");
788
ASSERT(first != NULL && last != NULL);
791
* find the new composite range, delete old extent nodes
794
new_startblock = startblock;
795
new_blockcount = blockcount;
798
ext != (rt_extent_tree_node_t *) last->avl_node.avl_nextino;
801
* preserve the next inorder node
803
next_ext = (rt_extent_tree_node_t *) ext->avl_node.avl_nextino;
805
* just bail if the new extent is contained within an old one
807
if (ext->rt_startblock <= startblock &&
808
ext->rt_blockcount >= blockcount)
811
* now check for overlaps and adjacent extents
813
if (ext->rt_startblock + ext->rt_blockcount >= startblock
814
|| ext->rt_startblock <= startblock + blockcount) {
816
if (ext->rt_startblock < new_startblock)
817
new_startblock = ext->rt_startblock;
819
if (ext->rt_startblock + ext->rt_blockcount >
820
new_startblock + new_blockcount)
821
new_blockcount = ext->rt_startblock +
825
avl64_delete(rt_ext_tree_ptr, (avl64node_t *) ext);
830
ext = mk_rt_extent_tree_nodes(new_startblock,
831
new_blockcount, XR_E_MULT);
833
if (avl64_insert(rt_ext_tree_ptr, (avl64node_t *) ext) == NULL) {
834
do_error("xfs_repair: duplicate extent range\n");
841
* returns 1 if block is a dup, 0 if not
845
search_rt_dup_extent(xfs_mount_t *mp, xfs_drtbno_t bno)
847
if (avl64_findrange(rt_ext_tree_ptr, bno) != NULL)
854
avl64_rt_ext_start(avl64node_t *node)
856
return(((rt_extent_tree_node_t *) node)->rt_startblock);
860
avl64_ext_end(avl64node_t *node)
862
return(((rt_extent_tree_node_t *) node)->rt_startblock +
863
((rt_extent_tree_node_t *) node)->rt_blockcount);
866
avl64ops_t avl64_extent_tree_ops = {
872
incore_ext_init(xfs_mount_t *mp)
875
xfs_agnumber_t agcount = mp->m_sb.sb_agcount;
880
if ((extent_tree_ptrs = malloc(agcount *
881
sizeof(avltree_desc_t *))) == NULL)
882
do_error("couldn't malloc dup extent tree descriptor table\n");
884
if ((extent_bno_ptrs = malloc(agcount *
885
sizeof(avltree_desc_t *))) == NULL)
886
do_error("couldn't malloc free by-bno extent tree descriptor table\n");
888
if ((extent_bcnt_ptrs = malloc(agcount *
889
sizeof(avltree_desc_t *))) == NULL)
890
do_error("couldn't malloc free by-bcnt extent tree descriptor table\n");
892
for (i = 0; i < agcount; i++) {
893
if ((extent_tree_ptrs[i] =
894
malloc(sizeof(avltree_desc_t))) == NULL)
895
do_error("couldn't malloc dup extent tree descriptor\n");
896
if ((extent_bno_ptrs[i] =
897
malloc(sizeof(avltree_desc_t))) == NULL)
898
do_error("couldn't malloc bno extent tree descriptor\n");
899
if ((extent_bcnt_ptrs[i] =
900
malloc(sizeof(avltree_desc_t))) == NULL)
901
do_error("couldn't malloc bcnt extent tree descriptor\n");
904
for (i = 0; i < agcount; i++) {
905
avl_init_tree(extent_tree_ptrs[i], &avl_extent_tree_ops);
906
avl_init_tree(extent_bno_ptrs[i], &avl_extent_tree_ops);
907
avl_init_tree(extent_bcnt_ptrs[i], &avl_extent_bcnt_tree_ops);
910
if ((rt_ext_tree_ptr = malloc(sizeof(avltree_desc_t))) == NULL)
911
do_error("couldn't malloc dup rt extent tree descriptor\n");
913
avl64_init_tree(rt_ext_tree_ptr, &avl64_extent_tree_ops);
916
ext_flist.list = NULL;
922
* this routine actually frees all the memory used to track per-AG trees
925
incore_ext_teardown(xfs_mount_t *mp)
929
free_allocations(ba_list);
931
for (i = 0; i < mp->m_sb.sb_agcount; i++) {
932
free(extent_tree_ptrs[i]);
933
free(extent_bno_ptrs[i]);
934
free(extent_bcnt_ptrs[i]);
937
free(extent_bcnt_ptrs);
938
free(extent_bno_ptrs);
939
free(extent_tree_ptrs);
941
extent_bcnt_ptrs = extent_bno_ptrs = extent_tree_ptrs = NULL;
947
count_extents(xfs_agnumber_t agno, avltree_desc_t *tree, int whichtree)
949
extent_tree_node_t *node;
952
node = (extent_tree_node_t *) tree->avl_firstino;
954
while (node != NULL) {
957
node = findnext_bcnt_extent(agno, node);
959
node = findnext_bno_extent(node);
966
count_bno_extents_blocks(xfs_agnumber_t agno, uint *numblocks)
969
extent_tree_node_t *node;
972
ASSERT(agno < glob_agcount);
976
node = (extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino;
978
while (node != NULL) {
979
nblocks += node->ex_blockcount;
981
node = findnext_bno_extent(node);
984
*numblocks = nblocks;
989
count_bno_extents(xfs_agnumber_t agno)
991
ASSERT(agno < glob_agcount);
992
return(count_extents(agno, extent_bno_ptrs[agno], 0));
996
count_bcnt_extents(xfs_agnumber_t agno)
998
ASSERT(agno < glob_agcount);
999
return(count_extents(agno, extent_bcnt_ptrs[agno], 1));