/****************************************************************************/ /* */ /* 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: /tmp_mnt/r/jove_staff3/mogul/code/NNstat/3.3beta/RCS/sobjws.c,v 1.6 1993/09/22 22:46:20 mogul Exp $"; /* * 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. * */ /* CHANGES: * 18Nov88 RTBraden -- Fix bug in read: missing SetupXRep() call. * Rel 3.0: * ISI: Add List routine. * ISI: Improve algorithm efficiency by using hash table for match. * ISI: Change format of output * ISI: Add WS2 class * Aug93/DECWRL: Alpha/OSF port. XDR is a pointer type! * */ /* * * WS, WS2 Classes * * Objects of the WS class or WS2 class compute a frequency * distribution related to the degree of locality of reference in a * sequence of field values. This problem is related closely to * virtual memory algorithms. * * Note: "WS" stands for "working set", which is actually a misnomer. * These objects measure LRU cache hit probabilities, not working set size. * * Let C(n) be the number of number of values in the given sequence * that fall within the set of the n most recent ones. If there are N * values in the sequence, C(n)/N is the corresponding cache hit * probability. The WS object returns C(1), C(2), C(4), ... C(4096) * for the given field; WS2 does the same for the value obtained by * catenating the two given fields. * * Operations on WS & WS2 class objects: * * SOBJ *Make_WS( object-name, &parmlist, nparms, datalen ) * * SOBJ *Make_WS2( object-name, &parmlist, nparms, datalen ) * There is one optional parameter; if present and nonzero, it * causes a SYMMETRIC matrix: (a,b) and (b,a) values are treated * as equivalent. * * Write_WS2( (SOBJ *) SOBJ-ptr, &value1, len1, &value2, len2) * * Write_WS( (SOBJ *) SOBJ-ptr, &value, len) * * Read_WS( fd, (SOBJ *) SOBJ-ptr ) * * Delete_WS( (SOBJ *) SOBJ-ptr ) * * Clear_WS( (SOBJ *) SOBJ-ptr ) * * List_WS( fd, OBJp ) */ #include #include #include "stat.h" #include "sobj.h" /* * Define WS object data structures * */ #define PAGE_pwr2 4 /* log2(MAX_PAGES) */ #define MAX_PAGES 1<wsa_page[((i)>>BIN_pwr2)]+ \ wsap->wsa_esize*((i)&BIN_MASK) ) /* Hash Function == simple congruential hash */ #define hashfunc( V, S) V%S #define WSr_SIZE(N) (2+N)*sizeof(u_int32) /* Bin format */ #define WSE struct ws_bin_element WSE { struct FBlinks wse_fb; /* LRU chain: forward and reverse links */ WSE *wse_next; /* hash chain: forward link */ u_int32 wse_hashv; /* hash value */ char wse_value[2*MAX_DLENG]; /* value */ /* Actually reserve 4*((dleng+3)/4) bytes */ }; /* Object area format */ #define WSA struct stat_xarea WSA { SOBJ wsa_sobj ; /* SOBJ = standard root of area */ int wsa_esize ; /* Size of element */ short wsa_hashs; /* Size of hash table (#shorts) */ int wsa_nextbin ; /* Index of first available bin */ int wsa_symswitch; /* WS2: true if want symmetry in F1, F2 */ struct FBlinks wsa_head; /* Head of LRU chain of bins */ int wsa_count[MAX_LOG2N+1]; /* Count vector */ WSE *wsa_lastp; /* Ptr to last bin */ WSE **wsa_hashp; /* Ptr to hash table */ WSE *wsa_page[MAX_PAGES] ; /* Ptrs to bin segments */ /*---------------------------------------------------- Hash Table... (a vector of pointers: the heads of hash chains) /*----------------------------------------------------*/ } ; SOBJ *Make_WS(), *Make_WS2(), *MakeWS() ; boolean Write_WS(), Write_WS2(), Read_WS() ; void Clear_WS(), Delete_WS(), List_WS() ; /* Transfer Vector * for external access to these routines */ GENERICOP WSop = { Make_WS, Write_WS, Read_WS, Clear_WS, Delete_WS, List_WS } ; GENERICOP WS2op = { Make_WS2, Write_WS2, Read_WS, Clear_WS, Delete_WS, List_WS } ; SOBJ *Make_WS(objname, parmp, nparms, datalen) char *objname; int *parmp; int datalen, nparms; { return(MakeWS(objname, parmp, nparms, datalen, 0)); } /* Make_WS() */ SOBJ *Make_WS2(objname, parmp, nparms, datalen1, datalen2) char *objname; int *parmp; int datalen1, datalen2, nparms; { if (datalen2 == 0) { SOBJ_error = "WS2: Missing second field"; return(NULL); } return(MakeWS(objname, parmp, nparms, datalen1, datalen2)); } /* Make_WS2() */ SOBJ *MakeWS(objname, parmp, nparms, datalen1, datalen2) char *objname; int *parmp; int datalen1, datalen2, nparms; { register WSA *wsap ; int hsize = HASHsize, i; if (datalen1 > MAX_DLENG || datalen2 > MAX_DLENG){ SOBJ_error = "WS2: Field size too big"; return(NULL); } i = (sizeof(WSE *))*hsize + sizeof (WSA) ; if ((wsap = (WSA *) malloc(i)) == NULL) { SOBJ_error = "WS: Mem overflow" ; return(NULL) ; } bzero(wsap, i) ; /* Clear entire area... */ wsap->wsa_esize = PTRALIGN(sizeof(WSE) - 2*MAX_DLENG + ALIGN(datalen1+datalen2)); wsap->wsa_hashs = hsize; wsap->wsa_nextbin = 0 ; wsap->wsa_symswitch = (nparms && *parmp && (datalen1 == datalen2)); wsap->wsa_hashp = (WSE **) ((char *) wsap + sizeof(WSA) ) ; /* Start of hash table */ return(&wsap->wsa_sobj) ; /* SUCCESS!! */ } /* MakeWS() */ boolean Write_WS(wsap, Valuep, L) register WSA *wsap ; char *Valuep ; int L; { u_int32 HValue; union v_union Value; ZERO_UNION(&Value); bcopy(Valuep, Value.v_byte, L); HValue = SUM_UNION(&Value); WriteWS( wsap, &Value, HValue, L); return(WRRET_OK) ; } /* Write_WS() */ boolean Write_WS2( wsap, Valuep1, L1, Valuep2, L2) register WSA *wsap; char *Valuep1, *Valuep2; int L1, L2; { register int L = L1; u_int32 HValue; union v_union Values; ZERO_UNION(&Values ); ZERO_UN2(&Values); if (wsap->wsa_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); } L = L1+L2; HValue = SUM_UNION(&Values)+SUM_UN2(&Values); WriteWS( wsap, &Values, HValue, L); return(WRRET_OK) ; } /* Write_WS() */ /* Common Write routine */ boolean WriteWS( wsap, Valuep, Hvalue, L) register WSA *wsap ; register union v_union *Valuep; u_int32 Hvalue; /* Folded value to be hashed */ int L; { register WSE *wsep; register int K; u_int32 Hashv = hashfunc(Hvalue, wsap->wsa_hashs) ; { register WSE **thp; thp = &wsap->wsa_hashp[Hashv]; while (wsep = *thp) { /* scan hash chain for match */ if ((WORD1(wsep->wse_value) == WORD1(Valuep)) && (L <= sizeof(int32) || ((WORD2(wsep->wse_value) == WORD2(Valuep)) && (L <= 2*sizeof(int32) || ((WORD3(wsep->wse_value) == WORD3(Valuep)) && (L <= 3*sizeof(int32) || ((WORD4(wsep->wse_value) == WORD4(Valuep)) ))))))) break; thp = &wsep->wse_next ; } } /* end of block */ if (wsep) { /* Found existing bin. Scan down list to find its ordinal * position K. (This linear search is unfortunate but a * necessary part of the algorithm). * If bin was already first, it would be included * in ANY set, so it can remain first in LRU list, and we * are all done. Else, remove it from list, so it can be * moved to front of list later. */ register WSE *tep; tep = (WSE *) wsap->wsa_head.FB_Fp; K = 0; while (tep != wsep && tep) { K++; tep = (WSE *) tep->wse_fb.FB_Fp ; } if (K == 0) return(WRRET_OK); FBrem(&wsep->wse_fb); if (wsep == wsap->wsa_lastp) /* was last ... */ wsap->wsa_lastp = (WSE *) wsep->wse_fb.FB_Bp; } else { if (wsap->wsa_nextbin >= BIN_MAX ) { /* We have run out of new bins. Reuse LRU bin. */ register WSE **thp; wsep = wsap->wsa_lastp; /* Use last WSE in LRU chain */ FBrem(&wsep->wse_fb); /* Remove WSE from LRU chain */ /* Scan hash chain and remove WSE */ thp = &wsap->wsa_hashp[wsep->wse_hashv]; while (*thp != wsep) thp = &((*thp)->wse_next); *thp = wsep->wse_next; wsep->wse_next = NULL; wsap->wsa_lastp = (WSE *) wsep->wse_fb.FB_Bp; K = BIN_MAX; } else { /* Create new bin... */ if ((wsep = BIN_ADDR( wsap, wsap->wsa_nextbin)) == NULL) { /* must obtain new page */ wsep = (WSE *) malloc(wsap->wsa_esize * BIN_PAGE) ; if (wsep == NULL) { /* Cannot get new bin page. Count as orphan. */ wsap->wsa_sobj.sob_orphans++ ; return(WRRET_OK) ; } wsap->wsa_page[(wsap->wsa_nextbin >> BIN_pwr2)] = wsep ; } /* got new page */ K = wsap->wsa_nextbin++; wsep->wse_fb.FB_Fp = wsep->wse_fb.FB_Bp = 0; if (wsap->wsa_head.FB_Fp == NULL) wsap->wsa_lastp = wsep; /* First bin */ } /* got new bin */ /* Prepend new/reused bin to hash chain */ wsep->wse_next = wsap->wsa_hashp[wsep->wse_hashv = Hashv]; wsap->wsa_hashp[wsep->wse_hashv] = wsep ; /* Now copy new value into new/reused bin */ WORD1(wsep->wse_value) = WORD1(Valuep); if (L > sizeof(int32)) { WORD2(wsep->wse_value) = WORD2(Valuep); if (L > 2*sizeof(int32)) { WORD3(wsep->wse_value) = WORD3(Valuep); if (L > 3*sizeof(int32)) { WORD4(wsep->wse_value) = WORD4(Valuep); } } } } /* At this point, wsep is referenced bin, and K is its * position in the LRU list. Compute i = floor(log2(K)), * and increment count[i] by one. * * This implies that the given value would have been a cache miss * if log2(cache size) < i+1 (or, since cache sizes are assumed * to be powers of 2: log2(cache size) <= i), and a cache hit * otherwise. */ { register int i; i = -1; while (K) { i++; K >>= 1; } if (i >= 0) { if (i <= MAX_LOG2N) wsap->wsa_count[i]++; else wsap->wsa_sobj.sob_orphans++ ; } } FBins(&wsep->wse_fb, &wsap->wsa_head); return(WRRET_OK) ; } /* WriteWS() */ void Delete_WS( wsap ) WSA *wsap ; { Clear_WS(wsap) ; free(wsap) ; } void Clear_WS( wsap ) register WSA *wsap ; { register int i; register WSE *wsep; bzero(wsap->wsa_hashp, (sizeof(WSE *))*wsap->wsa_hashs); wsap->wsa_nextbin = 0; wsap->wsa_head.FB_Fp = wsap->wsa_head.FB_Bp = 0; bzero(wsap->wsa_count, (1+MAX_LOG2N)*sizeof(int)); for (i = 0;iwsa_page[i]) { free(wsep) ; wsap->wsa_page[i] = NULL ; } else break ; } } /* Clear_WS() */ #define OUTSIZE 256 boolean Read_WS(fd, wsap) XDR *fd; register WSA *wsap ; { register int i; register int sum; u_int32 Ans[1+MAX_LOG2N], *vecptr = Ans; int veclen; OBJ xobj; /* Truncate transmission of trailing zeros in vector */ for (i = MAX_LOG2N; i >= 0; i--) if (wsap->wsa_count[i]) break; veclen = (iwsa_count[i]; for (i=0; i < veclen; i++) { Ans[i] = sum; sum -= wsap->wsa_count[i]; } SetupXRep(&xobj, wsap); if (!ReadWS(fd, &vecptr, &veclen, &wsap->wsa_nextbin, &xobj, ISTTY(fd))) return(FALSE); return(TRUE); } /* Read_WS() */ /* * List_WS(): called by remote rspy or collect, to obtain data from * XDR, format display of object, and log it. */ void List_WS(fd, OBJp) XDR *fd; OBJ *OBJp; { u_int32 Vector[1+MAX_LOG2N], *Vecptr = Vector; int count = 1+MAX_LOG2N; u_int32 distinct; if (!ReadWS(fd, &Vecptr, &count, &distinct, OBJp, 1)) printf(" BAD ReadWS! "); } /* List_WS() */ /* * ReadWS() -- I/O routine for working-set read data. * * */ boolean ReadWS(fd, vectorpp, maxnop, nbinp, objp, islog) register XDR *fd; /* XDR unit or NULL */ u_int32 **vectorpp; /* Ptr to cache-miss count vector */ int *maxnop; /* Ptr to word containing leng of vector */ u_int32 *nbinp; /* ptr to count of distinct bins */ OBJ *objp; /* ptr to OBJ structure for object */ int islog; /* If TRUE, log display in 'logfp' */ { register int i, n; int k = *maxnop; u_int32 *valp = *vectorpp, hits, total; char outp[OUTSIZE]; if (fd) { /* Number of bins, length of cache miss vector */ if (!xdr_u_int(fd, nbinp) || !xdr_int(fd, &k)) return(FALSE); } if (islog) { sprintf(outp, " # distinct values= %d\n", *nbinp) ; log(outp, logfp); } if (k>*maxnop) return(FALSE); /* Internal error: caller's buffer was too small. */ total = objp->obj_state.totalno - objp->obj_state.orphans; n = 1; for (i=0;i < k; i++) { if (fd) { if (!xdr_u_int(fd, valp)) return(FALSE); } if (islog&&total) { hits = total - *valp; if (tersemode) sprintf(outp, "%4d %5.3f\n", n, ((float) hits)/total); else sprintf(outp, "[Cache %4d]= %7d hits; Prob= %5.3f\n", n, hits, ((float) hits)/total); log(outp, logfp); } valp++; n <<= 1; } ; return(TRUE); } /* ReadWS() */