Changed args for RPC_undo_arg_list to reference types.
[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.4  1994/02/10 23:08:26  hollings
20  * Fixed list.h ++ function to work when a hash table has an element at
21  * slot zero in the table.
22  *
23  * Removed unused fields in hist class.
24  *
25  * Revision 1.3  1994/02/08  00:30:39  hollings
26  * Make libutil more compatable with ATT CC.
27  *
28  * Revision 1.2  1994/01/26  04:53:42  hollings
29  * Change to using <module>/h/*.h
30  *
31  * Revision 1.1  1994/01/25  20:50:25  hollings
32  * First real version of utility library.
33  *
34  * Revision 1.4  1993/12/15  21:06:23  hollings
35  * changed initial bucket width to 0.1.
36  *
37  * Revision 1.3  1993/08/11  18:03:54  hollings
38  * removed printf for folding hist.
39  *
40  * Revision 1.2  1993/08/05  18:55:08  hollings
41  * general fixups and include format.
42  *
43  * Revision 1.1  1993/05/07  20:19:17  hollings
44  * Initial revision
45  *
46  *
47  */
48
49 #include <stdio.h>
50 #include <assert.h>
51 #include <string.h>
52 #include <stdlib.h>
53
54 #include "util/h/hist.h"
55
56 /* number of intervals at which we switch to regular histograms */
57 #define MAX_INTERVALS   15
58
59 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
60
61 int Histogram::numBins = 1000;
62 timeStamp Histogram::bucketSize = 0.1;
63 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
64 Histogram *Histogram::allHist = NULL;
65 int Histogram::lastGlobalBin = 0;
66
67 Histogram::Histogram(metricStyle type)
68 {
69     smooth = False;
70     lastBin = 0;
71     metricType = type;
72     intervalCount = 0;
73     intervalLimit = MAX_INTERVALS;
74     storageType = HistInterval;
75     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
76     next = allHist;
77     allHist = this;
78 }
79
80 /*
81  * Given an array of buckets - turn them into a histogram.
82  *
83  */
84 Histogram::Histogram(Bin *buckets, metricStyle type)
85 {
86     // First call default constructor.
87     (void) Histogram(type);
88
89     storageType = HistBucket;
90     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
91     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
92 }
93
94 #define MAX(a, b)       ((a) > (b) ? (a):(b))
95
96 /*
97  * addInterval - add a value to a histogram from start to end.
98  *
99  * start, and end are relative to the global start time (i.e. 0.0 is the
100  *   left side of the first hist bin).
101  */
102 void Histogram::addInterval(timeStamp start, 
103                             timeStamp end, 
104                             sampleValue value, 
105                             Boolean smooth)
106 {
107     Histogram *h;
108     List<HistogramSubscriber*> currS;
109     Interval *currentInterval;
110
111
112     while ((end >= total_time) || (start >= total_time)) {
113         // colapse histogram.
114         foldAllHist();
115     }
116
117     lastBin = (int) (end / bucketSize);
118     lastGlobalBin = lastBin;
119     for (h=allHist; h; h=h->next) {
120         if ((h->lastBin < lastGlobalBin)) {
121             lastGlobalBin = h->lastBin;
122         }
123     }
124
125     if (value == 0.0) return;
126
127     if (storageType == HistInterval) {
128         if (intervalCount == intervalLimit) {
129             intervalLimit *= 2;
130             if (intervalLimit * sizeof(Interval) < 
131                 numBins * sizeof(Bin)) {
132                 dataPtr.intervals = (Interval *) 
133                     realloc(dataPtr.intervals, 
134                     sizeof(Interval)*intervalLimit);
135                     goto normal;
136             } else {
137                 /* convert to buckets */
138                 convertToBins();
139                 bucketValue(start, end, value, smooth);
140             }
141         } else {
142 normal:
143             currentInterval = &(dataPtr.intervals[intervalCount]);
144             assert(start >= 0.0);
145             assert(start <= total_time);
146             currentInterval->start = start;
147
148             assert(end >= 0.0);
149             assert(end <= total_time);
150             currentInterval->end = end;
151
152             currentInterval->value = value;
153             intervalCount++;
154         }
155     } else {
156         bucketValue(start, end, value, smooth);
157     }
158     for (currS = subscribers; *currS; currS++) {
159         (*currS)->callBack(HistNewValue, end, (*currS)->userData);
160     }
161 }
162
163 void Histogram::convertToBins()
164 {
165     int i;
166     Interval *intervals;
167     Interval *currentInterval;
168
169     if (storageType == HistBucket) return;
170
171     intervals = dataPtr.intervals;
172     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
173     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
174     for (i=0; i < intervalCount; i++) {
175         currentInterval = &(intervals[i]);
176         bucketValue(currentInterval->start, currentInterval->end, 
177             currentInterval->value, smooth);
178     }
179     free(intervals);
180     intervalCount = -1;
181     intervalLimit = 0;
182     storageType = HistBucket;
183 }
184
185 void Histogram::foldAllHist()
186 {
187     int i;
188     Bin *bins;
189     Histogram *curr;
190     List<HistogramSubscriber*> currS;
191
192
193     bucketSize *= 2.0;
194     total_time = (numBins * bucketSize);
195
196     lastGlobalBin = 0;
197     for (curr=allHist; curr; curr= curr->next) {
198         // fold individual hist.
199         if (curr->storageType == HistBucket) {
200             bins = curr->dataPtr.buckets;
201             for (i=0; i < numBins/2; i++) {
202                 bins[i] = bins[i*2] + bins[i*2+1];
203             }
204             curr->lastBin = i-1;
205             memset(&bins[i], '\0', (numBins - i) * sizeof(Bin));
206         }
207         for (currS = curr->subscribers; *currS; currS++) {
208             (*currS)->callBack(HistNewTimeBase, bucketSize, (*currS)->userData);
209         }
210     }
211 }
212
213 int Histogram::subscribe(timeStamp maxRate, 
214                            subscriberCallBack func, 
215                            void *userData)
216 {
217     HistogramSubscriber *curr;
218
219     curr = new HistogramSubscriber(maxRate, func, userData);
220     subscribers.add(curr);
221     return((int) curr);
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 * bucketSize;
257         }
258     } else {
259         if (last_bin == first_bin) {
260             dataPtr.buckets[first_bin] += value;
261             if (smooth && (dataPtr.buckets[first_bin] > bucketSize)) {
262                 /* value > 100% */
263                 smoothBins(dataPtr.buckets, first_bin, bucketSize);
264             }
265             return;
266         }
267
268         /* determine how much of the first & last bins were in this interval */
269         time_in_first_bin = bucketSize - (start_clock - first_bin_start);
270         time_in_last_bin = end_clock - last_bin_start;
271         time_in_other_bins = 
272             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
273
274         /* determine how much of value should be in each bin in the interval */
275         amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
276         amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
277         amt_other_bins = (time_in_other_bins / elapsed_clock) * value;
278         if (last_bin > first_bin+1) 
279             amt_other_bins /= (last_bin - first_bin) - 1.0;
280
281         /* add the appropriate amount of time to each bin */
282         dataPtr.buckets[first_bin] += amt_first_bin;
283         dataPtr.buckets[last_bin]  += amt_last_bin;
284         for (i=first_bin+1; i < last_bin; i++)
285             dataPtr.buckets[i]  += amt_other_bins;
286     }
287
288     /* limit absurd time values - anything over 100% is pushed back into 
289        previous buckets */
290     if (smooth) {
291         for (i = first_bin; i <= last_bin; i++) {
292             if (dataPtr.buckets[i] > bucketSize) 
293                 smoothBins(dataPtr.buckets, i, bucketSize);
294         }
295     }
296 }
297
298
299 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
300 {
301     int j;
302     sampleValue extra_time;
303
304     extra_time = (bins[i] - bucketSize);
305     bins[i] = bucketSize;
306     j = i - 1;
307     while ((j >= 0) && (extra_time > 0.0)) {
308         bins[j] += extra_time;
309         extra_time = 0.0;
310         if (bins[j] > bucketSize) {
311             extra_time = (bins[j] - bucketSize);
312             bins[j] = bucketSize;
313         }
314         j--;
315     }
316     if (extra_time > 0.0) {
317         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
318         abort();
319     }
320 }
321
322
323 static double splitTime(timeStamp startInterval, 
324                         timeStamp endInterval, 
325                         timeStamp startLimit, 
326                         timeStamp endLimit, 
327                         sampleValue value)
328 {
329     sampleValue time;
330     timeStamp inv_length;
331
332     inv_length = endInterval-startInterval;
333     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
334         time = value;
335     } else if (startInterval == endInterval) {  
336         /* can't split delta functions */               
337         time = 0.0;
338     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
339         /* overlaps the end */                          
340         time = value * (endLimit - startInterval) / inv_length;
341     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
342         /* overlaps the end */                          
343         time = value * (endInterval - startLimit) / inv_length;    
344     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
345         /* detail contains interval */
346         time = value * (endLimit - startLimit) / inv_length;
347     } else {
348         /* no overlap of time */
349         time = 0.0;
350     }
351     return(time);
352 }
353
354 /*
355  * Get the component of the histogram from start to end.
356  *
357  */
358 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
359 {               
360     int i;
361     Interval *cp;
362     sampleValue retVal = 0.0;
363     int first_bin, last_bin;
364     double pct_first_bin, pct_last_bin;
365
366     if (storageType == HistInterval) {
367         if (metricType == SampledFunction) {
368             // compute weight average of sample.
369             for (i=0; i < intervalCount; i++) {
370                 cp = &(dataPtr.intervals[i]);
371                 retVal += cp->value * (cp->end - cp->start);
372             }
373         } else {
374             // total over the interval.
375             for (i=0; i < intervalCount; i++) {
376                 cp = &(dataPtr.intervals[i]);
377                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
378             }
379         }
380     } else {
381         first_bin = (int) (start/bucketSize);
382         /* round up */
383         last_bin = (int) (end/bucketSize+0.5);
384         if (last_bin >= numBins) last_bin = numBins-1;
385         if (first_bin == last_bin) {
386             retVal = dataPtr.buckets[first_bin];
387         } else {
388             /* (first_bin+1)*bucketSize == time at end of first bucket */
389             pct_first_bin = (((first_bin+1)*bucketSize)-start)/bucketSize;
390             retVal += pct_first_bin * dataPtr.buckets[first_bin];
391             /* last_bin+*bucketSize == time at start of last bucket */
392             pct_last_bin = (end - last_bin*bucketSize)/bucketSize;
393             retVal += pct_last_bin * dataPtr.buckets[last_bin];
394             for (i=first_bin+1; i <= last_bin-1; i++) {
395                 retVal += dataPtr.buckets[i];
396             }
397         }
398     }
399     return(retVal);
400 }
401
402 sampleValue Histogram::getValue()
403 {               
404     return(getValue(0.0, numBins * bucketSize));
405 }
406
407 HistogramSubscriber::HistogramSubscriber(timeStamp max, 
408                                          subscriberCallBack func, 
409                                          void *u)
410 {
411     interval = max;
412     userData = u;
413     callBack = func;
414 }