/* * Copyright (c) 2011 Maurizio Lombardi * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * - Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * - Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * - The name of the author may not be used to endorse or promote products * derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** @addtogroup mfs * @{ */ #include #include "mfs.h" static int find_free_bit_and_set(bitchunk_t *b, const int bsize, const bool native, unsigned start_bit); static errno_t mfs_free_bit(struct mfs_instance *inst, uint32_t idx, bmap_id_t bid); static errno_t mfs_alloc_bit(struct mfs_instance *inst, uint32_t *idx, bmap_id_t bid); static errno_t mfs_count_free_bits(struct mfs_instance *inst, bmap_id_t bid, uint32_t *free); /**Allocate a new inode. * * @param inst Pointer to the filesystem instance. * @param inum Pointer to a 32 bit number where the index of * the new inode will be saved. * * @return EOK on success or an error code. */ errno_t mfs_alloc_inode(struct mfs_instance *inst, uint32_t *inum) { errno_t r = mfs_alloc_bit(inst, inum, BMAP_INODE); return r; } /**Free an inode. * * @param inst Pointer to the filesystem instance. * @param inum Number of the inode to free. * * @return EOK on success or an error code. */ errno_t mfs_free_inode(struct mfs_instance *inst, uint32_t inum) { return mfs_free_bit(inst, inum, BMAP_INODE); } /**Allocate a new zone. * * @param inst Pointer to the filesystem instance. * @param zone Pointer to a 32 bit number where the index * of the zone will be saved. * * @return EOK on success or an error code. */ errno_t mfs_alloc_zone(struct mfs_instance *inst, uint32_t *zone) { errno_t r = mfs_alloc_bit(inst, zone, BMAP_ZONE); if (r != EOK) return r; /* Update the cached number of free zones */ struct mfs_sb_info *sbi = inst->sbi; if (sbi->nfree_zones_valid) sbi->nfree_zones--; *zone += inst->sbi->firstdatazone - 1; return r; } /**Free a zone. * * @param inst Pointer to the filesystem instance. * @param zone Index of the zone to free. * * @return EOK on success or an error code. */ errno_t mfs_free_zone(struct mfs_instance *inst, uint32_t zone) { errno_t r; zone -= inst->sbi->firstdatazone - 1; r = mfs_free_bit(inst, zone, BMAP_ZONE); if (r != EOK) return r; /* Update the cached number of free zones */ struct mfs_sb_info *sbi = inst->sbi; if (sbi->nfree_zones_valid) sbi->nfree_zones++; return r; } /** Count the number of free zones * * @param inst Pointer to the instance structure. * @param zones Pointer to the memory location where the result * will be stored. * * @return EOK on success or an error code. */ errno_t mfs_count_free_zones(struct mfs_instance *inst, uint32_t *zones) { return mfs_count_free_bits(inst, BMAP_ZONE, zones); } /** Count the number of free inodes * * @param inst Pointer to the instance structure. * @param zones Pointer to the memory location where the result * will be stored. * * @return EOK on success or an error code. */ errno_t mfs_count_free_inodes(struct mfs_instance *inst, uint32_t *inodes) { return mfs_count_free_bits(inst, BMAP_INODE, inodes); } /** Count the number of free bits in a bitmap * * @param inst Pointer to the instance structure. * @param bid Type of the bitmap (inode or zone). * @param free Pointer to the memory location where the result * will be stores. * * @return EOK on success or an error code. */ static errno_t mfs_count_free_bits(struct mfs_instance *inst, bmap_id_t bid, uint32_t *free) { errno_t r; unsigned start_block; unsigned long nblocks; unsigned long nbits; unsigned long block; unsigned long free_bits = 0; bitchunk_t chunk; size_t const bitchunk_bits = sizeof(bitchunk_t) * 8; block_t *b; struct mfs_sb_info *sbi = inst->sbi; start_block = MFS_BMAP_START_BLOCK(sbi, bid); nblocks = MFS_BMAP_SIZE_BLOCKS(sbi, bid); nbits = MFS_BMAP_SIZE_BITS(sbi, bid); for (block = 0; block < nblocks; ++block) { r = block_get(&b, inst->service_id, block + start_block, BLOCK_FLAGS_NONE); if (r != EOK) return r; size_t i; bitchunk_t *data = (bitchunk_t *) b->data; /* * Read the bitmap block, chunk per chunk, * counting the zero bits. */ for (i = 0; i < sbi->block_size / sizeof(bitchunk_t); ++i) { chunk = conv32(sbi->native, data[i]); size_t bit; for (bit = 0; bit < bitchunk_bits && nbits > 0; ++bit, --nbits) { if (!(chunk & (1 << bit))) free_bits++; } if (nbits == 0) break; } r = block_put(b); if (r != EOK) return r; } *free = free_bits; assert(nbits == 0); return EOK; } /**Clear a bit in a bitmap. * * @param inst Pointer to the filesystem instance. * @param idx Index of the bit to clear. * @param bid BMAP_ZONE if operating on the zone's bitmap, * BMAP_INODE if operating on the inode's bitmap. * * @return EOK on success or an error code. */ static errno_t mfs_free_bit(struct mfs_instance *inst, uint32_t idx, bmap_id_t bid) { struct mfs_sb_info *sbi; errno_t r; unsigned start_block; unsigned *search; block_t *b; sbi = inst->sbi; start_block = MFS_BMAP_START_BLOCK(sbi, bid); if (bid == BMAP_ZONE) { search = &sbi->zsearch; if (idx > sbi->nzones) { printf(NAME ": Error! Trying to free beyond the " "bitmap max size\n"); return EIO; } } else { /* bid == BMAP_INODE */ search = &sbi->isearch; if (idx > sbi->ninodes) { printf(NAME ": Error! Trying to free beyond the " "bitmap max size\n"); return EIO; } } /* Compute the bitmap block */ uint32_t block = idx / (sbi->block_size * 8) + start_block; r = block_get(&b, inst->service_id, block, BLOCK_FLAGS_NONE); if (r != EOK) goto out_err; /* Compute the bit index in the block */ idx %= (sbi->block_size * 8); bitchunk_t *ptr = b->data; bitchunk_t chunk; const size_t chunk_bits = sizeof(bitchunk_t) * 8; chunk = conv32(sbi->native, ptr[idx / chunk_bits]); chunk &= ~(1 << (idx % chunk_bits)); ptr[idx / chunk_bits] = conv32(sbi->native, chunk); b->dirty = true; r = block_put(b); if (*search > idx) *search = idx; out_err: return r; } /**Search a free bit in a bitmap and mark it as used. * * @param inst Pointer to the filesystem instance. * @param idx Pointer of a 32 bit number where the index * of the found bit will be stored. * @param bid BMAP_ZONE if operating on the zone's bitmap, * BMAP_INODE if operating on the inode's bitmap. * * @return EOK on success or an error code. */ static errno_t mfs_alloc_bit(struct mfs_instance *inst, uint32_t *idx, bmap_id_t bid) { struct mfs_sb_info *sbi; uint32_t limit; unsigned long nblocks; unsigned *search, i, start_block; unsigned bits_per_block; errno_t r; int freebit; sbi = inst->sbi; start_block = MFS_BMAP_START_BLOCK(sbi, bid); limit = MFS_BMAP_SIZE_BITS(sbi, bid); nblocks = MFS_BMAP_SIZE_BLOCKS(sbi, bid); if (bid == BMAP_ZONE) { search = &sbi->zsearch; } else { /* bid == BMAP_INODE */ search = &sbi->isearch; } bits_per_block = sbi->block_size * 8; block_t *b; retry: for (i = *search / bits_per_block; i < nblocks; ++i) { r = block_get(&b, inst->service_id, i + start_block, BLOCK_FLAGS_NONE); if (r != EOK) goto out; unsigned tmp = *search % bits_per_block; freebit = find_free_bit_and_set(b->data, sbi->block_size, sbi->native, tmp); if (freebit == -1) { /* No free bit in this block */ r = block_put(b); if (r != EOK) goto out; continue; } /* Free bit found in this block, compute the real index */ *idx = freebit + bits_per_block * i; if (*idx > limit) { /* Index is beyond the limit, it is invalid */ r = block_put(b); if (r != EOK) goto out; break; } *search = *idx; b->dirty = true; r = block_put(b); goto out; } if (*search > 0) { /* Repeat the search from the first bitmap block */ *search = 0; goto retry; } /* Free bit not found, return error */ return ENOSPC; out: return r; } static int find_free_bit_and_set(bitchunk_t *b, const int bsize, const bool native, unsigned start_bit) { int r = -1; unsigned i, j; bitchunk_t chunk; const size_t chunk_bits = sizeof(bitchunk_t) * 8; for (i = start_bit / chunk_bits; i < bsize / sizeof(bitchunk_t); ++i) { if (!(~b[i])) { /* No free bit in this chunk */ continue; } chunk = conv32(native, b[i]); for (j = 0; j < chunk_bits; ++j) { if (!(chunk & (1 << j))) { r = i * chunk_bits + j; chunk |= 1 << j; b[i] = conv32(native, chunk); goto found; } } } found: return r; } /** * @} */