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