1 #include <u.h> 2 #include <libc.h> 3 #include "cformat.h" 4 #include "lru.h" 5 #include "bcache.h" 6 #include "disk.h" 7 8 int icformat(Disk*, ulong); 9 10 /* 11 * read in the disk structures, return -1 if the format 12 * is inconsistent. 13 */ 14 int 15 dinit(Disk *d, int f, int psize, char *expname) 16 { 17 ulong i; 18 uvlong length; 19 char buf[1024]; 20 Bbuf *b; 21 Dalloc *ba; 22 Dir *dir; 23 24 /* 25 * get disk size 26 */ 27 dir = dirfstat(f); 28 if(dir == nil){ 29 perror("dinit: stat"); 30 return -1; 31 } 32 length = dir->length; 33 free(dir); 34 35 /* 36 * read first physical block to get logical block size, # of inodes, 37 * and # of allocation blocks 38 */ 39 if(seek(f, 0, 0) < 0){ 40 perror("dinit: seek"); 41 return -1; 42 } 43 if(read(f, buf, sizeof(buf)) != sizeof(buf)){ 44 perror("dinit: read"); 45 return -1; 46 } 47 ba = (Dalloc*)buf; 48 if(ba->bsize <= 0){ 49 fprint(2, "dinit: bsize 0x%lux<= 0\n", ba->bsize); 50 return -1; 51 } 52 if((ba->bsize % psize) != 0){ 53 fprint(2, "dinit: logical bsize (%lud) not multiple of physical (%ud)\n", 54 ba->bsize, psize); 55 return -1; 56 } 57 d->bsize = ba->bsize; 58 d->nb = length/d->bsize; 59 d->b2b = (d->bsize - sizeof(Dahdr))*8; 60 d->nab = (d->nb+d->b2b-1)/d->b2b; 61 d->p2b = d->bsize/sizeof(Dptr); 62 strncpy(d->name, ba->name, sizeof d->name); 63 64 if (expname != nil && strncmp(d->name, expname, sizeof d->name) != 0) { 65 /* Mismatch with recorded name; fail here to force a format */ 66 fprint(2, "cfs: name mismatch\n"); 67 return -1; 68 } 69 70 /* 71 * check allocation blocks for consistency 72 */ 73 if(bcinit(d, f, d->bsize) < 0){ 74 fprint(2, "dinit: couldn't init block cache\n"); 75 return -1; 76 } 77 for(i = 0; i < d->nab; i++){ 78 b = bcread(d, i); 79 if(b == 0){ 80 perror("dinit: read"); 81 return -1; 82 } 83 ba = (Dalloc*)b->data; 84 if(ba->magic != Amagic){ 85 fprint(2, "dinit: bad magic in alloc block %uld\n", i); 86 return -1; 87 } 88 if(d->bsize != ba->bsize){ 89 fprint(2, "dinit: bad bsize in alloc block %uld\n", i); 90 return -1; 91 } 92 if(d->nab != ba->nab){ 93 fprint(2, "dinit: bad nab in alloc block %uld\n", i); 94 return -1; 95 } 96 if(strncmp(d->name, ba->name, sizeof(d->name))){ 97 fprint(2, "dinit: bad name in alloc block %uld\n", i); 98 return -1; 99 } 100 } 101 return 0; 102 } 103 104 /* 105 * format the disk as a cache 106 */ 107 int 108 dformat(Disk *d, int f, char *name, ulong bsize, ulong psize) 109 { 110 int i; 111 uvlong length; 112 Bbuf *b; 113 Dalloc *ba; 114 Dir *dir; 115 Dptr dptr; 116 117 fprint(2, "formatting disk\n"); 118 119 /* 120 * calculate basic numbers 121 */ 122 dir = dirfstat(f); 123 if(dir == nil) 124 return -1; 125 length = dir->length; 126 d->bsize = bsize; 127 if((d->bsize % psize) != 0){ 128 fprint(2, "cfs: logical bsize not multiple of physical\n"); 129 return -1; 130 } 131 d->nb = length/d->bsize; 132 d->b2b = (d->bsize - sizeof(Dahdr))*8; 133 d->nab = (d->nb+d->b2b-1)/d->b2b; 134 d->p2b = d->bsize/sizeof(Dptr); 135 136 /* 137 * init allocation blocks 138 */ 139 if(bcinit(d, f, d->bsize) < 0) 140 return -1; 141 for(i = 0; i < d->nab; i++){ 142 b = bcalloc(d, i); 143 if(b == 0){ 144 perror("cfs: bcalloc"); 145 return -1; 146 } 147 memset(b->data, 0, d->bsize); 148 ba = (Dalloc*)b->data; 149 ba->magic = Amagic; 150 ba->bsize = d->bsize; 151 ba->nab = d->nab; 152 strncpy(ba->name, name, sizeof(ba->name)); 153 bcmark(d, b); 154 } 155 156 /* 157 * allocate allocation blocks 158 */ 159 for(i = 0; i < d->nab; i++) 160 if(dalloc(d, &dptr) == Notabno){ 161 fprint(2, "can't allocate allocation blocks\n"); 162 return -1; 163 } 164 165 return bcsync(d); 166 } 167 168 /* 169 * allocate a block from a bit vector page 170 * 171 * a return value of Notabno means no blocks left 172 */ 173 static ulong 174 _balloc(Dalloc *ba, ulong max) 175 { 176 int len; /* number of valid words */ 177 ulong i; /* bit position in long */ 178 ulong m; /* 1<<i */ 179 ulong v; /* old value of long */ 180 ulong *p, *e; 181 182 /* 183 * find a word with a 0 bit 184 */ 185 len = (max+BtoUL-1)/BtoUL; 186 for(p = ba->bits, e = p + len; p < e; p++) 187 if(*p != 0xFFFFFFFF) 188 break; 189 if(p == e) 190 return Notabno; 191 192 /* 193 * find the first 0 bit 194 */ 195 v = *p; 196 for(m = 1, i = 0; i < BtoUL; i++, m <<= 1) 197 if((m|v) != v) 198 break; 199 200 /* 201 * calculate block number 202 */ 203 i += (p - ba->bits)*BtoUL; 204 if(i >= max) 205 return Notabno; 206 207 /* 208 * set bit to 1 209 */ 210 *p = v | m; 211 return i; 212 } 213 214 /* 215 * allocate a block 216 * 217 * return Notabno if none left 218 */ 219 ulong 220 dalloc(Disk *d, Dptr *p) 221 { 222 ulong bno, max, rv; 223 Bbuf *b; 224 Dalloc *ba; 225 226 max = d->nb; 227 for(bno = 0; bno < d->nab; bno++){ 228 b = bcread(d, bno); 229 ba = (Dalloc*)b->data; 230 rv = _balloc(ba, max > d->b2b ? d->b2b : max); 231 if(rv != Notabno){ 232 rv = bno*d->b2b + rv; 233 if(p){ 234 p->start = p->end = 0; 235 p->bno = rv; 236 } 237 bcmark(d, b); 238 return rv; 239 } 240 max -= d->b2b; 241 } 242 if(p) 243 p->bno = Notabno; 244 return Notabno; 245 } 246 247 /* 248 * allocate a block of pointers 249 */ 250 ulong 251 dpalloc(Disk *d, Dptr *p) 252 { 253 Bbuf *b; 254 Dptr *sp, *ep; 255 256 if(dalloc(d, p) == Notabno) 257 return Notabno; 258 259 /* 260 * allocate the page and invalidate all the 261 * pointers 262 */ 263 b = bcalloc(d, p->bno); 264 if(b == 0) 265 return -1; 266 sp = (Dptr*)b->data; 267 for(ep = sp + d->p2b; sp < ep; sp++){ 268 sp->bno = Notabno; 269 sp->start = sp->end = 0; 270 } 271 p->bno |= Indbno; 272 p->start = 0; 273 p->end = d->bsize; 274 275 /* 276 * mark the page as dirty 277 */ 278 bcmark(d, b); 279 return 0; 280 } 281 282 /* 283 * free a block 284 */ 285 int 286 _bfree(Disk *d, ulong i) 287 { 288 ulong bno, m; 289 ulong *p; 290 Bbuf *b; 291 Dalloc *ba; 292 293 /* 294 * get correct allocation block 295 */ 296 bno = i/d->b2b; 297 if(bno >= d->nab) 298 return -1; 299 b = bcread(d, bno); 300 if(b == 0) 301 return -1; 302 ba = (Dalloc*)b->data; 303 304 /* 305 * change bit 306 */ 307 i -= bno*d->b2b; 308 p = ba->bits + (i/BtoUL); 309 m = 1<<(i%BtoUL); 310 *p &= ~m; 311 bcmark(d, b); 312 313 return 0; 314 } 315 316 /* 317 * free a block (or blocks) 318 */ 319 int 320 dfree(Disk *d, Dptr *dp) 321 { 322 ulong bno; 323 Dptr *sp, *ep; 324 Bbuf *b; 325 326 bno = dp->bno; 327 dp->bno = Notabno; 328 329 /* 330 * nothing to free 331 */ 332 if(bno == Notabno) 333 return 0; 334 335 /* 336 * direct pointer 337 */ 338 if((bno & Indbno) == 0) 339 return _bfree(d, bno); 340 341 /* 342 * first indirect page 343 */ 344 bno &= ~Indbno; 345 _bfree(d, bno); 346 347 /* 348 * then all the pages it points to 349 * 350 * DANGER: this algorithm may fail if there are more 351 * allocation blocks than block buffers 352 */ 353 b = bcread(d, bno); 354 if(b == 0) 355 return -1; 356 sp = (Dptr*)b->data; 357 for(ep = sp + d->p2b; sp < ep; sp++) 358 if(dfree(d, sp) < 0) 359 return -1; 360 return 0; 361 } 362