2 * Copyright (C) 2004 Jens Axboe <axboe@suse.de>
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License version 2 as
6 * published by the Free Software Foundation.
16 #include <sys/types.h>
17 #include <sys/ioctl.h>
29 #define BITS_PER_LONG 64
30 static int arch = arch_x86_64;
31 inline unsigned long ffz(unsigned long bitmask)
33 __asm__("bsfq %1,%0" :"=r" (bitmask) :"r" (~bitmask));
36 #elif defined (__i386__)
37 #define BITS_PER_LONG 32
38 static int arch = arch_i386;
39 inline unsigned long ffz(unsigned long bitmask)
41 __asm__("bsfl %1,%0" :"=r" (bitmask) :"r" (~bitmask));
44 #elif defined (__powerpc__)
45 #define BITS_PER_LONG 32
46 static int arch = arch_ppc;
47 inline int __ilog2(unsigned long bitmask)
51 asm ("cntlzw %0,%1" : "=r" (lz) : "r" (bitmask));
55 static inline int ffz(unsigned long bitmask)
57 if ((bitmask = ~bitmask) == 0)
59 return __ilog2(bitmask & -bitmask);
61 #elif defined(__ia64__)
62 #define BITS_PER_LONG 64
63 static int arch = arch_ia64;
64 #define ia64_popcnt(x) \
66 unsigned long ia64_intri_res; \
67 asm ("popcnt %0=%1" : "=r" (ia64_intri_res) : "r" (x)); \
70 inline unsigned long ffz(unsigned long bitmask)
72 return ia64_popcnt(bitmask & (~bitmask - 1));
75 #error "Unsupported architecture"
78 #if BITS_PER_LONG == 32
79 typedef unsigned long long u64;
80 typedef unsigned long u32;
81 #elif BITS_PER_LONG == 64
82 typedef unsigned long u64;
83 typedef unsigned int u32;
87 #define BLKGETSIZE64 _IOR(0x12,114,size_t)
93 #define ALIGN(buf) (((unsigned long) (buf) + MASK) & ~(MASK))
95 #define BITMAP_BLOCKS(blocks) (((blocks) / BITS_PER_LONG) + 1)
96 #define BITMAP_SIZE(blocks) (BITMAP_BLOCKS(blocks) * sizeof(unsigned long))
98 #define RANDOM_COVERAGE (90)
100 static char device[256];
101 static char state_file[256];
102 static int progress_interval;
103 static int block_size;
104 static int restore_state = 1;
105 static struct timeval start;
106 static int sequential;
107 static int disk_util = 100;
108 static int disk_util_set;
109 static int state_file_fd = -1;
110 static int state_restored;
112 static unsigned long *read_bitmap;
113 static unsigned long find_next_bit_index;
114 static unsigned long blocks_read, blocks_read_now;
117 static struct drand48_data random_state;
125 #define DRIVESCAN_MAGIC 0xabc0ffee
126 #define DRIVESCAN_VERSION 2
128 struct progress_state {
135 struct drand48_data random_state;
138 inline int test_block_read(unsigned long block)
140 unsigned long index, bitnr;
142 index = block / BITS_PER_LONG;
143 bitnr = block & (BITS_PER_LONG - 1);
144 return (read_bitmap[index] & (1UL << bitnr)) != 0;
147 inline int mark_block_read(unsigned long block)
149 unsigned long index, bitnr, retval;
151 index = block / BITS_PER_LONG;
152 bitnr = block & (BITS_PER_LONG - 1);
154 retval = (read_bitmap[index] & (1UL << bitnr)) != 0;
155 read_bitmap[index] |= 1UL << bitnr;
159 inline unsigned long find_next_unread_block(void)
161 unsigned int i, bitnr;
163 for (i = find_next_bit_index; i < BITMAP_BLOCKS(dev_size); i++) {
164 if (read_bitmap[i] == ~0UL)
172 find_next_bit_index = i;
173 bitnr = ffz(read_bitmap[i]);
174 read_bitmap[i] |= 1UL << bitnr;
175 return bitnr + BITS_PER_LONG * i;
178 int load_progress_state(void)
180 struct progress_state state;
184 if (state_file_fd == -1)
187 if (lseek(state_file_fd, 0, SEEK_SET) == -1) {
188 perror("state file seek");
192 ret = read(state_file_fd, &state, sizeof(state));
194 perror("load progress file");
199 if (state.magic != DRIVESCAN_MAGIC) {
200 printf("Bad magic %lx\n", (unsigned long) state.magic);
203 if (state.version != DRIVESCAN_VERSION) {
204 printf("Unsupported file version (%d)\n", (int) state.version);
207 if (state.arch != arch) {
208 printf("State file from different arch\n");
212 read_bitmap = malloc(BITMAP_SIZE(state.blocks));
214 printf("Unable to allocate bitmap (blocks=%Lu)\n", (unsigned long long) state.blocks);
217 memset(read_bitmap, 0, BITMAP_SIZE(dev_size));
219 if (read(state_file_fd, (char *) read_bitmap, BITMAP_SIZE(state.blocks)) < BITMAP_SIZE(state.blocks)) {
220 printf("Unable to read bitmap\n");
225 for (i = 0; i < state.blocks; i++)
226 if (test_block_read(i))
229 if (blocks_read == dev_size)
232 memcpy(&random_state, &state.random_state, sizeof(random_state));
234 dev_size = state.blocks;
235 block_size = state.bs;
237 disk_util = state.disk_util;
238 printf("Restored state: %lu blocks\n", blocks_read);
243 void save_progress_state(void)
245 struct progress_state state;
248 if (ftruncate(state_file_fd, 0) == -1) {
249 perror("truncate state file");
252 if (lseek(state_file_fd, 0, SEEK_SET) == -1) {
253 perror("lseek state file");
257 memset(&state, 0, sizeof(state));
258 state.magic = DRIVESCAN_MAGIC;
260 state.version = DRIVESCAN_VERSION;
261 state.bs = block_size;
262 state.blocks = dev_size;
263 state.disk_util = disk_util;
264 memcpy(&state.random_state, &random_state, sizeof(random_state));
266 ret = write(state_file_fd, &state, sizeof(state));
268 perror("write state file");
272 ret = write(state_file_fd, (char *) read_bitmap, BITMAP_SIZE(dev_size));
274 perror("write state bitmap");
278 fsync(state_file_fd);
279 printf("Saved state: %lu blocks\n", blocks_read);
282 unsigned long utime_since(struct timeval *s)
287 gettimeofday(&now, NULL);
288 sec = now.tv_sec - s->tv_sec;
289 usec = now.tv_usec - s->tv_usec;
290 if (sec > 0 && usec < 0) {
294 return usec + (sec * (double) 1000000);
297 unsigned long time_since_now(void)
299 double sec, usec, ret;
302 gettimeofday(&now, NULL);
303 sec = now.tv_sec - start.tv_sec;
304 usec = now.tv_usec - start.tv_usec;
305 if (sec > 0 && usec < 0) {
309 ret = sec + usec / (double) 1000000;
313 return (unsigned long) ret;
316 void normalize_time(struct our_time *ot, unsigned long seconds)
318 ot->hour = seconds / 3600;
319 seconds -= ot->hour * 3600;
320 ot->min = seconds / 60;
321 seconds -= ot->min * 60;
325 void show_progress_state(void)
327 unsigned long rate, now;
328 struct our_time comp, left;
330 now = time_since_now();
332 normalize_time(&comp, now);
337 rate = blocks_read_now / now;
339 memset(&left, 0, sizeof(left));
341 normalize_time(&left, (dev_size * now / blocks_read_now) - now);
344 printf("\tRun: [%luh%lum%lusec, %luh%lum%lusec], %lu blocks/sec, %lu KiB/sec\n", comp.hour, comp.min, comp.sec, left.hour, left.min, left.sec, rate, rate * block_size / 1024);
345 printf("\tRead:[%lu, %lu]: %lu%% coverage\n", blocks_read, (unsigned long) dev_size, (unsigned long) (blocks_read * 100 / dev_size));
348 void sig_handler(int sig)
350 show_progress_state();
355 save_progress_state();
358 if (progress_interval)
359 alarm(progress_interval);
364 unsigned long get_next_offset(unsigned long blocks)
366 unsigned long b, retries = dev_size;
372 lrand48_r(&random_state, &r);
373 b = (1+(double) (blocks-1) * r / (RAND_MAX+1.0));
375 if (!mark_block_read(b))
381 printf("Gave up finding new block\n");
387 b = find_next_unread_block();
395 void idle_drive(struct timeval *s)
397 unsigned long msleep, sleep_time;
400 if (disk_util == 100)
403 msleep = utime_since(s);
404 ratio = (double) 100 / disk_util;
405 sleep_time = msleep * ratio - msleep;
409 void read_error_report(int fd, char *buffer, unsigned long long offset)
411 unsigned long long bad_block = offset >> 9;
412 int blocks = block_size / 512;
415 if (lseek(fd, offset, SEEK_SET) == -1) {
420 for (i = 0; i < blocks; i++) {
421 ret = read(fd, buffer, 512);
425 else if (ret < 512 && ret >= 0) {
426 printf("Short read at sector %Lu\n", bad_block + i);
429 if (errno == EINVAL) {
430 printf("512-b O_DIRECT does not work\n");
434 printf("Sector %Lu bad\n", bad_block + i);
438 void do_random_reads(int fd, unsigned long blocks)
444 ptr = malloc(block_size + MASK + 1);
445 buffer = (char *) ALIGN(ptr);
448 off_t offset = get_next_offset(blocks);
451 offset = get_next_offset(blocks);
455 offset = offset * block_size;
457 if (lseek(fd, offset, SEEK_SET) == -1) {
462 gettimeofday(&s, NULL);
463 ret = read(fd, buffer, block_size);
466 if (errno == EINVAL) {
467 printf("EINVAL on read, check if O_DIRECT works\n");
469 } else if (errno == EIO) {
470 read_error_report(fd, buffer, offset);
476 if (ret < block_size)
477 read_error_report(fd, buffer, offset);
479 coverage = blocks_read * 100 / dev_size;
480 if (!sequential && coverage >= RANDOM_COVERAGE) {
481 printf("Switching to scan for rest of blocks\n");
485 if (blocks_read == dev_size)
492 show_progress_state();
497 int seed_randomizer(void)
502 fd = open("/dev/random", O_RDONLY);
508 if (read(fd, &seed, sizeof(seed)) < (int) sizeof(seed)) {
515 printf("Randomizer seed: %lx\n", seed);
516 srand48_r(seed, &random_state);
520 void device_to_state_file(void)
522 unsigned int i, offset;
524 offset = sprintf(state_file, "scanstate");
526 for (i = 0; i < strlen(device); i++) {
527 if (device[i] == '/')
528 state_file[offset+i] = '_';
530 state_file[offset+i] = device[i];
534 void init_state_file(void)
537 device_to_state_file();
539 state_file_fd = open(state_file, O_RDWR | O_CREAT, 0644);
541 if (state_file_fd == -1) {
542 perror("open state file");
547 int get_options(int argc, char *argv[])
549 static struct option longoptions[] = {
550 { "device", 1, NULL, 'd' },
551 { "block-size", 1, NULL, 'b' },
552 { "progress", 1, NULL, 'p' },
553 { "file", 1, NULL, 'f' },
554 { "restore", 1, NULL, 'r' },
555 { "utilization",1, NULL, 'i' },
559 while ((c = getopt_long(argc, argv, "d:b:p:f:ru:", longoptions, &res)) != -1) {
562 strncpy(device, optarg, sizeof(device) - 1);
565 block_size = atoi(optarg);
566 if (block_size < 1 || block_size > 1024) {
567 printf("bad block size %d\n", block_size);
573 progress_interval = atoi(optarg);
576 strncpy(state_file, optarg, sizeof(state_file)-1);
579 restore_state = !!atoi(optarg);
582 disk_util = atoi(optarg);
593 printf("Must give device with -d\n");
602 int main(int argc, char *argv[])
608 if (get_options(argc, argv))
616 load_progress_state();
618 if (stat(device, &statbuf) == -1) {
623 if (!S_ISBLK(statbuf.st_mode)) {
624 printf("%s does not appear to be a block device\n", device);
628 fd = open(device, O_RDONLY | O_DIRECT | O_LARGEFILE);
634 if (ioctl(fd, BLKGETSIZE64, &size) == -1) {
635 perror("BLKGETSIZE64");
639 blocks = size / block_size;
641 if (state_restored && dev_size != blocks) {
642 printf("Device size seems different %lu != %lu\n", (unsigned long) dev_size, (unsigned long) blocks);
649 read_bitmap = malloc(BITMAP_SIZE(dev_size));
650 memset(read_bitmap, 0, BITMAP_SIZE(dev_size));
653 signal(SIGUSR1, sig_handler);
654 signal(SIGINT, sig_handler);
656 if (progress_interval) {
657 signal(SIGALRM, sig_handler);
658 alarm(progress_interval);
661 gettimeofday(&start, NULL);
662 do_random_reads(fd, blocks);
664 save_progress_state();
666 free((void *) read_bitmap);
668 if (state_file_fd != -1)
669 close(state_file_fd);