dskalloc.c

T-kernel 的extension源代码

/*
 *----------------------------------------------------------------------
 *    T-Kernel / Standard Extension
 *
 *    Copyright (C) 2006 by Ken Sakamura. All rights reserved.
 *    T-Kernel / Standard Extension is distributed 
 *      under the T-License for T-Kernel / Standard Extension.
 *----------------------------------------------------------------------
 *
 *    Version:   1.00.00
 *    Released by T-Engine Forum(http://www.t-engine.org) at 2006/8/11.
 *
 *----------------------------------------------------------------------
 */

/*
 *	dskalloc.c (file)
 *
 *	File management
 *	Disk allocation management
 */

#include "dskalloc.h"
#include "diskio.h"

/*
 * Access management information of the block bit map
 */
#define N_BM_MAPINFO		2
#define TSD_AFG_VAL_2		2
#define TSD_FRF_VAL_2		2
#define TSD_MEF_VAL_2		2
#define TSD_MAF_VAL_2		2
#define TSD_PAF_OK_M1		(-1)
#define TSD_DAM_BIT_0X80	0x80U
#define TSD_DAM_BIT_0X01	0x01U
#define TSD_DB0_RTN_M1		(-1)
#define TSD_DB1_RTN_M1		(-1)
#define TSD_NFE_RTN_32		32
#define TSD_GFS_SZ_4		4
#define TSD_GFS_SZ_2		2
#define TSD_FRF_SZ_2		2
#define TSD_MEF_SZ_2		2
#define TSD_FCF_VAL_2		2
#define TSD_AFG_FRE_2		2
#define TSD_AFG_OFF_2		2U
#define TSD_AFG_SBD_2		2
#define TSD_AFG_OF_2		2
#define TSD_FRF_OF_2		2
#define TSD_MEF_OF_2		2
#define TSD_MAF_OF_2		2
#define TSD_AFG_OFU_2		2U
#define TSD_DAM_BS_3		3
#define TSD_DAM_BSU_3		3U
#define TSD_DAM_RSF_7		7U
#define TSD_DAM_LSF_7		7U

typedef struct {
	struct bm_mapinfo {
		ID	mid;		/* Map ID (0 shows that not mapped yet) */
		UB	*mapbase;	/* Mapped memory address */
		UW	mflag;		/* Map state flag */
		W	offset;		/* Offset from the mapped bmadr */
		W	nbyte;		/* Mapped valid byte count */
	} mi[N_BM_MAPINFO];

	FsInfo	*fsinfo;	/* Target file system */
	DskAdrS	bmadr;		/* The first address of the block bit map */
	W	nbmp;		/* Size of the block bit map (Byte count) */
	ER	error;		/* Error recording */
	UB	idx;		/* mi[idx] was mapped lastly. */
	UB	dummy;		/* For dummy address in mapping error */
} BitMapIO;

Inline W N_FragEnt( OFCB *ofcb );
LOCAL void getFragment( Fragment *frag, DfFileHeaderBlock *fh, W no, FsInfo *fsinfo );
LOCAL void setFragment( DfFileHeaderBlock *fh, W no, Fragment *frag, FsInfo *fsinfo );
LOCAL UH getBorder( UH *border, FsInfo *fsinfo );
LOCAL void setBorder( UH *border, UH free, FsInfo *fsinfo );
LOCAL W getFragmentSize( Fragment *frag, BOOL *bottom, FsInfo *fsinfo );
LOCAL ER fmpChangeFragment( DskAdr oldfrag, DskAdr newfrag, W newsize, OFCB *ofcb );
LOCAL WER allocateFragment( DfFileHeaderBlock *fh, W no, DskAdr *dadr, W size, OFCB *ofcb );
LOCAL ER fmpAddFragment( UW blk, W use, W end, OFCB *ofcb);
LOCAL ER fmpDeleteFragment( DskAdr top, DskAdr end, OFCB *ofcb );
LOCAL ER openBitMap( BitMapIO *bm, DskAdrS bmadr, W nbmp, FsInfo *fsinfo );
LOCAL UB* bitMap( BitMapIO *bm, W offset, UW mflag );
LOCAL ER closeBitMap( BitMapIO *bm );
LOCAL W bitSearch0( BitMapIO *bm, W bno, W width );
LOCAL W bitSearch1( BitMapIO *bm, W bno, W width );
LOCAL void bitSet( BitMapIO *bm, W bno, W width );
LOCAL void bitClear( BitMapIO *bm, W bno, W width );
LOCAL ER blockSearch( LLogBlk *alloc, BitMapIO *bm, W bno, W end, W blkunits, W blklimit );
LOCAL ER changeUseBlockCount( W diff, OFCB *ofcb, FsInfo *fsinfo );
LOCAL ER allocateBlock( LLogBlk *alloc, W blksize, W blkunits, UW lblk, OFCB *ofcb, FsInfo *fsinfo );
LOCAL ER freeBlock( UW lblk, W cnt, OFCB *ofcb, FsInfo *fsinfo );

/* ======================================================================== */
/*
 *	Fragment table related
 */

/*
 * The number of entries of the fragment table.
 */
Inline W N_FragEnt( OFCB *ofcb )
{
	if ( ofcb->fsinfo->diskform < DiskForm_C ) {
		return TSD_NFE_RTN_32;
	} else {
		return (W)(ofcb->ridxofs - sizeof(DfFileHeader))
					/ sizeof(DfFragment2);
	}
}

/*
 * Fetch the entry of the fragment table.
 *	Fetch the no th fragment entry of file header block fh.
 *
 */
LOCAL void getFragment( Fragment *frag, DfFileHeaderBlock *fh, W no,
							FsInfo *fsinfo )
{
	if ( fsinfo->diskform < DiskForm_C ) {
		DfFragment	*f1 = &fh->f.frag[no];
		UW		locate;

		locate = fmpConvEndianW(getMisalignW(f1->locate), fsinfo);
		frag->locate.offset = (VP)(locate % fsinfo->sblk);
		frag->locate.lblk   = locate / fsinfo->sblk;
		frag->size          = (W)fmpConvEndianH(f1->size, fsinfo);
	} else {
		DfFragment2	*f2 = &fh->f.frag2[no];

		frag->locate.offset =
				(VP)(UW)fmpConvEndianH(f2->offset, fsinfo);
		frag->locate.lblk   = fmpConvEndianW(f2->blk, fsinfo);
		frag->size          = (W)fmpConvEndianH(f2->size, fsinfo);
	}
}

/*
 * Set the entry of the fragment table.
 *	Set to the no th fragment entry of the file header block fh.
 *
 */
LOCAL void setFragment( DfFileHeaderBlock *fh, W no, Fragment *frag,
							FsInfo *fsinfo )
{
	if ( fsinfo->diskform < DiskForm_C ) {
		DfFragment	*f1 = &fh->f.frag[no];
		UW		locate;

		locate = (frag->locate.lblk * fsinfo->sblk)
				+ (UW)frag->locate.offset;
		setMisalignW(f1->locate, fmpConvEndianW(locate, fsinfo));
		f1->size = fmpConvEndianH((UH)frag->size, fsinfo);
	} else {
		DfFragment2	*f2 = &fh->f.frag2[no];

		f2->offset =
			fmpConvEndianH((UH)(UW)frag->locate.offset, fsinfo);
		f2->blk    = fmpConvEndianW(frag->locate.lblk, fsinfo);
		f2->size   = fmpConvEndianH((UH)frag->size, fsinfo);
	}
}

/*
 * Fetch the separator code of the fragment.
 */
LOCAL UH getBorder( UH *border, FsInfo *fsinfo )
{
	return fmpConvEndianH(getMisalignH((UB*)border), fsinfo);
}

/*
 * Set the separator code of the fragment.
 */
LOCAL void setBorder( UH *border, UH free, FsInfo *fsinfo )
{
	setMisalignH((UB*)border, fmpConvEndianH(free, fsinfo));
}

/*
 * Obtain the free size of the fragment *frag.
 *	Return *bottom = TRUE when the free area is located at the end of the logical block.
 */
LOCAL W getFragmentSize( Fragment *frag, BOOL *bottom, FsInfo *fsinfo )
{
	W	free;
	UW	top;

	*bottom = FALSE;

	/* Remove the size of the separator code. */
	free = frag->size - TSD_GFS_SZ_4;

	top = (UW)frag->locate.offset;

	/* No separator code is required when it is located at the start/end of the logical block. */
	if ( top == 0U ) {
		free += TSD_GFS_SZ_2;
	}
	if ( (top + (UW)frag->size) == fsinfo->sblk ) {
		free += TSD_GFS_SZ_2;
		*bottom = TRUE;
	}

	return free;
}

/*
 * Change the location of the fragment registered in the fragment table from oldfrag
 * into newfrag, and change the size into newsize. If oldfrag is not registered,
 * register newfrag. When it exceeds the maximum number of entries of the fragment table,
 * the smallest size one is automatically deregistered.
 * Deregister the fragment when newsize < 2.
 */
LOCAL ER fmpChangeFragment( DskAdr oldfrag, DskAdr newfrag, W newsize,
								OFCB *ofcb )
{
	FsInfo			*fsinfo = ofcb->fsinfo;
	DfFileHeaderBlock	*fh;
	Fragment		frag;
	W			oldsize;
	W			i, j, nent;
	ID			mid;
	ER			err;

	if ( newsize < TSD_FCF_VAL_2 ) {
		newsize = 0;
	}

	/* Map the fragment table (File header). */
	fh = fmpMapDskAdr(ofcb->fhead, (W)ofcb->ridxofs, ofcb, &mid, fsinfo);
	if ( fh == NULL ) {
		err = (ER)mid;
		goto err_ret;
	}

	/* The number of entries of the fragment table. */
	nent = N_FragEnt(ofcb);

	/* Check whether oldfrag is registered in the fragment table. */
	oldsize = 0;
	for ( i = 0; i < nent; i++ ) {

		getFragment(&frag, fh, i, fsinfo);

		if ( frag.size == 0 ) {
			/* Because the size 0 is not necessarily set to the remaining unused entries,
			   Set the size 0 to the next entry at least in case that
			   the number of entries is increased. */
			if ( i < (nent - 1) ) {
				frag.locate.offset = 0;
				frag.locate.lblk   = 0;
				frag.size          = 0;
				setFragment(fh, i + 1, &frag, fsinfo);
			}
			break;
		}

		if ( CmpDskAdr(frag.locate, oldfrag) == 0 ) {
			oldsize = frag.size;
			break;
		}
	}

	/* Find the registration location while sorting. */
	if ( newsize >= oldsize ) {
		/* Scale up the size. */
		for ( j = i - 1; j >= 0; --j ) {
			getFragment(&frag, fh, j, fsinfo);
			if ( frag.size >= newsize ) {
				break;
			}

			if ( j < (nent - 1) ) {
				setFragment(fh, j + 1, &frag, fsinfo);
			}
		}
		j++;
	} else {
		/* Scale down the size. */
		for ( j = i + 1; j < nent; ++j ) {
			getFragment(&frag, fh, j, fsinfo);
			if ( frag.size <= newsize ) {
				break;
			}

			setFragment(fh, j - 1, &frag, fsinfo);
		}
		j--;
	}

	if ( j < nent ) {
		/* Registration */
		frag.locate = newfrag;
		frag.size   = newsize;
		setFragment(fh, j, &frag, fsinfo);
	}

	fmpUnmapDisk(mid, MD_WRITE);
	err = fmpCheckDiskError(ofcb, fsinfo);
	if ( err < E_OK ) {
		goto err_ret;
	}

	return E_OK;

err_ret:
	DEBUG_PRINT(("fmpChangeFragment err = %d\n", err));
	return err;
}

/*
 * Reserve an area from the fragment.
 *	Reserve the area of up to size bytes from the no th fragment entry of
 *	the file header block fh.
 *	Return the disk address of the reserved area to *dadr.
 *	Set the separator code to the reserved area, and update the fragment table too.
 *	Return the reserved size to the return value.
 */
LOCAL WER allocateFragment( DfFileHeaderBlock *fh, W no, DskAdr *dadr,
							W size, OFCB *ofcb )
{
	FsInfo		*fsinfo = ofcb->fsinfo;
	Fragment	frag;
	LogAdr		ladr;
	VB		*bp;
	UW		offset;
	BOOL		bottom;
	W		keep, free;
	ID		mid;
	ER		err;

	getFragment(&frag, fh, no, fsinfo);
	free = getFragmentSize(&frag, &bottom, fsinfo);
	keep = min(free, size);
	free -= keep;
	if ( bottom != 0 ) {
		free -= TSD_AFG_FRE_2; /* Size of the new separator code */
	}

	ladr = fmpDAdrToLAdr(frag.locate, fsinfo);

	/* Map the logical block that includes the fragment area. */
	bp = fmpMapLogBlk(ladr.blk, ofcb, &mid, fsinfo);
	if ( bp == NULL ) {
		err = (ER)mid;
		goto err_ret;
	}

	/* Set the separator code. */
	offset = ladr.offset;
	if ( offset >= TSD_AFG_OFF_2 ) {
		setBorder((UH*)(bp + offset), 0, fsinfo);
		setBorder((UH*)(bp + offset - TSD_AFG_SBD_2), 0, fsinfo);

		offset += TSD_AFG_OFU_2;
		dadr->offset = (VB*)frag.locate.offset + TSD_AFG_OF_2;
	} else {
		dadr->offset = frag.locate.offset;
	}
	dadr->lblk = frag.locate.lblk;
	offset += (UW)keep;
	ladr.offset = offset + TSD_AFG_OFU_2;
	if ( (W)offset <= (fsinfo->sblk - TSD_AFG_VAL_2) ) {
		setBorder((UH*)(bp + offset), (UH)free, fsinfo);

		offset += TSD_AFG_OF_2 + (UW)free;
		if ( (W)offset <= (fsinfo->sblk - TSD_AFG_VAL_2) ) {
			setBorder((UH*)(bp + offset), (UH)free, fsinfo);
		}
	}

	fmpUnmapDisk(mid, MD_WRITE);
	err = fmpCheckDiskError(ofcb, fsinfo);
	if ( err < E_OK ) {
		goto err_ret;
	}

	/* Update the fragment table. */
	err = fmpChangeFragment(frag.locate, fmpLAdrToDAdr(ladr, fsinfo), free,
									ofcb);
	if ( err < E_OK ) {
		goto err_ret;
	}

	return keep;

err_ret:
	DEBUG_PRINT(("allocateFragment err = %d\n", err));
	return err;
}

/*
 * Find/Reserve a free area from the fragment table.
 *	When the area of size or more can not be found, allocate the free area only when
 *	the end of its area is located at the end of the logical block.
 *	Return the allocated location and the size to *dadr and the return velue respectively.
 *	When a free area is allocated, update the fragment table too.
 */
EXPORT WER fmpAllocateFragment( DskAdr *dadr, W size, OFCB *ofcb )
{
	FsInfo			*fsinfo = ofcb->fsinfo;
	DfFileHeaderBlock	*fh;
	Fragment		frag;
	W			free;
	BOOL			bottom;
	W			i, ok, nent;
	W			keep = 0;
	ID			mid;
	ER			err;

	/* Map the fragment table (File header). */
	fh = fmpMapDskAdr(ofcb->fhead, (W)ofcb->ridxofs, ofcb, &mid, fsinfo);
	if ( fh == NULL ) {
		err = (ER)mid;
		goto err_ret1;
	}

	/* The number of entries of the fragment table */
	nent = N_FragEnt(ofcb);

	/* Find a free area. */
	ok = TSD_PAF_OK_M1;
	for ( i = 0; i < nent; ++i ) {

		/* Obtain the free size and the location. */
		getFragment(&frag, fh, i, fsinfo);
		if ( frag.size == 0 ) {
			break;
		}
		free = getFragmentSize(&frag, &bottom, fsinfo);
		if ( free <= 0 ) {
			continue;
		}

		/* Select the free area nearest to size. */
		if ( free >= size ) {
			ok = i;
			continue;
		}
		if ( ok >= 0 ) {
			break;
		}
		if ( bottom != 0 ) {
			ok = i;
			break;
		}
	}

	if ( ok >= 0 ) {
		/* Because a free area is found, reserve it. */
		keep = allocateFragment(fh, ok, dadr, size, ofcb);
		if ( keep < E_OK ) {
			err = (ER)keep;
			goto err_ret2;
		}
	}

	fmpUnmapDisk(mid, MD_RDONLY);
	err = fmpCheckDiskError(ofcb, fsinfo);
	if ( err < E_OK ) {
		goto err_ret1;
	}

	return keep;

err_ret2:
	fmpUnmapDisk(mid, MD_RDONLY);
err_ret1:
	DEBUG_PRINT(("fmpAllocateFragment err = %d\n", err));
	return err;
}

/*
 * Reserve a free area from the fragment area and scale up the size.
 *	Reserve the area of size bytes from the free area continued from use th byte of the
 *	logical block lblk. However, when there is no free area of size or more, allocate it
 *	only when the end of the free area matches with the end of the logical block.
 *	Return the allocated size to the return value.
 *	When the free area is allocated, update the fragment table too.
 */
EXPORT WER fmpResizeFragment( UW lblk, W use, W size, OFCB *ofcb )
{
	FsInfo	*fsinfo = ofcb->fsinfo;
	W	keep, free;
	VB	*bp;
	ID	mid;
	UW	mflag = MD_RDONLY;
	ER	err;

	keep = fsinfo->sblk - use;