xfs_dir2_node.c

linux 内核源代码

								newfdb),
							-1, &curbp,
							XFS_DATA_FORK))) {
						return error;
					}
					free = curbp->data;
					ASSERT(be32_to_cpu(free->hdr.magic) ==
					       XFS_DIR2_FREE_MAGIC);
					ASSERT((be32_to_cpu(free->hdr.firstdb) %
						XFS_DIR2_MAX_FREE_BESTS(mp)) ==
					       0);
					ASSERT(be32_to_cpu(free->hdr.firstdb) <= curdb);
					ASSERT(curdb <
					       be32_to_cpu(free->hdr.firstdb) +
					       be32_to_cpu(free->hdr.nvalid));
				}
				/*
				 * Get the index for our entry.
				 */
				fi = xfs_dir2_db_to_fdindex(mp, curdb);
				/*
				 * If it has room, return it.
				 */
				if (unlikely(be16_to_cpu(free->bests[fi]) == NULLDATAOFF)) {
					XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
							 XFS_ERRLEVEL_LOW, mp);
					if (curfdb != newfdb)
						xfs_da_brelse(tp, curbp);
					return XFS_ERROR(EFSCORRUPTED);
				}
				curfdb = newfdb;
				if (be16_to_cpu(free->bests[fi]) >= length) {
					*indexp = index;
					state->extravalid = 1;
					state->extrablk.bp = curbp;
					state->extrablk.blkno = curfdb;
					state->extrablk.index = fi;
					state->extrablk.magic =
						XFS_DIR2_FREE_MAGIC;
					ASSERT(args->oknoent);
					return XFS_ERROR(ENOENT);
				}
			}
		}
		/*
		 * Not adding a new entry, so we really want to find
		 * the name given to us.
		 */
		else {
			/*
			 * If it's a different data block, go get it.
			 */
			if (newdb != curdb) {
				/*
				 * If we had a block before, drop it.
				 */
				if (curbp)
					xfs_da_brelse(tp, curbp);
				/*
				 * Read the data block.
				 */
				if ((error =
				    xfs_da_read_buf(tp, dp,
					    xfs_dir2_db_to_da(mp, newdb), -1,
					    &curbp, XFS_DATA_FORK))) {
					return error;
				}
				xfs_dir2_data_check(dp, curbp);
				curdb = newdb;
			}
			/*
			 * Point to the data entry.
			 */
			dep = (xfs_dir2_data_entry_t *)
			      ((char *)curbp->data +
			       xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address)));
			/*
			 * Compare the entry, return it if it matches.
			 */
			if (dep->namelen == args->namelen &&
			    dep->name[0] == args->name[0] &&
			    memcmp(dep->name, args->name, args->namelen) == 0) {
				args->inumber = be64_to_cpu(dep->inumber);
				*indexp = index;
				state->extravalid = 1;
				state->extrablk.bp = curbp;
				state->extrablk.blkno = curdb;
				state->extrablk.index =
					(int)((char *)dep -
					      (char *)curbp->data);
				state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
				return XFS_ERROR(EEXIST);
			}
		}
	}
	/*
	 * Didn't find a match.
	 * If we are holding a buffer, give it back in case our caller
	 * finds it useful.
	 */
	if ((state->extravalid = (curbp != NULL))) {
		state->extrablk.bp = curbp;
		state->extrablk.index = -1;
		/*
		 * For addname, giving back a free block.
		 */
		if (args->addname) {
			state->extrablk.blkno = curfdb;
			state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
		}
		/*
		 * For other callers, giving back a data block.
		 */
		else {
			state->extrablk.blkno = curdb;
			state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
		}
	}
	/*
	 * Return the final index, that will be the insertion point.
	 */
	*indexp = index;
	ASSERT(index == be16_to_cpu(leaf->hdr.count) || args->oknoent);
	return XFS_ERROR(ENOENT);
}

/*
 * Move count leaf entries from source to destination leaf.
 * Log entries and headers.  Stale entries are preserved.
 */
static void
xfs_dir2_leafn_moveents(
	xfs_da_args_t	*args,			/* operation arguments */
	xfs_dabuf_t	*bp_s,			/* source leaf buffer */
	int		start_s,		/* source leaf index */
	xfs_dabuf_t	*bp_d,			/* destination leaf buffer */
	int		start_d,		/* destination leaf index */
	int		count)			/* count of leaves to copy */
{
	xfs_dir2_leaf_t	*leaf_d;		/* destination leaf structure */
	xfs_dir2_leaf_t	*leaf_s;		/* source leaf structure */
	int		stale;			/* count stale leaves copied */
	xfs_trans_t	*tp;			/* transaction pointer */

	xfs_dir2_trace_args_bibii("leafn_moveents", args, bp_s, start_s, bp_d,
		start_d, count);
	/*
	 * Silently return if nothing to do.
	 */
	if (count == 0) {
		return;
	}
	tp = args->trans;
	leaf_s = bp_s->data;
	leaf_d = bp_d->data;
	/*
	 * If the destination index is not the end of the current
	 * destination leaf entries, open up a hole in the destination
	 * to hold the new entries.
	 */
	if (start_d < be16_to_cpu(leaf_d->hdr.count)) {
		memmove(&leaf_d->ents[start_d + count], &leaf_d->ents[start_d],
			(be16_to_cpu(leaf_d->hdr.count) - start_d) *
			sizeof(xfs_dir2_leaf_entry_t));
		xfs_dir2_leaf_log_ents(tp, bp_d, start_d + count,
			count + be16_to_cpu(leaf_d->hdr.count) - 1);
	}
	/*
	 * If the source has stale leaves, count the ones in the copy range
	 * so we can update the header correctly.
	 */
	if (leaf_s->hdr.stale) {
		int	i;			/* temp leaf index */

		for (i = start_s, stale = 0; i < start_s + count; i++) {
			if (be32_to_cpu(leaf_s->ents[i].address) == XFS_DIR2_NULL_DATAPTR)
				stale++;
		}
	} else
		stale = 0;
	/*
	 * Copy the leaf entries from source to destination.
	 */
	memcpy(&leaf_d->ents[start_d], &leaf_s->ents[start_s],
		count * sizeof(xfs_dir2_leaf_entry_t));
	xfs_dir2_leaf_log_ents(tp, bp_d, start_d, start_d + count - 1);
	/*
	 * If there are source entries after the ones we copied,
	 * delete the ones we copied by sliding the next ones down.
	 */
	if (start_s + count < be16_to_cpu(leaf_s->hdr.count)) {
		memmove(&leaf_s->ents[start_s], &leaf_s->ents[start_s + count],
			count * sizeof(xfs_dir2_leaf_entry_t));
		xfs_dir2_leaf_log_ents(tp, bp_s, start_s, start_s + count - 1);
	}
	/*
	 * Update the headers and log them.
	 */
	be16_add(&leaf_s->hdr.count, -(count));
	be16_add(&leaf_s->hdr.stale, -(stale));
	be16_add(&leaf_d->hdr.count, count);
	be16_add(&leaf_d->hdr.stale, stale);
	xfs_dir2_leaf_log_header(tp, bp_s);
	xfs_dir2_leaf_log_header(tp, bp_d);
	xfs_dir2_leafn_check(args->dp, bp_s);
	xfs_dir2_leafn_check(args->dp, bp_d);
}

/*
 * Determine the sort order of two leaf blocks.
 * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
 */
int						/* sort order */
xfs_dir2_leafn_order(
	xfs_dabuf_t	*leaf1_bp,		/* leaf1 buffer */
	xfs_dabuf_t	*leaf2_bp)		/* leaf2 buffer */
{
	xfs_dir2_leaf_t	*leaf1;			/* leaf1 structure */
	xfs_dir2_leaf_t	*leaf2;			/* leaf2 structure */

	leaf1 = leaf1_bp->data;
	leaf2 = leaf2_bp->data;
	ASSERT(be16_to_cpu(leaf1->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
	ASSERT(be16_to_cpu(leaf2->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
	if (be16_to_cpu(leaf1->hdr.count) > 0 &&
	    be16_to_cpu(leaf2->hdr.count) > 0 &&
	    (be32_to_cpu(leaf2->ents[0].hashval) < be32_to_cpu(leaf1->ents[0].hashval) ||
	     be32_to_cpu(leaf2->ents[be16_to_cpu(leaf2->hdr.count) - 1].hashval) <
	     be32_to_cpu(leaf1->ents[be16_to_cpu(leaf1->hdr.count) - 1].hashval)))
		return 1;
	return 0;
}

/*
 * Rebalance leaf entries between two leaf blocks.
 * This is actually only called when the second block is new,
 * though the code deals with the general case.
 * A new entry will be inserted in one of the blocks, and that
 * entry is taken into account when balancing.
 */
static void
xfs_dir2_leafn_rebalance(
	xfs_da_state_t		*state,		/* btree cursor */
	xfs_da_state_blk_t	*blk1,		/* first btree block */
	xfs_da_state_blk_t	*blk2)		/* second btree block */
{
	xfs_da_args_t		*args;		/* operation arguments */
	int			count;		/* count (& direction) leaves */
	int			isleft;		/* new goes in left leaf */
	xfs_dir2_leaf_t		*leaf1;		/* first leaf structure */
	xfs_dir2_leaf_t		*leaf2;		/* second leaf structure */
	int			mid;		/* midpoint leaf index */
#ifdef DEBUG
	int			oldstale;	/* old count of stale leaves */
#endif
	int			oldsum;		/* old total leaf count */
	int			swap;		/* swapped leaf blocks */

	args = state->args;
	/*
	 * If the block order is wrong, swap the arguments.
	 */
	if ((swap = xfs_dir2_leafn_order(blk1->bp, blk2->bp))) {
		xfs_da_state_blk_t	*tmp;	/* temp for block swap */

		tmp = blk1;
		blk1 = blk2;
		blk2 = tmp;
	}
	leaf1 = blk1->bp->data;
	leaf2 = blk2->bp->data;
	oldsum = be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count);
#ifdef DEBUG
	oldstale = be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale);
#endif
	mid = oldsum >> 1;
	/*
	 * If the old leaf count was odd then the new one will be even,
	 * so we need to divide the new count evenly.
	 */
	if (oldsum & 1) {
		xfs_dahash_t	midhash;	/* middle entry hash value */

		if (mid >= be16_to_cpu(leaf1->hdr.count))
			midhash = be32_to_cpu(leaf2->ents[mid - be16_to_cpu(leaf1->hdr.count)].hashval);
		else
			midhash = be32_to_cpu(leaf1->ents[mid].hashval);
		isleft = args->hashval <= midhash;
	}
	/*
	 * If the old count is even then the new count is odd, so there's
	 * no preferred side for the new entry.
	 * Pick the left one.
	 */
	else
		isleft = 1;
	/*
	 * Calculate moved entry count.  Positive means left-to-right,
	 * negative means right-to-left.  Then move the entries.
	 */
	count = be16_to_cpu(leaf1->hdr.count) - mid + (isleft == 0);
	if (count > 0)
		xfs_dir2_leafn_moveents(args, blk1->bp,
			be16_to_cpu(leaf1->hdr.count) - count, blk2->bp, 0, count);
	else if (count < 0)
		xfs_dir2_leafn_moveents(args, blk2->bp, 0, blk1->bp,
			be16_to_cpu(leaf1->hdr.count), count);
	ASSERT(be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count) == oldsum);
	ASSERT(be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale) == oldstale);
	/*
	 * Mark whether we're inserting into the old or new leaf.
	 */
	if (be16_to_cpu(leaf1->hdr.count) < be16_to_cpu(leaf2->hdr.count))
		state->inleaf = swap;
	else if (be16_to_cpu(leaf1->hdr.count) > be16_to_cpu(leaf2->hdr.count))
		state->inleaf = !swap;
	else
		state->inleaf =
			swap ^ (blk1->index <= be16_to_cpu(leaf1->hdr.count));
	/*
	 * Adjust the expected index for insertion.
	 */
	if (!state->inleaf)
		blk2->index = blk1->index - be16_to_cpu(leaf1->hdr.count);
	
	/* 
	 * Finally sanity check just to make sure we are not returning a negative index 
	 */
	if(blk2->index < 0) {
		state->inleaf = 1;
		blk2->index = 0;
		cmn_err(CE_ALERT,
			"xfs_dir2_leafn_rebalance: picked the wrong leaf? reverting original leaf: "
			"blk1->index %d\n",
			blk1->index);
	}
}

/*
 * Remove an entry from a node directory.
 * This removes the leaf entry and the data entry,
 * and updates the free block if necessary.
 */
static int					/* error */
xfs_dir2_leafn_remove(
	xfs_da_args_t		*args,		/* operation arguments */
	xfs_dabuf_t		*bp,		/* leaf buffer */
	int			index,		/* leaf entry index */
	xfs_da_state_blk_t	*dblk,		/* data block */
	int			*rval)		/* resulting block needs join */
{
	xfs_dir2_data_t		*data;		/* data block structure */
	xfs_dir2_db_t		db;		/* data block number */
	xfs_dabuf_t		*dbp;		/* data block buffer */
	xfs_dir2_data_entry_t	*dep;		/* data block entry */
	xfs_inode_t		*dp;		/* incore directory inode */
	xfs_dir2_leaf_t		*leaf;		/* leaf structure */
	xfs_dir2_leaf_entry_t	*lep;		/* leaf entry */
	int			longest;	/* longest data free entry */
	int			off;		/* data block entry offset */
	xfs_mount_t		*mp;		/* filesystem mount point */
	int			needlog;	/* need to log data header */
	int			needscan;	/* need to rescan data frees */
	xfs_trans_t		*tp;		/* transaction pointer */

	xfs_dir2_trace_args_sb("leafn_remove", args, index, bp);
	dp = args->dp;
	tp = args->trans;
	mp = dp->i_mount;
	leaf = bp->data;
	ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
	/*
	 * Point to the entry we're removing.
	 */
	lep = &leaf->ents[index];
	/*
	 * Extract the data block and offset from the entry.
	 */
	db = xfs_dir2_dataptr_to_db(mp, be32_to_cpu(lep->address));
	ASSERT(dblk->blkno == db);
	off = xfs_dir2_dataptr_to_off(mp, be32_to_cpu(lep->address));
	ASSERT(dblk->index == off);
	/*
	 * Kill the leaf entry by marking it stale.
	 * Log the leaf block changes.
	 */
	be16_add(&leaf->hdr.stale, 1);
	xfs_dir2_leaf_log_header(tp, bp);
	lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
	xfs_dir2_leaf_log_ents(tp, bp, index, index);
	/*
	 * Make the data entry free.  Keep track of the longest freespace
	 * in the data block in case it changes.
	 */
	dbp = dblk->bp;
	data = dbp->data;
	dep = (xfs_dir2_data_entry_t *)((char *)data + off);
	longest = be16_to_cpu(data->hdr.bestfree[0].length);
	needlog = needscan = 0;
	xfs_dir2_data_make_free(tp, dbp, off,
		xfs_dir2_data_entsize(dep->namelen), &needlog, &needscan);
	/*
	 * Rescan the data block freespaces for bestfree.
	 * Log the data block header if needed.
	 */
	if (needscan)
		xfs_dir2_data_freescan(mp, data, &needlog);
	if (needlog)
		xfs_dir2_data_log_header(tp, dbp);
	xfs_dir2_data_check(dp, dbp);
	/*
	 * If the longest data block freespace changes, need to update
	 * the corresponding freeblock entry.
	 */
	if (longest < be16_to_cpu(data->hdr.bestfree[0].length)) {
		int		error;		/* error return value */
		xfs_dabuf_t	*fbp;		/* freeblock buffer */
		xfs_dir2_db_t	fdb;		/* freeblock block number */
		int		findex;		/* index in freeblock entries */
		xfs_dir2_free_t	*free;		/* freeblock structure */
		int		logfree;	/* need to log free entry */

		/*
		 * Convert the data block number to a free block,
		 * read in the free block.
		 */
		fdb = xfs_dir2_db_to_fdb(mp, db);
		if ((error = xfs_da_read_buf(tp, dp, xfs_dir2_db_to_da(mp, fdb),
				-1, &fbp, XFS_DATA_FORK))) {
			return error;
		}
		free = fbp->data;
		ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
		ASSERT(be32_to_cpu(free->hdr.firstdb) ==
		       XFS_DIR2_MAX_FREE_BESTS(mp) *
		       (fdb - XFS_DIR2_FREE_FIRSTDB(mp)));
		/*
		 * Calculate which entry we need to fix.
		 */
		findex = xfs_dir2_db_to_fdindex(mp, db);
		longest = be16_to_cpu(data->hdr.bestfree[0].length);
		/*
		 * If the data block is now empty we can get rid of it
		 * (usually).
		 */
		if (longest == mp->m_dirblksize - (uint)sizeof(data->hdr)) {
			/*
			 * Try to punch out the data block.
			 */
			error = xfs_dir2_shrink_inode(args, db, dbp);
			if (error == 0) {
				dblk->bp = NULL;
				data = NULL;
			}
			/*
			 * We can get ENOSPC if there's no space reservation.
			 * In this case just drop the buffer and some one else
			 * will eventually get rid of the empty block.
			 */
			else if (error == ENOSPC && args->total == 0)
				xfs_da_buf_done(dbp);
			else
				return error;
		}
		/*
		 * If we got rid of the data block, we can eliminate that entry
		 * in the free block.
		 */
		if (data == NULL) {
			/*
			 * One less used entry in the free table.
			 */
			be32_add(&free->hdr.nused, -1);
			xfs_dir2_free_log_header(tp, fbp);
			/*
			 * If this was the last entry in the table, we can
			 * trim the table size back.  There might be other
			 * entries at the end referring to non-existent
			 * data blocks, get those too.
			 */
			if (findex == be32_to_cpu(free->hdr.nvalid) - 1) {
				int	i;		/* free entry index */

				for (i = findex - 1;
				     i >= 0 && be16_to_cpu(free->bests[i]) == NULLDATAOFF;
				     i--)
					continue;
				free->hdr.nvalid = cpu_to_be32(i + 1);
				logfree = 0;
			}
			/*
			 * Not the last entry, just punch it out.
			 */
			else {
				free->bests[findex] = cpu_to_be16(NULLDATAOFF);
				logfree = 1;
			}
			/*
			 * If there are no useful entries left in the block,
			 * get rid of the block if we can.
			 */