fsckdire.c

在Linux内核从2.4升级到2.6时需要升级的软件包

/*
 *   Copyright (C) International Business Machines Corp., 2000-2005
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
/*
 *   (created from dtree.c: directory B+-tree manager for fsck)
 */

#include <config.h>
#include <errno.h>
#include <string.h>

#include "xfsckint.h"
#include "jfs_byteorder.h"
#include "jfs_unicode.h"

extern struct superblock *sb_ptr;

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  * fsck aggregate info structure pointer
  *
  *      defined in xchkdsk.c
  */
extern struct fsck_agg_record *agg_recptr;

/*
 *	btree traversal stack
 *
 * record the path traversed during the search;
 * top frame record the leaf page/entry selected.
 */
#define	MAXTREEHEIGHT		8
struct btframe {		/* stack frame */
	int64_t bn;		/*  8: */
	int16_t index;		/*  2: */
	int16_t lastindex;	/*  2: */
	struct btpage *bp;	/*  4: */
};				/* (16) */

struct btstack {
	struct btframe *top;	/* 4: */
	int32_t nsplit;		/* 4: */
	struct btframe stack[MAXTREEHEIGHT];
};

#define BT_CLR(btstack)\
	(btstack)->top = (btstack)->stack

#define BT_PUSH(BTSTACK, BN, INDEX)\
{\
	(BTSTACK)->top->bn = BN;\
	(BTSTACK)->top->index = INDEX;\
	++(BTSTACK)->top;\
}

#define BT_POP(btstack)\
	( (btstack)->top == (btstack)->stack ? NULL : --(btstack)->top )

#define BT_STACK(btstack)\
	( (btstack)->top == (btstack)->stack ? NULL : (btstack)->top )

/* retrieve search results */
#define BT_GETSEARCH(IP, LEAF, BN, BP, TYPE, P, INDEX)\
{\
	BN = (LEAF)->bn;\
	BP = (LEAF)->bp;\
	if (BN)\
		P = (TYPE *)BP;\
	else\
		P = (TYPE *)&IP->di_btroot;\
	INDEX = (LEAF)->index;\
}

/* put the page buffer of search */
#define BT_PUTSEARCH(BTSTACK)\
{\
	if ((BTSTACK)->top->bn)\
		recon_dnode_put((BTSTACK)->top->bp);\
}

/* get page from buffer page */
#define FSCK_BT_PAGE(IP, BP, TYPE)\
	(BP->flag & BT_ROOT) ? (TYPE *)&IP->di_btroot : (TYPE *)BP

/* get the page buffer and the page for specified block address */
#define FSCK_BT_GETPAGE(IP, BN, BP, TYPE, P, RC)\
{\
	if ((BN) == 0)\
	{\
		BP = (struct btpage *)&IP->di_btroot;\
		P = (TYPE *)&IP->di_btroot;\
		RC = 0;\
	}\
	else\
	{\
		RC = recon_dnode_get(BN, (dtpage_t **)&BP);\
		if (RC == 0)\
			P = (TYPE *)BP;\
	}\
}

/* put the page buffer */
#define FSCK_BT_PUTPAGE(BP)\
{\
	if (!((BP)->flag & BT_ROOT))\
		recon_dnode_put((dtpage_t *)BP);\
}

#define DO_INDEX() (sb_ptr->s_flag & JFS_DIR_INDEX)

/* dtree split parameter */
struct dtsplit {
	struct btpage *bp;
	int16_t index;
	int16_t nslot;
	struct component_name *key;
	ddata_t *data;
	struct pxdlist *pxdlist;
};

/*
 * forward references
 */
static int dtSplitUp(struct dinode *ip, struct dtsplit *split,
		     struct btstack *btstack);

static int dtSplitPage(struct dinode *ip, struct dtsplit *split,
		       struct btpage **rbpp, pxd_t * rxdp);

static int dtSplitRoot(struct dinode *ip, struct dtsplit *split,
		       struct btpage **rbpp);

static int fsck_dtDeleteUp(struct dinode *ip, struct btpage *fbp,
			   struct btstack *btstack);

static int dtRelink(struct dinode *ip, dtpage_t * p);

static int dtCompare(struct component_name *key, dtpage_t * p, int32_t si);

static void dtGetKey(dtpage_t * p, int32_t i, struct component_name *key);

static int ciCompare(struct component_name *key, dtpage_t * p, int32_t si,
		     int32_t flag);

static void ciGetLeafPrefixKey(dtpage_t * lp, int32_t li, dtpage_t * rp,
			       int32_t ri, struct component_name *key,
			       int32_t flag);

#define ciToUpper(c)   UniStrupr((c)->name)

static void dtInsertEntry(struct dinode *ip, dtpage_t * p, int32_t index,
			  struct component_name *key, ddata_t * data);

static void dtMoveEntry(dtpage_t * sp, int32_t si, dtpage_t * dp);

static void fsck_dtDeleteEntry(dtpage_t * p, int32_t fi);

void fsck_dtInitRoot(struct dinode *ip, uint32_t idotdot);

/* copy memory */
#define bcopy(source, dest, count)	memcpy(dest, source, count)

/*
 *	fsck_dtSearch()
 *
 * function:
 *	Search for the entry with specified key
 *
 * parameter:
 *
 * return: 0 - search result on stack, leaf page pinned;
 *	   errno - I/O error
 */
int fsck_dtSearch(struct dinode *ip,
		  struct component_name *key,
		  uint32_t * data, struct btstack *btstack, uint32_t flag)
{
	int rc = 0;
	int32_t cmp = 1;	/* init for empty page */
	int64_t bn;
	struct btpage *bp;
	dtpage_t *p = 0;
	int8_t *stbl;
	int32_t base, index, lim;
	struct btframe *btsp;
	pxd_t *pxd;
	uint32_t inumber;
	UniChar ciKeyName[JFS_NAME_MAX + 1];
	struct component_name ciKey = { 0, ciKeyName };

	/* uppercase search key for c-i directory */
	UniStrcpy(ciKeyName, key->name);
	ciKey.namlen = key->namlen;

	/* only uppercase if case-insensitive support is on */

	if ((sb_ptr->s_flag & JFS_OS2) == JFS_OS2) {
		ciToUpper(&ciKey);
	}

	BT_CLR(btstack);	/* reset stack */

	/* init level count for max pages to split */
	btstack->nsplit = 1;

	/*
	 *      search down tree from root:
	 *
	 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
	 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
	 *
	 * if entry with search key K is not found
	 * internal page search find the entry with largest key Ki
	 * less than K which point to the child page to search;
	 * leaf page search find the entry with smallest key Kj
	 * greater than K so that the returned index is the position of
	 * the entry to be shifted right for insertion of new entry.
	 * for empty tree, search key is greater than any key of the tree.
	 *
	 * by convention, root bn = 0.
	 */
	for (bn = 0;;) {
		/* get/pin the page to search */
		FSCK_BT_GETPAGE(ip, bn, bp, dtpage_t, p, rc);
		if (rc)
			return rc;

		/* get sorted entry table of the page */
		stbl = DT_GETSTBL(p);

		/*
		 * binary search with search key K on the current page.
		 */
		for (base = 0, lim = p->header.nextindex; lim; lim >>= 1) {
			index = base + (lim >> 1);

			if (p->header.flag & BT_LEAF) {
				/* uppercase leaf name to compare */
				cmp =
				    ciCompare(&ciKey, p, stbl[index],
					      sb_ptr->s_flag);
			} else {
				/* router key is in uppercase */
				cmp = dtCompare(&ciKey, p, stbl[index]);
			}

			if (cmp == 0) {
				/* search hit - leaf page:
				 * return the entry found
				 */
				if (p->header.flag & BT_LEAF) {
					inumber =
					    ((struct ldtentry *) &p->
					     slot[stbl[index]])->inumber;

					/*
					 * search for JFS_CREATE
					 */
					if (flag == JFS_CREATE) {
						*data = inumber;
						rc = EEXIST;
						goto out;
					}

					/*
					 * search for JFS_REMOVE
					 */
					if (flag == JFS_REMOVE
					    && *data != inumber) {
						rc = ESTALE;
						goto out;
					}

					/*
					 * JFS_REMOVE
					 */
					/* save search result */
					*data = inumber;
					btsp = btstack->top;
					btsp->bn = bn;
					btsp->index = index;
					btsp->bp = bp;

					return 0;
				}

				/* search hit - internal page:
				 * descend/search its child page
				 */
				goto getChild;
			}

			if (cmp > 0) {
				base = index + 1;
				--lim;
			}
		}

		/*
		 *      search miss
		 *
		 * base is the smallest index with key (Kj) greater than
		 * search key (K) and may be zero or (maxindex + 1) index.
		 */
		/*
		 * search miss - leaf page
		 *
		 * return location of entry (base) where new entry with
		 * search key K is to be inserted.
		 */
		if (p->header.flag & BT_LEAF) {
			/*
			 * search for JFS_LOOKUP, JFS_REMOVE, or JFS_RENAME
			 */
			if (flag == JFS_REMOVE) {
				rc = ENOENT;
				goto out;
			}

			/*
			 * search for JFS_CREATE
			 *
			 * save search result
			 */
			*data = 0;
			btsp = btstack->top;
			btsp->bn = bn;
			btsp->index = base;
			btsp->bp = bp;

			return 0;
		}

		/*
		 * search miss - internal page
		 *
		 * if base is non-zero, decrement base by one to get the parent
		 * entry of the child page to search.
		 */
		index = base ? base - 1 : base;

		/*
		 * go down to child page
		 */
	      getChild:
		/* update max. number of pages to split */
		/* assert(btstack->nsplit < 8); */
		btstack->nsplit++;

		/* push (bn, index) of the parent page/entry */
		BT_PUSH(btstack, bn, index);

		/* get the child page block number */
		pxd = (pxd_t *) & p->slot[stbl[index]];
		bn = addressPXD(pxd);

		/* unpin the parent page */
		FSCK_BT_PUTPAGE(bp);
	}

      out:
	FSCK_BT_PUTPAGE(bp);
	return rc;
}

/*
 *	fsck_dtInsert()
 *
 * function: insert an entry to directory tree
 *
 * parameter:
 *	ip	- parent directory
 *	name 	- entry name;
 *	fsn	- entry i_number;
 *
 * return: 0 - success;
 *	   errno - failure;
 */
int fsck_dtInsert(struct dinode *ip, struct component_name *name,
		  uint32_t * fsn)
{
	int rc = 0;
	struct btpage *bp;	/* page buffer */
	dtpage_t *p;		/* base B+-tree index page */
	int64_t bn;
	int32_t index;
	struct dtsplit split;	/* split information */
	ddata_t data;
	int32_t n;
	struct btstack btstack;
	uint32_t ino;

	/*
	 *      search for the entry to insert:
	 *
	 * fsck_dtSearch() returns (leaf page pinned, index at which to insert).
	 */
	rc = fsck_dtSearch(ip, name, &ino, &btstack, JFS_CREATE);
	if (rc)
		return rc;

	/*
	 *      retrieve search result
	 *
	 * fsck_dtSearch() returns (leaf page pinned, index at which to insert).
	 * n.b. fsck_dtSearch() may return index of (maxindex + 1) of
	 * the full page.
	 */
	BT_GETSEARCH(ip, btstack.top, bn, bp, dtpage_t, p, index);

	/*
	 *      insert entry for new key
	 */
	if (DO_INDEX())
		n = NDTLEAF(name->namlen);
	else
		n = NDTLEAF_LEGACY(name->namlen);
	data.leaf.ino = *fsn;

	/*
	 *      leaf page does not have enough room for new entry:
	 *
	 *      extend/split the leaf page;
	 *
	 * dtSplitUp() will insert the entry and unpin the leaf page.
	 */
	if (n > p->header.freecnt) {
		split.bp = bp;
		split.index = index;
		split.nslot = n;
		split.key = name;
		split.data = &data;
		rc = dtSplitUp(ip, &split, &btstack);
		return rc;
	}

	/*
	 *      leaf page does have enough room for new entry:
	 *
	 *      insert the new data entry into the leaf page;
	 */
	dtInsertEntry(ip, p, index, name, &data);

	/* unpin the leaf page */
	FSCK_BT_PUTPAGE(bp);

	return 0;
}

/*
 *	dtSplitUp()
 *
 * function: propagate insertion bottom up;
 *
 * parameter:
 *
 * return: 0 - success;
 *	   errno - failure;
 * 	leaf page unpinned;
 */
static int dtSplitUp(struct dinode *ip, struct dtsplit *split,
		     struct btstack *btstack)
{
	int rc = 0;
	struct btpage *sbp;
	dtpage_t *sp;		/* split page */
	struct btpage *rbp;
	dtpage_t *rp;		/* new right page split from sp */
	pxd_t rpxd;		/* new right page extent descriptor */
	struct btpage *lbp;
	dtpage_t *lp;		/* left child page */
	int32_t skip;		/* index of entry of insertion */
	struct btframe *parent;	/* parent page entry on traverse stack */
	int64_t xaddr;
	int32_t xlen;
	struct pxdlist pxdlist;
	pxd_t *pxd;
	UniChar name[JFS_NAME_MAX + 1];
	struct component_name key = { 0, name };
	ddata_t *data = split->data;
	int32_t n;

	/* get split page */
	sbp = split->bp;
	sp = FSCK_BT_PAGE(ip, sbp, dtpage_t);

	/*
	 *      split leaf page
	 *
	 *  The split routines insert the new entry
	 *
	 *      split root leaf page:
	 */
	if (sp->header.flag & BT_ROOT) {
		/*
		 * allocate a single extent child page
		 */
		xlen = agg_recptr->blksperpg;
		rc = fsck_alloc_fsblks(xlen, &xaddr);
		if (rc)
			return rc;

		pxdlist.maxnpxd = 1;
		pxdlist.npxd = 0;
		pxd = &pxdlist.pxd[0];
		PXDaddress(pxd, xaddr);
		PXDlength(pxd, xlen);
		split->pxdlist = &pxdlist;