modules/ps2fs/bitmap.c

   1 /*
   2 # _____     ___ ____     ___ ____
   3 #  ____|   |    ____|   |        | |____|
   4 # |     ___|   |____ ___|    ____| |    \    PS2DEV Open Source Project.
   5 #-----------------------------------------------------------------------
   6 # Copyright 2001-2004, ps2dev - http://www.ps2dev.org
   7 # Licenced under Academic Free License version 2.0
   8 # Review ps2sdk README & LICENSE files for further details.
   9 #
  10 # $Id: bitmap.c 911 2005-03-14 21:02:17Z oopo $
  11 # PFS bitmap manipulation routines
  12 */
  13
  14 #include "pfs.h"
  15
  16 u32 bitsPerBitmapChunk = 8192; // number of bitmap bits in each bitmap data chunk (1024 bytes)
  17
  18 // "Free zone" map. Used to get number of free zone in bitmap, 4-bits at a time
  19 u32 free_bitmap[16]={4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0};
  20
  21 void bitmapSetupInfo(pfs_mount_t *pfsMount, t_bitmapInfo *info, u32 subpart, u32 number)
  22 {
  23         u32 size;
  24
  25         size = pfsMount->blockDev->getSize(pfsMount->fd, subpart) >> pfsMount->sector_scale;
  26
  27         info->chunk = number / bitsPerBitmapChunk;
  28         info->bit = number & 31;
  29         info->index = (number % bitsPerBitmapChunk) / 32;
  30         info->partitionChunks = size / bitsPerBitmapChunk;
  31         info->partitionRemainder = size % bitsPerBitmapChunk;
  32 }
  33
  34 // Allocates or frees (depending on operation) the bitmap area starting at chunk/index/bit, of size count
  35 void bitmapAllocFree(pfs_cache_t *clink, u32 operation, u32 subpart, u32 chunk, u32 index, u32 _bit, u32 count)
  36 {
  37         int result;
  38         u32 sector, bit;
  39
  40         while (clink)
  41         {
  42                 for ( ; index < (metaSize / 4) && count; index++, _bit = 0)
  43                 {
  44                         for (bit = _bit; bit < 32 && count; bit++, count--)
  45                         {
  46                                 if(operation == BITMAP_ALLOC)
  47                                 {
  48                                         if (clink->u.bitmap[index] & (1 << bit))
  49                                                 printf("ps2fs: Error: Tried to allocate used block!\n");
  50
  51                                         clink->u.bitmap[index] |= (1 << bit);
  52                                 }
  53                                 else
  54                                 {
  55                                         if ((clink->u.bitmap[index] & (1 << bit))==0)
  56                                                 printf("ps2fs: Error: Tried to free unused block!\n");
  57
  58                                         clink->u.bitmap[index] &= ~(1 << bit);
  59                                 }
  60                         }
  61                 }
  62
  63                 index = 0;
  64                 clink->flags |= CACHE_FLAG_DIRTY;
  65                 cacheAdd(clink);
  66
  67                 if (count==0)
  68                         break;
  69
  70                 chunk++;
  71
  72                 sector = (1 << clink->pfsMount->inode_scale) + chunk;
  73                 if(subpart==0)
  74                         sector += 0x2000 >> blockSize;
  75
  76                 clink = cacheGetData(clink->pfsMount, subpart, sector, CACHE_FLAG_BITMAP, &result);
  77         }
  78 }
  79
  80 // Attempts to allocate 'count' more continuous zones for 'bi'
  81 int bitmapAllocateAdditionalZones(pfs_mount_t *pfsMount, pfs_blockinfo *bi, u32 count)
  82 {
  83         int result;
  84         t_bitmapInfo info;
  85         pfs_cache_t *c;
  86         int res=0;
  87
  88         bitmapSetupInfo(pfsMount, &info, bi->subpart, bi->number+bi->count);
  89
  90         // Make sure we're not trying to allocate more than is possible
  91         if (65535-bi->count < count)
  92                 count=65535-bi->count;
  93
  94         // Loop over each bitmap chunk (each is 1024 bytes in size) until either we have allocated
  95         // the requested amount of blocks, or until we have run out of space on the current partition
  96         while ((((info.partitionRemainder==0) && (info.chunk < info.partitionChunks  )) ||
  97                 ((info.partitionRemainder!=0) && (info.chunk < info.partitionChunks+1))) && count)
  98         {
  99                 u32 sector=(1<<pfsMount->inode_scale) + info.chunk;
 100
 101                 // if main partition, add offset (in units of blocks)
 102                 if (bi->subpart==0)
 103                         sector += 0x2000 >> blockSize;
 104
 105                 // Read the bitmap chunk from the hdd
 106                 c=cacheGetData(pfsMount, bi->subpart, sector, CACHE_FLAG_BITMAP, &result);
 107                 if (c==0)break;
 108
 109                 // Loop over each 32-bit word in the current bitmap chunk until
 110                 // we find a used zone or we've allocated all the zones we need
 111                 while ((info.index < (info.chunk==info.partitionChunks ? info.partitionRemainder / 32 : metaSize / 4)) && count)
 112                 {
 113                         // Loop over each of the 32 bits in the current word from the current bitmap chunk,
 114                         // trying to allocate the requested number of zones
 115                         for ( ; (info.bit < 32) && count; count--)
 116                         {
 117                                 // We only want to allocate a continuous area, so if we come
 118                                 // accross a used zone bail
 119                                 if (c->u.bitmap[info.index] & (1<<info.bit))
 120                                 {
 121                                         cacheAdd(c);
 122                                         goto exit;
 123                                 }
 124
 125                                 // If the current bit in the bitmap is marked as free, mark it was used
 126                                 res++;
 127                                 c->u.bitmap[info.index] |= 1<<info.bit;
 128                                 info.bit++;
 129                                 c->flags |= CACHE_FLAG_DIRTY;
 130                         }
 131
 132                         info.index++;
 133                         info.bit=0;
 134                 }
 135                 cacheAdd(c);
 136                 info.index=0;
 137                 info.chunk++;
 138         }
 139 exit:
 140
 141         // Adjust global free zone counts
 142         pfsMount->free_zone[bi->subpart]-=res;
 143         pfsMount->zfree-=res;
 144         return res;
 145 }
 146
 147 // Searches for 'amount' free zones, starting from the position specified in 'bi'.
 148 // Returns 1 if allocation was successful, otherwise 0.
 149 int bitmapAllocZones(pfs_mount_t *pfsMount, pfs_blockinfo *bi, u32 amount)
 150 {
 151         t_bitmapInfo info;
 152         int result;
 153         u32 startBit = 0, startPos = 0, startChunk = 0, count = 0;
 154         u32 sector;
 155         pfs_cache_t *bitmap;
 156         u32 *bitmapEnd, *bitmapWord;
 157         u32 i;
 158
 159         bitmapSetupInfo(pfsMount, &info, bi->subpart, bi->number);
 160
 161         for ( ; ((info.partitionRemainder==0) && (info.chunk < info.partitionChunks))||
 162                 ((info.partitionRemainder!=0) && (info.chunk < info.partitionChunks+1)); info.chunk++){
 163
 164                 sector = info.chunk + (1 << pfsMount->inode_scale);
 165                 if(bi->subpart==0)
 166                         sector += 0x2000 >> blockSize;
 167
 168                 // read in the bitmap chunk
 169                 bitmap = cacheGetData(pfsMount, bi->subpart, sector, CACHE_FLAG_BITMAP, &result);
 170                 if(bitmap==0)
 171                         return 0;
 172
 173                 bitmapEnd=bitmap->u.bitmap +
 174                         (info.chunk == info.partitionChunks ? info.partitionRemainder / 32 : metaSize / 4);
 175
 176                 for (bitmapWord=bitmap->u.bitmap + info.index; bitmapWord < bitmapEnd; info.bit=0, bitmapWord++)
 177                 {
 178                         for (i=info.bit; i < 32; i++)
 179                         {
 180                                 // if this bit is marked as free..
 181                                 if (((*bitmapWord >> i) & 1)==0)
 182                                 {
 183                                         if (count==0)
 184                                         {
 185                                                 startBit = i;
 186                                                 startChunk = info.chunk;
 187                                                 startPos = bitmapWord - bitmap->u.bitmap;
 188                                         }
 189                                         if (++count == amount)
 190                                         {
 191                                                 bi->number = (startPos * 32) + (startChunk * bitsPerBitmapChunk) + startBit;
 192                                                 if (count < bi->count)
 193                                                         bi->count=count;
 194
 195                                                 if (bitmap->sector != (startChunk + (1 << pfsMount->inode_scale)))
 196                                                 {
 197                                                         cacheAdd(bitmap);
 198                                                         sector = (1 << pfsMount->inode_scale) + startChunk;
 199                                                         if(bi->subpart==0)
 200                                                                 sector += 0x2000 >> blockSize;
 201
 202                                                         bitmap = cacheGetData(pfsMount, bi->subpart, sector, CACHE_FLAG_BITMAP, &result);
 203                                                 }
 204
 205                                                 bitmapAllocFree(bitmap, BITMAP_ALLOC, bi->subpart, startChunk, startPos, startBit, bi->count);
 206                                                 return 1;
 207                                         }
 208                                 }
 209                                 else
 210                                         count=0;
 211                         }
 212                 }
 213                 cacheAdd(bitmap);
 214                 info.index=0;
 215         }
 216         return 0;
 217 }
 218
 219 // Searches for 'max_count' free zones over all the partitions, and
 220 // allocates them. Returns 0 on success, -ENOSPC if the zones could
 221 // not be allocated.
 222 int searchFreeZone(pfs_mount_t *pfsMount, pfs_blockinfo *bi, u32 max_count)
 223 {
 224         u32 num, count, n;
 225
 226         num = pfsMount->num_subs + 1;
 227
 228         if (bi->subpart > pfsMount->num_subs)
 229                 bi->subpart = 0;
 230         if (bi->number)
 231                 num = pfsMount->num_subs + 2;
 232
 233         count = max_count < 33 ? max_count : 32;                //min(max_count, 32)
 234         count = count < bi->count ? bi->count : count;  //max(count, bi->count)
 235                                                                                                         // => count = bound(bi->count, 32);
 236         for(; num >= 0; num--)
 237         {
 238                 for (n = count; n; n /= 2)
 239                 {
 240                         if ((pfsMount->free_zone[bi->subpart] >= n) &&
 241                             bitmapAllocZones(pfsMount, bi, n))
 242                         {
 243                                 pfsMount->free_zone[bi->subpart] -= bi->count;
 244                                 pfsMount->zfree -= bi->count;
 245                                 return 0;       // the good exit ;)
 246                         }
 247                 }
 248
 249                 bi->number=0;
 250                 bi->subpart++;
 251
 252                 if(bi->subpart == pfsMount->num_subs + 1)
 253                         bi->subpart=0;
 254         }
 255         return -ENOSPC;
 256 }
 257
 258 // De-allocates the block segment 'bi' in the bitmaps
 259 void bitmapFreeBlockSegment(pfs_mount_t *pfsMount, pfs_blockinfo *bi)
 260 {
 261         t_bitmapInfo info;
 262         pfs_cache_t *clink;
 263         u32 sector;
 264         int rv;
 265
 266         bitmapSetupInfo(pfsMount, &info, bi->subpart, bi->number);
 267
 268         sector = (1 << pfsMount->inode_scale) + info.chunk;
 269         if(bi->subpart==0)
 270                 sector += 0x2000 >> blockSize;
 271
 272         if((clink=cacheGetData(pfsMount, (u16)bi->subpart, sector, CACHE_FLAG_BITMAP, &rv)) != NULL)
 273         {
 274                 bitmapAllocFree(clink, BITMAP_FREE, bi->subpart, info.chunk, info.index, info.bit, bi->count);
 275                 pfsMount->free_zone[(u16)bi->subpart]+=bi->count;
 276                 pfsMount->zfree+=bi->count;
 277         }
 278 }
 279
 280 // Returns the number of free zones for the partition 'sub'
 281 int calcFreeZones(pfs_mount_t *pfsMount, int sub)
 282 {
 283         int result;
 284         t_bitmapInfo info;
 285         pfs_cache_t *clink;
 286         u32 i, bitmapSize, zoneFree=0, sector;
 287
 288         bitmapSetupInfo(pfsMount, &info, sub, 0);
 289
 290         while (((info.partitionRemainder!=0) && (info.chunk<info.partitionChunks+1)) ||
 291                ((info.partitionRemainder==0) && (info.chunk<info.partitionChunks)))
 292         {
 293                 bitmapSize = info.chunk==info.partitionChunks ? info.partitionRemainder>>3 : metaSize;
 294
 295                 sector = (1<<pfsMount->inode_scale) + info.chunk;
 296                 if (sub==0)
 297                         sector +=0x2000>>blockSize;
 298
 299                 if ((clink=cacheGetData(pfsMount, sub, sector, CACHE_FLAG_BITMAP, &result)))
 300                 {
 301                         for (i=0; i<bitmapSize; i++)
 302                         {
 303                                 zoneFree+=free_bitmap[((u8*)clink->u.bitmap)[i] & 0xF]
 304                                    +free_bitmap[((u8*)clink->u.bitmap)[i] >> 4];
 305                         }
 306
 307                         cacheAdd(clink);
 308                 }
 309                 info.chunk++;
 310         }
 311
 312         return zoneFree;
 313 }
 314
 315 // Debugging function, prints bitmap information
 316 void bitmapShow(pfs_mount_t *pfsMount)
 317 {
 318         int result;
 319         t_bitmapInfo info;
 320         u32 pn, bitcnt;
 321
 322         for (pn=0; pn < pfsMount->num_subs+1; pn++)
 323         {
 324                 bitcnt=bitsPerBitmapChunk;
 325                 bitmapSetupInfo(pfsMount, &info, pn, 0);
 326
 327                 while (((info.partitionRemainder!=0) && (info.chunk<info.partitionChunks+1)) ||
 328                        ((info.partitionRemainder==0) && (info.chunk<info.partitionChunks)))
 329                 {
 330                         pfs_cache_t *clink;
 331                         u32 sector = (1<<pfsMount->inode_scale) + info.chunk;
 332                         u32 i;
 333
 334                         if(pn==0)
 335                                 sector += 0x2000 >> blockSize;
 336                         clink=cacheGetData(pfsMount, pn, sector, CACHE_FLAG_BITMAP, &result);
 337
 338                         if (info.chunk == info.partitionChunks)
 339                                 bitcnt=info.partitionRemainder;
 340
 341                         printf("ps2fs: Zone show: pn %ld, bn %ld, bitcnt %ld\n", pn, info.chunk, bitcnt);
 342
 343                         for(i=0; (i < (1<<blockSize)) && ((i * 512) < (bitcnt / 8)); i++)
 344                                 printBitmap(clink->u.bitmap+128*i);
 345
 346                         cacheAdd(clink);
 347                         info.chunk++;
 348                 }
 349         }
 350 }
 351
 352 // Free's all blocks allocated to an inode
 353 void bitmapFreeInodeBlocks(pfs_cache_t *clink)
 354 {
 355         pfs_mount_t *pfsMount=clink->pfsMount;
 356         u32 i;
 357
 358         cacheUsedAdd(clink);
 359         for(i=0;i < clink->u.inode->number_data; i++)
 360         {
 361                 u32 index = fixIndex(i);
 362                 pfs_blockinfo *bi=&clink->u.inode->data[index];
 363                 int err;
 364
 365                 if(i!=0) {
 366                         if(index==0)
 367                                 if((clink = blockGetNextSegment(clink, &err))==NULL)
 368                                         return;
 369                 }
 370
 371                 bitmapFreeBlockSegment(pfsMount, bi);
 372                 cacheMarkClean(pfsMount, (u16)bi->subpart,  bi->number << pfsMount->inode_scale,
 373                         (bi->number + bi->count) << pfsMount->inode_scale);
 374         }
 375         cacheAdd(clink);
 376 }