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