rom/filesys/afs/bitmap.c

   1 /*
   2     Copyright © 1995-2005, The AROS Development Team. All rights reserved.
   3     $Id$
   4 */
   5
   6 #ifndef DEBUG
   7 #define DEBUG 0
   8 #endif
   9
  10 #include "os.h"
  11 #include "bitmap.h"
  12 #include "cache.h"
  13 #include "checksums.h"
  14 #include "error.h"
  15 #include "afsblocks.h"
  16 #include "baseredef.h"
  17
  18 /**********************************************
  19  Name  : countUsedBlocksInBitmap
  20  Descr.: count used blocks in a bitmap block
  21  Input : volume  -
  22          block   - bitmap block to count in
  23          maxcount- max blocks marked in a bitmap block
  24  Output: nr of used blocks
  25 ***********************************************/
  26 ULONG countUsedBlocksInBitmap
  27         (
  28                 struct AFSBase *afsbase,
  29                 struct Volume *volume,
  30                 ULONG block,
  31                 ULONG maxcount
  32         )
  33 {
  34 UWORD i=1;
  35 ULONG count=0,lg,bits;
  36 struct BlockCache *blockbuffer;
  37
  38         if ((blockbuffer=getBlock(afsbase, volume,block))==0)
  39         {
  40                 showText(afsbase, "Couldn't read bitmap block %lu\nCount used blocks failed!",block);
  41                 return count;
  42         }
  43         if (!calcChkSum(volume->SizeBlock, blockbuffer->buffer))
  44         {
  45                 while (maxcount>=32)
  46                 {
  47                         lg=OS_BE2LONG(blockbuffer->buffer[i]);
  48                         if (!lg)
  49                         {
  50                                 count += 32;
  51                         }
  52                         else if (lg!=0xFFFFFFFF)
  53                         {
  54                                 bits=1;
  55                                 do
  56                                 {
  57                                         if (!(bits & lg))
  58                                                 count++;
  59                                         bits=bits<<1;
  60                                 } while (bits);
  61                         }
  62                         maxcount -=32;
  63                         i++;
  64                 }
  65                 /* are there some bits left ? */
  66                 if (maxcount)
  67                 {
  68                         lg=OS_BE2LONG(blockbuffer->buffer[i]);
  69                         if (!lg)
  70                         {
  71                                 count += maxcount;
  72                         }
  73                         else if (lg!=0xFFFFFFFF)
  74                         {
  75                                 bits=1;
  76                                 for (;maxcount;maxcount--)
  77                                 {
  78                                         if (!(bits & lg))
  79                                                 count++;
  80                                         bits=bits<<1;
  81                                 }
  82                         }
  83                 }
  84         }
  85         else
  86                 showError(afsbase, ERR_CHECKSUM,block);
  87         return count;
  88 }
  89
  90 /**************************************
  91  Name  : countUsedBlocks
  92  Descr.: count used blocks of a volume
  93  Input : volume  -
  94  Output: nr of used blocks of the volume
  95 ***************************************/
  96 ULONG countUsedBlocks(struct AFSBase *afsbase, struct Volume *volume) {
  97 UWORD i;
  98 ULONG blocks;
  99 ULONG maxinbitmap;
 100 ULONG curblock;
 101 ULONG count=0;
 102 struct BlockCache *blockbuffer;
 103
 104         blocks=volume->countblocks-volume->bootblocks; /* blocks to count */
 105         maxinbitmap = (volume->SizeBlock-1)*32;        /* max blocks marked in a bitmapblock */
 106         /* check bitmap blocks stored in rootblock */
 107         for (i=0;i<=24;i++)
 108         {
 109                 if (maxinbitmap>blocks)
 110                         maxinbitmap = blocks;
 111                 if (volume->bitmapblockpointers[i])
 112                 {
 113                         count +=
 114                                 countUsedBlocksInBitmap
 115                                         (afsbase, volume, volume->bitmapblockpointers[i], maxinbitmap);
 116                         blocks -= maxinbitmap;
 117                 }
 118                 if (blocks == 0)
 119                         break;
 120         }
 121         /* check extension blocks if neccessary */
 122         if (blocks != 0)
 123         {
 124                 curblock = volume->bitmapextensionblock;
 125                 while (curblock != 0)
 126                 {
 127
 128                         blockbuffer = getBlock(afsbase, volume, curblock);
 129                         if (blockbuffer == NULL)
 130                         {
 131                                 showText
 132                                         (
 133                                                 afsbase,
 134                                                 "Couldn't read bitmap extension block %lu\nCount used blocks failed!",
 135                                                 curblock
 136                                         );
 137                                 return count;
 138                         }
 139                         blockbuffer->flags |= BCF_USED;
 140                         for (i=0;i<volume->SizeBlock-1;i++)
 141                         {
 142                                 if (maxinbitmap > blocks)
 143                                         maxinbitmap = blocks;
 144                                 if (blockbuffer->buffer[i] != 0)
 145                                 {
 146                                         count +=
 147                                                 countUsedBlocksInBitmap
 148                                                         (
 149                                                                 afsbase,
 150                                                                 volume,
 151                                                                 OS_BE2LONG(blockbuffer->buffer[i]),
 152                                                                 maxinbitmap
 153                                                         );
 154                                         blocks -= maxinbitmap;
 155                                 }
 156                                 if (blocks == 0)
 157                                         break;
 158                         }
 159                         blockbuffer->flags &= ~BCF_USED;
 160                         if (blocks == 0)
 161                                 break;
 162                         curblock = OS_BE2LONG(blockbuffer->buffer[volume->SizeBlock-1]);
 163                 }
 164                 if (blocks != 0)
 165                         showError(afsbase, ERR_MISSING_BITMAP_BLOCKS);
 166         }
 167         return count;
 168 }
 169
 170 ULONG createNewBitmapBlocks(struct AFSBase *afsbase, struct Volume *volume) {
 171 struct BlockCache *bitmapblock,*extensionblock;
 172 ULONG i, blocks, maxinbitmap;
 173
 174         /* initialize a block as a bitmap block */
 175         extensionblock = getFreeCacheBlock(afsbase, volume, -1);
 176         extensionblock->flags |= BCF_USED;
 177         bitmapblock = getFreeCacheBlock(afsbase, volume, volume->rootblock+1);
 178         /* all blocks are free */
 179         for (i=1;i<volume->SizeBlock;i++)
 180                 bitmapblock->buffer[i] = 0xFFFFFFFF;
 181         bitmapblock->buffer[0] = 0;
 182         bitmapblock->buffer[0] = OS_LONG2BE(0-calcChkSum(volume->SizeBlock,bitmapblock->buffer));
 183         /* get nr of blocks to mark in bitmap blocks */
 184         blocks = volume->countblocks - volume->bootblocks;
 185         /* calc max blocks that can be marked in a single bitmap block */
 186         maxinbitmap = (volume->SizeBlock-1)*32;
 187         /* first create bitmapblocks stored in rootblock */
 188         for (i=0;i<=24;i++)
 189         {
 190                 if (maxinbitmap > blocks)
 191                         maxinbitmap = blocks;
 192                 volume->bitmapblockpointers[i] = bitmapblock->blocknum;
 193                 writeBlock(afsbase, volume, bitmapblock, -1);
 194                 bitmapblock->blocknum += 1;
 195                 blocks = blocks - maxinbitmap;
 196                 if (blocks == 0)
 197                 {
 198                         i++;
 199                         while (i<=24)
 200                                 volume->bitmapblockpointers[i++] = 0;
 201                 }
 202         }
 203         /* check extension blocks if necessary */
 204         if (blocks != 0)
 205         {
 206                 volume->bitmapextensionblock=bitmapblock->blocknum;
 207                 do
 208                 {
 209                         /* initialize extensionblock with zeros */
 210                         extensionblock->blocknum = bitmapblock->blocknum;
 211                         for (i=0;i<volume->SizeBlock;i++)
 212                                 extensionblock->buffer[i] = 0;
 213                         /* fill extensionblock and write bitmapblocks */
 214                         for (i=0;i<volume->SizeBlock-1;i++)
 215                         {
 216                                 if (maxinbitmap > blocks)
 217                                         maxinbitmap = blocks;
 218                                 bitmapblock->blocknum += 1;
 219                                 extensionblock->buffer[i] = OS_LONG2BE(bitmapblock->blocknum);
 220                                 writeBlock(afsbase, volume, bitmapblock, -1);
 221                                 blocks = blocks-maxinbitmap;
 222                                 if (blocks == 0)
 223                                         break;
 224                         }
 225                         if (blocks != 0)        /*write another extensionblock ? */
 226                         {
 227                                 /* fill next extension */
 228                                 extensionblock->buffer[volume->SizeBlock-1]=OS_LONG2BE(bitmapblock->blocknum+1);
 229                         }
 230                         writeBlock(afsbase, volume, extensionblock, -1);
 231                         bitmapblock->blocknum += 1;
 232                 } while (blocks != 0);
 233         }
 234         else
 235                 volume->bitmapextensionblock = 0;
 236         extensionblock->flags &= ~BCF_USED;
 237         return DOSTRUE;
 238 }
 239
 240 LONG setBitmapFlag(struct AFSBase *afsbase, struct Volume *volume, LONG flag) {
 241 struct BlockCache *blockbuffer;
 242
 243         D(bug("[afs] setBitmapFlag()\n"));
 244         blockbuffer = getBlock(afsbase, volume, volume->rootblock);
 245         if (blockbuffer == NULL)
 246                 return DOSFALSE;
 247         blockbuffer->buffer[BLK_BITMAP_VALID_FLAG(volume)] = flag;
 248         if ((blockbuffer->flags & BCF_WRITE) == 0)
 249         {
 250                 writeBlock(afsbase, volume, blockbuffer, BLK_CHECKSUM);
 251                 blockbuffer->flags |= BCF_WRITE;
 252         }
 253         else
 254                 writeBlockDeferred(afsbase, volume, blockbuffer, BLK_CHECKSUM);
 255         return DOSTRUE;
 256 }
 257
 258 LONG invalidBitmap(struct AFSBase *afsbase, struct Volume *volume) {
 259
 260         volume->lastextensionblock = 0;
 261         volume->lastposition = 0;
 262         volume->bstartblock = volume->bootblocks;       /* reserved */
 263         volume->bitmapblock = getBlock(afsbase, volume, volume->bitmapblockpointers[volume->lastposition]);
 264         if (volume->bitmapblock != NULL)
 265         {
 266                 volume->bitmapblock->flags |= BCF_USED;
 267                 if (setBitmapFlag(afsbase, volume, 0))
 268                 {
 269                         return DOSTRUE;
 270                 }
 271                 volume->bitmapblock->flags &= ~BCF_USED;
 272         }
 273         return DOSFALSE;
 274 }
 275
 276 LONG validBitmap(struct AFSBase *afsbase, struct Volume *volume) {
 277
 278         if (volume->bitmapblock->flags & BCF_WRITE)
 279         {
 280                 writeBlockDeferred(afsbase, volume, volume->bitmapblock, 0);
 281         }
 282         volume->bitmapblock->flags &= ~BCF_USED;
 283         setBitmapFlag(afsbase, volume, -1);
 284         return DOSTRUE;
 285 }
 286
 287 /*************************************************
 288  Name  : gotoBitmapBlock
 289  Descr.: go to the bitmap block where a block is marked
 290  Input : volume - which volume
 291          block  - the block we want to get infos about
 292          longnr - returns the n-th long block is associated to
 293          bitnr  - returns the bitnr block is associated to
 294  Note  : bitmapblock is changed (should be initialized first!)
 295 **************************************************/
 296 LONG gotoBitmapBlock
 297         (
 298                 struct AFSBase *afsbase,
 299                 struct Volume *volume,
 300                 ULONG block,
 301                 ULONG *longnr,
 302                 ULONG *bitnr
 303         )
 304 {
 305 struct BlockCache *extensionblock;
 306 ULONG bblock,togo,maxinbitmap;
 307
 308         block -= volume->bootblocks;  /* reserved blocks are not marked */
 309         maxinbitmap = (volume->SizeBlock-1)*32; /* max blocks marked in a bitmapblock */
 310         *bitnr = block % maxinbitmap; /* in the bblock-th block we have to mark the bit-th bit */
 311         *longnr = *bitnr/32+1;        /* int the longnr-th LONG is "block" marked (+1 because [0]=BLK_CHECKSUM) */
 312         *bitnr = *bitnr % 32;         /* in the bit-th bit of LONG "longnr" "block" is marked */
 313         /* load new block ? */
 314         if (
 315                         (block<volume->bstartblock) ||
 316                         (block>=(volume->bstartblock+maxinbitmap))
 317                 )
 318         {
 319                 bblock = block/maxinbitmap; /* in the bblock-th bitmap block is "block" marked */
 320                 if (volume->bitmapblock->flags & BCF_WRITE)
 321                 {
 322                         writeBlockDeferred(afsbase, volume, volume->bitmapblock, 0);
 323                 }
 324                 volume->bitmapblock->flags &= ~BCF_USED;
 325                 /* load new block */
 326                 if (bblock<=24)
 327                 {
 328                         volume->bitmapblock = getBlock(afsbase, volume, volume->bitmapblockpointers[bblock]);
 329                 }
 330                 else
 331                 {
 332                         volume->lastextensionblock = volume->bitmapextensionblock;
 333 //kprintf("get block from extension %lu\n", volume->lastextensionblock);
 334                         /* 25 entries in rootblock already processed */
 335                         volume->lastposition = bblock-25;
 336                         /* do we have to go to another extensionblock ? */
 337                         togo = volume->lastposition / (volume->SizeBlock-1);
 338 //kprintf("togo=%lu\n", togo);
 339                         volume->lastposition %= volume->SizeBlock-1;
 340 //kprintf("lp=%lu\n", volume->lastposition);
 341                         extensionblock=getBlock(afsbase, volume, volume->lastextensionblock);
 342                         if (extensionblock == NULL)
 343                         {
 344                                 showText(afsbase, "Could not read bitmap extionsion block %lu!", volume->lastextensionblock);
 345                                 return FALSE;
 346                         }
 347 //if (volume->lastposition == 5)
 348 //{
 349 //      kprintf("00: %08lx %08lx %08lx %08lx\n", extensionblock->buffer[0], extensionblock->buffer[1], extensionblock->buffer[2], extensionblock->buffer[3]);
 350 //      kprintf("10: %08lx %08lx %08lx %08lx\n", extensionblock->buffer[4], extensionblock->buffer[5], extensionblock->buffer[6], extensionblock->buffer[7]);
 351 //}
 352                         while (togo != 0)
 353                         {
 354                                 extensionblock =
 355                                         getBlock
 356                                                 (
 357                                                         afsbase,
 358                                                         volume,
 359                                                         OS_BE2LONG(extensionblock->buffer[volume->SizeBlock-1])
 360                                                 );
 361                                 if (extensionblock == NULL)
 362                                 {
 363                                         showText(afsbase, "Could not read bitmap extension block %lu!", OS_BE2LONG(extensionblock->buffer[volume->SizeBlock-1]));
 364                                         return FALSE;
 365                                 }
 366                                 volume->lastextensionblock = extensionblock->blocknum;
 367                                 togo--;
 368                         }
 369                         volume->bitmapblock =
 370                                 getBlock
 371                                         (
 372                                                 afsbase,
 373                                                 volume,
 374                                                 OS_BE2LONG(extensionblock->buffer[volume->lastposition])
 375                                         );
 376                 }
 377                 volume->bstartblock = bblock*maxinbitmap;
 378                 if (volume->bitmapblock == NULL)
 379                 {
 380                         showText(afsbase, "Could not read bitmap block!");
 381                         return FALSE;
 382                 }
 383                 volume->bitmapblock->flags |= BCF_USED;
 384         }
 385         return TRUE;
 386 }
 387
 388 LONG markBlock(struct AFSBase *afsbase, struct Volume *volume, ULONG block, ULONG mode) {
 389 ULONG bitnr, longnr,null=0;
 390
 391         D(bug("[afs]    markBlock: block=%lu mode=%lu\n",block,mode));
 392         if (block>=volume->countblocks)
 393                 null = null/null;
 394         if (!gotoBitmapBlock(afsbase, volume, block, &longnr, &bitnr))
 395                 return 0;
 396         if (mode)
 397         {
 398                 /* free a block */
 399                 volume->bitmapblock->buffer[longnr] =
 400                         OS_LONG2BE(OS_BE2LONG(volume->bitmapblock->buffer[longnr]) | (1 << bitnr));
 401                 volume->usedblockscount -= 1;
 402                 if (
 403                                 (
 404                                         (volume->lastaccess<volume->rootblock) && (block>=volume->rootblock)
 405                                 ) || // 1. case
 406                                 (
 407                                         (
 408                                                 ((volume->lastaccess>=volume->rootblock) && (block>=volume->rootblock)) ||      // 2.case and ...
 409                                                 ((volume->lastaccess<volume->rootblock) && (block<volume->rootblock))           // 3.case with ...
 410                                         ) &&
 411                                         (block<volume->lastaccess)
 412                                 )
 413                         )
 414                 {
 415                         volume->lastaccess = block;
 416                 }
 417         }
 418         else
 419         {
 420                 volume->bitmapblock->buffer[longnr] =
 421                         OS_LONG2BE(OS_BE2LONG(volume->bitmapblock->buffer[longnr]) & ~(1 << bitnr));
 422                 volume->usedblockscount += 1;
 423                 volume->lastaccess = block; /* all blocks before "block" are used! */
 424         }
 425         volume->bitmapblock->flags |= BCF_WRITE;
 426         return DOSTRUE;
 427 }
 428
 429 ULONG findFreeBlock
 430         (
 431                 struct AFSBase *afsbase,
 432                 struct Volume *volume,
 433                 ULONG togo,
 434                 ULONG longnr,
 435                 ULONG block
 436         )
 437 {
 438 ULONG maxinbitmap,maxblocks;
 439 ULONG bits,trash,lg;
 440
 441         maxinbitmap = (volume->SizeBlock-1)*32;  /* max blocks marked in a bitmapblock */
 442         maxblocks = maxinbitmap-((longnr-1)*32); /* blocks left to check */
 443         if (maxblocks > togo)
 444                 maxblocks = togo;
 445         for (;;)
 446         {
 447                 togo -= maxblocks;
 448                 while (maxblocks>=32)
 449                 {
 450                         /* do we have a free block ?
 451                                 if yes search within this long which block */
 452                         lg = OS_BE2LONG(volume->bitmapblock->buffer[longnr]);
 453                         if (lg != 0)
 454                         {
 455                                 bits = 1;
 456                                 do
 457                                 {
 458                                         if (bits & lg)
 459                                                 return block;
 460                                         bits = bits<<1;
 461                                         block++;
 462                                 } while (bits != 0);
 463                         }
 464                         else
 465                                 block += 32;
 466                         longnr++;
 467                         maxblocks -= 32;
 468                 }
 469                 if (maxblocks != 0)
 470                 {
 471                         lg = OS_BE2LONG(volume->bitmapblock->buffer[longnr]);
 472                         bits = 1;
 473                         for (;maxblocks;maxblocks--)
 474                         {
 475                                 if (bits & lg)
 476                                         return block;
 477                                 bits = bits<<1;
 478                                 block++;
 479                         }
 480                 }
 481                 if (togo == 0)
 482                         break;
 483                 if (!gotoBitmapBlock(afsbase, volume,block,&longnr,&trash))
 484                         return 0;
 485                 if ((longnr!=1) || (trash!=0))
 486                         showText(afsbase, "Wrong bitmapblockjump!");
 487                 maxblocks = togo<maxinbitmap ? togo : maxinbitmap;
 488                 longnr = 1;             // skip checksum
 489         }
 490         return 0;
 491 }
 492
 493 ULONG getFreeBlock(struct AFSBase *afsbase, struct Volume *volume) {
 494 ULONG block,longnr,bitnr,lg,maxbitcount;
 495
 496         D(bug("[afshandler] %s: enter\n", __FUNCTION__));
 497         /* check all blocks after rootblock */
 498         block = volume->lastaccess;
 499         /*
 500                 got exact position of last accessed block
 501                 this will update volume->bitmapblock and return
 502                 the long number and bit number that block is
 503         */
 504         if (!gotoBitmapBlock(afsbase, volume, block, &longnr, &bitnr))
 505                 return 0;
 506         if (bitnr != 0)
 507         {
 508                 maxbitcount = volume->countblocks-block;
 509                 if (maxbitcount != 0)
 510                 {
 511                         maxbitcount = ((32-bitnr)<maxbitcount) ? 32 : bitnr+maxbitcount;
 512                         lg = OS_BE2LONG(volume->bitmapblock->buffer[longnr]);
 513                         for (;bitnr<maxbitcount;bitnr++)
 514                         {
 515                                 if ((1<<bitnr) & lg)
 516                                         return block;
 517                                 block++;
 518                         }
 519                         longnr++;
 520                 }
 521                 if (block>=volume->countblocks)
 522                         block = volume->bootblocks;
 523         }
 524         if (block>=volume->rootblock)
 525         {
 526                 block =
 527                         findFreeBlock
 528                                 (
 529                                         afsbase,
 530                                         volume,
 531                                         volume->countblocks-block-1,
 532                                         longnr,
 533                                         block
 534                                 );
 535                 if (block != 0)
 536                         return block;
 537                 block = volume->bootblocks;
 538         }
 539         if (!gotoBitmapBlock(afsbase, volume, block, &longnr, &bitnr))
 540                 return 0;
 541         block = findFreeBlock(afsbase, volume, volume->rootblock-block,longnr, block);
 542         return block;
 543 }
 544
 545 ULONG allocBlock(struct AFSBase *afsbase, struct Volume *volume) {
 546 ULONG block;
 547
 548         block = getFreeBlock(afsbase, volume);
 549         if (block != 0)
 550         {
 551                 D(bug("[afs]    allocBlock: found a free block on %lu\n", block));
 552                 if (!markBlock(afsbase, volume,block,0))
 553                         block = 0;
 554         }
 555         return block;
 556 }
 557