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