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 }