From a5691b6c368c0bf21c558eeacb7c233d7e6272ef Mon Sep 17 00:00:00 2001 From: short <> Date: Fri, 2 Aug 2002 20:47:49 +0000 Subject: [PATCH] Initial commit --- Makefile | 6 + badblock-guess.c | 460 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 466 insertions(+) create mode 100644 Makefile create mode 100644 badblock-guess.c diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..87f0664 --- /dev/null +++ b/Makefile @@ -0,0 +1,6 @@ +# $Id$ + +all: badblock-guess + +badblock-guess: badblock-guess.c + gcc -s -O2 -Wall -static `glib-config --cflags glib` -o $@ $< `glib-config --libs glib` -lext2fs diff --git a/badblock-guess.c b/badblock-guess.c new file mode 100644 index 0000000..56ed478 --- /dev/null +++ b/badblock-guess.c @@ -0,0 +1,460 @@ +/* $Id$ */ + + +#define _LARGEFILE_SOURCE +#define _LARGEFILE64_SOURCE + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +/* configuation */ + +#define BUF_ZERO_BLOCKS 0x100 /* *BLOCK, =128KB, in BSS section */ +#define xDEBUG 1 + + +/* implementation */ + +#ifndef O_BINARY +#define O_BINARY 0 +#endif +#ifndef LINE_MAX +#define LINE_MAX 0x1000 +#endif + +#define BLOCK (0x200) /* 512 */ + +static void finish(void) G_GNUC_NORETURN; + +static int src_fd=-1,dst_fd=-1; +static const char *src_name,*dst_name; +static ext2_loff_t src_len; /* in blocks! */ +static blk_t src_lenblk; /* ==src_len, just a different type */ + +static ext2_loff_t stat_lastread,stat_todo,stat_bads,stat_largest,stat_todo_hunks; + +struct range { + ext2_loff_t start,end; + }; +static GTree *todo_tree; /* struct range *key, NULL value */ +static GTree *bad_tree; /* struct range *key, NULL value */ +static GMemChunk *node_memchunk; /* struct range */ + +static gint tree_linearize_traverse(struct range *key,gpointer value/*unused*/,struct range **r_fillp/*data*/) +{ + *(*r_fillp)++=*key; + g_mem_chunk_free(node_memchunk,key); + return FALSE; +} + +/* mallocated result, data-terminated, input "tree" destroyed */ +static struct range *tree_linearize(GTree *tree) +{ +struct range *r=g_new(struct range,g_tree_nnodes(tree)+1); +struct range *r_fill=r; + + g_tree_traverse(tree,(GTraverseFunc)tree_linearize_traverse,G_IN_ORDER,&r_fill/*data*/); + g_assert(r_fill==r+g_tree_nnodes(tree)); + r_fill->start=r_fill->end=src_len+1; /* terminator */ + g_tree_destroy(tree); + return r; +} + +/* returns terminator! */ +static struct range *linear_join(struct range *linear,GCompareFunc comparefunc) +{ +struct range *linear_term,*dst,*src; + + for (linear_term=linear;linear_term->start<=src_len;linear_term++); + qsort(linear,linear_term-linear,sizeof(*linear),(int (*)(const void *, const void *))comparefunc); + for (dst=src=linear;src->start<=src_len;src++) { + if (dst>linear && dst[-1].end==src->start) + dst[-1].end=src->end; + else + *dst++=*src; + } + *dst=*src; /* terminator */ + return dst; +} + +static gint range_compare(const struct range *range1,const struct range *range2) +{ +ext2_loff_t len1,len2; +int r; + + g_return_val_if_fail(range1->end>range1->start,0); + g_return_val_if_fail(range2->end>range2->start,0); + + len1=range1->end-range1->start; + len2=range2->end-range2->start; + + /* big..small (start with large blocks) */ + if ((r=(len2 > len1) - (len2 < len1))) + return r; + /* big..small (reversed processing order) */ + if ((r=(range2->start > range1->start) - (range2->start < range1->start))) + return r; + return 0; +} + +static gint range_compare_diskorder(const struct range *range1,const struct range *range2) +{ +int r; + + g_return_val_if_fail(range1->end>range1->start,0); + g_return_val_if_fail(range2->end>range2->start,0); + + /* small..big (linear disk processing order) */ + if ((r=(range2->start < range1->start) - (range2->start > range1->start))) + return r; + /* small..big (shouldn't have effect, just to get valid compare for ==) */ + if ((r=(range2->end < range1->end ) - (range2->end > range1->end ))) + return r; + return 0; +} + +static struct range *node_build(ext2_loff_t start,ext2_loff_t end) +{ +struct range *r=g_mem_chunk_alloc(node_memchunk); + + r->start=start; + r->end=end; + return r; +} + +static gint search_end(struct range *key,ext2_loff_t *endp/*data*/) +{ +int r; + + if ((r=(*endp < key->end) - (*endp > key->end))) + return r; + return 0; +} + +static gint search_start(struct range *key,ext2_loff_t *startp/*data*/) +{ +int r; + + if ((r=(*startp < key->start) - (*startp > key->start))) + return r; + return 0; +} + +static void node_add_bad(ext2_loff_t start,ext2_loff_t end) +{ +struct range *key,*neigh_left,*neigh_right; + + if (start>=end) + return; + key=node_build(start,end); + if ((neigh_left =g_tree_search(bad_tree,(GSearchFunc)search_end ,&start))) { + g_assert(neigh_left->end==key->start); + key->start=neigh_left->start; + g_tree_remove(bad_tree,neigh_left); + g_mem_chunk_free(node_memchunk,neigh_left); + } + if ((neigh_right=g_tree_search(bad_tree,(GSearchFunc)search_start,&end ))) { + g_assert(neigh_right->start==key->end); + key->end=neigh_right->end; + g_tree_remove(bad_tree,neigh_right); + g_mem_chunk_free(node_memchunk,neigh_right); + } + g_tree_insert(bad_tree,key/*key*/,NULL/*value*/); + stat_bads+=(end-start); +} + +static void node_add_todo(ext2_loff_t start,ext2_loff_t end) +{ + if (start>=end) + return; + g_tree_insert(todo_tree,node_build(start,end)/*key*/,NULL/*value*/); + stat_todo_hunks++; +} + +static gint traverse_fetchleftkey(gpointer key,gpointer value/*unused*/,gpointer *keyp/*data*/) +{ + *keyp=key; + return TRUE; +} + +static time_t stat_timelast; + +static void stat_print(void) +{ +time_t now; + + if (stat_timelast==(now=time(NULL))) + return; + stat_timelast=now; + fprintf(stderr,"@%llu/%llu,TODO=%llu,bad=%llu,largest=%llu,hunks=%llu %10s\r", + (unsigned long long)stat_lastread, + (unsigned long long)src_len, + (unsigned long long)stat_todo, + (unsigned long long)stat_bads, + (unsigned long long)stat_largest, + (unsigned long long)stat_todo_hunks, + ""); + fflush(stderr); +} + +static ext2_loff_t simulate_bads=0; + +static void user_input(ext2_loff_t pending_start,ext2_loff_t pending_end) +{ +fd_set rfds; +struct timeval tv; +char buf[LINE_MAX]; + + FD_ZERO(&rfds); + FD_SET(0,&rfds); + tv.tv_sec=0; + tv.tv_usec=0; + if (select(1,&rfds,NULL,NULL,&tv)<=0) + return; + if (buf!=fgets(buf,sizeof(buf),stdin)) { + fprintf(stderr,"Weird stdin in user_input, assumed line \"f\"\n"); + strcpy(buf,"f"); + } + stat_timelast=0; /* reprint statistics line immeadiately */ + switch (*buf) { + case 'f': + node_add_todo(pending_start,pending_end); + finish(); /* finish(): G_GNUC_NORETURN */ + /* NOTREACHED */ + case 'b': { +int bads=atoi(buf+1); + + simulate_bads+=(bads>=1 ? bads : 1); + } break; + default: + fprintf(stderr,"Unrecognized key '%c': 'f'=finish(), 'b[]'=simulate bads\n", + (isprint(*buf) ? *buf : '?')); + } +} + +static void write_dst(ext2_loff_t start,ext2_loff_t end,const void *buf) +{ +size_t len=(end-start)*BLOCK; +ssize_t gotssize; +ext2_loff_t gotext2_loff; + + if (dst_fd==-1) + return; + if (start*BLOCK!=(gotext2_loff=ext2fs_llseek(dst_fd,start*BLOCK,SEEK_SET))) { + fprintf(stderr,"ext2fs_llseek(\"%s\",%llu)=%lld: %m\n",dst_name,(unsigned long long)(start*BLOCK), + (signed long long)gotext2_loff); + exit(EXIT_FAILURE); + } + if (len!=(gotssize=write(dst_fd,buf,len))) { + fprintf(stderr,"write(\"%s\",@%llu-@%llu=%llu=%lluB)=%lld: %m\n",dst_name, + (unsigned long long)start, + (unsigned long long)end, + (unsigned long long)(end-start), + (unsigned long long)((end-start)*BLOCK), + ( signed long long)gotssize); + exit(EXIT_FAILURE); + } +} + +static void process(ext2_loff_t start,ext2_loff_t end) +{ +unsigned char block_buf[BLOCK]; +ext2_loff_t bads; +ext2_loff_t gotext2_loff; + + g_return_if_fail(start=end) /* finished */ + return; + goto restart; + } + + /* failed read */ + if (!simulate_bads) + bads=1; /* one block was detected */ + else { + bads=simulate_bads; + simulate_bads=0; + } + if (start+bads>src_len) + bads=src_len-start; + node_add_bad(start,start+bads); + start+=bads; + while (startBUF_ZERO_BLOCKS ? start+BUF_ZERO_BLOCKS : end); + g_assert(mid>=start); + g_assert(mid<=end); + + write_dst(start,mid,buf_zero); + + start=mid; + } +} + +static void finish(void) +{ +struct range *todo_linear=tree_linearize(todo_tree),*todol; +struct range *bad_linear =tree_linearize(bad_tree ),*badl ; + + linear_join(todo_linear,(GCompareFunc)range_compare_diskorder); + + fputc('\n',stderr); + for (todol=todo_linear,badl=bad_linear; + todol->start<=src_len || badl->start<=src_len;) { +ext2_loff_t start,end; + + g_assert(badl->start!=todol->start); + if (badl->startstart) { + g_assert(todol->start>=badl->end); + if (todol->start==badl->end) { + printf("%llu-%llu\t;BAD=%llu, TODO(@%llu-@%llu)=%llu", + (unsigned long long)(start=badl->start), + (unsigned long long)(end=todol->end), + (unsigned long long)(badl->end-badl->start), + (unsigned long long)todol->start, + (unsigned long long)todol->end, + (unsigned long long)(todol->end-todol->start)); + todol++; + } + else + printf("%llu-%llu\t;BAD=%llu", + (unsigned long long)(start=badl->start), + (unsigned long long)(end=badl->end), + (unsigned long long)(badl->end-badl->start)); + badl++; + } + else { + g_assert(badl->start>todol->start); + printf("%llu-%llu\t;TODO=%llu", + (unsigned long long)(start=todol->start), + (unsigned long long)(end=todol->end), + (unsigned long long)(todol->end-todol->start)); + todol++; + } + fflush(stdout); + range_zero(start,end); + putchar('\n'); + } + exit(EXIT_SUCCESS); +} + +int main(int argc,char **argv) +{ + /* prevent block-buffering such as: badblock-guess.c|tee x.log */ + setlinebuf(stdout); + setlinebuf(stderr); + + if (argc!=2 && argc!=3) { + fprintf(stderr,"Syntax: badblock-guess []\n"); + exit(EXIT_FAILURE); + } + if (-1==(src_fd=open64((src_name=argv[1]),O_RDONLY|O_BINARY))) { + fprintf(stderr,"open64(\"%s\",O_RDONLY|O_BINARY): %m\n",src_name); + exit(EXIT_FAILURE); + } + if (argv[2] && -1==(dst_fd=open64((dst_name=argv[2]),O_WRONLY|O_BINARY))) { + fprintf(stderr,"open64(\"%s\",O_WRONLY|O_BINARY): %m\n",dst_name); + exit(EXIT_FAILURE); + } + if (dst_fd!=-1) { +struct stat src_stat,dst_stat; + + if (fstat(src_fd,&src_stat)) { + fprintf(stderr,"fstat(\"%s\"): %m\n",src_name); + exit(EXIT_FAILURE); + } + if (fstat(dst_fd,&dst_stat)) { + fprintf(stderr,"fstat(\"%s\"): %m\n",dst_name); + exit(EXIT_FAILURE); + } + if ((S_ISBLK(src_stat.st_mode) && S_ISBLK(dst_stat.st_mode) && src_stat.st_rdev==dst_stat.st_rdev) + || (src_stat.st_dev==dst_stat.st_dev && src_stat.st_ino==dst_stat.st_ino)) { + fprintf(stderr,"Refusing to operate on two identical devs (src=\"%s\" and dst=\"%s\")\n",src_name,dst_name); + exit(EXIT_FAILURE); + } + } + if (ext2fs_get_device_size(src_name,BLOCK,&src_lenblk)) { + fprintf(stderr,"ext2fs_get_device_size(\"%s\",%d,...): %m\n",src_name,BLOCK); + exit(EXIT_FAILURE); + } + src_len=src_lenblk; + if (src_len<=0) { + fprintf(stderr,"\"%s\" length %llu <=0\n",src_name,(unsigned long long)src_len); + exit(EXIT_FAILURE); + } + + node_memchunk=g_mem_chunk_new("node_memchunk",sizeof(struct range)/*atom_size*/, + 0x1000 /*are_size: 64KB*/,G_ALLOC_AND_FREE); + todo_tree=g_tree_new((GCompareFunc)range_compare); + bad_tree=g_tree_new((GCompareFunc)range_compare_diskorder); + node_add_todo(0,src_len); + stat_todo=src_len; + + for (;;) { +struct range *left=NULL; /* key */ + + g_tree_traverse(todo_tree,(GTraverseFunc)traverse_fetchleftkey,G_IN_ORDER,&left/*data*/); + if (!left) /* done */ + break; +#ifndef G_DISABLE_ASSERT + { + gint nnodes_preremove=g_tree_nnodes(todo_tree); +#endif + g_tree_remove(todo_tree,left/*key*/); +#ifndef G_DISABLE_ASSERT + g_assert(g_tree_nnodes(todo_tree)==nnodes_preremove-1); + } +#endif + stat_largest=(left->end-left->start); + process(left->start,left->end); + g_mem_chunk_free(node_memchunk,left); + stat_todo_hunks--; + } + finish(); /* finish(): G_GNUC_NORETURN */ + /* NOTREACHED */ +} -- 1.8.3.1