rom/filesys/SFS/FS/bitmap.c

   1 #include "asmsupport.h"
   2
   3 #include <clib/macros.h>
   4 #include <dos/dos.h>
   5 #include <exec/types.h>
   6 #include <proto/exec.h>
   7
   8 #include "bitmap.h"
   9 #include "cachebuffers_protos.h"
  10 #include "debug.h"
  11 #include "objects.h"
  12 #include "transactions_protos.h"
  13 #include "req_protos.h"
  14 #include "globals.h"
  15
  16 extern LONG readcachebuffercheck(struct CacheBuffer **,ULONG,ULONG);
  17 extern void setchecksum(struct CacheBuffer *);
  18
  19 LONG getfreeblocks(ULONG *returned_freeblocks) {
  20   struct CacheBuffer *cb;
  21   LONG errorcode;
  22
  23   if((errorcode=readcachebuffercheck(&cb,globals->block_root,OBJECTCONTAINER_ID))==0) {
  24     struct fsRootInfo *ri=(struct fsRootInfo *)((UBYTE *)cb->data+globals->bytes_block-sizeof(struct fsRootInfo));
  25
  26     *returned_freeblocks=BE2L(ri->be_freeblocks);
  27   }
  28
  29   return(errorcode);
  30 }
  31
  32
  33
  34 LONG getusedblocks(ULONG *returned_usedblocks) {
  35   ULONG freeblocks;
  36   LONG errorcode;
  37
  38   if((errorcode=getfreeblocks(&freeblocks))==0) {
  39     *returned_usedblocks=globals->blocks_total-globals->blocks_reserved_start-globals->blocks_reserved_end-freeblocks;
  40   }
  41
  42   return(errorcode);
  43 }
  44
  45
  46
  47 LONG setfreeblocks(ULONG freeblocks) {
  48   struct CacheBuffer *cb;
  49   LONG errorcode;
  50
  51   if((errorcode=readcachebuffercheck(&cb,globals->block_root,OBJECTCONTAINER_ID))==0) {
  52     struct fsRootInfo *ri=(struct fsRootInfo *)((UBYTE *)cb->data+globals->bytes_block-sizeof(struct fsRootInfo));
  53
  54     preparecachebuffer(cb);
  55
  56     ri->be_freeblocks=L2BE(freeblocks);
  57
  58     errorcode=storecachebuffer(cb);
  59   }
  60
  61   return(errorcode);
  62 }
  63
  64
  65
  66 static BOOL enoughspace(ULONG blocks) {
  67   ULONG blocksfree;
  68
  69   if(getfreeblocks(&blocksfree)!=0 || blocksfree-transactionspace() < blocks+ALWAYSFREE) {
  70     return(FALSE);
  71   }
  72
  73   return(TRUE);
  74 }
  75
  76
  77 LONG availablespace(BLCK block,ULONG maxneeded);
  78
  79
  80 LONG markspace(BLCK block,ULONG blocks) {
  81   ULONG freeblocks;
  82   LONG errorcode;
  83
  84   _XDEBUG((DEBUG_BITMAP,"markspace: Marking %ld blocks from block %ld\n",blocks,block));
  85
  86   if((availablespace(block, blocks))<blocks) {
  87     req_unusual("Attempted to mark %ld blocks from block %ld,\n but some of them were already full.", blocks, block);
  88     return(-1);
  89   }
  90
  91   if((errorcode=getfreeblocks(&freeblocks))==0) {
  92     if((errorcode=setfreeblocks(freeblocks-blocks))==0) {
  93       struct CacheBuffer *cb;
  94       ULONG skipblocks=block/globals->blocks_inbitmap;
  95       ULONG longs=(globals->bytes_block-sizeof(struct fsBitmap))>>2;
  96       ULONG bitmapblock;
  97       // ULONG newrovingptr=block+blocks;
  98
  99       // blocks_useddiff+=blocks;
 100
 101       block-=skipblocks*globals->blocks_inbitmap;
 102       bitmapblock=globals->block_bitmapbase+skipblocks;
 103
 104       /* /block/ is bitoffset in the /bitmapblock/ */
 105
 106       while(blocks>0) {
 107         if((errorcode=readcachebuffercheck(&cb,bitmapblock++,BITMAP_ID))==0) {
 108           struct fsBitmap *b;
 109
 110           preparecachebuffer(cb);
 111
 112           b=cb->data;
 113
 114           blocks-=bmclr(b->bitmap,longs,block,blocks);
 115           block=0;
 116
 117           if((errorcode=storecachebuffer(cb))!=0) {
 118             return(errorcode);
 119           }
 120         }
 121         else {
 122           return(errorcode);
 123         }
 124       }
 125
 126       // block_rovingblockptr=newrovingptr;
 127       // if(block_rovingblockptr>=blocks_total) {
 128       //   block_rovingblockptr=0;
 129       // }
 130     }
 131   }
 132
 133   return(errorcode);
 134 }
 135
 136
 137
 138 LONG freespace(BLCK block,ULONG blocks) {
 139   ULONG freeblocks;
 140   LONG errorcode;
 141
 142   _XDEBUG((DEBUG_BITMAP,"freespace: Freeing %ld blocks from block %ld\n",blocks,block));
 143
 144   if((errorcode=getfreeblocks(&freeblocks))==0) {
 145     if((errorcode=setfreeblocks(freeblocks+blocks))==0) {
 146       struct CacheBuffer *cb;
 147       ULONG skipblocks=block/globals->blocks_inbitmap;
 148       ULONG longs=(globals->bytes_block-sizeof(struct fsBitmap))>>2;
 149       ULONG bitmapblock;
 150
 151       // blocks_useddiff-=blocks;
 152
 153       block-=skipblocks*globals->blocks_inbitmap;
 154       bitmapblock=globals->block_bitmapbase+skipblocks;
 155
 156       /* /block/ is bitoffset in the /bitmapblock/ */
 157
 158       while(blocks>0) {
 159         if((errorcode=readcachebuffercheck(&cb,bitmapblock++,BITMAP_ID))==0) {
 160           struct fsBitmap *b;
 161
 162           preparecachebuffer(cb);
 163
 164           b=cb->data;
 165
 166           blocks-=bmset(b->bitmap,longs,block,blocks);
 167           block=0;
 168
 169           if((errorcode=storecachebuffer(cb))!=0) {
 170             return(errorcode);
 171           }
 172         }
 173         else {
 174           return(errorcode);
 175         }
 176       }
 177     }
 178   }
 179
 180   return(errorcode);
 181 }
 182
 183
 184
 185
 186 LONG extractspace(UBYTE *dest, BLCK block, ULONG blocks) {
 187   ULONG skipblocks=block/globals->blocks_inbitmap;
 188   ULONG byteoffset=(block-(skipblocks*globals->blocks_inbitmap))>>3;
 189   ULONG bytesinbitmap=globals->blocks_inbitmap>>3;
 190   ULONG bytes=(blocks+7)>>3;
 191   ULONG bitmapblock=globals->block_bitmapbase+skipblocks;
 192
 193   if((block & 0x07)!=0 || block>=globals->blocks_total || block+blocks>globals->blocks_total) {
 194     return(ERROR_BAD_NUMBER);
 195   }
 196
 197   /* /block/ is bitoffset in the /bitmapblock/ */
 198
 199   while(bytes>0) {
 200     struct CacheBuffer *cb;
 201     LONG errorcode;
 202
 203     if((errorcode=readcachebuffercheck(&cb, bitmapblock++, BITMAP_ID))==0) {
 204       struct fsBitmap *b;
 205       ULONG bytestocopy=bytesinbitmap-byteoffset;
 206
 207       if(bytestocopy>bytes) {
 208         bytestocopy=bytes;
 209       }
 210
 211       b=cb->data;
 212
 213       CopyMem((UBYTE *)b->bitmap + byteoffset, dest, bytestocopy);
 214
 215       bytes-=bytestocopy;
 216       dest+=bytestocopy;
 217       byteoffset=0;
 218     }
 219     else {
 220       return(errorcode);
 221     }
 222   }
 223
 224   return(0);
 225 }
 226
 227
 228
 229 LONG availablespace(BLCK block,ULONG maxneeded) {
 230   struct CacheBuffer *cb;
 231   struct fsBitmap *b;
 232   ULONG longs=globals->blocks_inbitmap>>5;
 233   ULONG maxbitmapblock=globals->block_bitmapbase+globals->blocks_bitmap;
 234   LONG blocksfound=0;
 235   ULONG bitstart;
 236   LONG bitend;
 237   LONG errorcode=0;
 238   BLCK nextblock=globals->block_bitmapbase+block/globals->blocks_inbitmap;
 239
 240   /* Determines the amount of free blocks starting from block /block/.
 241      If there are no blocks found or if there was an error -1 is returned,
 242      otherwise this function will count the number of free blocks until
 243      an allocated block is encountered or until maxneeded has been
 244      exceeded. */
 245
 246   bitstart=block % globals->blocks_inbitmap;
 247
 248   while(nextblock<maxbitmapblock && (errorcode=readcachebuffercheck(&cb,nextblock++,BITMAP_ID))==0) {
 249     b=cb->data;
 250
 251     if((bitend=bmffz(b->bitmap,longs,bitstart))<(32*longs)) {
 252       blocksfound+=bitend-bitstart;
 253       return(blocksfound);
 254     }
 255
 256     blocksfound+=globals->blocks_inbitmap-bitstart;
 257     if(blocksfound>=maxneeded) {
 258       return(blocksfound);
 259     }
 260
 261     bitstart=0;
 262   }
 263
 264   if(errorcode!=0) {
 265     return(-1);
 266   }
 267
 268   return(blocksfound);
 269 }
 270
 271
 272
 273 LONG allocatedspace(BLCK block,ULONG maxneeded) {
 274   struct CacheBuffer *cb;
 275   struct fsBitmap *b;
 276   ULONG longs=globals->blocks_inbitmap>>5;
 277   ULONG maxbitmapblock=globals->block_bitmapbase+globals->blocks_bitmap;
 278   LONG blocksfound=0;
 279   ULONG bitstart;
 280   LONG bitend;
 281   LONG errorcode=0;
 282   BLCK nextblock=globals->block_bitmapbase+block/globals->blocks_inbitmap;
 283
 284   /* Determines the amount of free blocks starting from block /block/.
 285      If there are no blocks found or if there was an error -1 is returned,
 286      otherwise this function will count the number of free blocks until
 287      an allocated block is encountered or until maxneeded has been
 288      exceeded. */
 289
 290   bitstart=block % globals->blocks_inbitmap;
 291
 292   while(nextblock<maxbitmapblock && (errorcode=readcachebuffercheck(&cb,nextblock++,BITMAP_ID))==0) {
 293     b=cb->data;
 294
 295     if((bitend=bmffo(b->bitmap,longs,bitstart))<(32*longs)) {
 296       blocksfound+=bitend-bitstart;
 297       return(blocksfound);
 298     }
 299
 300     blocksfound+=globals->blocks_inbitmap-bitstart;
 301     if(blocksfound>=maxneeded) {
 302       return(blocksfound);
 303     }
 304
 305     bitstart=0;
 306   }
 307
 308   if(errorcode!=0) {
 309     return(-1);
 310   }
 311
 312   return(blocksfound);
 313 }
 314
 315
 316
 317 LONG findspace2(ULONG maxneeded, BLCK start, BLCK end, BLCK *returned_block, ULONG *returned_blocks) {
 318   struct CacheBuffer *cb;
 319   ULONG longs=globals->blocks_inbitmap>>5;
 320   ULONG space=0;
 321   ULONG block;
 322   BLCK bitmapblock=globals->block_bitmapbase + start/globals->blocks_inbitmap;
 323   BLCK breakpoint;
 324   LONG bitstart,bitend;
 325   LONG reads;
 326   LONG errorcode;
 327
 328   /* This function checks the bitmap and tries to locate /maxneeded/ adjacent
 329      unused blocks, or less if there aren't that many unused adjacent blocks.
 330
 331      The number of blocks found will be stored in returned_blocks, and the
 332      location of those blocks stored in returned_block.  The number of blocks
 333      found can be zero if the area to search in didn't contain any free blocks.
 334      This is not an error -- the return value will be 0.
 335
 336      Errors which occur during the execution of this function are returned as
 337      normal.  The contents of returned_block and returned_blocks is undefined
 338      in that case.
 339
 340      The search-area is limited by startblock (inclusive) and endblock (exclusive).
 341      Note that the search-area loops, so it is possible to do wrap-around searches
 342      by setting endblock<=startblock (see table below):
 343
 344      Start-block    End-block    Area searched
 345
 346           0            10        1111111111
 347           5            10        .....11111
 348           5             7        .....11...
 349           5             5        2222211111
 350           9            10        .........1
 351           9             0        .........1
 352           9             1        2........1
 353          10             2        11........ */
 354
 355   if(start>=globals->blocks_total) {
 356     start-=globals->blocks_total;
 357   }
 358
 359   if(end==0) {
 360     end=globals->blocks_total;
 361   }
 362
 363   reads=((end-1)/globals->blocks_inbitmap) + 1 - start/globals->blocks_inbitmap;
 364   if(start>=end) {
 365     reads+=(globals->blocks_total-1)/globals->blocks_inbitmap + 1;
 366   }
 367
 368   breakpoint=(start<end ? end : globals->blocks_total);
 369
 370   *returned_block=0;
 371   *returned_blocks=0;
 372
 373   bitend=start % globals->blocks_inbitmap;
 374   block=start-bitend;
 375
 376   while((errorcode=readcachebuffercheck(&cb, bitmapblock++, BITMAP_ID))==0) {
 377     struct fsBitmap *b=cb->data;
 378     ULONG localbreakpoint=breakpoint-block;
 379
 380     if(localbreakpoint>globals->blocks_inbitmap) {
 381       localbreakpoint=globals->blocks_inbitmap;
 382     }
 383
 384     /* At this point space contains the amount of free blocks at
 385        the end of the previous bitmap block.  If there are no
 386        free blocks at the start of this bitmap block, space will
 387        be set to zero, since in that case the space isn't adjacent. */
 388
 389     while((bitstart=bmffo(b->bitmap, longs, bitend))<globals->blocks_inbitmap) {
 390
 391       /* found the start of an empty space, now find out how large it is */
 392
 393       if(bitstart >= localbreakpoint) {     // Oct  3 1999: Check if the start of this empty space is within bounds.
 394         break;
 395       }
 396
 397       if(bitstart!=0) {
 398         space=0;
 399       }
 400
 401       bitend=bmffz(b->bitmap, longs, bitstart);
 402
 403       if(bitend > localbreakpoint) {
 404         bitend=localbreakpoint;
 405       }
 406
 407       space+=bitend-bitstart;
 408
 409       if(*returned_blocks<space) {
 410         *returned_block=block+bitend-space;
 411         if(space>=maxneeded) {
 412           *returned_blocks=maxneeded;
 413           return(0);
 414         }
 415         *returned_blocks=space;
 416       }
 417
 418       if(bitend>=localbreakpoint) {
 419         break;
 420       }
 421     }
 422
 423     if(--reads==0) {
 424       break;
 425     }
 426
 427     /* no (more) empty spaces found in this block */
 428
 429     if(bitend!=globals->blocks_inbitmap) {
 430       space=0;
 431     }
 432
 433     bitend=0;
 434     block+=globals->blocks_inbitmap;
 435
 436     if(block>=globals->blocks_total) {
 437       block=0;
 438       space=0;
 439       breakpoint=end;
 440       bitmapblock=globals->block_bitmapbase;
 441     }
 442   }
 443
 444   return(errorcode);
 445 }
 446
 447
 448 #if 0
 449 LONG findspace(ULONG blocksneeded,BLCK startblock,BLCK endblock,BLCK *returned_block) {
 450   ULONG blocks;
 451   LONG errorcode;
 452
 453   /* This function checks the bitmap and tries to locate at least /blocksneeded/
 454      adjacent unused blocks.  If found it set returned_block to the start block.
 455      If not it is set to zero.  Any error is returned.
 456
 457      The search-area is limited by startblock (inclusive) and endblock (exclusive). */
 458
 459   if((errorcode=findspace2(blocksneeded, startblock, endblock, returned_block, &blocks))==0) {
 460     if(blocks!=blocksneeded) {
 461       _DEBUG(("findspace: %ld != %ld\n", blocks, blocksneeded));
 462       return(ERROR_DISK_FULL);
 463     }
 464   }
 465
 466   return(errorcode);
 467 }
 468 #endif
 469
 470
 471 LONG findspace(ULONG blocksneeded, BLCK startblock, BLCK endblock, BLCK *returned_block) {
 472   ULONG blocks;
 473   LONG errorcode;
 474
 475   /* This function checks the bitmap and tries to locate at least /blocksneeded/
 476      adjacent unused blocks.  If found it sets returned_block to the start block
 477      and returns no error.  If not found, ERROR_DISK_IS_FULL is returned and
 478      returned_block is set to zero.  Any other errors are returned as well.
 479
 480      The search-area is limited by startblock (inclusive) and endblock (exclusive).
 481      Note that the search-area loops, so it is possible to do wrap-around searches
 482      by setting endblock<=startblock (see table below):
 483
 484      Start-block    End-block    Area searched
 485
 486           0            10        1111111111
 487           5            10        .....11111
 488           5             7        .....11...
 489           5             5        2222211111
 490           9            10        .........1
 491           9             0        .........1
 492           9             1        2........1 */
 493
 494   if((errorcode=findspace2(blocksneeded, startblock, endblock, returned_block, &blocks))==0) {
 495     if(blocks!=blocksneeded) {
 496       _DEBUG(("findspace: %ld != %ld\n", blocks, blocksneeded));
 497       return(ERROR_DISK_FULL);
 498     }
 499   }
 500
 501   return(errorcode);
 502 }
 503
 504
 505
 506 LONG findandmarkspace(ULONG blocksneeded, BLCK *returned_block) {
 507   LONG errorcode;
 508
 509   // This function is currently only used by AdminSpace allocation. */
 510
 511   if(enoughspace(blocksneeded)!=FALSE) {
 512
 513 //  if((errorcode=findspace(blocksneeded, block_rovingblockptr, block_rovingblockptr, returned_block))==0)
 514
 515     if((errorcode=findspace(blocksneeded, 0, globals->blocks_total, returned_block))==0) {
 516       errorcode=markspace(*returned_block,blocksneeded);
 517     }
 518   }
 519   else {
 520     errorcode=ERROR_DISK_FULL;
 521   }
 522
 523   return(errorcode);
 524 }
 525
 526
 527
 528 LONG smartfindandmarkspace(BLCK startblock,ULONG blocksneeded) {
 529   LONG freeblocks,allocblocks;
 530   BLCK block=startblock;
 531   ULONG blocksfound=0;
 532   UWORD entry=0;
 533   UWORD n;
 534   ULONG blocks, smallestfragment, newsmallestfragment;
 535   LONG errorcode;
 536
 537   /* This function searches the bitmap to locate /blocks/ blocks.  It will
 538      return the amount of blocks needed in a number of fragments if necessary.
 539
 540      Followed strategy:
 541
 542      If there are less free blocks than there are needed then this function
 543      will keep looking until the bitmap has been scanned completely.  It will
 544      return every free block available in this case.
 545
 546      If the number of blocks found is larger than the amount of needed blocks
 547      then there are a couple of options:
 548
 549      a) If the blocks found are a single fragment, then return immediately.
 550      b) If the blocks have fragments which average above 64K and atleast
 551         a quarter of the bitmap has been scanned, then return immediately.
 552      c) If the blocks have fragments which average above 16K and atleast
 553         half the bitmap has been scanned, then return immediately.
 554      d) Otherwise scan the bitmap completely (expensive!). */
 555
 556   if(enoughspace(blocksneeded)!=FALSE) {
 557
 558     while(entry<SPACELIST_MAX) {
 559       freeblocks=availablespace(block,blocksneeded);
 560       _XDEBUG((DEBUG_BITMAP,"sfams: availablespace returned %ld for block %ld while we needed %ld blocks\n",freeblocks,block,blocksneeded));
 561
 562       if(freeblocks>0) {
 563         if(freeblocks>=blocksneeded) {
 564           entry=0;
 565           globals->spacelist[entry].block=block;
 566           globals->spacelist[entry++].blocks=freeblocks;
 567           blocksfound=freeblocks;
 568           break;
 569         }
 570
 571         globals->spacelist[entry].block=block;
 572
 573         if(block<startblock && block+freeblocks>=startblock) {
 574           freeblocks=startblock-block;
 575
 576           blocksfound+=freeblocks;
 577           globals->spacelist[entry++].blocks=freeblocks;
 578           break;
 579         }
 580
 581         blocksfound+=freeblocks;
 582         globals->spacelist[entry++].blocks=freeblocks;
 583       }
 584       else if(freeblocks<0) {
 585         return(ERROR_DISK_FULL);
 586       }
 587
 588       block+=freeblocks;
 589       if(block>=globals->blocks_total) {
 590         if(startblock==0) {
 591           break;
 592         }
 593         block=0;
 594       }
 595
 596       allocblocks=allocatedspace(block,globals->blocks_inbitmap*2);
 597       _XDEBUG((DEBUG_BITMAP,"sfams: allocatedspace returned %ld for block %ld while we needed %ld blocks\n",allocblocks,block,globals->blocks_inbitmap*2));
 598
 599       if(allocblocks<0) {
 600         _DEBUG(("sfams: disk full 1\n"));
 601         return(ERROR_DISK_FULL);
 602       }
 603       else if(block<startblock && block+allocblocks>=startblock) {
 604         break;
 605       }
 606
 607       block+=allocblocks;
 608       if(block>=globals->blocks_total) {
 609         if(startblock==0) {
 610           break;
 611         }
 612         block=0;
 613       }
 614     }
 615
 616     if(entry==0) {
 617       _DEBUG(("sfams: disk full 2\n"));
 618       return(ERROR_DISK_FULL);
 619     }
 620
 621     globals->spacelist[entry].block=0;
 622
 623     /* blocksfound, entry & blocksneeded */
 624
 625     /* We need to eliminate the smallest fragments from the spacelist. */
 626
 627     smallestfragment=1;
 628
 629     while(blocksfound>=blocksneeded+smallestfragment) {
 630       n=0;
 631       newsmallestfragment=0xFFFF;
 632
 633       while(globals->spacelist[n].block!=0) {
 634         blocks=globals->spacelist[n].blocks;
 635         if(blocks!=0) {
 636           if(blocks==smallestfragment) {
 637             blocksfound-=smallestfragment;
 638             globals->spacelist[n].blocks=0;
 639             if(blocksfound-smallestfragment<blocksneeded) {
 640               break;
 641             }
 642           }
 643           else if(blocks<newsmallestfragment) {
 644             newsmallestfragment=blocks;
 645           }
 646         }
 647         n++;
 648       }
 649
 650       smallestfragment=newsmallestfragment;
 651     }
 652
 653     /* Now we need to mark the remaining fragments as used space.  The
 654        last fragment may need to be partially marked, depending on
 655        /blocksneeded/. */
 656
 657     n=0;
 658     while(globals->spacelist[n].block!=0) {
 659       blocks=globals->spacelist[n].blocks;
 660       if(blocks!=0) {
 661         if(blocksneeded<blocks) {
 662           blocks=blocksneeded;
 663         }
 664
 665         if((errorcode=markspace(globals->spacelist[n].block,blocks))!=0) {
 666           return(errorcode);
 667         }
 668
 669         blocksneeded-=blocks;
 670       }
 671
 672       n++;
 673     }
 674   }
 675   else {
 676     _DEBUG(("sfams: disk full 3\n"));
 677     return(ERROR_DISK_FULL);
 678   }
 679
 680   return(0);
 681 }
 682
 683
 684
 685
 686 /*
 687
 688  This function returns for (128, 353219, blocks_total) : 351840 (!!)  not allowed!
 689
 690 */
 691
 692
 693
 694 LONG findspace2_backwards(ULONG maxneeded, BLCK start, BLCK end, BLCK *returned_block, ULONG *returned_blocks) {
 695   struct CacheBuffer *cb;
 696   ULONG space=0;
 697   ULONG block;
 698   BLCK bitmapblock=globals->block_bitmapbase+start/globals->blocks_inbitmap;
 699   BLCK breakpoint;
 700   BLCK prevbitmapblock=globals->block_bitmapbase+(end-1)/globals->blocks_inbitmap;
 701   LONG bitstart,bitend;
 702   LONG errorcode;
 703
 704   /* This function checks the bitmap and tries to locate /maxneeded/ adjacent
 705      unused blocks, or less if there aren't that many unused adjacent blocks.
 706
 707      The number of blocks found will be stored in returned_blocks, and the
 708      location of those blocks stored in returned_block.  The number of blocks
 709      found can be zero if the area to search in didn't contain any free blocks.
 710      This is not an error -- the return value will be 0.
 711
 712      Errors which occur during the execution of this function are returned as
 713      normal.  The contents of returned_block and returned_blocks is undefined
 714      in that case.
 715
 716      The search-area is limited by start (inclusive) and end (exclusive). */
 717
 718 /*
 719   if(start>=blocks_total) {
 720     start-=blocks_total;
 721   }
 722
 723   if(end==0) {
 724     end=blocks_total;
 725   }
 726
 727   reads=((end-1)/blocks_inbitmap) + 1 - start/blocks_inbitmap;
 728   if(start>=end) {
 729     reads+=(blocks_total-1)/blocks_inbitmap + 1;
 730   }
 731
 732   breakpoint=(start<end ? start : 0);
 733 */
 734   breakpoint=start;
 735
 736   *returned_block=0;
 737   *returned_blocks=0;
 738
 739   bitstart=(end-1) % globals->blocks_inbitmap;
 740   block=(end-1) - bitstart;
 741
 742   while((errorcode=readcachebuffercheck(&cb, prevbitmapblock--, BITMAP_ID))==0) {
 743     struct fsBitmap *b=cb->data;
 744     LONG localbreakpoint=breakpoint-block;
 745
 746     if(localbreakpoint<0 || localbreakpoint>=globals->blocks_inbitmap) {
 747       localbreakpoint=0;
 748     }
 749
 750     while((bitend=bmflo(b->bitmap, bitstart))>=0) {
 751
 752       /* Found the end of an empty space, now find out how large it is. */
 753
 754       if(bitend < localbreakpoint) {       // Check if the end of this empty space is within bounds.
 755         break;
 756       }
 757
 758       if(bitend!=globals->blocks_inbitmap-1) {
 759         space=0;
 760       }
 761
 762       bitstart=bmflz(b->bitmap, bitend);
 763
 764       if(bitstart+1 < localbreakpoint) {
 765         bitstart=localbreakpoint-1;
 766       }
 767
 768       space+=bitend-bitstart;
 769
 770       if(*returned_blocks<space) {
 771         *returned_block=block+bitstart+1;
 772         if(space>=maxneeded) {
 773           *returned_block=*returned_block+space-maxneeded;
 774           *returned_blocks=maxneeded;
 775           return(0);
 776         }
 777         *returned_blocks=space;
 778       }
 779
 780       if(bitstart<=localbreakpoint) {
 781         break;
 782       }
 783     }
 784
 785     if(prevbitmapblock<bitmapblock) {
 786       break;
 787     }
 788
 789     /* no (more) empty spaces found in this block */
 790
 791     if(bitstart!=-1) {
 792       space=0;
 793     }
 794
 795     bitstart=globals->blocks_inbitmap-1;
 796     block-=globals->blocks_inbitmap;
 797   }
 798
 799   return(errorcode);
 800 }