qemu/roms/ipxe/src/core/profile.c

   1 /*
   2  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License as
   6  * published by the Free Software Foundation; either version 2 of the
   7  * License, or any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful, but
  10  * WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  17  * 02110-1301, USA.
  18  *
  19  * You can also choose to distribute this program under the terms of
  20  * the Unmodified Binary Distribution Licence (as given in the file
  21  * COPYING.UBDL), provided that you have satisfied its requirements.
  22  */
  23
  24 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
  25
  26 #include <stdint.h>
  27 #include <stdio.h>
  28 #include <strings.h>
  29 #include <assert.h>
  30 #include <ipxe/isqrt.h>
  31 #include <ipxe/profile.h>
  32
  33 /** @file
  34  *
  35  * Profiling
  36  *
  37  * The profiler computes basic statistics (mean, variance, and
  38  * standard deviation) for the samples which it records.  Note that
  39  * these statistics need not be completely accurate; it is sufficient
  40  * to give a rough approximation.
  41  *
  42  * The algorithm for updating the mean and variance estimators is from
  43  * The Art of Computer Programming (via Wikipedia), with adjustments
  44  * to avoid the use of floating-point instructions.
  45  */
  46
  47 /** Accumulated time excluded from profiling */
  48 unsigned long profile_excluded;
  49
  50 /**
  51  * Format a hex fraction (for debugging)
  52  *
  53  * @v value             Value
  54  * @v shift             Bit shift
  55  * @ret string          Formatted hex fraction
  56  */
  57 static const char * profile_hex_fraction ( signed long long value,
  58                                            unsigned int shift ) {
  59         static char buf[23] = "-"; /* -0xXXXXXXXXXXXXXXXX.XX + NUL */
  60         unsigned long long int_part;
  61         uint8_t frac_part;
  62         char *ptr;
  63
  64         if ( value < 0 ) {
  65                 value = -value;
  66                 ptr = &buf[0];
  67         } else {
  68                 ptr = &buf[1];
  69         }
  70         int_part = ( value >> shift );
  71         frac_part = ( value >> ( shift - ( 8 * sizeof ( frac_part ) ) ) );
  72         snprintf ( &buf[1], ( sizeof ( buf ) - 1  ), "%#llx.%02x",
  73                    int_part, frac_part );
  74         return ptr;
  75 }
  76
  77 /**
  78  * Calculate bit shift for mean sample value
  79  *
  80  * @v profiler          Profiler
  81  * @ret shift           Bit shift
  82  */
  83 static inline unsigned int profile_mean_shift ( struct profiler *profiler ) {
  84
  85         return ( ( ( 8 * sizeof ( profiler->mean ) ) - 1 ) /* MSB */
  86                  - 1 /* Leave sign bit unused */
  87                  - profiler->mean_msb );
  88 }
  89
  90 /**
  91  * Calculate bit shift for accumulated variance value
  92  *
  93  * @v profiler          Profiler
  94  * @ret shift           Bit shift
  95  */
  96 static inline unsigned int profile_accvar_shift ( struct profiler *profiler ) {
  97
  98         return ( ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) /* MSB */
  99                  - 1 /* Leave top bit unused */
 100                  - profiler->accvar_msb );
 101 }
 102
 103 /**
 104  * Update profiler with a new sample
 105  *
 106  * @v profiler          Profiler
 107  * @v sample            Sample value
 108  */
 109 void profile_update ( struct profiler *profiler, unsigned long sample ) {
 110         unsigned int sample_msb;
 111         unsigned int mean_shift;
 112         unsigned int delta_shift;
 113         signed long pre_delta;
 114         signed long post_delta;
 115         signed long long accvar_delta;
 116         unsigned int accvar_delta_shift;
 117         unsigned int accvar_delta_msb;
 118         unsigned int accvar_shift;
 119
 120         /* Our scaling logic assumes that sample values never overflow
 121          * a signed long (i.e. that the high bit is always zero).
 122          */
 123         assert ( ( ( signed ) sample ) >= 0 );
 124
 125         /* Update sample count */
 126         profiler->count++;
 127
 128         /* Adjust mean sample value scale if necessary.  Skip if
 129          * sample is zero (in which case flsl(sample)-1 would
 130          * underflow): in the case of a zero sample we have no need to
 131          * adjust the scale anyway.
 132          */
 133         if ( sample ) {
 134                 sample_msb = ( flsl ( sample ) - 1 );
 135                 if ( profiler->mean_msb < sample_msb ) {
 136                         profiler->mean >>= ( sample_msb - profiler->mean_msb );
 137                         profiler->mean_msb = sample_msb;
 138                 }
 139         }
 140
 141         /* Scale sample to internal units */
 142         mean_shift = profile_mean_shift ( profiler );
 143         sample <<= mean_shift;
 144
 145         /* Update mean */
 146         pre_delta = ( sample - profiler->mean );
 147         profiler->mean += ( pre_delta / ( ( signed ) profiler->count ) );
 148         post_delta = ( sample - profiler->mean );
 149         delta_shift = mean_shift;
 150         DBGC ( profiler, "PROFILER %p sample %#lx mean %s", profiler,
 151                ( sample >> mean_shift ),
 152                 profile_hex_fraction ( profiler->mean, mean_shift ) );
 153         DBGC ( profiler, " pre %s",
 154                profile_hex_fraction ( pre_delta, delta_shift ) );
 155         DBGC ( profiler, " post %s\n",
 156                profile_hex_fraction ( post_delta, delta_shift ) );
 157
 158         /* Scale both deltas to fit in half of an unsigned long long
 159          * to avoid potential overflow on multiplication.  Note that
 160          * shifting a signed quantity is "implementation-defined"
 161          * behaviour in the C standard, but gcc documents that it will
 162          * always perform sign extension.
 163          */
 164         if ( sizeof ( pre_delta ) > ( sizeof ( accvar_delta ) / 2 ) ) {
 165                 unsigned int shift = ( 8 * ( sizeof ( pre_delta ) -
 166                                              ( sizeof ( accvar_delta ) / 2 ) ));
 167                 pre_delta >>= shift;
 168                 post_delta >>= shift;
 169                 delta_shift -= shift;
 170         }
 171
 172         /* Update variance, if applicable.  Skip if either delta is
 173          * zero (in which case flsl(delta)-1 would underflow): in the
 174          * case of a zero delta there is no change to the accumulated
 175          * variance anyway.
 176          */
 177         if ( pre_delta && post_delta ) {
 178
 179                 /* Calculate variance delta */
 180                 accvar_delta = ( ( ( signed long long ) pre_delta ) *
 181                                  ( ( signed long long ) post_delta ) );
 182                 accvar_delta_shift = ( 2 * delta_shift );
 183                 assert ( accvar_delta > 0 );
 184
 185                 /* Calculate variance delta MSB, using flsl() on each
 186                  * delta individually to provide an upper bound rather
 187                  * than requiring the existence of flsll().
 188                  */
 189                 accvar_delta_msb = ( flsll ( accvar_delta ) - 1 );
 190                 if ( accvar_delta_msb > accvar_delta_shift ) {
 191                         accvar_delta_msb -= accvar_delta_shift;
 192                 } else {
 193                         accvar_delta_msb = 0;
 194                 }
 195
 196                 /* Adjust scales as necessary */
 197                 if ( profiler->accvar_msb < accvar_delta_msb ) {
 198                         /* Rescale accumulated variance */
 199                         profiler->accvar >>= ( accvar_delta_msb -
 200                                                profiler->accvar_msb );
 201                         profiler->accvar_msb = accvar_delta_msb;
 202                 } else {
 203                         /* Rescale variance delta */
 204                         accvar_delta >>= ( profiler->accvar_msb -
 205                                            accvar_delta_msb );
 206                         accvar_delta_shift -= ( profiler->accvar_msb -
 207                                                 accvar_delta_msb );
 208                 }
 209
 210                 /* Scale delta to internal units */
 211                 accvar_shift = profile_accvar_shift ( profiler );
 212                 accvar_delta <<= ( accvar_shift - accvar_delta_shift );
 213
 214                 /* Accumulate variance */
 215                 profiler->accvar += accvar_delta;
 216
 217                 /* Adjust scale if necessary */
 218                 if ( profiler->accvar &
 219                      ( 1ULL << ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) ) ) {
 220                         profiler->accvar >>= 1;
 221                         profiler->accvar_msb++;
 222                         accvar_delta >>= 1;
 223                         accvar_shift--;
 224                 }
 225
 226                 DBGC ( profiler, "PROFILER %p accvar %s", profiler,
 227                        profile_hex_fraction ( profiler->accvar, accvar_shift ));
 228                 DBGC ( profiler, " delta %s\n",
 229                        profile_hex_fraction ( accvar_delta, accvar_shift ) );
 230         }
 231 }
 232
 233 /**
 234  * Get mean sample value
 235  *
 236  * @v profiler          Profiler
 237  * @ret mean            Mean sample value
 238  */
 239 unsigned long profile_mean ( struct profiler *profiler ) {
 240         unsigned int mean_shift = profile_mean_shift ( profiler );
 241
 242         /* Round to nearest and scale down to original units */
 243         return ( ( profiler->mean + ( 1UL << ( mean_shift - 1 ) ) )
 244                  >> mean_shift );
 245 }
 246
 247 /**
 248  * Get sample variance
 249  *
 250  * @v profiler          Profiler
 251  * @ret variance        Sample variance
 252  */
 253 unsigned long profile_variance ( struct profiler *profiler ) {
 254         unsigned int accvar_shift = profile_accvar_shift ( profiler );
 255
 256         /* Variance is zero if fewer than two samples exist (avoiding
 257          * division by zero error).
 258          */
 259         if ( profiler->count < 2 )
 260                 return 0;
 261
 262         /* Calculate variance, round to nearest, and scale to original units */
 263         return ( ( ( profiler->accvar / ( profiler->count - 1 ) )
 264                    + ( 1ULL << ( accvar_shift - 1 ) ) ) >> accvar_shift );
 265 }
 266
 267 /**
 268  * Get sample standard deviation
 269  *
 270  * @v profiler          Profiler
 271  * @ret stddev          Sample standard deviation
 272  */
 273 unsigned long profile_stddev ( struct profiler *profiler ) {
 274
 275         return isqrt ( profile_variance ( profiler ) );
 276 }