fsckdire.c

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

	 *
	 * (? 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);
	for (i = 0; i < len; i++, kname++, name++) {
		/* uppercase the characer to match */

		if ((flag & JFS_OS2) == JFS_OS2)
			x = UniToupper(*name);	/* uppercase the characer to match */
		else
			x = *name;	/* leave the character alone */
		rc = *kname - x;
		if (rc)
			return rc;
	}

	klen -= len;
	namlen -= len;

	/* compare with additional segment(s) */
	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;
		for (i = 0; i < len; i++, kname++, name++) {

			if ((flag & JFS_OS2) == JFS_OS2)
				x = UniToupper(*name);	/* uppercase the characer to match */
			else
				x = *name;	/* leave the character alone */
			rc = *kname - x;
			if (rc)
				return rc;
		}

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

	return (klen - namlen);
}

/*
 *	ciGetLeafPrefixKey()
 *
 * function: compute prefix of suffix compression
 *	     from two adjacent leaf entries
 *	     across page boundary
 *
 * return:
 *	Number of prefix bytes needed to distinguish b from a.
 */
static void ciGetLeafPrefixKey(dtpage_t * lp,	/* left page */
			       int32_t li,	/* left entry index */
			       dtpage_t * rp,	/* right page */
			       int32_t ri,	/* right entry index */
			       struct component_name *key, int32_t flag)
{
	int32_t klen, namlen;
	UniChar *pl, *pr, *kname;
	UniChar lname[JFS_NAME_MAX + 1];
	struct component_name lkey = { 0, lname };
	UniChar rname[JFS_NAME_MAX + 1];
	struct component_name rkey = { 0, rname };

	/* get left and right key */
	dtGetKey(lp, li, &lkey);

	if ((flag & JFS_OS2) == JFS_OS2)
		ciToUpper(&lkey);

	dtGetKey(rp, ri, &rkey);

	if ((flag & JFS_OS2) == JFS_OS2)
		ciToUpper(&rkey);

	/* compute prefix */
	klen = 0;
	kname = key->name;
	namlen = MIN(lkey.namlen, rkey.namlen);
	for (pl = lkey.name, pr = rkey.name; namlen;
	     pl++, pr++, namlen--, klen++, kname++) {

		*kname = *pr;
		if (*pl != *pr) {
			key->namlen = klen + 1;
			return;
		}
	}

	/* l->namlen <= r->namlen since l <= r */
	if (lkey.namlen < rkey.namlen) {
		*kname = *pr;
		key->namlen = klen + 1;
	} else			/* l->namelen == r->namelen */
		key->namlen = klen;

	return;
}

/*
 *	dtGetKey()
 *
 * function: get key of the entry
 */
static void dtGetKey(dtpage_t * p, int32_t i,	/* entry index */
		     struct component_name *key)
{
	int32_t si;
	int8_t *stbl;
	struct ldtentry *lh;
	struct idtentry *ih;
	struct dtslot *t;
	int32_t namlen, len;
	UniChar *name, *kname;

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

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

	/*
	 *  move head/only segment
	 */
	UniStrncpy(kname, name, len);
	/*
	 *  bcopy(name, kname, len);
	 */

	/*
	 * move additional segment(s)
	 */
	while (si >= 0) {
		/* get next segment */
		t = &p->slot[si];
		kname += len;
		namlen -= len;
		len = MIN(namlen, DTSLOTDATALEN);
		UniStrncpy(kname, t->name, len);
		/*
		 * bcopy(t->name, kname, len);
		 */

		si = t->next;
	}
}

/*
 *	dtInsertEntry()
 *
 * function: allocate free slot(s) and
 *	     write a leaf/internal entry
 *
 * return: entry slot index
 */
static void dtInsertEntry(struct dinode *ip,
			  dtpage_t * p,	/* directory page */
			  int32_t index,	/* new entry index */
			  struct component_name *key,	/* key */
			  ddata_t * data)
{				/* data */
	struct dtslot *h;
	struct dtslot *t;
	struct ldtentry *lh = NULL;
	struct idtentry *ih = NULL;
	int32_t hsi, fsi, klen, len, nextindex;
	UniChar *kname, *name;
	int8_t *stbl;
	pxd_t *xd;

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

	/* allocate a free slot */
	hsi = fsi = p->header.freelist;
	h = &p->slot[fsi];
	p->header.freelist = h->next;
	--p->header.freecnt;

	/* write head/only segment */
	if (p->header.flag & BT_LEAF) {
		lh = (struct ldtentry *) h;
		lh->next = h->next;
		lh->inumber = data->leaf.ino;
		lh->namlen = klen;
		name = lh->name;
		if (DO_INDEX()) {
			len = MIN(klen, DTLHDRDATALEN);
			lh->index = 0;	/* Until we create index properly */
		} else
			len = MIN(klen, DTLHDRDATALEN_LEGACY);
	} else {
		ih = (struct idtentry *) h;
		ih->next = h->next;
		xd = (pxd_t *) ih;
		*xd = data->xd;
		ih->namlen = klen;
		name = ih->name;
		len = MIN(klen, DTIHDRDATALEN);
	}

	UniStrncpy(name, kname, len);
	/*
	 * bcopy(kname, name, len);
	 */

	/* write additional segment(s) */
	t = h;
	klen -= len;
	while (klen) {
		/* get free slot */
		fsi = p->header.freelist;
		t = &p->slot[fsi];
		p->header.freelist = t->next;
		--p->header.freecnt;

		kname += len;
		len = MIN(klen, DTSLOTDATALEN);
		UniStrncpy(t->name, kname, len);
		/*
		 * bcopy(kname, t->name, len);
		 */

		klen -= len;
	}

	/* terminate last/only segment */
	if (h == t) {
		/* single segment entry */
		if (p->header.flag & BT_LEAF)
			lh->next = -1;
		else
			ih->next = -1;
	} else
		/* multi-segment entry */
		t->next = -1;

	/* if insert into middle, shift right succeeding entries in stbl */
	stbl = DT_GETSTBL(p);
	nextindex = p->header.nextindex;
	if (index < nextindex) {
		memmove(stbl + index + 1, stbl + index, nextindex - index);
		/* Fix up directory index table */
		if ((p->header.flag & BT_LEAF) && DO_INDEX()) {
			int i;
			int64_t bn = 0;
			if (!(p->header.flag & BT_ROOT))
				bn = addressPXD(&p->header.self);
			for (i = index + 1; i <= nextindex; i++) {
				lh = (struct ldtentry *) &(p->slot[stbl[i]]);
				modify_index(ip, bn, i, lh->index);
			}
		}
	}

	stbl[index] = hsi;

	/* advance next available entry index of stbl */
	++p->header.nextindex;
}

/*
 *	dtMoveEntry()
 *
 * function: move entries from split/left page to new/right page
 *
 *	nextindex of dst page and freelist/freecnt of both pages
 *	are updated.
 */
static void dtMoveEntry(dtpage_t * sp,	/* src page */
			int32_t si,	/* src start entry index to move */
			dtpage_t * dp)
{				/* dst page */
	int32_t ssi, next;	/* src slot index */
	int32_t di;		/* dst entry index */
	int32_t dsi;		/* dst slot index */
	int8_t *sstbl, *dstbl;	/* sorted entry table */
	int32_t snamlen, len;
	struct ldtentry *slh;
	struct ldtentry *dlh = NULL;
	struct idtentry *sih;
	struct idtentry *dih = NULL;
	struct dtslot *h;
	struct dtslot *s;
	struct dtslot *d;
	int32_t nd;
	int32_t sfsi;

	sstbl = (int8_t *) & sp->slot[sp->header.stblindex];
	dstbl = (int8_t *) & dp->slot[dp->header.stblindex];

	dsi = dp->header.freelist;	/* first (whole page) free slot */
	sfsi = sp->header.freelist;

	/*
	 * move entries
	 */
	nd = 0;
	for (di = 0; si < sp->header.nextindex; si++, di++) {
		ssi = sstbl[si];
		dstbl[di] = dsi;

		/*
		 * move head/only segment of an entry
		 */
		/* get dst slot */
		h = d = &dp->slot[dsi];

		/* get src slot and move */
		s = &sp->slot[ssi];
		if (sp->header.flag & BT_LEAF) {
			/* get source entry */
			slh = (struct ldtentry *) s;
			snamlen = slh->namlen;

			if (DO_INDEX())
				len = MIN(snamlen, DTLHDRDATALEN);
			else
				len = MIN(snamlen, DTLHDRDATALEN_LEGACY);
			dlh = (struct ldtentry *) h;
			bcopy(slh, dlh, 6 + len * 2);
			/*
			 * bcopy(slh, dlh, 6 + len);
			 */

			next = slh->next;

			/* update dst head/only segment next field */
			dsi++;
			dlh->next = dsi;
		} else {
			sih = (struct idtentry *) s;
			snamlen = sih->namlen;

			len = MIN(snamlen, DTIHDRDATALEN);
			dih = (struct idtentry *) h;
			bcopy(sih, dih, 10 + len * 2);
			/*
			 * bcopy(sih, dih, 10 + len);
			 */

			next = sih->next;

			dsi++;
			dih->next = dsi;
		}

		/* free src head/only segment */
		s->next = sfsi;
		s->cnt = 1;
		sfsi = ssi;

		nd++;

		/*
		 * move additional segment(s) of the entry
		 */
		snamlen -= len;
		while ((ssi = next) >= 0) {
			/* get next source segment */
			s = &sp->slot[ssi];

			/* get next destination free slot */
			d++;

			len = MIN(snamlen, DTSLOTDATALEN);
			UniStrncpy(d->name, s->name, len);
			/*
			 * bcopy(s->name, d->name, len);
			 */

			nd++;

			dsi++;
			d->next = dsi;

			/* free source segment */
			next = s->next;
			s->next = sfsi;
			s->cnt = 1;
			sfsi = ssi;

			snamlen -= len;
		}		/* end while */

		/* terminate dst last/only segment */
		if (h == d) {
			/* single segment entry */
			if (dp->header.flag & BT_LEAF)
				dlh->next = -1;
			else
				dih->next = -1;
		} else
			/* multi-segment entry */
			d->next = -1;
	}			/* end for */

	/* update source header */
	sp->header.freelist = sfsi;
	sp->header.freecnt += nd;

	/* update destination header */
	dp->header.nextindex = di;

	dp->header.freelist = dsi;
	dp->header.freecnt -= nd;
}

/*
 *	fsck_dtDeleteEntry()
 *
 * function: free a (leaf/internal) entry
 *
 * log freelist header, stbl, and each segment slot of entry
 * (even though last/only segment next field is modified,
 * physical image logging requires all segment slots of
 * the entry logged to avoid applying previous updates
 * to the same slots)
 */
static void fsck_dtDeleteEntry(dtpage_t * p,	/* directory page */
			       int32_t fi)
{				/* free entry index */
	int32_t fsi;		/* free entry slot index */
	int8_t *stbl;
	struct dtslot *t;
	int32_t si, freecnt;

	/* get free entry slot index */
	stbl = DT_GETSTBL(p);
	fsi = stbl[fi];

	/* get the head/only segment */
	t = &p->slot[fsi];
	if (p->header.flag & BT_LEAF)
		si = ((struct ldtentry *) t)->next;
	else
		si = ((struct idtentry *) t)->next;
	t->next = si;
	t->cnt = 1;

	freecnt = 1;

	/* find the last/only segment */
	while (si >= 0) {
		freecnt++;

		t = &p->slot[si];
		t->cnt = 1;
		si = t->next;
	}

	/* update freelist */
	t->next = p->header.freelist;
	p->header.freelist = fsi;
	p->header.freecnt += freecnt;

	/* if delete from middle,
	 * shift left the succedding entries in the stbl
	 */
	si = p->header.nextindex;
	if (fi < si - 1)
		memmove(&stbl[fi], &stbl[fi + 1], si - fi - 1);

	p->header.nextindex--;
}