/* * Copyright (C) 2014 Michael Brown . * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License as * published by the Free Software Foundation; either version 2 of the * License, or any later version. * * This program is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * You can also choose to distribute this program under the terms of * the Unmodified Binary Distribution Licence (as given in the file * COPYING.UBDL), provided that you have satisfied its requirements. */ FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL ); #include #include #include #include #include #include #include /** @file * * Profiling * * The profiler computes basic statistics (mean, variance, and * standard deviation) for the samples which it records. Note that * these statistics need not be completely accurate; it is sufficient * to give a rough approximation. * * The algorithm for updating the mean and variance estimators is from * The Art of Computer Programming (via Wikipedia), with adjustments * to avoid the use of floating-point instructions. */ /** Accumulated time excluded from profiling */ unsigned long profile_excluded; /** * Format a hex fraction (for debugging) * * @v value Value * @v shift Bit shift * @ret string Formatted hex fraction */ static const char * profile_hex_fraction ( signed long long value, unsigned int shift ) { static char buf[23] = "-"; /* -0xXXXXXXXXXXXXXXXX.XX + NUL */ unsigned long long int_part; uint8_t frac_part; char *ptr; if ( value < 0 ) { value = -value; ptr = &buf[0]; } else { ptr = &buf[1]; } int_part = ( value >> shift ); frac_part = ( value >> ( shift - ( 8 * sizeof ( frac_part ) ) ) ); snprintf ( &buf[1], ( sizeof ( buf ) - 1 ), "%#llx.%02x", int_part, frac_part ); return ptr; } /** * Calculate bit shift for mean sample value * * @v profiler Profiler * @ret shift Bit shift */ static inline unsigned int profile_mean_shift ( struct profiler *profiler ) { return ( ( ( 8 * sizeof ( profiler->mean ) ) - 1 ) /* MSB */ - 1 /* Leave sign bit unused */ - profiler->mean_msb ); } /** * Calculate bit shift for accumulated variance value * * @v profiler Profiler * @ret shift Bit shift */ static inline unsigned int profile_accvar_shift ( struct profiler *profiler ) { return ( ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) /* MSB */ - 1 /* Leave top bit unused */ - profiler->accvar_msb ); } /** * Update profiler with a new sample * * @v profiler Profiler * @v sample Sample value */ void profile_update ( struct profiler *profiler, unsigned long sample ) { unsigned int sample_msb; unsigned int mean_shift; unsigned int delta_shift; signed long pre_delta; signed long post_delta; signed long long accvar_delta; unsigned int accvar_delta_shift; unsigned int accvar_delta_msb; unsigned int accvar_shift; /* Our scaling logic assumes that sample values never overflow * a signed long (i.e. that the high bit is always zero). */ assert ( ( ( signed ) sample ) >= 0 ); /* Update sample count, limiting to avoid signed overflow */ if ( profiler->count < INT_MAX ) profiler->count++; /* Adjust mean sample value scale if necessary. Skip if * sample is zero (in which case flsl(sample)-1 would * underflow): in the case of a zero sample we have no need to * adjust the scale anyway. */ if ( sample ) { sample_msb = ( flsl ( sample ) - 1 ); if ( profiler->mean_msb < sample_msb ) { profiler->mean >>= ( sample_msb - profiler->mean_msb ); profiler->mean_msb = sample_msb; } } /* Scale sample to internal units */ mean_shift = profile_mean_shift ( profiler ); sample <<= mean_shift; /* Update mean */ pre_delta = ( sample - profiler->mean ); profiler->mean += ( pre_delta / ( ( signed ) profiler->count ) ); post_delta = ( sample - profiler->mean ); delta_shift = mean_shift; DBGC ( profiler, "PROFILER %p sample %#lx mean %s", profiler, ( sample >> mean_shift ), profile_hex_fraction ( profiler->mean, mean_shift ) ); DBGC ( profiler, " pre %s", profile_hex_fraction ( pre_delta, delta_shift ) ); DBGC ( profiler, " post %s\n", profile_hex_fraction ( post_delta, delta_shift ) ); /* Scale both deltas to fit in half of an unsigned long long * to avoid potential overflow on multiplication. Note that * shifting a signed quantity is "implementation-defined" * behaviour in the C standard, but gcc documents that it will * always perform sign extension. */ if ( sizeof ( pre_delta ) > ( sizeof ( accvar_delta ) / 2 ) ) { unsigned int shift = ( 8 * ( sizeof ( pre_delta ) - ( sizeof ( accvar_delta ) / 2 ) )); pre_delta >>= shift; post_delta >>= shift; delta_shift -= shift; } /* Update variance, if applicable. Skip if either delta is * zero (in which case flsl(delta)-1 would underflow): in the * case of a zero delta there is no change to the accumulated * variance anyway. */ if ( pre_delta && post_delta ) { /* Calculate variance delta */ accvar_delta = ( ( ( signed long long ) pre_delta ) * ( ( signed long long ) post_delta ) ); accvar_delta_shift = ( 2 * delta_shift ); assert ( accvar_delta > 0 ); /* Calculate variance delta MSB, using flsl() on each * delta individually to provide an upper bound rather * than requiring the existence of flsll(). */ accvar_delta_msb = ( flsll ( accvar_delta ) - 1 ); if ( accvar_delta_msb > accvar_delta_shift ) { accvar_delta_msb -= accvar_delta_shift; } else { accvar_delta_msb = 0; } /* Adjust scales as necessary */ if ( profiler->accvar_msb < accvar_delta_msb ) { /* Rescale accumulated variance */ profiler->accvar >>= ( accvar_delta_msb - profiler->accvar_msb ); profiler->accvar_msb = accvar_delta_msb; } else { /* Rescale variance delta */ accvar_delta >>= ( profiler->accvar_msb - accvar_delta_msb ); accvar_delta_shift -= ( profiler->accvar_msb - accvar_delta_msb ); } /* Scale delta to internal units */ accvar_shift = profile_accvar_shift ( profiler ); accvar_delta <<= ( accvar_shift - accvar_delta_shift ); /* Accumulate variance */ profiler->accvar += accvar_delta; /* Adjust scale if necessary */ if ( profiler->accvar & ( 1ULL << ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) ) ) { profiler->accvar >>= 1; profiler->accvar_msb++; accvar_delta >>= 1; accvar_shift--; } DBGC ( profiler, "PROFILER %p accvar %s", profiler, profile_hex_fraction ( profiler->accvar, accvar_shift )); DBGC ( profiler, " delta %s\n", profile_hex_fraction ( accvar_delta, accvar_shift ) ); } } /** * Get mean sample value * * @v profiler Profiler * @ret mean Mean sample value */ unsigned long profile_mean ( struct profiler *profiler ) { unsigned int mean_shift = profile_mean_shift ( profiler ); /* Round to nearest and scale down to original units */ return ( ( profiler->mean + ( 1UL << ( mean_shift - 1 ) ) ) >> mean_shift ); } /** * Get sample variance * * @v profiler Profiler * @ret variance Sample variance */ unsigned long profile_variance ( struct profiler *profiler ) { unsigned int accvar_shift = profile_accvar_shift ( profiler ); /* Variance is zero if fewer than two samples exist (avoiding * division by zero error). */ if ( profiler->count < 2 ) return 0; /* Calculate variance, round to nearest, and scale to original units */ return ( ( ( profiler->accvar / ( profiler->count - 1 ) ) + ( 1ULL << ( accvar_shift - 1 ) ) ) >> accvar_shift ); } /** * Get sample standard deviation * * @v profiler Profiler * @ret stddev Sample standard deviation */ unsigned long profile_stddev ( struct profiler *profiler ) { return isqrt ( profile_variance ( profiler ) ); }