jfs_dmap.c

jfs-2.4-1.1.7.tar.gz jfs 2.4－1.1.7 源码

	int word, lword, rc;
	s8 *leaf;

	if (dp->tree.leafidx != cpu_to_le32(LEAFIND)) {
		jfs_error(bmp->db_ipbmap->i_sb,
			  "dbAllocNear: Corrupt dmap page");
		return -EIO;
	}

	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);

	/* determine the word within the dmap that holds the hint
	 * (i.e. blkno).  also, determine the last word in the dmap
	 * that we'll include in our examination.
	 */
	word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;
	lword = min(word + 4, LPERDMAP);

	/* examine the leaves for sufficient free space.
	 */
	for (; word < lword; word++) {
		/* does the leaf describe sufficient free space ?
		 */
		if (leaf[word] < l2nb)
			continue;

		/* determine the block number within the file system
		 * of the first block described by this dmap word.
		 */
		blkno = le64_to_cpu(dp->start) + (word << L2DBWORD);

		/* if not all bits of the dmap word are free, get the
		 * starting bit number within the dmap word of the required
		 * string of free bits and adjust the block number with the
		 * value.
		 */
		if (leaf[word] < BUDMIN)
			blkno +=
			    dbFindBits(le32_to_cpu(dp->wmap[word]), l2nb);

		/* allocate the blocks.
		 */
		if ((rc = dbAllocDmap(bmp, dp, blkno, nblocks)) == 0)
			*results = blkno;

		return (rc);
	}

	return -ENOSPC;
}


/*
 * NAME:	dbAllocAG()
 *
 * FUNCTION:    attempt to allocate the specified number of contiguous
 *		free blocks within the specified allocation group.
 *
 *		unless the allocation group size is equal to the number
 *		of blocks per dmap, the dmap control pages will be used to
 *		find the required free space, if available.  we start the
 *		search at the highest dmap control page level which
 *		distinctly describes the allocation group's free space
 *		(i.e. the highest level at which the allocation group's
 *		free space is not mixed in with that of any other group).
 *		in addition, we start the search within this level at a
 *		height of the dmapctl dmtree at which the nodes distinctly
 *		describe the allocation group's free space.  at this height,
 *		the allocation group's free space may be represented by 1
 *		or two sub-trees, depending on the allocation group size.
 *		we search the top nodes of these subtrees left to right for
 *		sufficient free space.  if sufficient free space is found,
 *		the subtree is searched to find the leftmost leaf that 
 *		has free space.  once we have made it to the leaf, we
 *		move the search to the next lower level dmap control page
 *		corresponding to this leaf.  we continue down the dmap control
 *		pages until we find the dmap that contains or starts the
 *		sufficient free space and we allocate at this dmap.
 *
 *		if the allocation group size is equal to the dmap size,
 *		we'll start at the dmap corresponding to the allocation
 *		group and attempt the allocation at this level.
 *
 *		the dmap control page search is also not performed if the
 *		allocation group is completely free and we go to the first
 *		dmap of the allocation group to do the allocation.  this is
 *		done because the allocation group may be part (not the first
 *		part) of a larger binary buddy system, causing the dmap
 *		control pages to indicate no free space (NOFREE) within
 *		the allocation group.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *	agno	- allocation group number.
 *      nblocks	-  actual number of contiguous free blocks desired.
 *      l2nb	-  log2 number of contiguous free blocks desired.
 *      results	-  on successful return, set to the starting block number
 *		   of the newly allocated range.
 *
 * RETURN VALUES:
 *      0	- success
 *      -ENOSPC	- insufficient disk resources
 *      -EIO	- i/o error
 *
 * note: IWRITE_LOCK(ipmap) held on entry/exit;
 */
static int
dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb, s64 * results)
{
	struct metapage *mp;
	struct dmapctl *dcp;
	int rc, ti, i, k, m, n, agperlev;
	s64 blkno, lblkno;
	int budmin;

	/* allocation request should not be for more than the
	 * allocation group size.
	 */
	if (l2nb > bmp->db_agl2size) {
		jfs_error(bmp->db_ipbmap->i_sb,
			  "dbAllocAG: allocation request is larger than the "
			  "allocation group size");
		return -EIO;
	}

	/* determine the starting block number of the allocation
	 * group.
	 */
	blkno = (s64) agno << bmp->db_agl2size;

	/* check if the allocation group size is the minimum allocation
	 * group size or if the allocation group is completely free. if
	 * the allocation group size is the minimum size of BPERDMAP (i.e.
	 * 1 dmap), there is no need to search the dmap control page (below)
	 * that fully describes the allocation group since the allocation
	 * group is already fully described by a dmap.  in this case, we
	 * just call dbAllocCtl() to search the dmap tree and allocate the
	 * required space if available.  
	 *
	 * if the allocation group is completely free, dbAllocCtl() is
	 * also called to allocate the required space.  this is done for
	 * two reasons.  first, it makes no sense searching the dmap control
	 * pages for free space when we know that free space exists.  second,
	 * the dmap control pages may indicate that the allocation group
	 * has no free space if the allocation group is part (not the first
	 * part) of a larger binary buddy system.
	 */
	if (bmp->db_agsize == BPERDMAP
	    || bmp->db_agfree[agno] == bmp->db_agsize) {
		rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
		if ((rc == -ENOSPC) &&
		    (bmp->db_agfree[agno] == bmp->db_agsize)) {
			printk(KERN_ERR "blkno = %Lx, blocks = %Lx\n",
			       (unsigned long long) blkno,
			       (unsigned long long) nblocks);
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbAllocAG: dbAllocCtl failed in free AG");
		}
		return (rc);
	}

	/* the buffer for the dmap control page that fully describes the
	 * allocation group.
	 */
	lblkno = BLKTOCTL(blkno, bmp->db_l2nbperpage, bmp->db_aglevel);
	mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
	if (mp == NULL)
		return -EIO;
	dcp = (struct dmapctl *) mp->data;
	budmin = dcp->budmin;

	if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
		jfs_error(bmp->db_ipbmap->i_sb,
			  "dbAllocAG: Corrupt dmapctl page");
		release_metapage(mp);
		return -EIO;
	}

	/* search the subtree(s) of the dmap control page that describes
	 * the allocation group, looking for sufficient free space.  to begin,
	 * determine how many allocation groups are represented in a dmap
	 * control page at the control page level (i.e. L0, L1, L2) that
	 * fully describes an allocation group. next, determine the starting
	 * tree index of this allocation group within the control page.
	 */
	agperlev =
	    (1 << (L2LPERCTL - (bmp->db_agheigth << 1))) / bmp->db_agwidth;
	ti = bmp->db_agstart + bmp->db_agwidth * (agno & (agperlev - 1));

	/* dmap control page trees fan-out by 4 and a single allocation 
	 * group may be described by 1 or 2 subtrees within the ag level
	 * dmap control page, depending upon the ag size. examine the ag's
	 * subtrees for sufficient free space, starting with the leftmost
	 * subtree.
	 */
	for (i = 0; i < bmp->db_agwidth; i++, ti++) {
		/* is there sufficient free space ?
		 */
		if (l2nb > dcp->stree[ti])
			continue;

		/* sufficient free space found in a subtree. now search down
		 * the subtree to find the leftmost leaf that describes this
		 * free space.
		 */
		for (k = bmp->db_agheigth; k > 0; k--) {
			for (n = 0, m = (ti << 2) + 1; n < 4; n++) {
				if (l2nb <= dcp->stree[m + n]) {
					ti = m + n;
					break;
				}
			}
			if (n == 4) {
				jfs_error(bmp->db_ipbmap->i_sb,
					  "dbAllocAG: failed descending stree");
				release_metapage(mp);
				return -EIO;
			}
		}

		/* determine the block number within the file system
		 * that corresponds to this leaf.
		 */
		if (bmp->db_aglevel == 2)
			blkno = 0;
		else if (bmp->db_aglevel == 1)
			blkno &= ~(MAXL1SIZE - 1);
		else		/* bmp->db_aglevel == 0 */
			blkno &= ~(MAXL0SIZE - 1);

		blkno +=
		    ((s64) (ti - le32_to_cpu(dcp->leafidx))) << budmin;

		/* release the buffer in preparation for going down
		 * the next level of dmap control pages.
		 */
		release_metapage(mp);

		/* check if we need to continue to search down the lower
		 * level dmap control pages.  we need to if the number of
		 * blocks required is less than maximum number of blocks
		 * described at the next lower level.
		 */
		if (l2nb < budmin) {

			/* search the lower level dmap control pages to get
			 * the starting block number of the the dmap that
			 * contains or starts off the free space.
			 */
			if ((rc =
			     dbFindCtl(bmp, l2nb, bmp->db_aglevel - 1,
				       &blkno))) {
				if (rc == -ENOSPC) {
					jfs_error(bmp->db_ipbmap->i_sb,
						  "dbAllocAG: control page "
						  "inconsistent");
					return -EIO;
				}
				return (rc);
			}
		}

		/* allocate the blocks.
		 */
		rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
		if (rc == -ENOSPC) {
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbAllocAG: unable to allocate blocks");
			rc = -EIO;
		}
		return (rc);
	}

	/* no space in the allocation group.  release the buffer and
	 * return -ENOSPC.
	 */
	release_metapage(mp);

	return -ENOSPC;
}


/*
 * NAME:	dbAllocAny()
 *
 * FUNCTION:    attempt to allocate the specified number of contiguous
 *		free blocks anywhere in the file system.
 *
 *		dbAllocAny() attempts to find the sufficient free space by
 *		searching down the dmap control pages, starting with the
 *		highest level (i.e. L0, L1, L2) control page.  if free space
 *		large enough to satisfy the desired free space is found, the
 *		desired free space is allocated.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *      nblocks	 -  actual number of contiguous free blocks desired.
 *      l2nb	 -  log2 number of contiguous free blocks desired.
 *      results	-  on successful return, set to the starting block number
 *		   of the newly allocated range.
 *
 * RETURN VALUES:
 *      0	- success
 *      -ENOSPC	- insufficient disk resources
 *      -EIO	- i/o error
 *
 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
 */
static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results)
{
	int rc;
	s64 blkno = 0;

	/* starting with the top level dmap control page, search
	 * down the dmap control levels for sufficient free space.
	 * if free space is found, dbFindCtl() returns the starting
	 * block number of the dmap that contains or starts off the
	 * range of free space.
	 */
	if ((rc = dbFindCtl(bmp, l2nb, bmp->db_maxlevel, &blkno)))
		return (rc);

	/* allocate the blocks.
	 */
	rc = dbAllocCtl(bmp, nblocks, l2nb, blkno, results);
	if (rc == -ENOSPC) {
		jfs_error(bmp->db_ipbmap->i_sb,
			  "dbAllocAny: unable to allocate blocks");
		return -EIO;
	}
	return (rc);
}


/*
 * NAME:	dbFindCtl()
 *
 * FUNCTION:    starting at a specified dmap control page level and block
 *		number, search down the dmap control levels for a range of
 *	        contiguous free blocks large enough to satisfy an allocation
 *		request for the specified number of free blocks.
 *
 *		if sufficient contiguous free blocks are found, this routine
 *		returns the starting block number within a dmap page that
 *		contains or starts a range of contiqious free blocks that
 *		is sufficient in size.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *      level	-  starting dmap control page level.
 *      l2nb	-  log2 number of contiguous free blocks desired.
 *      *blkno	-  on entry, starting block number for conducting the search.
 *		   on successful return, the first block within a dmap page
 *		   that contains or starts a range of contiguous free blocks.
 *
 * RETURN VALUES:
 *      0	- success
 *      -ENOSPC	- insufficient disk resources
 *      -EIO	- i/o error
 *
 * serialization: IWRITE_LOCK(ipbmap) held on entry/exit;
 */
static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno)
{
	int rc, leafidx, lev;
	s64 b, lblkno;
	struct dmapctl *dcp;
	int budmin;
	struct metapage *mp;

	/* starting at the specified dmap control page level and block
	 * number, search down the dmap control levels for the starting
	 * block number of a dmap page that contains or starts off 
	 * sufficient free blocks.
	 */
	for (lev = level, b = *blkno; lev >= 0; lev--) {
		/* get the buffer of the dmap control page for the block
		 * number and level (i.e. L0, L1, L2).
		 */
		lblkno = BLKTOCTL(b, bmp->db_l2nbperpage, lev);
		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
		if (mp == NULL)
			return -EIO;
		dcp = (struct dmapctl *) mp->data;
		budmin = dcp->budmin;

		if (dcp->leafidx != cpu_to_le32(CTLLEAFIND)) {
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbFindCtl: Corrupt dmapctl page");
			release_metapage(mp);
			return -EIO;
		}

		/* search the tree within the dmap control page for
		 * sufficent free space.  if sufficient free space is found,
		 * dbFindLeaf() returns the index of the leaf at which
		 * free space was found.
		 */
		rc = dbFindLeaf((dmtree_t *) dcp, l2nb, &leafidx);

		/* release the buffer.
		 */
		release_metapage(mp);

		/* space found ?
		 */
		if (rc) {
			if (lev != level) {
				jfs_error(bmp->db_ipbmap->i_sb,
					  "dbFindCtl: dmap inconsistent");
				return -EIO;
			}
			return -ENOSPC;
		}

		/* adjust the block number to reflect the location within
		 * the dmap control page (i.e. the leaf) at which free 
		 * space was found.
		 */
		b += (((s64) leafidx) << budmin);

		/* we stop the search at this dmap control page level if
		 * the number of blocks required is greater than or equal
		 * to the maximum number of blocks described at the next
		 * (lower) level.
		 */
		if (l2nb >= budmin)
			break;
	}

	*blkno = b;
	return (0);
}


/*
 * NAME:	dbAllocCtl()
 *
 * FUNCTION:    attempt to allocate a specified number of contiguous
 *		blocks starting within a specific dmap.  
 *		
 *		this routine is called by higher level routines that search
 *		the dmap control pages above the actual dmaps for contiguous
 *		free space.  the result of successful searches by these
 * 		routines are the starting block numbers within dmaps, with