repair/incore_ext.c

   1 /*
   2  * Copyright (c) 2000-2001 Silicon Graphics, Inc.  All Rights Reserved.
   3  *
   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.
   7  *
   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.
  11  *
  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.
  18  *
  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.
  22  *
  23  * Contact information: Silicon Graphics, Inc., 1600 Amphitheatre Pkwy,
  24  * Mountain View, CA  94043, or:
  25  *
  26  * http://www.sgi.com
  27  *
  28  * For further information regarding this notice, see:
  29  *
  30  * http://oss.sgi.com/projects/GenInfo/SGIGPLNoticeExplan/
  31  */
  32
  33 #include <libxfs.h>
  34 #include "avl.h"
  35 #include "globals.h"
  36 #include "incore.h"
  37 #include "agheader.h"
  38 #include "protos.h"
  39 #include "err_protos.h"
  40 #include "avl64.h"
  41 #define ALLOC_NUM_EXTS          100
  42
  43 /*
  44  * paranoia -- account for any weird padding, 64/32-bit alignment, etc.
  45  */
  46 typedef struct extent_alloc_rec  {
  47         ba_rec_t                alloc_rec;
  48         extent_tree_node_t      extents[ALLOC_NUM_EXTS];
  49 } extent_alloc_rec_t;
  50
  51 typedef struct rt_extent_alloc_rec  {
  52         ba_rec_t                alloc_rec;
  53         rt_extent_tree_node_t   extents[ALLOC_NUM_EXTS];
  54 } rt_extent_alloc_rec_t;
  55
  56 /*
  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.
  71  */
  72 typedef struct ext_flist_s  {
  73         extent_tree_node_t      *list;
  74         int                     cnt;
  75 } ext_flist_t;
  76
  77 static ext_flist_t ext_flist;
  78
  79 typedef struct rt_ext_flist_s  {
  80         rt_extent_tree_node_t   *list;
  81         int                     cnt;
  82 } rt_ext_flist_t;
  83
  84 static rt_ext_flist_t rt_ext_flist;
  85
  86 static avl64tree_desc_t *rt_ext_tree_ptr;       /* dup extent tree for rt */
  87
  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
  94                                                  * number
  95                                                  */
  96 static avltree_desc_t   **extent_bcnt_ptrs;     /*
  97                                                  * array of extent tree ptrs
  98                                                  * one per ag for free extents
  99                                                  * sorted by size
 100                                                  */
 101
 102 /*
 103  * list of allocated "blocks" for easy freeing later
 104  */
 105 static ba_rec_t         *ba_list;
 106 static ba_rec_t         *rt_ba_list;
 107
 108 /*
 109  * extent tree stuff is avl trees of duplicate extents,
 110  * sorted in order by block number.  there is one tree per ag.
 111  */
 112
 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)
 116 {
 117         int i;
 118         extent_tree_node_t *new;
 119         extent_alloc_rec_t *rec;
 120
 121         if (ext_flist.cnt == 0)  {
 122                 ASSERT(ext_flist.list == NULL);
 123
 124                 if ((rec = malloc(sizeof(extent_alloc_rec_t))) == NULL)
 125                         do_error(
 126                         _("couldn't allocate new extent descriptors.\n"));
 127
 128                 record_allocation(&rec->alloc_rec, ba_list);
 129
 130                 new = &rec->extents[0];
 131
 132                 for (i = 0; i < ALLOC_NUM_EXTS; i++)  {
 133                         new->avl_node.avl_nextino = (avlnode_t *)
 134                                                         ext_flist.list;
 135                         ext_flist.list = new;
 136                         ext_flist.cnt++;
 137                         new++;
 138                 }
 139         }
 140
 141         ASSERT(ext_flist.list != NULL);
 142
 143         new = ext_flist.list;
 144         ext_flist.list = (extent_tree_node_t *) new->avl_node.avl_nextino;
 145         ext_flist.cnt--;
 146         new->avl_node.avl_nextino = NULL;
 147
 148         /* initialize node */
 149
 150         new->ex_startblock = new_startblock;
 151         new->ex_blockcount = new_blockcount;
 152         new->ex_state = new_state;
 153         new->next = NULL;
 154
 155         return(new);
 156 }
 157
 158 void
 159 release_extent_tree_node(extent_tree_node_t *node)
 160 {
 161         node->avl_node.avl_nextino = (avlnode_t *) ext_flist.list;
 162         ext_flist.list = node;
 163         ext_flist.cnt++;
 164
 165         return;
 166 }
 167
 168 /*
 169  * routines to recycle all nodes in a tree.  it walks the tree
 170  * and puts all nodes back on the free list so the nodes can be
 171  * reused.  the duplicate and bno/bcnt extent trees for each AG
 172  * are recycled after they're no longer needed to save memory
 173  */
 174 void
 175 release_extent_tree(avltree_desc_t *tree)
 176 {
 177         extent_tree_node_t      *ext;
 178         extent_tree_node_t      *tmp;
 179         extent_tree_node_t      *lext;
 180         extent_tree_node_t      *ltmp;
 181
 182         if (tree->avl_firstino == NULL)
 183                 return;
 184
 185         ext = (extent_tree_node_t *) tree->avl_firstino;
 186
 187         while (ext != NULL)  {
 188                 tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino;
 189
 190                 /*
 191                  * ext->next is guaranteed to be set only in bcnt trees
 192                  */
 193                 if (ext->next != NULL)  {
 194                         lext = ext->next;
 195                         while (lext != NULL)  {
 196                                 ltmp = lext->next;
 197                                 release_extent_tree_node(lext);
 198                                 lext = ltmp;
 199                         }
 200                 }
 201
 202                 release_extent_tree_node(ext);
 203                 ext = tmp;
 204         }
 205
 206         tree->avl_root = tree->avl_firstino = NULL;
 207
 208         return;
 209 }
 210
 211 /*
 212  * top-level (visible) routines
 213  */
 214 void
 215 release_dup_extent_tree(xfs_agnumber_t agno)
 216 {
 217         release_extent_tree(extent_tree_ptrs[agno]);
 218
 219         return;
 220 }
 221
 222 void
 223 release_agbno_extent_tree(xfs_agnumber_t agno)
 224 {
 225         release_extent_tree(extent_bno_ptrs[agno]);
 226
 227         return;
 228 }
 229
 230 void
 231 release_agbcnt_extent_tree(xfs_agnumber_t agno)
 232 {
 233         release_extent_tree(extent_bcnt_ptrs[agno]);
 234
 235         return;
 236 }
 237
 238 /*
 239  * the next 4 routines manage the trees of free extents -- 2 trees
 240  * per AG.  The first tree is sorted by block number.  The second
 241  * tree is sorted by extent size.  This is the bno tree.
 242  */
 243 void
 244 add_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
 245                 xfs_extlen_t blockcount)
 246 {
 247         extent_tree_node_t *ext;
 248
 249         ASSERT(extent_bno_ptrs != NULL);
 250         ASSERT(extent_bno_ptrs[agno] != NULL);
 251
 252         ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE);
 253
 254         if (avl_insert(extent_bno_ptrs[agno], (avlnode_t *) ext) == NULL)  {
 255                 do_error(_("duplicate bno extent range\n"));
 256         }
 257 }
 258
 259 extent_tree_node_t *
 260 findfirst_bno_extent(xfs_agnumber_t agno)
 261 {
 262         ASSERT(extent_bno_ptrs != NULL);
 263         ASSERT(extent_bno_ptrs[agno] != NULL);
 264
 265         return((extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino);
 266 }
 267
 268 extent_tree_node_t *
 269 find_bno_extent(xfs_agnumber_t agno, xfs_agblock_t startblock)
 270 {
 271         ASSERT(extent_bno_ptrs != NULL);
 272         ASSERT(extent_bno_ptrs[agno] != NULL);
 273
 274         return((extent_tree_node_t *) avl_find(extent_bno_ptrs[agno],
 275                                                 startblock));
 276 }
 277
 278 /*
 279  * delete a node that's in the tree (pointer obtained by a find routine)
 280  */
 281 void
 282 get_bno_extent(xfs_agnumber_t agno, extent_tree_node_t *ext)
 283 {
 284         ASSERT(extent_bno_ptrs != NULL);
 285         ASSERT(extent_bno_ptrs[agno] != NULL);
 286
 287         avl_delete(extent_bno_ptrs[agno], &ext->avl_node);
 288
 289         return;
 290 }
 291
 292 /*
 293  * normalizing constant for bcnt size -> address conversion (see avl ops)
 294  * used by the AVL tree code to convert sizes and must be used when
 295  * doing an AVL search in the tree (e.g. avl_findrange(s))
 296  */
 297 #define MAXBCNT         0xFFFFFFFF
 298 #define BCNT_ADDR(cnt)  ((unsigned int) MAXBCNT - (cnt))
 299
 300 /*
 301  * the next 4 routines manage the trees of free extents -- 2 trees
 302  * per AG.  The first tree is sorted by block number.  The second
 303  * tree is sorted by extent size.  This is the bcnt tree.
 304  */
 305 void
 306 add_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
 307                 xfs_extlen_t blockcount)
 308 {
 309         extent_tree_node_t *ext, *prev, *current, *top;
 310         xfs_agblock_t           tmp_startblock;
 311         xfs_extlen_t            tmp_blockcount;
 312         extent_state_t          tmp_state;
 313
 314         ASSERT(extent_bcnt_ptrs != NULL);
 315         ASSERT(extent_bcnt_ptrs[agno] != NULL);
 316
 317         ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_FREE);
 318
 319         ASSERT(ext->next == NULL);
 320
 321 #ifdef XR_BCNT_TRACE
 322         fprintf(stderr, "adding bcnt: agno = %d, start = %u, count = %u\n",
 323                         agno, startblock, blockcount);
 324 #endif
 325         if ((current = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno],
 326                                                         blockcount)) != NULL)  {
 327                 /*
 328                  * avl tree code doesn't handle dups so insert
 329                  * onto linked list in increasing startblock order
 330                  */
 331                 top = prev = current;
 332                 while (current != NULL &&
 333                                 startblock > current->ex_startblock)  {
 334                         prev = current;
 335                         current = current->next;
 336                 }
 337
 338                 if (top == current)  {
 339                         ASSERT(top == prev);
 340                         /*
 341                          * swap the values of to-be-inserted element
 342                          * and the values of the head of the list.
 343                          * then insert as the 2nd element on the list.
 344                          *
 345                          * see the comment in get_bcnt_extent()
 346                          * as to why we have to do this.
 347                          */
 348                         tmp_startblock = top->ex_startblock;
 349                         tmp_blockcount = top->ex_blockcount;
 350                         tmp_state = top->ex_state;
 351
 352                         top->ex_startblock = ext->ex_startblock;
 353                         top->ex_blockcount = ext->ex_blockcount;
 354                         top->ex_state = ext->ex_state;
 355
 356                         ext->ex_startblock = tmp_startblock;
 357                         ext->ex_blockcount = tmp_blockcount;
 358                         ext->ex_state = tmp_state;
 359
 360                         current = top->next;
 361                         prev = top;
 362                 }
 363
 364                 prev->next = ext;
 365                 ext->next = current;
 366
 367                 return;
 368         }
 369
 370         if (avl_insert(extent_bcnt_ptrs[agno], (avlnode_t *) ext) == NULL)  {
 371                 do_error(_(":  duplicate bno extent range\n"));
 372         }
 373
 374         return;
 375 }
 376
 377 extent_tree_node_t *
 378 findfirst_bcnt_extent(xfs_agnumber_t agno)
 379 {
 380         ASSERT(extent_bcnt_ptrs != NULL);
 381         ASSERT(extent_bcnt_ptrs[agno] != NULL);
 382
 383         return((extent_tree_node_t *) extent_bcnt_ptrs[agno]->avl_firstino);
 384 }
 385
 386 extent_tree_node_t *
 387 findbiggest_bcnt_extent(xfs_agnumber_t agno)
 388 {
 389         extern avlnode_t *avl_lastino(avlnode_t *root);
 390
 391         ASSERT(extent_bcnt_ptrs != NULL);
 392         ASSERT(extent_bcnt_ptrs[agno] != NULL);
 393
 394         return((extent_tree_node_t *) avl_lastino(extent_bcnt_ptrs[agno]->avl_root));
 395 }
 396
 397 extent_tree_node_t *
 398 findnext_bcnt_extent(xfs_agnumber_t agno, extent_tree_node_t *ext)
 399 {
 400         avlnode_t *nextino;
 401
 402         if (ext->next != NULL)  {
 403                 ASSERT(ext->ex_blockcount == ext->next->ex_blockcount);
 404                 ASSERT(ext->ex_startblock < ext->next->ex_startblock);
 405                 return(ext->next);
 406         } else  {
 407                 /*
 408                  * have to look at the top of the list to get the
 409                  * correct avl_nextino pointer since that pointer
 410                  * is maintained and altered by the AVL code.
 411                  */
 412                 nextino = avl_find(extent_bcnt_ptrs[agno], ext->ex_blockcount);
 413                 ASSERT(nextino != NULL);
 414                 if (nextino->avl_nextino != NULL)  {
 415                         ASSERT(ext->ex_blockcount < ((extent_tree_node_t *)
 416                                         nextino->avl_nextino)->ex_blockcount);
 417                 }
 418                 return((extent_tree_node_t *) nextino->avl_nextino);
 419         }
 420 }
 421
 422 /*
 423  * this is meant to be called after you walk the bno tree to
 424  * determine exactly which extent you want (so you'll know the
 425  * desired value for startblock when you call this routine).
 426  */
 427 extent_tree_node_t *
 428 get_bcnt_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
 429                 xfs_extlen_t blockcount)
 430 {
 431         extent_tree_node_t      *ext, *prev, *top;
 432         xfs_agblock_t           tmp_startblock;
 433         xfs_extlen_t            tmp_blockcount;
 434         extent_state_t          tmp_state;
 435
 436         prev = NULL;
 437         ASSERT(extent_bcnt_ptrs != NULL);
 438         ASSERT(extent_bcnt_ptrs[agno] != NULL);
 439
 440         if ((ext = (extent_tree_node_t *) avl_find(extent_bcnt_ptrs[agno],
 441                                                         blockcount)) == NULL)
 442                 return(NULL);
 443
 444         top = ext;
 445
 446         if (ext->next != NULL)  {
 447                 /*
 448                  * pull it off the list
 449                  */
 450                 while (ext != NULL && startblock != ext->ex_startblock)  {
 451                         prev = ext;
 452                         ext = ext->next;
 453                 }
 454                 ASSERT(ext != NULL);
 455                 if (ext == top)  {
 456                         /*
 457                          * this node is linked into the tree so we
 458                          * swap the core values so we can delete
 459                          * the next item on the list instead of
 460                          * the head of the list.  This is because
 461                          * the rest of the tree undoubtedly has
 462                          * pointers to the piece of memory that
 463                          * is the head of the list so pulling
 464                          * the item out of the list and hence
 465                          * the avl tree would be a bad idea.
 466                          *
 467                          * (cheaper than the alternative, a tree
 468                          * delete of this node followed by a tree
 469                          * insert of the next node on the list).
 470                          */
 471                         tmp_startblock = ext->next->ex_startblock;
 472                         tmp_blockcount = ext->next->ex_blockcount;
 473                         tmp_state = ext->next->ex_state;
 474
 475                         ext->next->ex_startblock = ext->ex_startblock;
 476                         ext->next->ex_blockcount = ext->ex_blockcount;
 477                         ext->next->ex_state = ext->ex_state;
 478
 479                         ext->ex_startblock = tmp_startblock;
 480                         ext->ex_blockcount = tmp_blockcount;
 481                         ext->ex_state = tmp_state;
 482
 483                         ext = ext->next;
 484                         prev = top;
 485                 }
 486                 /*
 487                  * now, a simple list deletion
 488                  */
 489                 prev->next = ext->next;
 490                 ext->next = NULL;
 491         } else  {
 492                 /*
 493                  * no list, just one node.  simply delete
 494                  */
 495                 avl_delete(extent_bcnt_ptrs[agno], &ext->avl_node);
 496         }
 497
 498         ASSERT(ext->ex_startblock == startblock);
 499         ASSERT(ext->ex_blockcount == blockcount);
 500         return(ext);
 501 }
 502
 503 /*
 504  * the next 2 routines manage the trees of duplicate extents -- 1 tree
 505  * per AG
 506  */
 507 void
 508 add_dup_extent(xfs_agnumber_t agno, xfs_agblock_t startblock,
 509                 xfs_extlen_t blockcount)
 510 {
 511         extent_tree_node_t *first, *last, *ext, *next_ext;
 512         xfs_agblock_t new_startblock;
 513         xfs_extlen_t new_blockcount;
 514
 515         ASSERT(agno < glob_agcount);
 516
 517 #ifdef XR_DUP_TRACE
 518         fprintf(stderr, "Adding dup extent - %d/%d %d\n", agno, startblock, blockcount);
 519 #endif
 520         avl_findranges(extent_tree_ptrs[agno], startblock - 1,
 521                 startblock + blockcount + 1,
 522                 (avlnode_t **) &first, (avlnode_t **) &last);
 523         /*
 524          * find adjacent and overlapping extent blocks
 525          */
 526         if (first == NULL && last == NULL)  {
 527                 /* nothing, just make and insert new extent */
 528
 529                 ext = mk_extent_tree_nodes(startblock, blockcount, XR_E_MULT);
 530
 531                 if (avl_insert(extent_tree_ptrs[agno],
 532                                 (avlnode_t *) ext) == NULL)  {
 533                         do_error(_("duplicate extent range\n"));
 534                 }
 535
 536                 return;
 537         }
 538
 539         ASSERT(first != NULL && last != NULL);
 540
 541         /*
 542          * find the new composite range, delete old extent nodes
 543          * as we go
 544          */
 545         new_startblock = startblock;
 546         new_blockcount = blockcount;
 547
 548         for (ext = first;
 549                 ext != (extent_tree_node_t *) last->avl_node.avl_nextino;
 550                 ext = next_ext)  {
 551                 /*
 552                  * preserve the next inorder node
 553                  */
 554                 next_ext = (extent_tree_node_t *) ext->avl_node.avl_nextino;
 555                 /*
 556                  * just bail if the new extent is contained within an old one
 557                  */
 558                 if (ext->ex_startblock <= startblock &&
 559                                 ext->ex_blockcount >= blockcount)
 560                         return;
 561                 /*
 562                  * now check for overlaps and adjacent extents
 563                  */
 564                 if (ext->ex_startblock + ext->ex_blockcount >= startblock
 565                         || ext->ex_startblock <= startblock + blockcount)  {
 566
 567                         if (ext->ex_startblock < new_startblock)
 568                                 new_startblock = ext->ex_startblock;
 569
 570                         if (ext->ex_startblock + ext->ex_blockcount >
 571                                         new_startblock + new_blockcount)
 572                                 new_blockcount = ext->ex_startblock +
 573                                                         ext->ex_blockcount -
 574                                                         new_startblock;
 575
 576                         avl_delete(extent_tree_ptrs[agno], (avlnode_t *) ext);
 577                         continue;
 578                 }
 579         }
 580
 581         ext = mk_extent_tree_nodes(new_startblock, new_blockcount, XR_E_MULT);
 582
 583         if (avl_insert(extent_tree_ptrs[agno], (avlnode_t *) ext) == NULL)  {
 584                 do_error(_("duplicate extent range\n"));
 585         }
 586
 587         return;
 588 }
 589
 590 /*
 591  * returns 1 if block is a dup, 0 if not
 592  */
 593 /* ARGSUSED */
 594 int
 595 search_dup_extent(xfs_mount_t *mp, xfs_agnumber_t agno, xfs_agblock_t agbno)
 596 {
 597         ASSERT(agno < glob_agcount);
 598
 599         if (avl_findrange(extent_tree_ptrs[agno], agbno) != NULL)
 600                 return(1);
 601
 602         return(0);
 603 }
 604
 605 static __psunsigned_t
 606 avl_ext_start(avlnode_t *node)
 607 {
 608         return((__psunsigned_t)
 609                 ((extent_tree_node_t *) node)->ex_startblock);
 610 }
 611
 612 static __psunsigned_t
 613 avl_ext_end(avlnode_t *node)
 614 {
 615         return((__psunsigned_t) (
 616                 ((extent_tree_node_t *) node)->ex_startblock +
 617                 ((extent_tree_node_t *) node)->ex_blockcount));
 618 }
 619
 620 /*
 621  * convert size to an address for the AVL tree code -- the bigger the size,
 622  * the lower the address so the biggest extent will be first in the tree
 623  */
 624 static __psunsigned_t
 625 avl_ext_bcnt_start(avlnode_t *node)
 626 {
 627 /*
 628         return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *)
 629                                                 node)->ex_blockcount)));
 630 */
 631         return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount);
 632 }
 633
 634 static __psunsigned_t
 635 avl_ext_bcnt_end(avlnode_t *node)
 636 {
 637 /*
 638         return((__psunsigned_t) (BCNT_ADDR(((extent_tree_node_t *)
 639                                                 node)->ex_blockcount)));
 640 */
 641         return((__psunsigned_t) ((extent_tree_node_t *)node)->ex_blockcount);
 642 }
 643
 644 avlops_t avl_extent_bcnt_tree_ops = {
 645         avl_ext_bcnt_start,
 646         avl_ext_bcnt_end
 647 };
 648
 649 avlops_t avl_extent_tree_ops = {
 650         avl_ext_start,
 651         avl_ext_end
 652 };
 653
 654 /*
 655  * for real-time extents -- have to dup code since realtime extent
 656  * startblocks can be 64-bit values.
 657  */
 658 static rt_extent_tree_node_t *
 659 mk_rt_extent_tree_nodes(xfs_drtbno_t new_startblock,
 660         xfs_extlen_t new_blockcount, extent_state_t new_state)
 661 {
 662         int i;
 663         rt_extent_tree_node_t *new;
 664         rt_extent_alloc_rec_t *rec;
 665
 666         if (rt_ext_flist.cnt == 0)  {
 667                 ASSERT(rt_ext_flist.list == NULL);
 668
 669                 if ((rec = malloc(sizeof(rt_extent_alloc_rec_t))) == NULL)
 670                         do_error(
 671                         _("couldn't allocate new extent descriptors.\n"));
 672
 673                 record_allocation(&rec->alloc_rec, rt_ba_list);
 674
 675                 new = &rec->extents[0];
 676
 677                 for (i = 0; i < ALLOC_NUM_EXTS; i++)  {
 678                         new->avl_node.avl_nextino = (avlnode_t *)
 679                                                         rt_ext_flist.list;
 680                         rt_ext_flist.list = new;
 681                         rt_ext_flist.cnt++;
 682                         new++;
 683                 }
 684         }
 685
 686         ASSERT(rt_ext_flist.list != NULL);
 687
 688         new = rt_ext_flist.list;
 689         rt_ext_flist.list = (rt_extent_tree_node_t *) new->avl_node.avl_nextino;
 690         rt_ext_flist.cnt--;
 691         new->avl_node.avl_nextino = NULL;
 692
 693         /* initialize node */
 694
 695         new->rt_startblock = new_startblock;
 696         new->rt_blockcount = new_blockcount;
 697         new->rt_state = new_state;
 698
 699         return(new);
 700 }
 701
 702 #if 0
 703 void
 704 release_rt_extent_tree_node(rt_extent_tree_node_t *node)
 705 {
 706         node->avl_node.avl_nextino = (avlnode_t *) rt_ext_flist.list;
 707         rt_ext_flist.list = node;
 708         rt_ext_flist.cnt++;
 709
 710         return;
 711 }
 712
 713 void
 714 release_rt_extent_tree()
 715 {
 716         extent_tree_node_t      *ext;
 717         extent_tree_node_t      *tmp;
 718         extent_tree_node_t      *lext;
 719         extent_tree_node_t      *ltmp;
 720         avl64tree_desc_t        *tree;
 721
 722         tree = rt_extent_tree_ptr;
 723
 724         if (tree->avl_firstino == NULL)
 725                 return;
 726
 727         ext = (extent_tree_node_t *) tree->avl_firstino;
 728
 729         while (ext != NULL)  {
 730                 tmp = (extent_tree_node_t *) ext->avl_node.avl_nextino;
 731                 release_rt_extent_tree_node(ext);
 732                 ext = tmp;
 733         }
 734
 735         tree->avl_root = tree->avl_firstino = NULL;
 736
 737         return;
 738 }
 739 #endif
 740
 741 /*
 742  * don't need release functions for realtime tree teardown
 743  * since we only have one tree, not one per AG
 744  */
 745 /* ARGSUSED */
 746 void
 747 free_rt_dup_extent_tree(xfs_mount_t *mp)
 748 {
 749         ASSERT(mp->m_sb.sb_rblocks != 0);
 750
 751         free_allocations(rt_ba_list);
 752         free(rt_ext_tree_ptr);
 753
 754         rt_ba_list = NULL;
 755         rt_ext_tree_ptr = NULL;
 756
 757         return;
 758 }
 759
 760 /*
 761  * add a duplicate real-time extent
 762  */
 763 void
 764 add_rt_dup_extent(xfs_drtbno_t startblock, xfs_extlen_t blockcount)
 765 {
 766         rt_extent_tree_node_t *first, *last, *ext, *next_ext;
 767         xfs_drtbno_t new_startblock;
 768         xfs_extlen_t new_blockcount;
 769
 770         avl64_findranges(rt_ext_tree_ptr, startblock - 1,
 771                 startblock + blockcount + 1,
 772                 (avl64node_t **) &first, (avl64node_t **) &last);
 773         /*
 774          * find adjacent and overlapping extent blocks
 775          */
 776         if (first == NULL && last == NULL)  {
 777                 /* nothing, just make and insert new extent */
 778
 779                 ext = mk_rt_extent_tree_nodes(startblock,
 780                                 blockcount, XR_E_MULT);
 781
 782                 if (avl64_insert(rt_ext_tree_ptr,
 783                                 (avl64node_t *) ext) == NULL)  {
 784                         do_error(_("duplicate extent range\n"));
 785                 }
 786
 787                 return;
 788         }
 789
 790         ASSERT(first != NULL && last != NULL);
 791
 792         /*
 793          * find the new composite range, delete old extent nodes
 794          * as we go
 795          */
 796         new_startblock = startblock;
 797         new_blockcount = blockcount;
 798
 799         for (ext = first;
 800                 ext != (rt_extent_tree_node_t *) last->avl_node.avl_nextino;
 801                 ext = next_ext)  {
 802                 /*
 803                  * preserve the next inorder node
 804                  */
 805                 next_ext = (rt_extent_tree_node_t *) ext->avl_node.avl_nextino;
 806                 /*
 807                  * just bail if the new extent is contained within an old one
 808                  */
 809                 if (ext->rt_startblock <= startblock &&
 810                                 ext->rt_blockcount >= blockcount)
 811                         return;
 812                 /*
 813                  * now check for overlaps and adjacent extents
 814                  */
 815                 if (ext->rt_startblock + ext->rt_blockcount >= startblock
 816                         || ext->rt_startblock <= startblock + blockcount)  {
 817
 818                         if (ext->rt_startblock < new_startblock)
 819                                 new_startblock = ext->rt_startblock;
 820
 821                         if (ext->rt_startblock + ext->rt_blockcount >
 822                                         new_startblock + new_blockcount)
 823                                 new_blockcount = ext->rt_startblock +
 824                                                         ext->rt_blockcount -
 825                                                         new_startblock;
 826
 827                         avl64_delete(rt_ext_tree_ptr, (avl64node_t *) ext);
 828                         continue;
 829                 }
 830         }
 831
 832         ext = mk_rt_extent_tree_nodes(new_startblock,
 833                                 new_blockcount, XR_E_MULT);
 834
 835         if (avl64_insert(rt_ext_tree_ptr, (avl64node_t *) ext) == NULL)  {
 836                 do_error(_("duplicate extent range\n"));
 837         }
 838
 839         return;
 840 }
 841
 842 /*
 843  * returns 1 if block is a dup, 0 if not
 844  */
 845 /* ARGSUSED */
 846 int
 847 search_rt_dup_extent(xfs_mount_t *mp, xfs_drtbno_t bno)
 848 {
 849         if (avl64_findrange(rt_ext_tree_ptr, bno) != NULL)
 850                 return(1);
 851
 852         return(0);
 853 }
 854
 855 static __uint64_t
 856 avl64_rt_ext_start(avl64node_t *node)
 857 {
 858         return(((rt_extent_tree_node_t *) node)->rt_startblock);
 859 }
 860
 861 static __uint64_t
 862 avl64_ext_end(avl64node_t *node)
 863 {
 864         return(((rt_extent_tree_node_t *) node)->rt_startblock +
 865                 ((rt_extent_tree_node_t *) node)->rt_blockcount);
 866 }
 867
 868 avl64ops_t avl64_extent_tree_ops = {
 869         avl64_rt_ext_start,
 870         avl64_ext_end
 871 };
 872
 873 void
 874 incore_ext_init(xfs_mount_t *mp)
 875 {
 876         int i;
 877         xfs_agnumber_t agcount = mp->m_sb.sb_agcount;
 878
 879         ba_list = NULL;
 880         rt_ba_list = NULL;
 881
 882         if ((extent_tree_ptrs = malloc(agcount *
 883                                         sizeof(avltree_desc_t *))) == NULL)
 884                 do_error(
 885         _("couldn't malloc dup extent tree descriptor table\n"));
 886
 887         if ((extent_bno_ptrs = malloc(agcount *
 888                                         sizeof(avltree_desc_t *))) == NULL)
 889                 do_error(
 890         _("couldn't malloc free by-bno extent tree descriptor table\n"));
 891
 892         if ((extent_bcnt_ptrs = malloc(agcount *
 893                                         sizeof(avltree_desc_t *))) == NULL)
 894                 do_error(
 895         _("couldn't malloc free by-bcnt extent tree descriptor table\n"));
 896
 897         for (i = 0; i < agcount; i++)  {
 898                 if ((extent_tree_ptrs[i] =
 899                                 malloc(sizeof(avltree_desc_t))) == NULL)
 900                         do_error(
 901                         _("couldn't malloc dup extent tree descriptor\n"));
 902                 if ((extent_bno_ptrs[i] =
 903                                 malloc(sizeof(avltree_desc_t))) == NULL)
 904                         do_error(
 905                         _("couldn't malloc bno extent tree descriptor\n"));
 906                 if ((extent_bcnt_ptrs[i] =
 907                                 malloc(sizeof(avltree_desc_t))) == NULL)
 908                         do_error(
 909                         _("couldn't malloc bcnt extent tree descriptor\n"));
 910         }
 911
 912         for (i = 0; i < agcount; i++)  {
 913                 avl_init_tree(extent_tree_ptrs[i], &avl_extent_tree_ops);
 914                 avl_init_tree(extent_bno_ptrs[i], &avl_extent_tree_ops);
 915                 avl_init_tree(extent_bcnt_ptrs[i], &avl_extent_bcnt_tree_ops);
 916         }
 917
 918         if ((rt_ext_tree_ptr = malloc(sizeof(avltree_desc_t))) == NULL)
 919                 do_error(_("couldn't malloc dup rt extent tree descriptor\n"));
 920
 921         avl64_init_tree(rt_ext_tree_ptr, &avl64_extent_tree_ops);
 922
 923         ext_flist.cnt = 0;
 924         ext_flist.list = NULL;
 925
 926         return;
 927 }
 928
 929 /*
 930  * this routine actually frees all the memory used to track per-AG trees
 931  */
 932 void
 933 incore_ext_teardown(xfs_mount_t *mp)
 934 {
 935         xfs_agnumber_t i;
 936
 937         free_allocations(ba_list);
 938
 939         for (i = 0; i < mp->m_sb.sb_agcount; i++)  {
 940                 free(extent_tree_ptrs[i]);
 941                 free(extent_bno_ptrs[i]);
 942                 free(extent_bcnt_ptrs[i]);
 943         }
 944
 945         free(extent_bcnt_ptrs);
 946         free(extent_bno_ptrs);
 947         free(extent_tree_ptrs);
 948
 949         extent_bcnt_ptrs = extent_bno_ptrs = extent_tree_ptrs = NULL;
 950
 951         return;
 952 }
 953
 954 int
 955 count_extents(xfs_agnumber_t agno, avltree_desc_t *tree, int whichtree)
 956 {
 957         extent_tree_node_t *node;
 958         int i = 0;
 959
 960         node = (extent_tree_node_t *) tree->avl_firstino;
 961
 962         while (node != NULL)  {
 963                 i++;
 964                 if (whichtree)
 965                         node = findnext_bcnt_extent(agno, node);
 966                 else
 967                         node = findnext_bno_extent(node);
 968         }
 969
 970         return(i);
 971 }
 972
 973 int
 974 count_bno_extents_blocks(xfs_agnumber_t agno, uint *numblocks)
 975 {
 976         __uint64_t nblocks;
 977         extent_tree_node_t *node;
 978         int i = 0;
 979
 980         ASSERT(agno < glob_agcount);
 981
 982         nblocks = 0;
 983
 984         node = (extent_tree_node_t *) extent_bno_ptrs[agno]->avl_firstino;
 985
 986         while (node != NULL) {
 987                 nblocks += node->ex_blockcount;
 988                 i++;
 989                 node = findnext_bno_extent(node);
 990         }
 991
 992         *numblocks = nblocks;
 993         return(i);
 994 }
 995
 996 int
 997 count_bno_extents(xfs_agnumber_t agno)
 998 {
 999         ASSERT(agno < glob_agcount);
1000         return(count_extents(agno, extent_bno_ptrs[agno], 0));
1001 }
1002
1003 int
1004 count_bcnt_extents(xfs_agnumber_t agno)
1005 {
1006         ASSERT(agno < glob_agcount);
1007         return(count_extents(agno, extent_bcnt_ptrs[agno], 1));
1008 }