fsckdire.c

jfs 源码

		/* 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(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(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 ((sb_ptr->s_flag & JFS_DIR_INDEX) ==
				    JFS_DIR_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;

	/*
	 * the skipped index was on the left page,
	 */
	if (skip <= off) {
		/* insert the new entry in the split page */
		dtInsertEntry(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(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;
	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;

	/*
	 * insert the new entry into the new right/child page
	 * (skip index in the new right page will not change)
	 */
	dtInsertEntry(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);

		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;