From owner-svn-soc-all@FreeBSD.ORG Fri Jun 1 16:30:00 2012 Return-Path: Delivered-To: svn-soc-all@FreeBSD.org Received: from socsvn.FreeBSD.org (unknown [IPv6:2001:4f8:fff6::2f]) by hub.freebsd.org (Postfix) with SMTP id AE0B5106566B for ; Fri, 1 Jun 2012 16:29:59 +0000 (UTC) (envelope-from gpf@FreeBSD.org) Received: by socsvn.FreeBSD.org (sSMTP sendmail emulation); Fri, 01 Jun 2012 16:29:59 +0000 Date: Fri, 01 Jun 2012 16:29:59 +0000 From: gpf@FreeBSD.org To: svn-soc-all@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Message-Id: <20120601162959.AE0B5106566B@hub.freebsd.org> Cc: Subject: socsvn commit: r236881 - soc2012/gpf/misc X-BeenThere: svn-soc-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for the entire Summer of Code repository List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 01 Jun 2012 16:30:00 -0000 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 __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);