[netfilter-cvslog] r6556 - trunk/hashtrie
gandalf at netfilter.org
gandalf at netfilter.org
Wed Mar 22 21:13:11 CET 2006
Author: gandalf at netfilter.org
Date: 2006-03-22 21:13:10 +0100 (Wed, 22 Mar 2006)
New Revision: 6556
Modified:
trunk/hashtrie/newtable.c
trunk/hashtrie/newtable.h
trunk/hashtrie/newtest.c
Log:
Add debug_hashtrie() which iterates through the trie and gathers some simple statistics for each level (depth).
Then it prints out a small summary for each level (depth). Number of entries, buckets, and how many of those buckets that are "not full", "just full" or "overfull" and thus triggering expansion. The percentage of usage is also printed out for all the buckets in the whole level (depth) and for each bucket status.
Modified: trunk/hashtrie/newtable.c
===================================================================
--- trunk/hashtrie/newtable.c 2006-03-19 23:28:29 UTC (rev 6555)
+++ trunk/hashtrie/newtable.c 2006-03-22 20:13:10 UTC (rev 6556)
@@ -367,4 +367,103 @@
return 1;
}
+void debug_hashtrie(struct hashtrie_info *info)
+{
+ struct hashentry *curtable = info->hashtrie, *bucket;
+ struct hashentry_stack stack[MAXDEPTH];
+ struct hashtrie_debug debug[MAXDEPTH];
+ u8 depth = 0;
+ unsigned int slotnr, bucketnr = 0;
+ unsigned int numentries;
+ int i;
+ for (i = 0; i < MAXDEPTH; i++) {
+ debug[i].numchildren = 0;
+ debug[i].numbuckets = 0;
+ debug[i].numentries = 0;
+ debug[i].nfbuckets = 0;
+ }
+
+ for (;;) {
+ stack[depth].bucket = curtable;
+ stack[depth].bucketnr = bucketnr;
+ printd("Current depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr);
+
+ bucket = &curtable[bucketnr];
+
+ if (bucket->child) {
+ debug[depth].numchildren++;
+ depth++;
+ bucketnr = 0;
+ curtable = bucket->child;
+ printd("Following child to depth: %u table: %p bucketnr: %u\n", depth, curtable, bucketnr);
+ continue;
+ }
+
+ debug[depth].numbuckets++;
+
+ numentries = 0;
+ for (slotnr = !depth; slotnr < NUMENTRY; slotnr++) {
+ if (!bucket->data.members[slotnr])
+ continue;
+
+ numentries++;
+ delete(info, bucket->data.members[slotnr]);
+ }
+ debug[depth].numentries += numentries;
+
+ if (numentries != NUMENTRY - !depth) {
+ debug[depth].nfbuckets++;
+ }
+
+ bucketnr++;
+ if (bucketnr >= HASHNUM) {
+ if (depth == 0)
+ break;
+ depth--;
+ curtable = stack[depth].bucket;
+ bucketnr = stack[depth].bucketnr;
+
+
+ free(curtable[bucketnr].child);
+ curtable[bucketnr].child = NULL;
+ info->numchildren--;
+ //bucketcode_leave
+ }
+ }
+
+ printf("ip_conntrack_hash_rnd - %u\n", ip_conntrack_hash_rnd);
+
+ printf("Statistics:\n");
+ for (i = MAXDEPTH - 1; i >= 0; i--) {
+ int subentries = 0, j, fullbuckets, nfratio = 0, ofratio = 0, ratio = 0;
+
+ if (!debug[i].numbuckets)
+ continue;
+
+ if (i != MAXDEPTH) {
+ for (j = i + 1; j < MAXDEPTH; j++) {
+ subentries += debug[j].numentries;
+ }
+ }
+
+ fullbuckets = debug[i].numbuckets - debug[i].numchildren - debug[i].nfbuckets;
+
+ if (debug[i].nfbuckets)
+ nfratio = 100 * (debug[i].numentries - (fullbuckets + debug[i].numchildren) * ((NUMENTRY) - !i)) / (debug[i].nfbuckets * ((NUMENTRY) - !i));
+
+ if (debug[i].numchildren)
+ ofratio = 100 * (subentries + (debug[i].numchildren * ((NUMENTRY) - !i))) / (debug[i].numchildren * ((NUMENTRY) - !i));
+
+ ratio = 100 * debug[i].numentries / (debug[i].numbuckets * ((NUMENTRY) - !i));
+
+ printf("Depth %i:\n", i);
+ printf("\tnumber of entries: %i\n", debug[i].numentries);
+ printf("\tnumber of buckets: %i (%i%%)\n", debug[i].numbuckets, ratio);
+ printf("\t\tsubentries: %i\n", subentries);
+ printf("\t\tnot full buckets: %i (%i%%)\n", debug[i].nfbuckets, nfratio);
+ printf("\t\tfull buckets: %i (100%%)\n", fullbuckets);
+ printf("\t\toverfull buckets / children: %i (%i%%)\n", debug[i].numchildren, ofratio);
+ printf("\n");
+ }
+}
Modified: trunk/hashtrie/newtable.h
===================================================================
--- trunk/hashtrie/newtable.h 2006-03-19 23:28:29 UTC (rev 6555)
+++ trunk/hashtrie/newtable.h 2006-03-22 20:13:10 UTC (rev 6556)
@@ -35,6 +35,13 @@
u8 bucketnr;
};
+struct hashtrie_debug {
+ unsigned int numbuckets;
+ unsigned int numentries;
+ unsigned int numchildren;
+ unsigned int nfbuckets;
+};
+
struct hashentry {
unsigned char filler[PADNUM];
struct hashentry *child;
@@ -54,4 +61,6 @@
int allocate_hashtrie(struct hashtrie_info *);
int free_hashtrie(struct hashtrie_info *);
+void debug_hashtrie(struct hashtrie_info *info);
+
#endif
Modified: trunk/hashtrie/newtest.c
===================================================================
--- trunk/hashtrie/newtest.c 2006-03-19 23:28:29 UTC (rev 6555)
+++ trunk/hashtrie/newtest.c 2006-03-22 20:13:10 UTC (rev 6556)
@@ -140,6 +140,7 @@
printf("Number of children in hashtrie: %u\n", info.numchildren);
printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
printf("Maximum memory usage: %u\n", info.maxmem);
+ printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
total_count = 0;
total_time = 0;
@@ -268,6 +269,7 @@
printf("Number of children in hashtrie: %u\n", info.numchildren);
printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
printf("Maximum memory usage: %u\n", info.maxmem);
+ printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
printf("Removing entries between %u and %u.\n", REVINSFROM, REVINSTO - 1);
for (i = REVINSFROM; i < REVINSTO; i++) {
@@ -316,6 +318,7 @@
printf("Number of children in hashtrie: %u\n", info.numchildren);
printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
printf("Maximum memory usage: %u\n", info.maxmem);
+ printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
printf("Removing every other entry from 0 to %u\n", TESTNUM - 1);
for (i = 0; i < TESTNUM; i += 2) {
@@ -364,7 +367,9 @@
printf("Number of children in hashtrie: %u\n", info.numchildren);
printf("Maxdepth of hashtrie: %u (0 == root)\n", info.maxdepth);
printf("Maximum memory usage: %u\n", info.maxmem);
+ printf("Maximum memory usage per entry: %u\n", info.maxmem / info.numentries);
+ debug_hashtrie(&info);
if (!free_hashtrie(&info)) {
return 1;
More information about the netfilter-cvslog
mailing list