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