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