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 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 /* 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 return 0; 96 } 97 98 /* 99 * format the disk as a cache 100 */ 101 int 102 dformat(Disk *d, int f, char *name, ulong bsize, ulong psize) 103 { 104 int i; 105 uvlong length; 106 Bbuf *b; 107 Dalloc *ba; 108 Dir *dir; 109 Dptr dptr; 110 111 fprint(2, "formatting disk\n"); 112 113 /* 114 * calculate basic numbers 115 */ 116 dir = dirfstat(f); 117 if(dir == nil) 118 return -1; 119 length = dir->length; 120 d->bsize = bsize; 121 if((d->bsize % psize) != 0){ 122 fprint(2, "cfs: logical bsize not multiple of physical\n"); 123 return -1; 124 } 125 d->nb = length/d->bsize; 126 d->b2b = (d->bsize - sizeof(Dahdr))*8; 127 d->nab = (d->nb+d->b2b-1)/d->b2b; 128 d->p2b = d->bsize/sizeof(Dptr); 129 130 /* 131 * init allocation blocks 132 */ 133 if(bcinit(d, f, d->bsize) < 0) 134 return -1; 135 for(i = 0; i < d->nab; i++){ 136 b = bcalloc(d, i); 137 if(b == 0){ 138 perror("cfs: bcalloc"); 139 return -1; 140 } 141 memset(b->data, 0, d->bsize); 142 ba = (Dalloc*)b->data; 143 ba->magic = Amagic; 144 ba->bsize = d->bsize; 145 ba->nab = d->nab; 146 strncpy(ba->name, name, sizeof(ba->name)); 147 bcmark(d, b); 148 } 149 150 /* 151 * allocate allocation blocks 152 */ 153 for(i = 0; i < d->nab; i++) 154 if(dalloc(d, &dptr) == Notabno){ 155 fprint(2, "can't allocate allocation blocks\n"); 156 return -1; 157 } 158 159 return bcsync(d); 160 } 161 162 /* 163 * allocate a block from a bit vector page 164 * 165 * a return value of Notabno means no blocks left 166 */ 167 static ulong 168 _balloc(Dalloc *ba, ulong max) 169 { 170 int len; /* number of valid words */ 171 ulong i; /* bit position in long */ 172 ulong m; /* 1<<i */ 173 ulong v; /* old value of long */ 174 ulong *p, *e; 175 176 /* 177 * find a word with a 0 bit 178 */ 179 len = (max+BtoUL-1)/BtoUL; 180 for(p = ba->bits, e = p + len; p < e; p++) 181 if(*p != 0xFFFFFFFF) 182 break; 183 if(p == e) 184 return Notabno; 185 186 /* 187 * find the first 0 bit 188 */ 189 v = *p; 190 for(m = 1, i = 0; i < BtoUL; i++, m <<= 1) 191 if((m|v) != v) 192 break; 193 194 /* 195 * calculate block number 196 */ 197 i += (p - ba->bits)*BtoUL; 198 if(i >= max) 199 return Notabno; 200 201 /* 202 * set bit to 1 203 */ 204 *p = v | m; 205 return i; 206 } 207 208 /* 209 * allocate a block 210 * 211 * return Notabno if none left 212 */ 213 ulong 214 dalloc(Disk *d, Dptr *p) 215 { 216 ulong bno, max, rv; 217 Bbuf *b; 218 Dalloc *ba; 219 220 max = d->nb; 221 for(bno = 0; bno < d->nab; bno++){ 222 b = bcread(d, bno); 223 ba = (Dalloc*)b->data; 224 rv = _balloc(ba, max > d->b2b ? d->b2b : max); 225 if(rv != Notabno){ 226 rv = bno*d->b2b + rv; 227 if(p){ 228 p->start = p->end = 0; 229 p->bno = rv; 230 } 231 bcmark(d, b); 232 return rv; 233 } 234 max -= d->b2b; 235 } 236 if(p) 237 p->bno = Notabno; 238 return Notabno; 239 } 240 241 /* 242 * allocate a block of pointers 243 */ 244 ulong 245 dpalloc(Disk *d, Dptr *p) 246 { 247 Bbuf *b; 248 Dptr *sp, *ep; 249 250 if(dalloc(d, p) == Notabno) 251 return Notabno; 252 253 /* 254 * allocate the page and invalidate all the 255 * pointers 256 */ 257 b = bcalloc(d, p->bno); 258 if(b == 0) 259 return -1; 260 sp = (Dptr*)b->data; 261 for(ep = sp + d->p2b; sp < ep; sp++){ 262 sp->bno = Notabno; 263 sp->start = sp->end = 0; 264 } 265 p->bno |= Indbno; 266 p->start = 0; 267 p->end = d->bsize; 268 269 /* 270 * mark the page as dirty 271 */ 272 bcmark(d, b); 273 return 0; 274 } 275 276 /* 277 * free a block 278 */ 279 int 280 _bfree(Disk *d, ulong i) 281 { 282 ulong bno, m; 283 ulong *p; 284 Bbuf *b; 285 Dalloc *ba; 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 ulong bno; 317 Dptr *sp, *ep; 318 Bbuf *b; 319 320 bno = dp->bno; 321 dp->bno = Notabno; 322 323 /* 324 * nothing to free 325 */ 326 if(bno == Notabno) 327 return 0; 328 329 /* 330 * direct pointer 331 */ 332 if((bno & Indbno) == 0) 333 return _bfree(d, bno); 334 335 /* 336 * first indirect page 337 */ 338 bno &= ~Indbno; 339 _bfree(d, bno); 340 341 /* 342 * then all the pages it points to 343 * 344 * DANGER: this algorithm may fail if there are more 345 * allocation blocks than block buffers 346 */ 347 b = bcread(d, bno); 348 if(b == 0) 349 return -1; 350 sp = (Dptr*)b->data; 351 for(ep = sp + d->p2b; sp < ep; sp++) 352 if(dfree(d, sp) < 0) 353 return -1; 354 return 0; 355 } 356