badblock-guess.c

   1 /* $Id$ */
   2
   3
   4 #define _LARGEFILE_SOURCE
   5 #define _LARGEFILE64_SOURCE
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <unistd.h>
  10 #include <fcntl.h>
  11 #include <time.h>
  12 #include <sys/stat.h>
  13 #include <string.h>
  14 #include <limits.h>
  15 #include <ctype.h>
  16 #include <glib.h>
  17 #include <ext2fs/ext2fs.h>
  18
  19
  20 /* configuation */
  21
  22 #define BUF_ZERO_BLOCKS 0x100   /* *BLOCK, =128KB, in BSS section */
  23 #define xDEBUG 1
  24
  25
  26 /* implementation */
  27
  28 #ifndef O_BINARY
  29 #define O_BINARY 0
  30 #endif
  31 #ifndef LINE_MAX
  32 #define LINE_MAX 0x1000
  33 #endif
  34
  35 #define BLOCK (0x200)   /* 512 */
  36
  37 static void finish(void) G_GNUC_NORETURN;
  38
  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 */
  43
  44 static ext2_loff_t stat_lastread,stat_todo,stat_bads,stat_largest,stat_todo_hunks;
  45
  46 struct range {
  47                 ext2_loff_t start,end;
  48                 };
  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 */
  52
  53 static gint tree_linearize_traverse(struct range *key,gpointer value/*unused*/,struct range **r_fillp/*data*/)
  54 {
  55         *(*r_fillp)++=*key;
  56         g_mem_chunk_free(node_memchunk,key);
  57         return FALSE;
  58 }
  59
  60 /* mallocated result, data-terminated, input "tree" destroyed */
  61 static struct range *tree_linearize(GTree *tree)
  62 {
  63 struct range *r=g_new(struct range,g_tree_nnodes(tree)+1);
  64 struct range *r_fill=r;
  65
  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 */
  69         g_tree_destroy(tree);
  70         return r;
  71 }
  72
  73 /* returns terminator! */
  74 static struct range *linear_join(struct range *linear,GCompareFunc comparefunc)
  75 {
  76 struct range *linear_term,*dst,*src;
  77
  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)
  82                         dst[-1].end=src->end;
  83                 else
  84                         *dst++=*src;
  85                 }
  86         *dst=*src;      /* terminator */
  87         return dst;
  88 }
  89
  90 static gint range_compare(const struct range *range1,const struct range *range2)
  91 {
  92 ext2_loff_t len1,len2;
  93 int r;
  94
  95         g_return_val_if_fail(range1->end>range1->start,0);
  96         g_return_val_if_fail(range2->end>range2->start,0);
  97
  98         len1=range1->end-range1->start;
  99         len2=range2->end-range2->start;
 100
 101         /* big..small (start with large blocks) */
 102         if ((r=(len2 > len1) - (len2 < len1)))
 103                 return r;
 104         /* big..small (reversed processing order) */
 105         if ((r=(range2->start > range1->start) - (range2->start < range1->start)))
 106                 return r;
 107         return 0;
 108 }
 109
 110 static gint range_compare_diskorder(const struct range *range1,const struct range *range2)
 111 {
 112 int r;
 113
 114         g_return_val_if_fail(range1->end>range1->start,0);
 115         g_return_val_if_fail(range2->end>range2->start,0);
 116
 117         /* small..big (linear disk processing order) */
 118         if ((r=(range2->start < range1->start) - (range2->start > range1->start)))
 119                 return r;
 120         /* small..big (shouldn't have effect, just to get valid compare for ==) */
 121         if ((r=(range2->end   < range1->end  ) - (range2->end   > range1->end  )))
 122                 return r;
 123         return 0;
 124 }
 125
 126 static struct range *node_build(ext2_loff_t start,ext2_loff_t end)
 127 {
 128 struct range *r=g_mem_chunk_alloc(node_memchunk);
 129
 130         r->start=start;
 131         r->end=end;
 132         return r;
 133 }
 134
 135 static gint search_end(struct range *key,ext2_loff_t *endp/*data*/)
 136 {
 137 int r;
 138
 139         if ((r=(*endp < key->end) - (*endp > key->end)))
 140                 return r;
 141         return 0;
 142 }
 143
 144 static gint search_start(struct range *key,ext2_loff_t *startp/*data*/)
 145 {
 146 int r;
 147
 148         if ((r=(*startp < key->start) - (*startp > key->start)))
 149                 return r;
 150         return 0;
 151 }
 152
 153 static void node_add_bad(ext2_loff_t start,ext2_loff_t end)
 154 {
 155 struct range *key,*neigh_left,*neigh_right;
 156
 157         if (start>=end)
 158                 return;
 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);
 165                 }
 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);
 171                 }
 172         g_tree_insert(bad_tree,key/*key*/,NULL/*value*/);
 173         stat_bads+=(end-start);
 174 }
 175
 176 static void node_add_todo(ext2_loff_t start,ext2_loff_t end)
 177 {
 178         if (start>=end)
 179                 return;
 180         g_tree_insert(todo_tree,node_build(start,end)/*key*/,NULL/*value*/);
 181         stat_todo_hunks++;
 182 }
 183
 184 static gint traverse_fetchleftkey(gpointer key,gpointer value/*unused*/,gpointer *keyp/*data*/)
 185 {
 186         *keyp=key;
 187         return TRUE;
 188 }
 189
 190 static time_t stat_timelast;
 191
 192 static void stat_print(void)
 193 {
 194 time_t now;
 195
 196         if (stat_timelast==(now=time(NULL)))
 197                 return;
 198         stat_timelast=now;
 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,
 206                         "");
 207         fflush(stderr);
 208 }
 209
 210 static ext2_loff_t simulate_bads=0;
 211
 212 static void user_input(ext2_loff_t pending_start,ext2_loff_t pending_end)
 213 {
 214 fd_set rfds;
 215 struct timeval tv;
 216 char buf[LINE_MAX];
 217
 218         FD_ZERO(&rfds);
 219         FD_SET(0,&rfds);
 220         tv.tv_sec=0;
 221         tv.tv_usec=0;
 222         if (select(1,&rfds,NULL,NULL,&tv)<=0)
 223                 return;
 224         if (buf!=fgets(buf,sizeof(buf),stdin)) {
 225                 fprintf(stderr,"Weird stdin in user_input, assumed line \"f\"\n");
 226                 strcpy(buf,"f");
 227                 }
 228         stat_timelast=0;        /* reprint statistics line immeadiately */
 229         switch (*buf) {
 230                 case 'f':
 231                         node_add_todo(pending_start,pending_end);
 232                         finish();       /* finish(): G_GNUC_NORETURN */
 233                         /* NOTREACHED */
 234                 case 'b': {
 235 int bads=atoi(buf+1);
 236
 237                         simulate_bads+=(bads>=1 ? bads : 1);
 238                         } break;
 239                 default:
 240                         fprintf(stderr,"Unrecognized key '%c': 'f'=finish(), 'b[<num>]'=simulate bads\n",
 241                                         (isprint(*buf) ? *buf : '?'));
 242                 }
 243 }
 244
 245 static void write_dst(ext2_loff_t start,ext2_loff_t end,const void *buf)
 246 {
 247 size_t len=(end-start)*BLOCK;
 248 ssize_t gotssize;
 249 ext2_loff_t gotext2_loff;
 250
 251         if (dst_fd==-1)
 252                 return;
 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);
 256                 exit(EXIT_FAILURE);
 257                 }
 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);
 265                 exit(EXIT_FAILURE);
 266                 }
 267 }
 268
 269 static void process(ext2_loff_t start,ext2_loff_t end)
 270 {
 271 unsigned char block_buf[BLOCK];
 272 ext2_loff_t bads;
 273 ext2_loff_t gotext2_loff;
 274
 275         g_return_if_fail(start<end);
 276         g_return_if_fail(end<=src_len);
 277
 278 #ifdef DEBUG
 279         fprintf(stderr,"process([%llu,%llu])\n",(unsigned long long)start,(unsigned long long)end);
 280 #endif
 281
 282 restart:        /* continues when the block was successfuly read */
 283         stat_print();
 284         user_input(start,end);
 285
 286         stat_lastread=start;
 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);
 290                 exit(EXIT_FAILURE);
 291                 }
 292         stat_todo--;    /* for the forthcoming read() */
 293         if (!simulate_bads && sizeof(block_buf)==read(src_fd,block_buf,sizeof(block_buf))) {
 294                 /* success read */
 295                 write_dst(start,start+1,block_buf);
 296                 start++;
 297                 if (start>=end) /* finished */
 298                         return;
 299                 goto restart;
 300                 }
 301
 302         /* failed read */
 303         if (!simulate_bads)
 304                 bads=1; /* one block was detected */
 305         else {
 306                 bads=simulate_bads;
 307                 simulate_bads=0;
 308                 }
 309         if (start+bads>src_len)
 310                 bads=src_len-start;
 311         node_add_bad(start,start+bads);
 312         start+=bads;
 313         while (start<end) {
 314 ext2_loff_t mid=(start+end)/2;
 315
 316                 g_assert(mid<end);
 317                 node_add_todo(mid,end);
 318                 end=mid;
 319                 }
 320 }
 321
 322 static void range_zero(ext2_loff_t start,ext2_loff_t end)
 323 {
 324 static const unsigned char buf_zero[BUF_ZERO_BLOCKS*BLOCK];
 325
 326         g_return_if_fail(start<end);
 327
 328         while (start<end) {
 329                 ext2_loff_t mid=((end-start)>BUF_ZERO_BLOCKS ? start+BUF_ZERO_BLOCKS : end);
 330                 g_assert(mid>=start);
 331                 g_assert(mid<=end);
 332
 333                 write_dst(start,mid,buf_zero);
 334
 335                 start=mid;
 336                 }
 337 }
 338
 339 static void finish(void)
 340 {
 341 struct range *todo_linear=tree_linearize(todo_tree),*todol;
 342 struct range *bad_linear =tree_linearize(bad_tree ),*badl ;
 343
 344         linear_join(todo_linear,(GCompareFunc)range_compare_diskorder);
 345
 346         fputc('\n',stderr);
 347         for (todol=todo_linear,badl=bad_linear;
 348                         todol->start<=src_len || badl->start<=src_len;) {
 349 ext2_loff_t start,end;
 350
 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));
 362                                 todol++;
 363                                 }
 364                         else
 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));
 369                         badl++;
 370                         }
 371                 else {
 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));
 377                         todol++;
 378                         }
 379                 fflush(stdout);
 380                 range_zero(start,end);
 381                 putchar('\n');
 382                 }
 383         exit(EXIT_SUCCESS);
 384 }
 385
 386 int main(int argc,char **argv)
 387 {
 388         /* prevent block-buffering such as: badblock-guess.c|tee x.log */
 389         setlinebuf(stdout);
 390         setlinebuf(stderr);
 391
 392         if (argc!=2 && argc!=3) {
 393                 fprintf(stderr,"Syntax: badblock-guess <src_dev> [<dst_dev (OVERWRITTEN & DESTROYED!!!)>]\n");
 394                 exit(EXIT_FAILURE);
 395                 }
 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);
 398                 exit(EXIT_FAILURE);
 399                 }
 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);
 402                 exit(EXIT_FAILURE);
 403                 }
 404         if (dst_fd!=-1) {
 405 struct stat src_stat,dst_stat;
 406
 407                         if (fstat(src_fd,&src_stat)) {
 408                                 fprintf(stderr,"fstat(\"%s\"): %m\n",src_name);
 409                                 exit(EXIT_FAILURE);
 410                                 }
 411                         if (fstat(dst_fd,&dst_stat)) {
 412                                 fprintf(stderr,"fstat(\"%s\"): %m\n",dst_name);
 413                                 exit(EXIT_FAILURE);
 414                                 }
 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);
 418                                 exit(EXIT_FAILURE);
 419                                 }
 420                 }
 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);
 423                 exit(EXIT_FAILURE);
 424                 }
 425         src_len=src_lenblk;
 426         if (src_len<=0) {
 427                 fprintf(stderr,"\"%s\" length %llu <=0\n",src_name,(unsigned long long)src_len);
 428                 exit(EXIT_FAILURE);
 429                 }
 430
 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);
 436         stat_todo=src_len;
 437
 438         for (;;) {
 439 struct range *left=NULL;        /* key */
 440
 441                 g_tree_traverse(todo_tree,(GTraverseFunc)traverse_fetchleftkey,G_IN_ORDER,&left/*data*/);
 442                 if (!left)      /* done */
 443                                 break;
 444 #ifndef G_DISABLE_ASSERT
 445                 {
 446                         gint nnodes_preremove=g_tree_nnodes(todo_tree);
 447 #endif
 448                 g_tree_remove(todo_tree,left/*key*/);
 449 #ifndef G_DISABLE_ASSERT
 450                         g_assert(g_tree_nnodes(todo_tree)==nnodes_preremove-1);
 451                         }
 452 #endif
 453                 stat_largest=(left->end-left->start);
 454                 process(left->start,left->end);
 455                 g_mem_chunk_free(node_memchunk,left);
 456                 stat_todo_hunks--;
 457                 }
 458         finish();       /* finish(): G_GNUC_NORETURN */
 459         /* NOTREACHED */
 460 }