log_map.c

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

		if (nblocks)
			l2leaf++;	/* continue for next L1 */
		else {
			/* more than 1 L1 ? */
			if (k > 0)
				break;	/* build L2 page */
			else {
				/* initialize global bmap page */
				bmap->dn_maxfreebud = *l2leaf;
				goto finalize;
			}
		}
	}			/* for each L1 in a L2 */

	/* initialize global bmap page */
	bmap->dn_maxfreebud = adjTree(l2ptr, L2LPERCTL, L2MAXL1SIZE);

	/*
	 * write out the L2 page to disk
	 */
	ujfs_swap_dmapctl(l2ptr);
	rc = bMapWrite(vol, vopen[vol].L2_pagenum, l2ptr);
	if (rc != 0) {
		return (rc);
	}
	vopen[vol].L2_pagenum = -1;

	/*
	 * finalize bmap control page
	 */
      finalize:
	/*
	 * compute dn_maxag: highest active ag number
	 * (the rightmost allocation group with blocks allocated in it);
	 */
	/* get last ag number: assert(bmap->dn_numag >= 1); */
	i = bmap->dn_numag - 1;

	/* is last ag partial ag ? */
	ag_rem = bmap->dn_mapsize & (bmap->dn_agsize - 1);
	if (ag_rem) {
		/* is last ag active ? */
		if (bmap->dn_agfree[i] < ag_rem) {
			bmap->dn_maxag = i;
			goto agpref;
		} else
			i--;
	}

	/* scan backward for first ag with blocks allocated:
	 * (ag0 must be active from allocation of map itself)
	 */
	for (; i >= 0; i--) {
		if (bmap->dn_agfree[i] < bmap->dn_agsize)
			break;
	}
	bmap->dn_maxag = i;

	/*
	 * compute db_agpref: preferred ag to allocate from
	 * (the leftmost ag with average free space in it);
	 */
      agpref:
	/* get the number of active ags and inacitve ags */
	actags = bmap->dn_maxag + 1;
	inactags = bmap->dn_numag - actags;

	/* determine how many blocks are in the inactive allocation
	 * groups. in doing this, we must account for the fact that
	 * the rightmost group might be a partial group (i.e. file
	 * system size is not a multiple of the group size).
	 */
	inactfree = (inactags
		     && ag_rem) ? ((inactags - 1) << l2agsize) + ag_rem : inactags << l2agsize;

	/* determine how many free blocks are in the active
	 * allocation groups plus the average number of free blocks
	 * within the active ags.
	 */
	actfree = bmap->dn_nfree - inactfree;
	avgfree = actfree / actags;

	/* if the preferred allocation group has not average free space.
	 * re-establish the preferred group as the leftmost
	 * group with average free space.
	 */
	if (bmap->dn_agfree[bmap->dn_agpref] < avgfree) {
		for (bmap->dn_agpref = 0; bmap->dn_agpref < actags; bmap->dn_agpref++) {
			if (bmap->dn_agfree[bmap->dn_agpref] >= avgfree)
				break;
		}
		assert(bmap->dn_agpref < bmap->dn_numag);
	}
	/*
	 * compute db_aglevel, db_agheigth, db_width, db_agstart:
	 * an ag is covered in aglevel dmapctl summary tree,
	 * at agheight level height (from leaf) with agwidth number of nodes
	 * each, which starts at agstart index node of the smmary tree node
	 * array;
	 */
	bmap->dn_aglevel = BMAPSZTOLEV(bmap->dn_agsize);
	l2nl = bmap->dn_agl2size - (L2BPERDMAP + bmap->dn_aglevel * L2LPERCTL);
	bmap->dn_agheigth = l2nl >> 1;
	bmap->dn_agwidth = 1 << (l2nl - (bmap->dn_agheigth << 1));
	for (i = 5 - bmap->dn_agheigth, bmap->dn_agstart = 0, n = 1; i > 0; i--) {
		bmap->dn_agstart += n;
		n <<= 2;
	}

	/*
	 *      write out the control page to disk
	 */
	ujfs_swap_dbmap(bmap);
	rc = bMapWrite(vol, 0, (void *) bmap);
	if (rc != 0) {
		return (rc);
	}

	fsck_send_msg(lrdo_WRBMPDONE);

	return (0);
}

/*
 * NAME:        updDmapPage()
 *
 * FUNCTION:    copies the pmap to the wmap in the dmap.
 *              Rebuild the summary tree for this dmap.
 *              initializes the other fields for struct dmap.
 */
int updDmapPage(struct dmap *p0,	/* pointer to this struct dmap page */
		int32_t nblk,	/* num blks covered by this dmap */
		int8_t * treemax)
{				/* filled in with max free for this dmap */
	struct dmaptree *tp;	/* pointer to dmap tree */
	int8_t *cp;
	uint8_t *ucp;
	int16_t w;

	/* update nblock field according to nblk.
	 * Note that all the dmap page have the same nblock (BPERDMAP)
	 * except the last dmap. Without the extendfs the
	 * last dmap nblock is set properly by mkfs.
	 * With the extendfs, logredo need to take care of
	 * nblock field in case the system crashed after
	 * the transaction for extendfs is committed, but
	 * before the fs superblock was sync-written out.
	 * In that case, we need to reset the last dmap
	 * nblock field according to the fssize in the
	 * unchanged fs superblock.
	 */
	p0->nblocks = nblk;
	tp = &p0->tree;

	/* copy the perm map to the work map.
	 * count the num of free blks in this dmap
	 * Set the initial state for the leaves of the dmap tree
	 * according to the current state of pmap/wmap words.
	 */
	p0->nfree = 0;		/* init nfree field */

	if ((int32_t) (tp->leafidx) != (int32_t) (LEAFIND)) {
		fsck_send_msg(lrdo_UPDMPBADLFIDX);
		return ILLEGAL_LEAF_IND1;
	}
	cp = tp->stree + tp->leafidx;	/*cp points to first leaf of dmap tree */
	for (w = 0; w < LPERDMAP; w++) {
		p0->wmap[w] = p0->pmap[w];
		*(cp + w) = maxBud((unsigned char *) &p0->wmap[w]);
		if (~p0->wmap[w]) {
			ucp = (uint8_t *) & p0->wmap[w];
			p0->nfree += (maptab[*ucp] + maptab[*(ucp + 1)]
				      + maptab[*(ucp + 2)] + maptab[*(ucp + 3)]);
		}
	}

	/*
	 * With the leaves of the dmap initialized
	 * rebuild the dmap's tree.
	 */
	*treemax = adjTree((struct dmapctl *) tp, L2LPERDMAP, BUDMIN);
	return (0);
}

/*
 * NAME:        rXtree()
 *
 * FUNCTION:    return buffer page of leftmost leaf page of the xtree
 *              by traversing down leftmost path of xtree;
 *
 * RETURN:      buffer pointer to the first leaf of the xtree.
 */
int rXtree(int32_t vol,		/* index in vopen array */
	   struct dinode *dp,	/* disk inode of map    */
	   xtpage_t ** first_leaf)
{				/* pointer to first leaf page of map xtree */
	xtpage_t *p;
	caddr_t buf_ptr;
	pxd_t pxd;

	/* start from root in dinode */
	p = (xtpage_t *) & dp->di_btroot;
	/* is this page leaf ? */
	if (p->header.flag & BT_LEAF)
		goto out;

	/* get the pxd of leftmost child page */
	PXDlength(&pxd, vopen[vol].lbperpage);
	PXDaddress(&pxd, addressXAD(&p->xad[XTENTRYSTART]));

	/*
	 * traverse down leftmost child node to the leftmost leaf of xtree
	 */
	do {
		/* read in the leftmost child page */
		if (bread(vol, pxd, (void **) &buf_ptr, PB_READ) != 0) {
			fsck_send_msg(lrdo_RXTREADLFFAIL);
			return (MINOR_ERROR);
		}

		p = (xtpage_t *) buf_ptr;
		/* is this page leaf ? */
		if (p->header.flag & BT_LEAF)
			break;
		else {
			PXDlength(&pxd, vopen[vol].lbperpage);
			PXDaddress(&pxd, addressXAD(&p->xad[XTENTRYSTART]));
		}
	} while (!(p->header.flag & BT_LEAF));

      out:
	*first_leaf = p;

	return (0);
}

/*
 * NAME:        adjTree
 *
 * FUNCTION:    rebuild the tree of a dmap or dmapctl. the tree is fixed size.
 *
 *              for dmap tree, the number of leaf nodes are always LPERDMAP
 *              for a fixed aggregate size, the last dmap page may not
 *              used fully. The the partial unused pmap/wmap bits are marked
 *              as allocated.
 *              For dmapctl tree, the number of leaf nodes are always
 *              LPERCTL. If not 1024 dmaps exist, then the unused leaf
 *              nodes are marked as "-1".
 *
 * PARAMETERS:
 *      tp      - pointer to the current dmap page or dmapctl page
 *      l2leaves- Number of leaf nodes as a power of 2:
 *                for dmap, this is always L2LPERDMAP,
 *                for dmapctl, this is always L2LPERCTL;
 *      l2min   - Number of blocks actually covered by a leaf of the tree
 *                as a power of 2
 *
 * NOTES: This routine first works against the leaves of the tree to calculate
 *      the maximum free string for leaf buddys.  Once this is accomplished the
 *      values of the leaf nodes are bubbled up the tree.
 *
 * RETURNS:
 */
signed char adjTree(struct dmapctl *tp, int32_t l2leaves, int32_t l2min)
{
	int nleaves, l2max, nextbud, budsz, index;
	int l2free, leaf, firstp;
	int16_t nparents;
	signed char *cp0, *pp;
	signed char *cp = tp->stree;	/* Pointer to the top of the stree */

	/*
	 * Determine the number of leaves of the tree
	 */
	nleaves = (1 << l2leaves);

	/*
	 * Determine the maximum free string possible for the leaves.
	 */
	l2max = l2min + l2leaves;

	/*
	 * Combine buddies starting with a buddy size of 1 (i.e. two leaves).
	 *
	 * At a buddy size of 1 two buddy leaves can be combined if both buddies
	 * have a maximum free of l2min; the combination will result in the
	 * left buddy leaf having a maximum free of l2min+1 and the right
	 * buddy leaf changing value to '-1'.
	 *
	 * After processing  all buddies for a current size, process buddies
	 * at the next higher buddy size (i.e. current size * 2) against
	 * the next maximum free level (i.e. current free + 1 ).
	 *
	 * This continues until the maximum possible buddy
	 * combination yields maximum free.
	 *
	 * since the stree is fixed size, the index of the first leaf
	 * is in fixed position, tp->leafidx has this value.
	 */
	for (l2free = l2min, budsz = 1; l2free < l2max; l2free++, budsz = nextbud) {
		nextbud = budsz << 1;
		for (cp0 = cp + tp->leafidx, index = 0; index < nleaves;
		     index += nextbud, cp0 += nextbud) {
			if (*cp0 == l2free && *(cp0 + budsz) == l2free) {
				*cp0 = l2free + 1;
				*(cp0 + budsz) = -1;
			}
		}
	}

	/*
	 * With the leaves having maximum free values,
	 * bubble this information up the stree.
	 * Starting at the leaf node level, each four nodes form a group and
	 * have a parent in the higher level. The parent holds the maximum
	 * free value among its four children.
	 * All lower level nodes are processed in this fashion until we
	 * reach the root.
	 */
	for (leaf = tp->leafidx, nparents = nleaves >> 2;
	     nparents > 0; nparents >>= 2, leaf = firstp) {
		/* get the index of the first parent of the current
		 * leaf level
		 */
		firstp = (leaf - 1) >> 2;

		/*
		 * Process all nodes at the current leaf level.
		 * Parent node pp has the maximum value of its
		 * four children nodes.
		 */
		for (cp0 = cp + leaf, pp = cp + firstp, index = 0;
		     index < nparents; index++, cp0 += 4, pp++) {
			*pp = TREEMAX(cp0);
		}
	}

	return (*cp);
}

/*
 * NAME:        maxBud
 *
 * FUNCTION: Determines the maximum binary buddy string of free
 *              bits within a 32-bits word of the pmap/wmap.
 *
 * PARAMETERS:
 *      cp      - Pointer to wmap or pmap word.
 *
 * RETURNS: Maximum binary buddy of free bits within a dmap word.
 */
static int32_t maxBud(unsigned char *cp)
{
	/* check if the dmap word is all free. if so, the
	 * free buddy size is BUDMIN.
	 */
	if (*((uint32_t *) cp) == 0)
		return (BUDMIN);

	/* check if the dmap word is half free. if so, the
	 * free buddy size is BUDMIN-1.
	 */
	if (*((unsigned short *) cp) == 0 || *((unsigned short *) cp + 1) == 0)
		return (BUDMIN - 1);

	/* not all free or half free. determine the free buddy
	 * size thru table lookup using quarters of the dmap word.
	 */
	return (MAX(MAX(budtab[*cp], budtab[*(cp + 1)]),
		    MAX(budtab[*(cp + 2)], budtab[*(cp + 3)])));
}

/*
 * NAME:        bread ()
 *
 * FUNCTION:    return with buf set to pointer of page in buffer pool
 *              containing disk page specified by pxd.
 *              the parameter update specifies the caller's intentions.
 *
 * NOTE:        offset_t is "long long" type.
 */
int bread(int32_t vol,		/* index in vopen (minor of aggregate)  */
	  pxd_t pxd,		/* on-disk page pxd                     */
	  void **buf,		/* set to point to buffer pool page     */
	  int32_t update)
{				/* true if buffer will be modified      */
	FILE *fp;
	int rc;
	int32_t k, hash, oldhash, nxt, prv, found, head;
	int32_t nblocks, nbytes;
	int64_t blkno;		/* number of agge. blks in pxd */

	/* verify that pxd is within aggregate range */
	nblocks = lengthPXD(&pxd);
	blkno = addressPXD(&pxd);
	if (vopen[vol].bmap_ctl != NULL && (blkno + nblocks) > vopen[vol].fssize) {
		fsError(DBTYPE, vol, blkno);
		fsck_send_msg(lrdo_BRDBADBLOCK, (long long) blkno);
		return (MINOR_ERROR);
	}

	/* search buffer pool for specified page */
	hash = (blkno ^ vol) & bhmask;
	for (k = bhash[hash]; k != 0; k = bufhdr[k].hnext) {
		if (addressPXD(&bufhdr[k].pxd) == blkno &&
		    lengthPXD(&bufhdr[k].pxd) >= nblocks && bufhdr[k].vol == vol)
			break;
	}

	/* was it in buffer pool ? */
	found = (k != 0);
	k = (found) ? k : bufhdr[0].prev;

	/* remove k from current position in lru list */
	nxt = bufhdr[k].next;
	prv = bufhdr[k].prev;
	bufhdr[nxt].prev = prv;
	bufhdr[prv].next = nxt;

	/* move k to head of lru list */
	head = bufhdr[0].next;
	bufhdr[k].next = head;
	bufhdr[head].prev = k;
	bufhdr[k].prev = 0;
	bufhdr[0].next = k;

	/* bufhdr[k] describes buffer[k-1] */
	*buf = &buffer[k - 1];

	/*
	 * buffer has been reclaimed: update modify bit and return
	 */
	if (found) {
		bufhdr[k].modify |= update;
		return (0);
	}

	/*
	 * buffer is to be recycled:
	 */
	/* write it out if it was modified */
	if (bufhdr[k].inuse && bufhdr[k].modify) {
		if ((rc = bflush(k, &buffer[k - 1])) != 0)
			return (rc);
	}

	/* remove it from hash chain if necessary.
	 * hprev is 0 if it is at head of hash chain.
	 */
	if (bufhdr[k].inuse) {
		nxt = bufhdr[k].hnext;
		prv = bufhdr[k].hprev;
		if (prv == 0) {
			oldhash = (bufhdr[k].vol ^ addressPXD(&bufhdr[k].pxd)) & bhmask;
			bhash[oldhash] = nxt;
		} else {
			bufhdr[prv].hnext = nxt;
		}
		/* next assign is ok even if nxt is 0 */
		bufhdr[nxt].hprev = prv;
	}
	/* insert k at head of new hash chain */
	head = bhash[hash];
	bufhdr[k].hnext = head;
	bufhdr[k].hprev = 0;
	bufhdr[head].hprev = k;	/* ok even if head = 0 */
	bhash[hash] = k;

	/* fill in bufhdr with new data and read the page in */
	bufhdr[k].vol = vol;
	bufhdr[k].pxd = pxd;
	bufhdr[k].inuse = 1;
	bufhdr[k].modify = update;

	fp = vopen[vol].fp;
	nbytes = nblocks << vopen[vol].l2bsize;
	rc = ujfs_rw_diskblocks(fp,
				(uint64_t) (blkno << vopen[vol].l2bsize),
				(unsigned) nbytes, (char *) &buffer[k - 1], GET);
	if (rc != 0) {
		fsError(IOERROR, vol, blkno);
		fsck_send_msg(lrdo_BRDREADBLKFAIL, (long long) blkno);
		return (MINOR_ERROR);
	}

	return (0);
}