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) 16 { 17 Dir *dir; 18 char buf[1024]; 19 Dalloc *ba; 20 uvlong length; 21 ulong i; 22 Bbuf *b; 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, number of inodes, 37 * and number 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 /* 65 * check allocation blocks for consistency 66 */ 67 if(bcinit(d, f, d->bsize) < 0){ 68 fprint(2, "dinit: couldn't init block cache\n"); 69 return -1; 70 } 71 for(i = 0; i < d->nab; i++){ 72 b = bcread(d, i); 73 if(b == 0){ 74 perror("dinit: read"); 75 return -1; 76 } 77 ba = (Dalloc*)b->data; 78 if(ba->magic != Amagic){ 79 fprint(2, "dinit: bad magic in alloc block %uld\n", i); 80 return -1; 81 } 82 if(d->bsize != ba->bsize){ 83 fprint(2, "dinit: bad bsize in alloc block %uld\n", i); 84 return -1; 85 } 86 if(d->nab != ba->nab){ 87 fprint(2, "dinit: bad nab in alloc block %uld\n", i); 88 return -1; 89 } 90 if(strncmp(d->name, ba->name, sizeof(d->name))){ 91 fprint(2, "dinit: bad name in alloc block %uld\n", i); 92 return -1; 93 } 94 95 } 96 97 return 0; 98 } 99 100 /* 101 * format the disk as a cache 102 */ 103 int 104 dformat(Disk *d, int f, char *name, ulong bsize, ulong psize) 105 { 106 int i; 107 Dir *dir; 108 uvlong length; 109 Bbuf *b; 110 Dalloc *ba; 111 Dptr dptr; 112 113 fprint(2, "formatting disk\n"); 114 115 /* 116 * calculate basic numbers 117 */ 118 dir = dirfstat(f); 119 if(dir == nil) 120 return -1; 121 length = dir->length; 122 d->bsize = bsize; 123 if((d->bsize % psize) != 0){ 124 fprint(2, "cfs: logical bsize not multiple of physical\n"); 125 return -1; 126 } 127 d->nb = length/d->bsize; 128 d->b2b = (d->bsize - sizeof(Dahdr))*8; 129 d->nab = (d->nb+d->b2b-1)/d->b2b; 130 d->p2b = d->bsize/sizeof(Dptr); 131 132 /* 133 * init allocation blocks 134 */ 135 if(bcinit(d, f, d->bsize) < 0) 136 return -1; 137 for(i = 0; i < d->nab; i++){ 138 b = bcalloc(d, i); 139 if(b == 0){ 140 perror("cfs: bcalloc"); 141 return -1; 142 } 143 memset(b->data, 0, d->bsize); 144 ba = (Dalloc*)b->data; 145 ba->magic = Amagic; 146 ba->bsize = d->bsize; 147 ba->nab = d->nab; 148 strncpy(ba->name, name, sizeof(ba->name)); 149 bcmark(d, b); 150 } 151 152 /* 153 * allocate allocation blocks 154 */ 155 for(i = 0; i < d->nab; i++) 156 if(dalloc(d, &dptr) < 0){ 157 fprint(2, "can't allocate allocation blocks\n"); 158 return -1; 159 } 160 161 return bcsync(d); 162 } 163 164 /* 165 * allocate a block from a bit vector page 166 * 167 * a return value of Notabno means no blocks left 168 */ 169 static ulong 170 _balloc(Dalloc *ba, ulong max) 171 { 172 ulong *p; 173 ulong *e; 174 ulong i; /* bit position in long */ 175 ulong m; /* 1<<i */ 176 ulong v; /* old value of long */ 177 int len; /* number of valid words */ 178 179 /* 180 * find a word with a 0 bit 181 */ 182 len = (max+BtoUL-1)/BtoUL; 183 for(p = ba->bits, e = p + len; p < e; p++) 184 if(*p != 0xFFFFFFFF) 185 break; 186 if(p == e) 187 return Notabno; 188 189 /* 190 * find the first 0 bit 191 */ 192 v = *p; 193 for(m = 1, i = 0; i<BtoUL; i++, m<<=1) 194 if((m|v) != v) 195 break; 196 197 /* 198 * calculate block number 199 */ 200 i += (p - ba->bits)*BtoUL; 201 if(i >= max) 202 return Notabno; 203 204 /* 205 * set bit to 1 206 */ 207 *p = v | m; 208 return i; 209 } 210 211 /* 212 * allocate a block 213 * 214 * return Notabno if none left 215 */ 216 ulong 217 dalloc(Disk *d, Dptr *p) 218 { 219 ulong bno; 220 Bbuf *b; 221 Dalloc *ba; 222 ulong rv; 223 ulong max; 224 225 max = d->nb; 226 for(bno = 0; bno < d->nab; bno++){ 227 b = bcread(d, bno); 228 ba = (Dalloc*)b->data; 229 rv = _balloc(ba, max > d->b2b ? d->b2b : max); 230 if(rv != Notabno){ 231 rv = bno*d->b2b + rv; 232 if(p){ 233 p->start = p->end = 0; 234 p->bno = rv; 235 } 236 bcmark(d, b); 237 return rv; 238 } 239 max -= d->b2b; 240 } 241 if(p) 242 p->bno = Notabno; 243 return Notabno; 244 } 245 246 /* 247 * allocate a block of pointers 248 */ 249 ulong 250 dpalloc(Disk *d, Dptr *p) 251 { 252 Bbuf *b; 253 Dptr *sp; 254 Dptr *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 *p; 289 ulong m; 290 Bbuf *b; 291 Dalloc *ba; 292 ulong bno; 293 294 /* 295 * get correct allocation block 296 */ 297 bno = i/d->b2b; 298 if(bno >= d->nab) 299 return -1; 300 b = bcread(d, bno); 301 if(b == 0) 302 return -1; 303 ba = (Dalloc*)b->data; 304 305 /* 306 * change bit 307 */ 308 i -= bno*d->b2b; 309 p = ba->bits + (i/BtoUL); 310 m = 1<<(i%BtoUL); 311 *p &= ~m; 312 bcmark(d, b); 313 314 return 0; 315 } 316 317 /* 318 * free a block (or blocks) 319 */ 320 int 321 dfree(Disk *d, Dptr *dp) 322 { 323 Dptr *sp; 324 Dptr *ep; 325 Bbuf *b; 326 ulong bno; 327 328 bno = dp->bno; 329 dp->bno = Notabno; 330 331 /* 332 * nothing to free 333 */ 334 if(bno == Notabno) 335 return 0; 336 337 /* 338 * direct pointer 339 */ 340 if((bno & Indbno) == 0) 341 return _bfree(d, bno); 342 343 /* 344 * first indirect page 345 */ 346 bno &= ~Indbno; 347 _bfree(d, bno); 348 349 /* 350 * then all the pages it points to 351 * 352 * DANGER: this algorithm may fail is their are more 353 * allocation blocks than block buffers 354 */ 355 b = bcread(d, bno); 356 if(b == 0) 357 return -1; 358 sp = (Dptr*)b->data; 359 for(ep = sp + d->p2b; sp < ep; sp++) 360 if(dfree(d, sp) < 0) 361 return -1; 362 363 return 0; 364 } 365