4 * badblock-guess: Quickly recover most of the data from a damaged disk
5 * Copyright (C) 2002 Jan Kratochvil <short@ucw.cz>
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; exactly version 2 of the License required
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
22 #define _LARGEFILE_SOURCE
23 #define _LARGEFILE64_SOURCE
35 #include <ext2fs/ext2fs.h>
40 #define BUF_ZERO_BLOCKS 0x100 /* *BLOCK, =128KB, in BSS section */
50 #define LINE_MAX 0x1000
53 #define BLOCK (0x200) /* 512 */
55 static void finish(void) G_GNUC_NORETURN;
57 static int src_fd=-1,dst_fd=-1;
58 static const char *src_name,*dst_name;
59 static ext2_loff_t src_len; /* in blocks! */
60 static blk_t src_lenblk; /* ==src_len, just a different type */
62 static ext2_loff_t stat_lastread,stat_todo,stat_bads,stat_largest,stat_todo_hunks;
65 ext2_loff_t start,end;
67 static GTree *todo_tree; /* struct range *key, NULL value */
68 static GTree *bad_tree; /* struct range *key, NULL value */
69 static GMemChunk *node_memchunk; /* struct range */
71 static gint tree_linearize_traverse(struct range *key,gpointer value/*unused*/,struct range **r_fillp/*data*/)
74 g_mem_chunk_free(node_memchunk,key);
78 /* mallocated result, data-terminated, input "tree" destroyed */
79 static struct range *tree_linearize(GTree *tree)
81 struct range *r=g_new(struct range,g_tree_nnodes(tree)+1);
82 struct range *r_fill=r;
84 g_tree_traverse(tree,(GTraverseFunc)tree_linearize_traverse,G_IN_ORDER,&r_fill/*data*/);
85 g_assert(r_fill==r+g_tree_nnodes(tree));
86 r_fill->start=r_fill->end=src_len+1; /* terminator */
91 /* returns terminator! */
92 static struct range *linear_join(struct range *linear,GCompareFunc comparefunc)
94 struct range *linear_term,*dst,*src;
96 for (linear_term=linear;linear_term->start<=src_len;linear_term++);
97 qsort(linear,linear_term-linear,sizeof(*linear),(int (*)(const void *, const void *))comparefunc);
98 for (dst=src=linear;src->start<=src_len;src++) {
99 if (dst>linear && dst[-1].end==src->start)
100 dst[-1].end=src->end;
104 *dst=*src; /* terminator */
108 static gint range_compare(const struct range *range1,const struct range *range2)
110 ext2_loff_t len1,len2;
113 g_return_val_if_fail(range1->end>range1->start,0);
114 g_return_val_if_fail(range2->end>range2->start,0);
116 len1=range1->end-range1->start;
117 len2=range2->end-range2->start;
119 /* big..small (start with large blocks) */
120 if ((r=(len2 > len1) - (len2 < len1)))
122 /* big..small (reversed processing order) */
123 if ((r=(range2->start > range1->start) - (range2->start < range1->start)))
128 static gint range_compare_diskorder(const struct range *range1,const struct range *range2)
132 g_return_val_if_fail(range1->end>range1->start,0);
133 g_return_val_if_fail(range2->end>range2->start,0);
135 /* small..big (linear disk processing order) */
136 if ((r=(range2->start < range1->start) - (range2->start > range1->start)))
138 /* small..big (shouldn't have effect, just to get valid compare for ==) */
139 if ((r=(range2->end < range1->end ) - (range2->end > range1->end )))
144 static struct range *node_build(ext2_loff_t start,ext2_loff_t end)
146 struct range *r=g_mem_chunk_alloc(node_memchunk);
153 static gint search_end(struct range *key,ext2_loff_t *endp/*data*/)
157 if ((r=(*endp < key->end) - (*endp > key->end)))
162 static gint search_start(struct range *key,ext2_loff_t *startp/*data*/)
166 if ((r=(*startp < key->start) - (*startp > key->start)))
171 static void node_add_bad(ext2_loff_t start,ext2_loff_t end)
173 struct range *key,*neigh_left,*neigh_right;
177 key=node_build(start,end);
178 if ((neigh_left =g_tree_search(bad_tree,(GSearchFunc)search_end ,&start))) {
179 g_assert(neigh_left->end==key->start);
180 key->start=neigh_left->start;
181 g_tree_remove(bad_tree,neigh_left);
182 g_mem_chunk_free(node_memchunk,neigh_left);
184 if ((neigh_right=g_tree_search(bad_tree,(GSearchFunc)search_start,&end ))) {
185 g_assert(neigh_right->start==key->end);
186 key->end=neigh_right->end;
187 g_tree_remove(bad_tree,neigh_right);
188 g_mem_chunk_free(node_memchunk,neigh_right);
190 g_tree_insert(bad_tree,key/*key*/,NULL/*value*/);
191 stat_bads+=(end-start);
194 static void node_add_todo(ext2_loff_t start,ext2_loff_t end)
198 g_tree_insert(todo_tree,node_build(start,end)/*key*/,NULL/*value*/);
202 static gint traverse_fetchleftkey(gpointer key,gpointer value/*unused*/,gpointer *keyp/*data*/)
208 static time_t stat_timelast;
210 static void stat_print(void)
214 if (stat_timelast==(now=time(NULL)))
217 fprintf(stderr,"@%llu/%llu,TODO=%llu,bad=%llu,largest=%llu,hunks=%llu %10s\r",
218 (unsigned long long)stat_lastread,
219 (unsigned long long)src_len,
220 (unsigned long long)stat_todo,
221 (unsigned long long)stat_bads,
222 (unsigned long long)stat_largest,
223 (unsigned long long)stat_todo_hunks,
228 static ext2_loff_t simulate_bads=0;
230 static void user_input(ext2_loff_t pending_start,ext2_loff_t pending_end)
240 if (select(1,&rfds,NULL,NULL,&tv)<=0)
242 if (buf!=fgets(buf,sizeof(buf),stdin)) {
243 fprintf(stderr,"Weird stdin in user_input, assumed line \"f\"\n");
246 stat_timelast=0; /* reprint statistics line immeadiately */
249 node_add_todo(pending_start,pending_end);
250 finish(); /* finish(): G_GNUC_NORETURN */
253 int bads=atoi(buf+1);
255 simulate_bads+=(bads>=1 ? bads : 1);
258 fprintf(stderr,"Unrecognized key '%c': 'f'=finish(), 'b[<num>]'=simulate bads\n",
259 (isprint(*buf) ? *buf : '?'));
263 static void write_dst(ext2_loff_t start,ext2_loff_t end,const void *buf)
265 size_t len=(end-start)*BLOCK;
267 ext2_loff_t gotext2_loff;
271 if (start*BLOCK!=(gotext2_loff=ext2fs_llseek(dst_fd,start*BLOCK,SEEK_SET))) {
272 fprintf(stderr,"ext2fs_llseek(\"%s\",%llu)=%lld: %m\n",dst_name,(unsigned long long)(start*BLOCK),
273 (signed long long)gotext2_loff);
276 if (len!=(gotssize=write(dst_fd,buf,len))) {
277 fprintf(stderr,"write(\"%s\",@%llu-@%llu=%llu=%lluB)=%lld: %m\n",dst_name,
278 (unsigned long long)start,
279 (unsigned long long)end,
280 (unsigned long long)(end-start),
281 (unsigned long long)((end-start)*BLOCK),
282 ( signed long long)gotssize);
287 static void process(ext2_loff_t start,ext2_loff_t end)
289 unsigned char block_buf[BLOCK];
291 ext2_loff_t gotext2_loff;
293 g_return_if_fail(start<end);
294 g_return_if_fail(end<=src_len);
297 fprintf(stderr,"process([%llu,%llu])\n",(unsigned long long)start,(unsigned long long)end);
300 restart: /* continues when the block was successfuly read */
302 user_input(start,end);
305 if (start*BLOCK!=(gotext2_loff=ext2fs_llseek(src_fd,start*BLOCK,SEEK_SET))) {
306 fprintf(stderr,"ext2fs_llseek(\"%s\",%llu)=%lld: %m\n",src_name,(unsigned long long)(start*BLOCK),
307 (signed long long)gotext2_loff);
310 stat_todo--; /* for the forthcoming read() */
311 if (!simulate_bads && sizeof(block_buf)==read(src_fd,block_buf,sizeof(block_buf))) {
313 write_dst(start,start+1,block_buf);
315 if (start>=end) /* finished */
322 bads=1; /* one block was detected */
327 if (start+bads>src_len)
329 node_add_bad(start,start+bads);
332 ext2_loff_t mid=(start+end)/2;
335 node_add_todo(mid,end);
340 static void range_zero(ext2_loff_t start,ext2_loff_t end)
342 static const unsigned char buf_zero[BUF_ZERO_BLOCKS*BLOCK];
344 g_return_if_fail(start<end);
347 ext2_loff_t mid=((end-start)>BUF_ZERO_BLOCKS ? start+BUF_ZERO_BLOCKS : end);
348 g_assert(mid>=start);
351 write_dst(start,mid,buf_zero);
357 static void finish(void)
359 struct range *todo_linear=tree_linearize(todo_tree),*todol;
360 struct range *bad_linear =tree_linearize(bad_tree ),*badl ;
362 linear_join(todo_linear,(GCompareFunc)range_compare_diskorder);
365 for (todol=todo_linear,badl=bad_linear;
366 todol->start<=src_len || badl->start<=src_len;) {
367 ext2_loff_t start,end;
369 g_assert(badl->start!=todol->start);
370 if (badl->start<todol->start) {
371 g_assert(todol->start>=badl->end);
372 if (todol->start==badl->end) {
373 printf("%llu-%llu\t;BAD=%llu, TODO(@%llu-@%llu)=%llu",
374 (unsigned long long)(start=badl->start),
375 (unsigned long long)(end=todol->end),
376 (unsigned long long)(badl->end-badl->start),
377 (unsigned long long)todol->start,
378 (unsigned long long)todol->end,
379 (unsigned long long)(todol->end-todol->start));
383 printf("%llu-%llu\t;BAD=%llu",
384 (unsigned long long)(start=badl->start),
385 (unsigned long long)(end=badl->end),
386 (unsigned long long)(badl->end-badl->start));
390 g_assert(badl->start>todol->start);
391 printf("%llu-%llu\t;TODO=%llu",
392 (unsigned long long)(start=todol->start),
393 (unsigned long long)(end=todol->end),
394 (unsigned long long)(todol->end-todol->start));
398 range_zero(start,end);
404 int main(int argc,char **argv)
406 /* prevent block-buffering such as: badblock-guess.c|tee x.log */
410 if (argc!=2 && argc!=3) {
412 badblock-guess, Copyright (C) 2002 Jan Kratochvil <short@ucw.cz>\n\
414 badblock-guess comes with ABSOLUTELY NO WARRANTY.\n\
415 This is free software, and you are welcome to redistribute it\n\
416 under certain conditions.\n\
418 Syntax: badblock-guess <src_dev> [<dst_dev (OVERWRITTEN & DESTROYED!!!)>]\n\
422 if (-1==(src_fd=open64((src_name=argv[1]),O_RDONLY|O_BINARY))) {
423 fprintf(stderr,"open64(\"%s\",O_RDONLY|O_BINARY): %m\n",src_name);
426 if (argv[2] && -1==(dst_fd=open64((dst_name=argv[2]),O_WRONLY|O_BINARY))) {
427 fprintf(stderr,"open64(\"%s\",O_WRONLY|O_BINARY): %m\n",dst_name);
431 struct stat src_stat,dst_stat;
433 if (fstat(src_fd,&src_stat)) {
434 fprintf(stderr,"fstat(\"%s\"): %m\n",src_name);
437 if (fstat(dst_fd,&dst_stat)) {
438 fprintf(stderr,"fstat(\"%s\"): %m\n",dst_name);
441 if ((S_ISBLK(src_stat.st_mode) && S_ISBLK(dst_stat.st_mode) && src_stat.st_rdev==dst_stat.st_rdev)
442 || (src_stat.st_dev==dst_stat.st_dev && src_stat.st_ino==dst_stat.st_ino)) {
443 fprintf(stderr,"Refusing to operate on two identical devs (src=\"%s\" and dst=\"%s\")\n",src_name,dst_name);
447 if (ext2fs_get_device_size(src_name,BLOCK,&src_lenblk)) {
448 fprintf(stderr,"ext2fs_get_device_size(\"%s\",%d,...): %m\n",src_name,BLOCK);
453 fprintf(stderr,"\"%s\" length %llu <=0\n",src_name,(unsigned long long)src_len);
457 node_memchunk=g_mem_chunk_new("node_memchunk",sizeof(struct range)/*atom_size*/,
458 0x1000 /*are_size: 64KB*/,G_ALLOC_AND_FREE);
459 todo_tree=g_tree_new((GCompareFunc)range_compare);
460 bad_tree=g_tree_new((GCompareFunc)range_compare_diskorder);
461 node_add_todo(0,src_len);
465 struct range *left=NULL; /* key */
467 g_tree_traverse(todo_tree,(GTraverseFunc)traverse_fetchleftkey,G_IN_ORDER,&left/*data*/);
468 if (!left) /* done */
470 #ifndef G_DISABLE_ASSERT
472 gint nnodes_preremove=g_tree_nnodes(todo_tree);
474 g_tree_remove(todo_tree,left/*key*/);
475 #ifndef G_DISABLE_ASSERT
476 g_assert(g_tree_nnodes(todo_tree)==nnodes_preremove-1);
479 stat_largest=(left->end-left->start);
480 process(left->start,left->end);
481 g_mem_chunk_free(node_memchunk,left);
484 finish(); /* finish(): G_GNUC_NORETURN */