Logo Search packages:      
Sourcecode: jfsutils version File versions  Download package

diskmap.c

/*
 *   Copyright (c) International Business Machines Corp., 2000-2002
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
#include <config.h>
#include "jfs_types.h"
#include "jfs_dmap.h"
#include "diskmap.h"

/*
 * budtab[]
 *
 * used to determine the maximum free string in a character
 * of a wmap word.  the actual bit values of the character
 * serve as the index into this array and the value of the
 * array at that index is the max free string.
 *
 */
static int8_t budtab[256] = {
      3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
      2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
};

/*
 * NAME: ujfs_maxbuddy
 *
 * FUNCTION: Determines the maximum string of free blocks within a word of the
 *    wmap or pmap consistent with binary buddy.
 *
 * PRE CONDITIONS:
 *
 * POST CONDITIONS:
 *
 * PARAMETERS:
 *    cp    - Pointer to wmap or pmap word.
 *
 * NOTES:
 *
 * DATA STRUCTURES:
 *
 * RETURNS: Maximum string of free blocks within word.
 */
int8_t ujfs_maxbuddy(unsigned char *cp)
{
      /*
       * Check if the wmap or pmap word is all free. If so, the free buddy size is
       * BUDMIN.
       */
      if (*((uint32_t *) cp) == 0) {
            return (BUDMIN);
      }

      /*
       * Check if the wmap or pmap word is half free. If so, the free buddy size
       * is BUDMIN-1.
       */
      if (*((uint16_t *) cp) == 0 || *((uint16_t *) cp + 1) == 0) {
            return (BUDMIN - 1);
      }

      /*
       * Not all free or half free. Determine the free buddy size through table
       * lookup using quarters of the wmap or pmap word.
       */
      return (MAX(MAX(budtab[*cp], budtab[*(cp + 1)]),
                MAX(budtab[*(cp + 2)], budtab[*(cp + 3)])));
}

/*
 * NAME: ujfs_adjtree
 *
 * FUNCTION: Calculate the tree of a dmap or dmapctl.
 *
 * PRE CONDITIONS:
 *
 * POST CONDITIONS:
 *
 * PARAMETERS:
 *    cp    - Pointer to the top of the tree
 *    l2leaves- Number of leaf nodes as a power of 2
 *    l2min - Number of disk blocks actually covered by a leaf of the tree;
 *            specified as a power of 2
 *
 * NOTES: This routine first works against the leaves of the tree to calculate
 *    the maximum free string for leaf buddys.  Once this is accomplished the
 *    values of the leaf nodes are bubbled up the tree.
 *
 * DATA STRUCTURES:
 *
 * RETURNS:
 */
int8_t ujfs_adjtree(int8_t * treep, int32_t l2leaves, int32_t l2min)
{
      int32_t nleaves, leaf_index, l2max, nextb, bsize, index;
      int32_t l2free, leaf, num_this_level, nextp;
      int8_t *cp0, *cp1, *cp = treep;

      /*
       * Determine the number of leaves of the tree and the
       * index of the first leaf.
       * Note: I don't know why the leaf_index calculation works, but it does.
       */
      nleaves = (1 << l2leaves);
      leaf_index = (nleaves - 1) / 3;

      /*
       * Determine the maximum free string possible for the leaves.
       */
      l2max = l2min + l2leaves;

      /*
       * Try to combine buddies starting with a buddy size of 1 (i.e. two leaves).
       * At a buddy size of 1 two buddy leaves can be combined if both buddies
       * have a maximum free of l2min; the combination will result in the
       * left-most buddy leaf having a maximum free of l2min+1.  After processing
       * all buddies for a certain size, process buddies at the next higher buddy
       * size (i.e. current size * 2) and the next maximum free
       * (current free + 1).  This continues until the maximum possible buddy
       * combination yields maximum free.
       */
      for (l2free = l2min, bsize = 1; l2free < l2max; l2free++, bsize = nextb) {
            nextb = bsize << 1;

            for (cp0 = cp + leaf_index, index = 0; index < nleaves;
                 index += nextb, cp0 += nextb) {
                  if (*cp0 == l2free && *(cp0 + bsize) == l2free) {
                        *cp0 = l2free + 1;
                        *(cp0 + bsize) = -1;
                  }
            }
      }

      /*
       * With the leaves reflecting maximum free values bubble this information up
       * the tree.  Starting at the leaf node level, the four nodes described by
       * the higher level parent node are compared for a maximum free and this
       * maximum becomes the value of the parent node.  All lower level nodes are
       * processed in this fashion then we move up to the next level (parent
       * becomes a lower level node) and continue the process for that level.
       */
      for (leaf = leaf_index, num_this_level = nleaves >> 2; num_this_level > 0;
           num_this_level >>= 2, leaf = nextp) {
            nextp = (leaf - 1) >> 2;

            /*
             * Process all lower level nodes at this level setting the value of the
             * parent node as the maximum of the four lower level nodes.
             */
            for (cp0 = cp + leaf, cp1 = cp + nextp, index = 0;
                 index < num_this_level; index++, cp0 += 4, cp1++) {
                  *cp1 = TREEMAX(cp0);
            }
      }

      return (*cp);
}

/*
 * NAME: ujfs_complete_dmap
 *
 * FUNCTION: Fill in rest of dmap fields from wmap/pmap already initialized.
 *
 * PARAMETERS:
 *    dmap_page   - dmap to complete
 *    blkno       - starting block number for this dmap
 *    treemax           - will be filled in with max free for this dmap
 *
 * RETURNS: NONE
 */
void ujfs_complete_dmap(struct dmap *dmap_page, int64_t blkno, int8_t *treemax)
{
      struct dmaptree *tp;
      int8_t *cp;
      int32_t index;

      dmap_page->start = blkno;

      tp = &dmap_page->tree;
      tp->height = 4;
      tp->leafidx = LEAFIND;
      tp->nleafs = LPERDMAP;
      tp->l2nleafs = L2LPERDMAP;
      tp->budmin = BUDMIN;

      /*
       * Pick up the pointer to the first leaf of the dmap tree.
       */
      cp = tp->stree + tp->leafidx;

      /*
       * Set the initial state for the leaves of the dmap tree.  They will reflect
       * the current allocation state of the wmap words.
       */
      for (index = 0; index < LPERDMAP; index++) {
            *(cp + index) = ujfs_maxbuddy((unsigned char *) &dmap_page->wmap[index]);
      }

      /*
       * With the leaves of the dmap initialized adjust (initialize) the dmap's
       * tree.
       */
      *treemax = ujfs_adjtree(tp->stree, L2LPERDMAP, BUDMIN);
}

/*
 * NAME: ujfs_idmap_page
 *
 * FUNCTION: Initialize one dmap page
 *
 * POST CONDITIONS: Blocks which don't actually exist in the aggregate will be
 *    marked as allocated in the dmap page.  The total number of blocks will
 *    only account for the actually existing blocks.
 *
 * PARAMETERS:
 *    map_page    - pointer to page of map
 *    nblocks           - number of blocks this page
 *
 * RETURNS: NONE
 */
void ujfs_idmap_page(struct dmap *map_page, uint32_t nblocks)
{
      uint32_t index, nwords, bit;

      map_page->nblocks = map_page->nfree = nblocks;

      /*
       * Partial dmap page?
       * If there are not enough blocks to cover an entire dmap page the ones
       * which represent blocks which don't exist will be marked as allocated.
       *
       * nwords will indicate the first word beyond the end of existing blocks
       * bit will indicate if this block does not fall on a 32-bit boundary
       */
      nwords = nblocks / DBWORD;
      bit = nblocks % DBWORD;

      if (bit) {
            /*
             * Need to mark a partial word allocated
             */
            map_page->wmap[nwords] = map_page->pmap[nwords] = ONES >> bit;
            nwords++;
      }

      /*
       * Set the rest of the words in the page to ONES.
       */
      for (index = nwords; index < LPERDMAP; index++) {
            map_page->pmap[index] = map_page->wmap[index] = ONES;
      }
}

/*
 * NAME: ujfs_getagl2size
 *
 * FUNCTION: Determine log2(allocation group size) based on size of aggregate
 *
 * PARAMETERS:
 *    size        - Number of blocks in aggregate
 *    aggr_block_size   - Aggregate block size
 *
 * RETURNS: log2(allocation group size) in aggregate blocks
 */
int32_t ujfs_getagl2size(int64_t size, int32_t aggr_block_size)
{
      int64_t sz;
      int64_t m;
      int32_t l2sz;

      if (size < BPERDMAP * MAXAG) {
            return (L2BPERDMAP);
      }

      m = ((uint64_t) 1 << (64 - 1));
      for (l2sz = 64; l2sz >= 0; l2sz--, m >>= 1) {
            if (m & size) {
                  break;
            }
      }

      sz = (int64_t) 1 << l2sz;
      if (sz < size) {
            l2sz += 1;
      }

      return (l2sz - L2MAXAG);
}

Generated by  Doxygen 1.6.0   Back to index