# # 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 (byteles@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 # # Converted to limbo for Inferno 2000 by JR Firth, Vita Nuova Holdings Limited # implement Ftlimage; include "sys.m"; include "draw.m"; sys : Sys; OREAD, OWRITE, FD, open, create, read, write, print, fprint : import sys; Ftlimage : module { init : fn(nil : ref Draw->Context, argv : list of string); }; stderr : ref FD; flashsize, secsize : int; flashm : array of byte; trace : int = 0; Eshift : con 18; # 2^18=256k; log2(eraseunit) Flashseg : con 1<>Bshift; } MKBAM(b : int,t : int) : int { return (b<>Bshift, flashsize>>Bshift); } ftlread(buf : array of byte, n : int, offset : int) : int { ftl : ref Ftl; e : ref Terase; nb : int; a : int; pb : int; mapb : int; if(n <= 0 || n%Bsize || offset%Bsize) { fprint(stderr, "ftl: bad read\n"); exit; } ftl = ftls; nb = n/Bsize; offset /= Bsize; if(offset >= ftl.rwlimit) return 0; if(offset+nb > ftl.rwlimit) nb = ftl.rwlimit - offset; a = 0; for(n = 0; n < nb; n++){ (mapb, e, pb) = mapblk(ftl, offset+n); if(mapb) getflash(ftl, buf[a:], e.offset + pb*Bsize, Bsize); else memset(buf[a:], 0, Bsize); a += Bsize; } return a; } ftlwrite(buf : array of byte, n : int, offset : int) : int { ns, nb : int; a : int; e, oe : ref Terase; ob, v : int; ftl : ref Ftl; mapb : int; if(n <= 0) return 0; ftl = ftls; if(n <= 0 || n%Bsize || offset%Bsize) { fprint(stderr, "ftl: bad write\n"); exit; } nb = n/Bsize; offset /= Bsize; if(offset >= ftl.rwlimit) return 0; if(offset+nb > ftl.rwlimit) nb = ftl.rwlimit - offset; a = 0; for(n = 0; n < nb; n++){ ns = 0; while((v = allocblk(ftl)) == 0) if(!scavenge(ftl) || ++ns > 3){ fprint(stderr, "ftl: flash memory full\n"); } (mapb, oe, ob) = mapblk(ftl, offset+n); if(!mapb) oe = nil; e = ftl.unit[v>>16]; v &= 16rffff; putflash(ftl, e.offset + v*Bsize, buf[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; } mkftl(fname : string, base : int, size : int, eshift : int, op : string) : ref Ftl { i, j, nov, segblocks : int; limit : int; e : ref Terase; ftl := ref Ftl; 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< size) { fprint(stderr, "bad flash space parameters"); exit; } if(FTLDEBUG || ftl.trace || trace) print("%s flash %s #%x:#%x limit #%x\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; 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 >= 16r10000) ftl.nblock = 16r10000; ftl.vbm = array[ftl.nblock] of int; ftl.unit = array[ftl.nunit] of ref Terase; if(ftl.vbm == nil || ftl.unit == nil) { fprint(stderr, "out of mem"); exit; } for(i=0; i= 0 && ftl.nunit <= 1) { fprint(stderr, "ftl: no valid flash data units"); exit; } if(ftl.xfer < 0) fprint(stderr, "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; } ftlfree(ftl : ref Ftl) { if(ftl != nil){ ftl.unit = nil; ftl.vbm = nil; ftl = nil; } } # # this simple greedy algorithm weighted by nerase does seem to lead # to even wear of erase units (cf. the eNVy file system) # bestcopy(ftl : ref Ftl) : ref Terase { e, be : ref Terase; i : int; be = nil; for(i=0; i= be.ndead)) be = e; return be; } copyunit(ftl : ref Ftl, from : ref Terase, too : ref Terase) : int { i, nb : int; id := array[2] of byte; bam : array of byte; buf : array of byte; v, bno : int; if(FTLDEBUG || ftl.trace || trace) print("ftl: copying %d (#%x) to #%x\n", from.id, from.offset, too.offset); too.nbam = 0; too.bam = nil; bam = nil; buf = array[Bsize] of byte; if(buf == nil) return 0; PUT2(id, XferBusy); putflash(ftl, too.offset+O_ID, id, 2); # make new BAM nb = from.nbam*4; bam = array[nb] of byte; memmove(bam, from.bam, nb); too.nused = 0; too.nbad = 0; too.nfree = 0; too.ndead = 0; for(i = 0; i < from.nbam; i++) bv := GET4(bam[4*i:]); case(bv){ Bwriting or Bdeleted or Bfree => PUT4(bam[4*i:], Bfree); too.nfree++; break; * => case(bv&BlockType){ DataBlock or ReplacePage => v = bv; bno = BNO(v & ~BlockType); if(i < ftl.fstart || bno >= ftl.nblock){ print("ftl: unit %d:#%x bad bam[%d]=#%x\n", from.x, from.id, i, v); too.nfree++; PUT4(bam[4*i:], Bfree); break; } getflash(ftl, buf, from.offset+i*Bsize, Bsize); putflash(ftl, too.offset+i*Bsize, buf, Bsize); too.nused++; break; ControlBlock => too.nused++; break; * => # case BadBlock: # it isn't necessarily bad in this unit too.nfree++; PUT4(bam[4*i:], Bfree); break; } } # for(i=0; i 1) # print("to[%d]=#%x\n", i, v); # PUT4(bam[4*i:], v); # } putflash(ftl, too.bamoffset, bam, nb); # BUG: PUT4 ? IS IT ? # for(i=0; i= ftl.nunit) i = 0; }while(i != ftl.lastx); return 0; } mapblk(ftl : ref Ftl, bno : int) : (int, ref Terase, int) { v : int; x : int; if(bno < ftl.nblock){ v = ftl.vbm[bno]; if(v == 0 || v == ~0) return (0, nil, 0); x = v>>16; if(x >= ftl.nunit || x == ftl.xfer || ftl.unit[x] == nil){ print("ftl: corrupt format: bad block mapping %d . unit #%x\n", bno, x); return (0, nil, 0); } return (1, ftl.unit[x], v & 16rFFFF); } return (0, nil, 0); } eraseinit(ftl : ref Ftl, offset : int, id : int, nerase : int) { m : array of byte; bam : array of byte; i, nov : int; nov = ((ftl.segsize/Bsize)*4 + BAMoffset + Bsize - 1)/Bsize; # number of overhead blocks (header, and BAM itself) if(nov*Bsize >= ftl.segsize) { fprint(stderr, "ftl -- too small for files"); exit; } eraseflash(ftl, offset); m = array[ERASEHDRLEN] of byte; if(m == nil) { fprint(stderr, "nomem\n"); exit; } memset(m, 16rFF, len m); m[O_LINKTUPLE+0] = byte 16r13; m[O_LINKTUPLE+1] = byte 16r3; memmove(m[O_LINKTUPLE+2:], array of byte "CIS", 3); m[O_ORGTUPLE+0] = byte 16r46; m[O_ORGTUPLE+1] = byte 16r57; m[O_ORGTUPLE+2] = byte 16r00; memmove(m[O_ORGTUPLE+3:], array of byte "FTL100\0", 7); m[O_NXFER] = byte 1; PUT4(m[O_NERASE:], nerase); PUT2(m[O_ID:], id); m[O_BSHIFT] = byte ftl.bshift; m[O_ESHIFT] = byte ftl.eshift; PUT2(m[O_PSTART:], 0); PUT2(m[O_NUNITS:], ftl.nunit); PUT4(m[O_PSIZE:], ftl.size - nov*Bsize); PUT4(m[O_VBMBASE:], -1); # we always calculate the VBM (16rffffffff) PUT2(m[O_NVBM:], 0); m[O_FLAGS] = byte 0; m[O_CODE] = byte 16rFF; memmove(m[O_SERIAL:], array of byte "Inf1", 4); PUT4(m[O_ALTOFFSET:], 0); PUT4(m[O_BAMOFFSET:], BAMoffset); putflash(ftl, offset, m, ERASEHDRLEN); m = nil; if(id == XferID) return; nov *= 4; # now bytes of BAM bam = array[nov] of byte; if(bam == nil) { fprint(stderr, "nomem"); exit; } for(i=0; i break; DataBlock => # add to VBM if(v & (1<<31)) break; # negative => VBM page, ignored bno = BNO(v & ~BlockType); if(i < ftl.fstart || bno >= ftl.nblock){ print("ftl: unit %d:#%x bad bam[%d]=#%x\n", e.x, e.id, i, v); e.nbad++; break; } ftl.vbm[bno] = (e.x<<16) | i; e.nused++; break; ReplacePage => # replacement VBM page; ignored break; BadBlock => e.nbad++; break; * => print("ftl: unit %d:#%x bad bam[%d]=%x\n", e.x, e.id, i, v); } } } return e; } erasefree(e : ref Terase) { e.bam = nil; e = nil; } eraseflash(ftl : ref Ftl, offset : int) { offset += ftl.base; if(FTLDEBUG || ftl.trace || trace) print("ftl: erase seg @#%x\n", offset); memset(flashm[offset:], 16rff, secsize); } putflash(ftl : ref Ftl, offset : int, buf : array of byte, n : int) { offset += ftl.base; if(ftl.trace || trace) print("ftl: write(#%x, %d)\n", offset, n); memmove(flashm[offset:], buf, n); } getflash(ftl : ref Ftl, buf : array of byte, offset : int, n : int) { offset += ftl.base; if(ftl.trace || trace) print("ftl: read(#%x, %d)\n", offset, n); memmove(buf, flashm[offset:], n); } BUFSIZE : con 8192; main(argv : list of string) { k, r, sz, offset : int = 0; buf, buf1 : array of byte; fd1, fd2 : ref FD; if (len argv != 5) { fprint(stderr, "usage: %s flashsize secsize kfsfile flashfile\n", hd argv); exit; } flashsize = atoi(hd tl argv); secsize = atoi(hd tl tl argv); fd1 = open(hd tl tl tl argv, OREAD); fd2 = create(hd tl tl tl tl argv, OWRITE, 8r644); if (fd1 == nil || fd2 == nil) { fprint(stderr, "bad io files\n"); exit; } if(secsize == 0 || secsize > flashsize || secsize&(secsize-1) || 0&(secsize-1) || flashsize == 0 || flashsize != Nolimit && flashsize&(secsize-1)) { fprint(stderr, "ftl: bad sizes\n"); exit; } for(k=0; k<32 && (1<Context, argl : list of string) { sys = load Sys Sys->PATH; stderr = sys->fildes(2); main(argl); } memset(d : array of byte, v : int, n : int) { for (i := 0; i < n; i++) d[i] = byte v; } memmove(d : array of byte, s : array of byte, n : int) { d[0:] = s[0:n]; } memcmp(s1 : array of byte, s2 : array of byte, n : int) : int { for (i := 0; i < n; i++) { if (s1[i] < s2[i]) return -1; if (s1[i] > s2[i]) return 1; } return 0; } atoi(s : string) : int { v : int; base := 10; n := len s; neg := 0; for (i := 0; i < n && (s[i] == ' ' || s[i] == '\t'); i++) ; if (s[i] == '+' || s[i] == '-') { if (s[i] == '-') neg = 1; i++; } if (n-i >= 2 && s[i] == '0' && s[i+1] == 'x') { base = 16; i += 2; } else if (n-i >= 1 && s[i] == '0') { base = 8; i++; } m := 0; for(; i < n; i++) { c := s[i]; case c { 'a' to 'z' => v = c - 'a' + 10; 'A' to 'Z' => v = c - 'A' + 10; '0' to '9' => v = c - '0'; * => fprint(stderr, "ftl: bad character in number %s\n", s); exit; } if(v >= base) { fprint(stderr, "ftl: character too big for base in %s\n", s); exit; } m = m * base + v; } if(neg) m = -m; return m; } # little endian GET2(b : array of byte) : int { return ((int b[1]) << 8) | (int b[0]); } GET4(b : array of byte) : int { return ((int b[3]) << 24) | ((int b[2]) << 16) | ((int b[1]) << 8) | (int b[0]); } PUT2(b : array of byte, v : int) { b[1] = byte (v>>8); b[0] = byte v; } PUT4(b : array of byte, v : int) { b[3] = byte (v>>24); b[2] = byte (v>>16); b[1] = byte (v>>8); b[0] = byte v; }