4 #define _LARGEFILE_SOURCE
5 #define _LARGEFILE64_SOURCE
17 #include <ext2fs/ext2fs.h>
22 #define BUF_ZERO_BLOCKS 0x100 /* *BLOCK, =128KB, in BSS section */
32 #define LINE_MAX 0x1000
35 #define BLOCK (0x200) /* 512 */
37 static void finish(void) G_GNUC_NORETURN;
39 static int src_fd=-1,dst_fd=-1;
40 static const char *src_name,*dst_name;
41 static ext2_loff_t src_len; /* in blocks! */
42 static blk_t src_lenblk; /* ==src_len, just a different type */
44 static ext2_loff_t stat_lastread,stat_todo,stat_bads,stat_largest,stat_todo_hunks;
47 ext2_loff_t start,end;
49 static GTree *todo_tree; /* struct range *key, NULL value */
50 static GTree *bad_tree; /* struct range *key, NULL value */
51 static GMemChunk *node_memchunk; /* struct range */
53 static gint tree_linearize_traverse(struct range *key,gpointer value/*unused*/,struct range **r_fillp/*data*/)
56 g_mem_chunk_free(node_memchunk,key);
60 /* mallocated result, data-terminated, input "tree" destroyed */
61 static struct range *tree_linearize(GTree *tree)
63 struct range *r=g_new(struct range,g_tree_nnodes(tree)+1);
64 struct range *r_fill=r;
66 g_tree_traverse(tree,(GTraverseFunc)tree_linearize_traverse,G_IN_ORDER,&r_fill/*data*/);
67 g_assert(r_fill==r+g_tree_nnodes(tree));
68 r_fill->start=r_fill->end=src_len+1; /* terminator */
73 /* returns terminator! */
74 static struct range *linear_join(struct range *linear,GCompareFunc comparefunc)
76 struct range *linear_term,*dst,*src;
78 for (linear_term=linear;linear_term->start<=src_len;linear_term++);
79 qsort(linear,linear_term-linear,sizeof(*linear),(int (*)(const void *, const void *))comparefunc);
80 for (dst=src=linear;src->start<=src_len;src++) {
81 if (dst>linear && dst[-1].end==src->start)
86 *dst=*src; /* terminator */
90 static gint range_compare(const struct range *range1,const struct range *range2)
92 ext2_loff_t len1,len2;
95 g_return_val_if_fail(range1->end>range1->start,0);
96 g_return_val_if_fail(range2->end>range2->start,0);
98 len1=range1->end-range1->start;
99 len2=range2->end-range2->start;
101 /* big..small (start with large blocks) */
102 if ((r=(len2 > len1) - (len2 < len1)))
104 /* big..small (reversed processing order) */
105 if ((r=(range2->start > range1->start) - (range2->start < range1->start)))
110 static gint range_compare_diskorder(const struct range *range1,const struct range *range2)
114 g_return_val_if_fail(range1->end>range1->start,0);
115 g_return_val_if_fail(range2->end>range2->start,0);
117 /* small..big (linear disk processing order) */
118 if ((r=(range2->start < range1->start) - (range2->start > range1->start)))
120 /* small..big (shouldn't have effect, just to get valid compare for ==) */
121 if ((r=(range2->end < range1->end ) - (range2->end > range1->end )))
126 static struct range *node_build(ext2_loff_t start,ext2_loff_t end)
128 struct range *r=g_mem_chunk_alloc(node_memchunk);
135 static gint search_end(struct range *key,ext2_loff_t *endp/*data*/)
139 if ((r=(*endp < key->end) - (*endp > key->end)))
144 static gint search_start(struct range *key,ext2_loff_t *startp/*data*/)
148 if ((r=(*startp < key->start) - (*startp > key->start)))
153 static void node_add_bad(ext2_loff_t start,ext2_loff_t end)
155 struct range *key,*neigh_left,*neigh_right;
159 key=node_build(start,end);
160 if ((neigh_left =g_tree_search(bad_tree,(GSearchFunc)search_end ,&start))) {
161 g_assert(neigh_left->end==key->start);
162 key->start=neigh_left->start;
163 g_tree_remove(bad_tree,neigh_left);
164 g_mem_chunk_free(node_memchunk,neigh_left);
166 if ((neigh_right=g_tree_search(bad_tree,(GSearchFunc)search_start,&end ))) {
167 g_assert(neigh_right->start==key->end);
168 key->end=neigh_right->end;
169 g_tree_remove(bad_tree,neigh_right);
170 g_mem_chunk_free(node_memchunk,neigh_right);
172 g_tree_insert(bad_tree,key/*key*/,NULL/*value*/);
173 stat_bads+=(end-start);
176 static void node_add_todo(ext2_loff_t start,ext2_loff_t end)
180 g_tree_insert(todo_tree,node_build(start,end)/*key*/,NULL/*value*/);
184 static gint traverse_fetchleftkey(gpointer key,gpointer value/*unused*/,gpointer *keyp/*data*/)
190 static time_t stat_timelast;
192 static void stat_print(void)
196 if (stat_timelast==(now=time(NULL)))
199 fprintf(stderr,"@%llu/%llu,TODO=%llu,bad=%llu,largest=%llu,hunks=%llu %10s\r",
200 (unsigned long long)stat_lastread,
201 (unsigned long long)src_len,
202 (unsigned long long)stat_todo,
203 (unsigned long long)stat_bads,
204 (unsigned long long)stat_largest,
205 (unsigned long long)stat_todo_hunks,
210 static ext2_loff_t simulate_bads=0;
212 static void user_input(ext2_loff_t pending_start,ext2_loff_t pending_end)
222 if (select(1,&rfds,NULL,NULL,&tv)<=0)
224 if (buf!=fgets(buf,sizeof(buf),stdin)) {
225 fprintf(stderr,"Weird stdin in user_input, assumed line \"f\"\n");
228 stat_timelast=0; /* reprint statistics line immeadiately */
231 node_add_todo(pending_start,pending_end);
232 finish(); /* finish(): G_GNUC_NORETURN */
235 int bads=atoi(buf+1);
237 simulate_bads+=(bads>=1 ? bads : 1);
240 fprintf(stderr,"Unrecognized key '%c': 'f'=finish(), 'b[<num>]'=simulate bads\n",
241 (isprint(*buf) ? *buf : '?'));
245 static void write_dst(ext2_loff_t start,ext2_loff_t end,const void *buf)
247 size_t len=(end-start)*BLOCK;
249 ext2_loff_t gotext2_loff;
253 if (start*BLOCK!=(gotext2_loff=ext2fs_llseek(dst_fd,start*BLOCK,SEEK_SET))) {
254 fprintf(stderr,"ext2fs_llseek(\"%s\",%llu)=%lld: %m\n",dst_name,(unsigned long long)(start*BLOCK),
255 (signed long long)gotext2_loff);
258 if (len!=(gotssize=write(dst_fd,buf,len))) {
259 fprintf(stderr,"write(\"%s\",@%llu-@%llu=%llu=%lluB)=%lld: %m\n",dst_name,
260 (unsigned long long)start,
261 (unsigned long long)end,
262 (unsigned long long)(end-start),
263 (unsigned long long)((end-start)*BLOCK),
264 ( signed long long)gotssize);
269 static void process(ext2_loff_t start,ext2_loff_t end)
271 unsigned char block_buf[BLOCK];
273 ext2_loff_t gotext2_loff;
275 g_return_if_fail(start<end);
276 g_return_if_fail(end<=src_len);
279 fprintf(stderr,"process([%llu,%llu])\n",(unsigned long long)start,(unsigned long long)end);
282 restart: /* continues when the block was successfuly read */
284 user_input(start,end);
287 if (start*BLOCK!=(gotext2_loff=ext2fs_llseek(src_fd,start*BLOCK,SEEK_SET))) {
288 fprintf(stderr,"ext2fs_llseek(\"%s\",%llu)=%lld: %m\n",src_name,(unsigned long long)(start*BLOCK),
289 (signed long long)gotext2_loff);
292 stat_todo--; /* for the forthcoming read() */
293 if (!simulate_bads && sizeof(block_buf)==read(src_fd,block_buf,sizeof(block_buf))) {
295 write_dst(start,start+1,block_buf);
297 if (start>=end) /* finished */
304 bads=1; /* one block was detected */
309 if (start+bads>src_len)
311 node_add_bad(start,start+bads);
314 ext2_loff_t mid=(start+end)/2;
317 node_add_todo(mid,end);
322 static void range_zero(ext2_loff_t start,ext2_loff_t end)
324 static const unsigned char buf_zero[BUF_ZERO_BLOCKS*BLOCK];
326 g_return_if_fail(start<end);
329 ext2_loff_t mid=((end-start)>BUF_ZERO_BLOCKS ? start+BUF_ZERO_BLOCKS : end);
330 g_assert(mid>=start);
333 write_dst(start,mid,buf_zero);
339 static void finish(void)
341 struct range *todo_linear=tree_linearize(todo_tree),*todol;
342 struct range *bad_linear =tree_linearize(bad_tree ),*badl ;
344 linear_join(todo_linear,(GCompareFunc)range_compare_diskorder);
347 for (todol=todo_linear,badl=bad_linear;
348 todol->start<=src_len || badl->start<=src_len;) {
349 ext2_loff_t start,end;
351 g_assert(badl->start!=todol->start);
352 if (badl->start<todol->start) {
353 g_assert(todol->start>=badl->end);
354 if (todol->start==badl->end) {
355 printf("%llu-%llu\t;BAD=%llu, TODO(@%llu-@%llu)=%llu",
356 (unsigned long long)(start=badl->start),
357 (unsigned long long)(end=todol->end),
358 (unsigned long long)(badl->end-badl->start),
359 (unsigned long long)todol->start,
360 (unsigned long long)todol->end,
361 (unsigned long long)(todol->end-todol->start));
365 printf("%llu-%llu\t;BAD=%llu",
366 (unsigned long long)(start=badl->start),
367 (unsigned long long)(end=badl->end),
368 (unsigned long long)(badl->end-badl->start));
372 g_assert(badl->start>todol->start);
373 printf("%llu-%llu\t;TODO=%llu",
374 (unsigned long long)(start=todol->start),
375 (unsigned long long)(end=todol->end),
376 (unsigned long long)(todol->end-todol->start));
380 range_zero(start,end);
386 int main(int argc,char **argv)
388 /* prevent block-buffering such as: badblock-guess.c|tee x.log */
392 if (argc!=2 && argc!=3) {
393 fprintf(stderr,"Syntax: badblock-guess <src_dev> [<dst_dev (OVERWRITTEN & DESTROYED!!!)>]\n");
396 if (-1==(src_fd=open64((src_name=argv[1]),O_RDONLY|O_BINARY))) {
397 fprintf(stderr,"open64(\"%s\",O_RDONLY|O_BINARY): %m\n",src_name);
400 if (argv[2] && -1==(dst_fd=open64((dst_name=argv[2]),O_WRONLY|O_BINARY))) {
401 fprintf(stderr,"open64(\"%s\",O_WRONLY|O_BINARY): %m\n",dst_name);
405 struct stat src_stat,dst_stat;
407 if (fstat(src_fd,&src_stat)) {
408 fprintf(stderr,"fstat(\"%s\"): %m\n",src_name);
411 if (fstat(dst_fd,&dst_stat)) {
412 fprintf(stderr,"fstat(\"%s\"): %m\n",dst_name);
415 if ((S_ISBLK(src_stat.st_mode) && S_ISBLK(dst_stat.st_mode) && src_stat.st_rdev==dst_stat.st_rdev)
416 || (src_stat.st_dev==dst_stat.st_dev && src_stat.st_ino==dst_stat.st_ino)) {
417 fprintf(stderr,"Refusing to operate on two identical devs (src=\"%s\" and dst=\"%s\")\n",src_name,dst_name);
421 if (ext2fs_get_device_size(src_name,BLOCK,&src_lenblk)) {
422 fprintf(stderr,"ext2fs_get_device_size(\"%s\",%d,...): %m\n",src_name,BLOCK);
427 fprintf(stderr,"\"%s\" length %llu <=0\n",src_name,(unsigned long long)src_len);
431 node_memchunk=g_mem_chunk_new("node_memchunk",sizeof(struct range)/*atom_size*/,
432 0x1000 /*are_size: 64KB*/,G_ALLOC_AND_FREE);
433 todo_tree=g_tree_new((GCompareFunc)range_compare);
434 bad_tree=g_tree_new((GCompareFunc)range_compare_diskorder);
435 node_add_todo(0,src_len);
439 struct range *left=NULL; /* key */
441 g_tree_traverse(todo_tree,(GTraverseFunc)traverse_fetchleftkey,G_IN_ORDER,&left/*data*/);
442 if (!left) /* done */
444 #ifndef G_DISABLE_ASSERT
446 gint nnodes_preremove=g_tree_nnodes(todo_tree);
448 g_tree_remove(todo_tree,left/*key*/);
449 #ifndef G_DISABLE_ASSERT
450 g_assert(g_tree_nnodes(todo_tree)==nnodes_preremove-1);
453 stat_largest=(left->end-left->start);
454 process(left->start,left->end);
455 g_mem_chunk_free(node_memchunk,left);
458 finish(); /* finish(): G_GNUC_NORETURN */