imagezip.c 52 KB
Newer Older
Leigh B. Stoller's avatar
Leigh B. Stoller committed
1
2
/*
 * EMULAB-COPYRIGHT
3
 * Copyright (c) 2000-2011 University of Utah and the Flux Group.
Leigh B. Stoller's avatar
Leigh B. Stoller committed
4
5
6
 * All rights reserved.
 */

7
8
/*
 * An image zipper.
Mike Hibler's avatar
all:    
Mike Hibler committed
9
10
11
12
13
 *
 * TODO:
 *	Multithread so that we can be reading ahead on the input device
 *	and overlapping IO with compression.  Maybe a third thread for
 *	doing output.
14
 */
15
#include <ctype.h>
16
#include <err.h>
Mac Newbold's avatar
Mac Newbold committed
17
#include <fcntl.h>
18
#if !defined(__UCLIBC__)
19
#include <fstab.h>
20
#endif
21
22
#include <stdio.h>
#include <stdlib.h>
Mac Newbold's avatar
Mac Newbold committed
23
#include <unistd.h>
Mike Hibler's avatar
all:    
Mike Hibler committed
24
#include <string.h>
25
#include <assert.h>
Mike Hibler's avatar
all:    
Mike Hibler committed
26
#include <errno.h>
27
28
29
#include <sys/param.h>
#include <sys/time.h>
#include <sys/stat.h>
Mac Newbold's avatar
Mac Newbold committed
30
#include <zlib.h>
Mike Hibler's avatar
Mike Hibler committed
31

32
#include "imagehdr.h"
Mike Hibler's avatar
Mike Hibler committed
33
34
#include "sliceinfo.h"
#include "global.h"
35

Mike Hibler's avatar
Mike Hibler committed
36
37
38
/* XXX this is a hack right now */
#define USE_HACKSORT 0

39
#define min(a,b) ((a) <= (b) ? (a) : (b))
Mac Newbold's avatar
Mac Newbold committed
40

41
char	*infilename;
42
int	infd, outfd, outcanseek;
43
int	secsize	  = 512;	/* XXX bytes. */
44
int	debug	  = 0;
Mike Hibler's avatar
all:    
Mike Hibler committed
45
int	dots	  = 0;
46
int     info      = 0;
47
int     version   = 0;
48
int     slicemode = 0;
49
int     maxmode   = 0;
50
int     slice     = 0;
51
int	level	  = 4;
52
long	dev_bsize = 1;
53
int	oldstyle  = 0;
54
int	frangesize= 64;	/* 32k */
55
int	forcereads= 0;
56
int	badsectors= 0;
57
int	retrywrites= 1;
Mike Hibler's avatar
Mike Hibler committed
58
int	dorelocs  = 1;
59
int	metaoptimize = 0;
60
int	filemode  = 0;
Mike Hibler's avatar
Mike Hibler committed
61
off_t	datawritten;
62
partmap_t ignore, forceraw;
63
64
65
66

#ifdef WITH_HASH
char	*hashfile;
#endif
Mike Hibler's avatar
all:    
Mike Hibler committed
67

68
69
70
71
#define HDRUSED(reg, rel) \
    (sizeof(blockhdr_t) + \
    (reg) * sizeof(struct region) + (rel) * sizeof(struct blockreloc))

72
73
74
75
76
77
78
/*
 * We want to be able to compress slices by themselves, so we need
 * to know where the slice starts when reading the input file for
 * compression. 
 *
 * These numbers are in sectors.
 */
79
extern unsigned long getdisksize(int fd);
80
81
unsigned long inputminsec	= 0;
unsigned long inputmaxsec	= 0;	/* 0 means the entire input image */
82
83

/*
84
 * A list of data ranges. 
85
 */
86
struct range {
Mike Hibler's avatar
all:    
Mike Hibler committed
87
88
89
	uint32_t	start;		/* In sectors */
	uint32_t	size;		/* In sectors */
	void		*data;
90
	struct range	*next;
91
};
Mike Hibler's avatar
all:    
Mike Hibler committed
92
struct range	*ranges, *skips, *fixups;
93
int		numranges, numskips;
Mike Hibler's avatar
all:    
Mike Hibler committed
94
struct blockreloc	*relocs;
95
int			numregions, numrelocs;
Mike Hibler's avatar
all:    
Mike Hibler committed
96

97
void	dumpskips(int verbose);
Mike Hibler's avatar
Mike Hibler committed
98
static void	sortrange(struct range **head, int domerge,
Mike Hibler's avatar
Mike Hibler committed
99
		  int (*rangecmp)(struct range *, struct range *));
100
101
int	mergeskips(int verbose);
int	mergeranges(struct range *head);
102
void    makeranges(void);
103
void	freeranges(struct range *);
104
void	dumpranges(int verbose);
105
void	dumpfixups(int verbose);
106
void	addvalid(uint32_t start, uint32_t size);
Mike Hibler's avatar
all:    
Mike Hibler committed
107
void	addreloc(off_t offset, off_t size, int reloctype);
Mike Hibler's avatar
Mike Hibler committed
108
static int cmpfixups(struct range *r1, struct range *r2);
109
110
static int read_doslabel(int infd, int lsect, int pstart,
			 struct doslabel *label);
111
112

/* Forward decls */
113
int	read_image(u_int32_t start, int pstart, u_int32_t extstart);
Mike Hibler's avatar
all:    
Mike Hibler committed
114
int	read_raw(void);
115
116
117
int	compress_image(void);
void	usage(void);

118
119
#ifdef WITH_HASH
struct range *hashmap_compute_delta(struct range *, char *, int, u_int32_t);
120
void	report_hash_stats(int pnum);
121
122
#endif

Mike Hibler's avatar
Mike Hibler committed
123
124
125
126
127
static SLICEMAP_PROCESS_PROTO(read_slice);

struct slicemap fsmap[] = {
	{ DOSPTYP_UNUSED,	"UNUSED",	0 },
#ifdef WITH_FFS
Mike Hibler's avatar
Mike Hibler committed
128
129
	{ DOSPTYP_386BSD,	"FreeBSD FFS",	read_bsdslice },
	{ DOSPTYP_OPENBSD,	"OpenBSD FFS",	read_bsdslice },
Mike Hibler's avatar
Mike Hibler committed
130
131
132
#endif
#ifdef WITH_EXTFS
	{ DOSPTYP_LINUX,	"Linux EXT",	read_linuxslice },
133
//	{ DOSPTYP_EXT4,		"Linux EXT4",	read_ext4slice },
Mike Hibler's avatar
Mike Hibler committed
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
	{ DOSPTYP_LINSWP,	"Linux SWP",	read_linuxswap },
#endif
#ifdef WITH_NTFS
	{ DOSPTYP_NTFS,		"NTFS",		read_ntfsslice },
#endif
#ifdef WITH_FAT
	{ DOSPTYP_FAT12,	"FAT12",	read_fatslice },
	{ DOSPTYP_FAT16,	"FAT16",	read_fatslice },
	{ DOSPTYP_FAT16L,	"FAT16L",	read_fatslice },
	{ DOSPTYP_FAT16L_LBA,	"FAT16 LBA",	read_fatslice },
	{ DOSPTYP_FAT32,	"FAT32",	read_fatslice },
	{ DOSPTYP_FAT32_LBA,	"FAT32 LBA",	read_fatslice },
#endif
	{ DOSPTYP_EXT,		"DOSEXT",	0 },
	{ DOSPTYP_EXT_LBA,	"DOSEXT LBA",	0 },
	{ -1,			"",		0 },
};

152
static __inline struct slicemap *
Mike Hibler's avatar
Mike Hibler committed
153
154
155
156
157
158
159
160
161
getslicemap(int stype)
{
	struct slicemap *smap;

	for (smap = fsmap; smap->type != -1; smap++)
		if (smap->type == stype)
			return smap;
	return 0;
}
162

163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#define READ_RETRIES	1
#define WRITE_RETRIES	10

ssize_t
slowread(int fd, void *buf, size_t nbytes, off_t startoffset)
{
	int cc, i, count;

	fprintf(stderr, "read failed: will retry by sector %d more times\n",
		READ_RETRIES);
	
	count = 0;
	for (i = 0; i < READ_RETRIES; i++) {
		if (lseek(fd, startoffset, SEEK_SET) < 0) {
			perror("devread: seeking to set file ptr");
			exit(1);
		}
		while (nbytes > 0) {
			cc = read(fd, buf, nbytes);
			if (cc == 0) {
				nbytes = 0;
				continue;
			}
			if (cc > 0) {
				nbytes -= cc;
				buf     = (void *)((char *)buf + cc);
				count  += cc;
				continue;
			}

			nbytes += count;
			buf     = (void *)((char *)buf - count);
			count   = 0;
			break;
		}
		if (nbytes == 0)
			break;
	}
	return count;
}
203

Mike Hibler's avatar
Mike Hibler committed
204
205
206
207
208
/*
 * Assert the hell out of it...
 */
off_t
devlseek(int fd, off_t off, int whence)
209
210
211
212
{
	off_t noff;
	assert((off & (DEV_BSIZE-1)) == 0);
	noff = lseek(fd, off, whence);
213
214
215
	if (!filemode) {
		assert(noff == (off_t)-1 || (noff & (DEV_BSIZE-1)) == 0);
	}
216
217
218
	return noff;
}

219
220
221
222
223
224
/*
 * Wrap up read in a retry mechanism to persist in the face of IO errors,
 * even faking data if requested.
 */
ssize_t
devread(int fd, void *buf, size_t nbytes)
225
{
226
	int		cc, count;
227
	off_t		startoffset;
228
	size_t		onbytes;
229
230
231

#ifndef linux
	assert((nbytes & (DEV_BSIZE-1)) == 0);
232
#endif
233
234
235
	cc = read(fd, buf, nbytes);
	if (!forcereads || cc >= 0)
		return cc;
236

237
238
239
240
241
	/*
	 * Got an error reading the range.
	 * Retry one sector at a time, replacing any bad sectors with
	 * zeroed data.
	 */
242
243
244
245
	if ((startoffset = lseek(fd, (off_t) 0, SEEK_CUR)) < 0) {
		perror("devread: seeking to get input file ptr");
		exit(1);
	}
246
	assert((startoffset & (DEV_BSIZE-1)) == 0);
247

248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
	onbytes = nbytes;
	while (nbytes > 0) {
		if (nbytes > DEV_BSIZE)
			count = DEV_BSIZE;
		else
			count = nbytes;
		cc = slowread(fd, buf, count, startoffset);
		if (cc != count) {
			fprintf(stderr, "devread: read failed on sector %u, "
				"returning zeros\n",
				bytestosec(startoffset));
			if (cc < 0)
				cc = 0;
			memset(buf, 0, count-cc);
			badsectors++;
			cc = count;
264
		}
265
266
267
		nbytes -= cc;
		buf = (void *)((char *)buf + cc);
		startoffset += cc;
268
	}
269
	return onbytes;
270
}
271

272
273
274
275
276
/*
 * Wrap up write in a retry mechanism to protect against transient NFS
 * errors causing a fatal error. 
 */
ssize_t
277
devwrite(int fd, const void *buf, size_t nbytes)
278
279
{
	int		cc, i, count = 0;
Mike Hibler's avatar
all:    
Mike Hibler committed
280
	off_t		startoffset = 0;
281

282
	if (retrywrites && outcanseek &&
283
	    ((startoffset = lseek(fd, (off_t) 0, SEEK_CUR)) < 0)) {
284
		perror("devwrite: seeking to get output file ptr");
285
286
		exit(1);
	}
287

288
	for (i = 0; i < WRITE_RETRIES; i++) {
289
		while (nbytes) {
290
291
292
293
			cc = write(fd, buf, nbytes);

			if (cc > 0) {
				nbytes -= cc;
294
				buf     = (void *)((char *)buf + cc);
295
				count  += cc;
296
				continue;
297
			}
298
299
300

			if (!retrywrites)
				return cc;
301

302
			if (i == 0) 
303
				perror("write error: will retry");
304
	
305
			sleep(1);
306
			nbytes += count;
307
			buf     = (void *)((char *)buf - count);
308
309
			count   = 0;
			goto again;
310
		}
311
		if (retrywrites && fsync(fd) < 0) {
312
313
314
			perror("fsync error: will retry");
			sleep(1);
			nbytes += count;
315
			buf     = (void *)((char *)buf - count);
316
317
318
			count   = 0;
			goto again;
		}
Mike Hibler's avatar
Mike Hibler committed
319
		datawritten += count;
320
		return count;
321
	again:
322
		if (lseek(fd, startoffset, SEEK_SET) < 0) {
323
			perror("devwrite: seeking to set file ptr");
324
325
			exit(1);
		}
326
	}
327
328
329
	perror("write error: busted for too long");
	fflush(stderr);
	exit(1);
330
331
}

332
333
334
335
336
337
static int
setpartition(partmap_t map, char *str)
{
	int dospart;
	char bsdpart;

338
339
340
341
342
343
344
345
346
	if (isdigit(str[1])) {
		bsdpart = str[2];
		str[2] = '\0';
	} else {
		bsdpart = str[1];
		str[1] = '\0';
	}
	dospart = atoi(str);
	if (dospart < 1 || dospart > MAXSLICES)
347
348
349
350
351
352
353
354
355
356
357
358
359
360
		return EINVAL;

	/* common case: apply to complete DOS partition */
	if (bsdpart == '\0') {
		map[dospart-1] = ~0;
		return 0;
	}

	if (bsdpart < 'a' || bsdpart > 'p')
		return EINVAL;

	map[dospart-1] |= (1 << (bsdpart - 'a'));
	return 0;
}
Mac Newbold's avatar
Mac Newbold committed
361
362

int
363
main(int argc, char *argv[])
Mac Newbold's avatar
Mac Newbold committed
364
{
365
366
367
	int	ch, rval;
	char	*outfilename = 0;
	int	rawmode	  = 0;
Mike Hibler's avatar
Mike Hibler committed
368
	int	slicetype = 0;
369
	struct timeval sstamp;
370
	extern char build_info[];
Mac Newbold's avatar
Mac Newbold committed
371

372
	gettimeofday(&sstamp, 0);
373
	while ((ch = getopt(argc, argv, "vlbnNdihrs:c:z:ofI:1F:DR:S:XH:M")) != -1)
374
		switch(ch) {
375
376
377
		case 'v':
			version++;
			break;
378
379
		case 'i':
			info++;
380
			debug++;
381
			break;
Mike Hibler's avatar
Mike Hibler committed
382
		case 'D':
383
			retrywrites = 0;
Mike Hibler's avatar
Mike Hibler committed
384
			break;
385
386
387
388
		case 'd':
			debug++;
			break;
		case 'l':
Mike Hibler's avatar
Mike Hibler committed
389
			slicetype = DOSPTYP_LINUX;
390
391
			break;
		case 'b':
Mike Hibler's avatar
Mike Hibler committed
392
			slicetype = DOSPTYP_386BSD;
393
			break;
Mike Hibler's avatar
Mike Hibler committed
394
395
396
		case 'N':
			dorelocs = 0;
			break;
397
		case 'n':
Mike Hibler's avatar
Mike Hibler committed
398
			slicetype = DOSPTYP_NTFS;
399
			break;
Mike Hibler's avatar
all:    
Mike Hibler committed
400
401
402
		case 'o':
			dots++;
			break;
403
404
405
		case 'r':
			rawmode++;
			break;
Mike Hibler's avatar
Mike Hibler committed
406
407
408
		case 'S':
			slicetype = atoi(optarg);
			break;
409
410
411
412
		case 's':
			slicemode = 1;
			slice = atoi(optarg);
			break;
413
414
		case 'z':
			level = atoi(optarg);
Mike Hibler's avatar
all:    
Mike Hibler committed
415
			if (level < 0 || level > 9)
416
417
				usage();
			break;
418
		case 'c':
419
			maxmode     = 1;
420
421
			inputmaxsec = atoi(optarg);
			break;
Mike Hibler's avatar
all:    
Mike Hibler committed
422
		case 'I':
423
			if (setpartition(ignore, optarg))
Mike Hibler's avatar
all:    
Mike Hibler committed
424
425
				usage();
			break;
Mike Hibler's avatar
Mike Hibler committed
426
		case 'R':
427
			if (setpartition(forceraw, optarg))
Mike Hibler's avatar
Mike Hibler committed
428
429
				usage();
			break;
430
431
432
		case '1':
			oldstyle = 1;
			break;
433
434
435
436
437
		case 'F':
			frangesize = atoi(optarg);
			if (frangesize < 0)
				usage();
			break;
438
439
440
		case 'X':
			forcereads++;
			break;
441
442
443
444
445
446
447
		case 'H':
#ifdef WITH_HASH
			hashfile = optarg;
#else
			fprintf(stderr, "'H' option not supported\n");
			usage();
#endif
448
			break;
449
450
451
		case 'M':
			metaoptimize++;
			break;
452
453
454
455
		case 'f':
			filemode++;
			rawmode++;
			break;
456
457
458
459
460
461
462
		case 'h':
		case '?':
		default:
			usage();
		}
	argc -= optind;
	argv += optind;
Mac Newbold's avatar
Mac Newbold committed
463

464
	if (version || debug) {
465
		fprintf(stderr, "%s\n", build_info);
Mike Hibler's avatar
Mike Hibler committed
466
467
468
469
470
471
472
		if (version) {
			fprintf(stderr, "Supports");
			for (ch = 1; fsmap[ch].type != -1; ch++)
				if (fsmap[ch].process != 0)
					fprintf(stderr, "%c %s",
						ch > 1 ? ',' : ':',
						fsmap[ch].desc);
473
474
#ifdef WITH_HASH
			fprintf(stderr, ", hash-signature comparison");
475
#endif
Mike Hibler's avatar
Mike Hibler committed
476
			fprintf(stderr, "\n");
477
			exit(0);
Mike Hibler's avatar
Mike Hibler committed
478
		}
479
480
	}

481
482
	if (argc < 1 || argc > 2)
		usage();
Mac Newbold's avatar
Mac Newbold committed
483

484
485
486
	if (slicemode && (slice < 1 || slice > MAXSLICES)) {
		fprintf(stderr, "Slice must be a DOS partition (1-4) "
			"or extended DOS partition (5-%d)\n\n", MAXSLICES);
487
488
		usage();
	}
489
490
491
	if (maxmode && slicemode) {
		fprintf(stderr, "Count option (-c) cannot be used with "
			"the slice (-s) option\n\n");
492
493
494
495
496
		usage();
	}
	if (!info && argc != 2) {
		fprintf(stderr, "Must specify an output filename!\n\n");
		usage();
Mac Newbold's avatar
Mac Newbold committed
497
	}
498
499
	else
		outfilename = argv[1];
Mac Newbold's avatar
Mac Newbold committed
500

501
	if (!slicemode && !filemode && dorelocs)
Mike Hibler's avatar
Mike Hibler committed
502
503
		dorelocs = 0;

504
505
506
	infilename = argv[0];
	if ((infd = open(infilename, O_RDONLY, 0)) < 0) {
		perror(infilename);
Mac Newbold's avatar
Mac Newbold committed
507
508
		exit(1);
	}
509

510
511
512
513
514
515
516
517
518
519
520
#if 0
	/*
	 * Use OS-specific techniques to discover the size of the disk.
	 * Note that this could produce an image that will not fit on a
	 * smaller disk, as imagezip will consider any space beyond the
	 * final partition as allocated and will record the ranges.
	 */
	if (!slicemode && !maxmode)
		inputmaxsec = getdisksize(infd);
#endif

521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
	/*
	 * Create the skip list by scanning the filesystems on
	 * the disk or indicated partition.
	 */
	if (slicetype != 0) {
		rval = read_slice(-1, slicetype, 0, 0,
				  infilename, infd);
		if (rval == -1)
			fprintf(stderr, ", cannot process\n");
	} else if (rawmode)
		rval = read_raw();
	else
		rval = read_image(DOSBBSECTOR, 0, 0);
	if (rval) {
		fprintf(stderr, "* * * Aborting * * *\n");
		exit(1);
537
	}
538
539
540
541
542
543
544
545

	/*
	 * Create a valid range list from the skip list
	 */
	(void) mergeskips(debug > 1);
	if (debug)
		dumpskips(debug > 1);
	makeranges();
546
	if (debug)
547
		dumpranges(debug > 1);
Mike Hibler's avatar
Mike Hibler committed
548
	sortrange(&fixups, 0, cmpfixups);
549
550
	if (debug > 1)
		dumpfixups(debug > 2);
551
	fflush(stderr);
552

553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
#ifdef WITH_HASH
	/*
	 * If we are creating a "delta" image from a hash signature,
	 * we read in the signature info and reconcile that with the
	 * known allocated range that we have just computed.  The result
	 * is a new list of ranges that are currently allocated and that
	 * have changed from the signature version.
	 */
	if (hashfile != NULL) {
		struct range *nranges;

		/*
		 * next compare allocated 'ranges' and 'hinfo' to find out the
		 * changed blocks -- computing the hashes for some 'ranges'
		 * in the process
		 */
		nranges = hashmap_compute_delta(ranges, hashfile, infd,
						inputminsec);
		if (nranges == NULL)
			fprintf(stderr, "NO differences !!!!\n");

		freeranges(ranges);
		ranges = nranges;

		if (debug) {
			fprintf(stderr, "\nAfter delta computation: ");
			dumpranges(debug > 1);
		}
581
		report_hash_stats(slice);
582
	}
583
#endif
584

585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
	/*
	 * Now we have all the allocated information, create the image
	 * (unless we just want an info report).
	 */
	if (!info) {
		if (strcmp(outfilename, "-")) {
			if ((outfd = open(outfilename, O_RDWR|O_CREAT|O_TRUNC,
					  0666)) < 0) {
				perror("opening output file");
				exit(1);
			}
			outcanseek = 1;
		}
		else {
			outfd = fileno(stdout);
			outcanseek = 0;
			retrywrites = 0;
602
		}
603
		compress_image();
604
		assert(fixups == NULL);
605
606
607
	
		if (outcanseek)
			close(outfd);
608
	}
609
610
611
612
613
614
615
616
617
618
619
620
621
622
	close(infd);

	{
		struct timeval stamp;
		unsigned int ms;

		gettimeofday(&stamp, 0);
		if (stamp.tv_usec < sstamp.tv_usec) {
			stamp.tv_usec += 1000000;
			stamp.tv_sec--;
		}
		ms = (stamp.tv_sec - sstamp.tv_sec) * 1000 +
			(stamp.tv_usec - sstamp.tv_usec) / 1000;
		fprintf(stderr,
623
			"Finished in %u.%03u seconds\n",
624
			ms / 1000, ms % 1000);
Mac Newbold's avatar
Mac Newbold committed
625
	}
626
	fflush(stderr);
627

628
	exit(0);
629
630
}

Mike Hibler's avatar
Mike Hibler committed
631
632
633
634
635
636
637
638
639
640
641
642
643
644
static int
read_slice(int snum, int stype, u_int32_t start, u_int32_t size,
	   char *sname, int sfd)
{
	struct slicemap *smap = getslicemap(stype);

	if (smap && smap->process)
		return (*smap->process)(snum, stype, start, size, sname, sfd);
	
	fprintf(stderr, "Slice %d is an unknown type %#x (%s)",
		snum+1, stype, smap ? smap->desc : "??");
	return -1;
}

645
/*
646
647
 * Read a DOS partition table at the indicated offset.
 * If successful return 0 with *label filled in.  Otherwise return an error.
648
 */
649
650
static int
read_doslabel(int infd, int lsect, int pstart, struct doslabel *label)
651
{
652
	int cc;
653

654
655
	if (devlseek(infd, sectobytes(lsect), SEEK_SET) < 0) {
		warn("Could not seek to DOS label at sector %u", lsect);
656
657
		return 1;
	}
658
659
	if ((cc = devread(infd, label->pad2, DOSPARTSIZE)) < 0) {
		warn("Could not read DOS label at sector %u", lsect);
660
661
662
		return 1;
	}
	if (cc != DOSPARTSIZE) {
663
		warnx("Incomplete read of DOS label at sector %u", lsect);
664
665
 		return 1;
	}
666
	if (label->magic != BOOT_MAGIC) {
667
		warnx("Wrong magic number in DOS partition table at sector %u",
668
		      lsect);
669
670
671
672
 		return 1;
	}

	if (debug) {
673
674
675
		int i;

		if (lsect == DOSBBSECTOR)
676
677
678
679
			fprintf(stderr, "DOS Partitions:\n");
		else
			fprintf(stderr,
				"DOS Partitions in Extended table at %u\n",
680
				lsect);
681
		for (i = 0; i < NDOSPART; i++) {
682
			struct slicemap *smap;
683
684
685
686
			u_int32_t start;
			int bsdix = pstart + i;

			fprintf(stderr, "  P%d: ", bsdix + 1);
687
			smap = getslicemap(label->parts[i].dp_typ);
Mike Hibler's avatar
Mike Hibler committed
688
			if (smap == 0)
689
				fprintf(stderr, "%-12s", "UNKNOWN");
Mike Hibler's avatar
Mike Hibler committed
690
			else
691
				fprintf(stderr, "%-12s", smap->desc);
Mike Hibler's avatar
Mike Hibler committed
692

693
			start = label->parts[i].dp_start;
694
#if 0
Mike Hibler's avatar
Mike Hibler committed
695
			/* Make start sector absolute */
696
			if (ISEXT(label->parts[i].dp_typ))
697
698
699
700
				start += extstart;
			else
				start += bbstart;
#endif
701
			fprintf(stderr, "  start %9d, size %9d\n",
702
				start, label->parts[i].dp_size);
703
		}
704
		fprintf(stderr, "\n");
705
706
	}

707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
	return 0;
}

/*
 * Parse the DOS partition table and dispatch to the individual readers.
 */
int
read_image(u_int32_t bbstart, int pstart, u_int32_t extstart)
{
	int		i, rval = 0;
	struct slicemap	*smap;
	struct doslabel doslabel;

	if (read_doslabel(infd, bbstart, pstart, &doslabel) != 0)
		return 1;

723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
	/*
	 * Quick, brute-force check for overlap of partitions.
	 * XXX right now, any overlap is bad and we bail.  In the future,
	 * we could determine all areas of intersection and be conservative
	 * with those areas; i.e., always save unless overlap is strictly
	 * between unused/ignored partitions.
	 */
	for (i = 0; i < NDOSPART-1; i++) {
		u_int32_t start1, size1, start2, size2;
		int i2;

		if ((size1 = doslabel.parts[i].dp_size) == 0)
			continue;

		start1 = bbstart + doslabel.parts[i].dp_start;
		for (i2 = i+1; i2 < NDOSPART; i2++) {
			if ((size2 = doslabel.parts[i2].dp_size) == 0)
				continue;
			start2 = bbstart + doslabel.parts[i2].dp_start;
			if (start2+size2 > start1 &&
			    start1+size1 > start2) {
				warnx("P%d and P%d overlap!", i+1, i2+1);
				rval++;
			}
		}
	}
	if (rval)
		return 1;

752
753
754
755
756
	/*
	 * Now operate on individual slices. 
	 */
	for (i = 0; i < NDOSPART; i++) {
		unsigned char	type  = doslabel.parts[i].dp_typ;
757
		u_int32_t	start = bbstart + doslabel.parts[i].dp_start;
758
		u_int32_t	size  = doslabel.parts[i].dp_size;
759
		int		bsdix = pstart + i;
760

761
		if (slicemode && bsdix + 1 != slice && !ISEXT(type))
762
763
			continue;
		
764
765
		if (ignore[bsdix]) {
			if (!ISBSD(type) || ignore[bsdix] == ~0)
766
				type = DOSPTYP_UNUSED;
767
768
		} else if (forceraw[bsdix]) {
			if (!ISBSD(type) || forceraw[bsdix] == ~0) {
769
770
				fprintf(stderr,
					"  Slice %d, forcing raw compression\n",
771
					bsdix + 1);
772
773
				goto skipcheck;
			}
Mike Hibler's avatar
Mike Hibler committed
774
		}
Mike Hibler's avatar
all:    
Mike Hibler committed
775

Mike Hibler's avatar
Mike Hibler committed
776
		smap = getslicemap(type);
777
		switch (type) {
778
779
780
781
782
783
784
785
		case DOSPTYP_EXT:
		case DOSPTYP_EXT_LBA:
			/*
			 * XXX extended partition start sectors are
			 * relative to the first extended partition found
			 */
			rval = read_image(extstart + doslabel.parts[i].dp_start,
					  pstart + NDOSPART,
786
					  extstart ? extstart : start);
787
788
			/* XXX for inputmaxsec calculation below */
			start = extstart + doslabel.parts[i].dp_start;
789
790
			break;

Mike Hibler's avatar
all:    
Mike Hibler committed
791
		case DOSPTYP_UNUSED:
792
			fprintf(stderr,
793
794
				"  Slice %d %s, NOT SAVING.\n", bsdix + 1,
				ignore[bsdix] ? "ignored" : "is unused");
Mike Hibler's avatar
Mike Hibler committed
795
			if (size > 0)
796
				addskip(start, size);
Mike Hibler's avatar
all:    
Mike Hibler committed
797
			break;
Mike Hibler's avatar
Mike Hibler committed
798

Mike Hibler's avatar
all:    
Mike Hibler committed
799
		default:
Mike Hibler's avatar
Mike Hibler committed
800
801
802
803
804
805
			rval = read_slice(bsdix, type, start, size,
					  infilename, infd);
			if (rval == -1) {
				fprintf(stderr, ", forcing raw compression\n");
				rval = 0;
			}
Mike Hibler's avatar
all:    
Mike Hibler committed
806
			break;
807
		}
808
		if (rval) {
809
810
811
812
813
814
			if (!ISEXT(type))
				fprintf(stderr,
					"  Filesystem specific error "
					"in Slice %d, "
					"use -R%d to force raw compression.\n",
					bsdix + 1, bsdix + 1);
815
			break;
816
		}
817
		
Mike Hibler's avatar
Mike Hibler committed
818
	skipcheck:
819
820
821
822
823
824
825
826
827
828
829
830
831
832
		/*
		 * In slicemode, we need to set the bounds of compression.
		 * Slice is a DOS partition number (1-4). If not in slicemode,
		 * we cannot set the bounds according to the doslabel since its
		 * possible that someone will create a disk with empty space
		 * before the first partition (typical, to start partition 1
		 * at the second cylinder) or after the last partition (Mike!).
		 * However, do not set the inputminsec since we usually want the
		 * stuff before the first partition, which is the boot stuff.
		 */
		if (slicemode && slice == bsdix + 1) {
			inputminsec = start;
			inputmaxsec = start + size;
		} else if (!slicemode && !maxmode) {
833
834
835
			if (start + size > inputmaxsec)
				inputmaxsec = start + size;
		}
836
837
838
839
840
	}

	return rval;
}

841

842
843
/*
 * For a raw image (something we know nothing about), we report the size
844
 * and compress the entire thing (that is, there are no skip ranges).
845
846
847
848
849
850
 */
int
read_raw(void)
{
	off_t	size;

851
	if ((size = devlseek(infd, (off_t) 0, SEEK_END)) < 0) {
852
853
854
855
		warn("lseeking to end of raw image");
		return 1;
	}

856
857
858
859
860
861
	/*
	 * Round up the size to a sector boundary
	 */
	if (filemode)
		size = sectobytes(bytestosec(size + secsize-1));

862
	if (debug) {
863
		fprintf(stderr, "  Raw Image\n");
864
865
		fprintf(stderr, "        start %12d, size %12lld\n",
			0, (long long)size);
866
867
868
869
870
	}
	return 0;
}

char *usagestr = 
871
 "usage: imagezip [-vihor] [-s #] <image | device> [outputfilename]\n"
Mike Hibler's avatar
all:    
Mike Hibler committed
872
 " -v             Print version info and exit\n"
873
 " -i             Info mode only.  Do not write an output file\n"
Mike Hibler's avatar
all:    
Mike Hibler committed
874
 " -h             Print this help message\n"
875
876
 " -o             Print progress indicating dots\n"
 " -r             Generate a `raw' image.  No FS compression is attempted\n"
877
 " -f             Generate an image from a regular file (implies -r)\n"
878
879
880
881
882
883
884
 " -s slice       Compress a particular slice (DOS numbering 1-4)\n"
 " image | device The input image or a device special file (ie: /dev/ad0)\n"
 " outputfilename The output file ('-' for stdout)\n"
 "\n"
 " Advanced options\n"
 " -z level       Set the compression level.  Range 0-9 (0==none, default==4)\n"
 " -I slice       Ignore (skip) the indicated slice (not with slice mode)\n"
Mike Hibler's avatar
Mike Hibler committed
885
 " -R slice       Force raw compression of the indicated slice (not with slice mode)\n"
886
 " -c count       Compress <count> number of sectors (not with slice mode)\n"
Mike Hibler's avatar
Mike Hibler committed
887
 " -D             Do `dangerous' writes (don't check for async errors)\n"
888
 " -1             Output a version one image file\n"
889
 " -H hashfile    Use the specified imagehash-generated signature to produce a delta image\n"
890
891
 "\n"
 " Debugging options (not to be used by mere mortals!)\n"
892
 " -d             Turn on debugging.  Multiple -d options increase output\n"
893
894
 " -b             FreeBSD slice only.  Input must be a FreeBSD FFS slice\n"
 " -l             Linux slice only.  Input must be a Linux EXT2FS slice\n"
Mike Hibler's avatar
Mike Hibler committed
895
896
 " -n             NTFS slice only.  Input must be an NTFS slice\n"
 " -S DOS-ptype   Treat the input device as containing a slice of the given type\n";
897
898
899
900

void
usage()
{
901
	fprintf(stderr, "%s", usagestr);
902
903
904
	exit(1);
}

905
906
907
/*
 * Add a range of free space to skip
 */
908
void
Mike Hibler's avatar
all:    
Mike Hibler committed
909
addskip(uint32_t start, uint32_t size)
910
{
911
	struct range	   *skip;
912

913
	if ((skip = (struct range *) malloc(sizeof(*skip))) == NULL) {
914
915
916
917
		fprintf(stderr, "No memory for skip range, "
			"try again with '-F <numsect>'\n"
			"where <numsect> is greater than the current %d\n",
			frangesize);
918
919
920
		exit(1);
	}
	
921
922
923
924
925
	skip->start = start;
	skip->size  = size;
	skip->next  = skips;
	skips       = skip;
	numskips++;
926
927
}

928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
/*
 * Add an explicit valid block range.
 * We always add entries to the end of the list since we are commonly
 * called with alredy sorted entries.
 */
void
addvalid(uint32_t start, uint32_t size)
{
	static struct range **lastvalid = &ranges;
	struct range *valid;

	if ((valid = (struct range *) malloc(sizeof(*valid))) == NULL) {
		fprintf(stderr, "No memory for valid range\n");
		exit(1);
	}
	
	valid->start = start;
	valid->size  = size;
	valid->next  = 0;
	*lastvalid   = valid;
	lastvalid    = &valid->next;
	numranges++;
}

Mike Hibler's avatar
all:    
Mike Hibler committed
952
void
953
dumpskips(int verbose)
Mike Hibler's avatar
all:    
Mike Hibler committed
954
955
{
	struct range	*pskip;
956
	uint32_t	offset = 0, total = 0;
957
	int		nranges = 0;
Mike Hibler's avatar
all:    
Mike Hibler committed
958
959
960
961

	if (!skips)
		return;

962
963
964
965
966
	if (verbose) {
		fprintf(stderr, "\nMin sector %lu, Max sector %lu\n",
			inputminsec, inputmaxsec);
		fprintf(stderr, "Skip ranges (start/size) in sectors:\n");
	}
Mike Hibler's avatar
Mike Hibler committed
967

Mike Hibler's avatar
all:    
Mike Hibler committed
968
969
	pskip = skips;
	while (pskip) {
970
		if (verbose)
Mike Hibler's avatar
all:    
Mike Hibler committed
971
972
			fprintf(stderr,
				"  %12d    %9d\n", pskip->start, pskip->size);
Mike Hibler's avatar
Mike Hibler committed
973
		assert(pskip->start >= offset);
974
		offset = pskip->start + pskip->size;
Mike Hibler's avatar
all:    
Mike Hibler committed
975
		total += pskip->size;
976
		nranges++;
Mike Hibler's avatar
all:    
Mike Hibler committed
977
978
979
		pskip  = pskip->next;
	}
	
980
981
	fprintf(stderr,
		"Total Number of Free Sectors: %d (bytes %lld) in %d ranges\n",
982
		total, (long long)sectobytes(total), nranges);
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
}

#undef DOHISTO

/*
 * Sort and merge the list of skip blocks.
 * This code also winnows out the free ranges smaller than frangesize.
 * Returns the number of entries freed, useful so that it can be called
 * on-the-fly if we run out of memory to see if we managed to free anything.
 */
int
mergeskips(int verbose)
{
	struct range *prange, **prevp;
	int freed = 0, culled = 0;
	uint32_t total = 0;
#ifdef DOHISTO
	uint32_t histo[64];
	memset(histo, 0, sizeof(histo));
#endif

Mike Hibler's avatar
Mike Hibler committed
1004
	sortrange(&skips, 0, 0);
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
	freed += mergeranges(skips);

	/*
	 * After merging, make another pass to cull out the too-small ranges.
	 */
	if (frangesize) {
		prevp = &skips;
		while (*prevp) {
			prange = *prevp;
			if (prange->size < (uint32_t)frangesize) {
1015
				if (debug > 2)
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
					fprintf(stderr,
						"dropping range [%u-%u]\n",
						prange->start,
						prange->start+prange->size-1);
				total += prange->size;
#ifdef DOHISTO
				if (prange->size < 64)
					histo[prange->size]++;
#endif
				*prevp = prange->next;
				free(prange);
				culled++;
			} else
				prevp = &prange->next;
		}
		if (verbose && culled) {
			fprintf(stderr,
				"\nFree Sectors Ignored: %d (%lld bytes) in %d ranges\n",
1034
				total, (long long)sectobytes(total), culled);
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
#ifdef DOHISTO
			{
				int i;
				double r, s;
				double cumr = 0.0, cums = 0.0;
				for (i = 0; i < 64; i++) {
					if (histo[i] == 0)
						continue;
					r = (double)histo[i]/culled*100.0;
					cumr += r;
					s = (double)(histo[i]*i)/total*100.0;
					cums += s;
					fprintf(stderr,
						"%d: %u, %4.1f%% (%4.1f%%) of ranges "
						"%4.1f%% (%4.1f%%) of sectors)\n",
						i, histo[i], r, cumr, s, cums);
				}
			}
#endif
		}
	}

	return (freed + culled);
Mike Hibler's avatar
all:    
Mike Hibler committed
1058
1059
}

Mike Hibler's avatar
Mike Hibler committed
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
#if USE_HACKSORT > 0
/*
 * A "better" sort.  Put pointers to all the linked list elements in an
 * array so that we can use qsort and then rebuild the linked list afterward.
 * The best sort technology available with less than 5 minutes work!
 */
int
sfunc(void *rfunc, const void *e1, const void *e2)
{
	int ((*rangecmp)(struct range *, struct range *)) = rfunc;
	struct range *r1 = *(struct range **)e1;
	struct range *r2 = *(struct range **)e2;

	if (r1->start > r2->start ||
	    (rfunc && (*rangecmp)(r1, r2)))
		return 1;
	return -1;
}

struct range *
bettersort(struct range *head, int count,
	       int (*rangecmp)(struct range *, struct range *))
{
	struct range **tarray, *nlist, **listp, *prange;
	int i;

	tarray = calloc(count, sizeof(struct range *));
	if (tarray == NULL)
		return NULL;

	i = 0;
	for (prange = head; prange; prange = prange->next) {
		assert(i < count);
		tarray[i] = prange;
		i++;
	}
	assert(i == count);
	qsort_r(tarray, count, sizeof(struct range *), rangecmp, sfunc);
	listp = &nlist;
	for (i = 0; i < count; i++) {
		assert(tarray[i+1] == NULL ||
		       tarray[i]->start <= tarray[i+1]->start);
		prange = tarray[i];
		*listp = prange;
		listp = &prange->next;
	}
	*listp = NULL;
	free(tarray);
	return nlist;
}
#endif

1112
1113
1114
1115
/*
 * A very dumb bubblesort!
 */
void
Mike Hibler's avatar
Mike Hibler committed
1116
sortrange(struct range **headp, int domerge,
Mike Hibler's avatar
Mike Hibler committed
1117
	  int (*rangecmp)(struct range *, struct range *))
1118
{
Mike Hibler's avatar
Mike Hibler committed
1119
	struct range	*prange, tmp, *head = *headp;
1120
1121
	int		changed = 1;

Mike Hibler's avatar
all:    
Mike Hibler committed
1122
	if (head == NULL)
1123
1124
		return;
	
Mike Hibler's avatar
Mike Hibler committed
1125
1126
1127
1128
1129
1130
1131