- added support for (mips-sgi-irix6.4) native compiler build
[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.33 1999/08/09 05:45:05 csserra Exp $
44
45 #include "util/h/headers.h"
46 #include "util/h/hist.h"
47
48 /* number of intervals at which we switch to regular histograms */
49 #define MAX_INTERVALS   15
50
51 static void smoothBins(Bin *bins, int i, timeStamp bucketSize);
52
53 int Histogram::numBins = 1000;
54 int Histogram::lastGlobalBin = 0;
55 timeStamp Histogram::baseBucketSize = BASEBUCKETWIDTH;
56 timeStamp Histogram::globalBucketSize = BASEBUCKETWIDTH;
57 vector<Histogram *> Histogram::allHist;
58
59 Histogram::Histogram(metricStyle type, dataCallBack d, foldCallBack f, void *c,
60                      bool globalFlag)
61 :globalData(globalFlag)
62 {
63     smooth = false;
64     lastBin = 0;
65     metricType = type;
66     intervalCount = 0;
67     intervalLimit = MAX_INTERVALS;
68     storageType = HistInterval;
69     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
70     allHist += this;
71     dataFunc = d;
72     foldFunc = f;
73     cData = c;
74     active = true;
75     fold_on_inactive = false;
76     bucketWidth = globalBucketSize; 
77     total_time = bucketWidth*numBins;
78     startTime = 0.0;
79 }
80
81 /*
82  * Given an array of buckets - turn them into a histogram.
83  *
84  */
85 Histogram::Histogram(Bin *buckets, 
86                      metricStyle type, 
87                      dataCallBack d, 
88                      foldCallBack f,
89                      void *c,
90                      bool globalFlag)
91 {
92     // First call default constructor.
93     (void) Histogram(type, d, f, c, globalFlag);
94
95     storageType = HistBucket;
96     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
97     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
98 }
99
100
101 // constructor for histogram that doesn't start at time 0
102 Histogram::Histogram(timeStamp start, metricStyle type, dataCallBack d, 
103                      foldCallBack f, void *c, bool globalFlag)
104 :globalData(globalFlag)
105 {
106     smooth = false;
107     lastBin = 0;
108     metricType = type;
109     intervalCount = 0;
110     intervalLimit = MAX_INTERVALS;
111     storageType = HistInterval;
112     dataPtr.intervals = (Interval *) calloc(sizeof(Interval)*intervalLimit, 1);
113     dataFunc = d;
114     foldFunc = f;
115     cData = c;
116     active = true;
117     fold_on_inactive = false;
118     startTime = start;
119
120     // try to find an active histogram with the same start time 
121     // and use its bucket width  for "bucketWidth", otherwise, compute
122     // a value for "bucketWidth" based on startTime and global time
123     bool found = false;
124     for(unsigned i = 0; i < allHist.size(); i++){
125         if(((allHist[i])->startTime == startTime)&&(allHist[i])->active){
126             found = true;
127             bucketWidth = (allHist[i])->bucketWidth;
128             break;
129     } }
130     if(!found){
131         // compute bucketwidth based on start time
132         timeStamp minBucketWidth = 
133                 ((lastGlobalBin*globalBucketSize)  - startTime) / numBins;    
134         timeStamp i2 = baseBucketSize;
135         for(; i2 < minBucketWidth; i2 *= 2.0) ; 
136         bucketWidth = i2; 
137     }
138
139     allHist += this;
140     total_time = startTime + bucketWidth*numBins;
141 }
142
143
144 Histogram::Histogram(Bin *buckets, 
145                      timeStamp start,
146                      metricStyle type, 
147                      dataCallBack d, 
148                      foldCallBack f,
149                      void *c,
150                      bool globalFlag)
151 {
152     // First call default constructor.
153     (void) Histogram(start, type, d, f, c, globalFlag);
154     storageType = HistBucket;
155     dataPtr.buckets = (Bin *) calloc(sizeof(Bin), numBins);
156     memcpy(dataPtr.buckets, buckets, sizeof(Bin)*numBins);
157 }
158
159 Histogram::~Histogram(){
160
161     // remove from allHist
162     unsigned i=0;
163     for(; i < allHist.size(); i++){
164         if(allHist[i] == this){
165             break;
166         }
167     }
168     for(unsigned j = i; j < (allHist.size() - 1); j++){
169         allHist[j] = allHist[j+1];
170     }
171     allHist.resize(allHist.size() - 1);
172
173     // free bin space
174     if (storageType == HistInterval) {
175         free(dataPtr.intervals);
176     }
177     else {
178         delete [] dataPtr.buckets;
179     }
180 }
181
182 #if !defined(MAX)
183 #define MAX(a, b)       ((a) > (b) ? (a):(b))
184 #endif
185
186 /*
187  * addInterval - add a value to a histogram from start to end.
188  *
189  * start, and end are relative to the global start time (i.e. 0.0 is the
190  *   left side of the first hist bin).
191  */
192 void Histogram::addInterval(timeStamp start, 
193                             timeStamp end, 
194                             sampleValue value, 
195                             bool smooth)
196 {
197     while ((end >= total_time) || (start >= total_time)) {
198         // colapse histogram.
199         foldAllHist();
200     }
201
202     lastBin = (int) ((end - startTime) / bucketWidth);
203
204 #ifdef n_def
205     // update global info. if this histogram started at time 0
206     if(startTime == 0.0){
207         lastGlobalBin = lastBin;
208         for (unsigned i=0; i < allHist.size(); i++) {
209             if((allHist[i])->startTime == 0.0){
210                 if (((allHist[i])->lastBin < lastGlobalBin)) {
211                     lastGlobalBin = (allHist[i])->lastBin;
212             }}
213         }
214     }
215 #endif
216
217     // TODO: this should be replaced with the above code when
218     // the performance consultant is changed to correctly
219     // delete histograms that it is no longer collection 
220     // data values for
221     // change this so that lastGlobalbin is max of all lastBins
222     if (startTime == 0.0) {
223         if(lastBin > lastGlobalBin)
224             lastGlobalBin = lastBin;
225
226         const unsigned all_hist_size = allHist.size();
227         for (unsigned i=0; i < all_hist_size; i++) {
228             Histogram *theHist = allHist[i]; // a time saver; call operator[] just once
229
230             if (theHist->startTime == 0.0 && theHist->isActive())
231                 if (theHist->lastBin > lastGlobalBin)
232                     lastGlobalBin = theHist->lastBin;
233         }
234     }
235
236     if (storageType == HistInterval) {
237         /* convert to buckets */
238         convertToBins();
239     }
240     bucketValue(start, end, value, smooth);
241 }
242
243 void Histogram::convertToBins()
244 {
245     int i;
246     Interval *intervals;
247     Interval *currentInterval;
248
249     if (storageType == HistBucket) return;
250
251     intervals = dataPtr.intervals;
252     dataPtr.intervals = 0;
253     dataPtr.buckets = new Bin[numBins];
254     for(i = 0; i < numBins; i++){
255         dataPtr.buckets[i] = PARADYN_NaN; 
256     }
257
258     for (i=0; i < intervalCount; i++) {
259         currentInterval = &(intervals[i]);
260         bucketValue(currentInterval->start, currentInterval->end, 
261             currentInterval->value, smooth);
262     }
263     free(intervals);
264     intervalCount = -1;
265     intervalLimit = 0;
266     storageType = HistBucket;
267 }
268
269 void Histogram::foldAllHist()
270 {
271     // update global info.
272     if(startTime == 0.0){
273         globalBucketSize *= 2.0;
274         lastGlobalBin = numBins/2 - 1;
275     }
276     timeStamp newBucketWidth = bucketWidth*2.0;
277
278     // fold all histograms with the same time base
279     for(unsigned i = 0; i < allHist.size(); i++){
280         if(((allHist[i])->startTime == startTime)  // has same base time and 
281            && ((allHist[i])->active                // either, histogram active
282            || (allHist[i])->fold_on_inactive)){    // or fold on inactive set 
283
284           // don't fold this histogram if it has already folded
285           // This can happen to histograms that are created right
286           // after a fold, so that the initial bucket width may 
287           // not be correct and then the first data values will cause
288           // another fold...in this case we only want to fold the
289           // histograms that were not folded in the first round.  
290           if((allHist[i])->bucketWidth < newBucketWidth) {
291               (allHist[i])->bucketWidth *= 2.0;
292               if((allHist[i])->storageType == HistBucket){
293                   Bin *bins = (allHist[i])->dataPtr.buckets;
294                   int last_bin = -1;
295                   int j;
296                   for(j=0; j < numBins/2; j++){
297                       if(!isnan(bins[j*2+1])){   // both are not NaN
298                           bins[j] = (bins[j*2] + bins[j*2+1]) / 2.0F;
299                       }
300                       else if(!isnan(bins[j*2])){  // one is NaN
301                           bins[j] = (bins[j*2])/2.0F;   
302                           if(last_bin == -1) last_bin = j;
303                       }
304                       else {  // both are NaN
305                           bins[j] = PARADYN_NaN;
306                           if(last_bin == -1) last_bin = j;
307                       }
308                   }
309                   if(last_bin == -1) last_bin = j-1;
310                   (allHist[i])->lastBin = last_bin; 
311                   for(int k=numBins/2; k<numBins; k++){
312                       bins[k] = PARADYN_NaN;
313                   }
314               }
315               (allHist[i])->total_time = startTime + 
316                                        numBins*(allHist[i])->bucketWidth;
317               if((allHist[i])->foldFunc) 
318                   ((allHist[i])->foldFunc)((allHist[i])->bucketWidth, 
319                                         (allHist[i])->cData,
320                                         (allHist[i])->globalData);
321           }
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
341     // ignore bad values
342     if((first_bin < 0) || (first_bin > numBins)) return;
343     if (first_bin == numBins)
344         first_bin = numBins-1;
345     int last_bin = (int) ((end_clock - startTime) / bucketWidth);
346
347     // ignore bad values
348     if((last_bin < 0) || (last_bin > numBins)) return;
349     if (last_bin == numBins)
350         last_bin = numBins-1;
351
352     /* set starting times for first & last bins */
353     timeStamp first_bin_start = bucketWidth * first_bin;
354     timeStamp last_bin_start = bucketWidth  * last_bin;
355
356     if (metricType == SampledFunction) {
357         for (i=first_bin; i <= last_bin; i++) {
358             dataPtr.buckets[i] = value;
359         }
360     } else {
361         // normalize by bucket size.
362         value /= (sampleValue)bucketWidth;
363         if (last_bin == first_bin) {
364             if(isnan(dataPtr.buckets[first_bin])){ 
365                 dataPtr.buckets[first_bin] = 0.0;
366             }
367             dataPtr.buckets[first_bin] += value;
368             if (smooth && (dataPtr.buckets[first_bin] > 1.0)) {
369                 /* value > 100% */
370                 smoothBins(dataPtr.buckets, first_bin, bucketWidth);
371             }
372             return;
373         }
374
375         /* determine how much of the first & last bins were in this interval */
376         timeStamp time_in_first_bin = 
377                         bucketWidth - ((start_clock - startTime)- first_bin_start);
378         timeStamp time_in_last_bin = (end_clock- startTime) - last_bin_start;
379         timeStamp time_in_other_bins = 
380             MAX(elapsed_clock - (time_in_first_bin + time_in_last_bin), 0);
381         // ignore bad values
382         if((time_in_first_bin < 0) || 
383            (time_in_last_bin < 0) || 
384            (time_in_other_bins < 0)) 
385             return;
386
387         /* determine how much of value should be in each bin in the interval */
388         sampleValue amt_first_bin = 
389                 (sampleValue)(time_in_first_bin / elapsed_clock) * value;
390         sampleValue amt_last_bin  = 
391                 (sampleValue)(time_in_last_bin  / elapsed_clock) * value;
392         sampleValue amt_other_bins = 
393                 (sampleValue)(time_in_other_bins / elapsed_clock) * value;
394         if (last_bin > first_bin+1) 
395             amt_other_bins /= (last_bin - first_bin) - 1.0F;
396
397         // if bins contain NaN values set them to 0 before adding new value
398         if(isnan(dataPtr.buckets[first_bin])) 
399             dataPtr.buckets[first_bin] = 0.0;
400         if(isnan(dataPtr.buckets[last_bin])) 
401             dataPtr.buckets[last_bin] = 0.0;
402
403         /* add the appropriate amount of time to each bin */
404         dataPtr.buckets[first_bin] += amt_first_bin;
405         dataPtr.buckets[last_bin]  += amt_last_bin;
406         for (i=first_bin+1; i < last_bin; i++){
407             if(isnan(dataPtr.buckets[i])) 
408                 dataPtr.buckets[i] = 0.0;
409             dataPtr.buckets[i]  += amt_other_bins;
410         }
411     }
412
413     /* limit absurd time values - anything over 100% is pushed back into 
414        previous buckets */
415     if (smooth) {
416         for (i = first_bin; i <= last_bin; i++) {
417             if (dataPtr.buckets[i] > bucketWidth) 
418                 smoothBins(dataPtr.buckets, i, bucketWidth);
419         }
420     }
421
422     // inform users about the data.
423     // make sure they want to hear about it (dataFunc)
424     //  && that we have a full bin (last_bin>first_bin)
425     if (dataFunc && (last_bin-first_bin)) {
426         (dataFunc)(&dataPtr.buckets[first_bin], 
427                    startTime,
428                    last_bin-first_bin, 
429                    first_bin, 
430                    cData,
431                    globalData);
432     }
433 }
434
435
436 static void smoothBins(Bin *bins, int i, timeStamp bucketSize)
437 {
438     int j;
439     sampleValue extra_time;
440
441     extra_time = (sampleValue)(bins[i] - bucketSize);
442     bins[i] = (sampleValue)bucketSize;
443     j = i - 1;
444     while ((j >= 0) && (extra_time > 0.0)) {
445         bins[j] += extra_time;
446         extra_time = 0.0;
447         if (bins[j] > bucketSize) {
448             extra_time = (sampleValue)(bins[j] - bucketSize);
449             bins[j] = (sampleValue)bucketSize;
450         }
451         j--;
452     }
453     if (extra_time > 0.0) {
454         fprintf(stderr, "**** Unable to bucket %f seconds\n", extra_time);
455         abort();
456     }
457 }
458
459
460 static double splitTime(timeStamp startInterval, 
461                         timeStamp endInterval, 
462                         timeStamp startLimit, 
463                         timeStamp endLimit, 
464                         sampleValue value)
465 {
466     sampleValue time;
467     timeStamp inv_length;
468
469     inv_length = endInterval-startInterval;
470     if ((startInterval >= startLimit) && (endInterval <= endLimit)) {   
471         time = value;
472     } else if (startInterval == endInterval) {  
473         /* can't split delta functions */               
474         time = 0.0;
475     } else if ((startInterval >= startLimit) && (startInterval <= endLimit)) {
476         /* overlaps the end */                          
477         time = (sampleValue)(value * (endLimit - startInterval) / inv_length);
478     } else if ((endInterval <= endLimit) && (endInterval >= startLimit)) { 
479         /* overlaps the end */                          
480         time = (sampleValue)(value * (endInterval - startLimit) / inv_length);
481     } else if ((startInterval < startLimit) && (endInterval > endLimit)) {
482         /* detail contains interval */
483         time = (sampleValue)(value * (endLimit - startLimit) / inv_length);
484     } else {
485         /* no overlap of time */
486         time = 0.0;
487     }
488     return(time);
489 }
490
491 /*
492  * Get the component of the histogram from start to end.
493  *
494  */
495 sampleValue Histogram::getValue(timeStamp start, timeStamp end)
496 {               
497     int i;
498     Interval *cp;
499     sampleValue retVal = 0.0;
500     int first_bin, last_bin;
501     double pct_first_bin, pct_last_bin;
502
503     if (storageType == HistInterval) {
504         if (metricType == SampledFunction) {
505             // compute weight average of sample.
506             for (i=0; i < intervalCount; i++) {
507                 cp = &(dataPtr.intervals[i]);
508                 retVal += (sampleValue)(cp->value * (cp->end - cp->start));
509             }
510         } else {
511             // total over the interval.
512             for (i=0; i < intervalCount; i++) {
513                 cp = &(dataPtr.intervals[i]);
514                 retVal += (sampleValue)splitTime(cp->start, cp->end, start, end, cp->value);
515             }
516         }
517     } else {
518         first_bin = (int) (start/bucketWidth);
519         /* round up */
520         last_bin = (int) (end/bucketWidth+0.5);
521         if (last_bin >= numBins) last_bin = numBins-1;
522         if (first_bin == last_bin) {
523             retVal = dataPtr.buckets[first_bin];
524         } else {
525             /* (first_bin+1)*bucketWidth == time at end of first bucket */
526             pct_first_bin = (((first_bin+1)*bucketWidth)-start)/bucketWidth;
527             retVal += (sampleValue)(pct_first_bin * dataPtr.buckets[first_bin]);
528             /* last_bin+*bucketWidth == time at start of last bucket */
529             pct_last_bin = (end - last_bin*bucketWidth)/bucketWidth;
530             retVal += (sampleValue)(pct_last_bin * dataPtr.buckets[last_bin]);
531             for (i=first_bin+1; i <= last_bin-1; i++) {
532                 retVal += dataPtr.buckets[i];
533             }
534         }
535     }
536     return((sampleValue)(retVal * bucketWidth));
537 }
538
539 sampleValue Histogram::getValue()
540 {               
541     return(getValue(0.0, numBins * bucketWidth));
542 }
543
544 int Histogram::getBuckets(sampleValue *buckets, int numberOfBuckets, int first)
545 {
546     int i;
547     int last;
548
549     last = first + numberOfBuckets;
550     if (lastBin < last) last = lastBin;
551
552     // make sure its in bin form.
553     convertToBins();
554
555     assert(first >= 0);
556     assert(last <= lastBin); 
557     for (i=first; i < last; i++) {
558         float temp = dataPtr.buckets[i];
559         buckets[i-first] = temp;
560     }
561     return(last-first);
562 }