/* * Copyright (c) 1994, 1995, 1996, 1997, 1998, 1999, 2000, 2001, * 2002, 2003, 2004 * Ohio University. * * --- * * Starting with the release of tcptrace version 6 in 2001, tcptrace * is licensed under the GNU General Public License (GPL). We believe * that, among the available licenses, the GPL will do the best job of * allowing tcptrace to continue to be a valuable, freely-available * and well-maintained tool for the networking community. * * Previous versions of tcptrace were released under a license that * was much less restrictive with respect to how tcptrace could be * used in commercial products. Because of this, I am willing to * consider alternate license arrangements as allowed in Section 10 of * the GNU GPL. Before I would consider licensing tcptrace under an * alternate agreement with a particular individual or company, * however, I would have to be convinced that such an alternative * would be to the greater benefit of the networking community. * * --- * * This file is part of Tcptrace. * * Tcptrace was originally written and continues to be maintained by * Shawn Ostermann with the help of a group of devoted students and * users (see the file 'THANKS'). The work on tcptrace has been made * possible over the years through the generous support of NASA GRC, * the National Science Foundation, and Sun Microsystems. * * Tcptrace is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * Tcptrace is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with Tcptrace (in the file 'COPYING'); if not, write to the * Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, * MA 02111-1307 USA * * Author: Shawn Ostermann * School of Electrical Engineering and Computer Science * Ohio University * Athens, OH * ostermann@cs.ohiou.edu * http://www.tcptrace.org/ */ #include "tcptrace.h" static char const GCC_UNUSED copyright[] = "@(#)Copyright (c) 2004 -- Ohio University.\n"; static char const GCC_UNUSED rcsid[] = "@(#)$Header: /usr/local/cvs/tcptrace/dyncounter.c,v 1.7 2003/11/19 14:38:01 sdo Exp $"; /* dynamic counters/arrays */ /* uses a 10-ary tree to manage a sparse counter space */ #include "dyncounter.h" static int ldebug = 0; /* external routines */ void *MallocZ(int nbytes); /* WIDTH of the nodes (designed for 10, caveat emptor!) */ /* (sdo: tested at 2, 5, 10, 100) */ #define CARDINALITY 10 /* 10-ary tree node */ struct node { u_long depth; /* 1, 10, 100, 1000 ... 10,000,000 */ union { struct node *down[CARDINALITY]; /* if depth != 1 */ u_long value[CARDINALITY]; /* if depth == 1 */ } un; struct node *nextleaf; /* linked list of leaves, for NextCounter() */ u_long prefix; /* from trees above */ }; /* dynamically-sized counter structure */ struct dyn_counter { u_long gran; /* granularity of the IX */ u_long maxix; /* NOT scaled */ u_long minix; /* NOT scaled */ u_long maxcount; u_long total_count; /* sum of the "AddToCounters" call values */ struct node *tree; /* linked list of leaves */ struct node *firstleaf; struct node *lastleaf; }; /* local routines */ static struct dyn_counter *MakeCounterStruct(void); static struct node *NewNode(u_long depth); static u_long *FindTwig(struct node *lastnode, u_long ix); static struct node *FindLeaf( struct dyn_counter *pdc, struct node **ptree, u_long depth, u_long value, int fcreate); static u_long *FindCounter(struct dyn_counter **ppdc, u_long ix, int fcreate); static void PrintTree(struct node *tree); static void PrintTreeRecurse(struct node *tree, u_long depth); static void FinishTree(struct dyn_counter *pdc); static void FinishTreeRecurse(struct dyn_counter *pdc, struct node *pnode, u_long prefix, u_long depth); static void PrintLeafList(struct dyn_counter *pdc); static struct node *NextCounterRecurse(struct node *node, u_long nextix, u_long *pix, u_long *pcount); static struct node *MakeDepth(struct node *node, u_long depth); static void DestroyTree(struct node *pnode); static void MakeCounter(struct dyn_counter **ppdc, u_long ix, u_long val, u_long granularity, char set); /* add a value to a counter */ void AddToCounter( struct dyn_counter **ppdc, u_long ix, u_long val, u_long granularity) { if (ldebug) fprintf(stderr,"AddToCounter(%p, %lu, %lu) called\n", *ppdc, ix, val); MakeCounter(ppdc,ix,val,granularity,0); } /* set a value in a counter */ void SetCounter( struct dyn_counter **ppdc, u_long ix, u_long val, u_long granularity) { if (ldebug) fprintf(stderr,"SetCounter(%p, %lu, %lu) called\n", *ppdc, ix, val); MakeCounter(ppdc,ix,val,granularity,1); } /* read only, doesn't MAKE anything */ u_long LookupCounter( struct dyn_counter *pdc, u_long ix) { u_long *pdigit; if (ldebug) fprintf(stderr,"LookupCounter(p,%lu) called\n", ix); /* try to find the counter */ pdigit = FindCounter(&pdc, ix, 0); /* do NOT create */ if (pdigit == NULL) { /* no leaf node == no such counter */ if (ldebug) fprintf(stderr,"LookupCounter(p,%lu): no such leaf\n", ix); return(0); } return(*pdigit); } int NextCounter( struct dyn_counter **ppdc, void *pvoidcookie, u_long *pix, u_long *pcount) { struct dyn_counter *pdc; struct node *node; u_long nextix; if (ldebug) fprintf(stderr,"NextCounter(p,%p,%lu,%lu) called\n", *((char **)pvoidcookie), *pix, *pcount); /* if the counter tree doesn't exist yet, create it */ if (*ppdc == NULL) { *ppdc = MakeCounterStruct(); } pdc = *ppdc; /* scale ix by granularity */ *pix /= pdc->gran; /* make sure the linked list of leaves is up to date */ if (pdc->firstleaf == NULL) { FinishTree(pdc); if (ldebug) { PrintLeafList(pdc); PrintTree(pdc->tree); } } /* if cookie is NULL, start at the head */ if ((*((struct node **)pvoidcookie)) == NULL) { node = pdc->firstleaf; nextix = 0; } else { node = *((struct node **)pvoidcookie); nextix = ((*pix) % CARDINALITY) + 1; } /* sanity check on cookie */ if (node->depth != 1) { fprintf(stderr,"NextCounter: invalid cookie!\n"); exit(1); } /* recurse and solve */ node = NextCounterRecurse(node,nextix,pix,pcount); if (node == NULL) return(0); /* no more */ /* scale ix by granularity */ *pix *= pdc->gran; /* remember cookie for next time */ *((struct node **)pvoidcookie) = node; return(1); } /* access routine - maximum counter value */ u_long GetMaxCount( struct dyn_counter *pdc) { return(pdc->maxcount); } /* access routine - return MAX index */ u_long GetMaxIx( struct dyn_counter *pdc) { return(pdc->maxix); } /* access routine - return MIN index */ u_long GetMinIx( struct dyn_counter *pdc) { return(pdc->minix); } /* access routine - return stored granularity */ u_long GetGran( struct dyn_counter *pdc) { if (pdc == NULL) return(1); return(pdc->gran); } /* access routine - total value added with AddToCounter() */ u_long GetTotalCounter( struct dyn_counter *pdc) { if (pdc == NULL) return(0); return(pdc->total_count); } void DestroyCounters( dyn_counter *phandle) { if (!*phandle) return; if ((*phandle)->tree) DestroyTree((*phandle)->tree); free(*phandle); *phandle = NULL; } static struct dyn_counter * MakeCounterStruct() { struct dyn_counter *pdc = MallocZ(sizeof(struct dyn_counter)); pdc->minix = 0xffffffff; return(pdc); } static void DestroyTree( struct node *pnode) { int i; if (pnode == NULL) return; if (pnode->depth > 1) { /* recurse and delete */ for (i=0; i < CARDINALITY; ++i) { DestroyTree(pnode->un.down[i]); } } /* destroy ME */ free(pnode); return; } /* the heart of the routines, a 10-ary recursize search */ static struct node * FindLeaf( struct dyn_counter *pdc, struct node **ptree, u_long depth, u_long value, int fcreate) { u_long hidigit; u_long lowdigits; u_long valdepth; u_long valunits; u_long temp_value; if (ldebug) fprintf(stderr,"FindLeaf(%p(depth %lu), %lu, %s) called\n", *ptree, *ptree?((*ptree)->depth):0, value, fcreate?"CREATE":"NOCREATE"); /* if the tree is empty and we haven't asked to "create", then not found */ if ((*ptree == NULL) && (!fcreate)) return(NULL); /* determine the units of the MSDigit (the depth) */ valdepth = 1; valunits = 1; temp_value = value; while (temp_value >= CARDINALITY) { temp_value /= CARDINALITY; ++valdepth; valunits *= CARDINALITY; } if (ldebug) fprintf(stderr,"FindLeaf: value:%lu depth:%lu units:%lu\n", value, valdepth, valunits); /* is the tree deep enough? */ if ((*ptree == NULL) || (valdepth > (*ptree)->depth)) { u_long correct_depth; /* the correct depth is the MAX of: */ /* - the depth of the number we're looking for */ /* - the value of "depth" passed down */ correct_depth = depth; if (valdepth > correct_depth) correct_depth = valdepth; /* if the tree isn't that deep and we haven't asked to create, then not found */ if (!fcreate) return(NULL); /* increase the depth of this branch */ *ptree = MakeDepth((*ptree), correct_depth); /* linked list of leaves no longer valid! */ pdc->firstleaf = NULL; /* adjust */ depth = correct_depth; } /* if we're at the leaf depth, then we're done */ if ((*ptree)->depth == 1) return(*ptree); /* if the "depth" of val is less than the depth of this node, recurse down the "0" branch without changing the number */ if (valdepth < (*ptree)->depth) { return(FindLeaf(pdc, &(*ptree)->un.down[0], depth-1, value, fcreate)); } /* (else), already the correct level */ /* break the number into the MSDigit and LSDigits */ hidigit = value / valunits; lowdigits = value % valunits; if (ldebug) fprintf(stderr,"for value %lu, depth:%lu units:%lu hidigit:%lu lowdigits:%lu\n", value, valdepth, valunits, hidigit, lowdigits); /* recurse */ return(FindLeaf(pdc, &(*ptree)->un.down[hidigit], depth-1, lowdigits, fcreate)); } static struct node * MakeDepth( struct node *node, u_long depth) { struct node *newroot; if ((node != NULL) && (node->depth >= depth)) return(node); /* ELSE, insert a new level and recurse */ newroot = NewNode(depth); /* attach the old part of the tree */ if (depth > 1) newroot->un.down[0] = MakeDepth(node,depth-1); /* return the new root */ return(newroot); } static struct node * NewNode( u_long depth) { struct node *pn; if (ldebug) fprintf(stderr,"NewNode(%lu) called\n", depth); pn = MallocZ(sizeof(struct node)); pn->depth = depth; return(pn); } static u_long * FindTwig( struct node *lastnode, u_long ix) { unsigned digit; if (ldebug) fprintf(stderr,"FindTwig(%p(depth %lu), %lu) called\n", lastnode, lastnode->depth, ix); if (lastnode->depth != 1) { fprintf(stderr,"FindTwig: internal error, not at a leaf node\n"); exit(2); } digit = ix % CARDINALITY; return(&(lastnode->un.value[digit])); } static u_long * FindCounter( struct dyn_counter **ppdc, u_long ix, int fcreate) { struct dyn_counter *pdc; struct node *pnode; u_long *pcounter; if (ldebug) fprintf(stderr,"FindCounter(p, %lu) called\n", ix); /* if the counter tree doesn't exist yet, create it */ if (*ppdc == NULL) { *ppdc = MakeCounterStruct(); } pdc = *ppdc; /* track MAX and MIN */ if (ix > pdc->maxix) pdc->maxix = ix; if (ix < pdc->minix) pdc->minix = ix; if (ldebug>1) PrintTree(pdc->tree); /* scale (TRUNCATE) the index by the granularity */ ix /= (*ppdc)->gran; /* find the leaf node */ pnode = FindLeaf(pdc, &pdc->tree, pdc->tree?pdc->tree->depth:1, ix, fcreate); if (pnode == NULL) return(NULL); /* find the right counter */ pcounter = FindTwig(pnode, ix); return(pcounter); } static void Indent(int depth) { int i; for (i=0; i < depth; ++i) fputc(' ', stderr); } static void PrintTree( struct node *tree) { PrintTreeRecurse(tree,0); } static void PrintTreeRecurse( struct node *tree, u_long indent) { int i; if (tree == NULL) { Indent(indent); fprintf(stderr,"NULL\n"); return; } Indent(indent); fprintf(stderr,"Node %p, depth:%lu, prefix:%lu\n", tree, tree->depth, tree->prefix); if (tree->depth == 1) { for (i=0; i < CARDINALITY; ++i) { Indent(indent); fprintf(stderr,"Leaf[%d]: %lu (value:%lu)\n", i, tree->un.value[i], tree->prefix*CARDINALITY+i); } } else { for (i=0; i < CARDINALITY; ++i) { Indent(indent); fprintf(stderr,"Branch %d (prefix %lu, depth %lu)\n", i, tree->prefix*CARDINALITY+i, tree->depth); PrintTreeRecurse(tree->un.down[i], indent+3); } } } static void FinishTree( struct dyn_counter *pdc) { FinishTreeRecurse(pdc, pdc->tree, 0, pdc->tree->depth); } static void FinishTreeRecurse( struct dyn_counter *pdc, struct node *pnode, u_long prefix, u_long depth) { int i; /* special case, empty tree */ if (pnode == NULL) return; /* sanity check, verify depth */ if (pnode->depth != depth) { fprintf(stderr,"FinishTree: bad depth at node %p (%lu should be %lu)\n", pnode, pnode->depth, depth); PrintTree(pdc->tree); exit(-3); } /* insert prefix */ pnode->prefix = prefix; /* if we're a leaf, add to end of the list */ if (pnode->depth == 1) { if (pdc->firstleaf == NULL) { pdc->firstleaf = pdc->lastleaf = pnode; if (ldebug) fprintf(stderr,"FinishTree: Making %p the head\n", pnode); } else { pdc->lastleaf->nextleaf = pnode; pdc->lastleaf = pnode; if (ldebug) fprintf(stderr,"FinishTree: Making %p the tail\n", pnode); } return; } /* recurse down all branches */ for (i=0; i < CARDINALITY; ++i) { FinishTreeRecurse(pdc, pnode->un.down[i], prefix*CARDINALITY+i, depth-1); } } static void PrintLeafList( struct dyn_counter *ptree) { struct node *pnode = ptree->firstleaf; fprintf(stderr,"Leaf Linked List...\n"); while(pnode) { fprintf(stderr," pnode:%p prefix:%lu\n", pnode, pnode->prefix); pnode = pnode->nextleaf; } } static struct node * NextCounterRecurse( struct node *node, u_long nextix, u_long *pix, u_long *pcount) { int i; if (ldebug) fprintf(stderr,"NextCounterRecurse(%p,%lu,%lu,%lu) called\n", node, nextix, *pix, *pcount); /* base case, NULL */ if (node == NULL) return(NULL); /* first, check the rest of THIS leaf node */ for (i=nextix; i < CARDINALITY; ++i) { if (node->un.value[i] != 0) { *pix = node->prefix*CARDINALITY+i; *pcount = node->un.value[i]; return(node); } } /* check each counter in the NEXT leaf */ return(NextCounterRecurse(node->nextleaf, 0, pix, pcount)); } /* internal counter access routine */ static void MakeCounter( struct dyn_counter **ppdc, u_long ix, u_long val, u_long granularity, char is_set) /* "set" as opposed to "add" */ { u_long *pcounter; /* if the counter tree doesn't exist yet, create it */ if (*ppdc == NULL) { *ppdc = MakeCounterStruct(); } /* check granularity */ if ((*ppdc)->gran == 0) { (*ppdc)->gran = granularity; } else { /* error check */ if ((*ppdc)->gran != granularity) { fprintf(stderr,"DYNCOUNTER: internal error, granularity changed\n"); exit(-1); } } /* find/create the counter */ pcounter = FindCounter(ppdc, ix, 1); /* add or set */ if (is_set) { /* counter = val */ *pcounter = val; } else { /* counter += val */ *pcounter += val; (*ppdc)->total_count += val; } /* check MAX counter value */ if (*pcounter > (*ppdc)->maxcount) (*ppdc)->maxcount = *pcounter; return; }