iPXE
Functions | Variables
profile.c File Reference

Profiling. More...

#include <stdint.h>
#include <stdio.h>
#include <strings.h>
#include <limits.h>
#include <assert.h>
#include <ipxe/isqrt.h>
#include <ipxe/profile.h>

Go to the source code of this file.

Functions

 FILE_LICENCE (GPL2_OR_LATER_OR_UBDL)
static const char * profile_hex_fraction (signed long long value, unsigned int shift)
 Format a hex fraction (for debugging)
static unsigned int profile_mean_shift (struct profiler *profiler)
 Calculate bit shift for mean sample value.
static unsigned int profile_accvar_shift (struct profiler *profiler)
 Calculate bit shift for accumulated variance value.
void profile_update (struct profiler *profiler, unsigned long sample)
 Update profiler with a new sample.
unsigned long profile_mean (struct profiler *profiler)
 Get mean sample value.
unsigned long profile_variance (struct profiler *profiler)
 Get sample variance.
unsigned long profile_stddev (struct profiler *profiler)
 Get sample standard deviation.

Variables

unsigned long profile_excluded
 Accumulated time excluded from profiling.

Detailed Description

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.

Definition in file profile.c.


Function Documentation

FILE_LICENCE ( GPL2_OR_LATER_OR_UBDL  )
static const char* profile_hex_fraction ( signed long long  value,
unsigned int  shift 
) [static]

Format a hex fraction (for debugging)

Parameters:
valueValue
shiftBit shift
Return values:
stringFormatted hex fraction

Definition at line 58 of file profile.c.

References snprintf(), and value.

Referenced by profile_update().

                                                                {
        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;
}
static unsigned int profile_mean_shift ( struct profiler profiler) [inline, static]

Calculate bit shift for mean sample value.

Parameters:
profilerProfiler
Return values:
shiftBit shift

Definition at line 84 of file profile.c.

References profiler::mean, and profiler::mean_msb.

Referenced by profile_mean(), and profile_update().

                                                                            {

        return ( ( ( 8 * sizeof ( profiler->mean ) ) - 1 ) /* MSB */
                 - 1 /* Leave sign bit unused */
                 - profiler->mean_msb );
}
static unsigned int profile_accvar_shift ( struct profiler profiler) [inline, static]

Calculate bit shift for accumulated variance value.

Parameters:
profilerProfiler
Return values:
shiftBit shift

Definition at line 97 of file profile.c.

References profiler::accvar, and profiler::accvar_msb.

Referenced by profile_update(), and profile_variance().

                                                                              {

        return ( ( ( 8 * sizeof ( profiler->accvar ) ) - 1 ) /* MSB */
                 - 1 /* Leave top bit unused */
                 - profiler->accvar_msb );
}
void profile_update ( struct profiler profiler,
unsigned long  sample 
)

Update profiler with a new sample.

Parameters:
profilerProfiler
sampleSample value

Definition at line 110 of file profile.c.

References profiler::accvar, profiler::accvar_msb, assert, profiler::count, DBGC, flsl, flsll, INT_MAX, profiler::mean, profiler::mean_msb, profile_accvar_shift(), profile_hex_fraction(), and profile_mean_shift().

Referenced by profile_custom(), profile_okx(), and profile_stop_at().

                                                                        {
        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 ) );
        }
}
unsigned long profile_mean ( struct profiler profiler)

Get mean sample value.

Parameters:
profilerProfiler
Return values:
meanMean sample value

Definition at line 241 of file profile.c.

References profiler::mean, and profile_mean_shift().

Referenced by cipher_cost(), digest_cost(), memcpy_test_speed(), profile_okx(), profstat(), and tcpip_random_okx().

                                                         {
        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 );
}
unsigned long profile_variance ( struct profiler profiler)

Get sample variance.

Parameters:
profilerProfiler
Return values:
varianceSample variance

Definition at line 255 of file profile.c.

References profiler::accvar, profiler::count, and profile_accvar_shift().

Referenced by profile_stddev().

                                                             {
        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 );
}
unsigned long profile_stddev ( struct profiler profiler)

Get sample standard deviation.

Parameters:
profilerProfiler
Return values:
stddevSample standard deviation

Definition at line 275 of file profile.c.

References isqrt(), and profile_variance().

Referenced by memcpy_test_speed(), profile_okx(), profstat(), and tcpip_random_okx().

                                                           {

        return isqrt ( profile_variance ( profiler ) );
}

Variable Documentation

unsigned long profile_excluded

Accumulated time excluded from profiling.

Definition at line 49 of file profile.c.

Referenced by profile_exclude(), profile_start_at(), profile_started(), profile_stop_at(), and profile_stopped().