Skip site navigation (1)Skip section navigation (2)
Date:      Fri, 01 Jun 2012 16:29:59 +0000
From:      gpf@FreeBSD.org
To:        svn-soc-all@FreeBSD.org
Subject:   socsvn commit: r236881 - soc2012/gpf/misc
Message-ID:  <20120601162959.AE0B5106566B@hub.freebsd.org>

next in thread | raw e-mail | index | archive | help
Author: gpf
Date: Fri Jun  1 16:29:59 2012
New Revision: 236881
URL: http://svnweb.FreeBSD.org/socsvn/?view=rev&rev=236881

Log:
  new version of test_checksum.c for the new version of .pefs.checksum that is created
  with cuckoo hashing.
  

Modified:
  soc2012/gpf/misc/test_checksum.c

Modified: soc2012/gpf/misc/test_checksum.c
==============================================================================
--- soc2012/gpf/misc/test_checksum.c	Fri Jun  1 15:52:41 2012	(r236880)
+++ soc2012/gpf/misc/test_checksum.c	Fri Jun  1 16:29:59 2012	(r236881)
@@ -24,7 +24,7 @@
  * SUCH DAMAGE.
  *
  */
- 
+
 #include <sys/cdefs.h>
 __FBSDID("$FreeBSD$");
 
@@ -84,57 +84,40 @@
 };
 
 struct bucket {
-	struct file_header_head file_headers;
-	uint32_t offset_to_chain;
-	uint32_t nelements;
-	uint32_t elements_loaded;
+	struct file_header *fhp;
 };
 
-struct hash_table {
-	struct bucket *buckets;
-	uint32_t size; /* how many buckets */
+struct cuckoo_hash_table {
+	struct bucket *buckets1;
+	struct bucket *buckets2;
+	uint32_t size; /* how many buckets in each table */
 	uint32_t nelements;
 };
 
-
 static int
-pefs_allocate_hash_table(struct hash_table *checksum_hash_tablep, uint32_t size)
+pefs_allocate_hash_table(struct cuckoo_hash_table *chtp, uint32_t size)
 {
 	uint32_t i;
 
-	checksum_hash_tablep->size = size;
-	checksum_hash_tablep->buckets = malloc (size * sizeof(struct bucket));
-
-	if (checksum_hash_tablep->buckets == NULL) {
+	chtp->size = size;
+	chtp->buckets1 = malloc (size * sizeof(struct bucket));
+	if (chtp->buckets1 == NULL) {
 		perror("memory allocation error");
 		return (ERROR);
 	}
 
-	for (i = 0; i < checksum_hash_tablep->size; i++) {
-		checksum_hash_tablep->buckets[i].nelements = 0;
-		checksum_hash_tablep->buckets[i].elements_loaded = 0;
-		LIST_INIT(&(checksum_hash_tablep->buckets[i].file_headers));
+	chtp->buckets2 = malloc (size * sizeof(struct bucket));
+	if (chtp->buckets2 == NULL) {
+		perror("memory allocation error");
+		return (ERROR);
 	}
 
-	return (0);
-}
-
-static void
-pefs_add_to_bucket(struct bucket *bucketp, struct file_header *fhp)
-{
-	struct file_header *elementp;
-	struct file_header *last;
-
-	if (bucketp->elements_loaded == 0)
-		LIST_INSERT_HEAD(&(bucketp->file_headers), fhp, bucket_entries);
-	else {
-		LIST_FOREACH(elementp, &(bucketp->file_headers), bucket_entries) {
-			last = elementp;
-		}
-		LIST_INSERT_AFTER(last, fhp, bucket_entries);
+	for (i = 0; i < chtp->size; i++) {
+		chtp->buckets1[i].fhp = NULL;
+		chtp->buckets2[i].fhp = NULL;
 	}
 
-	bucketp->elements_loaded++;
+	return (0);
 }
 
 static void
@@ -143,24 +126,41 @@
 	TAILQ_INSERT_TAIL(&(fhp->checksums), csp, checksum_entries);
 }
 
-/* for debugging purposes */
 static void
-pefs_print_hash_table(struct hash_table *checksum_hash_tablep, uint8_t hash_len)
+pefs_print_hash_table(struct cuckoo_hash_table *chtp, uint8_t hash_len)
 {
 	struct file_header *fhp;
 	struct checksum *csp;
 	uint32_t i,j;
 
-	printf("\n+++Printing Hash Table+++\n\n");
-	for (i = 0; i < checksum_hash_tablep->size; i++) {
-		printf("\nbucket %d with elements: %u\n", i, checksum_hash_tablep->buckets[i].nelements);
-		LIST_FOREACH(fhp, &(checksum_hash_tablep->buckets[i].file_headers), bucket_entries) {
-			printf("\tid = %llu!\tnhashes = %d\n", fhp->file_id, fhp->nhashes);
+	dprintf(("\n+++Printing Hash Table 1+++\n\n"));
+	for (i = 0; i < chtp->size; i++) {
+		fhp = chtp->buckets1[i].fhp;
+		dprintf(("\nbucket %d with element: %d\n", i, fhp == NULL ? 0 : 1));
+		if (fhp != NULL) {
+			//dprintf(("\tpath=%s\tid = %llu\tnhashes = %d\n", fhp->path, fhp->file_id, fhp->nhashes));
+			dprintf(("\tid = %llu\tnhashes = %d\n", fhp->file_id, fhp->nhashes));
+			TAILQ_FOREACH(csp, &(fhp->checksums), checksum_entries) {
+				dprintf(("\t\tdigest="));
+				for (j = 0; j < hash_len; j++)
+					dprintf(("%02x", csp->hash[j]));
+				dprintf(("\n"));
+			}
+		}
+	}
+
+	dprintf(("\n+++Printing Hash Table 2+++\n\n"));
+	for (i = 0; i < chtp->size; i++) {
+		fhp = chtp->buckets2[i].fhp;
+		dprintf(("\nbucket %d with element: %d\n", i, fhp == NULL ? 0 : 1));
+		if (fhp != NULL) {
+			//dprintf(("\tpath=%s\tid = %llu\tnhashes = %d\n", fhp->path, fhp->file_id, fhp->nhashes));
+			dprintf(("\tid = %llu\tnhashes = %d\n", fhp->file_id, fhp->nhashes));
 			TAILQ_FOREACH(csp, &(fhp->checksums), checksum_entries) {
-				printf("\t\tdigest=");
+				dprintf(("\t\tdigest="));
 				for (j = 0; j < hash_len; j++)
-					printf("%02x", csp->hash[j]);
-				printf("\n");
+					dprintf(("%02x", csp->hash[j]));
+				dprintf(("\n"));
 			}
 		}
 	}
@@ -216,70 +216,68 @@
 }
 
 static int
-pefs_read_bucket(int fdin, struct bucket *bp, uint32_t *buckets_offset)
-{
-	uint32_t offset_to_chain, nelements;
-	int bytes;
-
-	//dprintf(("bucket offset = %d\n", *buckets_offset));
-
-	bytes = pread(fdin, &offset_to_chain, sizeof(offset_to_chain), *buckets_offset);
-	if (bytes != sizeof(offset_to_chain)) {
-		perror("error reading from .pefs.checksum");
-		return (ERROR);
-	}
-	bp->offset_to_chain = le32toh(offset_to_chain);
-	(*buckets_offset)+= sizeof(offset_to_chain);
-
-	bytes = pread(fdin, &nelements, sizeof(nelements), *buckets_offset);
-	if (bytes != sizeof(nelements)) {
-		perror("error reading from .pefs.checksum");
-		return (ERROR);
-	}
-	bp->nelements = le32toh(nelements);
-	(*buckets_offset)+= sizeof(nelements);
-
-	//dprintf(("\n++priting bucket info++\n"));
-	//dprintf(("offset to chain %d\nnelements %d\n", bp->offset_to_chain, bp->nelements));
-
-	return (0);
-}
-
-static int
-pefs_read_file_header(int fdin, struct file_header *fhp, uint32_t *fh_offset)
+pefs_read_file_header(int fdin, struct file_header *fhp, uint32_t *buckets_offset)
 {
 	uint64_t file_id;
 	uint32_t nhashes, offset_to_checksums;
 	int bytes;
 
-	bytes = pread(fdin, &nhashes, sizeof(nhashes), *fh_offset);
+	bytes = pread(fdin, &nhashes, sizeof(nhashes), *buckets_offset);
 	if (bytes != sizeof(nhashes)) {
 		perror("error reading from .pefs.checksum");
 		return (ERROR);
 	}
 	fhp->nhashes = le32toh(nhashes);
-	(*fh_offset)+= sizeof(nhashes);
+	(*buckets_offset)+= sizeof(nhashes);
 
-	bytes = pread(fdin, &offset_to_checksums, sizeof(offset_to_checksums), *fh_offset);
+	bytes = pread(fdin, &offset_to_checksums, sizeof(offset_to_checksums), *buckets_offset);
 	if (bytes != sizeof(offset_to_checksums)) {
 		perror("error reading from .pefs.checksum");
 		return (ERROR);
 	}
 	fhp->offset_to_checksums = le32toh(offset_to_checksums);
-	(*fh_offset)+= sizeof(offset_to_checksums);
-	
-	bytes = pread(fdin, &file_id, sizeof(file_id), *fh_offset);
+	(*buckets_offset)+= sizeof(offset_to_checksums);
+
+	bytes = pread(fdin, &file_id, sizeof(file_id), *buckets_offset);
 	if (bytes != sizeof(file_id)) {
 		perror("error reading from .pefs.checksum");
 		return (ERROR);
 	}
 	fhp->file_id = le64toh(file_id);
-	(*fh_offset)+= sizeof(file_id);
-	
+	(*buckets_offset)+= sizeof(file_id);
+
 	//dprintf(("\nfile header offset = %d\n", *fh_offset));
 	//dprintf(("\n++priting file header info++\n"));
-	//dprintf(("nhashes %d\noffset_to_checksums %d\n", fhp->nhashes, fhp->offset_to_checksums));
-	//dprintf(("file id %d\n", (int)fhp->file_id));
+	//dprintf(("nhashes %d\noffset_to_checksums %u\n", fhp->nhashes, fhp->offset_to_checksums));
+	//dprintf(("file id %llu\n", fhp->file_id));
+
+	return (0);
+}
+
+static int
+pefs_read_bucket(int fdin, struct bucket *bp, uint32_t *buckets_offset)
+{
+	struct file_header *fhp;
+	int error;
+
+	//dprintf(("bucket offset = %d\n", *buckets_offset));
+	fhp = malloc(sizeof(struct file_header));
+	if (fhp == NULL) {
+		perror("malloc");
+		return (ERROR);
+	}
+
+	error = pefs_read_file_header(fdin, fhp, buckets_offset);
+	if (error != 0)
+		return (error);
+
+	if (fhp->nhashes == 0) {
+		free(fhp);
+		fhp = NULL;
+	}
+	bp->fhp = fhp;
+
+	//dprintf(("\n++priting bucket info++\n"));
 
 	return (0);
 }
@@ -295,7 +293,7 @@
 		return (ERROR);
 	}
 	(*hashes_offset)+= hash_len;
-	
+
 	//dprintf(("hashes offset = %d\n", *hashes_offset));
 	//dprintf(("hash %s\n", csp->hash));
 
@@ -303,12 +301,12 @@
 }
 
 static int
-pefs_read_checksum_file(int fdin, struct checksum_file_header *cfhp, struct hash_table *chtp)
+pefs_read_checksum_file(int fdin, struct checksum_file_header *cfhp, struct cuckoo_hash_table *chtp)
 {
 	struct bucket *bp;
 	struct checksum *csp;
 	struct file_header *fhp;
-	uint32_t i, j, k, buckets_offset, fh_offset, hashes_offset;
+	uint32_t i, k, buckets_offset, hashes_offset;
 	int error;
 
 	error = pefs_read_checksum_file_header(fdin, cfhp);
@@ -323,27 +321,47 @@
 	buckets_offset = cfhp->offset_to_hash_table;
 
 	for (i = 0; i < chtp->size; i++) {
-		bp = &chtp->buckets[i];
+		bp = &chtp->buckets1[i];
 		error = pefs_read_bucket(fdin, bp, &buckets_offset);
 		if (error != 0)
 			return (error);
 
-		fh_offset = bp->offset_to_chain;
+		fhp = bp->fhp;
+		if (fhp != NULL) {
+			TAILQ_INIT(&(fhp->checksums));
+			hashes_offset = fhp->offset_to_checksums;
+
+			for (k = 0; k < fhp->nhashes; k++) {
+				csp = malloc(sizeof(struct checksum));
+				if (csp == NULL) {
+					perror("malloc");
+					return (ERROR);
+				}
+				csp->hash = malloc(cfhp->hash_len);
+				if (csp->hash == NULL) {
+					perror("malloc");
+					return (ERROR);
+				}
 
-		for (j = 0; j < bp->nelements; j++) {
-			fhp = malloc(sizeof(struct file_header));
-			if (fhp == NULL) {
-				perror("malloc");
-				return (ERROR);
+				error = pefs_read_hash(fdin, csp, &hashes_offset, cfhp->hash_len);
+				if (error != 0)
+					return (error);
+
+				pefs_add_to_file_header(fhp, csp);
 			}
+		}
+	}
 
-			error = pefs_read_file_header(fdin, fhp, &fh_offset);
-			if (error != 0)
-				return (ERROR);
+	for (i = 0; i < chtp->size; i++) {
+		bp = &chtp->buckets2[i];
+		error = pefs_read_bucket(fdin, bp, &buckets_offset);
+		if (error != 0)
+			return (error);
 
+		fhp = bp->fhp;
+		if (fhp != NULL) {
 			TAILQ_INIT(&(fhp->checksums));
 			hashes_offset = fhp->offset_to_checksums;
-			pefs_add_to_bucket(bp, fhp);
 
 			for (k = 0; k < fhp->nhashes; k++) {
 				csp = malloc(sizeof(struct checksum));
@@ -360,7 +378,7 @@
 				error = pefs_read_hash(fdin, csp, &hashes_offset, cfhp->hash_len);
 				if (error != 0)
 					return (error);
-				
+
 				pefs_add_to_file_header(fhp, csp);
 			}
 		}
@@ -377,15 +395,14 @@
 
 /*
  * XXXgpf: Purpose of code is to test validity of a .pefs.checksum file.
- * Output from this program's pefs_print_hash_table() is checked against 
+ * Output from this program's pefs_print_hash_table() is checked against
  * output from sbin/pefs' pefs_print_hash_table(). They should match.
- * 
  */
 int
 main(int argc, char *argv[])
 {
 	char checksum_path[MAXPATHLEN];
-	struct hash_table checksum_hash_table;
+	struct cuckoo_hash_table checksum_hash_table;
 	struct checksum_file_header cfh;
 	int error, fdin;
 
@@ -404,7 +421,8 @@
 	error = pefs_read_checksum_file(fdin, &cfh, &checksum_hash_table);
 
 	/* this output should be the same as the one from sbin/pefs */
-	pefs_print_hash_table(&checksum_hash_table, cfh.hash_len);
+	if (error == 0)
+		pefs_print_hash_table(&checksum_hash_table, cfh.hash_len);
 
 	close(fdin);
 



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20120601162959.AE0B5106566B>