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
md5cd(Cdimg * cd,ulong block,ulong length,uchar * digest)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*
mkdumpdir(char * name,uchar * md5,ulong block,ulong length)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**
ltreewalkmd5(Dumpdir ** l,uchar * md5)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**
ltreewalkblock(Dumpdir ** l,ulong block)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
addfile(Cdimg * cd,Dump * d,char * name,Direc * dir)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
insertmd5(Dump * d,char * name,uchar * md5,ulong block,ulong length)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
readkids(Cdimg * cd,Direc * dir,char * (* cvt)(uchar *,int))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
freekids(Direc * dir)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
adddir(Cdimg * cd,Dump * d,Direc * dir)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*
lookupmd5(Dump * d,uchar * md5)227 lookupmd5(Dump *d, uchar *md5)
228 {
229 return *ltreewalkmd5(&d->md5root, md5);
230 }
231
232 void
adddirx(Cdimg * cd,Dump * d,Direc * dir,int lev)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*
dumpcd(Cdimg * cd,Direc * dir)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
copybutname(Direc * d,Direc * s)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*
createdumpdir(Direc * root,XDir * dir,char * utfname)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
rmdirec(Direc * d,Direc * kid)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
rmdumpdir(Direc * root,char * utfname)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*
adddumpdir(Direc * root,ulong now,XDir * dir)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
Cputdumpblock(Cdimg * cd)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
hasdump(Cdimg * cd)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
readdumpdirs(Cdimg * cd,XDir * dir,char * (* cvt)(uchar *,int))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
isalldigit(char * s)456 isalldigit(char *s)
457 {
458 while(*s)
459 if(!isdigit((uchar)*s++))
460 return 0;
461 return 1;
462 }
463
464 void
readdumpconform(Cdimg * cd)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 }
512