dump.c (9576B)
1 #include <u.h> 2 #include <libc.h> 3 #include <bio.h> 4 #include <libsec.h> 5 #include <ctype.h> 6 #include "iso9660.h" 7 8 static void 9 md5cd(Cdimg *cd, ulong block, ulong length, uchar *digest) 10 { 11 int n; 12 uchar buf[Blocksize]; 13 DigestState *s; 14 15 s = md5(nil, 0, nil, nil); 16 while(length > 0) { 17 n = length; 18 if(n > Blocksize) 19 n = Blocksize; 20 21 Creadblock(cd, buf, block, n); 22 23 md5(buf, n, nil, s); 24 25 block++; 26 length -= n; 27 } 28 md5(nil, 0, digest, s); 29 } 30 31 static Dumpdir* 32 mkdumpdir(char *name, uchar *md5, ulong block, ulong length) 33 { 34 Dumpdir *d; 35 36 assert(block != 0); 37 38 d = emalloc(sizeof *d); 39 d->name = name; 40 memmove(d->md5, md5, sizeof d->md5); 41 d->block = block; 42 d->length = length; 43 44 return d; 45 } 46 47 static Dumpdir** 48 ltreewalkmd5(Dumpdir **l, uchar *md5) 49 { 50 int i; 51 52 while(*l) { 53 i = memcmp(md5, (*l)->md5, MD5dlen); 54 if(i < 0) 55 l = &(*l)->md5left; 56 else if(i == 0) 57 return l; 58 else 59 l = &(*l)->md5right; 60 } 61 return l; 62 } 63 64 static Dumpdir** 65 ltreewalkblock(Dumpdir **l, ulong block) 66 { 67 while(*l) { 68 if(block < (*l)->block) 69 l = &(*l)->blockleft; 70 else if(block == (*l)->block) 71 return l; 72 else 73 l = &(*l)->blockright; 74 } 75 return l; 76 } 77 78 /* 79 * Add a particular file to our binary tree. 80 */ 81 static void 82 addfile(Cdimg *cd, Dump *d, char *name, Direc *dir) 83 { 84 uchar md5[MD5dlen]; 85 Dumpdir **lblock; 86 87 assert((dir->mode & DMDIR) == 0); 88 89 if(dir->length == 0) 90 return; 91 92 lblock = ltreewalkblock(&d->blockroot, dir->block); 93 if(*lblock != nil) { 94 if((*lblock)->length == dir->length) 95 return; 96 fprint(2, "block %lud length %lud %s %lud %s\n", dir->block, (*lblock)->length, (*lblock)->name, 97 dir->length, dir->name); 98 assert(0); 99 } 100 101 md5cd(cd, dir->block, dir->length, md5); 102 if(chatty > 1) 103 fprint(2, "note file %.16H %lud (%s)\n", md5, dir->length, dir->name); 104 insertmd5(d, name, md5, dir->block, dir->length); 105 } 106 107 void 108 insertmd5(Dump *d, char *name, uchar *md5, ulong block, ulong length) 109 { 110 Dumpdir **lmd5; 111 Dumpdir **lblock; 112 113 lblock = ltreewalkblock(&d->blockroot, block); 114 if(*lblock != nil) { 115 if((*lblock)->length == length) 116 return; 117 fprint(2, "block %lud length %lud %lud\n", block, (*lblock)->length, length); 118 assert(0); 119 } 120 121 assert(length != 0); 122 *lblock = mkdumpdir(name, md5, block, length); 123 124 lmd5 = ltreewalkmd5(&d->md5root, md5); 125 if(*lmd5 != nil) 126 fprint(2, "warning: data duplicated on CD\n"); 127 else 128 *lmd5 = *lblock; 129 } 130 131 /* 132 * Fill all the children entries for a particular directory; 133 * all we care about is block, length, and whether it is a directory. 134 */ 135 void 136 readkids(Cdimg *cd, Direc *dir, char *(*cvt)(uchar*, int)) 137 { 138 char *dot, *dotdot; 139 int m, n; 140 uchar buf[Blocksize], *ebuf, *p; 141 ulong b, nb; 142 Cdir *c; 143 Direc dx; 144 145 assert(dir->mode & DMDIR); 146 147 dot = atom("."); 148 dotdot = atom(".."); 149 ebuf = buf+Blocksize; 150 nb = (dir->length+Blocksize-1) / Blocksize; 151 152 n = 0; 153 for(b=0; b<nb; b++) { 154 Creadblock(cd, buf, dir->block + b, Blocksize); 155 p = buf; 156 while(p < ebuf) { 157 c = (Cdir*)p; 158 if(c->len == 0) 159 break; 160 if(p+c->len > ebuf) 161 break; 162 if(parsedir(cd, &dx, p, ebuf-p, cvt) == 0 && dx.name != dot && dx.name != dotdot) 163 n++; 164 p += c->len; 165 } 166 } 167 168 m = (n+Ndirblock-1)/Ndirblock * Ndirblock; 169 dir->child = emalloc(m*sizeof dir->child[0]); 170 dir->nchild = n; 171 172 n = 0; 173 for(b=0; b<nb; b++) { 174 assert(n <= dir->nchild); 175 Creadblock(cd, buf, dir->block + b, Blocksize); 176 p = buf; 177 while(p < ebuf) { 178 c = (Cdir*)p; 179 if(c->len == 0) 180 break; 181 if(p+c->len > ebuf) 182 break; 183 if(parsedir(cd, &dx, p, ebuf-p, cvt) == 0 && dx.name != dot && dx.name != dotdot) { 184 assert(n < dir->nchild); 185 dir->child[n++] = dx; 186 } 187 p += c->len; 188 } 189 } 190 } 191 192 /* 193 * Free the children. Make sure their children are free too. 194 */ 195 void 196 freekids(Direc *dir) 197 { 198 int i; 199 200 for(i=0; i<dir->nchild; i++) 201 assert(dir->child[i].nchild == 0); 202 203 free(dir->child); 204 dir->child = nil; 205 dir->nchild = 0; 206 } 207 208 /* 209 * Add a whole directory and all its children to our binary tree. 210 */ 211 static void 212 adddir(Cdimg *cd, Dump *d, Direc *dir) 213 { 214 int i; 215 216 readkids(cd, dir, isostring); 217 for(i=0; i<dir->nchild; i++) { 218 if(dir->child[i].mode & DMDIR) 219 adddir(cd, d, &dir->child[i]); 220 else 221 addfile(cd, d, atom(dir->name), &dir->child[i]); 222 } 223 freekids(dir); 224 } 225 226 Dumpdir* 227 lookupmd5(Dump *d, uchar *md5) 228 { 229 return *ltreewalkmd5(&d->md5root, md5); 230 } 231 232 void 233 adddirx(Cdimg *cd, Dump *d, Direc *dir, int lev) 234 { 235 int i; 236 Direc dd; 237 238 if(lev == 2){ 239 dd = *dir; 240 adddir(cd, d, &dd); 241 return; 242 } 243 for(i=0; i<dir->nchild; i++) 244 adddirx(cd, d, &dir->child[i], lev+1); 245 } 246 247 Dump* 248 dumpcd(Cdimg *cd, Direc *dir) 249 { 250 Dump *d; 251 252 d = emalloc(sizeof *d); 253 d->cd = cd; 254 adddirx(cd, d, dir, 0); 255 return d; 256 } 257 258 /* 259 static ulong 260 minblock(Direc *root, int lev) 261 { 262 int i; 263 ulong m, n; 264 265 m = root->block; 266 for(i=0; i<root->nchild; i++) { 267 n = minblock(&root->child[i], lev-1); 268 if(m > n) 269 m = n; 270 } 271 return m; 272 } 273 */ 274 275 void 276 copybutname(Direc *d, Direc *s) 277 { 278 Direc x; 279 280 x = *d; 281 *d = *s; 282 d->name = x.name; 283 d->confname = x.confname; 284 } 285 286 Direc* 287 createdumpdir(Direc *root, XDir *dir, char *utfname) 288 { 289 char *p; 290 Direc *d; 291 292 if(utfname[0]=='/') 293 sysfatal("bad dump name '%s'", utfname); 294 p = strchr(utfname, '/'); 295 if(p == nil || strchr(p+1, '/')) 296 sysfatal("bad dump name '%s'", utfname); 297 *p++ = '\0'; 298 if((d = walkdirec(root, utfname)) == nil) 299 d = adddirec(root, utfname, dir); 300 if(walkdirec(d, p)) 301 sysfatal("duplicate dump name '%s/%s'", utfname, p); 302 d = adddirec(d, p, dir); 303 return d; 304 } 305 306 static void 307 rmdirec(Direc *d, Direc *kid) 308 { 309 Direc *ekid; 310 311 ekid = d->child+d->nchild; 312 assert(d->child <= kid && kid < ekid); 313 if(ekid != kid+1) 314 memmove(kid, kid+1, (ekid-(kid+1))*sizeof(*kid)); 315 d->nchild--; 316 } 317 318 void 319 rmdumpdir(Direc *root, char *utfname) 320 { 321 char *p; 322 Direc *d, *dd; 323 324 if(utfname[0]=='/') 325 sysfatal("bad dump name '%s'", utfname); 326 p = strchr(utfname, '/'); 327 if(p == nil || strchr(p+1, '/')) 328 sysfatal("bad dump name '%s'", utfname); 329 *p++ = '\0'; 330 if((d = walkdirec(root, utfname)) == nil) 331 sysfatal("cannot remove %s/%s: %s does not exist", utfname, p, utfname); 332 p[-1] = '/'; 333 334 if((dd = walkdirec(d, p)) == nil) 335 sysfatal("cannot remove %s: does not exist", utfname); 336 337 rmdirec(d, dd); 338 if(d->nchild == 0) 339 rmdirec(root, d); 340 } 341 342 char* 343 adddumpdir(Direc *root, ulong now, XDir *dir) 344 { 345 char buf[40], *p; 346 int n; 347 Direc *dday, *dyear; 348 Tm tm; 349 350 tm = *localtime(now); 351 352 sprint(buf, "%d", tm.year+1900); 353 if((dyear = walkdirec(root, buf)) == nil) { 354 dyear = adddirec(root, buf, dir); 355 assert(dyear != nil); 356 } 357 358 n = 0; 359 sprint(buf, "%.2d%.2d", tm.mon+1, tm.mday); 360 p = buf+strlen(buf); 361 while(walkdirec(dyear, buf)) 362 sprint(p, "%d", ++n); 363 364 dday = adddirec(dyear, buf, dir); 365 assert(dday != nil); 366 367 sprint(buf, "%s/%s", dyear->name, dday->name); 368 assert(walkdirec(root, buf)==dday); 369 return atom(buf); 370 } 371 372 /* 373 * The dump directory tree is inferred from a linked list of special blocks. 374 * One block is written at the end of each dump. 375 * The blocks have the form 376 * 377 * plan 9 dump cd 378 * <dump-name> <dump-time> <next-block> <conform-block> <conform-length> \ 379 * <iroot-block> <iroot-length> <jroot-block> <jroot-length> 380 * 381 * If only the first line is present, this is the end of the chain. 382 */ 383 static char magic[] = "plan 9 dump cd\n"; 384 ulong 385 Cputdumpblock(Cdimg *cd) 386 { 387 ulong x; 388 389 Cwseek(cd, cd->nextblock*Blocksize); 390 x = Cwoffset(cd); 391 Cwrite(cd, magic, sizeof(magic)-1); 392 Cpadblock(cd); 393 return x/Blocksize; 394 } 395 396 int 397 hasdump(Cdimg *cd) 398 { 399 int i; 400 char buf[128]; 401 402 for(i=16; i<24; i++) { 403 Creadblock(cd, buf, i, sizeof buf); 404 if(memcmp(buf, magic, sizeof(magic)-1) == 0) 405 return i; 406 } 407 return 0; 408 } 409 410 Direc 411 readdumpdirs(Cdimg *cd, XDir *dir, char *(*cvt)(uchar*, int)) 412 { 413 char buf[Blocksize]; 414 char *p, *q, *f[16]; 415 int i, nf; 416 ulong db, t; 417 Direc *nr, root; 418 XDir xd; 419 420 mkdirec(&root, dir); 421 db = hasdump(cd); 422 xd = *dir; 423 for(;;){ 424 if(db == 0) 425 sysfatal("error in dump blocks"); 426 427 Creadblock(cd, buf, db, sizeof buf); 428 if(memcmp(buf, magic, sizeof(magic)-1) != 0) 429 break; 430 p = buf+sizeof(magic)-1; 431 if(p[0] == '\0') 432 break; 433 if((q = strchr(p, '\n')) != nil) 434 *q = '\0'; 435 436 nf = tokenize(p, f, nelem(f)); 437 i = 5; 438 if(nf < i || (cvt==jolietstring && nf < i+2)) 439 sysfatal("error in dump block %lud: nf=%d; p='%s'", db, nf, p); 440 nr = createdumpdir(&root, &xd, f[0]); 441 t = strtoul(f[1], 0, 0); 442 xd.mtime = xd.ctime = xd.atime = t; 443 db = strtoul(f[2], 0, 0); 444 if(cvt == jolietstring) 445 i += 2; 446 nr->block = strtoul(f[i], 0, 0); 447 nr->length = strtoul(f[i+1], 0, 0); 448 } 449 cd->nulldump = db; 450 return root; 451 } 452 453 extern void addtx(char*, char*); 454 455 static int 456 isalldigit(char *s) 457 { 458 while(*s) 459 if(!isdigit((uchar)*s++)) 460 return 0; 461 return 1; 462 } 463 464 void 465 readdumpconform(Cdimg *cd) 466 { 467 char buf[Blocksize]; 468 char *p, *q, *f[10]; 469 ulong cb, nc, m, db; 470 int nf; 471 472 db = hasdump(cd); 473 assert(map==nil || map->nt == 0); 474 475 for(;;){ 476 if(db == 0) 477 sysfatal("error0 in dump blocks"); 478 479 Creadblock(cd, buf, db, sizeof buf); 480 if(memcmp(buf, magic, sizeof(magic)-1) != 0) 481 break; 482 p = buf+sizeof(magic)-1; 483 if(p[0] == '\0') 484 break; 485 if((q = strchr(p, '\n')) != nil) 486 *q = '\0'; 487 488 nf = tokenize(p, f, nelem(f)); 489 if(nf < 5) 490 sysfatal("error0 in dump block %lud", db); 491 492 db = strtoul(f[2], 0, 0); 493 cb = strtoul(f[3], 0, 0); 494 nc = strtoul(f[4], 0, 0); 495 496 Crseek(cd, cb*Blocksize); 497 m = cb*Blocksize+nc; 498 while(Croffset(cd) < m && (p = Crdline(cd, '\n')) != nil){ 499 p[Clinelen(cd)-1] = '\0'; 500 if(tokenize(p, f, 2) != 2 || (f[0][0] != 'D' && f[0][0] != 'F') 501 || strlen(f[0]) != 7 || !isalldigit(f[0]+1)) 502 break; 503 504 addtx(atom(f[1]), atom(f[0])); 505 } 506 } 507 if(map) 508 cd->nconform = map->nt; 509 else 510 cd->nconform = 0; 511 }