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