xfs_attr_leaf.c

来自「Linux Kernel 2.6.9 for OMAP1710」· C语言 代码 · 共 2,154 行 · 第 1/5 页

			blk2->index = blk1->index
				    - INT_GET(leaf1->hdr.count, ARCH_CONVERT);
			args->index = args->index2 = blk2->index;
			args->blkno = args->blkno2 = blk2->blkno;
		}
	} else {
		ASSERT(state->inleaf == 1);
		args->index = args->index2 = blk1->index;
		args->blkno = args->blkno2 = blk1->blkno;
	}
}

/*
 * Examine entries until we reduce the absolute difference in
 * byte usage between the two blocks to a minimum.
 * GROT: Is this really necessary?  With other than a 512 byte blocksize,
 * GROT: there will always be enough room in either block for a new entry.
 * GROT: Do a double-split for this case?
 */
STATIC int
xfs_attr_leaf_figure_balance(xfs_da_state_t *state,
				    xfs_da_state_blk_t *blk1,
				    xfs_da_state_blk_t *blk2,
				    int *countarg, int *usedbytesarg)
{
	xfs_attr_leafblock_t *leaf1, *leaf2;
	xfs_attr_leaf_hdr_t *hdr1, *hdr2;
	xfs_attr_leaf_entry_t *entry;
	int count, max, index, totallen, half;
	int lastdelta, foundit, tmp;

	/*
	 * Set up environment.
	 */
	leaf1 = blk1->bp->data;
	leaf2 = blk2->bp->data;
	hdr1 = &leaf1->hdr;
	hdr2 = &leaf2->hdr;
	foundit = 0;
	totallen = 0;

	/*
	 * Examine entries until we reduce the absolute difference in
	 * byte usage between the two blocks to a minimum.
	 */
	max = INT_GET(hdr1->count, ARCH_CONVERT)
			+ INT_GET(hdr2->count, ARCH_CONVERT);
	half  = (max+1) * sizeof(*entry);
	half += INT_GET(hdr1->usedbytes, ARCH_CONVERT)
				+ INT_GET(hdr2->usedbytes, ARCH_CONVERT)
				+ xfs_attr_leaf_newentsize(state->args,
						     state->blocksize, NULL);
	half /= 2;
	lastdelta = state->blocksize;
	entry = &leaf1->entries[0];
	for (count = index = 0; count < max; entry++, index++, count++) {

#define XFS_ATTR_ABS(A)	(((A) < 0) ? -(A) : (A))
		/*
		 * The new entry is in the first block, account for it.
		 */
		if (count == blk1->index) {
			tmp = totallen + sizeof(*entry) +
				xfs_attr_leaf_newentsize(state->args,
							 state->blocksize,
							 NULL);
			if (XFS_ATTR_ABS(half - tmp) > lastdelta)
				break;
			lastdelta = XFS_ATTR_ABS(half - tmp);
			totallen = tmp;
			foundit = 1;
		}

		/*
		 * Wrap around into the second block if necessary.
		 */
		if (count == INT_GET(hdr1->count, ARCH_CONVERT)) {
			leaf1 = leaf2;
			entry = &leaf1->entries[0];
			index = 0;
		}

		/*
		 * Figure out if next leaf entry would be too much.
		 */
		tmp = totallen + sizeof(*entry) + xfs_attr_leaf_entsize(leaf1,
									index);
		if (XFS_ATTR_ABS(half - tmp) > lastdelta)
			break;
		lastdelta = XFS_ATTR_ABS(half - tmp);
		totallen = tmp;
#undef XFS_ATTR_ABS
	}

	/*
	 * Calculate the number of usedbytes that will end up in lower block.
	 * If new entry not in lower block, fix up the count.
	 */
	totallen -= count * sizeof(*entry);
	if (foundit) {
		totallen -= sizeof(*entry) +
				xfs_attr_leaf_newentsize(state->args,
							 state->blocksize,
							 NULL);
	}

	*countarg = count;
	*usedbytesarg = totallen;
	return(foundit);
}

/*========================================================================
 * Routines used for shrinking the Btree.
 *========================================================================*/

/*
 * Check a leaf block and its neighbors to see if the block should be
 * collapsed into one or the other neighbor.  Always keep the block
 * with the smaller block number.
 * If the current block is over 50% full, don't try to join it, return 0.
 * If the block is empty, fill in the state structure and return 2.
 * If it can be collapsed, fill in the state structure and return 1.
 * If nothing can be done, return 0.
 *
 * GROT: allow for INCOMPLETE entries in calculation.
 */
int
xfs_attr_leaf_toosmall(xfs_da_state_t *state, int *action)
{
	xfs_attr_leafblock_t *leaf;
	xfs_da_state_blk_t *blk;
	xfs_da_blkinfo_t *info;
	int count, bytes, forward, error, retval, i;
	xfs_dablk_t blkno;
	xfs_dabuf_t *bp;

	/*
	 * Check for the degenerate case of the block being over 50% full.
	 * If so, it's not worth even looking to see if we might be able
	 * to coalesce with a sibling.
	 */
	blk = &state->path.blk[ state->path.active-1 ];
	info = blk->bp->data;
	ASSERT(INT_GET(info->magic, ARCH_CONVERT) == XFS_ATTR_LEAF_MAGIC);
	leaf = (xfs_attr_leafblock_t *)info;
	count = INT_GET(leaf->hdr.count, ARCH_CONVERT);
	bytes = sizeof(xfs_attr_leaf_hdr_t) +
		count * sizeof(xfs_attr_leaf_entry_t) +
		INT_GET(leaf->hdr.usedbytes, ARCH_CONVERT);
	if (bytes > (state->blocksize >> 1)) {
		*action = 0;	/* blk over 50%, don't try to join */
		return(0);
	}

	/*
	 * Check for the degenerate case of the block being empty.
	 * If the block is empty, we'll simply delete it, no need to
	 * coalesce it with a sibling block.  We choose (aribtrarily)
	 * to merge with the forward block unless it is NULL.
	 */
	if (count == 0) {
		/*
		 * Make altpath point to the block we want to keep and
		 * path point to the block we want to drop (this one).
		 */
		forward = (!INT_ISZERO(info->forw, ARCH_CONVERT));
		memcpy(&state->altpath, &state->path, sizeof(state->path));
		error = xfs_da_path_shift(state, &state->altpath, forward,
						 0, &retval);
		if (error)
			return(error);
		if (retval) {
			*action = 0;
		} else {
			*action = 2;
		}
		return(0);
	}

	/*
	 * Examine each sibling block to see if we can coalesce with
	 * at least 25% free space to spare.  We need to figure out
	 * whether to merge with the forward or the backward block.
	 * We prefer coalescing with the lower numbered sibling so as
	 * to shrink an attribute list over time.
	 */
	/* start with smaller blk num */
	forward = (INT_GET(info->forw, ARCH_CONVERT)
					< INT_GET(info->back, ARCH_CONVERT));
	for (i = 0; i < 2; forward = !forward, i++) {
		if (forward)
			blkno = INT_GET(info->forw, ARCH_CONVERT);
		else
			blkno = INT_GET(info->back, ARCH_CONVERT);
		if (blkno == 0)
			continue;
		error = xfs_da_read_buf(state->args->trans, state->args->dp,
					blkno, -1, &bp, XFS_ATTR_FORK);
		if (error)
			return(error);
		ASSERT(bp != NULL);

		leaf = (xfs_attr_leafblock_t *)info;
		count  = INT_GET(leaf->hdr.count, ARCH_CONVERT);
		bytes  = state->blocksize - (state->blocksize>>2);
		bytes -= INT_GET(leaf->hdr.usedbytes, ARCH_CONVERT);
		leaf = bp->data;
		ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT)
						== XFS_ATTR_LEAF_MAGIC);
		count += INT_GET(leaf->hdr.count, ARCH_CONVERT);
		bytes -= INT_GET(leaf->hdr.usedbytes, ARCH_CONVERT);
		bytes -= count * sizeof(xfs_attr_leaf_entry_t);
		bytes -= sizeof(xfs_attr_leaf_hdr_t);
		xfs_da_brelse(state->args->trans, bp);
		if (bytes >= 0)
			break;	/* fits with at least 25% to spare */
	}
	if (i >= 2) {
		*action = 0;
		return(0);
	}

	/*
	 * Make altpath point to the block we want to keep (the lower
	 * numbered block) and path point to the block we want to drop.
	 */
	memcpy(&state->altpath, &state->path, sizeof(state->path));
	if (blkno < blk->blkno) {
		error = xfs_da_path_shift(state, &state->altpath, forward,
						 0, &retval);
	} else {
		error = xfs_da_path_shift(state, &state->path, forward,
						 0, &retval);
	}
	if (error)
		return(error);
	if (retval) {
		*action = 0;
	} else {
		*action = 1;
	}
	return(0);
}

/*
 * Remove a name from the leaf attribute list structure.
 *
 * Return 1 if leaf is less than 37% full, 0 if >= 37% full.
 * If two leaves are 37% full, when combined they will leave 25% free.
 */
int
xfs_attr_leaf_remove(xfs_dabuf_t *bp, xfs_da_args_t *args)
{
	xfs_attr_leafblock_t *leaf;
	xfs_attr_leaf_hdr_t *hdr;
	xfs_attr_leaf_map_t *map;
	xfs_attr_leaf_entry_t *entry;
	int before, after, smallest, entsize;
	int tablesize, tmp, i;
	xfs_mount_t *mp;

	leaf = bp->data;
	ASSERT(INT_GET(leaf->hdr.info.magic, ARCH_CONVERT)
						== XFS_ATTR_LEAF_MAGIC);
	hdr = &leaf->hdr;
	mp = args->trans->t_mountp;
	ASSERT((INT_GET(hdr->count, ARCH_CONVERT) > 0)
		&& (INT_GET(hdr->count, ARCH_CONVERT) < (XFS_LBSIZE(mp)/8)));
	ASSERT((args->index >= 0)
		&& (args->index < INT_GET(hdr->count, ARCH_CONVERT)));
	ASSERT(INT_GET(hdr->firstused, ARCH_CONVERT)
				>= ((INT_GET(hdr->count, ARCH_CONVERT)
					* sizeof(*entry))+sizeof(*hdr)));
	entry = &leaf->entries[args->index];
	ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT)
				>= INT_GET(hdr->firstused, ARCH_CONVERT));
	ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT) < XFS_LBSIZE(mp));

	/*
	 * Scan through free region table:
	 *    check for adjacency of free'd entry with an existing one,
	 *    find smallest free region in case we need to replace it,
	 *    adjust any map that borders the entry table,
	 */
	tablesize = INT_GET(hdr->count, ARCH_CONVERT)
					* sizeof(xfs_attr_leaf_entry_t)
					+ sizeof(xfs_attr_leaf_hdr_t);
	map = &hdr->freemap[0];
	tmp = INT_GET(map->size, ARCH_CONVERT);
	before = after = -1;
	smallest = XFS_ATTR_LEAF_MAPSIZE - 1;
	entsize = xfs_attr_leaf_entsize(leaf, args->index);
	for (i = 0; i < XFS_ATTR_LEAF_MAPSIZE; map++, i++) {
		ASSERT(INT_GET(map->base, ARCH_CONVERT) < XFS_LBSIZE(mp));
		ASSERT(INT_GET(map->size, ARCH_CONVERT) < XFS_LBSIZE(mp));
		if (INT_GET(map->base, ARCH_CONVERT) == tablesize) {
			INT_MOD(map->base, ARCH_CONVERT,
					-sizeof(xfs_attr_leaf_entry_t));
			INT_MOD(map->size, ARCH_CONVERT,
					sizeof(xfs_attr_leaf_entry_t));
		}

		if ((INT_GET(map->base, ARCH_CONVERT)
					+ INT_GET(map->size, ARCH_CONVERT))
				== INT_GET(entry->nameidx, ARCH_CONVERT)) {
			before = i;
		} else if (INT_GET(map->base, ARCH_CONVERT)
			== (INT_GET(entry->nameidx, ARCH_CONVERT) + entsize)) {
			after = i;
		} else if (INT_GET(map->size, ARCH_CONVERT) < tmp) {
			tmp = INT_GET(map->size, ARCH_CONVERT);
			smallest = i;
		}
	}

	/*
	 * Coalesce adjacent freemap regions,
	 * or replace the smallest region.
	 */
	if ((before >= 0) || (after >= 0)) {
		if ((before >= 0) && (after >= 0)) {
			map = &hdr->freemap[before];
			INT_MOD(map->size, ARCH_CONVERT, entsize);
			INT_MOD(map->size, ARCH_CONVERT,
				INT_GET(hdr->freemap[after].size,
							ARCH_CONVERT));
			INT_ZERO(hdr->freemap[after].base, ARCH_CONVERT);
			INT_ZERO(hdr->freemap[after].size, ARCH_CONVERT);
		} else if (before >= 0) {
			map = &hdr->freemap[before];
			INT_MOD(map->size, ARCH_CONVERT, entsize);
		} else {
			map = &hdr->freemap[after];
			/* both on-disk, don't endian flip twice */
			map->base = entry->nameidx;
			INT_MOD(map->size, ARCH_CONVERT, entsize);
		}
	} else {
		/*
		 * Replace smallest region (if it is smaller than free'd entry)
		 */
		map = &hdr->freemap[smallest];
		if (INT_GET(map->size, ARCH_CONVERT) < entsize) {
			INT_SET(map->base, ARCH_CONVERT,
					INT_GET(entry->nameidx, ARCH_CONVERT));
			INT_SET(map->size, ARCH_CONVERT, entsize);
		}
	}

	/*
	 * Did we remove the first entry?
	 */
	if (INT_GET(entry->nameidx, ARCH_CONVERT)
				== INT_GET(hdr->firstused, ARCH_CONVERT))
		smallest = 1;
	else
		smallest = 0;

	/*
	 * Compress the remaining entries and zero out the removed stuff.
	 */
	memset(XFS_ATTR_LEAF_NAME(leaf, args->index), 0, entsize);
	INT_MOD(hdr->usedbytes, ARCH_CONVERT, -entsize);
	xfs_da_log_buf(args->trans, bp,
	     XFS_DA_LOGRANGE(leaf, XFS_ATTR_LEAF_NAME(leaf, args->index),
				   entsize));

	tmp = (INT_GET(hdr->count, ARCH_CONVERT) - args->index)
					* sizeof(xfs_attr_leaf_entry_t);
	memmove((char *)entry, (char *)(entry+1), tmp);
	INT_MOD(hdr->count, ARCH_CONVERT, -1);
	xfs_da_log_buf(args->trans, bp,
	    XFS_DA_LOGRANGE(leaf, entry, tmp + sizeof(*entry)));
	entry = &leaf->entries[INT_GET(hdr->count, ARCH_CONVERT)];
	memset((char *)entry, 0, sizeof(xfs_attr_leaf_entry_t));

	/*
	 * If we removed the first entry, re-find the first used byte
	 * in the name area.  Note that if the entry was the "firstused",
	 * then we don't have a "hole" in our block resulting from
	 * removing the name.
	 */
	if (smallest) {
		tmp = XFS_LBSIZE(mp);
		entry = &leaf->entries[0];
		for (i = INT_GET(hdr->count, ARCH_CONVERT)-1;
						i >= 0; entry++, i--) {
			ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT)
				>= INT_GET(hdr->firstused, ARCH_CONVERT));
			ASSERT(INT_GET(entry->nameidx, ARCH_CONVERT)
							< XFS_LBSIZE(mp));
			if (INT_GET(entry->nameidx, ARCH_CONVERT) < tmp)
				tmp = INT_GET(entry->nameidx, ARCH_CONVERT);
		}
		INT_SET(hdr->firstused, ARCH_CONVERT, tmp);
		if (INT_ISZERO(hdr->firstused, ARCH_CONVERT)) {
			INT_SET(hdr->firstused, ARCH_CONVERT,
					tmp - XFS_ATTR_LEAF_NAME_ALIGN);
		}
	} else {
		hdr->holes = 1;		/* mark as needing compaction */
	}
	xfs_da_log_buf(args->trans, bp,
			  XFS_DA_LOGRANGE(leaf, hdr, sizeof(*hdr)));

	/*
	 * Check if leaf is less than 50% full, caller may want to
	 * "join" the leaf with a sibling if so.
	 */
	tmp  = sizeof(xfs_attr_leaf_hdr_t);
	tmp += INT_GET(leaf->hdr.count, ARCH_CONVERT)
					* sizeof(xfs_attr_leaf_entry_t);
	tmp += INT_GET(leaf->hdr.usedbytes, ARCH_CONVERT);
	return(tmp < mp->m_attr_magicpct); /* leaf is < 37% full */
}

/*
 * Move all the attribute list entries from drop_leaf into save_leaf.
 */
void
xfs_attr_leaf_unbalance(xfs_da_state_t *state, xfs_da_state_blk_t *drop_blk,
				       xfs_da_state_blk_t *save_blk)
{
	xfs_attr_leafblock_t *drop_leaf, *save_leaf, *tmp_leaf;
	xfs_attr_leaf_hdr_t *drop_hdr, *save_hdr, *tmp_hdr;
	xfs_mount_t *mp;
	char *tmpbuffer;

	/*
	 * Set up environment.
	 */