/****************************************************************************/ /* */ /* NNstat -- Internet Statistics Collection Package */ /* */ /* Written by: Bob Braden & Annette DeSchon */ /* USC Information Sciences Institute */ /* Marina del Rey, California */ /* */ /* Copyright (c) 1991 University of Southern California. */ /* All rights reserved. */ /* */ /* Redistribution and use in source and binary forms are permitted */ /* provided that the above copyright notice and this paragraph are */ /* duplicated in all such forms and that any documentation, */ /* advertising materials, and other materials related to such */ /* distribution and use acknowledge that the software was */ /* developed by the University of Southern California, Information */ /* Sciences Institute. The name of the University may not be used */ /* to endorse or promote products derived from this software */ /* without specific prior written permission. */ /* THIS SOFTWARE IS PROVIDED "AS IS" AND WITHOUT ANY EXPRESS OR */ /* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ /* PURPOSE. */ /* */ /****************************************************************************/ static char rcsid[]= "$Header: sobjmfb.c,v 1.9 93/10/11 18:42:15 mogul Exp $"; /* * CHANGES: * 01Nov89 ISI: Add this module * Rel 3.0: * ISI: Add List routine. * ISI: Remove redundant NL when no bins. * ISI: Read/List output to logfp, not stdout. * Aug93/DECWRL: Alpha/OSF port; XDR is a pointer type! * stuff to print out Ether/FDDI load percentages * * */ /* * Internet Statistics Facility -- Generic Operation Routines * * This module defines a set of operations on a particular class * of Statistical Objects. In the spirit of object-oriented * programming and information-hiding, these routines are * the only ones which know about the internal structre of the * Statistical Object (SOBJ) data structures. * */ /* * Object Classes == FAB: Frequency-all-Bytes, * MAB: Matrix-all-Bytes, * MSB: Matrix-sym-Bytes * * Objects of the MAB and MSB classes are frequency matrices for * pairs of 32-bit values, using dynamically-created bins, and also * accumulating total packet bytes. Objects of the FAB class are * one-dimensional frequency distributions, with total bytes. * * MAB: every distinct pair (a,b) is counted in a separate bin. * MSB: (a,b) and (b,a) are counted in the same bin. * * These objects are implemented using a chained hash table. The bins are * in a space which is allocated dynamically in pages of 4K bytes. * Bins are also linked into a doubly-linked list, sorted by decreasing * count field. Within the same count,they are sorted by increasing last- * reference time. * * The one- and two-D distributions basically use the same datastructures * and algorithms, so they use common code. For the two-D objects, the * two arguments are concatenated to make a single argument for lookup * purposes. * * Operations on these objects: * * SOBJ *Make_MAB( object-name, &sym-switch, 1/0, datalen1, datalen2 ) * SOBJ *Make_MSB( object-name, &parmlist, nparms, datalen1, datalen2 ) * SOBJ *Make_FAB( object-name, &parmlist, nparms, datalen ) * (There should be no parmlist (nparms=0)) for FAB, MSB) * * Write_MAB( (SOBJ *) SOBJ-ptr, &value1, len1, &value2, &len2) * (also used for MFB; or:) * Write_FAB( (SOBJ *) SOBJ-ptr, &value, len) * (Note that packet length is implicit parameter to both...) * * Read_MFB( fd, (SOBJ *) SOBJ-ptr ) (used for MAB, MSB, FAB) * * Delete_MFB( (SOBJ *) SOBJ-ptr ) (used for MAB, MSB, FAB) * * Clear_MFB( (SOBJ *) SOBJ-ptr ) (used for MAB, MSB, FAB) * * List_MFB( fd, OBJp ) * */ #include #include #include "stat.h" #include "sobj.h" /* * Define MAB/MSB/FAB object data structures * */ #define MAX_PAGES 8 /* Max no. 256-entry (4K byte) bin pages */ #define HASHsize 255 #define BIN_pwr2 8 /* log2( number bins per extension page )*/ #define BIN_PAGE (1<mfba_page[(i)>>BIN_pwr2]+ p->mfba_esize*((i)&BIN_MASK) ) /* Hash Function == simple congruential hash */ #define hashfunc( V, S) V%S /* Bin format */ #define MFBE struct ma_bin_element MFBE { struct FBlinks mfbe_fb; /* Doubly-linked sort list */ MFBE *mfbe_next ; /* Hash chain field */ MFBDE mfbe_mfbde ; /* Rest... count, value[], time, bytes */ /* * For matrix ops, value[] is concatenation of two values; value is * padded to fullword boundary, so length of value[] is: * 4*((dleng1+dleng2+3)/4) bytes. * * We chose an internal representation which is the SAME as the * network representation, to simplify READ operations [see stat.h]. */ }; #define mfbe_value mfbe_mfbde.mfbd_value #define mfbe_count mfbe_mfbde.mfbd_count #define mfbe_time mfbe_mfbde.mfbd_time #define mfbe_Hbyte mfbe_mfbde.mfbd_Hbyte #define mfbe_Lbyte mfbe_mfbde.mfbd_Lbyte /* Common Object Area format */ #define MFBA struct stat_xarea MFBA { SOBJ mfba_sobj; /* SOBJ = standard root of area */ short mfba_esize; /* Size of element */ short mfba_hashs; /* Size of hash table (#shorts) */ short mfba_symswitch; /* Symmetry switch -- Matrix classes */ short mfba_maxchain; /* Max chain length */ struct FBlinks mfba_head; /* Head of sorted list */ MFBE *mfba_tail; /* Tail of sorted list */ long mfba_infinity; /* Infinite count -- 'fence' */ long mfba_cntmoves; /* Total places moved in sorting */ int mfba_currbin; /* Index of first available bin */ MFBE **mfba_hashp; /* Ptr to hash table */ char *mfba_page[MAX_PAGES]; /* Ptrs to bin segments */ /*---------------------------------------------------- Hash Table... (a vector of pointers: the heads of hash chains) /*----------------------------------------------------*/ } ; SOBJ *Make_MAB(), *Make_MSB(), *Make_FAB(); boolean Write_MAB(), Write_FAB(), Read_MFB(); void Clear_MFB(), Delete_MFB(), List_MFB(); /* Transfer Vectors * for external access to these routines */ GENERICOP MABop = { Make_MAB, Write_MAB, Read_MFB, Clear_MFB, Delete_MFB,List_MFB}; GENERICOP MSBop = { Make_MSB, Write_MAB, Read_MFB, Clear_MFB, Delete_MFB,List_MFB}; GENERICOP FABop = { Make_FAB, Write_FAB, Read_MFB, Clear_MFB, Delete_MFB,List_MFB}; /* * Common Make routine * */ SOBJ *Make_mfb(symswitch, datalen1, datalen2) boolean symswitch; int datalen1, datalen2; { register MFBA *mfbap ; register int i ; int hsize = HASHsize ; int vsize = ALIGN(datalen1+datalen2); if (datalen1 > MAX_DLENG || datalen2 > MAX_DLENG){ SOBJ_error = "FAB/MAB/MSB: Field size too big"; return(NULL); } i = (sizeof(char *))*hsize + sizeof ( MFBA ) ; if ((mfbap = (MFBA *) malloc(i)) == NULL) { SOBJ_error = "FAB/MAB/MSB: Memory overflow" ; return(NULL) ; } bzero(mfbap, i) ; /* Clear entire area... */ mfbap->mfba_esize = PTRALIGN(sizeof(MFBE) + vsize - 2*MAX_DLENG); mfbap->mfba_hashs = hsize; mfbap->mfba_currbin = 0; SETMAXINT(mfbap->mfba_infinity); mfbap->mfba_tail = (MFBE *) &mfbap->mfba_head; mfbap->mfba_symswitch = (symswitch && (datalen1 == datalen2)); mfbap->mfba_hashp = (MFBE **) ((char *) mfbap + sizeof(MFBA) ) ; /* Start of hash table */ return(&mfbap->mfba_sobj) ; /* SUCCESS!! */ } SOBJ *Make_FAB(objname, parmp, nparms, datalen) char *objname; int *parmp; int nparms, datalen; { return(Make_mfb(0, datalen, 0)); } SOBJ *Make_MSB(objname, parmp, nparms, datalen1, datalen2) char *objname; int *parmp; int nparms, datalen1, datalen2; { if (datalen2 == 0) { attach_error("MSB: Missing 2nd field for obj", objname); return(NULL); } return(Make_mfb(1, datalen1, datalen2)); } SOBJ *Make_MAB(objname, parmp, nparms, datalen1, datalen2) char *objname; int *parmp; int nparms, datalen1, datalen2; { int symswitch = 0; if (datalen2 == 0) { attach_error("MAB: Missing 2nd field for obj", objname); return(NULL); } if (nparms) symswitch = *parmp; return(Make_mfb(symswitch, datalen1, datalen2)); } boolean Write_FAB( mfbap, Valuep, L) register MFBA *mfbap ; char *Valuep; int L; { union v_union Value; ZERO_UNION(&Value); Bcopy(Valuep, Value.v_byte, L); return(Write_mfb(mfbap, &Value, L, SUM_UNION(&Value))); } boolean Write_MAB( mfbap, Valuep1, L1, Valuep2, L2) register MFBA *mfbap ; char *Valuep1, *Valuep2 ; int L1, L2; { register int L = L1; union v_union Values; extern int CLC(); extern Bcopy(); ZERO_UNION(&Values); ZERO_UN2(&Values); if (mfbap->mfba_symswitch && CLC(Valuep1, Valuep2, L1) > 0) { /* Symmetry-switch set (this can only happen if L1 == L2). * Reverse order if Value2 < Value 1. */ Bcopy(Valuep2, Values.v_byte, L); Bcopy(Valuep1, &Values.v_byte[L1], L); } else { Bcopy(Valuep1, Values.v_byte, L); Bcopy(Valuep2, &Values.v_byte[L1], L2); } return(Write_mfb(mfbap, &Values, L1+L2, SUM_UN2(&Values)+SUM_UNION(&Values))); } /* */ boolean Write_mfb( mfbap, Valuep, L, HValue) register MFBA *mfbap; char *Valuep; /* Ptr to aligned value(s) */ int L; /* Length of value(s) */ u_int32 HValue; /* Derived 32-bit value to be hashed */ { register MFBE *mfbep, **thp, *tep; MFBE **hp; int n = 0; extern short packetlen; /* DIRECTLY ACCESS LENGTH IN BYTES */ /* Find hash table bucket */ hp = thp = &mfbap->mfba_hashp[ hashfunc(HValue, mfbap->mfba_hashs) ]; /* Search down hash chain */ while (mfbep = *thp) { if ((WORD1(mfbep->mfbe_value) == WORD1(Valuep)) && (L <= sizeof(int32) || ((WORD2(mfbep->mfbe_value) == WORD2(Valuep)) && (L <= 2*sizeof(int32) || ((WORD3(mfbep->mfbe_value) == WORD3(Valuep)) && (L <= 3*sizeof(int32) || ((WORD4(mfbep->mfbe_value) == WORD4(Valuep)) ))))))) /* Lisp, anyone? */ { /* Found bin, so increment count and accumulate bytes */ mfbep->mfbe_count++ ; ; if ((mfbep->mfbe_Lbyte += packetlen) >= MAX_LBYTE) { mfbep->mfbe_Lbyte -= MAX_LBYTE; mfbep->mfbe_Hbyte++; } mfbep->mfbe_time = CurrTime ; if (mfbep->mfbe_count >= (tep = (MFBE *) mfbep->mfbe_fb.FB_Bp)->mfbe_count) { /* Bin is now out of sorts. Move it up in list. * Note that head of list has artificial infinite * count as 'fence', so cannot get here if bin is * already first in list. * * First, adjust tail pointer if necessary. */ if (mfbep == mfbap->mfba_tail) mfbap->mfba_tail = (MFBE *) mfbep->mfbe_fb.FB_Bp; else if (mfbep->mfbe_count == 2 && mfbap->mfba_tail->mfbe_count>2) mfbap->mfba_tail = mfbep; FBrem(&mfbep->mfbe_fb); do { tep = (MFBE *) tep->mfbe_fb.FB_Bp; mfbap->mfba_cntmoves++; /* Keep performance stat */ } while (mfbep->mfbe_count >= tep->mfbe_count); FBins(&mfbep->mfbe_fb, &tep->mfbe_fb); } else { /* Don't have to move bin at all. May still have to * adjust tail pointer... */ if (mfbep->mfbe_count == 2) mfbap->mfba_tail = mfbep; } return(WRRET_OK) ; } thp = &mfbep->mfbe_next ; n++; } /* No such bin... Must create new one and insert into hash list... */ if (mfbap->mfba_currbin >= BIN_MAX ) { /* We have run out of new bins. Count as orphan. */ mfbap->mfba_sobj.sob_orphans++ ; return(WRRET_OK) ; } if ((mfbep = BIN_ADDR( mfbap, mfbap->mfba_currbin)) == NULL) { /* must obtain new page */ mfbep = (MFBE *) malloc(mfbap->mfba_esize * BIN_PAGE) ; if (mfbep == NULL) { /* Cannot get new bin page. Count as orphan. */ mfbap->mfba_sobj.sob_orphans++ ; return(WRRET_OK) ; } mfbap->mfba_page[(mfbap->mfba_currbin >> BIN_pwr2)] = (char *) mfbep ; } /* * Fill in new bin */ WORD1(mfbep->mfbe_value) = WORD1(Valuep); if (L > sizeof(int32)) { WORD2(mfbep->mfbe_value) = WORD2(Valuep); if (L > 2*sizeof(int32)) { WORD3(mfbep->mfbe_value) = WORD3(Valuep); if (L > 3*sizeof(int32)) { WORD4(mfbep->mfbe_value) = WORD4(Valuep); } } } mfbep->mfbe_count = 1 ; mfbep->mfbe_Lbyte = packetlen; mfbep->mfbe_Hbyte = 0; mfbep->mfbe_time = CurrTime ; mfbap->mfba_currbin++ ; /* Insert bin at BEGINNING of 1-count segment of list */ tep = mfbap->mfba_tail; FBins(&mfbep->mfbe_fb, &tep->mfbe_fb); /* PREPEND new bin to hash chain (take advantage of ref. locality) */ mfbep->mfbe_next = *hp; *hp = mfbep ; /* Measure the health of the hash chains... * record maximum length of any chain */ if (++n > mfbap->mfba_maxchain) mfbap->mfba_maxchain = n; return(WRRET_OK) ; } void Delete_MFB( mfbap ) MFBA *mfbap ; { Clear_MFB(mfbap) ; free(mfbap) ; } void Clear_MFB( mfbap ) register MFBA *mfbap ; { register int i ; register char *pp ; bzero(mfbap->mfba_hashp, (sizeof(char *))*mfbap->mfba_hashs); mfbap->mfba_currbin = mfbap->mfba_maxchain = mfbap->mfba_cntmoves = 0; mfbap->mfba_head.FB_Bp = mfbap->mfba_head.FB_Fp = NULL; mfbap->mfba_tail = (MFBE *) &mfbap->mfba_head; for (i = 0;imfba_page[i]) { free(pp) ; mfbap->mfba_page[i] = NULL ; } else break ; } } #define OUTSIZE 256 boolean Read_MFB(fd, mfbap) XDR *fd; register MFBA *mfbap ; { register MFBE *mfbep ; char outp[OUTSIZE]; int outl = (ISTTY(fd))?OUTSIZE:0; OBJ xobj; EnumHandle enumh = NULL; extern MakeCols(); struct dblword byt_dbl; char bytbuf[18]; #ifdef PRINT_NETLOAD char bytbuf2[18]; #endif if (outl) enumh = ExistEnumObj(mfbap->mfba_sobj.sob_name); if (!PutReadResp(fd, MFBr_SIZE(mfbap->mfba_currbin, mfbap->mfba_sobj.sob_dleng+mfbap->mfba_sobj.sob_dleng2), mfbap)) return(FALSE); Sum_Bytes(mfbap, &byt_dbl); if (ISTTY(fd)) { MakeCols(NULL); /* Initialize formatting */ print_dbl(bytbuf, byt_dbl.H, byt_dbl.L); fprintf(logfp, #ifdef PRINT_NETLOAD " Total Bytes= %sB #bins= %d Maxchain = %d SortMoves = %d ", #else " Total Bytes= %sB #bins= %d Maxchain = %d SortMoves = %d\n", #endif bytbuf, mfbap->mfba_currbin, mfbap->mfba_maxchain, mfbap->mfba_cntmoves) ; #ifdef PRINT_NETLOAD SetupXRep(&xobj, mfbap); bytbuf[0] = '\0'; print_netload_percent(bytbuf, byt_dbl.H, byt_dbl.L, xobj.obj_state.totalno, xobj.obj_state.currtime - xobj.obj_state.cleartime); /* Gross hack: we need to "evaluate away" one layer of %s */ sprintf(bytbuf2, bytbuf); fprintf(logfp,"%s\n",bytbuf2); #endif } else { if (!xdr_opaque(fd, &byt_dbl, sizeof(byt_dbl)) || /* Total bytes */ !xdr_int(fd, &mfbap->mfba_currbin) ) /* XDR count field for element array that follows */ return(FALSE) ; } SetupXRep(&xobj, mfbap); if ((mfbep = (MFBE *) mfbap->mfba_head.FB_Fp) == NULL) return(TRUE); while (mfbep) { /* run down the sorted list... */ if (!MFB_list(fd, outp, outl, &mfbep->mfbe_mfbde, &xobj.obj_state, enumh)) return(FALSE); if (outl) log(outp, logfp); mfbep = (MFBE *) mfbep->mfbe_fb.FB_Fp; } ; if (outl) log("\n", logfp); return(TRUE); } /* Read_MFB() */ #ifdef OUTSIZE #undef OUTSIZE #endif #define OUTSIZE 256 void List_MFB(fd, OBJp) XDR *fd; OBJ *OBJp; { MFBDE bin; int j, count; EnumHandle isEnum; struct dblword bytdbl; char bytbuf[18]; char out[OUTSIZE]; isEnum = ExistEnumObj(OBJp->obj_name); if (!xdr_opaque(fd, &bytdbl, sizeof(bytdbl))) { printf(" Bad MFB read"); return; } print_dbl(bytbuf, bytdbl.H, bytdbl.L); sprintf(out, " Total Bytes= %sB ", bytbuf); #ifndef PRINT_NETLOAD count = get_long(fd, endof(out), " #bins"); #else count = get_long_nonl(fd, endof(out), " #bins"); print_netload_percent(endof(out), bytdbl.H, bytdbl.L, OBJp->obj_state.totalno, OBJp->obj_state.currtime - OBJp->obj_state.cleartime); sprintf(endof(out), "\n"); #endif log(out, logfp); MakeCols(NULL); for (j=0;jobj_state, isEnum)) { printf(" BAD MFB_list! "); break; } else log(out, logfp); } if (count) log("\n", logfp); } /* List_MFB() */ /* * MFB_list() -- I/O routine for single entry of freq-all-bytes or * matrix-all-bytes * objstp: contains parameters of object * mfbep: pts to element that may be sent or received (determined by * direction of fd), and perhaps (if outl > 0) * displayed into buffer: char *outp. * */ boolean MFB_list(fd, outp, outl, mfbep, objstp, enumh) register XDR *fd; char *outp; int outl; MFBDE *mfbep; struct Obj_state *objstp; EnumHandle enumh; { register char *cp = outp; char *Enump, *FindEnum(); int i; char bytbuf[20]; if (mfbep == NULL) return(FALSE); if (fd) { if (!xdr_u_int(fd, &mfbep->mfbd_count) || !xdr_int(fd, &mfbep->mfbd_time) || !xdr_opaque(fd, &mfbep->mfbd_Hbyte, 8) || !xdr_opaque(fd, mfbep->mfbd_value, objstp->dleng+objstp->dleng2) ) return(FALSE); } if (outl) { if (outl < 80) return(FALSE); *cp++ = '['; print_val(cp, mfbep->mfbd_value, objstp->datatype, objstp->dleng); if (Enump = FindEnum(enumh, mfbep->mfbd_value, objstp->dleng)) { strcat(cp, " \""); strcat(cp, Enump); strcat(cp, "\""); cp = endof(cp); } if (objstp->dleng2) { strcat(cp, (tersemode)?":":" : "); print_val(endof(cp), mfbep->mfbd_value+objstp->dleng, objstp->datatyp2, objstp->dleng2); } print_dbl(bytbuf, mfbep->mfbd_Hbyte, mfbep->mfbd_Lbyte); sprintf(cp = endof(cp), "]= %d &%sB ", mfbep->mfbd_count, bytbuf); if ((i = Align(outp)) != 0) sprintf(endof(cp), "%*c", i, ' '); print_percent(endof(cp), objstp->totalno, mfbep->mfbd_count); #ifdef PRINT_NETLOAD print_netload_percent(endof(outp), mfbep->mfbd_Hbyte, mfbep->mfbd_Lbyte, mfbep->mfbd_count, objstp->currtime - objstp->cleartime); #endif sprintf(endof(cp), "@-%dsec ", objstp->currtime - mfbep->mfbd_time); MakeCols(outp); } return(TRUE); } /* MFB_list() */ /* * When read, call the following routine to sum up all bytes. * This is expensive, but probably not prohibitively expensive, * and maybe useful. */ Sum_Bytes(mfbap, dblp) MFBA *mfbap; register struct dblword *dblp; { register MFBE *mfbep = (MFBE *) (mfbap->mfba_head.FB_Fp); dblp->H = dblp->L = 0; while (mfbep) { /* run down the sorted list... */ dblp->H += mfbep->mfbe_Hbyte; if ((dblp->L += mfbep->mfbe_Lbyte) >= MAX_LBYTE) { /* Handle carry from lower part */ dblp->L -= MAX_LBYTE; dblp->H++; } mfbep = (MFBE *) mfbep->mfbe_fb.FB_Fp; } }