iPXE
profile.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2014 Michael Brown <mbrown@fensystems.co.uk>.
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License as
00006  * published by the Free Software Foundation; either version 2 of the
00007  * License, or any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful, but
00010  * WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
00017  * 02110-1301, USA.
00018  *
00019  * You can also choose to distribute this program under the terms of
00020  * the Unmodified Binary Distribution Licence (as given in the file
00021  * COPYING.UBDL), provided that you have satisfied its requirements.
00022  */
00023 
00024 FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL );
00025 
00026 #include <stdint.h>
00027 #include <stdio.h>
00028 #include <strings.h>
00029 #include <limits.h>
00030 #include <assert.h>
00031 #include <ipxe/isqrt.h>
00032 #include <ipxe/profile.h>
00033 
00034 /** @file
00035  *
00036  * Profiling
00037  *
00038  * The profiler computes basic statistics (mean, variance, and
00039  * standard deviation) for the samples which it records.  Note that
00040  * these statistics need not be completely accurate; it is sufficient
00041  * to give a rough approximation.
00042  *
00043  * The algorithm for updating the mean and variance estimators is from
00044  * The Art of Computer Programming (via Wikipedia), with adjustments
00045  * to avoid the use of floating-point instructions.
00046  */
00047 
00048 /** Accumulated time excluded from profiling */
00049 unsigned long profile_excluded;
00050 
00051 /**
00052  * Format a hex fraction (for debugging)
00053  *
00054  * @v value             Value
00055  * @v shift             Bit shift
00056  * @ret string          Formatted hex fraction
00057  */
00058 static const char * profile_hex_fraction ( signed long long value,
00059                                            unsigned int shift ) {
00060         static char buf[23] = "-"; /* -0xXXXXXXXXXXXXXXXX.XX + NUL */
00061         unsigned long long int_part;
00062         uint8_t frac_part;
00063         char *ptr;
00064 
00065         if ( value < 0 ) {
00066                 value = -value;
00067                 ptr = &buf[0];
00068         } else {
00069                 ptr = &buf[1];
00070         }
00071         int_part = ( value >> shift );
00072         frac_part = ( value >> ( shift - ( 8 * sizeof ( frac_part ) ) ) );
00073         snprintf ( &buf[1], ( sizeof ( buf ) - 1  ), "%#llx.%02x",
00074                    int_part, frac_part );
00075         return ptr;
00076 }
00077 
00078 /**
00079  * Calculate bit shift for mean sample value
00080  *
00081  * @v profiler          Profiler
00082  * @ret shift           Bit shift
00083  */
00084 static inline unsigned int profile_mean_shift ( struct profiler *profiler ) {
00085 
00086         return ( ( ( 8 * sizeof ( profiler->mean ) ) - 1 ) /* MSB */
00087                  - 1 /* Leave sign bit unused */
00088                  - profiler->mean_msb );
00089 }
00090 
00091 /**
00092  * Calculate bit shift for accumulated variance value
00093  *
00094  * @v profiler          Profiler
00095  * @ret shift           Bit shift
00096  */
00097 static inline unsigned int profile_accvar_shift ( struct profiler *profiler ) {
00098 
00099         return ( ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) /* MSB */
00100                  - 1 /* Leave top bit unused */
00101                  - profiler->accvar_msb );
00102 }
00103 
00104 /**
00105  * Update profiler with a new sample
00106  *
00107  * @v profiler          Profiler
00108  * @v sample            Sample value
00109  */
00110 void profile_update ( struct profiler *profiler, unsigned long sample ) {
00111         unsigned int sample_msb;
00112         unsigned int mean_shift;
00113         unsigned int delta_shift;
00114         signed long pre_delta;
00115         signed long post_delta;
00116         signed long long accvar_delta;
00117         unsigned int accvar_delta_shift;
00118         unsigned int accvar_delta_msb;
00119         unsigned int accvar_shift;
00120 
00121         /* Our scaling logic assumes that sample values never overflow
00122          * a signed long (i.e. that the high bit is always zero).
00123          */
00124         assert ( ( ( signed ) sample ) >= 0 );
00125 
00126         /* Update sample count, limiting to avoid signed overflow */
00127         if ( profiler->count < INT_MAX )
00128                 profiler->count++;
00129 
00130         /* Adjust mean sample value scale if necessary.  Skip if
00131          * sample is zero (in which case flsl(sample)-1 would
00132          * underflow): in the case of a zero sample we have no need to
00133          * adjust the scale anyway.
00134          */
00135         if ( sample ) {
00136                 sample_msb = ( flsl ( sample ) - 1 );
00137                 if ( profiler->mean_msb < sample_msb ) {
00138                         profiler->mean >>= ( sample_msb - profiler->mean_msb );
00139                         profiler->mean_msb = sample_msb;
00140                 }
00141         }
00142 
00143         /* Scale sample to internal units */
00144         mean_shift = profile_mean_shift ( profiler );
00145         sample <<= mean_shift;
00146 
00147         /* Update mean */
00148         pre_delta = ( sample - profiler->mean );
00149         profiler->mean += ( pre_delta / ( ( signed ) profiler->count ) );
00150         post_delta = ( sample - profiler->mean );
00151         delta_shift = mean_shift;
00152         DBGC ( profiler, "PROFILER %p sample %#lx mean %s", profiler,
00153                ( sample >> mean_shift ),
00154                 profile_hex_fraction ( profiler->mean, mean_shift ) );
00155         DBGC ( profiler, " pre %s",
00156                profile_hex_fraction ( pre_delta, delta_shift ) );
00157         DBGC ( profiler, " post %s\n",
00158                profile_hex_fraction ( post_delta, delta_shift ) );
00159 
00160         /* Scale both deltas to fit in half of an unsigned long long
00161          * to avoid potential overflow on multiplication.  Note that
00162          * shifting a signed quantity is "implementation-defined"
00163          * behaviour in the C standard, but gcc documents that it will
00164          * always perform sign extension.
00165          */
00166         if ( sizeof ( pre_delta ) > ( sizeof ( accvar_delta ) / 2 ) ) {
00167                 unsigned int shift = ( 8 * ( sizeof ( pre_delta ) -
00168                                              ( sizeof ( accvar_delta ) / 2 ) ));
00169                 pre_delta >>= shift;
00170                 post_delta >>= shift;
00171                 delta_shift -= shift;
00172         }
00173 
00174         /* Update variance, if applicable.  Skip if either delta is
00175          * zero (in which case flsl(delta)-1 would underflow): in the
00176          * case of a zero delta there is no change to the accumulated
00177          * variance anyway.
00178          */
00179         if ( pre_delta && post_delta ) {
00180 
00181                 /* Calculate variance delta */
00182                 accvar_delta = ( ( ( signed long long ) pre_delta ) *
00183                                  ( ( signed long long ) post_delta ) );
00184                 accvar_delta_shift = ( 2 * delta_shift );
00185                 assert ( accvar_delta > 0 );
00186 
00187                 /* Calculate variance delta MSB, using flsl() on each
00188                  * delta individually to provide an upper bound rather
00189                  * than requiring the existence of flsll().
00190                  */
00191                 accvar_delta_msb = ( flsll ( accvar_delta ) - 1 );
00192                 if ( accvar_delta_msb > accvar_delta_shift ) {
00193                         accvar_delta_msb -= accvar_delta_shift;
00194                 } else {
00195                         accvar_delta_msb = 0;
00196                 }
00197 
00198                 /* Adjust scales as necessary */
00199                 if ( profiler->accvar_msb < accvar_delta_msb ) {
00200                         /* Rescale accumulated variance */
00201                         profiler->accvar >>= ( accvar_delta_msb -
00202                                                profiler->accvar_msb );
00203                         profiler->accvar_msb = accvar_delta_msb;
00204                 } else {
00205                         /* Rescale variance delta */
00206                         accvar_delta >>= ( profiler->accvar_msb -
00207                                            accvar_delta_msb );
00208                         accvar_delta_shift -= ( profiler->accvar_msb -
00209                                                 accvar_delta_msb );
00210                 }
00211 
00212                 /* Scale delta to internal units */
00213                 accvar_shift = profile_accvar_shift ( profiler );
00214                 accvar_delta <<= ( accvar_shift - accvar_delta_shift );
00215 
00216                 /* Accumulate variance */
00217                 profiler->accvar += accvar_delta;
00218 
00219                 /* Adjust scale if necessary */
00220                 if ( profiler->accvar &
00221                      ( 1ULL << ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) ) ) {
00222                         profiler->accvar >>= 1;
00223                         profiler->accvar_msb++;
00224                         accvar_delta >>= 1;
00225                         accvar_shift--;
00226                 }
00227 
00228                 DBGC ( profiler, "PROFILER %p accvar %s", profiler,
00229                        profile_hex_fraction ( profiler->accvar, accvar_shift ));
00230                 DBGC ( profiler, " delta %s\n",
00231                        profile_hex_fraction ( accvar_delta, accvar_shift ) );
00232         }
00233 }
00234 
00235 /**
00236  * Get mean sample value
00237  *
00238  * @v profiler          Profiler
00239  * @ret mean            Mean sample value
00240  */
00241 unsigned long profile_mean ( struct profiler *profiler ) {
00242         unsigned int mean_shift = profile_mean_shift ( profiler );
00243 
00244         /* Round to nearest and scale down to original units */
00245         return ( ( profiler->mean + ( 1UL << ( mean_shift - 1 ) ) )
00246                  >> mean_shift );
00247 }
00248 
00249 /**
00250  * Get sample variance
00251  *
00252  * @v profiler          Profiler
00253  * @ret variance        Sample variance
00254  */
00255 unsigned long profile_variance ( struct profiler *profiler ) {
00256         unsigned int accvar_shift = profile_accvar_shift ( profiler );
00257 
00258         /* Variance is zero if fewer than two samples exist (avoiding
00259          * division by zero error).
00260          */
00261         if ( profiler->count < 2 )
00262                 return 0;
00263 
00264         /* Calculate variance, round to nearest, and scale to original units */
00265         return ( ( ( profiler->accvar / ( profiler->count - 1 ) )
00266                    + ( 1ULL << ( accvar_shift - 1 ) ) ) >> accvar_shift );
00267 }
00268 
00269 /**
00270  * Get sample standard deviation
00271  *
00272  * @v profiler          Profiler
00273  * @ret stddev          Sample standard deviation
00274  */
00275 unsigned long profile_stddev ( struct profiler *profiler ) {
00276 
00277         return isqrt ( profile_variance ( profiler ) );
00278 }