jfs_dmap.c

linux 内核源代码

	/*
	 * validate extent request:
	 *
	 * note: defragfs policy:
	 *  max 64 blocks will be moved.
	 *  allocation request size must be satisfied from a single dmap.
	 */
	if (nblocks <= 0 || nblocks > BPERDMAP || blkno >= bmp->db_mapsize) {
		IREAD_UNLOCK(ipbmap);
		return -EINVAL;
	}

	if (nblocks > ((s64) 1 << bmp->db_maxfreebud)) {
		/* the free space is no longer available */
		IREAD_UNLOCK(ipbmap);
		return -ENOSPC;
	}

	/* read in the dmap covering the extent */
	lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
	mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
	if (mp == NULL) {
		IREAD_UNLOCK(ipbmap);
		return -EIO;
	}
	dp = (struct dmap *) mp->data;

	/* try to allocate the requested extent */
	rc = dbAllocNext(bmp, dp, blkno, nblocks);

	IREAD_UNLOCK(ipbmap);

	if (rc == 0)
		mark_metapage_dirty(mp);

	release_metapage(mp);

	return (rc);
}
#endif /* _NOTYET */

/*
 * NAME:	dbReAlloc()
 *
 * FUNCTION:	attempt to extend a current allocation by a specified
 *		number of blocks.
 *
 *		this routine attempts to satisfy the allocation request
 *		by first trying to extend the existing allocation in
 *		place by allocating the additional blocks as the blocks
 *		immediately following the current allocation.  if these
 *		blocks are not available, this routine will attempt to
 *		allocate a new set of contiguous blocks large enough
 *		to cover the existing allocation plus the additional
 *		number of blocks required.
 *
 * PARAMETERS:
 *	ip	    -  pointer to in-core inode requiring allocation.
 *	blkno	    -  starting block of the current allocation.
 *	nblocks	    -  number of contiguous blocks within the current
 *		       allocation.
 *	addnblocks  -  number of blocks to add to the allocation.
 *	results	-      on successful return, set to the starting block number
 *		       of the existing allocation if the existing allocation
 *		       was extended in place or to a newly allocated contiguous
 *		       range if the existing allocation could not be extended
 *		       in place.
 *
 * RETURN VALUES:
 *	0	- success
 *	-ENOSPC	- insufficient disk resources
 *	-EIO	- i/o error
 */
int
dbReAlloc(struct inode *ip,
	  s64 blkno, s64 nblocks, s64 addnblocks, s64 * results)
{
	int rc;

	/* try to extend the allocation in place.
	 */
	if ((rc = dbExtend(ip, blkno, nblocks, addnblocks)) == 0) {
		*results = blkno;
		return (0);
	} else {
		if (rc != -ENOSPC)
			return (rc);
	}

	/* could not extend the allocation in place, so allocate a
	 * new set of blocks for the entire request (i.e. try to get
	 * a range of contiguous blocks large enough to cover the
	 * existing allocation plus the additional blocks.)
	 */
	return (dbAlloc
		(ip, blkno + nblocks - 1, addnblocks + nblocks, results));
}


/*
 * NAME:	dbExtend()
 *
 * FUNCTION:	attempt to extend a current allocation by a specified
 *		number of blocks.
 *
 *		this routine attempts to satisfy the allocation request
 *		by first trying to extend the existing allocation in
 *		place by allocating the additional blocks as the blocks
 *		immediately following the current allocation.
 *
 * PARAMETERS:
 *	ip	    -  pointer to in-core inode requiring allocation.
 *	blkno	    -  starting block of the current allocation.
 *	nblocks	    -  number of contiguous blocks within the current
 *		       allocation.
 *	addnblocks  -  number of blocks to add to the allocation.
 *
 * RETURN VALUES:
 *	0	- success
 *	-ENOSPC	- insufficient disk resources
 *	-EIO	- i/o error
 */
static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks)
{
	struct jfs_sb_info *sbi = JFS_SBI(ip->i_sb);
	s64 lblkno, lastblkno, extblkno;
	uint rel_block;
	struct metapage *mp;
	struct dmap *dp;
	int rc;
	struct inode *ipbmap = sbi->ipbmap;
	struct bmap *bmp;

	/*
	 * We don't want a non-aligned extent to cross a page boundary
	 */
	if (((rel_block = blkno & (sbi->nbperpage - 1))) &&
	    (rel_block + nblocks + addnblocks > sbi->nbperpage))
		return -ENOSPC;

	/* get the last block of the current allocation */
	lastblkno = blkno + nblocks - 1;

	/* determine the block number of the block following
	 * the existing allocation.
	 */
	extblkno = lastblkno + 1;

	IREAD_LOCK(ipbmap, RDWRLOCK_DMAP);

	/* better be within the file system */
	bmp = sbi->bmap;
	if (lastblkno < 0 || lastblkno >= bmp->db_mapsize) {
		IREAD_UNLOCK(ipbmap);
		jfs_error(ip->i_sb,
			  "dbExtend: the block is outside the filesystem");
		return -EIO;
	}

	/* we'll attempt to extend the current allocation in place by
	 * allocating the additional blocks as the blocks immediately
	 * following the current allocation.  we only try to extend the
	 * current allocation in place if the number of additional blocks
	 * can fit into a dmap, the last block of the current allocation
	 * is not the last block of the file system, and the start of the
	 * inplace extension is not on an allocation group boundary.
	 */
	if (addnblocks > BPERDMAP || extblkno >= bmp->db_mapsize ||
	    (extblkno & (bmp->db_agsize - 1)) == 0) {
		IREAD_UNLOCK(ipbmap);
		return -ENOSPC;
	}

	/* get the buffer for the dmap containing the first block
	 * of the extension.
	 */
	lblkno = BLKTODMAP(extblkno, bmp->db_l2nbperpage);
	mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
	if (mp == NULL) {
		IREAD_UNLOCK(ipbmap);
		return -EIO;
	}

	dp = (struct dmap *) mp->data;

	/* try to allocate the blocks immediately following the
	 * current allocation.
	 */
	rc = dbAllocNext(bmp, dp, extblkno, (int) addnblocks);

	IREAD_UNLOCK(ipbmap);

	/* were we successful ? */
	if (rc == 0)
		write_metapage(mp);
	else
		/* we were not successful */
		release_metapage(mp);


	return (rc);
}


/*
 * NAME:	dbAllocNext()
 *
 * FUNCTION:	attempt to allocate the blocks of the specified block
 *		range within a dmap.
 *
 * PARAMETERS:
 *	bmp	-  pointer to bmap descriptor
 *	dp	-  pointer to dmap.
 *	blkno	-  starting block number of the range.
 *	nblocks	-  number of contiguous free blocks of the range.
 *
 * RETURN VALUES:
 *	0	- success
 *	-ENOSPC	- insufficient disk resources
 *	-EIO	- i/o error
 *
 * serialization: IREAD_LOCK(ipbmap) held on entry/exit;
 */
static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks)
{
	int dbitno, word, rembits, nb, nwords, wbitno, nw;
	int l2size;
	s8 *leaf;
	u32 mask;

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

	/* pick up a pointer to the leaves of the dmap tree.
	 */
	leaf = dp->tree.stree + le32_to_cpu(dp->tree.leafidx);

	/* determine the bit number and word within the dmap of the
	 * starting block.
	 */
	dbitno = blkno & (BPERDMAP - 1);
	word = dbitno >> L2DBWORD;

	/* check if the specified block range is contained within
	 * this dmap.
	 */
	if (dbitno + nblocks > BPERDMAP)
		return -ENOSPC;

	/* check if the starting leaf indicates that anything
	 * is free.
	 */
	if (leaf[word] == NOFREE)
		return -ENOSPC;

	/* check the dmaps words corresponding to block range to see
	 * if the block range is free.  not all bits of the first and
	 * last words may be contained within the block range.  if this
	 * is the case, we'll work against those words (i.e. partial first
	 * and/or last) on an individual basis (a single pass) and examine
	 * the actual bits to determine if they are free.  a single pass
	 * will be used for all dmap words fully contained within the
	 * specified range.  within this pass, the leaves of the dmap
	 * tree will be examined to determine if the blocks are free. a
	 * single leaf may describe the free space of multiple dmap
	 * words, so we may visit only a subset of the actual leaves
	 * corresponding to the dmap words of the block range.
	 */
	for (rembits = nblocks; rembits > 0; rembits -= nb, dbitno += nb) {
		/* determine the bit number within the word and
		 * the number of bits within the word.
		 */
		wbitno = dbitno & (DBWORD - 1);
		nb = min(rembits, DBWORD - wbitno);

		/* check if only part of the word is to be examined.
		 */
		if (nb < DBWORD) {
			/* check if the bits are free.
			 */
			mask = (ONES << (DBWORD - nb) >> wbitno);
			if ((mask & ~le32_to_cpu(dp->wmap[word])) != mask)
				return -ENOSPC;

			word += 1;
		} else {
			/* one or more dmap words are fully contained
			 * within the block range.  determine how many
			 * words and how many bits.
			 */
			nwords = rembits >> L2DBWORD;
			nb = nwords << L2DBWORD;

			/* now examine the appropriate leaves to determine
			 * if the blocks are free.
			 */
			while (nwords > 0) {
				/* does the leaf describe any free space ?
				 */
				if (leaf[word] < BUDMIN)
					return -ENOSPC;

				/* determine the l2 number of bits provided
				 * by this leaf.
				 */
				l2size =
				    min((int)leaf[word], NLSTOL2BSZ(nwords));

				/* determine how many words were handled.
				 */
				nw = BUDSIZE(l2size, BUDMIN);

				nwords -= nw;
				word += nw;
			}
		}
	}

	/* allocate the blocks.
	 */
	return (dbAllocDmap(bmp, dp, blkno, nblocks));
}


/*
 * NAME:	dbAllocNear()
 *
 * FUNCTION:	attempt to allocate a number of contiguous free blocks near
 *		a specified block (hint) within a dmap.
 *
 *		starting with the dmap leaf that covers the hint, we'll
 *		check the next four contiguous leaves for sufficient free
 *		space.  if sufficient free space is found, we'll allocate
 *		the desired free space.
 *
 * PARAMETERS:
 *	bmp	-  pointer to bmap descriptor
 *	dp	-  pointer to dmap.
 *	blkno	-  block number to allocate near.
 *	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: IREAD_LOCK(ipbmap) held on entry/exit;
 */
static int
dbAllocNear(struct bmap * bmp,
	    struct dmap * dp, s64 blkno, int nblocks, int l2nb, s64 * results)
{
	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