jfs_xtree.c

jfs-2.4-1.1.7.tar.gz jfs 2.4－1.1.7 源码

/*
 *   Copyright (C) International Business Machines Corp., 2000-2003
 *
 *   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
 */
/*
 *      jfs_xtree.c: extent allocation descriptor B+-tree manager
 */

#include <linux/fs.h>
#include "jfs_incore.h"
#include "jfs_filsys.h"
#include "jfs_metapage.h"
#include "jfs_dmap.h"
#include "jfs_dinode.h"
#include "jfs_superblock.h"
#include "jfs_debug.h"

/*
 * xtree local flag
 */
#define XT_INSERT       0x00000001

/*
 *       xtree key/entry comparison: extent offset
 *
 * return:
 *      -1: k < start of extent
 *       0: start_of_extent <= k <= end_of_extent
 *       1: k > end_of_extent
 */
#define XT_CMP(CMP, K, X, OFFSET64)\
{\
        OFFSET64 = offsetXAD(X);\
        (CMP) = ((K) >= OFFSET64 + lengthXAD(X)) ? 1 :\
              ((K) < OFFSET64) ? -1 : 0;\
}

/* write a xad entry */
#define XT_PUTENTRY(XAD, FLAG, OFF, LEN, ADDR)\
{\
        (XAD)->flag = (FLAG);\
        XADoffset((XAD), (OFF));\
        XADlength((XAD), (LEN));\
        XADaddress((XAD), (ADDR));\
}

#define XT_PAGE(IP, MP) BT_PAGE(IP, MP, xtpage_t, i_xtroot)

/* get page buffer for specified block address */
/* ToDo: Replace this ugly macro with a function */
#define XT_GETPAGE(IP, BN, MP, SIZE, P, RC)\
{\
	BT_GETPAGE(IP, BN, MP, xtpage_t, SIZE, P, RC, i_xtroot)\
	if (!(RC))\
	{\
		if ((le16_to_cpu((P)->header.nextindex) < XTENTRYSTART) ||\
		    (le16_to_cpu((P)->header.nextindex) > le16_to_cpu((P)->header.maxentry)) ||\
		    (le16_to_cpu((P)->header.maxentry) > (((BN)==0)?XTROOTMAXSLOT:PSIZE>>L2XTSLOTSIZE)))\
		{\
			jfs_error((IP)->i_sb, "XT_GETPAGE: xtree page corrupt");\
			BT_PUTPAGE(MP);\
			MP = NULL;\
			RC = -EIO;\
		}\
        }\
}

/* for consistency */
#define XT_PUTPAGE(MP) BT_PUTPAGE(MP)

#define XT_GETSEARCH(IP, LEAF, BN, MP,  P, INDEX) \
	BT_GETSEARCH(IP, LEAF, BN, MP, xtpage_t, P, INDEX, i_xtroot)
/* xtree entry parameter descriptor */
struct xtsplit {
	struct metapage *mp;
	s16 index;
	u8 flag;
	s64 off;
	s64 addr;
	int len;
	struct pxdlist *pxdlist;
};


/*
 *      statistics
 */
#ifdef CONFIG_JFS_STATISTICS
static struct {
	uint search;
	uint fastSearch;
	uint split;
} xtStat;
#endif


/*
 * forward references
 */
static int xtSearch(struct inode *ip,
		    s64 xoff, int *cmpp, struct btstack * btstack, int flag);

static int xtSplitUp(tid_t tid,
		     struct inode *ip,
		     struct xtsplit * split, struct btstack * btstack);

static int xtSplitPage(tid_t tid, struct inode *ip, struct xtsplit * split,
		       struct metapage ** rmpp, s64 * rbnp);

static int xtSplitRoot(tid_t tid, struct inode *ip,
		       struct xtsplit * split, struct metapage ** rmpp);

#ifdef _STILL_TO_PORT
static int xtDeleteUp(tid_t tid, struct inode *ip, struct metapage * fmp,
		      xtpage_t * fp, struct btstack * btstack);

static int xtSearchNode(struct inode *ip,
			xad_t * xad,
			int *cmpp, struct btstack * btstack, int flag);

static int xtRelink(tid_t tid, struct inode *ip, xtpage_t * fp);
#endif				/*  _STILL_TO_PORT */

/* External references */

/*
 *      debug control
 */
/*      #define _JFS_DEBUG_XTREE        1 */


/*
 *      xtLookup()
 *
 * function: map a single page into a physical extent;
 */
int xtLookup(struct inode *ip, s64 lstart,
	     s64 llen, int *pflag, s64 * paddr, s32 * plen, int no_check)
{
	int rc = 0;
	struct btstack btstack;
	int cmp;
	s64 bn;
	struct metapage *mp;
	xtpage_t *p;
	int index;
	xad_t *xad;
	s64 size, xoff, xend;
	int xlen;
	s64 xaddr;

	*plen = 0;

	if (!no_check) {
		/* is lookup offset beyond eof ? */
		size = ((u64) ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
		    JFS_SBI(ip->i_sb)->l2bsize;
		if (lstart >= size) {
			jfs_err("xtLookup: lstart (0x%lx) >= size (0x%lx)",
				(ulong) lstart, (ulong) size);
			return 0;
		}
	}

	/*
	 * search for the xad entry covering the logical extent
	 */
//search:
	if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0))) {
		jfs_err("xtLookup: xtSearch returned %d", rc);
		return rc;
	}

	/*
	 *      compute the physical extent covering logical extent
	 *
	 * N.B. search may have failed (e.g., hole in sparse file),
	 * and returned the index of the next entry.
	 */
	/* retrieve search result */
	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);

	/* is xad found covering start of logical extent ?
	 * lstart is a page start address,
	 * i.e., lstart cannot start in a hole;
	 */
	if (cmp)
		goto out;

	/*
	 * lxd covered by xad
	 */
	xad = &p->xad[index];
	xoff = offsetXAD(xad);
	xlen = lengthXAD(xad);
	xend = xoff + xlen;
	xaddr = addressXAD(xad);

	/* initialize new pxd */
	*pflag = xad->flag;
	*paddr = xaddr + (lstart - xoff);
	/* a page must be fully covered by an xad */
	*plen = min(xend - lstart, llen);

      out:
	XT_PUTPAGE(mp);

	return rc;
}


/*
 *      xtLookupList()
 *
 * function: map a single logical extent into a list of physical extent;
 *
 * parameter:
 *      struct inode    *ip,
 *      struct lxdlist  *lxdlist,       lxd list (in)
 *      struct xadlist  *xadlist,       xad list (in/out)
 *      int		flag)
 *
 * coverage of lxd by xad under assumption of
 * . lxd's are ordered and disjoint.
 * . xad's are ordered and disjoint.
 *
 * return:
 *      0:      success
 *
 * note: a page being written (even a single byte) is backed fully,
 *      except the last page which is only backed with blocks
 *      required to cover the last byte;
 *      the extent backing a page is fully contained within an xad;
 */
int xtLookupList(struct inode *ip, struct lxdlist * lxdlist,
		 struct xadlist * xadlist, int flag)
{
	int rc = 0;
	struct btstack btstack;
	int cmp;
	s64 bn;
	struct metapage *mp;
	xtpage_t *p;
	int index;
	lxd_t *lxd;
	xad_t *xad, *pxd;
	s64 size, lstart, lend, xstart, xend, pstart;
	s64 llen, xlen, plen;
	s64 xaddr, paddr;
	int nlxd, npxd, maxnpxd;

	npxd = xadlist->nxad = 0;
	maxnpxd = xadlist->maxnxad;
	pxd = xadlist->xad;

	nlxd = lxdlist->nlxd;
	lxd = lxdlist->lxd;

	lstart = offsetLXD(lxd);
	llen = lengthLXD(lxd);
	lend = lstart + llen;

	size = (ip->i_size + (JFS_SBI(ip->i_sb)->bsize - 1)) >>
	    JFS_SBI(ip->i_sb)->l2bsize;

	/*
	 * search for the xad entry covering the logical extent
	 */
      search:
	if (lstart >= size)
		return 0;

	if ((rc = xtSearch(ip, lstart, &cmp, &btstack, 0)))
		return rc;

	/*
	 *      compute the physical extent covering logical extent
	 *
	 * N.B. search may have failed (e.g., hole in sparse file),
	 * and returned the index of the next entry.
	 */
//map:
	/* retrieve search result */
	XT_GETSEARCH(ip, btstack.top, bn, mp, p, index);

	/* is xad on the next sibling page ? */
	if (index == le16_to_cpu(p->header.nextindex)) {
		if (p->header.flag & BT_ROOT)
			goto mapend;

		if ((bn = le64_to_cpu(p->header.next)) == 0)
			goto mapend;

		XT_PUTPAGE(mp);

		/* get next sibling page */
		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
		if (rc)
			return rc;

		index = XTENTRYSTART;
	}

	xad = &p->xad[index];

	/*
	 * is lxd covered by xad ?
	 */
      compare:
	xstart = offsetXAD(xad);
	xlen = lengthXAD(xad);
	xend = xstart + xlen;
	xaddr = addressXAD(xad);

      compare1:
	if (xstart < lstart)
		goto compare2;

	/* (lstart <= xstart) */

	/* lxd is NOT covered by xad */
	if (lend <= xstart) {
		/*
		 * get next lxd
		 */
		if (--nlxd == 0)
			goto mapend;
		lxd++;

		lstart = offsetLXD(lxd);
		llen = lengthLXD(lxd);
		lend = lstart + llen;
		if (lstart >= size)
			goto mapend;

		/* compare with the current xad  */
		goto compare1;
	}
	/* lxd is covered by xad */
	else {			/* (xstart < lend) */

		/* initialize new pxd */
		pstart = xstart;
		plen = min(lend - xstart, xlen);
		paddr = xaddr;

		goto cover;
	}

	/* (xstart < lstart) */
      compare2:
	/* lxd is covered by xad */
	if (lstart < xend) {
		/* initialize new pxd */
		pstart = lstart;
		plen = min(xend - lstart, llen);
		paddr = xaddr + (lstart - xstart);

		goto cover;
	}
	/* lxd is NOT covered by xad */
	else {			/* (xend <= lstart) */

		/*
		 * get next xad
		 *
		 * linear search next xad covering lxd on
		 * the current xad page, and then tree search
		 */
		if (index == le16_to_cpu(p->header.nextindex) - 1) {
			if (p->header.flag & BT_ROOT)
				goto mapend;

			XT_PUTPAGE(mp);
			goto search;
		} else {
			index++;
			xad++;

			/* compare with new xad */
			goto compare;
		}
	}

	/*
	 * lxd is covered by xad and a new pxd has been initialized
	 * (lstart <= xstart < lend) or (xstart < lstart < xend)
	 */
      cover:
	/* finalize pxd corresponding to current xad */
	XT_PUTENTRY(pxd, xad->flag, pstart, plen, paddr);

	if (++npxd >= maxnpxd)
		goto mapend;
	pxd++;

	/*
	 * lxd is fully covered by xad
	 */
	if (lend <= xend) {
		/*
		 * get next lxd
		 */
		if (--nlxd == 0)
			goto mapend;
		lxd++;

		lstart = offsetLXD(lxd);
		llen = lengthLXD(lxd);
		lend = lstart + llen;
		if (lstart >= size)
			goto mapend;

		/*
		 * test for old xad covering new lxd
		 * (old xstart < new lstart)
		 */
		goto compare2;
	}
	/*
	 * lxd is partially covered by xad
	 */
	else {			/* (xend < lend)  */

		/*
		 * get next xad
		 *
		 * linear search next xad covering lxd on
		 * the current xad page, and then next xad page search
		 */
		if (index == le16_to_cpu(p->header.nextindex) - 1) {
			if (p->header.flag & BT_ROOT)
				goto mapend;

			if ((bn = le64_to_cpu(p->header.next)) == 0)
				goto mapend;

			XT_PUTPAGE(mp);

			/* get next sibling page */
			XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
			if (rc)
				return rc;

			index = XTENTRYSTART;
			xad = &p->xad[index];
		} else {
			index++;
			xad++;
		}

		/*
		 * test for new xad covering old lxd
		 * (old lstart < new xstart)
		 */
		goto compare;
	}

      mapend:
	xadlist->nxad = npxd;

//out:
	XT_PUTPAGE(mp);

	return rc;
}


/*
 *      xtSearch()
 *
 * function:    search for the xad entry covering specified offset.
 *
 * parameters:
 *      ip      - file object;
 *      xoff    - extent offset;
 *      cmpp    - comparison result:
 *      btstack - traverse stack;
 *      flag    - search process flag (XT_INSERT);
 *
 * returns:
 *      btstack contains (bn, index) of search path traversed to the entry.
 *      *cmpp is set to result of comparison with the entry returned.
 *      the page containing the entry is pinned at exit.
 */
static int xtSearch(struct inode *ip, s64 xoff,	/* offset of extent */
		    int *cmpp, struct btstack * btstack, int flag)
{
	struct jfs_inode_info *jfs_ip = JFS_IP(ip);
	int rc = 0;
	int cmp = 1;		/* init for empty page */
	s64 bn;			/* block number */
	struct metapage *mp;	/* page buffer */
	xtpage_t *p;		/* page */
	xad_t *xad;
	int base, index, lim, btindex;
	struct btframe *btsp;
	int nsplit = 0;		/* number of pages to split */
	s64 t64;

	INCREMENT(xtStat.search);

	BT_CLR(btstack);

	btstack->nsplit = 0;

	/*
	 *      search down tree from root:
	 *
	 * between two consecutive entries of <Ki, Pi> and <Kj, Pj> of
	 * internal page, child page Pi contains entry with k, Ki <= K < Kj.
	 *
	 * if entry with search key K is not found
	 * internal page search find the entry with largest key Ki
	 * less than K which point to the child page to search;
	 * leaf page search find the entry with smallest key Kj
	 * greater than K so that the returned index is the position of
	 * the entry to be shifted right for insertion of new entry.
	 * for empty tree, search key is greater than any key of the tree.
	 *
	 * by convention, root bn = 0.
	 */
	for (bn = 0;;) {
		/* get/pin the page to search */
		XT_GETPAGE(ip, bn, mp, PSIZE, p, rc);
		if (rc)
			return rc;

		/* try sequential access heuristics with the previous
		 * access entry in target leaf page:
		 * once search narrowed down into the target leaf,
		 * key must either match an entry in the leaf or
		 * key entry does not exist in the tree;