fsckdire.c

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

	rp->header.maxslot = n;
	stblsize = (n + 31) >> L2DTSLOTSIZE;

	/* copy old stbl to new stbl at start of extended area */
	rp->header.stblindex = DTROOTMAXSLOT;
	stbl = (int8_t *) & rp->slot[DTROOTMAXSLOT];
	bcopy(sp->header.stbl, stbl, sp->header.nextindex);
	rp->header.nextindex = sp->header.nextindex;

	/* copy old data area to start of new data area */
	bcopy(&sp->slot[1], &rp->slot[1], IDATASIZE);

	/*
	 * append free region of newly extended area at tail of freelist
	 */
	/* init free region of newly extended area */
	fsi = n = DTROOTMAXSLOT + stblsize;
	f = &rp->slot[fsi];
	for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
		f->next = fsi;
	f->next = -1;

	/* append new free region at tail of old freelist */
	fsi = sp->header.freelist;
	if (fsi == -1)
		rp->header.freelist = n;
	else {
		rp->header.freelist = fsi;

		do {
			f = &rp->slot[fsi];
			fsi = f->next;
		} while (fsi != -1);

		f->next = n;
	}

	rp->header.freecnt = sp->header.freecnt + rp->header.maxslot - n;

	/*
	 * Update directory index table for entries now in right page;
	 */
	if ((rp->header.flag & BT_LEAF) && DO_INDEX()) {
		struct ldtentry *ldtentry;

		stbl = DT_GETSTBL(rp);
		for (n = 0; n < rp->header.nextindex; n++) {
			ldtentry= (struct ldtentry *) &rp->slot[stbl[n]];
			modify_index(ip, rbn, n, ldtentry->index);
		}
	}
	/*
	 * insert the new entry into the new right/child page
	 * (skip index in the new right page will not change)
	 */
	dtInsertEntry(ip, rp, split->index, split->key, split->data);

	/*
	 *      reset parent/root page
	 *
	 * set the 1st entry offset to 0, which force the left-most key
	 * at any level of the tree to be less than any search key.
	 *
	 * The btree comparison code guarantees that the left-most key on any
	 * level of the tree is never used, so it doesn't need to be filled in.
	 */
	/* update page header of root */
	if (sp->header.flag & BT_LEAF) {
		sp->header.flag &= ~BT_LEAF;
		sp->header.flag |= BT_INTERNAL;
	}

	/* init the first entry */
	s = (struct idtentry *) &sp->slot[DTENTRYSTART];
	ppxd = (pxd_t *) s;
	*ppxd = *pxd;
	s->next = -1;
	s->namlen = 0;

	stbl = sp->header.stbl;
	stbl[0] = DTENTRYSTART;
	sp->header.nextindex = 1;

	/* init freelist */
	fsi = DTENTRYSTART + 1;
	f = &sp->slot[fsi];

	/* init free region of remaining area */
	for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
		f->next = fsi;
	f->next = -1;

	sp->header.freelist = DTENTRYSTART + 1;
	sp->header.freecnt = DTROOTMAXSLOT - (DTENTRYSTART + 1);

	*rbpp = rbp;

	ip->di_nblocks += lengthPXD(pxd);
	return 0;
}

/*
 *	fsck_dtDelete()
 *
 * function: delete the entry(s) referenced by a key.
 *
 * parameter:
 *	ip	- parent directory
 *	key 	- entry name;
 *	ino	- entry i_number;
 *
 * return:
 */
int fsck_dtDelete(struct dinode *ip, struct component_name *key, uint32_t * ino)
{
	int rc = 0;
	int64_t bn;
	struct btpage *bp;
	dtpage_t *p;
	int32_t index;
	struct btstack btstack;

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

	/* retrieve search result */
	BT_GETSEARCH(ip, btstack.top, bn, bp, dtpage_t, p, index);

	/*
	 * the leaf page becomes empty, delete the page
	 */
	if (p->header.nextindex == 1) {
		/* delete empty page */
		rc = fsck_dtDeleteUp(ip, bp, &btstack);
	} else {
		/*
		 * the leaf page has other entries remaining:
		 *
		 * delete the entry from the leaf page.
		 */
		/* free the leaf entry */
		fsck_dtDeleteEntry(p, index);

		/*
		 * Update directory index table for entries moved in stbl
		 */
		if (DO_INDEX() && index < p->header.nextindex) {
			int i;
			struct ldtentry *ldtentry;
			int8_t *stbl;
			stbl = DT_GETSTBL(p);
			for (i = index; i < p->header.nextindex; i++) {
				ldtentry = (struct ldtentry *)&p->slot[stbl[i]];
				modify_index(ip, bn, i, ldtentry->index);
			}
		}

		FSCK_BT_PUTPAGE(bp);
	}

	return rc;
}

/*
 *	fsck_dtDeleteUp()
 *
 * function:
 *	free empty pages as propagating deletion up the tree
 *
 * parameter:
 *
 * return:
 */
static int fsck_dtDeleteUp(struct dinode *ip, struct btpage *fbp,
			   struct btstack *btstack)
{
	int rc = 0;
	struct btpage *bp;
	dtpage_t *fp, *p = 0;
	int32_t index, nextindex;
	int64_t xaddr;
	int32_t xlen;
	struct btframe *parent;

	/* get page to delete */
	fp = FSCK_BT_PAGE(ip, fbp, dtpage_t);

	/*
	 *      keep the root leaf page which has become empty
	 */
	if (fp->header.flag & BT_ROOT) {
		/*
		 * reset the root
		 *
		 * fsck_dtInitRoot() acquires txlock on the root
		 */
		fsck_dtInitRoot(ip, ip->di_parent);

		FSCK_BT_PUTPAGE(fbp);

		return 0;
	}

	/*
	 *      free the non-root leaf page
	 */
	/* update sibling pointers */
	rc = dtRelink(ip, fp);
	if (rc)
		return rc;

	xaddr = addressPXD(&fp->header.self);
	xlen = lengthPXD(&fp->header.self);
	ip->di_nblocks -= xlen;

	/* free backing extent */
	fsck_dealloc_fsblks(xlen, xaddr);

	/* free/invalidate its buffer page */
	recon_dnode_release((dtpage_t *) fbp);

	/*
	 *      propagate page deletion up the directory tree
	 *
	 * If the delete from the parent page makes it empty,
	 * continue all the way up the tree.
	 * stop if the root page is reached (which is never deleted) or
	 * if the entry deletion does not empty the page.
	 */
	while ((parent = BT_POP(btstack)) != NULL) {
		/* pin the parent page <sp> */
		FSCK_BT_GETPAGE(ip, parent->bn, bp, dtpage_t, p, rc);
		if (rc)
			return rc;

		/*
		 * free the extent of the child page deleted
		 */
		index = parent->index;

		/*
		 * delete the entry for the child page from parent
		 */
		nextindex = p->header.nextindex;

		/*
		 * the parent has the single entry being deleted:
		 *
		 * free the parent page which has become empty.
		 */
		if (nextindex == 1) {
			/*
			 * keep the root internal page which has become empty
			 */
			if (p->header.flag & BT_ROOT) {
				/*
				 * reset the root
				 *
				 * fsck_dtInitRoot() acquires txlock on the root
				 */
				fsck_dtInitRoot(ip, ip->di_parent);

				FSCK_BT_PUTPAGE(bp);

				return 0;
			} else {
				/*
				 * free the parent page
				 */
				/* update sibling pointers */
				rc = dtRelink(ip, p);
				if (rc)
					return rc;

				xaddr = addressPXD(&p->header.self);
				xlen = lengthPXD(&p->header.self);
				ip->di_nblocks -= xlen;

				/* free backing extent */
				fsck_dealloc_fsblks(xlen, xaddr);

				/* free/invalidate its buffer page */
				recon_dnode_release((dtpage_t *) bp);

				/* propagate up */
				continue;
			}
		}

		/*
		 * the parent has other entries remaining:
		 *
		 * delete the router entry from the parent page.
		 */
		/* free the router entry */
		fsck_dtDeleteEntry(p, index);

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

		/* exit propagation up */
		break;
	}

	ip->di_size -= PSIZE;
	return 0;
}

/*
 *	dtRelink()
 *
 * function:
 *	link around a freed page.
 *
 * parameter:
 *	fp:	page to be freed
 *
 * return:
 */
static int dtRelink(struct dinode *ip, dtpage_t * p)
{
	int rc;
	struct btpage *bp;
	int64_t nextbn, prevbn;

	nextbn = p->header.next;
	prevbn = p->header.prev;

	/* update prev pointer of the next page */
	if (nextbn != 0) {
		FSCK_BT_GETPAGE(ip, nextbn, bp, dtpage_t, p, rc);
		if (rc)
			return rc;

		p->header.prev = prevbn;
		FSCK_BT_PUTPAGE(bp);
	}

	/* update next pointer of the previous page */
	if (prevbn != 0) {
		FSCK_BT_GETPAGE(ip, prevbn, bp, dtpage_t, p, rc);
		if (rc)
			return rc;

		p->header.next = nextbn;
		FSCK_BT_PUTPAGE(bp);
	}

	return 0;
}

/*
 *	fsck_dtInitRoot()
 *
 * initialize directory root (inline in inode)
 */
void fsck_dtInitRoot(struct dinode *ip, uint32_t idotdot)
{
	dtroot_t *p;
	int32_t fsi;
	struct dtslot *f;

	p = (dtroot_t *) & ip->di_btroot;

	p->header.flag = DXD_INDEX | BT_ROOT | BT_LEAF;

	p->header.nextindex = 0;

	/* init freelist */
	fsi = 1;
	f = &p->slot[fsi];

	/* init data area of root */
	for (fsi++; fsi < DTROOTMAXSLOT; f++, fsi++)
		f->next = fsi;
	f->next = -1;

	p->header.freelist = 1;
	p->header.freecnt = 8;

	/* init '..' entry in btroot */
	p->header.idotdot = idotdot;

	ip->di_size = IDATASIZE;

	return;
}

/*
 *	dtCompare()
 *
 * function: compare search key with an (leaf/internal) entry
 *
 * return:
 *	< 0 if k is < record
 *	= 0 if k is = record
 *	> 0 if k is > record
 */
static int dtCompare(struct component_name *key,	/* search key */
		     dtpage_t * p,	/* directory page */
		     int32_t si)
{				/* entry slot index */
	int rc;
	UniChar *kname, *name;
	int32_t klen, namlen, len;
	struct ldtentry *lh;
	struct idtentry *ih;
	struct dtslot *t;

	/*
	 * force the left-most key on internal pages, at any level of
	 * the tree, to be less than any search key.
	 * this obviates having to update the leftmost key on an internal
	 * page when the user inserts a new key in the tree smaller than
	 * anything that has been stored.
	 *
	 * (? if/when fsck_dtSearch() narrows down to 1st entry (index = 0),
	 * at any internal page at any level of the tree,
	 * it descends to child of the entry anyway -
	 * ? make the entry as min size dummy entry)
	 *
	 * if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & BT_LEAF))
	 * return (1);
	 */

	kname = key->name;
	klen = key->namlen;

	/*
	 * leaf page entry
	 */
	if (p->header.flag & BT_LEAF) {
		lh = (struct ldtentry *) &p->slot[si];
		si = lh->next;
		name = lh->name;
		namlen = lh->namlen;
		if (DO_INDEX())
			len = MIN(namlen, DTLHDRDATALEN);
		else
			len = MIN(namlen, DTLHDRDATALEN_LEGACY);
	} else {
		/*
		 * internal page entry
		 */
		ih = (struct idtentry *) &p->slot[si];
		si = ih->next;
		name = ih->name;
		namlen = ih->namlen;
		len = MIN(namlen, DTIHDRDATALEN);
	}

	/* compare with head/only segment */
	len = MIN(klen, len);
	rc = *kname - *name;
	if (rc)
		return rc;
	rc = UniStrncmp(kname, name, len);
	if (rc)
		return rc;

	klen -= len;
	namlen -= len;

	/* compare with additional segment(s) */
	kname += len;
	while (klen > 0 && namlen > 0) {
		/* compare with next name segment */
		t = (struct dtslot *) &p->slot[si];
		len = MIN(namlen, DTSLOTDATALEN);
		len = MIN(klen, len);
		name = t->name;
		rc = *kname - *name;
		if (rc)
			return rc;
		rc = UniStrncmp(kname, name, len);
		if (rc)
			return rc;

		klen -= len;
		namlen -= len;
		kname += len;
		si = t->next;
	}

	return (klen - namlen);
}

/*
 *	ciCompare()
 *
 * function: compare search key with an (leaf/internal) entry
 *
 * return:
 *	< 0 if k is < record
 *	= 0 if k is = record
 *	> 0 if k is > record
 */
static int ciCompare(struct component_name *key,	/* search key */
		     dtpage_t * p,	/* directory page */
		     int32_t si,	/* entry slot index */
		     int32_t flag)
{
	int rc;
	UniChar *kname, *name, x;
	int32_t klen, namlen, len;
	struct ldtentry *lh;
	struct idtentry *ih;
	struct dtslot *t;
	int32_t i;

	/*
	 * force the left-most key on internal pages, at any level of
	 * the tree, to be less than any search key.
	 * this obviates having to update the leftmost key on an internal
	 * page when the user inserts a new key in the tree smaller than
	 * anything that has been stored.