13e12c5d1SDavid du Colombier #include <u.h>
23e12c5d1SDavid du Colombier #include <libc.h>
33e12c5d1SDavid du Colombier #include "cformat.h"
43e12c5d1SDavid du Colombier #include "lru.h"
53e12c5d1SDavid du Colombier #include "bcache.h"
63e12c5d1SDavid du Colombier #include "disk.h"
73e12c5d1SDavid du Colombier
83e12c5d1SDavid du Colombier int icformat(Disk*, ulong);
93e12c5d1SDavid du Colombier
103e12c5d1SDavid du Colombier /*
113e12c5d1SDavid du Colombier * read in the disk structures, return -1 if the format
123e12c5d1SDavid du Colombier * is inconsistent.
133e12c5d1SDavid du Colombier */
143e12c5d1SDavid du Colombier int
dinit(Disk * d,int f,int psize,char * expname)15*7c70c028SDavid du Colombier dinit(Disk *d, int f, int psize, char *expname)
163e12c5d1SDavid du Colombier {
173e12c5d1SDavid du Colombier ulong i;
1841fb754aSDavid du Colombier uvlong length;
1941fb754aSDavid du Colombier char buf[1024];
203e12c5d1SDavid du Colombier Bbuf *b;
2141fb754aSDavid du Colombier Dalloc *ba;
2241fb754aSDavid du Colombier Dir *dir;
233e12c5d1SDavid du Colombier
243e12c5d1SDavid du Colombier /*
253e12c5d1SDavid du Colombier * get disk size
263e12c5d1SDavid du Colombier */
279a747e4fSDavid du Colombier dir = dirfstat(f);
289a747e4fSDavid du Colombier if(dir == nil){
293e12c5d1SDavid du Colombier perror("dinit: stat");
303e12c5d1SDavid du Colombier return -1;
313e12c5d1SDavid du Colombier }
329a747e4fSDavid du Colombier length = dir->length;
339a747e4fSDavid du Colombier free(dir);
343e12c5d1SDavid du Colombier
353e12c5d1SDavid du Colombier /*
3641fb754aSDavid du Colombier * read first physical block to get logical block size, # of inodes,
3741fb754aSDavid du Colombier * and # of allocation blocks
383e12c5d1SDavid du Colombier */
393e12c5d1SDavid du Colombier if(seek(f, 0, 0) < 0){
403e12c5d1SDavid du Colombier perror("dinit: seek");
413e12c5d1SDavid du Colombier return -1;
423e12c5d1SDavid du Colombier }
433e12c5d1SDavid du Colombier if(read(f, buf, sizeof(buf)) != sizeof(buf)){
443e12c5d1SDavid du Colombier perror("dinit: read");
453e12c5d1SDavid du Colombier return -1;
463e12c5d1SDavid du Colombier }
473e12c5d1SDavid du Colombier ba = (Dalloc*)buf;
483e12c5d1SDavid du Colombier if(ba->bsize <= 0){
493e12c5d1SDavid du Colombier fprint(2, "dinit: bsize 0x%lux<= 0\n", ba->bsize);
503e12c5d1SDavid du Colombier return -1;
513e12c5d1SDavid du Colombier }
523e12c5d1SDavid du Colombier if((ba->bsize % psize) != 0){
537dd7cddfSDavid du Colombier fprint(2, "dinit: logical bsize (%lud) not multiple of physical (%ud)\n",
543e12c5d1SDavid du Colombier ba->bsize, psize);
553e12c5d1SDavid du Colombier return -1;
563e12c5d1SDavid du Colombier }
573e12c5d1SDavid du Colombier d->bsize = ba->bsize;
589a747e4fSDavid du Colombier d->nb = length/d->bsize;
593e12c5d1SDavid du Colombier d->b2b = (d->bsize - sizeof(Dahdr))*8;
603e12c5d1SDavid du Colombier d->nab = (d->nb+d->b2b-1)/d->b2b;
613e12c5d1SDavid du Colombier d->p2b = d->bsize/sizeof(Dptr);
62*7c70c028SDavid du Colombier strncpy(d->name, ba->name, sizeof d->name);
63*7c70c028SDavid du Colombier
64*7c70c028SDavid du Colombier if (expname != nil && strncmp(d->name, expname, sizeof d->name) != 0) {
65*7c70c028SDavid du Colombier /* Mismatch with recorded name; fail here to force a format */
66*7c70c028SDavid du Colombier fprint(2, "cfs: name mismatch\n");
67*7c70c028SDavid du Colombier return -1;
68*7c70c028SDavid du Colombier }
693e12c5d1SDavid du Colombier
703e12c5d1SDavid du Colombier /*
713e12c5d1SDavid du Colombier * check allocation blocks for consistency
723e12c5d1SDavid du Colombier */
733e12c5d1SDavid du Colombier if(bcinit(d, f, d->bsize) < 0){
743e12c5d1SDavid du Colombier fprint(2, "dinit: couldn't init block cache\n");
753e12c5d1SDavid du Colombier return -1;
763e12c5d1SDavid du Colombier }
773e12c5d1SDavid du Colombier for(i = 0; i < d->nab; i++){
783e12c5d1SDavid du Colombier b = bcread(d, i);
793e12c5d1SDavid du Colombier if(b == 0){
803e12c5d1SDavid du Colombier perror("dinit: read");
813e12c5d1SDavid du Colombier return -1;
823e12c5d1SDavid du Colombier }
833e12c5d1SDavid du Colombier ba = (Dalloc*)b->data;
843e12c5d1SDavid du Colombier if(ba->magic != Amagic){
857dd7cddfSDavid du Colombier fprint(2, "dinit: bad magic in alloc block %uld\n", i);
863e12c5d1SDavid du Colombier return -1;
873e12c5d1SDavid du Colombier }
883e12c5d1SDavid du Colombier if(d->bsize != ba->bsize){
897dd7cddfSDavid du Colombier fprint(2, "dinit: bad bsize in alloc block %uld\n", i);
903e12c5d1SDavid du Colombier return -1;
913e12c5d1SDavid du Colombier }
923e12c5d1SDavid du Colombier if(d->nab != ba->nab){
937dd7cddfSDavid du Colombier fprint(2, "dinit: bad nab in alloc block %uld\n", i);
943e12c5d1SDavid du Colombier return -1;
953e12c5d1SDavid du Colombier }
963e12c5d1SDavid du Colombier if(strncmp(d->name, ba->name, sizeof(d->name))){
977dd7cddfSDavid du Colombier fprint(2, "dinit: bad name in alloc block %uld\n", i);
983e12c5d1SDavid du Colombier return -1;
993e12c5d1SDavid du Colombier }
1003e12c5d1SDavid du Colombier }
1013e12c5d1SDavid du Colombier return 0;
1023e12c5d1SDavid du Colombier }
1033e12c5d1SDavid du Colombier
1043e12c5d1SDavid du Colombier /*
1053e12c5d1SDavid du Colombier * format the disk as a cache
1063e12c5d1SDavid du Colombier */
1073e12c5d1SDavid du Colombier int
dformat(Disk * d,int f,char * name,ulong bsize,ulong psize)1083e12c5d1SDavid du Colombier dformat(Disk *d, int f, char *name, ulong bsize, ulong psize)
1093e12c5d1SDavid du Colombier {
1103e12c5d1SDavid du Colombier int i;
1119a747e4fSDavid du Colombier uvlong length;
1123e12c5d1SDavid du Colombier Bbuf *b;
1133e12c5d1SDavid du Colombier Dalloc *ba;
11441fb754aSDavid du Colombier Dir *dir;
1153e12c5d1SDavid du Colombier Dptr dptr;
1163e12c5d1SDavid du Colombier
1173e12c5d1SDavid du Colombier fprint(2, "formatting disk\n");
1183e12c5d1SDavid du Colombier
1193e12c5d1SDavid du Colombier /*
1203e12c5d1SDavid du Colombier * calculate basic numbers
1213e12c5d1SDavid du Colombier */
1229a747e4fSDavid du Colombier dir = dirfstat(f);
1239a747e4fSDavid du Colombier if(dir == nil)
1243e12c5d1SDavid du Colombier return -1;
1259a747e4fSDavid du Colombier length = dir->length;
1263e12c5d1SDavid du Colombier d->bsize = bsize;
1273e12c5d1SDavid du Colombier if((d->bsize % psize) != 0){
1283e12c5d1SDavid du Colombier fprint(2, "cfs: logical bsize not multiple of physical\n");
1293e12c5d1SDavid du Colombier return -1;
1303e12c5d1SDavid du Colombier }
1319a747e4fSDavid du Colombier d->nb = length/d->bsize;
1323e12c5d1SDavid du Colombier d->b2b = (d->bsize - sizeof(Dahdr))*8;
1333e12c5d1SDavid du Colombier d->nab = (d->nb+d->b2b-1)/d->b2b;
1343e12c5d1SDavid du Colombier d->p2b = d->bsize/sizeof(Dptr);
1353e12c5d1SDavid du Colombier
1363e12c5d1SDavid du Colombier /*
1373e12c5d1SDavid du Colombier * init allocation blocks
1383e12c5d1SDavid du Colombier */
1393e12c5d1SDavid du Colombier if(bcinit(d, f, d->bsize) < 0)
1403e12c5d1SDavid du Colombier return -1;
1413e12c5d1SDavid du Colombier for(i = 0; i < d->nab; i++){
1423e12c5d1SDavid du Colombier b = bcalloc(d, i);
1433e12c5d1SDavid du Colombier if(b == 0){
1443e12c5d1SDavid du Colombier perror("cfs: bcalloc");
1453e12c5d1SDavid du Colombier return -1;
1463e12c5d1SDavid du Colombier }
1473e12c5d1SDavid du Colombier memset(b->data, 0, d->bsize);
1483e12c5d1SDavid du Colombier ba = (Dalloc*)b->data;
1493e12c5d1SDavid du Colombier ba->magic = Amagic;
1503e12c5d1SDavid du Colombier ba->bsize = d->bsize;
1513e12c5d1SDavid du Colombier ba->nab = d->nab;
1523e12c5d1SDavid du Colombier strncpy(ba->name, name, sizeof(ba->name));
1533e12c5d1SDavid du Colombier bcmark(d, b);
1543e12c5d1SDavid du Colombier }
1553e12c5d1SDavid du Colombier
1563e12c5d1SDavid du Colombier /*
1573e12c5d1SDavid du Colombier * allocate allocation blocks
1583e12c5d1SDavid du Colombier */
1593e12c5d1SDavid du Colombier for(i = 0; i < d->nab; i++)
16022a127bbSDavid du Colombier if(dalloc(d, &dptr) == Notabno){
1613e12c5d1SDavid du Colombier fprint(2, "can't allocate allocation blocks\n");
1623e12c5d1SDavid du Colombier return -1;
1633e12c5d1SDavid du Colombier }
1643e12c5d1SDavid du Colombier
1653e12c5d1SDavid du Colombier return bcsync(d);
1663e12c5d1SDavid du Colombier }
1673e12c5d1SDavid du Colombier
1683e12c5d1SDavid du Colombier /*
1693e12c5d1SDavid du Colombier * allocate a block from a bit vector page
1703e12c5d1SDavid du Colombier *
1713e12c5d1SDavid du Colombier * a return value of Notabno means no blocks left
1723e12c5d1SDavid du Colombier */
1733e12c5d1SDavid du Colombier static ulong
_balloc(Dalloc * ba,ulong max)1743e12c5d1SDavid du Colombier _balloc(Dalloc *ba, ulong max)
1753e12c5d1SDavid du Colombier {
17641fb754aSDavid du Colombier int len; /* number of valid words */
1773e12c5d1SDavid du Colombier ulong i; /* bit position in long */
1783e12c5d1SDavid du Colombier ulong m; /* 1<<i */
1793e12c5d1SDavid du Colombier ulong v; /* old value of long */
18041fb754aSDavid du Colombier ulong *p, *e;
1813e12c5d1SDavid du Colombier
1823e12c5d1SDavid du Colombier /*
1833e12c5d1SDavid du Colombier * find a word with a 0 bit
1843e12c5d1SDavid du Colombier */
1853e12c5d1SDavid du Colombier len = (max+BtoUL-1)/BtoUL;
1863e12c5d1SDavid du Colombier for(p = ba->bits, e = p + len; p < e; p++)
1873e12c5d1SDavid du Colombier if(*p != 0xFFFFFFFF)
1883e12c5d1SDavid du Colombier break;
1893e12c5d1SDavid du Colombier if(p == e)
1903e12c5d1SDavid du Colombier return Notabno;
1913e12c5d1SDavid du Colombier
1923e12c5d1SDavid du Colombier /*
1933e12c5d1SDavid du Colombier * find the first 0 bit
1943e12c5d1SDavid du Colombier */
1953e12c5d1SDavid du Colombier v = *p;
1963e12c5d1SDavid du Colombier for(m = 1, i = 0; i < BtoUL; i++, m <<= 1)
1973e12c5d1SDavid du Colombier if((m|v) != v)
1983e12c5d1SDavid du Colombier break;
1993e12c5d1SDavid du Colombier
2003e12c5d1SDavid du Colombier /*
2013e12c5d1SDavid du Colombier * calculate block number
2023e12c5d1SDavid du Colombier */
2033e12c5d1SDavid du Colombier i += (p - ba->bits)*BtoUL;
2043e12c5d1SDavid du Colombier if(i >= max)
2053e12c5d1SDavid du Colombier return Notabno;
2063e12c5d1SDavid du Colombier
2073e12c5d1SDavid du Colombier /*
2083e12c5d1SDavid du Colombier * set bit to 1
2093e12c5d1SDavid du Colombier */
2103e12c5d1SDavid du Colombier *p = v | m;
2113e12c5d1SDavid du Colombier return i;
2123e12c5d1SDavid du Colombier }
2133e12c5d1SDavid du Colombier
2143e12c5d1SDavid du Colombier /*
2153e12c5d1SDavid du Colombier * allocate a block
2163e12c5d1SDavid du Colombier *
2173e12c5d1SDavid du Colombier * return Notabno if none left
2183e12c5d1SDavid du Colombier */
2193e12c5d1SDavid du Colombier ulong
dalloc(Disk * d,Dptr * p)2203e12c5d1SDavid du Colombier dalloc(Disk *d, Dptr *p)
2213e12c5d1SDavid du Colombier {
22241fb754aSDavid du Colombier ulong bno, max, rv;
2233e12c5d1SDavid du Colombier Bbuf *b;
2243e12c5d1SDavid du Colombier Dalloc *ba;
2253e12c5d1SDavid du Colombier
2263e12c5d1SDavid du Colombier max = d->nb;
2273e12c5d1SDavid du Colombier for(bno = 0; bno < d->nab; bno++){
2283e12c5d1SDavid du Colombier b = bcread(d, bno);
2293e12c5d1SDavid du Colombier ba = (Dalloc*)b->data;
2303e12c5d1SDavid du Colombier rv = _balloc(ba, max > d->b2b ? d->b2b : max);
2313e12c5d1SDavid du Colombier if(rv != Notabno){
2323e12c5d1SDavid du Colombier rv = bno*d->b2b + rv;
2333e12c5d1SDavid du Colombier if(p){
2343e12c5d1SDavid du Colombier p->start = p->end = 0;
2353e12c5d1SDavid du Colombier p->bno = rv;
2363e12c5d1SDavid du Colombier }
2373e12c5d1SDavid du Colombier bcmark(d, b);
2383e12c5d1SDavid du Colombier return rv;
2393e12c5d1SDavid du Colombier }
2403e12c5d1SDavid du Colombier max -= d->b2b;
2413e12c5d1SDavid du Colombier }
2423e12c5d1SDavid du Colombier if(p)
2433e12c5d1SDavid du Colombier p->bno = Notabno;
2443e12c5d1SDavid du Colombier return Notabno;
2453e12c5d1SDavid du Colombier }
2463e12c5d1SDavid du Colombier
2473e12c5d1SDavid du Colombier /*
2483e12c5d1SDavid du Colombier * allocate a block of pointers
2493e12c5d1SDavid du Colombier */
2503e12c5d1SDavid du Colombier ulong
dpalloc(Disk * d,Dptr * p)2513e12c5d1SDavid du Colombier dpalloc(Disk *d, Dptr *p)
2523e12c5d1SDavid du Colombier {
2533e12c5d1SDavid du Colombier Bbuf *b;
25441fb754aSDavid du Colombier Dptr *sp, *ep;
2553e12c5d1SDavid du Colombier
2563e12c5d1SDavid du Colombier if(dalloc(d, p) == Notabno)
2573e12c5d1SDavid du Colombier return Notabno;
2583e12c5d1SDavid du Colombier
2593e12c5d1SDavid du Colombier /*
2603e12c5d1SDavid du Colombier * allocate the page and invalidate all the
2613e12c5d1SDavid du Colombier * pointers
2623e12c5d1SDavid du Colombier */
2633e12c5d1SDavid du Colombier b = bcalloc(d, p->bno);
2643e12c5d1SDavid du Colombier if(b == 0)
2653e12c5d1SDavid du Colombier return -1;
2663e12c5d1SDavid du Colombier sp = (Dptr*)b->data;
2673e12c5d1SDavid du Colombier for(ep = sp + d->p2b; sp < ep; sp++){
2683e12c5d1SDavid du Colombier sp->bno = Notabno;
2693e12c5d1SDavid du Colombier sp->start = sp->end = 0;
2703e12c5d1SDavid du Colombier }
2713e12c5d1SDavid du Colombier p->bno |= Indbno;
2723e12c5d1SDavid du Colombier p->start = 0;
2733e12c5d1SDavid du Colombier p->end = d->bsize;
2743e12c5d1SDavid du Colombier
2753e12c5d1SDavid du Colombier /*
2763e12c5d1SDavid du Colombier * mark the page as dirty
2773e12c5d1SDavid du Colombier */
2783e12c5d1SDavid du Colombier bcmark(d, b);
2793e12c5d1SDavid du Colombier return 0;
2803e12c5d1SDavid du Colombier }
2813e12c5d1SDavid du Colombier
2823e12c5d1SDavid du Colombier /*
2833e12c5d1SDavid du Colombier * free a block
2843e12c5d1SDavid du Colombier */
2853e12c5d1SDavid du Colombier int
_bfree(Disk * d,ulong i)2863e12c5d1SDavid du Colombier _bfree(Disk *d, ulong i)
2873e12c5d1SDavid du Colombier {
28841fb754aSDavid du Colombier ulong bno, m;
2893e12c5d1SDavid du Colombier ulong *p;
2903e12c5d1SDavid du Colombier Bbuf *b;
2913e12c5d1SDavid du Colombier Dalloc *ba;
2923e12c5d1SDavid du Colombier
2933e12c5d1SDavid du Colombier /*
2943e12c5d1SDavid du Colombier * get correct allocation block
2953e12c5d1SDavid du Colombier */
2963e12c5d1SDavid du Colombier bno = i/d->b2b;
2973e12c5d1SDavid du Colombier if(bno >= d->nab)
2983e12c5d1SDavid du Colombier return -1;
2993e12c5d1SDavid du Colombier b = bcread(d, bno);
3003e12c5d1SDavid du Colombier if(b == 0)
3013e12c5d1SDavid du Colombier return -1;
3023e12c5d1SDavid du Colombier ba = (Dalloc*)b->data;
3033e12c5d1SDavid du Colombier
3043e12c5d1SDavid du Colombier /*
3053e12c5d1SDavid du Colombier * change bit
3063e12c5d1SDavid du Colombier */
3073e12c5d1SDavid du Colombier i -= bno*d->b2b;
3083e12c5d1SDavid du Colombier p = ba->bits + (i/BtoUL);
3093e12c5d1SDavid du Colombier m = 1<<(i%BtoUL);
3103e12c5d1SDavid du Colombier *p &= ~m;
3113e12c5d1SDavid du Colombier bcmark(d, b);
3123e12c5d1SDavid du Colombier
3133e12c5d1SDavid du Colombier return 0;
3143e12c5d1SDavid du Colombier }
3153e12c5d1SDavid du Colombier
3163e12c5d1SDavid du Colombier /*
3173e12c5d1SDavid du Colombier * free a block (or blocks)
3183e12c5d1SDavid du Colombier */
3193e12c5d1SDavid du Colombier int
dfree(Disk * d,Dptr * dp)3203e12c5d1SDavid du Colombier dfree(Disk *d, Dptr *dp)
3213e12c5d1SDavid du Colombier {
3223e12c5d1SDavid du Colombier ulong bno;
32341fb754aSDavid du Colombier Dptr *sp, *ep;
32441fb754aSDavid du Colombier Bbuf *b;
3253e12c5d1SDavid du Colombier
3263e12c5d1SDavid du Colombier bno = dp->bno;
3273e12c5d1SDavid du Colombier dp->bno = Notabno;
3283e12c5d1SDavid du Colombier
3293e12c5d1SDavid du Colombier /*
3303e12c5d1SDavid du Colombier * nothing to free
3313e12c5d1SDavid du Colombier */
3323e12c5d1SDavid du Colombier if(bno == Notabno)
3333e12c5d1SDavid du Colombier return 0;
3343e12c5d1SDavid du Colombier
3353e12c5d1SDavid du Colombier /*
3363e12c5d1SDavid du Colombier * direct pointer
3373e12c5d1SDavid du Colombier */
3383e12c5d1SDavid du Colombier if((bno & Indbno) == 0)
3393e12c5d1SDavid du Colombier return _bfree(d, bno);
3403e12c5d1SDavid du Colombier
3413e12c5d1SDavid du Colombier /*
3423e12c5d1SDavid du Colombier * first indirect page
3433e12c5d1SDavid du Colombier */
3443e12c5d1SDavid du Colombier bno &= ~Indbno;
3453e12c5d1SDavid du Colombier _bfree(d, bno);
3463e12c5d1SDavid du Colombier
3473e12c5d1SDavid du Colombier /*
3483e12c5d1SDavid du Colombier * then all the pages it points to
3493e12c5d1SDavid du Colombier *
35041fb754aSDavid du Colombier * DANGER: this algorithm may fail if there are more
3513e12c5d1SDavid du Colombier * allocation blocks than block buffers
3523e12c5d1SDavid du Colombier */
3533e12c5d1SDavid du Colombier b = bcread(d, bno);
3543e12c5d1SDavid du Colombier if(b == 0)
3553e12c5d1SDavid du Colombier return -1;
3563e12c5d1SDavid du Colombier sp = (Dptr*)b->data;
3573e12c5d1SDavid du Colombier for(ep = sp + d->p2b; sp < ep; sp++)
3583e12c5d1SDavid du Colombier if(dfree(d, sp) < 0)
3593e12c5d1SDavid du Colombier return -1;
3603e12c5d1SDavid du Colombier return 0;
3613e12c5d1SDavid du Colombier }
362