log_map.c

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

/*
 *   Copyright (c) International Business Machines Corp., 2000-2002
 *
 *   This program is free software;  you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation; either version 2 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY;  without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See
 *   the GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program;  if not, write to the Free Software
 *   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 */
/*
 *   FUNCTION: log_map.c: recovery manager
 */
#include <config.h>
#include <assert.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <errno.h>
#include "jfs_types.h"
#include "jfs_endian.h"
#include "jfs_filsys.h"
#include "jfs_superblock.h"
#include "jfs_dinode.h"
#include "jfs_dtree.h"
#include "jfs_xtree.h"
#include "jfs_logmgr.h"
#include "jfs_dmap.h"
#include "jfs_imap.h"
#include "logredo.h"
#include "devices.h"
#include "debug.h"
#include "fsck_message.h"		/* for fsck message logging facility */

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  *    R E M E M B E R    M E M O R Y    A L L O C    F A I L U R E
  *
  */
extern int32_t Insuff_memory_for_maps;
extern char *available_stg_addr;
extern int32_t available_stg_bytes;
extern char *bmap_stg_addr;
extern int32_t bmap_stg_bytes;

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  *   L O C A L   M A C R O    D E F I N I T I O N S
  *
  */
#define UZBIT_32        ((uint32_t) (1 << 31 ))

/* The following define is for aggregate block allocation map */
#define SIZEOFDMAPCTL   sizeof(struct dmapctl)

/*
 * At the logredo time, the dmap read into memory to form an array
 * of file pages. The first page is always the aggregate disk allocation
 * map descriptor ( i.e. the bmap control page), the remaining pages are
 * either dmap control pages or dmap pages.
 * given zero origin dmapctl level of the top dmapctl, tlvl,
 * if tlvl == 2, L2 page exists;
 * if tlvl == 1, L2 does not exist,
 *               but L1.n and L0.n pages exist (0 <= n <= 1023);
 * if tlvl == 0, L2 and L1 pages do not exist,
 *               only L0.n pages exist (0 <= n <= 1023);
 */

/* convert disk block number to bmap file page number */
#define BLKTODMAPN(b)\
        (((b) >> 13) + ((b) >> 23) + ((b) >> 33) + 3 + 1)

/* convert dmap block number to bmap file page number */
#define DMAPTOBMAPN(d)\
        ((d) + ((d) >> 10) + ((d) >> 20) + 3 + 1)

/* convert disk block number to allocation group number */
#define BLKNOTOAG(b,l2agsize)   ((b) >> l2agsize)

/* things for the block allocation map */
int16_t top_dmapctl_lvl;	/* zero origin level of the top dmapctl */

 /* + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  *
  *    S T U F F    F O R    T H E    L O G
  *
  *       externals defined in logredo.c
  */
extern struct vopen vopen[];	/* (88) */

#define  fs_next        fsimap_lst.next
#define  fs_fileset     fsimap_lst.fileset
#define  fsimap_ctrl    fsimap_lst.fsimapctrl

/*
 *      file system page buffer cache
 *
 * for k > 0, bufhdr[k] describes contents of buffer[k-1].
 * bufhdr[0] is reserved as anchor for free/lru list:
 * bufhdr[0].next points to the MRU buffer (head),
 * bufhdr[0].prev points to the LRU buffer (tail);
 */
int32_t bhmask = (NBUFPOOL - 1);	/* hash mask for bhash */
int16_t bhash[NBUFPOOL];	/* hashlist anchor table */

/* buffer header table */
extern struct bufhdr {
	int16_t next;		/* 2: next on free/lru list */
	int16_t prev;		/* 2: previous on free/lru list */
	int16_t hnext;		/* 2: next on hash chain */
	int16_t hprev;		/* 2: previous on hash chain */
	char modify;		/* 1: buffer was modified */
	char inuse;		/* 1: buffer on hash chain */
	int16_t reserve;	/* 2 */
	int32_t vol;		/* 4: minor of agrregate/lv number */
	pxd_t pxd;		/* 8: on-disk page pxd */
} bufhdr[];			/* (24) */

/* buffer table */
extern struct bufpool {
	char bytes[PSIZE];
} buffer[];

/*
 *      maptab[]
 *
 * maptab is used for imap. It determines number of zeroes within
 * characters of imap bitmap words. The character values  serve
 * as indexes into the table
 * e.g. if char has value of "3", maptab[2] = 6 which indicates there
 * are 6 zeroes in "3".
 */
unsigned char maptab[256] = {
	8, 7, 7, 6, 7, 6, 6, 5, 7, 6, 6, 5, 6, 5, 5, 4,
	7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
	7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
	7, 6, 6, 5, 6, 5, 5, 4, 6, 5, 5, 4, 5, 4, 4, 3,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
	6, 5, 5, 4, 5, 4, 4, 3, 5, 4, 4, 3, 4, 3, 3, 2,
	5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
	5, 4, 4, 3, 4, 3, 3, 2, 4, 3, 3, 2, 3, 2, 2, 1,
	4, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 0
};

/*
 *      budtab[]
 *
 * used to determine the maximum free string(i.e. buddy size)
 * in a character of a dmap bitmap word.  the values of the character
 * serve as the index into this array and the value of the budtab[]
 * array at that index is the max binary buddy of free bits within
 * the character.
 * e.g. when char = "15" (i.e. 00001111), budtab[15] = 2 because
 * the max free bits is 2**2 (=4).
 *
 */
signed char budtab[256] = {
	3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0,
	2, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, -1
};

/*
 * external references
 */
extern int fsError(int, int, int64_t);
extern int markBmap(struct dmap *, pxd_t, int, int);
extern int bflush(int32_t, struct bufpool *);
extern int alloc_storage(int32_t, void **, int32_t *);
extern int alloc_dmap_bitrec(struct dmap_bitmaps **);

extern int alloc_wrksp(uint32_t, int, int, void **);

/*
 * forward references
 */
int initMaps(int32_t);
int bMapInit(int, struct dinode *);
int bMapRead(int, int32_t, void *);
int bMapWrite(int, int32_t, void *);
int dMapGet(int, int32_t);
int iMapInit(int, struct dinode *);
int iMapRead(int, int32_t, void *);
int iMapWrite(int, int32_t, void *);
int iagGet(int, int32_t);
int updateMaps(int);
int writeImap(int, struct fsimap_lst, struct dinode *);
int updateImapPage(int32_t, struct iag *, int16_t *, int16_t *);
int writeBmap(int, struct dbmap *, struct dinode *);
int updDmapPage(struct dmap *, int32_t, int8_t *);
int rXtree(int32_t, struct dinode *, xtpage_t **);
signed char adjTree(struct dmapctl *, int32_t, int32_t);
static int32_t maxBud(unsigned char *);
int bread(int32_t, pxd_t, void **, int32_t);

/*
 * NAME:        initMaps()
 *
 * FUNCTION:    Logredo() needs to reconstruct fileset imap and Blk alloc map.
 *              In the first release, the aggregate imap is regarding as
 *              static.
 *              In XJFS, the imaps and bmap are dynamically allocated.
 *              At the beginning of logredo, the xtrees for these maps are
 *              the only trustable things. The xtree is rooted
 *              at the inode. So read the inodes first. then call
 *              readMap() to allocate storage for inode and disk maps and
 *              read them into memory. initialize workmaps to zeros.
 */
int initMaps(int32_t vol)
{				/* index in vopen array = minor(volid) */
	int rc;
	struct dinode *dip;
	pxd_t pxd1;

	/*
	 *      initialize in-memory block allocation map
	 */
	/* read in the bmap inode (i_number = 2) in a buffer: */
	PXDaddress(&pxd1, AITBL_OFF >> vopen[vol].l2bsize);
	PXDlength(&pxd1, vopen[vol].lbperpage);
	if ((rc = bread(vol, pxd1, (void **) &dip, PB_READ)) != 0) {
		fsck_send_msg(lrdo_READBMAPINOFAIL, errno);
		return (BREAD_BMAPINIT);
	}

	/* locate the inode in the buffer page */
	dip += BMAP_I;

	/* read block map into memory and init workmap to zeros */
	if ((rc = bMapInit(vol, dip)) != 0) {
		fsck_send_msg(lrdo_READBMAPFAIL);
		return (rc);
	}

	/*
	 *      initialize in-memory fileset inode allocation map
	 */
	/* read in the fileset imap inode (i_number = 16) in a buffer: */
	PXDaddress(&pxd1, (AITBL_OFF + (SIZE_OF_MAP_PAGE << 1)) >> vopen[vol].l2bsize);
	if ((rc = bread(vol, pxd1, (void **) &dip, PB_READ)) != 0) {
		fsck_send_msg(lrdo_READIMAPINOFAIL, errno);
		return (BREAD_IMAPINIT);
	}

	/* locate the inode in the buffer page */
	dip += FILESYSTEM_I & 0x07;

	/* read inode map into memory and init workmap to zeros */
	if ((rc = iMapInit(vol, dip)) != 0) {
		fsck_send_msg(lrdo_READIMAPFAIL);
		return (rc);
	}
	/* Return 0 */
	return (rc);
}

/***************************************************************
 * NAME: 	bMapInit()
 *
 * FUNCTION:	Calculate the number of pages in the block map.  Allocate
 *		an array of records so there is one for each page in the
 *		Aggregate Block Map.  Initialize each array element with the
 *		aggregate offset of the page it describes.
 *
 *		Allocate page buffers for the control page, one dmap page,
 *		and one control page at each Ln level used in this BMap.
 *
 *		Read in the map control page.
 *
 *		Get the bitmaps for the last dMap page and set the
 *		'excess bits' to ones.
 *
 * NOTES:	In order to minimize logredo storage usage (because we
 *		must be able to run during autocheck when there is no
 *		paging space available), we won't actually read in a dmap
 *		page unless/until we need to touch it.  At that point we'll
 *		allocate enough storage to accomodate the dmap's wmap
 *		and pmap only.
 *
 * MORE NOTES:
 *              There are two fields are trustable at the beginning of
 *              the logredo. One is fssize, which is the s_size field in
 *              aggregate superblock converting to number of aggregate
 *              blocks. This size only tells how many struct dmap pages are
 *              need for the bmap. Another is di_size field in struct dinode.
 *              In XJFS, the aggre. bmap xtree  is rooted at aggregate
 *              inode #2. The xtree for map is journaled.
 *              Since a COMMIT_FORCE is used for the transaction of
 *              xtree update, index pages are synced written out at
 *              commit time, we can assume that the xtree as well as
 *              the di_size for map is ok for reading the map pages
 *              at the logredo time.
 *
 *              Allocate storage according to di_size for bmap file.
 *
 *              In XJFS, the bmap is dynamically allocated. Its xtree
 *              is rooted at aggregate inode #2.  The xtree for map is
 *              journaled. Since a COMMIT_FORCE is used for the
 *              transaction of xtree update, index pages are synced
 *              (i.e., written out at commit time), we can assume that
 *              the xtree for map is ok for reading the map pages at
 *              the logredo
 */
int bMapInit(int vol,		/* index in vopen array */
	     struct dinode *dip)
{				/* disk inode of bmap */
	int bmi_rc = 0;
	int32_t ndmaps;
	int I_am_logredo = -1;
	uint32_t bytes_needed = 0;
	caddr_t p0 = NULL;
	xtpage_t *xp;
	int i, j, k, w, pgidx;
	int32_t nbytes, npages, this_page;
	uint32_t *pmap, mask;
	pxd_t pxd;
	int64_t xaddr;

	/*
	 * compute the number pages in the Aggregate Block Map, then
	 * allocate an array of records to describe them.
	 *
	 * Note that we also allocate
	 *      a page so we can start on a page boundary.
	 *      a page for the BMap control page
	 *      a page buffer for reading and writing dmap pages
	 *      a page buffer for reading and writing L0 pages
	 *      a page buffer for reading and writing L1 pages
	 *      a page buffer for reading and writing the L2 page
	 */
	vopen[vol].bmap_page_count = __le64_to_cpu(dip->di_size) / PSIZE;

	bytes_needed = (6 * PSIZE) + (vopen[vol].bmap_page_count * sizeof (struct bmap_wsp));

	ndmaps = ((vopen[vol].fssize + BPERDMAP - 1) >> L2BPERDMAP);

	bmi_rc = alloc_wrksp((uint32_t) bytes_needed, 0, I_am_logredo, (void **) &p0);
	/*
	 * note that failure to allocate the bmap is a special case.
	 *
	 * We can replay the log without updating the bmap and
	 * then tell fsck to run a full check/repair which will
	 * rebuild the bmap.  This would not work with the imap.
	 */
	if ((bmi_rc == 0) && (p0 != NULL)) {	/* we got the storage */
		bmap_stg_addr = p0;
		bmap_stg_bytes = bytes_needed;
	} else {
		fsck_send_msg(lrdo_ALLOC4BMAPFAIL, (long long) __le64_to_cpu(dip->di_size));
		Insuff_memory_for_maps = -1;
		return (0);
	}

	/*
	 * we got the storage.
	 * find the first page boundary and parcel it out.
	 */
	p0 = (char *) (((((size_t) p0) + PSIZE - 1) / PSIZE) * PSIZE);
	vopen[vol].bmap_ctl = (struct dbmap *) p0;
	p0 = (char *) (p0 + PSIZE);
	vopen[vol].L2_pbuf = (struct dmapctl *) p0;
	p0 = (char *) (p0 + PSIZE);
	vopen[vol].L1_pbuf = (struct dmapctl *) p0;
	p0 = (char *) (p0 + PSIZE);
	vopen[vol].L0_pbuf = (struct dmapctl *) p0;
	p0 = (char *) (p0 + PSIZE);
	vopen[vol].dmap_pbuf = (struct dmap *) p0;
	p0 = (char *) (p0 + PSIZE);
	vopen[vol].bmap_wsp = (struct bmap_wsp *) p0;

	/*
	 * set the record to say they are currently empty.
	 */
	vopen[vol].L2_pagenum = -1;
	vopen[vol].L1_pagenum = -1;
	vopen[vol].L0_pagenum = -1;
	vopen[vol].dmap_pagenum = -1;

	/*
	 * Initialize the BMap workspace array with aggregate offsets
	 */
	pgidx = 0;
	/*
	 * read in the leftmost leaf page of the
	 * block allocation map xtree
	 */
	if (rXtree(vol, dip, &xp)) {
		fsck_send_msg(lrdo_RBMPREADXTFAIL);
		return (BMAP_READERROR1);
	}

	/*
	 * in case of leaf root, init next sibling pointer so it will
	 * appear as last non-root leaf page termination
	 */
	if (xp->header.flag & BT_ROOT)
		xp->header.next = 0;

	/*
	 * the leaf pages contain the aggregate offsets we need
	 */
	PXDlength(&pxd, vopen[vol].lbperpage);
	do {
		/*
		 * get extent descriptors from the current leaf
		 */
		for (i = XTENTRYSTART; i < __le16_to_cpu(xp->header.nextindex); i++) {
			xaddr = addressXAD(&xp->xad[i]) << vopen[vol].l2bsize;
			nbytes = lengthXAD(&xp->xad[i]) << vopen[vol].l2bsize;
			npages = nbytes / PSIZE;
			/*
			 * get page offsets from the current extent descriptor
			 */
			for (j = 0; j < npages; j++) {
				vopen[vol].bmap_wsp[pgidx].page_offset = xaddr + (j * PSIZE);
				pgidx++;
			}
		}
		/*
		 * read in the next leaf (if any)
		 */
		xaddr = __le64_to_cpu(xp->header.next);
		if (xaddr) {
			PXDaddress(&pxd, xaddr);
			if (bread(vol, pxd, (void **) &xp, PB_READ)) {
				fsck_send_msg(lrdo_RBMPREADNXTLFFAIL);
				return (BMAP_READERROR3);
			}
		}
	} while (xaddr);

	/*
	 * Now read in the map control page
	 */
	bmi_rc = bMapRead(vol, 0, (void *) vopen[vol].bmap_ctl);
	if (bmi_rc != 0) {
		return (bmi_rc);
	}
	ujfs_swap_dbmap(vopen[vol].bmap_ctl);

	/*
	 * And the last dmap page
	 */
	bmi_rc = dMapGet(vol, (ndmaps - 1));
	if (bmi_rc || Insuff_memory_for_maps)
		return bmi_rc;

	/*
	 * init persistent bit map of last/partial dmap page
	 *
	 * if the last dmap may have bits that are beyond mapsize,
	 * the pmap[] bits for these non-existing blocks have to be
	 * inited as allocated.
	 */
	k = vopen[vol].fssize & (BPERDMAP - 1);
	if (k > 0) {
		this_page = DMAPTOBMAPN(ndmaps - 1);
		pmap = (uint32_t *) & (vopen[vol].bmap_wsp[this_page].dmap_bitmaps->pmap);

		i = k & (DBWORD - 1);	/* valid bits in partial word */
		w = k >> L2DBWORD;	/* number of valid full words */

		/* init last valid/first invalid partial word */