jfs_dmap.c

linux 内核源代码

 *		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 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
 *		the dmaps themselves containing the desired contiguous free
 *		space or starting a contiguous free space of desired size
 *		that is made up of the blocks of one or more dmaps. these
 *		calls should not fail due to insufficent resources.
 *
 *		this routine is called in some cases where it is not known
 *		whether it will fail due to insufficient resources.  more
 *		specifically, this occurs when allocating from an allocation
 *		group whose size is equal to the number of blocks per dmap.
 *		in this case, the dmap control pages are not examined prior
 *		to calling this routine (to save pathlength) and the call
 *		might fail.
 *
 *		for a request size that fits within a dmap, this routine relies
 *		upon the dmap's dmtree to find the requested contiguous free
 *		space.  for request sizes that are larger than a dmap, the
 *		requested free space will start at the first block of the
 *		first dmap (i.e. blkno).
 *
 * PARAMETERS:
 *	bmp	-  pointer to bmap descriptor
 *	nblocks	 -  actual number of contiguous free blocks to allocate.
 *	l2nb	 -  log2 number of contiguous free blocks to allocate.
 *	blkno	 -  starting block number of the dmap to start the allocation
 *		    from.
 *	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
dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno, s64 * results)
{
	int rc, nb;
	s64 b, lblkno, n;
	struct metapage *mp;
	struct dmap *dp;

	/* check if the allocation request is confined to a single dmap.
	 */
	if (l2nb <= L2BPERDMAP) {
		/* get the buffer for the dmap.
		 */
		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
		if (mp == NULL)
			return -EIO;
		dp = (struct dmap *) mp->data;

		/* try to allocate the blocks.
		 */
		rc = dbAllocDmapLev(bmp, dp, (int) nblocks, l2nb, results);
		if (rc == 0)
			mark_metapage_dirty(mp);

		release_metapage(mp);

		return (rc);
	}

	/* allocation request involving multiple dmaps. it must start on
	 * a dmap boundary.
	 */
	assert((blkno & (BPERDMAP - 1)) == 0);

	/* allocate the blocks dmap by dmap.
	 */
	for (n = nblocks, b = blkno; n > 0; n -= nb, b += nb) {
		/* get the buffer for the dmap.
		 */
		lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
		if (mp == NULL) {
			rc = -EIO;
			goto backout;
		}
		dp = (struct dmap *) mp->data;

		/* the dmap better be all free.
		 */
		if (dp->tree.stree[ROOT] != L2BPERDMAP) {
			release_metapage(mp);
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbAllocCtl: the dmap is not all free");
			rc = -EIO;
			goto backout;