/* * basic Flash Translation Layer driver *	see for instance the Intel technical paper *	``Understanding the Flash Translation Layer (FTL) Specification'' *	Order number 297816-001 (online at www.intel.com) * * a public driver by David Hinds, dhinds@allegro.stanford.edu * further helps with some details. * * this driver uses the common simplification of never storing * the VBM on the medium (a waste of precious flash!) but * rather building it on the fly as the block maps are read. * * Plan 9 driver (c) 1997 by C H Forsyth (forsyth@caldo.demon.co.uk) *	This driver may be used or adapted by anyone for any non-commercial purpose. * * adapted for Inferno 1998 by C H Forsyth, Vita Nuova Limited, York, England (charles@vitanuova.com) * * C H Forsyth and Vita Nuova Limited expressly allow Lucent Technologies * to use this driver freely for any Inferno-related purposes whatever, * including commercial applications. * * TO DO: *	check error handling details for get/put flash *	bad block handling *	reserved space in formatted size *	possibly block size as parameter *	fetch parameters from header on init * * Adapted to a ftl formatter for Inferno 2000 by J R Firth, Vita Nuova Limited * 	usage : ftl flashsize secsize inputfile outputfile * outputfile will then be a ftl image of inputfile * nb assumes the base address is zero * */ #include <lib9.h> ulong flashsize, secsize;char *flashm;int trace = 0; #ifndef offsetof#define offsetof(T,X) ((ulong)&(((T*)0)->X))#endif typedef struct Ftl Ftl;typedef struct Merase Merase;typedef struct Terase Terase; enum {	Eshift = 18,	/* 2^18=256k; log2(eraseunit) */	Flashseg = 1<<Eshift,	Bshift = 9,		/* 2^9=512 */	Bsize = 1<<Bshift,	BAMoffset = 0x100,	Nolimit = ~0,	USABLEPCT = 95,	/* release only this % to client */ 	FTLDEBUG = 0}; /* erase unit header (defined by FTL specification) */struct Merase {	uchar	linktuple[5];	uchar	orgtuple[10];	uchar	nxfer;	uchar	nerase[4];	uchar	id[2];	uchar	bshift;	uchar	eshift;	uchar	pstart[2];	uchar	nunits[2];	uchar	psize[4];	uchar	vbmbase[4];	uchar	nvbm[2];	uchar	flags;	uchar	code;	uchar	serial[4];	uchar	altoffset[4];	uchar	bamoffset[4];	uchar	rsv2[12];};#define	ERASEHDRLEN	64 enum {	/* special unit IDs */	XferID = 0xffff,	XferBusy = 0x7fff, 	/* special BAM addresses */	Bfree = 0xffffffff,	Bwriting = 0xfffffffe,	Bdeleted = 0, 	/* block types */	TypeShift = 7,	BlockType = (1<<TypeShift)-1,	ControlBlock = 0x30,	DataBlock = 0x40,	ReplacePage = 0x60,	BadBlock = 0x70,}; #define	BTYPE(b)	((b) & BlockType)#define	BADDR(b)	((b) & ~BlockType)#define	BNO(va)	(((ulong)(va))>>Bshift)#define	MKBAM(b,t)	(((b)<<Bshift)|(t)) struct Terase {	int	x;	int	id;	ulong	offset;	ulong	bamoffset;	ulong	nbam;	ulong*	bam;	ulong	bamx;	ulong	nfree;	ulong	nused;	ulong	ndead;	ulong	nbad;	ulong	nerase;}; struct Ftl {	ulong	base;	/* base of flash region */	ulong	size;	/* size of flash region */	ulong	segsize;	/* size of flash segment (erase unit) */	int	eshift;	/* log2(erase-unit-size) */	int	bshift;	/* log2(bsize) */	int	bsize;	int	nunit;	/* number of segments (erase units) */	Terase**	unit;	int	lastx;	/* index in unit of last allocation */	int	xfer;		/* index in unit of current transfer unit (-1 if none) */	ulong	nfree;	/* total free space in blocks */	ulong	nblock;	/* total space in blocks */	ulong	rwlimit;	/* user-visible block limit (`formatted size') */	ulong*	vbm;		/* virtual block map */	ulong	fstart;	/* address of first block of data in a segment */	int	trace;	/* (debugging) trace of read/write actions */	int	detach;	/* free Ftl on last close */ 	/* scavenging variables */	int	needspace;	int	hasproc;}; enum {	/* Ftl.detach */	Detached = 1,	/* detach on close */	Deferred	/* scavenger must free it */}; /* little endian */#define	GET2(p)	(((p)[1]<<8)|(p)[0])#define	GET4(p)	(((((((p)[3]<<8)|(p)[2])<<8)|(p)[1])<<8)|(p)[0])#define	PUT2(p,v)	(((p)[1]=(v)>>8),((p)[0]=(v)))#define	PUT4(p,v)	(((p)[3]=(v)>>24),((p)[2]=(v)>>16),((p)[1]=(v)>>8),((p)[0]=(v))) static	Ftl	*ftls; static	ulong	allocblk(Ftl*);static	void	eraseflash(Ftl*, ulong);static	void	erasefree(Terase*);static	void	eraseinit(Ftl*, ulong, int, int);static	Terase*	eraseload(Ftl*, int, ulong);static	void	ftlfree(Ftl*);static	void	getflash(Ftl*, void*, ulong, long);static	int	mapblk(Ftl*, ulong, Terase**, ulong*);static	Ftl*	mkftl(char*, ulong, ulong, int, char*);static	void	putbam(Ftl*, Terase*, int, ulong);static	void	putflash(Ftl*, ulong, void*, long);static	int	scavenge(Ftl*); static void	 ftlstat(int sz){	print("0x%lux:0x%ux:0x%lux\n", ftls->rwlimit*Bsize, sz, flashsize);	print("%lud:%d:%lud in 512b blocks\n", ftls->rwlimit, sz>>Bshift, flashsize>>Bshift);} static long	 ftlread(void *buf, long n, ulong offset){	Ftl *ftl;	Terase *e;	int nb;	uchar *a;	ulong pb; 		if(n <= 0 || n%Bsize || offset%Bsize) {			fprint(2, "bad read\n");			exits("1");		}		ftl = ftls;		nb = n/Bsize;		offset /= Bsize;		if(offset >= ftl->rwlimit)			return 0;		if(offset+nb > ftl->rwlimit)			nb = ftl->rwlimit - offset;		a = buf;		for(n = 0; n < nb; n++){			if(mapblk(ftl, offset+n, &e, &pb))				getflash(ftl, a, e->offset + pb*Bsize, Bsize);			else				memset(a, 0, Bsize);			a += Bsize;		}		return a-(uchar*)buf;	return 0;		/* not reached */} static long	 ftlwrite(void *buf, long n, ulong offset){	int ns, nb;	uchar *a;	Terase *e, *oe;	ulong ob, v;	Ftl *ftl; 	if(n <= 0)		return 0;		ftl = ftls;		if(n <= 0 || n%Bsize || offset%Bsize) {			fprint(2, "bad write\n");			exits("1");		}		nb = n/Bsize;		offset /= Bsize;		if(offset >= ftl->rwlimit)			return 0;		if(offset+nb > ftl->rwlimit)			nb = ftl->rwlimit - offset;		a = buf;		for(n = 0; n < nb; n++){			ns = 0;			while((v = allocblk(ftl)) == 0)				if(!scavenge(ftl) || ++ns > 3){					print("ftl: flash memory full\n");				}			if(!mapblk(ftl, offset+n, &oe, &ob))				oe = nil;			e = ftl->unit[v>>16];			v &= 0xffff;			putflash(ftl, e->offset + v*Bsize, a, Bsize);			putbam(ftl, e, v, MKBAM(offset+n, DataBlock));			/* both old and new block references exist in this window (can't be closed?) */			ftl->vbm[offset+n] = (e->x<<16) | v;			if(oe != nil){				putbam(ftl, oe, ob, Bdeleted);				oe->ndead++;			}			a += Bsize;		}		return a-(uchar*)buf;	return 0;		/* not reached */} static Ftl *mkftl(char *fname, ulong base, ulong size, int eshift, char *op){	int i, j, nov, segblocks;	ulong limit;	Terase *e;	Ftl *ftl; 	ftl = malloc(sizeof(*ftl));	if(ftl == nil) {		fprint(2, "out of memory\n");		exits("1");	}	ftl->lastx = 0;	ftl->detach = 0;	ftl->needspace = 0;	ftl->hasproc = 0;	ftl->trace = 0;	limit = flashsize;	if(size == Nolimit)		size = limit-base;	if(base >= limit || size > limit || base+size > limit || eshift < 8 || (1<<eshift) > size) {		fprint(2, "bad flash space parameters");		exits("1");	}	if(FTLDEBUG || ftl->trace || trace)		print("%s flash %s #%lux:#%lux limit #%lux\n", op, fname, base, size, limit);	ftl->base = base;	ftl->size = size;	ftl->bshift = Bshift;	ftl->bsize = Bsize;	ftl->eshift = eshift;	ftl->segsize = 1<<eshift;	ftl->nunit = size>>eshift;	nov = ((ftl->segsize/Bsize)*4 + BAMoffset + Bsize - 1)/Bsize;	/* number of overhead blocks per segment (header, and BAM itself) */	ftl->fstart = nov;	segblocks = ftl->segsize/Bsize - nov;	ftl->nblock = ftl->nunit*segblocks;	if(ftl->nblock >= 0x10000)		ftl->nblock = 0x10000;	ftl->vbm = malloc(ftl->nblock*sizeof(*ftl->vbm));	ftl->unit = malloc(ftl->nunit*sizeof(*ftl->unit));	if(ftl->vbm == nil || ftl->unit == nil) {		fprint(2, "out of mem");		exits("1");	}	for(i=0; i<ftl->nblock; i++)		ftl->vbm[i] = 0;	if(strcmp(op, "format") == 0){		for(i=0; i<ftl->nunit-1; i++)			eraseinit(ftl, i*ftl->segsize, i, 1);		eraseinit(ftl, i*ftl->segsize, XferID, 1);	}	ftl->xfer = -1;	for(i=0; i<ftl->nunit; i++){		e = eraseload(ftl, i, i*ftl->segsize);		if(e == nil){			print("ftl: logical segment %d: bad format\n", i);			continue;		}		if(e->id == XferBusy){			e->nerase++;			eraseinit(ftl, e->offset, XferID, e->nerase);			e->id = XferID;		}		for(j=0; j<ftl->nunit; j++)			if(ftl->unit[j] != nil && ftl->unit[j]->id == e->id){				print("ftl: duplicate erase unit #%x\n", e->id);				erasefree(e);				e = nil;				break;			}		if(e){			ftl->unit[e->x] = e;			if(e->id == XferID)				ftl->xfer = e->x;			if (FTLDEBUG || ftl->trace || trace)				print("ftl: unit %d:#%x used %lud free %lud dead %lud bad %lud nerase %lud\n",					e->x, e->id, e->nused, e->nfree, e->ndead, e->nbad, e->nerase);		}	}	if(ftl->xfer < 0 && ftl->nunit <= 0 || ftl->xfer >= 0 && ftl->nunit <= 1) {		fprint(2, "no valid flash data units");		exits("1");	}	if(ftl->xfer < 0)		print("ftl: no transfer unit: device is WORM\n");	else		ftl->nblock -= segblocks;	/* discount transfer segment */	if(ftl->nblock >= 1000)		ftl->rwlimit = ftl->nblock-100;	/* TO DO: variable reserve */	else		ftl->rwlimit = ftl->nblock*USABLEPCT/100;	return ftl;} static voidftlfree(Ftl *ftl){	if(ftl != nil){		free(ftl->unit);		free(ftl->vbm);		free(ftl);	}} /* * this simple greedy algorithm weighted by nerase does seem to lead * to even wear of erase units (cf. the eNVy file system) */static Terase *bestcopy(Ftl *ftl){	Terase *e, *be;	int i; 	be = nil;	for(i=0; i<ftl->nunit; i++)		if((e = ftl->unit[i]) != nil && e->id != XferID && e->id != XferBusy && e->ndead+e->nbad &&		    (be == nil || e->nerase <= be->nerase && e->ndead >= be->ndead))			be = e;	return be;} static intcopyunit(Ftl *ftl, Terase *from, Terase *to){	int i, nb;	uchar id[2];	ulong *bam;	uchar *buf;	ulong v, bno; 	if(FTLDEBUG || ftl->trace || trace)		print("ftl: copying %d (#%lux) to #%lux\n", from->id, from->offset, to->offset);	to->nbam = 0;	free(to->bam);	to->bam = nil;	buf = malloc(Bsize);	if(buf == nil)		return 0;	PUT2(id, XferBusy);	putflash(ftl, to->offset+offsetof(Merase,id[0]), id, 2);	/* make new BAM */	nb = from->nbam*sizeof(*to->bam);	bam = malloc(nb);	if(bam == nil) {		fprint(2, "nomem\n");		exits("1");	}	memmove(bam, from->bam, nb);	to->nused = 0;	to->nbad = 0;	to->nfree = 0;	to->ndead = 0;	for(i = 0; i < from->nbam; i++)		switch(bam[i]){		case Bwriting:		case Bdeleted:		case Bfree:			bam[i] = Bfree;			to->nfree++;			break;		default:			switch(bam[i]&BlockType){			default:			case BadBlock:	/* it isn't necessarily bad in this unit */				to->nfree++;				bam[i] = Bfree;				break;			case DataBlock:			case ReplacePage:				v = bam[i];				bno = BNO(v & ~BlockType);				if(i < ftl->fstart || bno >= ftl->nblock){					print("ftl: unit %d:#%x bad bam[%d]=#%lux\n", from->x, from->id, i, v);					to->nfree++;					bam[i] = Bfree;					break;				}				getflash(ftl, buf, from->offset+i*Bsize, Bsize);				putflash(ftl, to->offset+i*Bsize, buf, Bsize);				to->nused++;				break;			case ControlBlock:				to->nused++;				break;			}		}	for(i=0; i<from->nbam; i++){		uchar *p = (uchar*)&bam[i];		v = bam[i];		if(v != Bfree && ftl->trace > 1)			print("to[%d]=#%lux\n", i, v);		PUT4(p, v);	}	putflash(ftl, to->bamoffset, bam, nb);	/* BUG: PUT4 */	for(i=0; i<from->nbam; i++){		uchar *p = (uchar*)&bam[i];		v = bam[i];		PUT4(p, v);	}	to->id = from->id;	PUT2(id, to->id);	putflash(ftl, to->offset+offsetof(Merase,id[0]), id, 2);	to->nbam = from->nbam;	to->bam = bam;	ftl->nfree += to->nfree - from->nfree;	free(buf);	return 1;} static intmustscavenge(void *a){	return ((Ftl*)a)->needspace || ((Ftl*)a)->detach == Deferred;} static intdonescavenge(void *a){	return ((Ftl*)a)->needspace == 0;} static voidscavengeproc(void *arg){	Ftl *ftl;	int i;	Terase *e, *ne; 	ftl = arg;	if(mustscavenge(ftl)){		if(ftl->detach == Deferred){			ftlfree(ftl);			fprint(2, "scavenge out of memory\n");			exits("1");		}		if(FTLDEBUG || ftl->trace || trace)

Lines 1–500 of 867. Load more