rom/filesys/pfs3/fs/allocation.c

   1 /*
   2  * File:
   3  *
   4  *  allocation.c
   5  *
   6  * Description:
   7  *
   8  *  Description
   9  *
  10  * Revision History:
  11  *
  12  *  $Id$
  13  *
  14  *  $Log: allocation.c $
  15  * Revision 14.8  1999/09/11  17:05:14  Michiel
  16  * bugfix version 18.4
  17  *
  18  * Revision 14.7  1999/05/14  11:31:34  Michiel
  19  * Long filename support implemented; bugfixes
  20  *
  21  * Revision 14.6  1999/03/09  10:35:13  Michiel
  22  * 00114: reserved roving op bit resolutie
  23  *
  24  * Revision 14.5  1998/09/27  11:26:37  Michiel
  25  * bugfixes
  26  * ErrorMsg param
  27  *
  28  * Revision 14.4  1998/09/03  07:12:14  Michiel
  29  * versie 17.4
  30  * bugfixes 118, 121, 123 and superindexblocks and td64 support
  31  *
  32  * Revision 14.3  1997/03/03  22:04:04  Michiel
  33  * Release 16.21
  34  *
  35  * Revision 14.2  1995/12/21  12:02:28  Michiel
  36  * Using reserved roving from rootblock extension
  37  * FreeAllAC() killed
  38  *
  39  * Revision 14.1  1995/11/15  15:10:44  Michiel
  40  * Postponed operation implemented and bugfixed
  41  * (FreeBlocksAC, RestoreAnodeChain)
  42  *
  43  * Revision 13.4  1995/11/07  14:48:30  Michiel
  44  * atomic update stuff
  45  *
  46  * Revision 13.3  1995/10/20  10:11:52  Michiel
  47  * Anode reserved area adaptions (16.3)
  48  *
  49  * Revision 13.2  1995/10/04  17:15:52  Michiel
  50  * preallocation for extended files implemented (in
  51  * AllocateBlocksAC)
  52  *
  53  * Revision 13.1  1995/10/03  10:47:40  Michiel
  54  * merged develop tree: anodecache
  55  *
  56  * Revision 12.11  1995/10/03  09:56:57  Michiel
  57  * AllocReservedBlock --> g->dirty
  58  *
  59  * Revision 12.10  1995/08/21  18:31:24  Michiel
  60  * fixed deldir FreeBlocks problem: disk was not dirty after
  61  * full tobefreed cache
  62  *
  63  * Revision 12.9  1995/08/21  04:17:36  Michiel
  64  * fixed deldir related bug in FreeBlocks
  65  *
  66  * Revision 12.8  1995/08/04  04:12:43  Michiel
  67  * extra CUTDOWN protection
  68  *
  69  * Revision 12.7  1995/07/21  06:51:11  Michiel
  70  * Adapted FreeBlocks() to allow for the anodes to be kept (needed for deldir)
  71  *
  72  * Revision 12.6  1995/07/11  17:29:31  Michiel
  73  * ErrorMsg () calls use messages.c variables now.
  74  *
  75  * Revision 12.5  1995/02/28  18:32:06  Michiel
  76  * UWORD optimize
  77  * AllocReservedBlockSave update
  78  *
  79  * Revision 12.4  1995/02/15  16:43:39  Michiel
  80  * Release version
  81  * Using new headers (struct.h & blocks.h)
  82  *
  83  * Revision 12.3  1995/01/29  07:34:57  Michiel
  84  * Small UpdateFreeList improvement
  85  * Raw res read/write and LOCK update
  86  *
  87  * Revision 12.2  1995/01/18  04:29:34  Michiel
  88  * Bugfixes. Now ready for beta release.
  89  *
  90  * Revision 12.1  1995/01/08  15:14:15  Michiel
  91  * Compiled
  92  *
  93  * Revision 11.2  1994/12/30  08:41:20  Michiel
  94  * Fixed and completed
  95  * Compilable
  96  *
  97  * Revision 11.1  1994/12/28  09:41:29  Michiel
  98  * Now using bitmaps for allocation
  99  * also using allocation.h now
 100  *
 101  */
 102
 103 /*
 104  * General includes
 105  */
 106 #define __USE_SYSBASE
 107
 108 #include <exec/types.h>
 109 #include <exec/memory.h>
 110 #include <exec/devices.h>
 111 #include <exec/io.h>
 112 #include <dos/filehandler.h>
 113 #include <proto/dos.h>
 114 #include <proto/exec.h>
 115 #include <string.h>
 116 #include "debug.h"
 117 #include <limits.h>
 118 #include <math.h>
 119 #include "ass_protos.h"
 120
 121 /*
 122  * Own includes
 123  */
 124 #include "blocks.h"
 125 #include "struct.h"
 126 #include "allocation_protos.h"
 127 #include "update_protos.h"
 128 #include "anodes_protos.h"
 129 #include "disk_protos.h"
 130 #include "lru_protos.h"
 131 #include "volume_protos.h"
 132 #include "directory_protos.h"
 133
 134 /*
 135  * Contents
 136  */
 137 static struct cindexblock *NewBitmapIndexBlock(UWORD , globaldata * );
 138
 139 /*
 140  * Get bitmapblock seqnr
 141  */
 142
 143 /*
 144  * InitAllocation
 145  *
 146  * currentvolume has to be ok.
 147  */
 148 VOID InitAllocation (struct volumedata *volume, globaldata *g)
 149 {
 150   ULONG t;
 151   rootblock_t *rootblock = volume->rootblk;
 152
 153         if (g->harddiskmode)
 154         {
 155                 alloc_data.clean_blocksfree = rootblock->blocksfree;
 156                 alloc_data.alloc_available = rootblock->blocksfree - rootblock->alwaysfree;
 157                 alloc_data.longsperbmb = LONGS_PER_BMB;
 158
 159                 t = (volume->numblocks - (rootblock->lastreserved + 1) + 31)/32;
 160                 t = (t+LONGS_PER_BMB-1)/LONGS_PER_BMB;
 161                 alloc_data.no_bmb = t;
 162                 alloc_data.bitmapstart = rootblock->lastreserved + 1;
 163                 memset (alloc_data.tobefreed, 0, TBF_CACHE_SIZE*2*sizeof(ULONG));
 164                 alloc_data.tobefreed_index = 0;
 165                 alloc_data.tbf_resneed = 0;
 166                 alloc_data.res_bitmap = (bitmapblock_t *)(rootblock+1);     /* bitmap directly behind rootblock */
 167
 168                 if (volume->rblkextension)
 169                 {
 170                         if (!(rootblock->options & MODE_EXTROVING))
 171                         {
 172                                 rootblock->options |= MODE_EXTROVING;
 173                                 g->dirty = TRUE;
 174                                 volume->rblkextension->blk.reserved_roving *= 32;
 175                         }
 176                         alloc_data.res_roving = volume->rblkextension->blk.reserved_roving;
 177                         alloc_data.rovingbit = volume->rblkextension->blk.rovingbit;
 178                 }
 179                 else
 180                 {
 181                         alloc_data.res_roving = 0;
 182                         alloc_data.rovingbit = 0;
 183                 }
 184
 185                 alloc_data.numreserved = (rootblock->lastreserved - rootblock->firstreserved + 1)/(volume->rescluster);
 186                 alloc_data.reservedtobefreed = NULL;
 187                 alloc_data.rtbf_size = 0;
 188                 alloc_data.rtbf_index = 0;
 189                 alloc_data.res_alert = 0;
 190         }
 191         else
 192         {
 193                 ErrorMsg (AFS_ERROR_ANODE_INIT, NULL, g);
 194         }
 195 }
 196
 197
 198 /*
 199  * AllocateBlocks
 200  */
 201 BOOL AllocateBlocks (ULONG anodenr, ULONG size, globaldata *g)
 202 {
 203   struct anodechain *ac;
 204   BOOL success;
 205
 206         if (!(ac = GetAnodeChain (anodenr, g)))
 207                 return DOSFALSE;
 208
 209         success = AllocateBlocksAC (ac, size, NULL, g);
 210         DetachAnodeChain (ac, g);
 211         return success;
 212 }
 213
 214 /*
 215  * AllocateBlocksAC
 216  * Allocate blocks to end of (cached) anodechain.
 217  * If ref != NULL then online directory update enabled.
 218  * Make sure the state is valid before you call this function!
 219  * Returns success
 220  * if FAIL, then a part of the needed blocks could already have been allocated
 221  */
 222 BOOL AllocateBlocksAC (struct anodechain *achain, ULONG size,
 223         struct fileinfo *ref, globaldata *g)
 224 {
 225   ULONG nr, field, i, j, blocknr, blocksdone = 0;
 226   ULONG extra;
 227   FSIZE oldfilesize = 0;
 228   UWORD bmseqnr, bmoffset, oldlocknr;
 229   cbitmapblock_t *bitmap;
 230   struct anodechainnode *chnode;
 231   struct volumedata *vol = g->currentvolume;
 232   BOOL extend = FALSE, updateroving = TRUE;
 233
 234
 235         ENTER("AllocateBlocksAC");
 236
 237         /* Check if allocation possible */
 238         if(alloc_data.alloc_available < size)
 239                 return DOSFALSE;
 240
 241         /* check for sufficient clean freespace (freespace that doesn't overlap
 242          * with the current state on disk)
 243          */
 244         if (alloc_data.clean_blocksfree < size)
 245                 UpdateDisk (g);
 246
 247 #if VERSION23
 248         /* remember filesize in order to be able to cancel */
 249         if (ref)
 250                 oldfilesize = GetDEFileSize(ref->direntry, g);
 251 #endif
 252
 253         /* count number of fragments and decide on fileextend preallocation
 254          * get anode to expand
 255          */
 256         chnode = &achain->head;
 257         for (i=0; chnode->next; i++)
 258                 chnode = chnode->next;
 259
 260         extra = min (256, i*8);
 261         if (chnode->an.blocknr && (chnode->an.blocknr != -1))
 262         {
 263                 i = chnode->an.blocknr + chnode->an.clustersize - alloc_data.bitmapstart;
 264                 nr = i/32;
 265                 i %= 32;
 266                 j = 1<<(31-i);
 267                 bmseqnr = nr/alloc_data.longsperbmb;
 268                 bmoffset = nr%alloc_data.longsperbmb;
 269                 bitmap = GetBitmapBlock (bmseqnr, g);
 270                 field = bitmap->blk.bitmap[bmoffset];
 271
 272                 /* block directly behind file free ? */
 273                 if (field & j)
 274                 {
 275                         extend = true;
 276
 277                         /* if the position we want to allocate does not corresponds to the
 278                          * rovingpointer, the rovingpointer should not be updated
 279                          */
 280                         if (nr != g->rootblock->roving_ptr)
 281                                 updateroving = false;
 282                 }
 283         }
 284
 285
 286         /* Get bitmap to allocate from */
 287         if (!extend)
 288         {
 289                 nr = g->rootblock->roving_ptr;
 290                 bmseqnr = nr/alloc_data.longsperbmb;
 291                 bmoffset = nr%alloc_data.longsperbmb;
 292                 i = alloc_data.rovingbit;
 293                 j = 1<<(31-i);
 294         }
 295
 296         /* Allocate */
 297         while (size)
 298         {
 299                 /* scan all bitmapblocks */
 300                 bitmap = GetBitmapBlock(bmseqnr, g);
 301                 oldlocknr = bitmap->used;
 302
 303                 /* find all empty fields */
 304                 while (bmoffset < alloc_data.longsperbmb)
 305                 {
 306                         field = bitmap->blk.bitmap[bmoffset];
 307                         if (field)
 308                         {
 309                                 /* take all empty bits */
 310                                 for ( ; i<32; j>>=1, i++)
 311                                 {
 312                                         if (field & j)
 313                                         {
 314                                                 /* block is available, calc blocknr */
 315                                                 blocknr = (bmseqnr*alloc_data.longsperbmb + bmoffset)*32 + i +
 316                                                                 alloc_data.bitmapstart;
 317
 318                                                 /* check in range */
 319                                                 if (blocknr >= vol->numblocks)
 320                                                 {
 321                                                         bmoffset = alloc_data.longsperbmb;
 322                                                         continue;
 323                                                 }
 324
 325                                                 /* take block */
 326                                                 else
 327                                                 {
 328                                                         /* uninitialized anode */
 329                                                         if (chnode->an.blocknr == -1)
 330                                                         {
 331                                                                 chnode->an.blocknr = blocknr;
 332                                                                 chnode->an.clustersize = 0;
 333                                                                 chnode->an.next = 0;
 334                                                         }
 335
 336                                                         /* check blockconnect */
 337                                                         else if (!(chnode->an.blocknr + chnode->an.clustersize == blocknr))
 338                                                         {
 339                                                           ULONG anodenr;
 340
 341                                                                 LOCK(bitmap);
 342
 343                                                                 if (!(chnode->next = AllocMemP (sizeof(struct anodechainnode), g)))
 344                                                                 {
 345 #if VERSION23
 346                                                                         if (ref)
 347                                                                         {
 348                                                                                 SetDEFileSize(ref->direntry, oldfilesize, g);
 349                                                                                 MakeBlockDirty ((struct cachedblock *)ref->dirblock, g);
 350                                                                         }
 351 #endif
 352                                                                         /* undo allocation so far */
 353                                                                         FreeBlocksAC (achain, blocksdone, freeanodes, g);
 354                                                                         return DOSFALSE;
 355                                                                 }
 356
 357                                                                 anodenr = AllocAnode (chnode->an.nr, g);    /* should not go wrong! */
 358                                                                 chnode->an.next = anodenr;
 359                                                                 SaveAnode (&chnode->an, chnode->an.nr, g);
 360                                                                 chnode = chnode->next;
 361                                                                 chnode->an.nr = anodenr;
 362                                                                 chnode->an.blocknr = blocknr;
 363                                                                 chnode->an.clustersize = 0;
 364                                                                 chnode->an.next = 0;
 365                                                         }
 366
 367                                                         bitmap->blk.bitmap[bmoffset] &= ~j;     /* remove block from freelist */
 368                                                         chnode->an.clustersize++;           /* to file                  */
 369                                                         MakeBlockDirty ((struct cachedblock *)bitmap, g);
 370
 371                                                         /* update counters */
 372                                                         alloc_data.clean_blocksfree--;
 373                                                         alloc_data.alloc_available--;
 374                                                         blocksdone++;
 375
 376                                                         /* update reference */
 377                                                         if (ref)
 378                                                         {
 379                                                                 SetDEFileSize(ref->direntry, GetDEFileSize(ref->direntry, g) + BLOCKSIZE, g);
 380                                                                 if (IsUpdateNeeded(RTBF_POSTPONED_TH))
 381                                                                 {
 382                                                                         /* make state valid and update disk */
 383                                                                         MakeBlockDirty ((struct cachedblock *)ref->dirblock, g);
 384                                                                         SaveAnode (&chnode->an, chnode->an.nr, g);
 385                                                                         UpdateDisk (g);
 386
 387                                                                         /* abort if running out of reserved blocks */
 388                                                                         if (g->rootblock->reserved_free <= RESFREE_THRESHOLD)
 389                                                                         {
 390 #if VERSION23
 391                                                                                 SetDEFileSize(ref->direntry, oldfilesize, g);
 392                                                                                 MakeBlockDirty ((struct cachedblock *)ref->dirblock, g);
 393 #endif
 394                                                                                 FreeBlocksAC (achain, blocksdone, freeanodes, g);
 395                                                                                 return DOSFALSE;
 396                                                                         }
 397                                                                 }
 398                                                         }
 399
 400
 401                                                         if (!--size)
 402                                                                 goto alloc_end;
 403                                                 }
 404                                         }
 405                                 }
 406
 407                                 i = 0;
 408                                 j = 1<<31;
 409                         }
 410                         bmoffset++;
 411                 }
 412
 413                 bitmap->used = oldlocknr;
 414
 415                 /* get ready for next block */
 416                 bmseqnr = (bmseqnr+1)%(alloc_data.no_bmb);
 417                 bmoffset = 0;
 418         }
 419
 420 alloc_end:
 421
 422         /* finish by saving anode and updating roving ptr */
 423         SaveAnode (&chnode->an, chnode->an.nr, g);
 424
 425         /* add fileextension preallocation */
 426         if (updateroving)
 427         {
 428                 if (extend)
 429                 {
 430                         i += extra;
 431                         alloc_data.rovingbit = i%32;
 432                         bmoffset += i/32;
 433                         if (bmoffset > alloc_data.longsperbmb)
 434                         {
 435                                 bmoffset -= alloc_data.longsperbmb;
 436                                 bmseqnr = (bmseqnr+1)%(alloc_data.no_bmb);
 437                         }
 438                 }
 439                 else
 440                 {
 441                         alloc_data.rovingbit = i;
 442                 }
 443
 444                 g->rootblock->roving_ptr = bmseqnr*alloc_data.longsperbmb + bmoffset;
 445         }
 446
 447         EXIT ("AllocateBlocksAC");
 448         return DOSTRUE;
 449 }
 450
 451
 452 /*
 453  * Free all blocks in an anodechain? Use FreeBlocksAC(achain,ULONG_MAX,freetype,g)
 454  */
 455
 456 /*
 457  * Frees blocks allocated with AllocateBlocks. Freed blocks are added
 458  * to tobefreed list, and are not actually freed until UpdateFreeList
 459  * is called. Frees from END of anodelist.
 460  *
 461  * 'freetype' specifies if the anodes involved should be freed (freeanodes) or
 462  * not (keepanodes). In keepanodes mode the whole file (size >= filesize) should
 463  * be deleted, since otherwise the anodes cannot consistently be kept (dual
 464  * definition). In freeanodes mode the leading anode is not freed.
 465  *
 466  * VERSION23: uses tobedone fields. Because freeing blocks is idem-potent, fully
 467  * repeating an interrupted operation after reboot is ok. The blocks should not
 468  * be added to the blocksfree counter twice, however (see DoPostoned())
 469  *
 470  * -> all references that indicate the freed blocks must have been
 471  *    done (atomically).
 472  */
 473 static void RestoreAnodeChain (struct anodechain *achain, BOOL empty, struct anodechainnode *tail, globaldata *g);
 474 VOID FreeBlocksAC (struct anodechain *achain, ULONG size, enum freeblocktype freetype, globaldata *g)
 475 {
 476   struct anodechainnode *chnode, *tail;
 477   ULONG freeing;
 478   UWORD i, t = 0;
 479   BOOL empty = FALSE;
 480   struct crootblockextension *rext;
 481   ULONG blocksdone = 0;
 482
 483         ENTER("FreeBlocksAC");
 484
 485         i = alloc_data.tobefreed_index;
 486         tail = NULL;
 487
 488         /* store operation tobedone */
 489         rext = g->currentvolume->rblkextension;
 490         if (rext)
 491         {
 492                 if (freetype == keepanodes)
 493                         rext->blk.tobedone.operation_id = PP_FREEBLOCKS_KEEP;
 494                 else
 495                         rext->blk.tobedone.operation_id = PP_FREEBLOCKS_FREE;
 496
 497                 rext->blk.tobedone.argument1 = achain->head.an.nr;
 498                 rext->blk.tobedone.argument2 = size;
 499                 rext->blk.tobedone.argument3 = 0;       /* blocks done (FREEBLOCKS_KEEP) */
 500                 MakeBlockDirty ((struct cachedblock *)rext, g);
 501         }
 502
 503         /* check if tobefreedcache is sufficiently large,
 504          * otherwise updatedisk
 505          */
 506         for (chnode = &achain->head; chnode->next; t++)
 507                 chnode = chnode->next;
 508
 509         if ((i>0) && (t+i >= TBF_CACHE_SIZE-1))
 510         {
 511                 UpdateDisk (g);
 512                 i = alloc_data.tobefreed_index;
 513         }
 514
 515         if (size)
 516                 goto l1;
 517
 518         /* reverse order freeloop */
 519         while (size && !empty)
 520         {
 521                 /* Get chainnode to free from */
 522                 chnode = &achain->head;
 523                 while (chnode->next != tail)
 524                         chnode = chnode->next;
 525
 526 l1:     /* get blocks to free */
 527                 if (chnode->an.clustersize <= size)
 528                 {
 529                         freeing = chnode->an.clustersize;
 530                         chnode->an.clustersize = 0;
 531
 532                         tail = chnode;
 533                         empty = tail == &achain->head;
 534                 }
 535                 else
 536                 {
 537                         /* anode is partially freed;
 538                          * should only be possible in freeanodes mode
 539                          */
 540                         freeing = size;
 541                         chnode->an.clustersize -= size;
 542                         chnode->an.next = 0;
 543                         if (freetype == freeanodes)
 544                                 SaveAnode (&chnode->an, chnode->an.nr, g);
 545                 }
 546
 547                 /* and put them in the tobefreed list */
 548                 if (freeing)
 549                 {
 550                         alloc_data.tobefreed[i][TBF_BLOCKNR] = chnode->an.blocknr + chnode->an.clustersize;
 551                         alloc_data.tobefreed[i++][TBF_SIZE] = freeing;
 552                         alloc_data.tbf_resneed += 3 + freeing/(32*alloc_data.longsperbmb);
 553                         alloc_data.alloc_available += freeing;
 554                         size -= freeing;
 555                         blocksdone += freeing;
 556
 557                         /* free anode if it is empty, we're supposed to and it is not the head */
 558                         if (!empty && freetype == freeanodes && !chnode->an.clustersize)
 559                         {
 560                                 FreeAnode (chnode->an.nr, g);
 561                                 FreeMemP (chnode, g);
 562                         }
 563                 }
 564
 565                 /* check if intermediate update is needed
 566                  * (tobefreed cache full, low on reserved blocks etc)
 567                  */
 568                 if (i>=TBF_CACHE_SIZE || IsUpdateNeeded(RTBF_POSTPONED_TH))
 569                 {
 570                         alloc_data.tobefreed_index = i;
 571                         g->dirty = DOSTRUE;
 572                         if (rext && freetype == freeanodes)
 573                         {
 574                                 /* make anodechain consistent */
 575                                 RestoreAnodeChain (achain, empty, tail, g);
 576                                 tail = NULL;
 577
 578                                 /* postponed op: finish operation later */
 579                                 rext->blk.tobedone.argument2 = size;
 580                         }
 581                         else
 582                                 /* postponed op: repeat operation later, but don't increase blocks free twice */
 583                                 rext->blk.tobedone.argument3 = blocksdone;
 584
 585                         MakeBlockDirty ((struct cachedblock *)rext, g);
 586                         UpdateDisk (g);
 587                         i = alloc_data.tobefreed_index;
 588                 }
 589         }
 590
 591         /* restore anode chain (both cached and on disk) */
 592         if (freetype == freeanodes)
 593                 RestoreAnodeChain (achain, empty, tail, g);
 594
 595         /* cancel posponed operation */
 596         if (rext)
 597         {
 598                 rext->blk.tobedone.operation_id = 0;
 599                 rext->blk.tobedone.argument1 = 0;
 600                 rext->blk.tobedone.argument2 = 0;
 601                 rext->blk.tobedone.argument3 = 0;
 602                 MakeBlockDirty ((struct cachedblock *)rext, g);
 603         }
 604
 605         /* update tobefreed index */
 606         g->dirty = DOSTRUE;
 607         alloc_data.tobefreed_index = i;
 608
 609         EXIT ("FreeBlocksAC");
 610 }
 611
 612
 613 /* local function of FreeBlocksAC
 614  * restore anodechain (freeanode mode only)
 615  */
 616 static void RestoreAnodeChain (struct anodechain *achain, BOOL empty,
 617         struct anodechainnode *tail, globaldata *g)
 618 {
 619   struct anodechainnode *chnode;
 620
 621         if (empty)
 622         {
 623                 achain->head.next = NULL;
 624                 achain->head.an.clustersize = 0;
 625                 achain->head.an.blocknr = ~0L;
 626                 achain->head.an.next = 0;
 627                 SaveAnode (&achain->head.an, achain->head.an.nr, g);
 628         }
 629         else
 630         {
 631                 chnode = &achain->head;
 632                 while (chnode->next != tail)
 633                         chnode = chnode->next;
 634
 635                 chnode->next = NULL;
 636                 chnode->an.next = 0;
 637                 SaveAnode (&chnode->an, chnode->an.nr, g);
 638         }
 639 }
 640
 641 /*
 642  * Update bitmap
 643  */
 644 void UpdateFreeList (globaldata *g)
 645 {
 646   cbitmapblock_t *bitmap = 0;
 647   UWORD i;
 648   ULONG longnr, blocknr, bmseqnr, newbmseqnr, bmoffset, bitnr;
 649
 650         /* sort the free list */
 651         // not done right now
 652
 653         /* free all blocks in list */
 654         bmseqnr = ~0;
 655         for (i=0; i<alloc_data.tobefreed_index; i++)
 656         {
 657                 for ( blocknr = alloc_data.tobefreed[i][TBF_BLOCKNR];
 658                           blocknr < alloc_data.tobefreed[i][TBF_SIZE] + alloc_data.tobefreed[i][TBF_BLOCKNR];
 659                           blocknr++ )
 660                 {
 661                         /* now free block blocknr */
 662                         bitnr = blocknr - alloc_data.bitmapstart;
 663                         longnr = bitnr/32;
 664                         newbmseqnr = longnr/alloc_data.longsperbmb;
 665                         bmoffset = longnr%alloc_data.longsperbmb;
 666                         if(newbmseqnr != bmseqnr)
 667                         {
 668                                 bmseqnr = newbmseqnr;
 669                                 bitmap = GetBitmapBlock (bmseqnr, g);
 670                         }
 671                         bitmap->blk.bitmap[bmoffset] |= (1<<(31-(bitnr%32)));
 672                         MakeBlockDirty ((struct cachedblock *)bitmap, g);
 673                 }
 674
 675                 alloc_data.clean_blocksfree += alloc_data.tobefreed[i][TBF_SIZE];
 676         }
 677
 678         /* update global data */
 679         /* alloc_data.alloc_available should already be equal blocksfree - alwaysfree */
 680         alloc_data.tobefreed_index = 0;
 681         alloc_data.tbf_resneed = 0;
 682         g->rootblock->blocksfree = alloc_data.clean_blocksfree;
 683         g->currentvolume->rootblockchangeflag = TRUE;
 684 }
 685
 686 /*
 687  * AllocReservedBlock
 688  */
 689
 690 ULONG AllocReservedBlock (globaldata *g)
 691 {
 692   struct volumedata *vol = g->currentvolume;
 693   ULONG *bitmap = alloc_data.res_bitmap->bitmap;
 694   ULONG *free = &g->rootblock->reserved_free;
 695   ULONG blocknr;
 696   LONG i, j;
 697
 698   ENTER("AllocReservedBlock");
 699
 700   /* Check if allocation possible
 701    * (really necessary?)
 702    */
 703   if (*free == 0)
 704         return 0;
 705
 706   j = 31 - alloc_data.res_roving % 32;
 707   for (i = alloc_data.res_roving / 32; i <= (alloc_data.numreserved/32); i++, j=31)
 708   {
 709         if (bitmap[i] != 0)
 710         {
 711           ULONG field = bitmap[i];
 712           for ( ;j >= 0; j--)
 713           {
 714                 if (field & (1 << j))
 715                 {
 716                   blocknr = g->rootblock->firstreserved + (i*32+(31-j))*vol->rescluster;
 717                   if (blocknr <= g->rootblock->lastreserved)
 718                   {
 719                         bitmap[i] &= ~(1 << j);
 720                         g->currentvolume->rootblockchangeflag = TRUE;
 721                         g->dirty = TRUE;
 722                         (*free)--;
 723                         alloc_data.res_roving = 32*i + (31 - j);
 724                         DB(Trace(10,"AllocReservedBlock","allocated %ld\n", blocknr));
 725                         return blocknr;
 726                   }
 727                 }
 728           }
 729         }
 730   }
 731
 732   /* end of bitmap reached. Reset roving pointer and try again
 733   */
 734   if (alloc_data.res_roving)
 735   {
 736         alloc_data.res_roving = 0;
 737         return AllocReservedBlock (g);
 738   }
 739   else
 740         return 0;
 741
 742   EXIT("AllocReservedBlock");
 743 }
 744
 745
 746 #if 0
 747 /*
 748  * Allocates a reserved block while keeping at least
 749  * RESERVED_BUFFER reserved blocks free
 750  */
 751 ULONG AllocReservedBlockSave (globaldata *g)
 752 {
 753   ULONG free = g->rootblock->reserved_free;
 754   ULONG blocknr;
 755
 756         /* dirty blocks claim two blocks, so */
 757         if (free + g->blocks_dirty < RESERVED_BUFFER)
 758                 return NULL;
 759
 760         if (!(blocknr = AllocReservedBlock(g)))
 761         {
 762                 UpdateDisk(g);
 763                 blocknr = AllocReservedBlock(g);
 764         }
 765
 766         return blocknr;
 767 }
 768 #endif
 769
 770 /*
 771  * frees reserved block, or does nothing if blocknr = 0
 772  */
 773 VOID FreeReservedBlock (ULONG blocknr, globaldata *g)
 774 {
 775   ULONG *bitmap, t;
 776
 777         if (blocknr && blocknr <= g->rootblock->lastreserved)
 778         {
 779                 bitmap = alloc_data.res_bitmap->bitmap;
 780                 t = (blocknr - g->rootblock->firstreserved)/g->currentvolume->rescluster;
 781                 bitmap[t/32] |= (0x80000000UL >> (t%32));
 782                 g->rootblock->reserved_free++;
 783                 g->currentvolume->rootblockchangeflag = TRUE;
 784         }
 785 }
 786
 787 /* this routine is analogous GetAnodeBlock()
 788  * GetBitmapIndex is analogous GetIndexBlock()
 789  */
 790 struct cbitmapblock *GetBitmapBlock(UWORD seqnr, globaldata *g)
 791 {
 792   ULONG blocknr, temp;
 793   cbitmapblock_t *bmb;
 794   cindexblock_t *indexblock;
 795   struct volumedata *volume = g->currentvolume;
 796
 797         /* check cache */
 798         for (bmb = HeadOf(&volume->bmblks); bmb->next; bmb=bmb->next)
 799         {
 800                 if (bmb->blk.seqnr == seqnr)
 801                 {
 802                         MakeLRU (bmb);
 803                         return bmb;
 804                 }
 805         }
 806
 807         /* not in cache, put it in */
 808         /* get the indexblock */
 809         temp = divide (seqnr, andata.indexperblock);
 810         if (!(indexblock = GetBitmapIndex(temp /* & 0xffff */, g)))
 811                 return NULL;
 812
 813         /* get blocknr */
 814         if (!(blocknr = indexblock->blk.index[temp>>16]) ||
 815                 !(bmb = (cbitmapblock_t *)AllocLRU(g)))
 816                 return NULL;
 817
 818         DB(Trace(10,"GetBitmapBlock", "seqnr = %ld blocknr = %lx\n", seqnr, blocknr));
 819
 820         /* read it */
 821         if (RawRead((UBYTE*)&bmb->blk, RESCLUSTER, blocknr, g) != 0)
 822         {
 823                 FreeLRU((struct cachedblock *)bmb);
 824                 return NULL;
 825         }
 826
 827         /* check it */
 828         if (bmb->blk.id != BMBLKID)
 829         {
 830                 ULONG args[2];
 831                 args[0] = bmb->blk.id;
 832                 args[1] = blocknr;
 833                 FreeLRU ((struct cachedblock *)bmb);
 834                 ErrorMsg (AFS_ERROR_DNV_WRONG_BMID, args, g);
 835                 return NULL;
 836         }
 837
 838         /* initialize it */
 839         bmb->volume = volume;
 840         bmb->blocknr = blocknr;
 841         bmb->used = FALSE;
 842         bmb->changeflag = FALSE;
 843         MinAddHead(&volume->bmblks, bmb);
 844
 845         return bmb;
 846 }
 847
 848 cindexblock_t *GetBitmapIndex (UWORD nr, globaldata *g)
 849 {
 850   ULONG blocknr;
 851   cindexblock_t *indexblk;
 852   struct volumedata *volume = g->currentvolume;
 853
 854         /* check cache */
 855         for (indexblk = HeadOf(&volume->bmindexblks); indexblk->next; indexblk=indexblk->next)
 856         {
 857                 if (indexblk->blk.seqnr == nr)
 858                 {
 859                         MakeLRU(indexblk);
 860                         return indexblk;
 861                 }
 862         }
 863
 864         /* not in cache, put it in */
 865         if ((nr > (g->supermode ? MAXBITMAPINDEX : MAXSMALLBITMAPINDEX)) ||
 866                 !(blocknr = volume->rootblk->idx.large.bitmapindex[nr]) ||
 867                 !(indexblk = (struct cindexblock *)AllocLRU(g)) )
 868         return NULL;
 869
 870         DB(Trace(10,"GetBitmapIndex", "seqnr = %ld blocknr = %lx\n", nr, blocknr));
 871
 872         if (RawRead((UBYTE*)&indexblk->blk, RESCLUSTER, blocknr, g) != 0) {
 873                 FreeLRU((struct cachedblock *)indexblk);
 874                 return NULL;
 875         }
 876
 877         if (indexblk->blk.id == BMIBLKID)
 878         {
 879                 indexblk->volume     = volume;
 880                 indexblk->blocknr    = blocknr;
 881                 indexblk->used       = FALSE;
 882                 indexblk->changeflag = FALSE;
 883                 MinAddHead (&volume->bmindexblks, indexblk);
 884         }
 885         else
 886         {
 887                 ULONG args[5] = { indexblk->blk.id, BMIBLKID, blocknr, nr, 0 };
 888                 FreeLRU ((struct cachedblock *)indexblk);
 889                 ErrorMsg (AFS_ERROR_DNV_WRONG_INDID, args, g);
 890                 return NULL;
 891         }
 892
 893         LOCK(indexblk);
 894         return indexblk;
 895 }
 896
 897 /*
 898  * the following routines (NewBitmapBlock & NewBitmapIndexBlock are
 899  * primarily (read only) used by Format
 900  */
 901 struct cbitmapblock *NewBitmapBlock (UWORD seqnr, globaldata *g)
 902 {
 903   struct cbitmapblock *blok;
 904   struct cindexblock *indexblock;
 905   struct volumedata *volume = g->currentvolume;
 906   ULONG indexblnr, blocknr, indexoffset;
 907   ULONG *bitmap, i;
 908   UWORD oldlock;
 909
 910         /* get indexblock */
 911         indexblnr = seqnr/andata.indexperblock;
 912         indexoffset = seqnr%andata.indexperblock;
 913         if (!(indexblock = GetBitmapIndex(indexblnr, g)))
 914                 if (!(indexblock = NewBitmapIndexBlock(indexblnr, g)))
 915                         return NULL;
 916
 917         oldlock = indexblock->used;
 918         LOCK(indexblock);
 919         if (!(blok = (struct cbitmapblock *)AllocLRU(g)) ||
 920                 !(blocknr = AllocReservedBlock(g)) )
 921                 return NULL;
 922
 923         indexblock->blk.index[indexoffset] = blocknr;
 924
 925         blok->volume = volume;
 926         blok->blocknr = blocknr;
 927         blok->used = FALSE;
 928         blok->blk.id = BMBLKID;
 929         blok->blk.seqnr = seqnr;
 930         blok->changeflag = TRUE;
 931
 932         /* fill bitmap */
 933         bitmap = blok->blk.bitmap;
 934         for (i = 0; i<alloc_data.longsperbmb; i++)
 935                 *bitmap++ = ~0;
 936
 937         MinAddHead(&volume->bmblks, blok);
 938         MakeBlockDirty((struct cachedblock *)indexblock, g);
 939         indexblock->used = oldlock;             // unlock;
 940
 941         return blok;
 942 }
 943
 944 static struct cindexblock *NewBitmapIndexBlock (UWORD seqnr, globaldata *g)
 945 {
 946   struct cindexblock *blok;
 947   struct volumedata *volume = g->currentvolume;
 948
 949         if (seqnr > (g->supermode ? MAXBITMAPINDEX : MAXSMALLBITMAPINDEX) ||
 950                 !(blok = (struct cindexblock *)AllocLRU(g)))
 951                 return NULL;
 952
 953         if (!(g->rootblock->idx.large.bitmapindex[seqnr] = AllocReservedBlock (g)))
 954         {
 955                 FreeLRU((struct cachedblock *)blok);
 956                 return NULL;
 957         }
 958
 959         volume->rootblockchangeflag = TRUE;
 960
 961         blok->volume     = volume;
 962         blok->blocknr    = volume->rootblk->idx.large.bitmapindex[seqnr];
 963         blok->used       = FALSE;
 964         blok->blk.id     = BMIBLKID;
 965         blok->blk.seqnr  = seqnr;
 966         blok->changeflag = TRUE;
 967         MinAddHead(&volume->bmindexblks, blok);
 968
 969         return blok;
 970 }
 971
 972
 973 /*
 974  * End allocation.c
 975  */