created error #22
[dyninst.git] / common / src / hist.C
1 /* 
2  * Copyright (c) 1992 Barton P. Miller, Morgan Clark, Timothy Torzewski,
3  *     Jeff Hollingsworth, and Bruce Irvin. All rights reserved.
4  *
5  * This software is furnished under the condition that it may not
6  * be provided or otherwise made available to, or used by, any
7  * other person.  No title to or ownership of the software is
8  * hereby transferred.  The name of the principals
9  * may not be used in any advertising or publicity related to this
10  * software without specific, written prior authorization.
11  * Any use of this software must include the above copyright notice.
12  *
13  */
14
15 /*
16  * hist.C - routines to manage hisograms.
17  *
18  * $Log: hist.C,v $
19  * Revision 1.10  1994/06/29 02:48:31  hollings
20  * Added destructor to Histogram class.
21  *
22  * Revision 1.9  1994/05/10  03:56:47  hollings
23  * Changed hist data upcall to return array of buckets not single value.
24  *
25  * Revision 1.8  1994/04/30  21:00:03  hollings
26  * Fixed bug in fold callback that caused all fold message to go to the
27  * Histogram that caused the fold not the correct ones.
28  *
29  * Revision 1.7  1994/04/20  15:19:30  hollings
30  * Added method to get histogram buckets.
31  *
32  * Revision 1.6  1994/04/12  22:11:22  hollings
33  * removed special case of bucket a zero value since it caused upcalls not to
34  * happen.
35  *
36  * Revision 1.5  1994/03/08  17:12:29  hollings
37  * Added fold callback and changed from multiple data callbacks to one per
38  * histogram instance.  Also made the data callbacks happen once per bucket.
39  *
40  * Revision 1.4  1994/02/10  23:08:26  hollings
41  * Fixed list.h ++ function to work when a hash table has an element at
42  * slot zero in the table.
43  *
44  * Removed unused fields in hist class.
45  *
46  * Revision 1.3  1994/02/08  00:30:39  hollings
47  * Make libutil more compatable with ATT CC.
48  *
49  * Revision 1.2  1994/01/26  04:53:42  hollings
50  * Change to using <module>/h/.h
51  *
52  * Revision 1.1  1994/01/25  20:50:25  hollings
53  * First real version of utility library.
54  *
55  * Revision 1.4  1993/12/15  21:06:23  hollings
56  * changed initial bucket width to 0.1.
57  *
58  * Revision 1.3  1993/08/11  18:03:54  hollings
59  * removed printf for folding hist.
60  *
61  * Revision 1.2  1993/08/05  18:55:08  hollings
62  * general fixups and include format.
63  *
64  * Revision 1.1  1993/05/07  20:19:17  hollings
65  * Initial revision
66  *
67  *
68  */
69
70 #include <stdio.h>
71 #include <assert.h>
72 #include <string.h>
73 #include <stdlib.h>
74
75 #include "util/h/hist.h"
76
77 /* number of intervals at which we switch to regular histograms */
78 #define MAX_INTERVALS   15
79
80 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
81
82 int Histogram::numBins = 1000;
83 timeStamp Histogram::bucketSize = 0.1;
84 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
85 Histogram *Histogram::allHist = NULL;
86 int Histogram::lastGlobalBin = 0;
87
88 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c)
89 {
90     smooth = False;
91     lastBin = 0;
92     metricType = type;
93     intervalCount = 0;
94     intervalLimit = MAX_INTERVALS;
95     storageType = HistInterval;
96     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
97     next = allHist;
98     allHist = this;
99     dataFunc = d;
100     foldFunc = f;
101     cData = c;
102 }
103
104 /*
105  * Given an array of buckets - turn them into a histogram.
106  *
107  */
108 Histogram::Histogram(Bin *buckets, 
109                      metricStyle type, 
110                      dataCallBack d, 
111                      foldCallBack f,
112                      void *c)
113 {
114     // First call default constructor.
115     (void) Histogram(type, d, f, c);
116
117     storageType = HistBucket;
118     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
119     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
120 }
121
122 Histogram::~Histogram()
123 {
124     Histogram *lag;
125     Histogram *curr;
126
127     // remove us from allHist
128     for (curr=allHist, lag=NULL; curr; curr = curr->next) {
129         if (curr == this) {
130             break;
131         }
132         lag = curr;
133     }
134
135     if (!lag) {
136         allHist = curr->next;
137     } else {
138         lag->next = curr->next;
139     }
140
141 }
142
143 #define MAX(a, b)       ((a) > (b) ? (a):(b))
144
145 /*
146  * addInterval - add a value to a histogram from start to end.
147  *
148  * start, and end are relative to the global start time (i.e. 0.0 is the
149  *   left side of the first hist bin).
150  */
151 void Histogram::addInterval(timeStamp start, 
152                             timeStamp end, 
153                             sampleValue value, 
154                             Boolean smooth)
155 {
156     Histogram *h;
157
158     while ((end >= total_time) || (start >= total_time)) {
159         // colapse histogram.
160         foldAllHist();
161     }
162
163     lastBin = (int) (end / bucketSize);
164     lastGlobalBin = lastBin;
165     for (h=allHist; h; h=h->next) {
166         if ((h->lastBin < lastGlobalBin)) {
167             lastGlobalBin = h->lastBin;
168         }
169     }
170
171     if (storageType == HistInterval) {
172         /* convert to buckets */
173         convertToBins();
174     }
175     bucketValue(start, end, value, smooth);
176 }
177
178 void Histogram::convertToBins()
179 {
180     int i;
181     Interval *intervals;
182     Interval *currentInterval;
183
184     if (storageType == HistBucket) return;
185
186     intervals = dataPtr.intervals;
187     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
188     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
189     for (i=0; i < intervalCount; i++) {
190         currentInterval = &(intervals[i]);
191         bucketValue(currentInterval->start, currentInterval->end, 
192             currentInterval->value, smooth);
193     }
194     free(intervals);
195     intervalCount = -1;
196     intervalLimit = 0;
197     storageType = HistBucket;
198 }
199
200 void Histogram::foldAllHist()
201 {
202     int i;
203     Bin *bins;
204     Histogram *curr;
205
206     bucketSize *= 2.0;
207     total_time = (numBins * bucketSize);
208
209     lastGlobalBin = 0;
210     for (curr=allHist; curr; curr= curr->next) {
211         // fold individual hist.
212         if (curr->storageType == HistBucket) {
213             bins = curr->dataPtr.buckets;
214             for (i=0; i < numBins/2; i++) {
215                 bins[i] = (bins[i*2] + bins[i*2+1]) / 2.0;
216             }
217             curr->lastBin = i-1;
218             memset(&bins[i], '\0', (numBins - i) * sizeof(Bin));
219         }
220         if (curr->foldFunc) (curr->foldFunc)(bucketSize, curr->cData);
221     }
222 }
223
224 void Histogram::bucketValue(timeStamp start_clock, 
225                            timeStamp end_clock, 
226                            sampleValue value, 
227                            Boolean smooth)
228 {
229     register int i;
230     int first_bin, last_bin;
231     timeStamp elapsed_clock = (timeStamp) 0.0;
232     timeStamp first_bin_start, last_bin_start;
233     sampleValue amt_first_bin, amt_last_bin, amt_other_bins;
234     timeStamp time_in_first_bin, time_in_last_bin, time_in_other_bins;
235
236
237     elapsed_clock = end_clock - start_clock;
238
239     /* set starting and ending bins */
240     first_bin = (int) (start_clock / bucketSize);
241     assert(first_bin >= 0);
242     assert(first_bin <= numBins);
243     if (first_bin == numBins)
244         first_bin = numBins-1;
245     last_bin = (int) (end_clock / bucketSize);
246     assert(last_bin >= 0);
247     assert(last_bin <= numBins);
248     if (last_bin == numBins)
249         last_bin = numBins-1;
250     /* set starting times for first & last bins */
251     first_bin_start = bucketSize * first_bin;
252     last_bin_start = bucketSize  * last_bin;
253
254     if (metricType == SampledFunction) {
255         for (i=first_bin; i <= last_bin; i++) {
256             dataPtr.buckets[i] = value;
257         }
258     } else {
259         // normalize by bucket size.
260         value /= bucketSize;
261         if (last_bin == first_bin) {
262             dataPtr.buckets[first_bin] += value;
263             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
264                 /* value > 100% */
265                 smoothBins(dataPtr.buckets, first_bin, bucketSize);
266             }
267             return;
268         }
269
270         /* determine how much of the first & last bins were in this interval */
271         time_in_first_bin = bucketSize - (start_clock - first_bin_start);
272         time_in_last_bin = end_clock - last_bin_start;
273         time_in_other_bins = 
274             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
275
276         /* determine how much of value should be in each bin in the interval */
277         amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
278         amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
279         amt_other_bins = (time_in_other_bins / elapsed_clock) * value;
280         if (last_bin > first_bin+1) 
281             amt_other_bins /= (last_bin - first_bin) - 1.0;
282
283         /* add the appropriate amount of time to each bin */
284         dataPtr.buckets[first_bin] += amt_first_bin;
285         dataPtr.buckets[last_bin]  += amt_last_bin;
286         for (i=first_bin+1; i < last_bin; i++)
287             dataPtr.buckets[i]  += amt_other_bins;
288     }
289
290     /* limit absurd time values - anything over 100% is pushed back into 
291        previous buckets */
292     if (smooth) {
293         for (i = first_bin; i <= last_bin; i++) {
294             if (dataPtr.buckets[i] > bucketSize) 
295                 smoothBins(dataPtr.buckets, i, bucketSize);
296         }
297     }
298
299     // inform users about the data.
300     // make sure they want to hear about it (dataFunc)
301     //  && that we have a full bin (last_bin>first_bin)
302     if (dataFunc && (last_bin-first_bin)) {
303         (dataFunc)(&dataPtr.buckets[first_bin], 
304                    last_bin-first_bin, 
305                    first_bin, 
306                    cData);
307     }
308 }
309
310
311 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
312 {
313     int j;
314     sampleValue extra_time;
315
316     extra_time = (bins[i] - bucketSize);
317     bins[i] = bucketSize;
318     j = i - 1;
319     while ((j >= 0) && (extra_time > 0.0)) {
320         bins[j] += extra_time;
321         extra_time = 0.0;
322         if (bins[j] > bucketSize) {
323             extra_time = (bins[j] - bucketSize);
324             bins[j] = bucketSize;
325         }
326         j--;
327     }
328     if (extra_time > 0.0) {
329         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
330         abort();
331     }
332 }
333
334
335 static double splitTime(timeStamp startInterval, 
336                         timeStamp endInterval, 
337                         timeStamp startLimit, 
338                         timeStamp endLimit, 
339                         sampleValue value)
340 {
341     sampleValue time;
342     timeStamp inv_length;
343
344     inv_length = endInterval-startInterval;
345     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
346         time = value;
347     } else if (startInterval == endInterval) {  
348         /* can't split delta functions */               
349         time = 0.0;
350     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
351         /* overlaps the end */                          
352         time = value * (endLimit - startInterval) / inv_length;
353     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
354         /* overlaps the end */                          
355         time = value * (endInterval - startLimit) / inv_length;    
356     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
357         /* detail contains interval */
358         time = value * (endLimit - startLimit) / inv_length;
359     } else {
360         /* no overlap of time */
361         time = 0.0;
362     }
363     return(time);
364 }
365
366 /*
367  * Get the component of the histogram from start to end.
368  *
369  */
370 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
371 {               
372     int i;
373     Interval *cp;
374     sampleValue retVal = 0.0;
375     int first_bin, last_bin;
376     double pct_first_bin, pct_last_bin;
377
378     if (storageType == HistInterval) {
379         if (metricType == SampledFunction) {
380             // compute weight average of sample.
381             for (i=0; i < intervalCount; i++) {
382                 cp = &(dataPtr.intervals[i]);
383                 retVal += cp->value * (cp->end - cp->start);
384             }
385         } else {
386             // total over the interval.
387             for (i=0; i < intervalCount; i++) {
388                 cp = &(dataPtr.intervals[i]);
389                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
390             }
391         }
392     } else {
393         first_bin = (int) (start/bucketSize);
394         /* round up */
395         last_bin = (int) (end/bucketSize+0.5);
396         if (last_bin >= numBins) last_bin = numBins-1;
397         if (first_bin == last_bin) {
398             retVal = dataPtr.buckets[first_bin];
399         } else {
400             /* (first_bin+1)*bucketSize == time at end of first bucket */
401             pct_first_bin = (((first_bin+1)*bucketSize)-start)/bucketSize;
402             retVal += pct_first_bin * dataPtr.buckets[first_bin];
403             /* last_bin+*bucketSize == time at start of last bucket */
404             pct_last_bin = (end - last_bin*bucketSize)/bucketSize;
405             retVal += pct_last_bin * dataPtr.buckets[last_bin];
406             for (i=first_bin+1; i <= last_bin-1; i++) {
407                 retVal += dataPtr.buckets[i];
408             }
409         }
410     }
411     return(retVal * bucketSize);
412 }
413
414 sampleValue Histogram::getValue()
415 {               
416     return(getValue(0.0, numBins * bucketSize));
417 }
418
419 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
420 {
421     int i;
422     int last;
423
424     last = first + numberOfBuckets;
425     if (lastBin < last) last = lastBin;
426
427     // make sure its in bin form.
428     convertToBins();
429
430     for (i=first; i < last; i++) {
431         buckets[i-first] = dataPtr.buckets[i];
432     }
433     return(last-first);
434 }