stats: incorrect clock square algorithm 76/14376/2
authorMark Vitale <mvitale@sinenomine.net>
Mon, 18 Sep 2017 23:45:10 +0000 (19:45 -0400)
committerBenjamin Kaduk <kaduk@mit.edu>
Fri, 23 Oct 2020 16:25:43 +0000 (12:25 -0400)
commite1e5df918fee00d4d9152c31c24cc1e7f23b71a6
tree2864027dff135cb9b8497477bf84d3054eca709a
parente985d43d99d93172b5608a3c73fd3201d3b3a212
stats: incorrect clock square algorithm

Since the original IBM code import, OpenAFS has an algorithm for
squaring clock values, implemented identically in three different
places.  This algorithm does not account correctly for microsecs
overflow into seconds, resulting in incorrect "sum-of-squares" values
for queue and execution time in several OpenAFS performance utilities.

Specifically, this code:

        t1.tv_usec += (2 * t2.tv_sec * t2.tv_usec) % 1000000                   \
                      + (t2.tv_usec / 1000)*(t2.tv_usec / 1000)                \
                      + 2 * (t2.tv_usec / 1000) * (t2.tv_usec % 1000) / 1000   \
                      + (((t2.tv_usec % 1000) > 707) ? 1 : 0);                 \

Can allow for the tv_usec field to be increased by a theoretical max
of around:

        t1.tv_usec += 999998                                                   \
                      + 999*999                                                \
                      + 2 * 999 * 999 / 1000                                   \
                      + 1;                                                     \

Or:

        t1.tv_usec += 1999996;                                                 \

If t1.tv_usec is already 999999, after this calculation its value
could be as high as 2999995. So just checking once if t1.tv_usec is
over 1000000 is not sufficient, since the resulting value (1999995) is
still over 1000000.

Correct all implementations by repeatedly checking if tv_usec is over
1000000 after the above calculation:

macro                   affected utility
=====================   ============================
afs_stats_SquareAddTo   xstat_cm_test
fs_stats_SquareAddTo    xstat_fs_test
clock_AddSq             rxstat_get_process and _peer

Change-Id: I3145d592ba6bc1556729eac657f43d476c99eede
Reviewed-on: https://gerrit.openafs.org/14376
Tested-by: BuildBot <buildbot@rampaginggeek.com>
Reviewed-by: Cheyenne Wills <cwills@sinenomine.net>
Reviewed-by: Andrew Deason <adeason@sinenomine.net>
Reviewed-by: Benjamin Kaduk <kaduk@mit.edu>
src/afs/afs_stats.h
src/rx/rx_clock.h
src/viced/fs_stats.h