badblock-guess.c

   1 /* $Id$ */
   2
   3 /*
   4  * badblock-guess: Quickly recover most of the data from a damaged disk
   5  * Copyright (C) 2002  Jan Kratochvil <short@ucw.cz>
   6  *
   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
  10  *
  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.
  15  *
  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
  19  */
  20
  21
  22 #define _LARGEFILE_SOURCE
  23 #define _LARGEFILE64_SOURCE
  24
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <unistd.h>
  28 #include <fcntl.h>
  29 #include <time.h>
  30 #include <sys/stat.h>
  31 #include <string.h>
  32 #include <limits.h>
  33 #include <ctype.h>
  34 #include <glib.h>
  35 #include <ext2fs/ext2fs.h>
  36
  37
  38 /* configuation */
  39
  40 #define BUF_ZERO_BLOCKS 0x100   /* *BLOCK, =128KB, in BSS section */
  41 #define xDEBUG 1
  42
  43
  44 /* implementation */
  45
  46 #ifndef O_BINARY
  47 #define O_BINARY 0
  48 #endif
  49 #ifndef LINE_MAX
  50 #define LINE_MAX 0x1000
  51 #endif
  52
  53 #define BLOCK (0x200)   /* 512 */
  54
  55 static void finish(void) G_GNUC_NORETURN;
  56
  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 */
  61
  62 static ext2_loff_t stat_lastread,stat_todo,stat_bads,stat_largest,stat_todo_hunks;
  63
  64 struct range {
  65                 ext2_loff_t start,end;
  66                 };
  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 */
  70
  71 static gint tree_linearize_traverse(struct range *key,gpointer value/*unused*/,struct range **r_fillp/*data*/)
  72 {
  73         *(*r_fillp)++=*key;
  74         g_mem_chunk_free(node_memchunk,key);
  75         return FALSE;
  76 }
  77
  78 /* mallocated result, data-terminated, input "tree" destroyed */
  79 static struct range *tree_linearize(GTree *tree)
  80 {
  81 struct range *r=g_new(struct range,g_tree_nnodes(tree)+1);
  82 struct range *r_fill=r;
  83
  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 */
  87         g_tree_destroy(tree);
  88         return r;
  89 }
  90
  91 /* returns terminator! */
  92 static struct range *linear_join(struct range *linear,GCompareFunc comparefunc)
  93 {
  94 struct range *linear_term,*dst,*src;
  95
  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;
 101                 else
 102                         *dst++=*src;
 103                 }
 104         *dst=*src;      /* terminator */
 105         return dst;
 106 }
 107
 108 static gint range_compare(const struct range *range1,const struct range *range2)
 109 {
 110 ext2_loff_t len1,len2;
 111 int r;
 112
 113         g_return_val_if_fail(range1->end>range1->start,0);
 114         g_return_val_if_fail(range2->end>range2->start,0);
 115
 116         len1=range1->end-range1->start;
 117         len2=range2->end-range2->start;
 118
 119         /* big..small (start with large blocks) */
 120         if ((r=(len2 > len1) - (len2 < len1)))
 121                 return r;
 122         /* big..small (reversed processing order) */
 123         if ((r=(range2->start > range1->start) - (range2->start < range1->start)))
 124                 return r;
 125         return 0;
 126 }
 127
 128 static gint range_compare_diskorder(const struct range *range1,const struct range *range2)
 129 {
 130 int r;
 131
 132         g_return_val_if_fail(range1->end>range1->start,0);
 133         g_return_val_if_fail(range2->end>range2->start,0);
 134
 135         /* small..big (linear disk processing order) */
 136         if ((r=(range2->start < range1->start) - (range2->start > range1->start)))
 137                 return r;
 138         /* small..big (shouldn't have effect, just to get valid compare for ==) */
 139         if ((r=(range2->end   < range1->end  ) - (range2->end   > range1->end  )))
 140                 return r;
 141         return 0;
 142 }
 143
 144 static struct range *node_build(ext2_loff_t start,ext2_loff_t end)
 145 {
 146 struct range *r=g_mem_chunk_alloc(node_memchunk);
 147
 148         r->start=start;
 149         r->end=end;
 150         return r;
 151 }
 152
 153 static gint search_end(struct range *key,ext2_loff_t *endp/*data*/)
 154 {
 155 int r;
 156
 157         if ((r=(*endp < key->end) - (*endp > key->end)))
 158                 return r;
 159         return 0;
 160 }
 161
 162 static gint search_start(struct range *key,ext2_loff_t *startp/*data*/)
 163 {
 164 int r;
 165
 166         if ((r=(*startp < key->start) - (*startp > key->start)))
 167                 return r;
 168         return 0;
 169 }
 170
 171 static void node_add_bad(ext2_loff_t start,ext2_loff_t end)
 172 {
 173 struct range *key,*neigh_left,*neigh_right;
 174
 175         if (start>=end)
 176                 return;
 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);
 183                 }
 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);
 189                 }
 190         g_tree_insert(bad_tree,key/*key*/,NULL/*value*/);
 191         stat_bads+=(end-start);
 192 }
 193
 194 static void node_add_todo(ext2_loff_t start,ext2_loff_t end)
 195 {
 196         if (start>=end)
 197                 return;
 198         g_tree_insert(todo_tree,node_build(start,end)/*key*/,NULL/*value*/);
 199         stat_todo_hunks++;
 200 }
 201
 202 static gint traverse_fetchleftkey(gpointer key,gpointer value/*unused*/,gpointer *keyp/*data*/)
 203 {
 204         *keyp=key;
 205         return TRUE;
 206 }
 207
 208 static time_t stat_timelast;
 209
 210 static void stat_print(void)
 211 {
 212 time_t now;
 213
 214         if (stat_timelast==(now=time(NULL)))
 215                 return;
 216         stat_timelast=now;
 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,
 224                         "");
 225         fflush(stderr);
 226 }
 227
 228 static ext2_loff_t simulate_bads=0;
 229
 230 static void user_input(ext2_loff_t pending_start,ext2_loff_t pending_end)
 231 {
 232 fd_set rfds;
 233 struct timeval tv;
 234 char buf[LINE_MAX];
 235
 236         FD_ZERO(&rfds);
 237         FD_SET(0,&rfds);
 238         tv.tv_sec=0;
 239         tv.tv_usec=0;
 240         if (select(1,&rfds,NULL,NULL,&tv)<=0)
 241                 return;
 242         if (buf!=fgets(buf,sizeof(buf),stdin)) {
 243                 fprintf(stderr,"Weird stdin in user_input, assumed line \"f\"\n");
 244                 strcpy(buf,"f");
 245                 }
 246         stat_timelast=0;        /* reprint statistics line immeadiately */
 247         switch (*buf) {
 248                 case 'f':
 249                         node_add_todo(pending_start,pending_end);
 250                         finish();       /* finish(): G_GNUC_NORETURN */
 251                         /* NOTREACHED */
 252                 case 'b': {
 253 int bads=atoi(buf+1);
 254
 255                         simulate_bads+=(bads>=1 ? bads : 1);
 256                         } break;
 257                 default:
 258                         fprintf(stderr,"Unrecognized key '%c': 'f'=finish(), 'b[<num>]'=simulate bads\n",
 259                                         (isprint(*buf) ? *buf : '?'));
 260                 }
 261 }
 262
 263 static void write_dst(ext2_loff_t start,ext2_loff_t end,const void *buf)
 264 {
 265 size_t len=(end-start)*BLOCK;
 266 ssize_t gotssize;
 267 ext2_loff_t gotext2_loff;
 268
 269         if (dst_fd==-1)
 270                 return;
 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);
 274                 exit(EXIT_FAILURE);
 275                 }
 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);
 283                 exit(EXIT_FAILURE);
 284                 }
 285 }
 286
 287 static void process(ext2_loff_t start,ext2_loff_t end)
 288 {
 289 unsigned char block_buf[BLOCK];
 290 ext2_loff_t bads;
 291 ext2_loff_t gotext2_loff;
 292
 293         g_return_if_fail(start<end);
 294         g_return_if_fail(end<=src_len);
 295
 296 #ifdef DEBUG
 297         fprintf(stderr,"process([%llu,%llu])\n",(unsigned long long)start,(unsigned long long)end);
 298 #endif
 299
 300 restart:        /* continues when the block was successfuly read */
 301         stat_print();
 302         user_input(start,end);
 303
 304         stat_lastread=start;
 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);
 308                 exit(EXIT_FAILURE);
 309                 }
 310         stat_todo--;    /* for the forthcoming read() */
 311         if (!simulate_bads && sizeof(block_buf)==read(src_fd,block_buf,sizeof(block_buf))) {
 312                 /* success read */
 313                 write_dst(start,start+1,block_buf);
 314                 start++;
 315                 if (start>=end) /* finished */
 316                         return;
 317                 goto restart;
 318                 }
 319
 320         /* failed read */
 321         if (!simulate_bads)
 322                 bads=1; /* one block was detected */
 323         else {
 324                 bads=simulate_bads;
 325                 simulate_bads=0;
 326                 }
 327         if (start+bads>src_len)
 328                 bads=src_len-start;
 329         node_add_bad(start,start+bads);
 330         start+=bads;
 331         while (start<end) {
 332 ext2_loff_t mid=(start+end)/2;
 333
 334                 g_assert(mid<end);
 335                 node_add_todo(mid,end);
 336                 end=mid;
 337                 }
 338 }
 339
 340 static void range_zero(ext2_loff_t start,ext2_loff_t end)
 341 {
 342 static const unsigned char buf_zero[BUF_ZERO_BLOCKS*BLOCK];
 343
 344         g_return_if_fail(start<end);
 345
 346         while (start<end) {
 347                 ext2_loff_t mid=((end-start)>BUF_ZERO_BLOCKS ? start+BUF_ZERO_BLOCKS : end);
 348                 g_assert(mid>=start);
 349                 g_assert(mid<=end);
 350
 351                 write_dst(start,mid,buf_zero);
 352
 353                 start=mid;
 354                 }
 355 }
 356
 357 static void finish(void)
 358 {
 359 struct range *todo_linear=tree_linearize(todo_tree),*todol;
 360 struct range *bad_linear =tree_linearize(bad_tree ),*badl ;
 361
 362         linear_join(todo_linear,(GCompareFunc)range_compare_diskorder);
 363
 364         fputc('\n',stderr);
 365         for (todol=todo_linear,badl=bad_linear;
 366                         todol->start<=src_len || badl->start<=src_len;) {
 367 ext2_loff_t start,end;
 368
 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));
 380                                 todol++;
 381                                 }
 382                         else
 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));
 387                         badl++;
 388                         }
 389                 else {
 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));
 395                         todol++;
 396                         }
 397                 fflush(stdout);
 398                 range_zero(start,end);
 399                 putchar('\n');
 400                 }
 401         exit(EXIT_SUCCESS);
 402 }
 403
 404 int main(int argc,char **argv)
 405 {
 406         /* prevent block-buffering such as: badblock-guess.c|tee x.log */
 407         setlinebuf(stdout);
 408         setlinebuf(stderr);
 409
 410         if (argc!=2 && argc!=3) {
 411                 fprintf(stderr,"\
 412 badblock-guess, Copyright (C) 2002 Jan Kratochvil <short@ucw.cz>\n\
 413 $Id$\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\
 417 \n\
 418 Syntax: badblock-guess <src_dev> [<dst_dev (OVERWRITTEN & DESTROYED!!!)>]\n\
 419 \n");
 420                 exit(EXIT_FAILURE);
 421                 }
 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);
 424                 exit(EXIT_FAILURE);
 425                 }
 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);
 428                 exit(EXIT_FAILURE);
 429                 }
 430         if (dst_fd!=-1) {
 431 struct stat src_stat,dst_stat;
 432
 433                         if (fstat(src_fd,&src_stat)) {
 434                                 fprintf(stderr,"fstat(\"%s\"): %m\n",src_name);
 435                                 exit(EXIT_FAILURE);
 436                                 }
 437                         if (fstat(dst_fd,&dst_stat)) {
 438                                 fprintf(stderr,"fstat(\"%s\"): %m\n",dst_name);
 439                                 exit(EXIT_FAILURE);
 440                                 }
 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);
 444                                 exit(EXIT_FAILURE);
 445                                 }
 446                 }
 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);
 449                 exit(EXIT_FAILURE);
 450                 }
 451         src_len=src_lenblk;
 452         if (src_len<=0) {
 453                 fprintf(stderr,"\"%s\" length %llu <=0\n",src_name,(unsigned long long)src_len);
 454                 exit(EXIT_FAILURE);
 455                 }
 456
 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);
 462         stat_todo=src_len;
 463
 464         for (;;) {
 465 struct range *left=NULL;        /* key */
 466
 467                 g_tree_traverse(todo_tree,(GTraverseFunc)traverse_fetchleftkey,G_IN_ORDER,&left/*data*/);
 468                 if (!left)      /* done */
 469                                 break;
 470 #ifndef G_DISABLE_ASSERT
 471                 {
 472                         gint nnodes_preremove=g_tree_nnodes(todo_tree);
 473 #endif
 474                 g_tree_remove(todo_tree,left/*key*/);
 475 #ifndef G_DISABLE_ASSERT
 476                         g_assert(g_tree_nnodes(todo_tree)==nnodes_preremove-1);
 477                         }
 478 #endif
 479                 stat_largest=(left->end-left->start);
 480                 process(left->start,left->end);
 481                 g_mem_chunk_free(node_memchunk,left);
 482                 stat_todo_hunks--;
 483                 }
 484         finish();       /* finish(): G_GNUC_NORETURN */
 485         /* NOTREACHED */
 486 }