+ Added inclusion of <math.h> as makenan.h no longer includes it
[dyninst.git] / common / src / hist.C
1 /*
2  * Copyright (c) 1996 Barton P. Miller
3  * 
4  * We provide the Paradyn Parallel Performance Tools (below
5  * described as Paradyn") on an AS IS basis, and do not warrant its
6  * validity or performance.  We reserve the right to update, modify,
7  * or discontinue this software at any time.  We shall have no
8  * obligation to supply such updates or modifications or any other
9  * form of support to you.
10  * 
11  * This license is for research uses.  For such uses, there is no
12  * charge. We define "research use" to mean you may freely use it
13  * inside your organization for whatever purposes you see fit. But you
14  * may not re-distribute Paradyn or parts of Paradyn, in any form
15  * source or binary (including derivatives), electronic or otherwise,
16  * to any other organization or entity without our permission.
17  * 
18  * (for other uses, please contact us at paradyn@cs.wisc.edu)
19  * 
20  * All warranties, including without limitation, any warranty of
21  * merchantability or fitness for a particular purpose, are hereby
22  * excluded.
23  * 
24  * By your use of Paradyn, you understand and agree that we (or any
25  * other person or entity with proprietary rights in Paradyn) are
26  * under no obligation to provide either maintenance services,
27  * update services, notices of latent defects, or correction of
28  * defects for Paradyn.
29  * 
30  * Even if advised of the possibility of such damages, under no
31  * circumstances shall we (or any other person or entity with
32  * proprietary rights in the software licensed hereunder) be liable
33  * to you or any third party for direct, indirect, or consequential
34  * damages of any character regardless of type of action, including,
35  * without limitation, loss of profits, loss of use, loss of good
36  * will, or computer failure or malfunction.  You agree to indemnify
37  * us (and any other person or entity with proprietary rights in the
38  * software licensed hereunder) for any and all liability it may
39  * incur to third parties resulting from your use of Paradyn.
40  */
41
42 // hist.C - routines to manage histograms.
43 // $Id: hist.C,v 1.35 1999/10/19 05:11:11 nick Exp $
44
45 #include "util/h/headers.h"
46 #include "util/h/hist.h"
47 #include <math.h>
48
49 /* number of intervals at which we switch to regular histograms */
50 #define MAX_INTERVALS   15
51
52 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
53
54 int Histogram::numBins = 1000;
55 int Histogram::lastGlobalBin = 0;
56 timeStamp Histogram::baseBucketSize = BASEBUCKETWIDTH;
57 timeStamp Histogram::globalBucketSize = BASEBUCKETWIDTH;
58 vector<Histogram *> Histogram::allHist;
59
60 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c,
61                      bool globalFlag)
62 :globalData(globalFlag)
63 {
64     smooth = false;
65     lastBin = 0;
66     metricType = type;
67     intervalCount = 0;
68     intervalLimit = MAX_INTERVALS;
69     storageType = HistInterval;
70     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
71     allHist += this;
72     dataFunc = d;
73     foldFunc = f;
74     cData = c;
75     active = true;
76     fold_on_inactive = false;
77     bucketWidth = globalBucketSize; 
78     total_time = bucketWidth*numBins;
79     startTime = 0.0;
80 }
81
82 /*
83  * Given an array of buckets - turn them into a histogram.
84  *
85  */
86 Histogram::Histogram(Bin *buckets, 
87                      metricStyle type, 
88                      dataCallBack d, 
89                      foldCallBack f,
90                      void *c,
91                      bool globalFlag)
92 {
93     // First call default constructor.
94     (void) Histogram(type, d, f, c, globalFlag);
95
96     storageType = HistBucket;
97     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
98     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
99 }
100
101
102 // constructor for histogram that doesn't start at time 0
103 Histogram::Histogram(timeStamp start, metricStyle type, dataCallBack d, 
104                      foldCallBack f, void *c, bool globalFlag)
105 :globalData(globalFlag)
106 {
107     smooth = false;
108     lastBin = 0;
109     metricType = type;
110     intervalCount = 0;
111     intervalLimit = MAX_INTERVALS;
112     storageType = HistInterval;
113     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
114     dataFunc = d;
115     foldFunc = f;
116     cData = c;
117     active = true;
118     fold_on_inactive = false;
119     startTime = start;
120
121     // try to find an active histogram with the same start time 
122     // and use its bucket width  for "bucketWidth", otherwise, compute
123     // a value for "bucketWidth" based on startTime and global time
124     bool found = false;
125     for(unsigned i = 0; i < allHist.size(); i++){
126         if(((allHist[i])->startTime == startTime)&&(allHist[i])->active){
127             found = true;
128             bucketWidth = (allHist[i])->bucketWidth;
129             break;
130     } }
131     if(!found){
132         // compute bucketwidth based on start time
133         timeStamp minBucketWidth = 
134                 ((lastGlobalBin*globalBucketSize)  - startTime) / numBins;    
135         timeStamp i2 = baseBucketSize;
136         for(; i2 < minBucketWidth; i2 *= 2.0) ; 
137         bucketWidth = i2; 
138     }
139
140     allHist += this;
141     total_time = startTime + bucketWidth*numBins;
142 }
143
144
145 Histogram::Histogram(Bin *buckets, 
146                      timeStamp start,
147                      metricStyle type, 
148                      dataCallBack d, 
149                      foldCallBack f,
150                      void *c,
151                      bool globalFlag)
152 {
153     // First call default constructor.
154     (void) Histogram(start, type, d, f, c, globalFlag);
155     storageType = HistBucket;
156     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
157     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
158 }
159
160 Histogram::~Histogram(){
161
162     // remove from allHist
163     unsigned i=0;
164     for(; i < allHist.size(); i++){
165         if(allHist[i] == this){
166             break;
167         }
168     }
169     for(unsigned j = i; j < (allHist.size() - 1); j++){
170         allHist[j] = allHist[j+1];
171     }
172     allHist.resize(allHist.size() - 1);
173
174     // free bin space
175     if (storageType == HistInterval) {
176         free(dataPtr.intervals);
177     }
178     else {
179         delete [] dataPtr.buckets;
180     }
181 }
182
183 #if !defined(MAX)
184 #define MAX(a, b)       ((a) > (b) ? (a):(b))
185 #endif
186
187 /*
188  * addInterval - add a value to a histogram from start to end.
189  *
190  * start, and end are relative to the global start time (i.e. 0.0 is the
191  *   left side of the first hist bin).
192  */
193 void Histogram::addInterval(timeStamp start, 
194                             timeStamp end, 
195                             sampleValue value, 
196                             bool smooth)
197 {
198     while ((end >= total_time) || (start >= total_time)) {
199         // colapse histogram.
200         foldAllHist();
201     }
202
203     lastBin = (int) ((end - startTime) / bucketWidth);
204
205 #ifdef n_def
206     // update global info. if this histogram started at time 0
207     if(startTime == 0.0){
208         lastGlobalBin = lastBin;
209         for (unsigned i=0; i < allHist.size(); i++) {
210             if((allHist[i])->startTime == 0.0){
211                 if (((allHist[i])->lastBin < lastGlobalBin)) {
212                     lastGlobalBin = (allHist[i])->lastBin;
213             }}
214         }
215     }
216 #endif
217
218     // TODO: this should be replaced with the above code when
219     // the performance consultant is changed to correctly
220     // delete histograms that it is no longer collection 
221     // data values for
222     // change this so that lastGlobalbin is max of all lastBins
223     if (startTime == 0.0) {
224         if(lastBin > lastGlobalBin)
225             lastGlobalBin = lastBin;
226
227         const unsigned all_hist_size = allHist.size();
228         for (unsigned i=0; i < all_hist_size; i++) {
229             Histogram *theHist = allHist[i]; // a time saver; call operator[] just once
230
231             if (theHist->startTime == 0.0 && theHist->isActive())
232                 if (theHist->lastBin > lastGlobalBin)
233                     lastGlobalBin = theHist->lastBin;
234         }
235     }
236
237     if (storageType == HistInterval) {
238         /* convert to buckets */
239         convertToBins();
240     }
241     bucketValue(start, end, value, smooth);
242 }
243
244 void Histogram::convertToBins()
245 {
246     int i;
247     Interval *intervals;
248     Interval *currentInterval;
249
250     if (storageType == HistBucket) return;
251
252     intervals = dataPtr.intervals;
253     dataPtr.intervals = 0;
254     dataPtr.buckets = new Bin[numBins];
255     for(i = 0; i < numBins; i++){
256         dataPtr.buckets[i] = PARADYN_NaN; 
257     }
258
259     for (i=0; i < intervalCount; i++) {
260         currentInterval = &(intervals[i]);
261         bucketValue(currentInterval->start, currentInterval->end, 
262             currentInterval->value, smooth);
263     }
264     free(intervals);
265     intervalCount = -1;
266     intervalLimit = 0;
267     storageType = HistBucket;
268 }
269
270 void Histogram::foldAllHist()
271 {
272     // update global info.
273     if(startTime == 0.0){
274         globalBucketSize *= 2.0;
275         lastGlobalBin = numBins/2 - 1;
276     }
277     timeStamp newBucketWidth = bucketWidth*2.0;
278
279     // fold all histograms with the same time base
280     for(unsigned i = 0; i < allHist.size(); i++){
281         if(((allHist[i])->startTime == startTime)  // has same base time and 
282            && ((allHist[i])->active                // either, histogram active
283            || (allHist[i])->fold_on_inactive)){    // or fold on inactive set 
284
285           // don't fold this histogram if it has already folded
286           // This can happen to histograms that are created right
287           // after a fold, so that the initial bucket width may 
288           // not be correct and then the first data values will cause
289           // another fold...in this case we only want to fold the
290           // histograms that were not folded in the first round.  
291           if((allHist[i])->bucketWidth < newBucketWidth) {
292               (allHist[i])->bucketWidth *= 2.0;
293               if((allHist[i])->storageType == HistBucket){
294                   int j;
295                   Bin *bins = (allHist[i])->dataPtr.buckets;
296                   int last_bin = -1;
297                   for(j=0; j < numBins/2; j++){
298                       if(!isnan(bins[j*2+1])){   // both are not NaN
299                           bins[j] = (bins[j*2] + bins[j*2+1]) / 2.0F;
300                       }
301                       else if(!isnan(bins[j*2])){  // one is NaN
302                           bins[j] = (bins[j*2])/2.0F;   
303                           if(last_bin == -1) last_bin = j;
304                       }
305                       else {  // both are NaN
306                           bins[j] = PARADYN_NaN;
307                           if(last_bin == -1) last_bin = j;
308                       }
309                   }
310                   if(last_bin == -1) last_bin = j-1;
311                   (allHist[i])->lastBin = last_bin; 
312                   for(int k=numBins/2; k<numBins; k++){
313                       bins[k] = PARADYN_NaN;
314                   }
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])->globalData);
322           }
323         }
324     }
325 }
326
327 void Histogram::bucketValue(timeStamp start_clock, 
328                            timeStamp end_clock, 
329                            sampleValue value, 
330                            bool smooth)
331 {
332     register int i;
333
334     // don't add values to an inactive histogram
335     if(!active) return;
336
337     timeStamp elapsed_clock = end_clock - start_clock;
338
339     /* set starting and ending bins */
340     int first_bin = (int) ((start_clock - startTime )/ bucketWidth);
341
342     // ignore bad values
343     if((first_bin < 0) || (first_bin > numBins)) return;
344     if (first_bin == numBins)
345         first_bin = numBins-1;
346     int last_bin = (int) ((end_clock - startTime) / bucketWidth);
347
348     // ignore bad values
349     if((last_bin < 0) || (last_bin > numBins)) return;
350     if (last_bin == numBins)
351         last_bin = numBins-1;
352
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 /= (sampleValue)bucketWidth;
364         if (last_bin == first_bin) {
365             if(isnan(dataPtr.buckets[first_bin])){ 
366                 dataPtr.buckets[first_bin] = 0.0;
367             }
368             dataPtr.buckets[first_bin] += value;
369             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
370                 /* value > 100% */
371                 smoothBins(dataPtr.buckets, first_bin, bucketWidth);
372             }
373             return;
374         }
375
376         /* determine how much of the first & last bins were in this interval */
377         timeStamp time_in_first_bin = 
378                         bucketWidth - ((start_clock - startTime)- first_bin_start);
379         timeStamp time_in_last_bin = (end_clock- startTime) - last_bin_start;
380         timeStamp time_in_other_bins = 
381             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
382         // ignore bad values
383         if((time_in_first_bin < 0) || 
384            (time_in_last_bin < 0) || 
385            (time_in_other_bins < 0)) 
386             return;
387
388         /* determine how much of value should be in each bin in the interval */
389         sampleValue amt_first_bin = 
390                 (sampleValue)(time_in_first_bin / elapsed_clock) * value;
391         sampleValue amt_last_bin  = 
392                 (sampleValue)(time_in_last_bin  / elapsed_clock) * value;
393         sampleValue amt_other_bins = 
394                 (sampleValue)(time_in_other_bins / elapsed_clock) * value;
395         if (last_bin > first_bin+1) 
396             amt_other_bins /= (last_bin - first_bin) - 1.0F;
397
398         // if bins contain NaN values set them to 0 before adding new value
399         if(isnan(dataPtr.buckets[first_bin])) 
400             dataPtr.buckets[first_bin] = 0.0;
401         if(isnan(dataPtr.buckets[last_bin])) 
402             dataPtr.buckets[last_bin] = 0.0;
403
404         /* add the appropriate amount of time to each bin */
405         dataPtr.buckets[first_bin] += amt_first_bin;
406         dataPtr.buckets[last_bin]  += amt_last_bin;
407         for (i=first_bin+1; i < last_bin; i++){
408             if(isnan(dataPtr.buckets[i])) 
409                 dataPtr.buckets[i] = 0.0;
410             dataPtr.buckets[i]  += amt_other_bins;
411         }
412     }
413
414     /* limit absurd time values - anything over 100% is pushed back into 
415        previous buckets */
416     if (smooth) {
417         for (i = first_bin; i <= last_bin; i++) {
418             if (dataPtr.buckets[i] > bucketWidth) 
419                 smoothBins(dataPtr.buckets, i, bucketWidth);
420         }
421     }
422
423     // inform users about the data.
424     // make sure they want to hear about it (dataFunc)
425     //  && that we have a full bin (last_bin>first_bin)
426     if (dataFunc && (last_bin-first_bin)) {
427         (dataFunc)(&dataPtr.buckets[first_bin], 
428                    startTime,
429                    last_bin-first_bin, 
430                    first_bin, 
431                    cData,
432                    globalData);
433     }
434 }
435
436
437 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
438 {
439     int j;
440     sampleValue extra_time;
441
442     extra_time = (sampleValue)(bins[i] - bucketSize);
443     bins[i] = (sampleValue)bucketSize;
444     j = i - 1;
445     while ((j >= 0) && (extra_time > 0.0)) {
446         bins[j] += extra_time;
447         extra_time = 0.0;
448         if (bins[j] > bucketSize) {
449             extra_time = (sampleValue)(bins[j] - bucketSize);
450             bins[j] = (sampleValue)bucketSize;
451         }
452         j--;
453     }
454     if (extra_time > 0.0) {
455         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
456         abort();
457     }
458 }
459
460
461 static double splitTime(timeStamp startInterval, 
462                         timeStamp endInterval, 
463                         timeStamp startLimit, 
464                         timeStamp endLimit, 
465                         sampleValue value)
466 {
467     sampleValue time;
468     timeStamp inv_length;
469
470     inv_length = endInterval-startInterval;
471     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
472         time = value;
473     } else if (startInterval == endInterval) {  
474         /* can't split delta functions */               
475         time = 0.0;
476     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
477         /* overlaps the end */                          
478         time = (sampleValue)(value * (endLimit - startInterval) / inv_length);
479     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
480         /* overlaps the end */                          
481         time = (sampleValue)(value * (endInterval - startLimit) / inv_length);
482     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
483         /* detail contains interval */
484         time = (sampleValue)(value * (endLimit - startLimit) / inv_length);
485     } else {
486         /* no overlap of time */
487         time = 0.0;
488     }
489     return(time);
490 }
491
492 /*
493  * Get the component of the histogram from start to end.
494  *
495  */
496 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
497 {               
498     int i;
499     Interval *cp;
500     sampleValue retVal = 0.0;
501     int first_bin, last_bin;
502     double pct_first_bin, pct_last_bin;
503
504     if (storageType == HistInterval) {
505         if (metricType == SampledFunction) {
506             // compute weight average of sample.
507             for (i=0; i < intervalCount; i++) {
508                 cp = &(dataPtr.intervals[i]);
509                 retVal += (sampleValue)(cp->value * (cp->end - cp->start));
510             }
511         } else {
512             // total over the interval.
513             for (i=0; i < intervalCount; i++) {
514                 cp = &(dataPtr.intervals[i]);
515                 retVal += (sampleValue)splitTime(cp->start, cp->end, start, end, cp->value);
516             }
517         }
518     } else {
519         first_bin = (int) (start/bucketWidth);
520         /* round up */
521         last_bin = (int) (end/bucketWidth+0.5);
522         if (last_bin >= numBins) last_bin = numBins-1;
523         if (first_bin == last_bin) {
524             retVal = dataPtr.buckets[first_bin];
525         } else {
526             /* (first_bin+1)*bucketWidth == time at end of first bucket */
527             pct_first_bin = (((first_bin+1)*bucketWidth)-start)/bucketWidth;
528             retVal += (sampleValue)(pct_first_bin * dataPtr.buckets[first_bin]);
529             /* last_bin+*bucketWidth == time at start of last bucket */
530             pct_last_bin = (end - last_bin*bucketWidth)/bucketWidth;
531             retVal += (sampleValue)(pct_last_bin * dataPtr.buckets[last_bin]);
532             for (i=first_bin+1; i <= last_bin-1; i++) {
533                 retVal += dataPtr.buckets[i];
534             }
535         }
536     }
537     return((sampleValue)(retVal * bucketWidth));
538 }
539
540 sampleValue Histogram::getValue()
541 {               
542     return(getValue(0.0, numBins * bucketWidth));
543 }
544
545 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
546 {
547     int i;
548     int last;
549
550     last = first + numberOfBuckets;
551     if (lastBin < last) last = lastBin;
552
553     // make sure its in bin form.
554     convertToBins();
555
556     assert(first >= 0);
557     assert(last <= lastBin); 
558     for (i=first; i < last; i++) {
559         float temp = dataPtr.buckets[i];
560         buckets[i-first] = temp;
561     }
562     return(last-first);
563 }