source: rtems/cpukit/libfs/src/rfs/rtems-rfs-block.c @ 0ec9bbc

/**
 * @file
 *
 * @brief RTEMS File Systems Block Routines
 * @ingroup rtems_rfs
 * 
 * These functions manage blocks in the RFS file system. A block is an area of
 * the media and its size is set for a each specific media. The block size is
 * set when the file system is set up and needs to be matched for it to be 
 * read correctly.
 *
 * Blocks are managed as groups. A block group or "group" is part of the total
 * number of blocks being managed by the file system and exist to allow
 * resources to localised. A file in a directory will be allocated blocks in
 * the same group as the directory, and the blocks for the file will also be
 * allocated in the same group.
 *
 * A group consist of a block bitmap, inodes and data blocks. The first block
 * of the file system will hold the superblock. The block bitmap is a
 * collection of blocks that hold a map of bits, one bit per block for each
 * block in the group. When a file system is mounted the block bitmaps are 
 * read and a summary bit map is made. The summary bitmap has a single bit for
 * 32 bits in the bitmap and is set when all 32 bits it maps to are set. This
 * speeds up the search for a free block by a factor of 32.
 */

/*
 *  COPYRIGHT (c) 2010 Chris Johns <chrisj@rtems.org>
 *
 *  The license and distribution terms for this file may be
 *  found in the file LICENSE in this distribution or at
 *  http://www.rtems.org/license/LICENSE.
 */

#if HAVE_CONFIG_H
#include "config.h"
#endif

#include <inttypes.h>
#include <string.h>

#include <rtems/rfs/rtems-rfs-block.h>
#include <rtems/rfs/rtems-rfs-data.h>
#include <rtems/rfs/rtems-rfs-group.h>
#include <rtems/rfs/rtems-rfs-inode.h>

void
rtems_rfs_block_get_bpos (rtems_rfs_file_system* fs,
                          rtems_rfs_pos          pos,
                          rtems_rfs_block_pos*   bpos)
{
  bpos->bno  = pos / rtems_rfs_fs_block_size (fs);
  bpos->boff = pos % rtems_rfs_fs_block_size (fs);
}

rtems_rfs_pos
rtems_rfs_block_get_pos (rtems_rfs_file_system* fs,
                         rtems_rfs_block_pos*   bpos)
{
  return (bpos->bno * rtems_rfs_fs_block_size (fs)) + bpos->boff;
}

void
rtems_rfs_block_get_block_size (rtems_rfs_file_system* fs,
                                rtems_rfs_pos          pos,
                                rtems_rfs_block_size*  size)
{
  if (pos == 0)
    rtems_rfs_block_set_size_zero (size);
  else
  {
    size->count  = pos / rtems_rfs_fs_block_size (fs) + 1;
    size->offset = pos % rtems_rfs_fs_block_size (fs);
  }
}

rtems_rfs_pos
rtems_rfs_block_get_size (rtems_rfs_file_system* fs,
                          rtems_rfs_block_size*  size)
{
  uint32_t offset;
  uint64_t block_size;
  if (size->count == 0)
    return 0;
  if (size->offset == 0)
    offset = rtems_rfs_fs_block_size (fs);
  else
    offset = size->offset;
  block_size = rtems_rfs_fs_block_size (fs);
  return (((uint64_t) (size->count - 1)) * block_size) + offset;
}

int
rtems_rfs_block_map_open (rtems_rfs_file_system*  fs,
                          rtems_rfs_inode_handle* inode,
                          rtems_rfs_block_map*    map)
{
  int b;
  int rc;

  /*
   * Set the count to 0 so at least find fails, then open the handle and make
   * sure the inode has been loaded into memory. If we did not load the inode
   * do not unload it. The caller may assume it is still loaded when we return.
   */

  map->dirty = false;
  map->inode = NULL;
  rtems_rfs_block_set_size_zero (&map->size);
  rtems_rfs_block_set_bpos_zero (&map->bpos);

  rc = rtems_rfs_buffer_handle_open (fs, &map->singly_buffer);
  if (rc > 0)
    return rc;
  rc = rtems_rfs_buffer_handle_open (fs, &map->doubly_buffer);
  if (rc > 0)
    return rc;

  rc = rtems_rfs_inode_load (fs, inode);
  if (rc > 0)
  {
    rtems_rfs_buffer_handle_close (fs, &map->singly_buffer);
    rtems_rfs_buffer_handle_close (fs, &map->doubly_buffer);
    return rc;
  }

  /*
   * Extract the block and block count data from the inode into the targets
   * byte order.
   */
  map->inode = inode;
  for (b = 0; b < RTEMS_RFS_INODE_BLOCKS; b++)
    map->blocks[b] = rtems_rfs_inode_get_block (inode, b);
  map->size.count = rtems_rfs_inode_get_block_count (inode);
  map->size.offset = rtems_rfs_inode_get_block_offset (inode);
  map->last_map_block = rtems_rfs_inode_get_last_map_block (inode);
  map->last_data_block = rtems_rfs_inode_get_last_data_block (inode);

  rc = rtems_rfs_inode_unload (fs, inode, false);

  return rc;
}

int
rtems_rfs_block_map_close (rtems_rfs_file_system* fs,
                           rtems_rfs_block_map*   map)
{
  int rc = 0;
  int brc;

  if (map->dirty && map->inode)
  {
    brc = rtems_rfs_inode_load (fs, map->inode);
    if (brc > 0)
      rc = brc;

    if (rc == 0)
    {
      int b;

      for (b = 0; b < RTEMS_RFS_INODE_BLOCKS; b++)
        rtems_rfs_inode_set_block (map->inode, b, map->blocks[b]);
      rtems_rfs_inode_set_block_count (map->inode, map->size.count);
      rtems_rfs_inode_set_block_offset (map->inode, map->size.offset);
      rtems_rfs_inode_set_last_map_block (map->inode, map->last_map_block);
      rtems_rfs_inode_set_last_data_block (map->inode, map->last_data_block);

      brc = rtems_rfs_inode_unload (fs, map->inode, true);
      if (brc > 0)
        rc = brc;

      map->dirty = false;
    }
  }

  map->inode = NULL;

  brc = rtems_rfs_buffer_handle_close (fs, &map->singly_buffer);
  if ((brc > 0) && (rc == 0))
    rc = brc;
  brc = rtems_rfs_buffer_handle_close (fs, &map->doubly_buffer);
  if ((brc > 0) && (rc == 0))
    rc = brc;
  return rc;
}

/**
 * Find a block indirectly held in a table of block numbers.
 *
 * @param fs The file system.
 * @param buffer The handle to access the block data by.
 * @param block The block number of the table of block numbers.
 * @param offset The offset in the table of the block number to return. This is
 *               a block number offset not a byte offset into the table.
 * @param result Pointer to the result of the search.
 * @return int The error number (errno). No error if 0.
 */
static int
rtems_rfs_block_find_indirect (rtems_rfs_file_system*   fs,
                               rtems_rfs_buffer_handle* buffer,
                               rtems_rfs_block_no       block,
                               int                      offset,
                               rtems_rfs_block_no*      result)
{
   int rc;

  /*
   * If the handle has a buffer and this request is a different block the current
   * buffer is released.
   */
  rc = rtems_rfs_buffer_handle_request (fs, buffer, block, true);
  if (rc > 0)
    return rc;

  *result = rtems_rfs_block_get_number (buffer, offset);
  if ((*result + 1) == 0)
    *result = 0;

  if (*result >= rtems_rfs_fs_blocks (fs))
  {
    if (rtems_rfs_trace (RTEMS_RFS_TRACE_BLOCK_FIND))
      printf ("rtems-rfs: block-find: invalid block in table:"
              " block=%" PRId32 ", indirect=%" PRId32 "/%d\n", *result, block, offset);
    *result = 0;
    rc = EIO;
  }

  return 0;
}

int
rtems_rfs_block_map_find (rtems_rfs_file_system* fs,
                          rtems_rfs_block_map*   map,
                          rtems_rfs_block_pos*   bpos,
                          rtems_rfs_block_no*    block)
{
  int rc = 0;

  *block = 0;

  /*
   * Range checking here makes the remaining logic simpler.
   */
  if (rtems_rfs_block_pos_block_past_end (bpos, &map->size))
    return ENXIO;

  /*
   * If the block position is the same and we have found the block just return it.
   */
  if ((bpos->bno == map->bpos.bno) && (map->bpos.block != 0))
  {
    *block = map->bpos.block;
  }
  else
  {
    /*
     * Determine the type of access we need to perform. If the number of blocks
     * is less than or equal to the number of slots in the inode the blocks are
     * directly accessed.
     */
    if (map->size.count <= RTEMS_RFS_INODE_BLOCKS)
    {
      *block = map->blocks[bpos->bno];
    }
    else
    {
      /*
       * The map is either singly or doubly indirect.
       */
      rtems_rfs_block_no direct;
      rtems_rfs_block_no singly;

      direct = bpos->bno % fs->blocks_per_block;
      singly = bpos->bno / fs->blocks_per_block;

      if (map->size.count <= fs->block_map_singly_blocks)
      {
        /*
         * This is a single indirect table of blocks anchored off a slot in the
         * inode.
         */
        rc = rtems_rfs_block_find_indirect (fs,
                                            &map->singly_buffer,
                                            map->blocks[singly],
                                            direct, block);
      }
      else
      {
        /*
         * The map is doubly indirect.
         */
        rtems_rfs_block_no doubly;

        doubly  = singly / fs->blocks_per_block;
        singly %= fs->blocks_per_block;

        if (map->size.count < fs->block_map_doubly_blocks)
        {
          rc = rtems_rfs_block_find_indirect (fs,
                                              &map->doubly_buffer,
                                              map->blocks[doubly],
                                              singly, &singly);
          if (rc == 0)
          {
            rc = rtems_rfs_block_find_indirect (fs,
                                                &map->singly_buffer,
                                                singly, direct, block);
          }
        }
        else
        {
          /*
           * This should never happen. Here so Joel can remove once his coverage
           * testing gets to the file systems.
           */
          rc = ENXIO;
        }
      }
    }
  }

  if (rc == 0)
  {
    rtems_rfs_block_copy_bpos (&map->bpos, bpos);
    map->bpos.block = *block;
  }

  return rc;
}

int
rtems_rfs_block_map_seek (rtems_rfs_file_system* fs,
                          rtems_rfs_block_map*   map,
                          rtems_rfs_pos_rel      offset,
                          rtems_rfs_block_no*    block)
{
  rtems_rfs_block_pos bpos;
  rtems_rfs_block_copy_bpos (&bpos, &map->bpos);
  rtems_rfs_block_add_pos (fs, offset, &bpos);
  return rtems_rfs_block_map_find (fs, map, &bpos, block);
}

int
rtems_rfs_block_map_next_block (rtems_rfs_file_system* fs,
                                rtems_rfs_block_map*   map,
                                rtems_rfs_block_no*    block)
{
  rtems_rfs_block_pos bpos;
  bpos.bno = map->bpos.bno + 1;
  bpos.boff = 0;
  bpos.block = 0;
  return rtems_rfs_block_map_find (fs, map, &bpos, block);
}

/**
 * Allocate an indirect block to a map.
 *
 * @param fs The file system data.
 * @param map The map the allocation is for.
 * @param buffer The buffer the indirect block is accessed by.
 * @param block The block number of the indirect block allocated.
 * @param upping True is upping the map to the next indirect level.
 * @return int The error number (errno). No error if 0.
 */
static int
rtems_rfs_block_map_indirect_alloc (rtems_rfs_file_system*   fs,
                                    rtems_rfs_block_map*     map,
                                    rtems_rfs_buffer_handle* buffer,
                                    rtems_rfs_block_no*      block,
                                    bool                     upping)
{
  rtems_rfs_bitmap_bit new_block;
  int                  rc;
  /*
   * Save the new block locally because upping can have *block pointing to the
   * slots which are cleared when upping.
   */
  rc = rtems_rfs_group_bitmap_alloc (fs, map->last_map_block, false, &new_block);
  if (rc > 0)
    return rc;
  rc = rtems_rfs_buffer_handle_request (fs, buffer, new_block, false);
  if (rc > 0)
  {
    rtems_rfs_group_bitmap_free (fs, false, new_block);
    return rc;
  }
  memset (rtems_rfs_buffer_data (buffer), 0xff, rtems_rfs_fs_block_size (fs));
  if (upping)
  {
    int b;
    if (rtems_rfs_trace (RTEMS_RFS_TRACE_BLOCK_MAP_GROW))
      printf ("rtems-rfs: block-map-grow: upping: block-count=%" PRId32 "\n",
              map->size.count);
    for (b = 0; b < RTEMS_RFS_INODE_BLOCKS; b++)
      rtems_rfs_block_set_number (buffer, b, map->blocks[b]);
    memset (map->blocks, 0, sizeof (map->blocks));
  }
  rtems_rfs_buffer_mark_dirty (buffer);
  *block = new_block;
  map->last_map_block = new_block;
  return 0;
}

int
rtems_rfs_block_map_grow (rtems_rfs_file_system* fs,
                          rtems_rfs_block_map*   map,
                          size_t                 blocks,
                          rtems_rfs_block_no*    new_block)
{
  int b;

  if (rtems_rfs_trace (RTEMS_RFS_TRACE_BLOCK_MAP_GROW))
    printf ("rtems-rfs: block-map-grow: entry: blocks=%zd count=%" PRIu32 "\n",
            blocks, map->size.count);

  if ((map->size.count + blocks) >= rtems_rfs_fs_max_block_map_blocks (fs))
    return EFBIG;

  /*
   * Allocate a block at a time. The buffer handles hold the blocks so adding
   * this way does not thrash the cache with lots of requests.
   */
  for (b = 0; b < blocks; b++)
  {
    rtems_rfs_bitmap_bit block;
    int                  rc;

    /*
     * Allocate the block. If an indirect block is needed and cannot be
     * allocated free this block.
     */

    rc = rtems_rfs_group_bitmap_alloc (fs, map->last_data_block,
                                       false, &block);
    if (rc > 0)
      return rc;

    if (map->size.count < RTEMS_RFS_INODE_BLOCKS)
      map->blocks[map->size.count] = block;
    else
    {
      /*
       * Single indirect access is occuring. It could still be doubly indirect.
       */
      rtems_rfs_block_no direct;
      rtems_rfs_block_no singly;

      direct = map->size.count % fs->blocks_per_block;
      singly = map->size.count / fs->blocks_per_block;

      if (map->size.count < fs->block_map_singly_blocks)
      {
        /*
         * Singly indirect tables are being used. Allocate a new block for a
         * mapping table if direct is 0 or we are moving up (upping). If upping
         * move the direct blocks into the table and if not this is the first
         * entry of a new block.
         */
        if ((direct == 0) ||
            ((singly == 0) && (direct == RTEMS_RFS_INODE_BLOCKS)))
        {
          /*
           * Upping is when we move from direct to singly indirect.
           */
          bool upping;
          upping = map->size.count == RTEMS_RFS_INODE_BLOCKS;
          rc = rtems_rfs_block_map_indirect_alloc (fs, map,
                                                   &map->singly_buffer,
                                                   &map->blocks[singly],
                                                   upping);
        }
        else
        {
          rc = rtems_rfs_buffer_handle_request (fs,  &map->singly_buffer,
                                                map->blocks[singly], true);
        }

        if (rc > 0)
        {
          rtems_rfs_group_bitmap_free (fs, false, block);
          return rc;
        }
      }
      else
      {
        /*
         * Doubly indirect tables are being used.
         */
        rtems_rfs_block_no doubly;
        rtems_rfs_block_no singly_block;

        doubly  = singly / fs->blocks_per_block;
        singly %= fs->blocks_per_block;

        /*
         * Allocate a new block for a singly indirect table if direct is 0 as
         * it is the first entry of a new block. We may also need to allocate a
         * doubly indirect block as well. Both always occur when direct is 0
         * and the doubly indirect block when singly is 0.
         */
        if (direct == 0)
        {
          rc = rtems_rfs_block_map_indirect_alloc (fs, map,
                                                   &map->singly_buffer,
                                                   &singly_block,
                                                   false);
          if (rc > 0)
          {
            rtems_rfs_group_bitmap_free (fs, false, block);
            return rc;
          }

          /*
           * Allocate a new block for a doubly indirect table if singly is 0 as
           * it is the first entry of a new singly indirect block.
           */
          if ((singly == 0) ||
              ((doubly == 0) && (singly == RTEMS_RFS_INODE_BLOCKS)))
          {
            bool upping;
            upping = map->size.count == fs->block_map_singly_blocks;
            rc = rtems_rfs_block_map_indirect_alloc (fs, map,
                                                     &map->doubly_buffer,
                                                     &map->blocks[doubly],
                                                     upping);
            if (rc > 0)
            {
              rtems_rfs_group_bitmap_free (fs, false, singly_block);
              rtems_rfs_group_bitmap_free (fs, false, block);
              return rc;
            }
          }
          else
          {
            rc = rtems_rfs_buffer_handle_request (fs, &map->doubly_buffer,
                                                  map->blocks[doubly], true);
            if (rc > 0)
            {
              rtems_rfs_group_bitmap_free (fs, false, singly_block);
              rtems_rfs_group_bitmap_free (fs, false, block);
              return rc;
            }
          }

          rtems_rfs_block_set_number (&map->doubly_buffer,
                                      singly,
                                      singly_block);
        }
        else
        {
          rc = rtems_rfs_buffer_handle_request (fs,
                                                &map->doubly_buffer,
                                                map->blocks[doubly],
                                                true);
          if (rc > 0)
          {
            rtems_rfs_group_bitmap_free (fs, false, block);
            return rc;
          }

          singly_block = rtems_rfs_block_get_number (&map->doubly_buffer,
                                                     singly);

          rc = rtems_rfs_buffer_handle_request (fs, &map->singly_buffer,
                                                singly_block, true);
          if (rc > 0)
          {
            rtems_rfs_group_bitmap_free (fs, false, block);
            return rc;
          }
        }
      }

      rtems_rfs_block_set_number (&map->singly_buffer, direct, block);
    }

    map->size.count++;
    map->size.offset = 0;

    if (b == 0)
      *new_block = block;
    map->last_data_block = block;
    map->dirty = true;
  }

  return 0;
}

/**
 * Shrink an indirect block.
 *
 * @param fs The file system data.
 * @param map The map the allocation is for.
 * @param buffer The buffer the indirect block is accessed by.
 * @param indirect The index index in the inode's block table.
 * @param index The index in the indirect table of the block.
 * @return int The error number (errno). No error if 0.
 */
static int
rtems_rfs_block_map_indirect_shrink (rtems_rfs_file_system*   fs,
                                     rtems_rfs_block_map*     map,
                                     rtems_rfs_buffer_handle* buffer,
                                     rtems_rfs_block_no       indirect,
                                     rtems_rfs_block_no       index)
{
  int rc = 0;

  /*
   * If this is the first block in the indirect table (index == 0), ie the last
   * block to be freed and the indirect block is now also free, or we have only
   * one indirect table and we can fit the remaining blocks into the inode,
   * then either move to the next indirect block or move the remaining blocks
   * into the inode and free the indirect table's block.
   */
  if ((index == 0) ||
      ((indirect == 0) && (index == RTEMS_RFS_INODE_BLOCKS)))
  {
    rtems_rfs_block_no block_to_free = map->blocks[indirect];

    if ((indirect == 0) && (index == RTEMS_RFS_INODE_BLOCKS))
    {
      /*
       * Move to direct inode access.
       */
      int b;
      for (b = 0; b < RTEMS_RFS_INODE_BLOCKS; b++)
        map->blocks[b] = rtems_rfs_block_get_number (buffer, b);
    }
    else
    {
      /*
       * One less singly indirect block in the inode.
       */
      map->blocks[indirect] = 0;
    }

    rc = rtems_rfs_group_bitmap_free (fs, false, block_to_free);
    if (rc > 0)
      return rc;

    map->last_map_block = block_to_free;
  }

  return rc;
}

int
rtems_rfs_block_map_shrink (rtems_rfs_file_system* fs,
                            rtems_rfs_block_map*   map,
                            size_t                 blocks)
{
  if (rtems_rfs_trace (RTEMS_RFS_TRACE_BLOCK_MAP_SHRINK))
    printf ("rtems-rfs: block-map-shrink: entry: blocks=%zd count=%" PRIu32 "\n",
            blocks, map->size.count);

  if (map->size.count == 0)
    return 0;

  if (blocks > map->size.count)
    blocks = map->size.count;

  while (blocks)
  {
    rtems_rfs_block_no block;
    rtems_rfs_block_no block_to_free;
    int                rc;

    block = map->size.count - 1;

    if (block < RTEMS_RFS_INODE_BLOCKS)
    {
      /*
       * We have less than RTEMS_RFS_INODE_BLOCKS so they are held in the
       * inode.
       */
      block_to_free = map->blocks[block];
      map->blocks[block] = 0;
    }
    else
    {
      /*
       * Single indirect access is occuring. It could still be doubly indirect.
       *
       * The 'direct' variable is the offset in to the indirect table of
       * blocks, and 'singly' is the inode block index of the singly indirect
       * table of block numbers.
       */
      rtems_rfs_block_no direct;
      rtems_rfs_block_no singly;

      direct = block % fs->blocks_per_block;
      singly = block / fs->blocks_per_block;

      if (block < fs->block_map_singly_blocks)
      {
        /*
         * Request the indirect block and then obtain the block number from the
         * indirect block.
         */
        rc = rtems_rfs_buffer_handle_request (fs, &map->singly_buffer,
                                              map->blocks[singly], true);
        if (rc > 0)
          return rc;

        block_to_free = rtems_rfs_block_get_number (&map->singly_buffer,
                                                    direct);

        rc = rtems_rfs_block_map_indirect_shrink (fs, map, &map->singly_buffer,
                                                  singly, direct);
        if (rc)
          return rc;
      }
      else if (block < fs->block_map_doubly_blocks)
      {
        /*
         * Doubly indirect tables are being used. The 'doubly' variable is the
         * index in to the inode's block table and points to a singly indirect
         * table of block numbers. The 'doubly_singly' variable is the index
         * into the doubly indirect table pointing to the singly indirect table
         * of block numbers that form the map. This is used later to determine
         * if the current doubly indirect table needs to be freed. The 'direct'
         * value is still valid for doubly indirect tables.
         */
        rtems_rfs_block_no doubly;
        rtems_rfs_block_no doubly_singly;

        doubly        = singly / fs->blocks_per_block;
        doubly_singly = singly % fs->blocks_per_block;

        rc = rtems_rfs_buffer_handle_request (fs, &map->doubly_buffer,
                                              map->blocks[doubly], true);
        if (rc > 0)
          return rc;

        singly = rtems_rfs_block_get_number (&map->doubly_buffer,
                                             doubly_singly);

        /*
         * Read the singly indirect table and get the block number.
         */
        rc = rtems_rfs_buffer_handle_request (fs, &map->singly_buffer,
                                              singly, true);
        if (rc > 0)
          return rc;

        block_to_free = rtems_rfs_block_get_number (&map->singly_buffer,
                                                    direct);

        if (direct == 0)
        {
          rc = rtems_rfs_group_bitmap_free (fs, false, singly);
          if (rc > 0)
            return rc;

          map->last_map_block = singly;

          rc = rtems_rfs_block_map_indirect_shrink (fs, map, &map->doubly_buffer,
                                                    doubly, doubly_singly);
          if (rc)
            return rc;
        }
      }
      else
      {
        rc = EIO;
        break;
      }
    }
    rc = rtems_rfs_group_bitmap_free (fs, false, block_to_free);
    if (rc > 0)
      return rc;
    map->size.count--;
    map->size.offset = 0;
    map->last_data_block = block_to_free;
    map->dirty = true;
    blocks--;
  }

  if (map->size.count == 0)
  {
    map->last_map_block = 0;
    map->last_data_block = 0;
  }

  /*
   * Keep the position inside the map.
   */
  if (rtems_rfs_block_pos_past_end (&map->bpos, &map->size))
    rtems_rfs_block_size_get_bpos (&map->size, &map->bpos);

  return 0;
}

int
rtems_rfs_block_map_free_all (rtems_rfs_file_system* fs,
                              rtems_rfs_block_map*   map)
{
  return rtems_rfs_block_map_shrink (fs, map, map->size.count);
}