fsckdire.c

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

		rc = dtSplitRoot(ip, split, &rbp);

		FSCK_BT_PUTPAGE(rbp);
		FSCK_BT_PUTPAGE(sbp);

		ip->di_size = xlen << agg_recptr->log2_blksize;

		return rc;
	}

	/*
	 *      split leaf page <sp> into <sp> and a new right page <rp>.
	 *
	 *  return <rp> pinned and its extent descriptor <rpxd>
	 *
	 *  allocate new directory page extent and
	 *  new index page(s) to cover page split(s)
	 *
	 *  allocation hint: ?
	 */
	n = btstack->nsplit;
	pxdlist.maxnpxd = pxdlist.npxd = 0;
	xlen = agg_recptr->blksperpg;
	for (pxd = pxdlist.pxd; n > 0; n--, pxd++) {
		rc = fsck_alloc_fsblks(xlen, &xaddr);
		if (rc == 0) {
			PXDaddress(pxd, xaddr);
			PXDlength(pxd, xlen);
			pxdlist.maxnpxd++;
			continue;
		}

		FSCK_BT_PUTPAGE(sbp);

		/* undo allocation */
		goto splitOut;
	}

	split->pxdlist = &pxdlist;
	rc = dtSplitPage(ip, split, &rbp, &rpxd);
	if (rc) {
		FSCK_BT_PUTPAGE(sbp);

		/* undo allocation */
		goto splitOut;
	}

	ip->di_size += PSIZE;

	/*
	 * propagate up the router entry for the leaf page just split
	 *
	 * insert a router entry for the new page into the parent page,
	 * propagate the insert/split up the tree by walking back the stack
	 * of (bn of parent page, index of child page entry in parent page)
	 * that were traversed during the search for the page that split.
	 *
	 * the propagation of insert/split up the tree stops if the root
	 * splits or the page inserted into doesn't have to split to hold
	 * the new entry.
	 *
	 * the parent entry for the split page remains the same, and
	 * a new entry is inserted at its right with the first key and
	 * block number of the new right page.
	 *
	 * There are a maximum of 4 pages pinned at any time:
	 * two children, left parent and right parent (when the parent splits).
	 * keep the child pages pinned while working on the parent.
	 * make sure that all pins are released at exit.
	 */
	while ((parent = BT_POP(btstack)) != NULL) {
		/* parent page specified by stack frame <parent> */
		/* keep current child pages (<lp>, <rp>) pinned */
		lbp = sbp;
		lp = sp;
		rp = FSCK_BT_PAGE(ip, rbp, dtpage_t);

		/*
		 * insert router entry in parent for new right child page <rp>
		 *
		 * get the parent page <sp>
		 */
		FSCK_BT_GETPAGE(ip, parent->bn, sbp, dtpage_t, sp, rc);
		if (rc) {
			FSCK_BT_PUTPAGE(lbp);
			FSCK_BT_PUTPAGE(rbp);
			goto splitOut;
		}

		/*
		 * The new key entry goes ONE AFTER the index of parent entry,
		 * because the split was to the right.
		 */
		skip = parent->index + 1;

		/*
		 * compute the key for the router entry
		 *
		 * key suffix compression:
		 * for internal pages that have leaf pages as children,
		 * retain only what's needed to distinguish between
		 * the new entry and the entry on the page to its left.
		 * If the keys compare equal, retain the entire key.
		 *
		 * note that compression is performed only at computing
		 * router key at the lowest internal level.
		 * further compression of the key between pairs of higher
		 * level internal pages loses too much information and
		 * the search may fail.
		 * (e.g., two adjacent leaf pages of {a, ..., x} {xx, ...,}
		 * results in two adjacent parent entries (a)(xx).
		 * if split occurs between these two entries, and
		 * if compression is applied, the router key of parent entry
		 * of right page (x) will divert search for x into right
		 * subtree and miss x in the left subtree.)
		 *
		 * the entire key must be retained for the next-to-leftmost
		 * internal key at any level of the tree, or search may fail
		 * (e.g., ?)
		 */
		switch (rp->header.flag & BT_TYPE) {
		case BT_LEAF:
			/*
			 * compute the length of prefix for suffix compression
			 * between last entry of left page and first entry
			 * of right page
			 */
			if ((sp->header.flag & BT_ROOT && skip > 1) ||
			    sp->header.prev != 0 || skip > 1) {
				/* compute uppercase router prefix key */
				ciGetLeafPrefixKey(lp, lp->header.nextindex - 1,
						   rp, 0, &key, sb_ptr->s_flag);
			} else {
				/* next to leftmost entry of lowest internal level */
				/* compute uppercase router key */
				dtGetKey(rp, 0, &key);

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

			n = NDTINTERNAL(key.namlen);
			break;

		case BT_INTERNAL:
			dtGetKey(rp, 0, &key);
			n = NDTINTERNAL(key.namlen);
			break;

		default:
#ifdef _JFS_DEBUG
			printf("dtSplitUp(): UFO!\n");
#endif
			break;
		}

		/* unpin left child page */
		FSCK_BT_PUTPAGE(lbp);

		/*
		 * compute the data for the router entry
		 */
		/* child page xd */
		data->xd = rpxd;

		/*
		 * parent page is full - split the parent page
		 */
		if (n > sp->header.freecnt) {
			/* init for parent page split */
			split->bp = sbp;
			/* index at insert */
			split->index = skip;
			split->nslot = n;
			split->key = &key;
			/* split->data = data; */

			/* unpin right child page */
			FSCK_BT_PUTPAGE(rbp);

			/* The split routines insert the new entry,
			 * acquire txLock as appropriate.
			 * return <rp> pinned and its block number <rbn>.
			 */
			rc = (sp->header.flag & BT_ROOT) ?
			    dtSplitRoot(ip, split, &rbp) : dtSplitPage(ip,
								       split,
								       &rbp,
								       &rpxd);
			if (rc) {
				FSCK_BT_PUTPAGE(sbp);
				goto splitOut;
			}

			/* sbp and rbp are pinned */
		} else {
			/*
			 * parent page is not full - insert router entry in parent page
			 */
			dtInsertEntry(ip, sp, skip, &key, data);

			/* exit propagate up */
			break;
		}
	}

	/* unpin current split and its right page */
	FSCK_BT_PUTPAGE(sbp);
	FSCK_BT_PUTPAGE(rbp);

	/*
	 * free remaining extents allocated for split
	 */
      splitOut:
	n = pxdlist.npxd;
	pxd = &pxdlist.pxd[n];
	for (; n < pxdlist.maxnpxd; n++, pxd++)
		fsck_dealloc_fsblks(lengthPXD(pxd), (int64_t) addressPXD(pxd));

	return rc;
}

/*
 *	dtSplitPage()
 *
 * function: Split a non-root page of a btree.
 *
 * parameter:
 *
 * return: 0 - success;
 *	   errno - failure;
 *	return split and new page pinned;
 */
static int dtSplitPage(struct dinode *ip, struct dtsplit *split,
		       struct btpage **rbpp, pxd_t * rpxdp)
{
	int rc = 0;
	struct btpage *sbp;
	dtpage_t *sp;
	struct btpage *rbp;
	dtpage_t *rp;		/* new right page allocated */
	int64_t rbn;		/* new right page block number */
	struct btpage *bp;
	dtpage_t *p = 0;
	int64_t nextbn;
	struct pxdlist *pxdlist;
	pxd_t *pxd;
	int32_t skip, nextindex, half, left, nxt, off, si;
	struct ldtentry *ldtentry;
	struct idtentry *idtentry;
	uint8_t *stbl;
	struct dtslot *f;
	int32_t fsi, stblsize;
	int32_t n;

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

	/*
	 * allocate the new right page for the split
	 */
	pxdlist = split->pxdlist;
	pxd = &pxdlist->pxd[pxdlist->npxd];
	pxdlist->npxd++;
	rbn = addressPXD(pxd);
	recon_dnode_assign(rbn, (dtpage_t **) & rbp);
	/* rbp->b_lblkno = rbn; */
#ifdef _JFS_DEBUG
	printf("split: ip:0x%08x sbp:0x%08x rbp:0x%08x\n", ip, sbp, rbp);
#endif
	rp = (dtpage_t *) rbp;
	rp->header.self = *pxd;

	/*
	 * initialize/update sibling pointers between sp and rp
	 */
	nextbn = sp->header.next;
	rp->header.next = nextbn;
	rp->header.prev = addressPXD(&sp->header.self);
	sp->header.next = rbn;

	/*
	 * initialize new right page
	 */
	rp->header.flag = sp->header.flag;

	/* compute sorted entry table at start of extent data area */
	rp->header.nextindex = 0;
	rp->header.stblindex = 1;

	n = PSIZE >> L2DTSLOTSIZE;
	rp->header.maxslot = n;
	/* in unit of slot */
	stblsize = (n + 31) >> L2DTSLOTSIZE;

	/* init freelist */
	fsi = rp->header.stblindex + stblsize;
	rp->header.freelist = fsi;
	rp->header.freecnt = rp->header.maxslot - fsi;

	/*
	 *      sequential append at tail: append without split
	 *
	 * If splitting the last page on a level because of appending
	 * a entry to it (skip is maxentry), it's likely that the access is
	 * sequential. Adding an empty page on the side of the level is less
	 * work and can push the fill factor much higher than normal.
	 * If we're wrong it's no big deal, we'll just do the split the right
	 * way next time.
	 * (It may look like it's equally easy to do a similar hack for
	 * reverse sorted data, that is, split the tree left,
	 * but it's not. Be my guest.)
	 */
	if (nextbn == 0 && split->index == sp->header.nextindex) {
		/*
		 * initialize freelist of new right page
		 */
		f = &rp->slot[fsi];
		for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
			f->next = fsi;
		f->next = -1;

		/* insert entry at the first entry of the new right page */
		dtInsertEntry(ip, rp, 0, split->key, split->data);

		goto out;
	}

	/*
	 *      non-sequential insert (at possibly middle page)
	 *
	 *  update prev pointer of previous right sibling page;
	 */
	if (nextbn != 0) {
		FSCK_BT_GETPAGE(ip, nextbn, bp, dtpage_t, p, rc);
		if (rc) {
			recon_dnode_release((dtpage_t *) rbp);
			return rc;
		}

		p->header.prev = rbn;

		FSCK_BT_PUTPAGE(bp);
	}

	/*
	 * split the data between the split and right pages.
	 */
	skip = split->index;
	half = (PSIZE >> L2DTSLOTSIZE) >> 1;	/* swag */
	left = 0;

	/*
	 *      compute fill factor for split pages
	 *
	 *  <nxt> traces the next entry to move to rp
	 *  <off> traces the next entry to stay in sp
	 */
	stbl = (uint8_t *) & sp->slot[sp->header.stblindex];
	nextindex = sp->header.nextindex;
	for (nxt = off = 0; nxt < nextindex; ++off) {
		if (off == skip)
			/* check for fill factor with new entry size */
			n = split->nslot;
		else {
			si = stbl[nxt];
			switch (sp->header.flag & BT_TYPE) {
			case BT_LEAF:
				ldtentry = (struct ldtentry *) &sp->slot[si];
				if (DO_INDEX())
					n = NDTLEAF(ldtentry->namlen);
				else
					n = NDTLEAF_LEGACY(ldtentry->namlen);
				break;

			case BT_INTERNAL:
				idtentry = (struct idtentry *) &sp->slot[si];
				n = NDTINTERNAL(idtentry->namlen);
				break;

			default:
				break;
			}

			++nxt;	/* advance to next entry to move in sp */
		}

		left += n;
		if (left >= half)
			break;
	}

	/* <nxt> poins to the 1st entry to move */

	/*
	 *      move entries to right page
	 *
	 *  dtMoveEntry() initializes rp and reserves entry for insertion
	 */
	dtMoveEntry(sp, nxt, rp);

	sp->header.nextindex = nxt;

	/*
	 * finalize freelist of new right page
	 */
	fsi = rp->header.freelist;
	f = &rp->slot[fsi];
	for (fsi++; fsi < rp->header.maxslot; f++, fsi++)
		f->next = fsi;
	f->next = -1;

	/*
	 * Update directory index table for entries now in right page
	 */
	if ((rp->header.flag & BT_LEAF) && DO_INDEX()) {
		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);
		}
	}

	/*
	 * the skipped index was on the left page,
	 */
	if (skip <= off) {
		/* insert the new entry in the split page */
		dtInsertEntry(ip, sp, skip, split->key, split->data);
	} else {
		/*
		 * the skipped index was on the right page,
		 */
		/* adjust the skip index to reflect the new position */
		skip -= nxt;

		/* insert the new entry in the right page */
		dtInsertEntry(ip, rp, skip, split->key, split->data);
	}

      out:
	*rbpp = rbp;
	*rpxdp = *pxd;

#ifdef _JFS_DEBUG
	printf("split: ip:0x%08x sbp:0x%08x rbp:0x%08x\n", ip, sbp, rbp);
#endif

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

/*
 *	dtSplitRoot()
 *
 * function:
 *	split the full root page into
 *	original/root/split page and new right page
 *	i.e., root remains fixed in tree anchor (inode) and
 *	the root is copied to a single new right child page
 *	since root page << non-root page, and
 *	the split root page contains a single entry for the
 *	new right child page.
 *
 * parameter:
 *
 * return: 0 - success;
 *	   errno - failure;
 *	return new page pinned;
 */
static int dtSplitRoot(struct dinode *ip, struct dtsplit *split,
		       struct btpage **rbpp)
{
	dtroot_t *sp;
	struct btpage *rbp;
	dtpage_t *rp;
	int64_t rbn;
	int32_t xlen;
	int32_t xsize;
	struct dtslot *f;
	int8_t *stbl;
	int32_t fsi, stblsize, n;
	struct idtentry *s;
	pxd_t *ppxd;
	struct pxdlist *pxdlist;
	pxd_t *pxd;

	/* get split root page */
	sp = (dtroot_t *) & ip->di_btroot;

	/*
	 *      allocate/initialize a single (right) child page
	 *
	 * N.B. In normal processing,
	 *             at first split, a one (or two) block to fit
	 *             new entry is allocated; at subsequent split,
	 *             a full page is allocated;
	 *      During fsck processing,
	 *             at first split a full page is allocated.
	 */
	pxdlist = split->pxdlist;
	pxd = &pxdlist->pxd[pxdlist->npxd];
	pxdlist->npxd++;
	rbn = addressPXD(pxd);
	xlen = lengthPXD(pxd);
	xsize = xlen << agg_recptr->log2_blksize;
	recon_dnode_assign(rbn, (dtpage_t **) & rbp);
	/* rbp->b_lblkno = rbn; */

	rp = (dtpage_t *) rbp;
	rp->header.flag = (sp->header.flag & BT_LEAF) ? BT_LEAF : BT_INTERNAL;
	rp->header.self = *pxd;

	/* initialize sibling pointers */
	rp->header.next = 0;
	rp->header.prev = 0;

	/*
	 *      move in-line root page into new right page extent
	 */
	n = xsize >> L2DTSLOTSIZE;