Fonctions des slices terminées, module recovery qui contient l'algo de récupération terminé aussi.

Main minimaliste pour lancer des tests à droite à gauche.
Mises au points à coup de valgrind et ddd, ça a l'air presque bien, il reste peut être un bug ou deux dans des cas à la con.

La fonction slicesFindLargest est coûteuse. On peut imaginer une version qui prends en argument :
- le max potentiellement trouvable (permet d'éliminer plein de parcours dans la majorité des cas vue l'utilisation qui est faite des slices dans le recovery. La fonction retournerai le premier slice qui correspond à cette valeur de maximum.
- un pointeur vers le slice à partir duquel commencer la recherche, qui serait le pointeur du slice trouvé la précédente fois. Permet dans le cas général de trouver vite. Il faut quand même reprendre la liste au début jusqu'à ce pointeur si on arrive à la fin de la liste sans avoir trouvé.



git-svn-id: file:///var/svn/2011-ddhardrescue/trunk@3 d3078510-dda0-49f1-841c-895ef4b7ec81

5 files changed, 235 insertions, 42 deletions

diff --git a/src/ddhardrescue.c b/src/ddhardrescue.c
index 56cc5bf..a99b9d8 100755
--- a/src/ddhardrescue.c
+++ b/src/ddhardrescue.c
@@ -6,30 +6,53 @@
 #include "recover.h"
 
 int end=0;
+unsigned long c=0;
 
 void sigHookAbrt() {
 	end=1;
 }
 
 int main() {
-	char *src, *dst, *ddOpts;
-	address_t beginSector, endSector;
-	int depth;
+	char *src, *dst, *ddOpts, *dump;
+	address_t beginSector, endSector, blockSize;
+	int /*depth,*/i;
 	slices_t *slices;
+	slice_t *curr, *toFree;
 	
 	//TODO Parse args
 	src="/dev/sdb";
 	dst="./test.img";
 	ddOpts="";
 	beginSector=0;
-	endSector=100;
-	depth=10;
-
+	endSector=19999;
+//	depth=1;
+/*
+	endSector=1999999999;
+	depth=100000;
+*/
 	//TODO signal...
 
-	slices=recover(src,dst,ddOpts,beginSector,endSector,depth);
+	slices=recover(src,dst,ddOpts,beginSector,endSector/*,depth*/);
 	
-	//TODO final reporting
+	blockSize=0;
+	dump=slicesDump(slices, &blockSize, 1000, beginSector, endSector);
+	puts(dump);
+	free(dump);
+	printf("blockSize==%ld\n", blockSize);
+	printf("c==%ld\n", c);
+	printf("slices->count==%d\n", slices->count);
+
+	curr=slices->first;
+	i=0;
+	while (curr!=NULL) {
+		i++;
+		toFree=curr;
+		curr=curr->next;
+		free(toFree);
+	}
+	free(slices);
+
+	printf("i==%d\n", i);
 
 	return 0;
 }
diff --git a/src/recover.c b/src/recover.c
index c2c2eff..0f305a1 100755
--- a/src/recover.c
+++ b/src/recover.c
@@ -1,7 +1,10 @@
 #include <errno.h>
+#include <stdio.h>
 #include "recover.h"
 
-slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector, int depth) {
+extern unsigned long c;
+
+slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector/*, int depth*/) {
 	slices_t *slices;
 	slice_t *sliceToRead;
 	address_t firstError=0, median;
@@ -16,17 +19,21 @@ slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, addr
 	slicesAppend(slices, sliceToRead);
 	
 	// Main loop 
-	while (!end && slices->count < (endSector-beginSector)/depth) {
+	while (!end) { // && slices->count < (endSector-beginSector)/depth) {
 		// try to recover sliceToRead and split it if read error
-		switch ( tryRecoverUntilError(sliceToRead, &firstError) ) {
+		switch ( tryRecoverUntilError(sliceToRead, &firstError, src, dst, ddOpts) ) {
 			case 0:
 				// slice recovery has been executed without read error
 				sliceToRead->status=S_RECOVERED;
 				break;
 			case EIO:
-				// slice recovery has encuontered a readerror
-				res=sliceSplit(sliceToRead, firstError, S_RECOVERED, S_UNREADABLE, S_UNKNOWN);
-				if (res!=0) { exit(5); } //TODO
+				// slice recovery has encountered a readerror
+				res=sliceSplit(slices, sliceToRead, firstError, S_RECOVERED, S_UNREADABLE, S_UNKNOWN);
+				if (res<1) {
+					//TODO
+					printf("sliceSplit return %d\n", res);
+					exit(5);
+				}
 				break;
 			default:
 				exit(2); //TODO
@@ -35,34 +42,84 @@ slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, addr
 		/* Now, search the largest S_UNKNOWN zone
 		 split it in two parts */
 		sliceToRead=slicesFindLargest(slices, S_UNKNOWN);
-		if ( sliceToRead == NULL ) { exit(3); } //TODO 
+		if ( sliceToRead == NULL ) {
+			// There is nothing more to recover, bailout
+			end=1;
+			continue;
+		}
+			
 
  		median=(sliceToRead->begin+sliceToRead->end)/2;
-		res=sliceSplit(sliceToRead, median, S_UNKNOWN, S_UNKNOWN, S_UNKNOWN);
-		if (res!=0) { exit(4); } //TODO
-
-		/* After splitting an S_UNKNOWN zone in two parts
-		   take the second for further analysis.
-		   We already now that this first one is just preceded by
-		   a read error, and errors are frequently grouped in zones,
-		   so trying to read a sector just after a faulty sector is
-		   most likely a waste of time.
-		*/
-		sliceToRead=sliceToRead->next; 
+		res=sliceSplit(slices, sliceToRead, median, S_UNKNOWN, S_UNKNOWN, S_UNKNOWN);
+		switch (res) {
+			case 1:
+				// No split, try analyse this zone
+				// Should be a slice of length 1
+				break;
+			case 2:
+				/* After splitting an S_UNKNOWN zone in two parts
+				   take the second for further analysis.
+				   We already now that this first one is just preceded by
+				   a read error, and errors are frequently grouped in zones,
+				   so trying to read a sector just after a faulty sector is
+				   most likely a waste of time.
+				*/
+				sliceToRead=sliceToRead->next; 
+				break;
+			case 3:
+				// Internal error of sliceSlpit because this set of parameters prevent split by 3
+				exit(5); // TODO
+				break;
+			case -1:
+				// Memory error
+				exit(4); //TODO
+				break;
+			default:
+				// API error, all necessary cases are already listed
+				exit(6); // TODO
+			}
 	}
 	return slices;
 }
 
-int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError) {
+int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError, char *src, char *dst, char*ddOpts) {
 	//TODO : implement realy that
+	char ddinvocation[256];
 	int res;
+	address_t seek, count;
+
+	c++; //XXX This is a debug counter
 
+	seek=sliceToRead->begin;
+	count=sliceToRead->end - seek + 1;
+	res=snprintf(ddinvocation, 255, "dd %s %s %s seek=%ld skip=%ld count=%ld", src, dst, ddOpts, seek, seek, count);
+	puts(ddinvocation);
+
+	// Simulate that we have systematically a read error at first sector
+	*firstError=sliceToRead->begin;
+	res=EIO;
+
+/*
+	// Simulate for each read, tha we have an error just in the middle if read for mor than one sector
 	if ( sliceToRead->begin == sliceToRead->end ) {
 		res=0;
 	} else {
 		*firstError=(sliceToRead->begin + sliceToRead->end)/2;
 		res=EIO;
 	}
+*/
+
+/*
+	// Simulate for each read a pseudo random error position and generate some cases of full read without error
+	int error=sliceToRead->begin + rand()%count;
+	if ( error % 42 == 0 ) {
+		res=0;
+	} else {
+		res=EIO;
+		*firstError=error;
+	}
+*/
+
 	return res;
 }
 
diff --git a/src/recover.h b/src/recover.h
index d8b1409..84c7286 100755
--- a/src/recover.h
+++ b/src/recover.h
@@ -5,7 +5,7 @@
 
 extern int end;
 
-slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector, int depth);
-int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError);
+slices_t *recover(char *src, char *dst, char*ddOpts, address_t beginSector, address_t endSector/*, int depth*/);
+int tryRecoverUntilError(slice_t *sliceToRead, address_t *firstError, char *src, char *dst, char*ddOpts);
 
 #endif /*RECOVER_H*/
diff --git a/src/slices.c b/src/slices.c
index edae571..8e9aee6 100755
--- a/src/slices.c
+++ b/src/slices.c
@@ -1,8 +1,12 @@
 #include <string.h>
 #include "slices.h"
 
+int min(int a, int b) { return (a<b)?a:b; }
+
 slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next) {
-	slice_t *s = malloc(1*sizeof(slice_t));
+	slice_t *s;
+
+	s = malloc(1*sizeof(slice_t));
 	if (s!=NULL) {
 		s->begin=begin;
 		s->end=end;
@@ -13,8 +17,62 @@ slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t
 	return s;
 }
 
-int sliceSplit(slice_t *slice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
-	return 1;
+// Return the numbers of slices after split (3 in the general case, 2 or 1 in particular cases. -1 is memory error)
+int sliceSplit(slices_t *slices, slice_t *initialSlice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter) {
+	slice_t *secondSlice, *thirdSlice, *rightSlice;
+	int splitAfterSingularity, splitBeforeSingularity;
+
+	/* Basically, we want to split the slice in 3 :
+	[a;b] shoud be transformed in : [a;splitAt-1], [splitAt;splitAt], [splitAt+1;b]
+	There is exceptions and singularities :
+	* If splitAt is not within [a;b], bail out, no coherent solution
+	* If splitAt==a, the first slice should not exists
+	* If splitAt==b, the last slice shoud not exists
+	* If a==b (and so, ==splitAt), there is nothing to split, just change status
+	But, if statusBefore==statusAt, we don't want an interval [splitAt;splitAt], we want just split in 2.
+	This unwanted interval should be kept merged with the first interval.
+
+	For pratical reasons with pointer mess-up, the first action is to split between the second and the last slice
+	and then between he first and second if needed.
+	*/
+
+	if ( splitAt < initialSlice->begin || splitAt > initialSlice->end ) return 2;
+	
+	// Test before act because we'll change values of the initialSlice because
+	//  it would become the firstSlice or even the second one if the first is zero-lenght
+	splitAfterSingularity=(splitAt != initialSlice->end);
+	splitBeforeSingularity=(splitAt != initialSlice->begin) && (statusBefore != statusAt);
+
+	if ( splitAfterSingularity ) {
+		thirdSlice = sliceNew(splitAt+1, initialSlice->end, statusAfter, initialSlice->next);
+		if ( thirdSlice == NULL ) return -1;
+
+		initialSlice->end = splitAt;
+		// No status change because we'll split again in 2 parts or not
+		initialSlice->next = thirdSlice;
+		if ( initialSlice == slices->last ) slices->last = thirdSlice;
+		(slices->count)++;
+
+		rightSlice=thirdSlice;
+	} else {
+		rightSlice=initialSlice->next;
+	}
+
+	if ( splitBeforeSingularity ) {
+		secondSlice = sliceNew(splitAt, splitAt, statusAt, rightSlice);
+		if ( secondSlice == NULL ) return -1;
+		
+		initialSlice->end = splitAt-1;
+		initialSlice->status=statusBefore;
+		initialSlice->next = secondSlice;
+		if ( initialSlice == slices->last ) slices->last = secondSlice;
+		(slices->count)++;
+	} else {
+		initialSlice->status=statusAt; // Two cases : a==splitAt or statusAt==statusBefore
+	}
+
+	
+	return 1 + (splitBeforeSingularity?1:0) + (splitAfterSingularity?1:0);
 }
 
 slices_t *slicesNew() {
@@ -29,25 +87,75 @@ slices_t *slicesNew() {
 }
 
 void slicesAppend(slices_t *slices, slice_t *slice) {
-
+	slice->next=NULL; //XXX Could be generalized
+	if (slices->first==NULL || slices->last==NULL) {
+		slices->first = slice;
+	} else {
+		slices->last->next=slice;
+	}
+	slices->last=slice;
+	(slices->count)++;
 }
 
 slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status) {
-	return NULL;
+	slice_t *curr, *sMax = NULL;
+	address_t i, iMax = 0;
+	
+	curr = slices->first;
+	while (curr != NULL) {
+		i=curr->end - curr->begin + 1;
+		if ( curr->status == status && i > iMax ) {
+			iMax = i;
+			sMax = curr;
+		}
+		curr=curr->next;
+	}
+	return sMax;
 }
 
-char *slicesDump(slices_t *slices, int charCount, address_t begin, address_t end) {
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end) {
 	slice_t *curr = slices->first;
-	address_t sb,se, blockSize=(end-begin)/(charCount+1);
-	char *dump=malloc(1*charCount+1);
+	unsigned int sb,se,i;
+	char *dump, ci;
+
+	// If blockSize is 0, try to autodetect to display entire slice chain
+	if (*blockSize == 0) {
+		*blockSize=(end-begin+1)/(charCount+1);
+		// If we have a too big zoom factor, draw it at 1:1 scale
+		if (*blockSize==0) *blockSize=1;
+	}
+
+	dump = malloc(charCount+1);
+	if (dump==NULL) { return NULL; }
 	memset(dump, ' ', charCount);
+	dump[charCount]=0;
 
 	while (curr != NULL) {
-		sb=curr->begin;
-		// TODO : boucle pour dessiner les caractères correspondant selon le type de zone. Attention aux cas ou 1 caractère contient la frontière de plusieurs zones (ne pas toujours écraser avec la dernière valeur)
+		sb=curr->begin / *blockSize; //FIXME : gérer le max également !
+		se=min(curr->end / *blockSize,charCount-1);
+
+		switch (curr->status) {
+			case S_UNKNOWN:		ci='_'; break;
+			case S_UNREADABLE:	ci='!'; break;
+			case S_RECOVERED:	ci='.'; break;
+			default:		ci='~'; break;
+		}
+
+		for (i=sb;i<=se;i++) {
+			if (dump[i] == ' ' ) {
+				// This is a new information
+				dump[i]=ci;
+			} else if ( dump[i] == ci || dump[i] == '!' ) {
+				// Already the right information or error, don't modify
+			} else {
+				// Multiple information on the same character
+				dump[i]='#';
+			}
+		}
 
 		curr=curr->next;
 	}
 
 	return dump;
 }
+
diff --git a/src/slices.h b/src/slices.h
index 062c4f4..9f97246 100755
--- a/src/slices.h
+++ b/src/slices.h
@@ -4,8 +4,13 @@
 #include <stdint.h>
 #include <stdlib.h>
 
+/* IMPORTANT NOTES
+Slice are inclusive intervals. Let say sliceNew(1,2,S_UNKNOWN,NULL) return a [1;2] interval,
+ so interval lenght is end-begin+1. Here, it is 2 sectors lenght slice.
+*/
+
 typedef enum { S_UNKNOWN, S_RECOVERED, S_UNREADABLE } sliceStatus_t;
-typedef uint32_t address_t;
+typedef unsigned long int address_t;
 
 typedef struct _slice {
 	uint32_t begin, end;
@@ -19,11 +24,11 @@ typedef struct {
 } slices_t;
 
 slice_t *sliceNew(address_t begin, address_t end, sliceStatus_t status, slice_t *next);
-int sliceSplit(slice_t *slice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter); 
+int sliceSplit(slices_t *slices, slice_t *initialSlice, address_t splitAt, sliceStatus_t statusBefore, sliceStatus_t statusAt, sliceStatus_t statusAfter);
 
 slices_t *slicesNew();
 void slicesAppend(slices_t *slices, slice_t *slice);
 slice_t *slicesFindLargest(slices_t *slices, sliceStatus_t status);
-char *slicesDump(slices_t *slices, int charCount, address_t begin, address_t end);
+char *slicesDump(slices_t *slices, address_t *blockSize, unsigned int charCount, address_t begin, address_t end);
 
 #endif /*SLICES_H*/