jfs_dmap.c

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

 *		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;
		}

		/* determine how many blocks to allocate from this dmap.
		 */
		nb = min(n, (s64)BPERDMAP);

		/* allocate the blocks from the dmap.
		 */
		if ((rc = dbAllocDmap(bmp, dp, b, nb))) {
			release_metapage(mp);
			goto backout;
		}

		/* write the buffer.
		 */
		write_metapage(mp);
	}

	/* set the results (starting block number) and return.
	 */
	*results = blkno;
	return (0);

	/* something failed in handling an allocation request involving
	 * multiple dmaps.  we'll try to clean up by backing out any
	 * allocation that has already happened for this request.  if
	 * we fail in backing out the allocation, we'll mark the file
	 * system to indicate that blocks have been leaked.
	 */
      backout:

	/* try to backout the allocations dmap by dmap.
	 */
	for (n = nblocks - n, b = blkno; n > 0;
	     n -= BPERDMAP, b += BPERDMAP) {
		/* get the buffer for this dmap.
		 */
		lblkno = BLKTODMAP(b, bmp->db_l2nbperpage);
		mp = read_metapage(bmp->db_ipbmap, lblkno, PSIZE, 0);
		if (mp == NULL) {
			/* could not back out.  mark the file system
			 * to indicate that we have leaked blocks.
			 */
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbAllocCtl: I/O Error: Block Leakage.");
			continue;
		}
		dp = (struct dmap *) mp->data;

		/* free the blocks is this dmap.
		 */
		if (dbFreeDmap(bmp, dp, b, BPERDMAP)) {
			/* could not back out.  mark the file system
			 * to indicate that we have leaked blocks.
			 */
			release_metapage(mp);
			jfs_error(bmp->db_ipbmap->i_sb,
				  "dbAllocCtl: Block Leakage.");
			continue;
		}

		/* write the buffer.
		 */
		write_metapage(mp);
	}

	return (rc);
}


/*
 * NAME:	dbAllocDmapLev()
 *
 * FUNCTION:    attempt to allocate a specified number of contiguous blocks
 *		from a specified dmap.
 *		
 *		this routine checks if the contiguous blocks are available.
 *		if so, nblocks of blocks are allocated; otherwise, ENOSPC is
 *		returned.
 *
 * PARAMETERS:
 *      mp	-  pointer to bmap descriptor
 *      dp	-  pointer to dmap to attempt to allocate blocks from. 
 *      l2nb	-  log2 number of contiguous block desired.
 *      nblocks	-  actual number of contiguous block 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), e.g., from dbAlloc(), or 
 *	IWRITE_LOCK(ipbmap), e.g., dbAllocCtl(), held on entry/exit;
 */
static int
dbAllocDmapLev(struct bmap * bmp,
	       struct dmap * dp, int nblocks, int l2nb, s64 * results)
{
	s64 blkno;
	int leafidx, rc;

	/* can't be more than a dmaps worth of blocks */
	assert(l2nb <= L2BPERDMAP);

	/* search the tree within the dmap page for sufficient
	 * free space.  if sufficient free space is found, dbFindLeaf()
	 * returns the index of the leaf at which free space was found.
	 */
	if (dbFindLeaf((dmtree_t *) & dp->tree, l2nb, &leafidx))
		return -ENOSPC;

	/* determine the block number within the file system corresponding
	 * to the leaf at which free space was found.
	 */
	blkno = le64_to_cpu(dp->start) + (leafidx << 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 this value.
	 */
	if (dp->tree.stree[leafidx + LEAFIND] < BUDMIN)
		blkno += dbFindBits(le32_to_cpu(dp->wmap[leafidx]), l2nb);

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

	return (rc);
}


/*
 * NAME:	dbAllocDmap()
 *
 * FUNCTION:    adjust the disk allocation map to reflect the allocation
 *		of a specified block range within a dmap.
 *
 *		this routine allocates the specified blocks from the dmap
 *		through a call to dbAllocBits(). if the allocation of the
 *		block range causes the maximum string of free blocks within
 *		the dmap to change (i.e. the value of the root of the dmap's
 *		dmtree), this routine will cause this change to be reflected
 *		up through the appropriate levels of the dmap control pages
 *		by a call to dbAdjCtl() for the L0 dmap control page that
 *		covers this dmap.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *      dp	-  pointer to dmap to allocate the block range from.
 *      blkno	-  starting block number of the block to be allocated.
 *      nblocks	-  number of blocks to be allocated.
 *
 * RETURN VALUES:
 *      0	- success
 *      -EIO	- i/o error
 *
 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
 */
static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks)
{
	s8 oldroot;
	int rc;

	/* save the current value of the root (i.e. maximum free string)
	 * of the dmap tree.
	 */
	oldroot = dp->tree.stree[ROOT];

	/* allocate the specified (blocks) bits */
	dbAllocBits(bmp, dp, blkno, nblocks);

	/* if the root has not changed, done. */
	if (dp->tree.stree[ROOT] == oldroot)
		return (0);

	/* root changed. bubble the change up to the dmap control pages.
	 * if the adjustment of the upper level control pages fails,
	 * backout the bit allocation (thus making everything consistent).
	 */
	if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 1, 0)))
		dbFreeBits(bmp, dp, blkno, nblocks);

	return (rc);
}


/*
 * NAME:	dbFreeDmap()
 *
 * FUNCTION:    adjust the disk allocation map to reflect the allocation
 *		of a specified block range within a dmap.
 *
 *		this routine frees the specified blocks from the dmap through
 *		a call to dbFreeBits(). if the deallocation of the block range
 *		causes the maximum string of free blocks within the dmap to
 *		change (i.e. the value of the root of the dmap's dmtree), this
 *		routine will cause this change to be reflected up through the
 *	        appropriate levels of the dmap control pages by a call to
 *		dbAdjCtl() for the L0 dmap control page that covers this dmap.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *      dp	-  pointer to dmap to free the block range from.
 *      blkno	-  starting block number of the block to be freed.
 *      nblocks	-  number of blocks to be freed.
 *
 * RETURN VALUES:
 *      0	- success
 *      -EIO	- i/o error
 *
 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
 */
static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
		      int nblocks)
{
	s8 oldroot;
	int rc, word;

	/* save the current value of the root (i.e. maximum free string)
	 * of the dmap tree.
	 */
	oldroot = dp->tree.stree[ROOT];

	/* free the specified (blocks) bits */
	dbFreeBits(bmp, dp, blkno, nblocks);

	/* if the root has not changed, done. */
	if (dp->tree.stree[ROOT] == oldroot)
		return (0);

	/* root changed. bubble the change up to the dmap control pages.
	 * if the adjustment of the upper level control pages fails,
	 * backout the deallocation. 
	 */
	if ((rc = dbAdjCtl(bmp, blkno, dp->tree.stree[ROOT], 0, 0))) {
		word = (blkno & (BPERDMAP - 1)) >> L2DBWORD;

		/* as part of backing out the deallocation, we will have
		 * to back split the dmap tree if the deallocation caused
		 * the freed blocks to become part of a larger binary buddy
		 * system.
		 */
		if (dp->tree.stree[word] == NOFREE)
			dbBackSplit((dmtree_t *) & dp->tree, word);

		dbAllocBits(bmp, dp, blkno, nblocks);
	}

	return (rc);
}


/*
 * NAME:	dbAllocBits()
 *
 * FUNCTION:    allocate a specified block range from a dmap.
 *
 *		this routine updates the dmap to reflect the working
 *		state allocation of the specified block range. it directly
 *		updates the bits of the working map and causes the adjustment
 *		of the binary buddy system described by the dmap's dmtree
 *		leaves to reflect the bits allocated.  it also causes the
 *		dmap's dmtree, as a whole, to reflect the allocated range.
 *
 * PARAMETERS:
 *      bmp	-  pointer to bmap descriptor
 *      dp	-  pointer to dmap to allocate bits from.
 *      blkno	-  starting block number of the bits to be allocated.
 *      nblocks	-  number of bits to be allocated.
 *
 * RETURN VALUES: none
 *
 * serialization: IREAD_LOCK(ipbmap) or IWRITE_LOCK(ipbmap) held on entry/exit;
 */
static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
			int nblocks)
{
	int dbitno, word, rembits, nb, nwords, wbitno, nw, agno;
	dmtree_t *tp = (dmtree_t *) & dp->tree;
	int size;
	s8 *leaf;

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

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

	/* block range better be within the dmap */
	assert(dbitno + nblocks <= BPERDMAP);

	/* allocate the bits of the dmap's words corresponding to the block
	 * range. 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), allocating the bits of interest by hand and
	 * updating the leaf corresponding to the dmap word. a single pass
	 * will be used for all dmap words fully contained within the
	 * specified range.  within this pass, the bits of all fully contained
	 * dmap words will be marked as free in a single shot and the leaves
	 * will be updated. a single leaf may describe the free space of
	 * multiple dmap words, so we may update 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 a word is to be allocated.
		 */
		if (nb < DBWORD) {
			/* allocate (set to 1) the appropriate bits within
			 * this dmap word.
			 */
			dp->wmap[word] |= cpu_to_le32(ONES << (DBWORD - nb)
						      >> wbitno);

			/* update the leaf for this dmap word. in addition
			 * to setting the leaf value to the binary buddy max
			 * of the updated dmap word, dbSplit() will split
			 * the binary system of the leaves if need be.
			 */
			dbSplit(tp, word, BUDMIN,
				dbMaxBud((u8 *) & dp->wmap[word]));

			word += 1;
		} else {
			/* one or more dmap words are fully contained
			 * within the block range.  determine how many
			 * words and allocate (set to 1) the bits of these
			 * words.
			 */
			nwords = rembits >> L2DBWORD;
			memset(&dp->wmap[word], (int) ONES, nwords * 4);

			/* determine how many bits.
			 */
			nb = nwords << L2DBWORD;

			/* now update the appropriate leaves to reflect