uspace/srv/fs/mfs/mfs_balloc.c

   1 /*
   2  * Copyright (c) 2011 Maurizio Lombardi
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * - Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  * - Redistributions in binary form must reproduce the above copyright
  12  *   notice, this list of conditions and the following disclaimer in the
  13  *   documentation and/or other materials provided with the distribution.
  14  * - The name of the author may not be used to endorse or promote products
  15  *   derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  18  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  19  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  20  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  21  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  22  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 /** @addtogroup fs
  30  * @{
  31  */
  32
  33 #include <stdlib.h>
  34 #include "mfs.h"
  35
  36 static int
  37 find_free_bit_and_set(bitchunk_t *b, const int bsize,
  38     const bool native, unsigned start_bit);
  39
  40 static int
  41 mfs_free_bit(struct mfs_instance *inst, uint32_t idx, bmap_id_t bid);
  42
  43 static int
  44 mfs_alloc_bit(struct mfs_instance *inst, uint32_t *idx, bmap_id_t bid);
  45
  46 static int
  47 mfs_count_free_bits(struct mfs_instance *inst, bmap_id_t bid, uint32_t *free);
  48
  49
  50 /**Allocate a new inode.
  51  *
  52  * @param inst          Pointer to the filesystem instance.
  53  * @param inum          Pointer to a 32 bit number where the index of
  54  *                      the new inode will be saved.
  55  *
  56  * @return              EOK on success or a negative error code.
  57  */
  58 int
  59 mfs_alloc_inode(struct mfs_instance *inst, uint32_t *inum)
  60 {
  61         int r = mfs_alloc_bit(inst, inum, BMAP_INODE);
  62         return r;
  63 }
  64
  65 /**Free an inode.
  66  *
  67  * @param inst          Pointer to the filesystem instance.
  68  * @param inum          Number of the inode to free.
  69  *
  70  * @return              EOK on success or a negative error code.
  71  */
  72 int
  73 mfs_free_inode(struct mfs_instance *inst, uint32_t inum)
  74 {
  75         return mfs_free_bit(inst, inum, BMAP_INODE);
  76 }
  77
  78 /**Allocate a new zone.
  79  *
  80  * @param inst          Pointer to the filesystem instance.
  81  * @param zone          Pointer to a 32 bit number where the index
  82  *                      of the zone will be saved.
  83  *
  84  * @return              EOK on success or a negative error code.
  85  */
  86 int
  87 mfs_alloc_zone(struct mfs_instance *inst, uint32_t *zone)
  88 {
  89         int r = mfs_alloc_bit(inst, zone, BMAP_ZONE);
  90         if (r != EOK)
  91                 return r;
  92
  93         /* Update the cached number of free zones */
  94         struct mfs_sb_info *sbi = inst->sbi;
  95         if (sbi->nfree_zones_valid)
  96                 sbi->nfree_zones--;
  97
  98         *zone += inst->sbi->firstdatazone - 1;
  99         return r;
 100 }
 101
 102 /**Free a zone.
 103  *
 104  * @param inst          Pointer to the filesystem instance.
 105  * @param zone          Index of the zone to free.
 106  *
 107  * @return              EOK on success or a negative error code.
 108  */
 109 int
 110 mfs_free_zone(struct mfs_instance *inst, uint32_t zone)
 111 {
 112         int r;
 113
 114         zone -= inst->sbi->firstdatazone - 1;
 115
 116         r = mfs_free_bit(inst, zone, BMAP_ZONE);
 117         if (r != EOK)
 118                 return r;
 119
 120         /* Update the cached number of free zones */
 121         struct mfs_sb_info *sbi = inst->sbi;
 122         if (sbi->nfree_zones_valid)
 123                 sbi->nfree_zones++;
 124
 125         return r;
 126 }
 127
 128 /** Count the number of free zones
 129  *
 130  * @param inst          Pointer to the instance structure.
 131  * @param zones         Pointer to the memory location where the result
 132  *                      will be stored.
 133  *
 134  * @return              EOK on success or a negative error code.
 135  */
 136 int
 137 mfs_count_free_zones(struct mfs_instance *inst, uint32_t *zones)
 138 {
 139         return mfs_count_free_bits(inst, BMAP_ZONE, zones);
 140 }
 141
 142 /** Count the number of free inodes
 143  *
 144  * @param inst          Pointer to the instance structure.
 145  * @param zones         Pointer to the memory location where the result
 146  *                      will be stored.
 147  *
 148  * @return              EOK on success or a negative error code.
 149  */
 150
 151 int
 152 mfs_count_free_inodes(struct mfs_instance *inst, uint32_t *inodes)
 153 {
 154         return mfs_count_free_bits(inst, BMAP_INODE, inodes);
 155 }
 156
 157 /** Count the number of free bits in a bitmap
 158  *
 159  * @param inst          Pointer to the instance structure.
 160  * @param bid           Type of the bitmap (inode or zone).
 161  * @param free          Pointer to the memory location where the result
 162  *                      will be stores.
 163  *
 164  * @return              EOK on success or a negative error code.
 165  */
 166 static int
 167 mfs_count_free_bits(struct mfs_instance *inst, bmap_id_t bid, uint32_t *free)
 168 {
 169         int r;
 170         unsigned start_block;
 171         unsigned long nblocks;
 172         unsigned long nbits;
 173         unsigned long block;
 174         unsigned long free_bits = 0;
 175         bitchunk_t chunk;
 176         size_t const bitchunk_bits = sizeof(bitchunk_t) * 8;
 177         block_t *b;
 178         struct mfs_sb_info *sbi = inst->sbi;
 179
 180         start_block = MFS_BMAP_START_BLOCK(sbi, bid);
 181         nblocks = MFS_BMAP_SIZE_BLOCKS(sbi, bid);
 182         nbits = MFS_BMAP_SIZE_BITS(sbi, bid);
 183
 184         for (block = 0; block < nblocks; ++block) {
 185                 r = block_get(&b, inst->service_id, block + start_block,
 186                     BLOCK_FLAGS_NONE);
 187                 if (r != EOK)
 188                         return r;
 189
 190                 size_t i;
 191                 bitchunk_t *data = (bitchunk_t *) b->data;
 192
 193                 /* Read the bitmap block, chunk per chunk,
 194                  * counting the zero bits.
 195                  */
 196                 for (i = 0; i < sbi->block_size / sizeof(bitchunk_t); ++i) {
 197                         chunk = conv32(sbi->native, data[i]);
 198
 199                         size_t bit;
 200                         for (bit = 0; bit < bitchunk_bits && nbits > 0;
 201                             ++bit, --nbits) {
 202                                 if (!(chunk & (1 << bit)))
 203                                         free_bits++;
 204                         }
 205
 206                         if (nbits == 0)
 207                                 break;
 208                 }
 209
 210                 r = block_put(b);
 211                 if (r != EOK)
 212                         return r;
 213         }
 214
 215         *free = free_bits;
 216         assert(nbits == 0);
 217
 218         return EOK;
 219 }
 220
 221 /**Clear a bit in a bitmap.
 222  *
 223  * @param inst          Pointer to the filesystem instance.
 224  * @param idx           Index of the bit to clear.
 225  * @param bid           BMAP_ZONE if operating on the zone's bitmap,
 226  *                      BMAP_INODE if operating on the inode's bitmap.
 227  *
 228  * @return              EOK on success or a negative error code.
 229  */
 230 static int
 231 mfs_free_bit(struct mfs_instance *inst, uint32_t idx, bmap_id_t bid)
 232 {
 233         struct mfs_sb_info *sbi;
 234         int r;
 235         unsigned start_block;
 236         unsigned *search;
 237         block_t *b;
 238
 239         sbi = inst->sbi;
 240
 241         start_block = MFS_BMAP_START_BLOCK(sbi, bid);
 242
 243         if (bid == BMAP_ZONE) {
 244                 search = &sbi->zsearch;
 245                 if (idx > sbi->nzones) {
 246                         printf(NAME ": Error! Trying to free beyond the "
 247                             "bitmap max size\n");
 248                         return -1;
 249                 }
 250         } else {
 251                 /* bid == BMAP_INODE */
 252                 search = &sbi->isearch;
 253                 if (idx > sbi->ninodes) {
 254                         printf(NAME ": Error! Trying to free beyond the "
 255                             "bitmap max size\n");
 256                         return -1;
 257                 }
 258         }
 259
 260         /* Compute the bitmap block */
 261         uint32_t block = idx / (sbi->block_size * 8) + start_block;
 262
 263         r = block_get(&b, inst->service_id, block, BLOCK_FLAGS_NONE);
 264         if (r != EOK)
 265                 goto out_err;
 266
 267         /* Compute the bit index in the block */
 268         idx %= (sbi->block_size * 8);
 269         bitchunk_t *ptr = b->data;
 270         bitchunk_t chunk;
 271         const size_t chunk_bits = sizeof(bitchunk_t) * 8;
 272
 273         chunk = conv32(sbi->native, ptr[idx / chunk_bits]);
 274         chunk &= ~(1 << (idx % chunk_bits));
 275         ptr[idx / chunk_bits] = conv32(sbi->native, chunk);
 276
 277         b->dirty = true;
 278         r = block_put(b);
 279
 280         if (*search > idx)
 281                 *search = idx;
 282
 283 out_err:
 284         return r;
 285 }
 286
 287 /**Search a free bit in a bitmap and mark it as used.
 288  *
 289  * @param inst          Pointer to the filesystem instance.
 290  * @param idx           Pointer of a 32 bit number where the index
 291  *                      of the found bit will be stored.
 292  * @param bid           BMAP_ZONE if operating on the zone's bitmap,
 293  *                      BMAP_INODE if operating on the inode's bitmap.
 294  *
 295  * @return              EOK on success or a negative error code.
 296  */
 297 static int
 298 mfs_alloc_bit(struct mfs_instance *inst, uint32_t *idx, bmap_id_t bid)
 299 {
 300         struct mfs_sb_info *sbi;
 301         uint32_t limit;
 302         unsigned long nblocks;
 303         unsigned *search, i, start_block;
 304         unsigned bits_per_block;
 305         int r, freebit;
 306
 307         sbi = inst->sbi;
 308
 309         start_block = MFS_BMAP_START_BLOCK(sbi, bid);
 310         limit = MFS_BMAP_SIZE_BITS(sbi, bid);
 311         nblocks = MFS_BMAP_SIZE_BLOCKS(sbi, bid);
 312
 313         if (bid == BMAP_ZONE) {
 314                 search = &sbi->zsearch;
 315         } else {
 316                 /* bid == BMAP_INODE */
 317                 search = &sbi->isearch;
 318         }
 319         bits_per_block = sbi->block_size * 8;
 320
 321         block_t *b;
 322
 323 retry:
 324
 325         for (i = *search / bits_per_block; i < nblocks; ++i) {
 326                 r = block_get(&b, inst->service_id, i + start_block,
 327                     BLOCK_FLAGS_NONE);
 328
 329                 if (r != EOK)
 330                         goto out;
 331
 332                 unsigned tmp = *search % bits_per_block;
 333
 334                 freebit = find_free_bit_and_set(b->data, sbi->block_size,
 335                     sbi->native, tmp);
 336                 if (freebit == -1) {
 337                         /* No free bit in this block */
 338                         r = block_put(b);
 339                         if (r != EOK)
 340                                 goto out;
 341                         continue;
 342                 }
 343
 344                 /* Free bit found in this block, compute the real index */
 345                 *idx = freebit + bits_per_block * i;
 346                 if (*idx > limit) {
 347                         /* Index is beyond the limit, it is invalid */
 348                         r = block_put(b);
 349                         if (r != EOK)
 350                                 goto out;
 351                         break;
 352                 }
 353
 354                 *search = *idx;
 355                 b->dirty = true;
 356                 r = block_put(b);
 357                 goto out;
 358         }
 359
 360         if (*search > 0) {
 361                 /* Repeat the search from the first bitmap block */
 362                 *search = 0;
 363                 goto retry;
 364         }
 365
 366         /* Free bit not found, return error */
 367         return ENOSPC;
 368
 369 out:
 370         return r;
 371 }
 372
 373 static int
 374 find_free_bit_and_set(bitchunk_t *b, const int bsize,
 375     const bool native, unsigned start_bit)
 376 {
 377         int r = -1;
 378         unsigned i, j;
 379         bitchunk_t chunk;
 380         const size_t chunk_bits = sizeof(bitchunk_t) * 8;
 381
 382         for (i = start_bit / chunk_bits;
 383             i < bsize / sizeof(bitchunk_t); ++i) {
 384
 385                 if (!(~b[i])) {
 386                         /* No free bit in this chunk */
 387                         continue;
 388                 }
 389
 390                 chunk = conv32(native, b[i]);
 391
 392                 for (j = 0; j < chunk_bits; ++j) {
 393                         if (!(chunk & (1 << j))) {
 394                                 r = i * chunk_bits + j;
 395                                 chunk |= 1 << j;
 396                                 b[i] = conv32(native, chunk);
 397                                 goto found;
 398                         }
 399                 }
 400         }
 401 found:
 402         return r;
 403 }
 404
 405 /**
 406  * @}
 407  */
 408