9ns: mnt: Don't use a 'bogus' struct
[akaros.git] / kern / arch / x86 / rdtsc_test.c
1 /* Barret Rhoden
2  *
3  * Code heavily ported from "How to Benchmark Code Execution Times on Intel(R)
4  * IA-32 and IA-64 Instruction Set Architectures" for linux, except for
5  * check_timing_stability().
6  *
7  * The idea behind this was that the traditional style of using rdtsc was to
8  * call:
9  *                      cpuid;
10  *                      rdtsc;
11  * since rdtsc does no serialization (meaning later instructions can get
12  * executed before it, or vice versa).  While this first cpuid isn't a big deal,
13  * doing this in pairs means reading the end time also measures cpuid.  This is
14  * a problem since cpuid can vary quite a bit.
15  *
16  * If we use rdtscp for the end call, we can put the cpuid after rdtscp, thereby
17  * not including cpuid's overhead (and variability) in our measurement.  That's
18  * where the intel doc ends.  For more info, check out:
19  *              http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf
20  *
21  * Note that the Intel SDM says you can serialize rdtsc with lfence, such as:
22  *                      lfence;
23  *                      rdtsc;
24  * Linux uses this (mfence on amd64, lfence on intel).  For more info:
25  *              https://lkml.org/lkml/2008/1/2/353
26  * Note this use of lfence before rdtsc is supposedly serializing any
27  * instruction, not just loads.  Some stranger on the internet suggested that
28  * while lfence only serializes memory (and not arbitrary instructions), in
29  * actual hardware there is no point to reorder non-memory instructions around
30  * rdtsc:
31  *              http://stackoverflow.com/questions/12631856/difference-between-rdtscp-rdtsc-memory-and-cpuid-rdtsc
32  *              (look for janneb's response to questions about his comment)
33  *
34  * Its not clear from what anyone writes as to whether or not you need to
35  * serialize below rdtsc.  Supposedly, you'd need cpuid/lfence on both sides of
36  * rdtsc to prevent reordering in both directions.  Andi Kleen does this in a
37  * few places
38  *              https://lkml.org/lkml/2008/1/7/276
39  * though other places in the kernel suggest it is unnecessary (at least for
40  * loads:
41  *              http://lxr.linux.no/#linux+v3.8.2/arch/x86/kvm/x86.c#L1258
42  * The intel docs don't mention it (otherwise we would be told to use
43  * lfence;rdtsc;lfence).  The howto this file is based off of didn't mention it
44  * either, other than to say rdtscp needs to serialize from below.  AFAIK,
45  * rdtscp is like rdtsc, except that it serializes from above (and also returns
46  * the CPU id).  If rdtscp needs to serialize from below, then so should rdtsc.
47  *
48  * That being said, if these rdtsc(p) calls do not need serialization from
49  * below, then rdtscp (which provides serialization from above) should not need
50  * any additional serialization (lfence or cpuid).
51  *
52  * I tried out a few options for the assembly for the start and end time
53  * measurements, using the intel benchmark.  The benchmark reports variance, max
54  * deviation, and minimum per inner loop (line), as well as an overall variance,
55  * max dev, and variance of vars/mins.
56  *
57  * CASE    START ASM            END ASM
58  * ---------------------------------------------------
59  * case 0: cpuid;rdtsc;                 cpuid;rdtscp;
60  * case 1: cpuid;rdtsc;                 rdtscp;cpuid; (or rdtscp;lfence)
61  * case 2: lfence;rdtsc;                rdtscp;cpuid; (or rdtscp;lfence)
62  * case 3: rdtscp;                              rdtscp;cpuid; (or rdtscp;lfence)
63  * case 4: rdtscp;                              rdtscp;
64  * case 5: lfence;rdtsc;                lfence;rdtsc;
65  * case 6: lfence;rdtsc;lfence; lfence;rdtsc;lfence;
66  *
67  * Note I only ran these a couple times, with 1000x10000, and I did notice some
68  * slight variation between runs (on cases 3 and 4).
69  *
70  * case 0:       wildly variant, variance of variances wasn't 0, etc (as
71  * reported by intel).
72  * case 0:  some lines     0 var, 0-8 max dev, 420 min
73  * case 0: other lines 50-60 var,  20 max dev, 388 min
74  *
75  * For all of the other cases, variance of variances and of minvalues was 0.
76  *
77  * case 1: most lines 2-3 var, 4 max dev, 44 min, 2 var 4 max dev overall
78  * case 2: most lines 2-3 var, 4 max dev, 44 min, 2 var 4 max dev overall
79  * case 3: most lines   0 var, 0 max dev, 32 min, 0 var 0 max dev overall
80  * case 4: most lines   0 var, 0 max dev, 32 min, 0 var 4 max dev overall
81  * case 5: most lines   3 var, 4 max dev, 28 min, 2 var 4 max dev overall
82  * case 6: most lines   3 var, 4 max dev, 44 min, 2 var 4 max dev overall
83  *
84  *              case 1-3: cpuid vs lfence: both seem to work the same and have no effect
85  *              (since they are outside the loop)
86  *
87  * So running with rdtscp for both start and stop (case 3 and 4) had the least
88  * amount of variance (both per line and total).  When these cases have had any
89  * deviation, it was because one run had a min of 28, but o/w was 32.  (1 out of
90  * 10000000, often the first run).
91  *
92  * All the others have a little deviation, but with a more stable min.  Again,
93  * this is taken mostly from a small number of runs (of 1kx10k).
94  *
95  * Note that cases 5 and 6 have lfences inside the measurement area, and this
96  * does not seem to cause problems the same way cpuid does.  However, lfences
97  * inside the critical section (esp after whatever code we are measuring)
98  * probably will have an effect on real code that has made memory accesses (keep
99  * in mind we need to do an mfence on amd64 here).
100  *
101  * All that being said, it's not clear which option to use.  Ideally, we want
102  * an isolated region of code to be measured, with very little variance and max
103  * deviation.  If cases 1-6 are all the same in terms of protection (which I'm
104  * not sure about), then 3-4 look nice.  However, the fact that sometimes the
105  * min is less than 'normal', means that we could get negative numbers for some
106  * measurements (the goal is to determine the overhead and subtract that from
107  * our total measurement, and if we think the overhead is 32 but was actually 28
108  * for a run, we could have issues).
109  *
110  * But wait, there's more:
111  *
112  * When we add code around (and inside) the measurement, things get even worse:
113  * - If we put variable (a volatile btw) = j + i; in the loop, there's no real
114  *   change.  I checked cases 1, 4 and 5, 1 being the intel recommended, 4 being
115  *   the one with the best variance with no code, and 5 being a good symmetric
116  *   choice (same on start and end).  Case 1 had no change at all.  4 and 5 had
117  *   little change (min was the same, occasional deviation).  Note that case 5
118  *   doesn't use rdtscp at the end either.
119  * - If we put in variable = i; as well, the minimum still is unaffected, and
120  *   there is a little more variance.  For example, for case 4, the min is still
121  *   32, and sometimes you get a 36.
122  *
123  * If we add more code (like a for loop that grows in length with each outer
124  * loop), eventually we can detect the existence of the instructions.  The Intel
125  * author talks about this in 3.3 when he finds the resolution of the benchmark.
126  *
127  * My hunch is that the rdtsc(p) calls hide the latency of some previous
128  * instructions, regardless of serialization commands.  We see this 'hiding' of
129  * the cost of instructions regardless of whether or not the first or last
130  * commands are rdtscp (I'm more concerned with the end time call, which is
131  * where this hiding may be happening).  Perhaps the pipeline needs to be
132  * drained (or something), and it takes a certain amount of time to do so,
133  * regardless of a few extra instructions squeezed in.  Meaning we can't tell
134  * the difference between 0 and a few cycles, and probably a few cycles are
135  * 'free' / hidden by the rdtsc call.
136  *
137  * Bottom line?  Our measurements are inexact, despite the stable minimum and
138  * low variance.  Everything will be +/- our max deviation, as well as
139  * potentially underestimating by a few cycles/ticks.  One thing we can do is
140  * try to see what the resolution is of the different methods.
141  *
142  * case 1: cpuid;rdtsc;                 rdtscp;cpuid; (or rdtscp;lfence)
143  * -------------------
144  * loop_size:0 >>>> variance(cycles): 3; max_deviation: 8; min time: 44
145  * loop_size:1 >>>> variance(cycles): 6; max_deviation: 28; min time: 44
146  * loop_size:2 >>>> variance(cycles): 4; max_deviation: 16; min time: 44
147  * loop_size:3 >>>> variance(cycles): 12; max_deviation: 44; min time: 44
148  * loop_size:4 >>>> variance(cycles): 10; max_deviation: 32; min time: 44
149  * loop_size:5 >>>> variance(cycles): 10; max_deviation: 32; min time: 44
150  * loop_size:6 >>>> variance(cycles): 12; max_deviation: 36; min time: 44
151  * loop_size:7 >>>> variance(cycles): 5; max_deviation: 32; min time: 48
152  * loop_size:8 >>>> variance(cycles): 16; max_deviation: 52; min time: 48
153  * loop_size:9 >>>> variance(cycles): 13; max_deviation: 48; min time: 52
154  * loop_size:10 >>>> variance(cycles): 9; max_deviation: 36; min time: 52
155  * loop_size:11 >>>> variance(cycles): 16; max_deviation: 64; min time: 56
156  *
157  * case 4: rdtscp;                              rdtscp;
158  * -------------------
159  * loop_size:0 >>>> variance(cycles): 1; max_deviation: 20; min time: 32
160  * loop_size:1 >>>> variance(cycles): 12; max_deviation: 36; min time: 36
161  * loop_size:2 >>>> variance(cycles): 13; max_deviation: 32; min time: 36
162  * loop_size:3 >>>> variance(cycles): 7; max_deviation: 32; min time: 40
163  * loop_size:4 >>>> variance(cycles): 1; max_deviation: 16; min time: 44
164  * loop_size:5 >>>> variance(cycles): 4; max_deviation: 28; min time: 44
165  * loop_size:6 >>>> variance(cycles): 12; max_deviation: 48; min time: 44
166  * loop_size:7 >>>> variance(cycles): 8; max_deviation: 32; min time: 44
167  * loop_size:8 >>>> variance(cycles): 10; max_deviation: 48; min time: 48
168  *
169  * case 5: lfence;rdtsc;                lfence;rdtsc;
170  * -------------------
171  * loop_size:0 >>>> variance(cycles): 3; max_deviation: 12; min time: 28
172  * loop_size:1 >>>> variance(cycles): 8; max_deviation: 28; min time: 32
173  * loop_size:2 >>>> variance(cycles): 8; max_deviation: 28; min time: 32
174  * loop_size:3 >>>> variance(cycles): 6; max_deviation: 28; min time: 32
175  * loop_size:4 >>>> variance(cycles): 2; max_deviation: 24; min time: 36
176  * loop_size:5 >>>> variance(cycles): 6; max_deviation: 28; min time: 36
177  * loop_size:6 >>>> variance(cycles): 11; max_deviation: 44; min time: 36
178  * loop_size:7 >>>> variance(cycles): 7; max_deviation: 32; min time: 36
179  * loop_size:8 >>>> variance(cycles): 1; max_deviation: 16; min time: 40
180  *
181  * For cases 4 and 5, we notice quite quickly.  The for loop itself has some
182  * overhead (probably more than our simple stores and adds).  So the resolution
183  * of these methods is a little more than a loop's overhead.  For case 1, we
184  * need about 7 loops, in addition to the overhead, until we can reliably detect
185  * the additional instructions.  Note the deviation and variation increases for
186  * all cases.
187  *
188  *
189  * What about extra code before the measurement?  I reran the test cases with
190  * some extra tsc-related code above the measurement (an accidental asm
191  * insertion of lfence;rdtsc above reading the start time) and with no work in
192  * between:
193  *              case 1: no effect
194  *              case 2: no effect
195  * These both had some form of serialization (cpuid or lfence) above the rdtsc
196  * command.  But when we try using just rdtscp (with no extra serialization:)
197  *              case 3, normal: lines   0 var, 0 max dev, 32 min, 0 var 0 max dev
198  *              case 3, extras: lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
199  * Similar deal with case 4.  Lots of 28s and deviation.  It looks like some
200  * times the rdtsc diff is only 28, and others 32 (hence the deviation of 4).
201  * Note this means the measurement interval is *lower*, which means the code was
202  * *faster*.  Was the rdtscp not serializing instructions from above (which
203  * doesn't make sense, since anything sneaking in from above should make the
204  * code *slower*)?  Or is it because the previous command was rdtsc, which might
205  * 'speed up' subsequent rdtscs.  I tried it again, with a little work between
206  * the unused TSC read and the start tsc read:
207  *              case 3, more crap : lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
208  * So no real change from adding minor code in between.  What about adding an
209  * lfence above the rdtscp (so it is almost exactly like case 2)?
210  * Our assembly code now looks like:
211  *              lfence;
212  *              rdtsc;
213  *              mov %edx, (memory);     // these get overwritten
214  *              mov %eax, (memory);     // these get overwritten
215  *
216  *              mov (memory), %eax;             // misc work (variable = i + j)
217  *              add %esi, %eax;                 // misc work (variable = i + j)
218  *              mov %eax, (memory);             // misc work (variable = i + j)
219  *
220  *              lfence;
221  *              rdtscp;                                 // this is the real start measurement
222  *              mov %edx, (memory);
223  *              mov %eax, (memory);
224  *
225  *      // no extra work here
226  *
227  *              rdtscp;                                 // this is the real end measurement
228  *              mov %edx, (memory);
229  *              mov %eax, (memory);
230  *              cpuid;                                  // this is case 3, with sync after
231  *
232  * Even with this extra lfence, case 3-style still shows numbers like:
233  *              case 3, added crap: lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
234  * So either rdtscp is somehow faster due to internal-processor-caching (a
235  * previous rdtsc makes the next rdtscp somewhat faster sometimes, including
236  * after some instructions and an lfence), or the baseline case of no variation
237  * is "wrong", and we really should expect between 28 and 32.  FWIW, the Intel
238  * author also had a max deviation of 4 (per line).  And remember, on rare
239  * occasions we get a 28 for case 3 and 4 (the other 9999999 times it is 32).
240  *
241  * Note how the modified case 3 is pretty much the same *in performance* as a
242  * case 5.  But its code is nearly identical to case 2.  If you change the start
243  * measurement's rdtscp to an rdtsc, the min goes from 28 -> 44 (this is case
244  * 2).  And if you change the end measurements rdtscp to an lfence; rdtscp, we
245  * go from 44->48 (this is no case).  Then if you change that rdtscp to an
246  * rdtsc, we drop from 48->28 (this is case 5).  Based on this, it looks like
247  * the different types of rdtsc take their time measurement at different points
248  * within their execution.  rdtsc probably takes its measurement earlier in the
249  * instruction (~16-20 cycles/ticks earlier perhaps?), based on the 48->28
250  * back-side step and the front-side 28->44 step.
251  *
252  * Anyway, what matters is a relatively stable method without a lot of variance
253  * that has a solid floor/min that we can detect at runtime (to run tests on a
254  * given machine).  Using rdtscp for the start measurement seems unreliable
255  * (when run alone we get 32, when run with things we get 28, on the corei7).
256  * So even though case 3 and 4 had nice low variances and deviations, I don't
257  * trust it, and would rather go with something that always gives me the same
258  * result (as well as being a low result).  So case 5 will be my go-to for now.
259  * It should have the same protection as the others (perhaps 6 is better), it is
260  * stable, and it has a low overhead and low resolution (less capacity to hide
261  * instruction latency).  Finally, the start and end measurements use the same
262  * code, which is very convenient.
263  *
264  * This isn't conclusive - we'd need to do more tests with different workloads
265  * on different machines, and probably talk to an intel architect.
266  *
267  * Still reading?  There's one more thing: System Management Mode!  This is an
268  * interrupt context that is invisible to the OS, but we can see its effects in
269  * our measurements.  If you run this code with the default settings, you often
270  * won't see it (unless you have some loops).  However, if you run with
271  * 1024x16384 (0x400 by 0x4000), you are likely to see very large max
272  * deviations, such as 100, 600, or even 1500000.  From what I can tell, the
273  * likelihood depends on how long the inner loop.  Using case 5 at 0x400,
274  * 0x4000, after 3-4 runs, I had one line out of 1024 lines that was much
275  * higher.  Three were 112, one was 1659260.  AFAIK, this is system management
276  * mode kicking in.  You can mitigate this by disabling all types of USB legacy
277  * support in the BIOS.  Specifically, faking USB keyboards and mice (making
278  * them look like PS/2) and USB mass storage (making them look like a HDD) all
279  * lead to an increase in SMIs.  For more info, check out:
280  *              https://rt.wiki.kernel.org/index.php/HOWTO:_Build_an_RT-application
281  * It is not sufficient to merely not use things like the USB mass storage.  It
282  * needs to be disabled in the BIOS.  At least, this is true on my nehalem.  A
283  * while back, we had an issue with microbenchmarks taking 10% longer if you
284  * held down a key on the keyboard, even if the code was running on a core that
285  * did not receive the keyboard IRQ.  Turns out this was due to a USB keyboard
286  * in legacy mode.  The real root of this problem was SMM, which forces all
287  * cores to enter SMM whenever any core enters SMM (hence the cross-core
288  * interference).
289  *
290  * So finally, disable anything that may lead to SMM interference.  I have some
291  * code that runs at startup that tries to determine the min time for the given
292  * approved method of measurement (i.e., case 5), and also tries to detect SMIs
293  * via massive latency spikes.  */
294
295 #include <ros/common.h>
296 #include <arch/arch.h>
297 #include <stdio.h>
298 #include <kmalloc.h>
299 #include <time.h>
300 #include <smp.h>
301 #include <ros/procinfo.h>
302
303 #define STAT_SIZE_DEF 10000
304 #define LOOP_BOUND_DEF 1000
305
306 /* Fills in the **times with the results of the double loop measurement.  There
307  * are many options for start and end time measurements, all inside #if 0 #endif
308  * comments.  Copy/paste whichever you'd like to test out. */
309 static inline void filltimes(uint64_t **times, unsigned int loop_bound,
310                              unsigned int stat_size)
311 {
312         unsigned long flags;
313         int i, j;
314         uint64_t start, end;
315         unsigned int start_low, start_high, end_low, end_high;
316         unsigned int dummy_low, dummy_high;
317         volatile int variable = 0;
318         int8_t state = 0;
319
320         /* Variety of warmups.  recommended for cpuid... */
321         asm volatile ("cpuid\n\t"
322                       "rdtsc\n\t"
323                       "cpuid\n\t"
324                       "rdtsc\n\t"
325                       "cpuid\n\t"
326                       "rdtsc\n\t"
327                       "mov %%edx, %0\n\t"
328                       "mov %%eax, %1\n\t": "=m" (dummy_high), "=m" (dummy_low)::
329                       "%eax", "%ebx", "%ecx", "%edx");
330         for (j = 0; j < loop_bound; j++) {
331                 for (i = 0; i < stat_size; i++) {
332                         variable = 0;
333                         /* starting side, i want to make sure we always copy out to memory
334                          * (stack), instead of sometimes using registers (and other times
335                          * not).  if you use =a, for instance, with no work, the compiler
336                          * will use esi and edi to store start_high and _low.
337                          *
338                          * The same concern is probably unnecessary at the end, but it might
339                          * keep the compiler from reserving the use of those registers.*/
340
341                         #if 0 /* extra crap before the measurement code */
342                         asm volatile (
343                                                   "lfence;"
344                                       "rdtsc;"
345                                                   "mov %%edx, %0;"
346                                                   "mov %%eax, %1;"
347                                                   : "=m" (dummy_high), "=m" (dummy_low)
348                                                   :
349                                                   : "%eax", "%edx");
350
351                         variable = i + j;
352                         #endif
353
354                         asm volatile (
355                                                   "lfence;"
356                                       "rdtsc;"
357                                                   "mov %%edx, %0;"
358                                                   "mov %%eax, %1;"
359                                                   : "=m" (start_high), "=m" (start_low)
360                                                   :
361                                                   : "%eax", "%edx");
362                         #if 0   /* types of start time measurements */
363                         asm volatile (
364                                       "cpuid;"
365                                       "rdtsc;"
366                                                   "mov %%edx, %0;"
367                                                   "mov %%eax, %1;"
368                                                   : "=m" (start_high), "=m" (start_low)
369                                                   :
370                                                   : "%eax", "%ebx", "%ecx", "%edx");
371                         asm volatile (
372                                                   "lfence;"
373                                       "rdtsc;"
374                                                   "mov %%edx, %0;"
375                                                   "mov %%eax, %1;"
376                                                   : "=m" (start_high), "=m" (start_low)
377                                                   :
378                                                   : "%eax", "%edx");
379                         asm volatile (
380                                                   "lfence;"
381                                       "rdtsc;"
382                                                   "lfence;"
383                                                   "mov %%edx, %0;"
384                                                   "mov %%eax, %1;"
385                                                   : "=m" (start_high), "=m" (start_low)
386                                                   :
387                                                   : "%eax", "%edx");
388
389                         asm volatile(
390                                      "rdtscp;"
391                                                   "mov %%edx, %0;"
392                                                   "mov %%eax, %1;"
393                                                  : "=m" (start_high), "=m" (start_low)
394                                                  :
395                                                  : "%eax", "%ecx", "%edx");
396                         #endif
397
398                         /* call the function to measure here */
399
400                         #if 0 /* some options for code to measure */
401                         variable = j;
402
403                         variable = i + j;
404
405                         for (int k = 0; k < j; k++)
406                                 variable = k;
407                         #endif
408
409                         asm volatile("lfence;"
410                                      "rdtsc;"
411                                      "mov %%edx, %0;"
412                                      "mov %%eax, %1;"
413                                                  : "=m" (end_high), "=m" (end_low)
414                                                  :
415                                                  : "%eax", "%edx");
416                         #if 0   /* types of end time measurements */
417                         asm volatile("cpuid;"
418                                      "rdtsc;"
419                                      "mov %%edx, %0;"
420                                      "mov %%eax, %1;"
421                                                  : "=m" (end_high), "=m" (end_low)
422                                                  :
423                                                  : "%eax", "%ebx", "%ecx", "%edx");
424                         asm volatile("lfence;"
425                                      "rdtsc;"
426                                      "mov %%edx, %0;"
427                                      "mov %%eax, %1;"
428                                                  : "=m" (end_high), "=m" (end_low)
429                                                  :
430                                                  : "%eax", "%edx");
431                         asm volatile("lfence;"
432                                      "rdtsc;"
433                                                   "lfence;"
434                                      "mov %%edx, %0;"
435                                      "mov %%eax, %1;"
436                                                  : "=m" (end_high), "=m" (end_low)
437                                                  :
438                                                  : "%eax", "%edx");
439
440                         asm volatile(
441                                      "rdtscp;"
442                                      "mov %%edx, %0;"
443                                      "mov %%eax, %1;"
444                                                  : "=m" (end_high), "=m" (end_low)
445                                                  :
446                                                  : "%eax", "%ecx", "%edx");
447                         asm volatile(
448                                      "rdtscp;"
449                                                  "lfence;"
450                                      "mov %%edx, %0;"
451                                      "mov %%eax, %1;"
452                                                  : "=m" (end_high), "=m" (end_low)
453                                                  :
454                                                  : "%eax", "%ecx", "%edx");
455                         asm volatile(
456                                      "rdtscp;"
457                                      "mov %%edx, %0;"
458                                      "mov %%eax, %1;"
459                                      "cpuid;"
460                                                  : "=m" (end_high), "=m" (end_low)
461                                                  :
462                                                  : "%eax", "%ebx", "%ecx", "%edx");
463                         #endif
464
465                         start = ( ((uint64_t)start_high << 32) | start_low );
466                         end = ( ((uint64_t)end_high << 32) | end_low );
467
468                         if ( (int64_t)(end - start) < 0) {
469                                 printk("CRITICAL ERROR IN TAKING THE TIME!!!!!!\n"
470                        "loop(%d) stat(%d) start = %llu, end = %llu, "
471                        "variable = %u\n", j, i, start, end, variable);
472                                 times[j][i] = 0;
473                         } else {
474                                 times[j][i] = end - start;
475                         }
476                 }
477         }
478 }
479
480 /* http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance, doing pop
481  * variance, multiplying by N/N, and not checking overflow of size*size */
482 uint64_t var_calc(uint64_t *inputs, int size)
483 {
484         int i;
485         uint64_t acc = 0, previous = 0, temp_var = 0;
486         for (i = 0; i < size; i++) {
487                 if (acc < previous)
488                         goto overflow;
489                 previous = acc;
490                 acc += inputs[i];
491         }
492         acc = acc * acc;
493         if (acc < previous)
494                 goto overflow;
495         previous = 0;
496         for (i = 0; i < size; i++) {
497                 if (temp_var < previous)
498                         goto overflow;
499                 previous = temp_var;
500                 temp_var+= (inputs[i]*inputs[i]);
501         }
502         temp_var = temp_var * size;
503         if (temp_var < previous)
504                 goto overflow;
505         temp_var = (temp_var - acc)/(((uint64_t)(size))*((uint64_t)(size)));
506         return (temp_var);
507 overflow:
508         printk("CRITICAL OVERFLOW ERROR IN var_calc!!!!!!\n\n");
509         return -1;
510 }
511
512 int test_rdtsc(unsigned int loop_bound, unsigned int stat_size)
513 {
514         int8_t state = 0;
515
516         int i = 0, j = 0, spurious = 0, k = 0;
517         uint64_t **times;
518         uint64_t *variances;
519         uint64_t *min_values;
520         uint64_t max_dev = 0, min_time = 0, max_time = 0, prev_min = 0;
521         uint64_t tot_var = 0, max_dev_all = 0, var_of_vars = 0, var_of_mins = 0;
522         loop_bound = loop_bound ?: LOOP_BOUND_DEF;
523         stat_size = stat_size ?: STAT_SIZE_DEF;
524
525         printk("Running rdtsc tests...\n");
526
527         times = kmalloc(loop_bound * sizeof(uint64_t*), 0);
528         if (!times) {
529                 printk("unable to allocate memory for times\n");
530                 return 0;
531         }
532
533         for (j = 0; j < loop_bound; j++) {
534                 times[j] = kmalloc(stat_size * sizeof(uint64_t), 0);
535                 if (!times[j]) {
536                         printk("unable to allocate memory for times[%d]\n", j);
537                         for (k = 0; k < j; k++)
538                                 kfree(times[k]);
539                         return 0;
540                 }
541         }
542
543         variances = kmalloc(loop_bound * sizeof(uint64_t), 0);
544         if (!variances) {
545                 printk("unable to allocate memory for variances\n");
546                 // not bothering to free **times
547                 return 0;
548         }
549
550         min_values = kmalloc(loop_bound * sizeof(uint64_t), 0);
551         if (!min_values) {
552                 printk("unable to allocate memory for min_values\n");
553                 // not bothering to free **times or variances
554                 return 0;
555         }
556
557         disable_irqsave(&state);
558
559         filltimes(times, loop_bound, stat_size);
560
561         enable_irqsave(&state);
562
563         for (j = 0; j < loop_bound; j++) {
564                 max_dev = 0;
565                 min_time = 0;
566                 max_time = 0;
567
568                 for (i = 0; i < stat_size; i++) {
569                         if ((min_time == 0) || (min_time > times[j][i]))
570                                 min_time = times[j][i];
571                         if (max_time < times[j][i])
572                                 max_time = times[j][i];
573                 }
574                 max_dev = max_time - min_time;
575                 min_values[j] = min_time;
576                 if ((prev_min != 0) && (prev_min > min_time))
577                         spurious++;
578                 if (max_dev > max_dev_all)
579                         max_dev_all = max_dev;
580                 variances[j] = var_calc(times[j], stat_size);
581                 tot_var += variances[j];
582
583                 printk("loop_size:%d >>>> variance(cycles): %llu; "
584                "max_deviation: %llu; min time: %llu\n", j, variances[j],
585                max_dev, min_time);
586                 prev_min = min_time;
587         }
588
589         var_of_vars = var_calc(variances, loop_bound);
590         var_of_mins = var_calc(min_values, loop_bound);
591
592         printk("total number of spurious min values = %d\n", spurious);
593         /* is this next one the mean variance, not the total? */
594         printk("total variance = %llu\n", (tot_var/loop_bound));
595         printk("absolute max deviation = %llu\n", max_dev_all);
596         printk("variance of variances = %llu\n", var_of_vars);
597         printk("variance of minimum values = %llu\n", var_of_mins);
598
599         for (j = 0; j < loop_bound; j++) {
600                 kfree(times[j]);
601         }
602         kfree(times);
603         kfree(variances);
604         kfree(min_values);
605         return 0;
606 }
607
608
609 /* Crude SMI or other TSC-instability detection. */
610 bool check_timing_stability(void)
611 {
612         uint64_t min_overhead = UINT64_MAX;
613         uint64_t max_overhead = 0;
614         uint64_t start, end, diff;
615         uint32_t edx;
616         int8_t irq_state = 0;
617         volatile int dummy = 0;
618
619         /* Don't even bother if we don't have an invariant TSC */
620         cpuid(0x80000007, 0x0, 0, 0, 0, &edx);
621         if (!(edx & (1 << 8))) {
622                 printk("Invariant TSC not present.  Do not benchmark!\n");
623                 return FALSE;
624         }
625         disable_irqsave(&irq_state);
626         /* 2mil detected an SMI about 95% of the time on my nehalem. */
627         for (int i = 0; i < 3000000; i++) {
628                 start = read_tsc_serialized();
629                 for (int j = 0; j < 500; j++)
630                         dummy = j;
631                 end = read_tsc_serialized();
632                 if ((int64_t)(end - start) < 0) {
633                         printk("TSC stability overflow error!\n");
634                         return FALSE;
635                 }
636                 diff = end - start;
637                 min_overhead = MIN(min_overhead, diff);
638                 max_overhead = MAX(max_overhead, diff);
639         }
640         enable_irqsave(&irq_state);
641         if (max_overhead - min_overhead > 50) {
642                 printk("Test TSC overhead unstable (Min: %llu, Max: %llu).  "
643                        "Do not benchmark!\n", min_overhead, max_overhead);
644                 return FALSE;
645         }
646         return TRUE;
647 }
648
649 void test_tsc_cycles(void)
650 {
651         uint64_t start, end;
652         int8_t irq_state = 0;
653
654         disable_irqsave(&irq_state);
655         start = read_tsc_serialized();
656         for (int i = 0; i < 1000; i++) {
657                 asm volatile ("addl $1, %%eax;"
658                           "addl $1, %%eax;"
659                           "addl $1, %%eax;"
660                           "addl $1, %%eax;"
661                           "addl $1, %%eax;"
662                           "addl $1, %%eax;"
663                           "addl $1, %%eax;"
664                           "addl $1, %%eax;"
665                           "addl $1, %%eax;"
666                           "addl $1, %%eax;"
667                           "addl $1, %%eax;"
668                           "addl $1, %%eax;"
669                           "addl $1, %%eax;"
670                           "addl $1, %%eax;"
671                           "addl $1, %%eax;"
672                           "addl $1, %%eax;"
673                           "addl $1, %%eax;"
674                           "addl $1, %%eax;"
675                           "addl $1, %%eax;"
676                           "addl $1, %%eax;"
677                           "addl $1, %%eax;"
678                           "addl $1, %%eax;"
679                           "addl $1, %%eax;"
680                           "addl $1, %%eax;"
681                           "addl $1, %%eax;"
682                           "addl $1, %%eax;"
683                           "addl $1, %%eax;"
684                           "addl $1, %%eax;"
685                           "addl $1, %%eax;"
686                           "addl $1, %%eax;"
687                           "addl $1, %%eax;"
688                           "addl $1, %%eax;"
689                           "addl $1, %%eax;"
690                           "addl $1, %%eax;"
691                           "addl $1, %%eax;"
692                           "addl $1, %%eax;"
693                           "addl $1, %%eax;"
694                           "addl $1, %%eax;"
695                           "addl $1, %%eax;"
696                           "addl $1, %%eax;"
697                           "addl $1, %%eax;"
698                           "addl $1, %%eax;"
699                           "addl $1, %%eax;"
700                           "addl $1, %%eax;"
701                           "addl $1, %%eax;"
702                           "addl $1, %%eax;"
703                           "addl $1, %%eax;"
704                           "addl $1, %%eax;"
705                           "addl $1, %%eax;"
706                           "addl $1, %%eax;"
707                           "addl $1, %%eax;"
708                           "addl $1, %%eax;"
709                           "addl $1, %%eax;"
710                           "addl $1, %%eax;"
711                           "addl $1, %%eax;"
712                           "addl $1, %%eax;"
713                           "addl $1, %%eax;"
714                           "addl $1, %%eax;"
715                           "addl $1, %%eax;"
716                           "addl $1, %%eax;"
717                           "addl $1, %%eax;"
718                           "addl $1, %%eax;"
719                           "addl $1, %%eax;"
720                           "addl $1, %%eax;"
721                           "addl $1, %%eax;"
722                           "addl $1, %%eax;"
723                           "addl $1, %%eax;"
724                           "addl $1, %%eax;"
725                           "addl $1, %%eax;"
726                           "addl $1, %%eax;"
727                           "addl $1, %%eax;"
728                           "addl $1, %%eax;"
729                           "addl $1, %%eax;"
730                           "addl $1, %%eax;"
731                           "addl $1, %%eax;"
732                           "addl $1, %%eax;"
733                           "addl $1, %%eax;"
734                           "addl $1, %%eax;"
735                           "addl $1, %%eax;"
736                           "addl $1, %%eax;"
737                           "addl $1, %%eax;"
738                           "addl $1, %%eax;"
739                           "addl $1, %%eax;"
740                           "addl $1, %%eax;"
741                           "addl $1, %%eax;"
742                           "addl $1, %%eax;"
743                           "addl $1, %%eax;"
744                           "addl $1, %%eax;"
745                           "addl $1, %%eax;"
746                           "addl $1, %%eax;"
747                           "addl $1, %%eax;"
748                           "addl $1, %%eax;"
749                           "addl $1, %%eax;"
750                           "addl $1, %%eax;"
751                           "addl $1, %%eax;"
752                           "addl $1, %%eax;"
753                           "addl $1, %%eax;"
754                           "addl $1, %%eax;"
755                           "addl $1, %%eax;"
756                           "addl $1, %%eax;"
757                                       : : : "eax", "cc");
758         }
759         end = read_tsc_serialized();
760         end = end - start - __proc_global_info.tsc_overhead;
761         printk("%llu (100,000) ticks passed, run twice to load the icache\n", end);
762
763         enable_irqsave(&irq_state);
764 }
765
766 static inline __attribute__((always_inline))
767 uint64_t pmc_cycles(void)
768 {
769         unsigned int a = 0, d = 0;
770         int ecx = (1 << 30) + 1;
771
772         asm volatile("lfence; rdpmc" : "=a"(a), "=d"(d) : "c"(ecx));
773         return ((uint64_t)a) | (((uint64_t)d) << 32);
774 }
775
776 /* run with $ perf stat m kfunc wrmsr_test 0xMSR 100000 */
777 void wrmsr_test(unsigned int msr, int loops)
778 {
779         uint64_t start_cycles, diff_cycles;
780         uint64_t start_time, diff_time;
781         uint64_t msrval = read_msr(msr);
782
783         loops = MAX(loops, 1);
784         start_cycles = pmc_cycles();
785         start_time = start_timing();
786
787         for (int i = 0; i < loops; i++)
788                 write_msr(msr, msrval);
789
790         diff_cycles = pmc_cycles() - start_cycles;
791         diff_time = stop_timing(start_time);
792
793         printk("msr 0x%x, cycles per: %llu, nsec per: %llu\n", msr,
794                diff_cycles / loops, tsc2nsec(diff_time) / loops);
795 }
796
797 /* Does a basic test for interference.  You should kfunc this, often after
798  * starting the monitor on another core.  You can spam it with ipi_spam().
799  * You'll also need the PMCs to run.  Easiest way is with:
800  * $ perf stat -e cycles sleep 9999999. */
801 void interference_test(void)
802 {
803         #define THRESHOLD 200
804         uint64_t low_samples[THRESHOLD] = {0};
805         uint64_t deadline = sec2tsc(5); /* assumes TSC and cycles are close */
806         uint64_t start, diff;
807         size_t nr_below_thresh = 0;
808         size_t nr_over_thresh = 0;
809         size_t total = 0;
810         size_t max = 0;
811
812     deadline += pmc_cycles();
813         enable_irq();
814         do {
815                 total++;
816                 start = pmc_cycles();
817                 diff = pmc_cycles() - start;
818                 if (diff < COUNT_OF(low_samples))
819                         low_samples[diff]++;
820                 max = diff > max ? diff : max;
821                 if (diff < THRESHOLD)
822                         nr_below_thresh++;
823                 else
824                         nr_over_thresh++;
825                 if (!start) {
826                         warn("rdpmc got 0, is perf stat -e cycles running? (aborting)");
827                         break;
828                 }
829         } while (start < deadline);
830         disable_irq();
831
832         printk("\nCore %d\n--------\n", core_id());
833         for (int i = 0; i < COUNT_OF(low_samples); i++) {
834                 if (low_samples[i])
835                         printk("\t[ %2d ] : %lu\n", i, low_samples[i]);
836         }
837         printk("Total loops %lu, threshold %u\n", total, THRESHOLD);
838         printk("Nr over thresh %lu\n", nr_over_thresh);
839         printk("Nr below thresh %lu\n", nr_below_thresh);
840         printk("Max %lu\n", max);
841 }
842
843 /* Kfunc this to spam a core with IPIs */
844 void ipi_spam(int coreid)
845 {
846         for (int i = 0; i < 1000; i++) {
847                 send_ipi(coreid, I_POKE_CORE);
848                 udelay(1000);
849         }
850 }
851
852 /* Kfunc this to halt with IRQs off.  Note this doesn't fully work as
853  * advertised.  Keyboard and NIC IRQs still wake it up, but LAPIC timers don't
854  * seem to. */
855 void superhalt(void)
856 {
857         unsigned int x86_cstate = X86_MWAIT_C2;
858
859         disable_irq();
860         asm volatile("monitor" : : "a"(KERNBASE), "c"(0), "d"(0));
861         asm volatile("mwait" : : "c"(0x0), "a"(x86_cstate) : "memory");
862         printk("Core %d woke from superhalt!\n", core_id());
863 }