jfs_dmap.c

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

/*
 *   Copyright (C) International Business Machines Corp., 2000-2004
 *
 *   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
 */

#include <linux/fs.h>
#include "jfs_incore.h"
#include "jfs_superblock.h"
#include "jfs_dmap.h"
#include "jfs_imap.h"
#include "jfs_lock.h"
#include "jfs_metapage.h"
#include "jfs_superblock.h"
#include "jfs_debug.h"

/*
 *	Debug code for double-checking block map
 */
/* #define	_JFS_DEBUG_DMAP	1 */

#ifdef	_JFS_DEBUG_DMAP
#define DBINITMAP(size,ipbmap,results) \
	DBinitmap(size,ipbmap,results)
#define DBALLOC(dbmap,mapsize,blkno,nblocks) \
	DBAlloc(dbmap,mapsize,blkno,nblocks)
#define DBFREE(dbmap,mapsize,blkno,nblocks) \
	DBFree(dbmap,mapsize,blkno,nblocks)
#define DBALLOCCK(dbmap,mapsize,blkno,nblocks) \
	DBAllocCK(dbmap,mapsize,blkno,nblocks)
#define DBFREECK(dbmap,mapsize,blkno,nblocks) \
	DBFreeCK(dbmap,mapsize,blkno,nblocks)

static void DBinitmap(s64, struct inode *, u32 **);
static void DBAlloc(uint *, s64, s64, s64);
static void DBFree(uint *, s64, s64, s64);
static void DBAllocCK(uint *, s64, s64, s64);
static void DBFreeCK(uint *, s64, s64, s64);
#else
#define DBINITMAP(size,ipbmap,results)
#define DBALLOC(dbmap, mapsize, blkno, nblocks)
#define DBFREE(dbmap, mapsize, blkno, nblocks)
#define DBALLOCCK(dbmap, mapsize, blkno, nblocks)
#define DBFREECK(dbmap, mapsize, blkno, nblocks)
#endif				/* _JFS_DEBUG_DMAP */

/*
 *	SERIALIZATION of the Block Allocation Map.
 *
 *	the working state of the block allocation map is accessed in
 *	two directions:
 *	
 *	1) allocation and free requests that start at the dmap
 *	   level and move up through the dmap control pages (i.e.
 *	   the vast majority of requests).
 * 
 * 	2) allocation requests that start at dmap control page
 *	   level and work down towards the dmaps.
 *	
 *	the serialization scheme used here is as follows. 
 *
 *	requests which start at the bottom are serialized against each 
 *	other through buffers and each requests holds onto its buffers 
 *	as it works it way up from a single dmap to the required level 
 *	of dmap control page.
 *	requests that start at the top are serialized against each other
 *	and request that start from the bottom by the multiple read/single
 *	write inode lock of the bmap inode. requests starting at the top
 *	take this lock in write mode while request starting at the bottom
 *	take the lock in read mode.  a single top-down request may proceed
 *	exclusively while multiple bottoms-up requests may proceed 
 * 	simultaneously (under the protection of busy buffers).
 *	
 *	in addition to information found in dmaps and dmap control pages,
 *	the working state of the block allocation map also includes read/
 *	write information maintained in the bmap descriptor (i.e. total
 *	free block count, allocation group level free block counts).
 *	a single exclusive lock (BMAP_LOCK) is used to guard this information
 *	in the face of multiple-bottoms up requests.
 *	(lock ordering: IREAD_LOCK, BMAP_LOCK);
 *	
 *	accesses to the persistent state of the block allocation map (limited
 *	to the persistent bitmaps in dmaps) is guarded by (busy) buffers.
 */

#define BMAP_LOCK_INIT(bmp)	init_MUTEX(&bmp->db_bmaplock)
#define BMAP_LOCK(bmp)		down(&bmp->db_bmaplock)
#define BMAP_UNLOCK(bmp)	up(&bmp->db_bmaplock)

/*
 * forward references
 */
static void dbAllocBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
			int nblocks);
static void dbSplit(dmtree_t * tp, int leafno, int splitsz, int newval);
static void dbBackSplit(dmtree_t * tp, int leafno);
static void dbJoin(dmtree_t * tp, int leafno, int newval);
static void dbAdjTree(dmtree_t * tp, int leafno, int newval);
static int dbAdjCtl(struct bmap * bmp, s64 blkno, int newval, int alloc,
		    int level);
static int dbAllocAny(struct bmap * bmp, s64 nblocks, int l2nb, s64 * results);
static int dbAllocNext(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks);
static int dbAllocNear(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks,
		       int l2nb, s64 * results);
static int dbAllocDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks);
static int dbAllocDmapLev(struct bmap * bmp, struct dmap * dp, int nblocks,
			  int l2nb,
			  s64 * results);
static int dbAllocAG(struct bmap * bmp, int agno, s64 nblocks, int l2nb,
		     s64 * results);
static int dbAllocCtl(struct bmap * bmp, s64 nblocks, int l2nb, s64 blkno,
		      s64 * results);
static int dbExtend(struct inode *ip, s64 blkno, s64 nblocks, s64 addnblocks);
static int dbFindBits(u32 word, int l2nb);
static int dbFindCtl(struct bmap * bmp, int l2nb, int level, s64 * blkno);
static int dbFindLeaf(dmtree_t * tp, int l2nb, int *leafidx);
static void dbFreeBits(struct bmap * bmp, struct dmap * dp, s64 blkno,
		       int nblocks);
static int dbFreeDmap(struct bmap * bmp, struct dmap * dp, s64 blkno,
		      int nblocks);
static int dbMaxBud(u8 * cp);
s64 dbMapFileSizeToMapSize(struct inode *ipbmap);
static int blkstol2(s64 nb);

static int cntlz(u32 value);
static int cnttz(u32 word);

static int dbAllocDmapBU(struct bmap * bmp, struct dmap * dp, s64 blkno,
			 int nblocks);
static int dbInitDmap(struct dmap * dp, s64 blkno, int nblocks);
static int dbInitDmapTree(struct dmap * dp);
static int dbInitTree(struct dmaptree * dtp);
static int dbInitDmapCtl(struct dmapctl * dcp, int level, int i);
static int dbGetL2AGSize(s64 nblocks);

/*
 *	buddy table
 *
 * table used for determining buddy sizes within characters of 
 * dmap bitmap words.  the characters themselves serve as indexes
 * into the table, with the table elements yielding the maximum
 * binary buddy of free bits within the character.
 */
static s8 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
};


/*
 * NAME:    	dbMount()
 *
 * FUNCTION:	initializate the block allocation map.
 *
 *		memory is allocated for the in-core bmap descriptor and
 *		the in-core descriptor is initialized from disk.
 *
 * PARAMETERS:
 *      ipbmap	-  pointer to in-core inode for the block map.
 *
 * RETURN VALUES:
 *      0	- success
 *      -ENOMEM	- insufficient memory
 *      -EIO	- i/o error
 */
int dbMount(struct inode *ipbmap)
{
	struct bmap *bmp;
	struct dbmap *dbmp_le;
	struct metapage *mp;
	int i;

	/*
	 * allocate/initialize the in-memory bmap descriptor
	 */
	/* allocate memory for the in-memory bmap descriptor */
	bmp = kmalloc(sizeof(struct bmap), GFP_KERNEL);
	if (bmp == NULL)
		return -ENOMEM;

	/* read the on-disk bmap descriptor. */
	mp = read_metapage(ipbmap,
			   BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
			   PSIZE, 0);
	if (mp == NULL) {
		kfree(bmp);
		return -EIO;
	}

	/* copy the on-disk bmap descriptor to its in-memory version. */
	dbmp_le = (struct dbmap *) mp->data;
	bmp->db_mapsize = le64_to_cpu(dbmp_le->dn_mapsize);
	bmp->db_nfree = le64_to_cpu(dbmp_le->dn_nfree);
	bmp->db_l2nbperpage = le32_to_cpu(dbmp_le->dn_l2nbperpage);
	bmp->db_numag = le32_to_cpu(dbmp_le->dn_numag);
	bmp->db_maxlevel = le32_to_cpu(dbmp_le->dn_maxlevel);
	bmp->db_maxag = le32_to_cpu(dbmp_le->dn_maxag);
	bmp->db_agpref = le32_to_cpu(dbmp_le->dn_agpref);
	bmp->db_aglevel = le32_to_cpu(dbmp_le->dn_aglevel);
	bmp->db_agheigth = le32_to_cpu(dbmp_le->dn_agheigth);
	bmp->db_agwidth = le32_to_cpu(dbmp_le->dn_agwidth);
	bmp->db_agstart = le32_to_cpu(dbmp_le->dn_agstart);
	bmp->db_agl2size = le32_to_cpu(dbmp_le->dn_agl2size);
	for (i = 0; i < MAXAG; i++)
		bmp->db_agfree[i] = le64_to_cpu(dbmp_le->dn_agfree[i]);
	bmp->db_agsize = le64_to_cpu(dbmp_le->dn_agsize);
	bmp->db_maxfreebud = dbmp_le->dn_maxfreebud;

	/* release the buffer. */
	release_metapage(mp);

	/* bind the bmap inode and the bmap descriptor to each other. */
	bmp->db_ipbmap = ipbmap;
	JFS_SBI(ipbmap->i_sb)->bmap = bmp;

	memset(bmp->db_active, 0, sizeof(bmp->db_active));
	DBINITMAP(bmp->db_mapsize, ipbmap, &bmp->db_DBmap);

	/*
	 * allocate/initialize the bmap lock
	 */
	BMAP_LOCK_INIT(bmp);

	return (0);
}


/*
 * NAME:    	dbUnmount()
 *
 * FUNCTION:	terminate the block allocation map in preparation for
 *		file system unmount.
 *
 * 		the in-core bmap descriptor is written to disk and
 *		the memory for this descriptor is freed.
 *
 * PARAMETERS:
 *      ipbmap	-  pointer to in-core inode for the block map.
 *
 * RETURN VALUES:
 *      0	- success
 *      -EIO	- i/o error
 */
int dbUnmount(struct inode *ipbmap, int mounterror)
{
	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
	int i;

	if (!(mounterror || isReadOnly(ipbmap)))
		dbSync(ipbmap);

	/*
	 * Invalidate the page cache buffers
	 */
	truncate_inode_pages(ipbmap->i_mapping, 0);

	/*
	 * Sanity Check
	 */
	for (i = 0; i < bmp->db_numag; i++)
		if (atomic_read(&bmp->db_active[i]))
			printk(KERN_ERR "dbUnmount: db_active[%d] = %d\n",
			       i, atomic_read(&bmp->db_active[i]));

	/* free the memory for the in-memory bmap. */
	kfree(bmp);

	return (0);
}

/*
 *	dbSync()
 */
int dbSync(struct inode *ipbmap)
{
	struct dbmap *dbmp_le;
	struct bmap *bmp = JFS_SBI(ipbmap->i_sb)->bmap;
	struct metapage *mp;
	int i;

	/*
	 * write bmap global control page
	 */
	/* get the buffer for the on-disk bmap descriptor. */
	mp = read_metapage(ipbmap,
			   BMAPBLKNO << JFS_SBI(ipbmap->i_sb)->l2nbperpage,
			   PSIZE, 0);
	if (mp == NULL) {
		jfs_err("dbSync: read_metapage failed!");
		return -EIO;
	}
	/* copy the in-memory version of the bmap to the on-disk version */
	dbmp_le = (struct dbmap *) mp->data;
	dbmp_le->dn_mapsize = cpu_to_le64(bmp->db_mapsize);
	dbmp_le->dn_nfree = cpu_to_le64(bmp->db_nfree);
	dbmp_le->dn_l2nbperpage = cpu_to_le32(bmp->db_l2nbperpage);
	dbmp_le->dn_numag = cpu_to_le32(bmp->db_numag);
	dbmp_le->dn_maxlevel = cpu_to_le32(bmp->db_maxlevel);
	dbmp_le->dn_maxag = cpu_to_le32(bmp->db_maxag);
	dbmp_le->dn_agpref = cpu_to_le32(bmp->db_agpref);
	dbmp_le->dn_aglevel = cpu_to_le32(bmp->db_aglevel);
	dbmp_le->dn_agheigth = cpu_to_le32(bmp->db_agheigth);
	dbmp_le->dn_agwidth = cpu_to_le32(bmp->db_agwidth);
	dbmp_le->dn_agstart = cpu_to_le32(bmp->db_agstart);
	dbmp_le->dn_agl2size = cpu_to_le32(bmp->db_agl2size);
	for (i = 0; i < MAXAG; i++)
		dbmp_le->dn_agfree[i] = cpu_to_le64(bmp->db_agfree[i]);
	dbmp_le->dn_agsize = cpu_to_le64(bmp->db_agsize);
	dbmp_le->dn_maxfreebud = bmp->db_maxfreebud;

	/* write the buffer */
	write_metapage(mp);

	/*
	 * write out dirty pages of bmap
	 */
	fsync_inode_data_buffers(ipbmap);

	ipbmap->i_state |= I_DIRTY;
	diWriteSpecial(ipbmap, 0);

	return (0);
}


/*
 * NAME:    	dbFree()
 *
 * FUNCTION:	free the specified block range from the working block
 *		allocation map.
 *
 *		the blocks will be free from the working map one dmap
 *		at a time.
 *
 * PARAMETERS:
 *      ip	-  pointer to in-core inode;
 *      blkno	-  starting block number to be freed.
 *      nblocks	-  number of blocks to be freed.
 *
 * RETURN VALUES:
 *      0	- success
 *      -EIO	- i/o error
 */
int dbFree(struct inode *ip, s64 blkno, s64 nblocks)
{
	struct metapage *mp;
	struct dmap *dp;
	int nb, rc;
	s64 lblkno, rem;
	struct inode *ipbmap = JFS_SBI(ip->i_sb)->ipbmap;
	struct bmap *bmp = JFS_SBI(ip->i_sb)->bmap;

	IREAD_LOCK(ipbmap);

	/* block to be freed better be within the mapsize. */
	if (unlikely((blkno == 0) || (blkno + nblocks > bmp->db_mapsize))) {
		IREAD_UNLOCK(ipbmap);
		printk(KERN_ERR "blkno = %Lx, nblocks = %Lx\n",
		       (unsigned long long) blkno,
		       (unsigned long long) nblocks);
		jfs_error(ip->i_sb,
			  "dbFree: block to be freed is outside the map");
		return -EIO;
	}

	/*
	 * free the blocks a dmap at a time.
	 */
	mp = NULL;
	for (rem = nblocks; rem > 0; rem -= nb, blkno += nb) {
		/* release previous dmap if any */
		if (mp) {
			write_metapage(mp);
		}

		/* get the buffer for the current dmap. */
		lblkno = BLKTODMAP(blkno, bmp->db_l2nbperpage);
		mp = read_metapage(ipbmap, lblkno, PSIZE, 0);
		if (mp == NULL) {
			IREAD_UNLOCK(ipbmap);
			return -EIO;
		}
		dp = (struct dmap *) mp->data;

		/* determine the number of blocks to be freed from
		 * this dmap.
		 */
		nb = min(rem, BPERDMAP - (blkno & (BPERDMAP - 1)));

		DBALLOCCK(bmp->db_DBmap, bmp->db_mapsize, blkno, nb);

		/* free the blocks. */
		if ((rc = dbFreeDmap(bmp, dp, blkno, nb))) {
			release_metapage(mp);
			IREAD_UNLOCK(ipbmap);
			return (rc);
		}

		DBFREE(bmp->db_DBmap, bmp->db_mapsize, blkno, nb);
	}

	/* write the last buffer. */
	write_metapage(mp);

	IREAD_UNLOCK(ipbmap);

	return (0);
}


/*
 * NAME:	dbUpdatePMap()
 *
 * FUNCTION:    update the allocation state (free or allocate) of the
 *		specified block range in the persistent block allocation map.
 *