fix to how global time is computed
[dyninst.git] / pdutil / 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.15  1995/08/01 01:56:32  newhall
20  * fix to how global time is computed
21  *
22  * Revision 1.14  1995/07/20 22:30:13  rbi
23  * Fixed a folding bug
24  *
25  * Revision 1.13  1995/07/06  01:52:13  newhall
26  * support for Histograms with non-zero start time
27  *
28  * Revision 1.12  1995/06/02  21:00:08  newhall
29  * added a NaN value generator
30  * fixed memory leaks in Histogram class
31  * added newValue member with a vector<sampleInfo *> to class sampleInfo
32  *
33  * Revision 1.11  1995/02/16  09:28:02  markc
34  * Removed compiler warnings.
35  * Changed Boolean to bool
36  *
37  * Revision 1.10  1994/06/29  02:48:31  hollings
38  * Added destructor to Histogram class.
39  *
40  * Revision 1.9  1994/05/10  03:56:47  hollings
41  * Changed hist data upcall to return array of buckets not single value.
42  *
43  * Revision 1.8  1994/04/30  21:00:03  hollings
44  * Fixed bug in fold callback that caused all fold message to go to the
45  * Histogram that caused the fold not the correct ones.
46  *
47  * Revision 1.7  1994/04/20  15:19:30  hollings
48  * Added method to get histogram buckets.
49  *
50  * Revision 1.6  1994/04/12  22:11:22  hollings
51  * removed special case of bucket a zero value since it caused upcalls not to
52  * happen.
53  *
54  * Revision 1.5  1994/03/08  17:12:29  hollings
55  * Added fold callback and changed from multiple data callbacks to one per
56  * histogram instance.  Also made the data callbacks happen once per bucket.
57  *
58  * Revision 1.4  1994/02/10  23:08:26  hollings
59  * Fixed list.h ++ function to work when a hash table has an element at
60  * slot zero in the table.
61  *
62  * Removed unused fields in hist class.
63  *
64  * Revision 1.3  1994/02/08  00:30:39  hollings
65  * Make libutil more compatable with ATT CC.
66  *
67  * Revision 1.2  1994/01/26  04:53:42  hollings
68  * Change to using <module>/h/.h
69  *
70  * Revision 1.1  1994/01/25  20:50:25  hollings
71  * First real version of utility library.
72  *
73  * Revision 1.4  1993/12/15  21:06:23  hollings
74  * changed initial bucket width to 0.1.
75  *
76  * Revision 1.3  1993/08/11  18:03:54  hollings
77  * removed printf for folding hist.
78  *
79  * Revision 1.2  1993/08/05  18:55:08  hollings
80  * general fixups and include format.
81  *
82  * Revision 1.1  1993/05/07  20:19:17  hollings
83  * Initial revision
84  *
85  *
86  */
87
88 #include <stdio.h>
89 #include <assert.h>
90 #include <string.h>
91 #include <stdlib.h>
92
93 #include "util/h/hist.h"
94
95 /* number of intervals at which we switch to regular histograms */
96 #define MAX_INTERVALS   15
97
98 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
99
100 #ifdef n_def
101 int Histogram::numBins = 1000;
102 timeStamp Histogram::bucketSize = 0.1;
103 timeStamp Histogram::total_time = (Histogram::numBins * Histogram::bucketSize);
104 Histogram *Histogram::allHist = NULL;
105 int Histogram::lastGlobalBin = 0;
106 #endif
107
108 int Histogram::numBins = 1000;
109 int Histogram::lastGlobalBin = 0;
110 timeStamp Histogram::baseBucketSize = 0.1;
111 timeStamp Histogram::globalBucketSize = 0.1;
112 vector<Histogram *> Histogram::allHist;
113
114 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c)
115 {
116     smooth = false;
117     lastBin = 0;
118     metricType = type;
119     intervalCount = 0;
120     intervalLimit = MAX_INTERVALS;
121     storageType = HistInterval;
122     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
123     allHist += this;
124     dataFunc = d;
125     foldFunc = f;
126     cData = c;
127     active = true;
128     bucketWidth = globalBucketSize; 
129     total_time = bucketWidth*numBins;
130     startTime = 0.0;
131 }
132
133 /*
134  * Given an array of buckets - turn them into a histogram.
135  *
136  */
137 Histogram::Histogram(Bin *buckets, 
138                      metricStyle type, 
139                      dataCallBack d, 
140                      foldCallBack f,
141                      void *c)
142 {
143     // First call default constructor.
144     (void) Histogram(type, d, f, c);
145
146     storageType = HistBucket;
147     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
148     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
149 }
150
151
152 // constructor for histogram that doesn't start at time 0
153 Histogram::Histogram(timeStamp start, metricStyle type, dataCallBack d, 
154                      foldCallBack f, void *c)
155 {
156     smooth = false;
157     lastBin = 0;
158     metricType = type;
159     intervalCount = 0;
160     intervalLimit = MAX_INTERVALS;
161     storageType = HistInterval;
162     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
163     allHist += this;
164     dataFunc = d;
165     foldFunc = f;
166     cData = c;
167     active = true;
168     startTime = start;
169
170     // compute bucketwidth based on start time
171     timeStamp minBucketWidth = 
172             ((lastGlobalBin*globalBucketSize)  - startTime) / numBins;    
173     for(timeStamp i = baseBucketSize; i < minBucketWidth; i *= 2.0) ; 
174     bucketWidth = i; 
175     total_time = startTime + bucketWidth*numBins;
176 }
177
178
179 Histogram::Histogram(Bin *buckets, 
180                      timeStamp start,
181                      metricStyle type, 
182                      dataCallBack d, 
183                      foldCallBack f,
184                      void *c)
185 {
186     // First call default constructor.
187     (void) Histogram(start, type, d, f, c);
188     storageType = HistBucket;
189     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
190     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
191 }
192
193 Histogram::~Histogram(){
194
195     // remove from allHist
196     for(unsigned i=0; i < allHist.size(); i++){
197         if(allHist[i] == this){
198             break;
199         }
200     }
201     for(unsigned j = i; j < (allHist.size() - 1); j++){
202         allHist[j] = allHist[j+1];
203     }
204     allHist.resize(allHist.size() - 1);
205
206     // free bin space
207     if (storageType == HistInterval) {
208         free(dataPtr.intervals);
209     }
210     else {
211         free(dataPtr.buckets);
212     }
213 }
214
215
216 #define MAX(a, b)       ((a) > (b) ? (a):(b))
217
218 /*
219  * addInterval - add a value to a histogram from start to end.
220  *
221  * start, and end are relative to the global start time (i.e. 0.0 is the
222  *   left side of the first hist bin).
223  */
224 void Histogram::addInterval(timeStamp start, 
225                             timeStamp end, 
226                             sampleValue value, 
227                             bool smooth)
228 {
229     while ((end >= total_time) || (start >= total_time)) {
230         // colapse histogram.
231         foldAllHist();
232     }
233
234     lastBin = (int) ((end - startTime) / bucketWidth);
235
236 #ifdef n_def
237     // update global info. if this histogram started at time 0
238     if(startTime == 0.0){
239         lastGlobalBin = lastBin;
240         for (unsigned i=0; i < allHist.size(); i++) {
241             if((allHist[i])->startTime == 0.0){
242                 if (((allHist[i])->lastBin < lastGlobalBin)) {
243                     lastGlobalBin = (allHist[i])->lastBin;
244             }}
245         }
246     }
247 #endif
248
249     // TODO: this should be replaced with the above code when
250     // the performance consultant is changed to correctly
251     // delete histograms that it is no longer collection 
252     // data values for
253     // change this so that lastGlobalbin is max of all lastBins
254     if(startTime == 0.0){
255         if(lastBin > lastGlobalBin)
256             lastGlobalBin = lastBin;
257         for (unsigned i=0; i < allHist.size(); i++) {
258             if(((allHist[i])->startTime == 0.0)
259                && ((allHist[i])->isActive())){
260                 if (((allHist[i])->lastBin > lastGlobalBin)) {
261                     lastGlobalBin = (allHist[i])->lastBin;
262             }}
263         }
264     }
265
266     if (storageType == HistInterval) {
267         /* convert to buckets */
268         convertToBins();
269     }
270     bucketValue(start, end, value, smooth);
271 }
272
273 void Histogram::convertToBins()
274 {
275     int i;
276     Interval *intervals;
277     Interval *currentInterval;
278
279     if (storageType == HistBucket) return;
280
281     intervals = dataPtr.intervals;
282     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
283     memset(dataPtr.buckets, '\0', sizeof(Bin)*numBins);
284     for (i=0; i < intervalCount; i++) {
285         currentInterval = &(intervals[i]);
286         bucketValue(currentInterval->start, currentInterval->end, 
287             currentInterval->value, smooth);
288     }
289     free(intervals);
290     intervalCount = -1;
291     intervalLimit = 0;
292     storageType = HistBucket;
293 }
294
295 void Histogram::foldAllHist()
296 {
297     // update global info.
298     if(startTime == 0.0){
299         globalBucketSize *= 2.0;
300         lastGlobalBin = numBins/2 - 1;
301     }
302
303     // fold all histograms with the same time base
304     for(unsigned i = 0; i < allHist.size(); i++){
305         if(((allHist[i])->startTime == startTime) 
306            && (allHist[i])->active){
307             (allHist[i])->bucketWidth *= 2.0;
308             if((allHist[i])->storageType == HistBucket){
309                 Bin *bins = (allHist[i])->dataPtr.buckets;
310                 for(unsigned j=0; j < numBins/2; j++){
311                     bins[j] = (bins[j*2] + bins[j*2+1]) / 2.0;
312                 }
313                 (allHist[i])->lastBin = j - 1; 
314                 memset(&bins[j], '\0', (numBins - j) * sizeof(Bin));
315             }
316             (allHist[i])->total_time = startTime + 
317                                        numBins*(allHist[i])->bucketWidth;
318             if((allHist[i])->foldFunc) 
319                 ((allHist[i])->foldFunc)((allHist[i])->bucketWidth, 
320                                         (allHist[i])->cData,
321                                         (allHist[i])->startTime);
322         }
323     }
324 }
325
326 void Histogram::bucketValue(timeStamp start_clock, 
327                            timeStamp end_clock, 
328                            sampleValue value, 
329                            bool smooth)
330 {
331     register int i;
332
333     // don't add values to an inactive histogram
334     if(!active) return;
335
336     timeStamp elapsed_clock = end_clock - start_clock;
337
338     /* set starting and ending bins */
339     int first_bin = (int) ((start_clock - startTime )/ bucketWidth);
340     // ignore bad values
341     if((first_bin < 0) || (first_bin > numBins)) return;
342     //assert(first_bin >= 0);
343     //assert(first_bin <= numBins);
344     if (first_bin == numBins)
345         first_bin = numBins-1;
346     int last_bin = (int) ((end_clock - startTime) / bucketWidth);
347     // ignore bad values
348     if((last_bin < 0) || (last_bin > numBins)) return;
349     // assert(last_bin >= 0);
350     // assert(last_bin <= numBins);
351     if (last_bin == numBins)
352         last_bin = numBins-1;
353     /* set starting times for first & last bins */
354     timeStamp first_bin_start = bucketWidth * first_bin;
355     timeStamp last_bin_start = bucketWidth  * last_bin;
356
357     if (metricType == SampledFunction) {
358         for (i=first_bin; i <= last_bin; i++) {
359             dataPtr.buckets[i] = value;
360         }
361     } else {
362         // normalize by bucket size.
363         value /= bucketWidth;
364         if (last_bin == first_bin) {
365             dataPtr.buckets[first_bin] += value;
366             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
367                 /* value > 100% */
368                 smoothBins(dataPtr.buckets, first_bin, bucketWidth);
369             }
370             return;
371         }
372
373         /* determine how much of the first & last bins were in this interval */
374         timeStamp time_in_first_bin = 
375                         bucketWidth - ((start_clock - startTime)- first_bin_start);
376         timeStamp time_in_last_bin = (end_clock- startTime) - last_bin_start;
377         timeStamp time_in_other_bins = 
378             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
379         // ignore bad values
380         if((time_in_first_bin < 0) || 
381            (time_in_last_bin < 0) || 
382            (time_in_other_bins < 0)) 
383             return;
384
385         /* determine how much of value should be in each bin in the interval */
386         sampleValue amt_first_bin = (time_in_first_bin / elapsed_clock) * value;
387         sampleValue amt_last_bin  = (time_in_last_bin  / elapsed_clock) * value;
388         sampleValue amt_other_bins = 
389                                 (time_in_other_bins / elapsed_clock) * value;
390         if (last_bin > first_bin+1) 
391             amt_other_bins /= (last_bin - first_bin) - 1.0;
392
393         /* add the appropriate amount of time to each bin */
394         dataPtr.buckets[first_bin] += amt_first_bin;
395         dataPtr.buckets[last_bin]  += amt_last_bin;
396         for (i=first_bin+1; i < last_bin; i++)
397             dataPtr.buckets[i]  += amt_other_bins;
398     }
399
400     /* limit absurd time values - anything over 100% is pushed back into 
401        previous buckets */
402     if (smooth) {
403         for (i = first_bin; i <= last_bin; i++) {
404             if (dataPtr.buckets[i] > bucketWidth) 
405                 smoothBins(dataPtr.buckets, i, bucketWidth);
406         }
407     }
408
409     // inform users about the data.
410     // make sure they want to hear about it (dataFunc)
411     //  && that we have a full bin (last_bin>first_bin)
412     if (dataFunc && (last_bin-first_bin)) {
413         (dataFunc)(&dataPtr.buckets[first_bin], 
414                    startTime,
415                    last_bin-first_bin, 
416                    first_bin, 
417                    cData);
418     }
419 }
420
421
422 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
423 {
424     int j;
425     sampleValue extra_time;
426
427     extra_time = (bins[i] - bucketSize);
428     bins[i] = bucketSize;
429     j = i - 1;
430     while ((j >= 0) && (extra_time > 0.0)) {
431         bins[j] += extra_time;
432         extra_time = 0.0;
433         if (bins[j] > bucketSize) {
434             extra_time = (bins[j] - bucketSize);
435             bins[j] = bucketSize;
436         }
437         j--;
438     }
439     if (extra_time > 0.0) {
440         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
441         abort();
442     }
443 }
444
445
446 static double splitTime(timeStamp startInterval, 
447                         timeStamp endInterval, 
448                         timeStamp startLimit, 
449                         timeStamp endLimit, 
450                         sampleValue value)
451 {
452     sampleValue time;
453     timeStamp inv_length;
454
455     inv_length = endInterval-startInterval;
456     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
457         time = value;
458     } else if (startInterval == endInterval) {  
459         /* can't split delta functions */               
460         time = 0.0;
461     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
462         /* overlaps the end */                          
463         time = value * (endLimit - startInterval) / inv_length;
464     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
465         /* overlaps the end */                          
466         time = value * (endInterval - startLimit) / inv_length;    
467     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
468         /* detail contains interval */
469         time = value * (endLimit - startLimit) / inv_length;
470     } else {
471         /* no overlap of time */
472         time = 0.0;
473     }
474     return(time);
475 }
476
477 /*
478  * Get the component of the histogram from start to end.
479  *
480  */
481 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
482 {               
483     int i;
484     Interval *cp;
485     sampleValue retVal = 0.0;
486     int first_bin, last_bin;
487     double pct_first_bin, pct_last_bin;
488
489     if (storageType == HistInterval) {
490         if (metricType == SampledFunction) {
491             // compute weight average of sample.
492             for (i=0; i < intervalCount; i++) {
493                 cp = &(dataPtr.intervals[i]);
494                 retVal += cp->value * (cp->end - cp->start);
495             }
496         } else {
497             // total over the interval.
498             for (i=0; i < intervalCount; i++) {
499                 cp = &(dataPtr.intervals[i]);
500                 retVal += splitTime(cp->start, cp->end, start, end, cp->value);
501             }
502         }
503     } else {
504         first_bin = (int) (start/bucketWidth);
505         /* round up */
506         last_bin = (int) (end/bucketWidth+0.5);
507         if (last_bin >= numBins) last_bin = numBins-1;
508         if (first_bin == last_bin) {
509             retVal = dataPtr.buckets[first_bin];
510         } else {
511             /* (first_bin+1)*bucketWidth == time at end of first bucket */
512             pct_first_bin = (((first_bin+1)*bucketWidth)-start)/bucketWidth;
513             retVal += pct_first_bin * dataPtr.buckets[first_bin];
514             /* last_bin+*bucketWidth == time at start of last bucket */
515             pct_last_bin = (end - last_bin*bucketWidth)/bucketWidth;
516             retVal += pct_last_bin * dataPtr.buckets[last_bin];
517             for (i=first_bin+1; i <= last_bin-1; i++) {
518                 retVal += dataPtr.buckets[i];
519             }
520         }
521     }
522     return(retVal * bucketWidth);
523 }
524
525 sampleValue Histogram::getValue()
526 {               
527     return(getValue(0.0, numBins * bucketWidth));
528 }
529
530 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
531 {
532     int i;
533     int last;
534
535     last = first + numberOfBuckets;
536     if (lastBin < last) last = lastBin;
537
538     // make sure its in bin form.
539     convertToBins();
540
541     for (i=first; i < last; i++) {
542         buckets[i-first] = dataPtr.buckets[i];
543     }
544     return(last-first);
545 }