From be1c7e50e1e8809ea56f2c9d472eccd8ffd73a97 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 19 Apr 2024 04:57:58 +0200 Subject: Adding upstream version 1.44.3. Signed-off-by: Daniel Baumann --- libnetdata/storage_number/Makefile.am | 12 ++ libnetdata/storage_number/README.md | 21 ++ libnetdata/storage_number/storage_number.c | 233 +++++++++++++++++++++ libnetdata/storage_number/storage_number.h | 178 ++++++++++++++++ libnetdata/storage_number/tests/Makefile.am | 4 + .../storage_number/tests/test_storage_number.c | 52 +++++ 6 files changed, 500 insertions(+) create mode 100644 libnetdata/storage_number/Makefile.am create mode 100644 libnetdata/storage_number/README.md create mode 100644 libnetdata/storage_number/storage_number.c create mode 100644 libnetdata/storage_number/storage_number.h create mode 100644 libnetdata/storage_number/tests/Makefile.am create mode 100644 libnetdata/storage_number/tests/test_storage_number.c (limited to 'libnetdata/storage_number') diff --git a/libnetdata/storage_number/Makefile.am b/libnetdata/storage_number/Makefile.am new file mode 100644 index 00000000..c5f84504 --- /dev/null +++ b/libnetdata/storage_number/Makefile.am @@ -0,0 +1,12 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in + +SUBDIRS = \ + tests \ + $(NULL) + +dist_noinst_DATA = \ + README.md \ + $(NULL) diff --git a/libnetdata/storage_number/README.md b/libnetdata/storage_number/README.md new file mode 100644 index 00000000..2dd6df6c --- /dev/null +++ b/libnetdata/storage_number/README.md @@ -0,0 +1,21 @@ + + +# Netdata storage number + +Although `netdata` does all its calculations using `long double`, it stores all values using +a **custom-made 32-bit number**. + +This custom-made number can store in 29 bits values from `-167772150000000.0` to `167772150000000.0` +with a precision of 0.00001 (yes, it's a floating point number, meaning that higher integer values +have less decimal precision) and 3 bits for flags. + +This provides an extremely optimized memory footprint with just 0.0001% max accuracy loss. + + diff --git a/libnetdata/storage_number/storage_number.c b/libnetdata/storage_number/storage_number.c new file mode 100644 index 00000000..6468951b --- /dev/null +++ b/libnetdata/storage_number/storage_number.c @@ -0,0 +1,233 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../libnetdata.h" + +bool is_system_ieee754_double(void) { + static bool logged = false; + + struct { + NETDATA_DOUBLE original; + + union { + uint64_t i; + NETDATA_DOUBLE d; + }; + } tests[] = { + { .original = 1.25, .i = 0x3FF4000000000000 }, + { .original = 1.0, .i = 0x3FF0000000000000 }, + { .original = 2.0, .i = 0x4000000000000000 }, + { .original = 4.0, .i = 0x4010000000000000 }, + { .original = 8.8, .i = 0x402199999999999A }, + { .original = 16.16, .i = 0x403028F5C28F5C29 }, + { .original = 32.32, .i = 0x404028F5C28F5C29 }, + { .original = 64.64, .i = 0x405028F5C28F5C29 }, + { .original = 128.128, .i = 0x406004189374BC6A }, + { .original = 32768.32768, .i = 0x40E0000A7C5AC472 }, + { .original = 65536.65536, .i = 0x40F0000A7C5AC472 }, + { .original = -65536.65536, .i = 0xC0F0000A7C5AC472 }, + { .original = 65535.65535, .i = 0x40EFFFF4F8A0902E }, + { .original = -65535.65535, .i = 0xC0EFFFF4F8A0902E }, + { .original = 4.503599627e15, .i = 0x432FFFFFFFF4B180 }, + { .original = -4.503599627e15, .i = 0xC32FFFFFFFF4B180 }, + { .original = 1.25e25, .i = 0x4524ADF4B7320335 }, + { .original = 1.25e307, .i = 0x7FB1CCF385EBC8A0 }, + { .original = 1.25e-25, .i = 0x3AC357C299A88EA7 }, + { .original = 1.25e-100, .i = 0x2B317F7D4ED8C33E }, + { .original = NAN, .i = 0x7FF8000000000000 }, + { .original = -INFINITY, .i = 0xFFF0000000000000 }, + { .original = INFINITY, .i = 0x7FF0000000000000 }, + { .original = 1.25e-132, .i = 0x248C6463225AB7EC }, + { .original = 0.0, .i = 0x0000000000000000 }, + { .original = -0.0, .i = 0x8000000000000000 }, + { .original = DBL_MIN, .i = 0x0010000000000000 }, + { .original = DBL_MAX, .i = 0x7FEFFFFFFFFFFFFF }, + { .original = -DBL_MIN, .i = 0x8010000000000000 }, + { .original = -DBL_MAX, .i = 0xFFEFFFFFFFFFFFFF }, + }; + + size_t errors = 0; + size_t elements = sizeof(tests) / sizeof(tests[0]); + for(size_t i = 0; i < elements ; i++) { + uint64_t *ptr = (uint64_t *)&tests[i].original; + + if(*ptr != tests[i].i && (tests[i].original == tests[i].d || (isnan(tests[i].original) && isnan(tests[i].d)))) { + if(!logged) + netdata_log_info("IEEE754: test #%zu, value " NETDATA_DOUBLE_FORMAT_G " is represented in this system as %lX, but it was expected as %lX", + i+1, tests[i].original, *ptr, tests[i].i); + errors++; + } + } + + if(!errors && sizeof(NETDATA_DOUBLE) == sizeof(uint64_t)) { + if(!logged) + netdata_log_info("IEEE754: system is using IEEE754 DOUBLE PRECISION values"); + + logged = true; + return true; + } + else { + if(!logged) + netdata_log_info("IEEE754: system is NOT compatible with IEEE754 DOUBLE PRECISION values"); + + logged = true; + return false; + } +} + +storage_number pack_storage_number(NETDATA_DOUBLE value, SN_FLAGS flags) { + // bit 32 = sign 0:positive, 1:negative + // bit 31 = 0:divide, 1:multiply + // bit 30, 29, 28 = (multiplier or divider) 0-7 (8 total) + // bit 27 SN_EXISTS_100 + // bit 26 SN_EXISTS_RESET + // bit 25 SN_ANOMALY_BIT = 0: anomalous, 1: not anomalous + // bit 24 to bit 1 = the value + + if(unlikely(fpclassify(value) == FP_NAN || fpclassify(value) == FP_INFINITE)) + return SN_EMPTY_SLOT; + + storage_number r = flags & SN_USER_FLAGS; + + if(unlikely(fpclassify(value) == FP_ZERO || fpclassify(value) == FP_SUBNORMAL)) + return r; + + int m = 0; + NETDATA_DOUBLE n = value, factor = 10; + + // if the value is negative + // add the sign bit and make it positive + if(n < 0) { + r += SN_FLAG_NEGATIVE; // the sign bit 32 + n = -n; + } + + if(n / 10000000.0 > 0x00ffffff) { + factor = 100; + r |= SN_FLAG_NOT_EXISTS_MUL100; + } + + // make its integer part fit in 0x00ffffff + // by dividing it by 10 up to 7 times + // and increasing the multiplier + while(m < 7 && n > (NETDATA_DOUBLE)0x00ffffff) { + n /= factor; + m++; + } + + if(m) { + // the value was too big, and we divided it + // so, we add a multiplier to unpack it + r += SN_FLAG_MULTIPLY + (m << 27); // the multiplier m + + if(n > (NETDATA_DOUBLE)0x00ffffff) { + #ifdef NETDATA_INTERNAL_CHECKS + netdata_log_error("Number " NETDATA_DOUBLE_FORMAT " is too big.", value); + #endif + r += 0x00ffffff; + return r; + } + } + else { + // 0x0019999e is the number that can be multiplied + // by 10 to give 0x00ffffff + // while the value is below 0x0019999e we can + // multiply it by 10, up to 7 times, increasing + // the multiplier + while(m < 7 && n < (NETDATA_DOUBLE)0x0019999e) { + n *= 10; + m++; + } + + if (unlikely(n > (NETDATA_DOUBLE)0x00ffffff)) { + n /= 10; + m--; + } + // the value was small enough, and we multiplied it + // so, we add a divider to unpack it + r += (m << 27); // the divider m + } + +#ifdef STORAGE_WITH_MATH + // without this there are rounding problems + // example: 0.9 becomes 0.89 + r += lrint((double) n); +#else + r += (storage_number)n; +#endif + + return r; +} + +// Lookup table to make storage number unpacking efficient. +NETDATA_DOUBLE unpack_storage_number_lut10x[4 * 8]; + +__attribute__((constructor)) void initialize_lut(void) { + // The lookup table is partitioned in 4 subtables based on the + // values of the factor and exp bits. + for (int i = 0; i < 8; i++) { + // factor = 0 + unpack_storage_number_lut10x[0 * 8 + i] = 1 / pow(10, i); // exp = 0 + unpack_storage_number_lut10x[1 * 8 + i] = pow(10, i); // exp = 1 + + // factor = 1 + unpack_storage_number_lut10x[2 * 8 + i] = 1 / pow(100, i); // exp = 0 + unpack_storage_number_lut10x[3 * 8 + i] = pow(100, i); // exp = 1 + } +} + +/* +int print_netdata_double(char *str, NETDATA_DOUBLE value) +{ + char *wstr = str; + + int sign = (value < 0) ? 1 : 0; + if(sign) value = -value; + +#ifdef STORAGE_WITH_MATH + // without llrintl() there are rounding problems + // for example 0.9 becomes 0.89 + unsigned long long uvalue = (unsigned long long int) llrintl(value * (NETDATA_DOUBLE)100000); +#else + unsigned long long uvalue = value * (NETDATA_DOUBLE)100000; +#endif + + wstr = print_number_llu_r_smart(str, uvalue); + + // make sure we have 6 bytes at least + while((wstr - str) < 6) *wstr++ = '0'; + + // put the sign back + if(sign) *wstr++ = '-'; + + // reverse it + char *begin = str, *end = --wstr, aux; + while (end > begin) aux = *end, *end-- = *begin, *begin++ = aux; + // wstr--; + // strreverse(str, wstr); + + // remove trailing zeros + int decimal = 5; + while(decimal > 0 && *wstr == '0') { + *wstr-- = '\0'; + decimal--; + } + + // terminate it, one position to the right + // to let space for a dot + wstr[2] = '\0'; + + // make space for the dot + int i; + for(i = 0; i < decimal ;i++) { + wstr[1] = wstr[0]; + wstr--; + } + + // put the dot + if(wstr[2] == '\0') { wstr[1] = '\0'; decimal--; } + else wstr[1] = '.'; + + // return the buffer length + return (int) ((wstr - str) + 2 + decimal ); +} +*/ diff --git a/libnetdata/storage_number/storage_number.h b/libnetdata/storage_number/storage_number.h new file mode 100644 index 00000000..82c870d6 --- /dev/null +++ b/libnetdata/storage_number/storage_number.h @@ -0,0 +1,178 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#ifndef NETDATA_STORAGE_NUMBER_H +#define NETDATA_STORAGE_NUMBER_H 1 + +#include +#include "../libnetdata.h" + +#ifdef NETDATA_WITH_LONG_DOUBLE + +typedef long double NETDATA_DOUBLE; +#define NETDATA_DOUBLE_FORMAT "%0.7Lf" +#define NETDATA_DOUBLE_FORMAT_ZERO "%0.0Lf" +#define NETDATA_DOUBLE_FORMAT_AUTO "%Lf" +#define NETDATA_DOUBLE_MODIFIER "Lf" +#define NETDATA_DOUBLE_FORMAT_G "%0.19Le" + +#define NETDATA_DOUBLE_MAX LDBL_MAX + +#define strtondd(s, endptr) strtold(s, endptr) +#define powndd(x, y) powl(x, y) +#define llrintndd(x) llrintl(x) +#define roundndd(x) roundl(x) +#define sqrtndd(x) sqrtl(x) +#define copysignndd(x, y) copysignl(x, y) +#define modfndd(x, y) modfl(x, y) +#define fabsndd(x) fabsl(x) +#define floorndd(x) floorl(x) +#define ceilndd(x) ceill(x) +#define log10ndd(x) log10l(x) + +#else // NETDATA_WITH_LONG_DOUBLE + +typedef double NETDATA_DOUBLE; +#define NETDATA_DOUBLE_FORMAT "%0.7f" +#define NETDATA_DOUBLE_FORMAT_ZERO "%0.0f" +#define NETDATA_DOUBLE_FORMAT_AUTO "%f" +#define NETDATA_DOUBLE_MODIFIER "f" +#define NETDATA_DOUBLE_FORMAT_G "%0.19e" + +#define NETDATA_DOUBLE_MAX DBL_MAX + +#define strtondd(s, endptr) strtod(s, endptr) +#define powndd(x, y) pow(x, y) +#define llrintndd(x) llrint(x) +#define roundndd(x) round(x) +#define sqrtndd(x) sqrt(x) +#define copysignndd(x, y) copysign(x, y) +#define modfndd(x, y) modf(x, y) +#define fabsndd(x) fabs(x) +#define floorndd(x) floor(x) +#define ceilndd(x) ceil(x) +#define log10ndd(x) log10(x) + +#endif // NETDATA_WITH_LONG_DOUBLE + +typedef long long collected_number; +#define COLLECTED_NUMBER_FORMAT "%lld" + +#define epsilonndd (NETDATA_DOUBLE)0.0000001 +#define considered_equal_ndd(a, b) (fabsndd((a) - (b)) < epsilonndd) + +#if defined(HAVE_ISFINITE) || defined(isfinite) +// The isfinite() macro shall determine whether its argument has a +// finite value (zero, subnormal, or normal, and not infinite or NaN). +#define netdata_double_isnumber(a) (isfinite(a)) +#elif defined(HAVE_FINITE) || defined(finite) +#define netdata_double_isnumber(a) (finite(a)) +#else +#define netdata_double_isnumber(a) (fpclassify(a) != FP_NAN && fpclassify(a) != FP_INFINITE) +#endif + +#define netdata_double_is_zero(a) (!netdata_double_isnumber(a) || considered_equal_ndd(a, 0.0)) +#define netdata_double_is_nonzero(a) (!netdata_double_is_zero(a)) + +typedef uint32_t storage_number; + +typedef struct storage_number_tier1 { + float sum_value; + float min_value; + float max_value; + uint16_t count; + uint16_t anomaly_count; +} storage_number_tier1_t; + +#define STORAGE_NUMBER_FORMAT "%u" + +typedef enum { + SN_FLAG_NONE = 0, + SN_FLAG_NOT_ANOMALOUS = (1 << 24), // the anomaly bit of the value (0:anomalous, 1:not anomalous) + SN_FLAG_RESET = (1 << 25), // the value has been overflown + SN_FLAG_NOT_EXISTS_MUL100 = (1 << 26), // very large value (multiplier is 100 instead of 10) + SN_FLAG_MULTIPLY = (1 << 30), // multiply, else divide + SN_FLAG_NEGATIVE = (1 << 31), // negative, else positive +} SN_FLAGS; + +#define SN_USER_FLAGS (SN_FLAG_NOT_ANOMALOUS | SN_FLAG_RESET) + +// default flags for all storage numbers +// anomaly bit is reversed, so we set it by default +#define SN_DEFAULT_FLAGS SN_FLAG_NOT_ANOMALOUS + +// When the calculated number is zero and the value is anomalous (ie. it's bit +// is zero) we want to return a storage_number representation that is +// different from the empty slot. We achieve this by mapping zero to +// SN_EXISTS_100. Unpacking the SN_EXISTS_100 value will return zero because +// its fraction field (as well as its exponent factor field) will be zero. +#define SN_EMPTY_SLOT SN_FLAG_NOT_EXISTS_MUL100 + +// checks +#define does_storage_number_exist(value) (((storage_number)(value)) != SN_EMPTY_SLOT) +#define did_storage_number_reset(value) ((((storage_number)(value)) & SN_FLAG_RESET)) +#define is_storage_number_anomalous(value) (does_storage_number_exist(value) && !(((storage_number)(value)) & SN_FLAG_NOT_ANOMALOUS)) + +storage_number pack_storage_number(NETDATA_DOUBLE value, SN_FLAGS flags) __attribute__((const)); +static inline NETDATA_DOUBLE unpack_storage_number(storage_number value) __attribute__((const)); + +// sign div/mul <--- multiplier / divider ---> 10/100 RESET EXISTS VALUE +#define STORAGE_NUMBER_POSITIVE_MAX_RAW (storage_number)( (0 << 31) | (1 << 30) | (1 << 29) | (1 << 28) | (1 << 27) | (1 << 26) | (0 << 25) | (1 << 24) | 0x00ffffff ) +#define STORAGE_NUMBER_POSITIVE_MIN_RAW (storage_number)( (0 << 31) | (0 << 30) | (1 << 29) | (1 << 28) | (1 << 27) | (0 << 26) | (0 << 25) | (1 << 24) | 0x00000001 ) +#define STORAGE_NUMBER_NEGATIVE_MAX_RAW (storage_number)( (1 << 31) | (0 << 30) | (1 << 29) | (1 << 28) | (1 << 27) | (0 << 26) | (0 << 25) | (1 << 24) | 0x00000001 ) +#define STORAGE_NUMBER_NEGATIVE_MIN_RAW (storage_number)( (1 << 31) | (1 << 30) | (1 << 29) | (1 << 28) | (1 << 27) | (1 << 26) | (0 << 25) | (1 << 24) | 0x00ffffff ) + +// accepted accuracy loss +#define ACCURACY_LOSS_ACCEPTED_PERCENT 0.0001 +#define accuracy_loss(t1, t2) (((t1) == (t2) || (t1) == 0.0 || (t2) == 0.0) ? 0.0 : (100.0 - (((t1) > (t2)) ? ((t2) * 100.0 / (t1) ) : ((t1) * 100.0 / (t2))))) + +// Maximum acceptable rate of increase for counters. With a rate of 10% netdata can safely detect overflows with a +// period of at least every other 10 samples. +#define MAX_INCREMENTAL_PERCENT_RATE 10 + + +static inline NETDATA_DOUBLE unpack_storage_number(storage_number value) { + extern NETDATA_DOUBLE unpack_storage_number_lut10x[4 * 8]; + + if(unlikely(value == SN_EMPTY_SLOT)) + return NAN; + + int sign = 1, exp = 0; + int factor = 0; + + // bit 32 = 0:positive, 1:negative + if(unlikely(value & SN_FLAG_NEGATIVE)) + sign = -1; + + // bit 31 = 0:divide, 1:multiply + if(unlikely(value & SN_FLAG_MULTIPLY)) + exp = 1; + + // bit 27 SN_FLAG_NOT_EXISTS_MUL100 + if(unlikely(value & SN_FLAG_NOT_EXISTS_MUL100)) + factor = 1; + + // bit 26 SN_FLAG_RESET + // bit 25 SN_FLAG_NOT_ANOMALOUS + + // bit 30, 29, 28 = (multiplier or divider) 0-7 (8 total) + int mul = (int)((value & ((1<<29)|(1<<28)|(1<<27))) >> 27); + + // bit 24 to bit 1 = the value, so remove all other bits + value ^= value & ((1<<31)|(1<<30)|(1<<29)|(1<<28)|(1<<27)|(1<<26)|(1<<25)|(1<<24)); + + NETDATA_DOUBLE n = value; + + // fprintf(stderr, "UNPACK: %08X, sign = %d, exp = %d, mul = %d, factor = %d, n = " CALCULATED_NUMBER_FORMAT "\n", value, sign, exp, mul, factor, n); + + return sign * unpack_storage_number_lut10x[(factor * 16) + (exp * 8) + mul] * n; +} + +// all these prefixes should use characters that are not allowed in the numbers they represent +#define HEX_PREFIX "0x" // we check 2 characters when parsing +#define IEEE754_UINT64_B64_PREFIX "#" // we check the 1st character during parsing +#define IEEE754_DOUBLE_B64_PREFIX "@" // we check the 1st character during parsing +#define IEEE754_DOUBLE_HEX_PREFIX "%" // we check the 1st character during parsing + +bool is_system_ieee754_double(void); + +#endif /* NETDATA_STORAGE_NUMBER_H */ diff --git a/libnetdata/storage_number/tests/Makefile.am b/libnetdata/storage_number/tests/Makefile.am new file mode 100644 index 00000000..babdcf0d --- /dev/null +++ b/libnetdata/storage_number/tests/Makefile.am @@ -0,0 +1,4 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in diff --git a/libnetdata/storage_number/tests/test_storage_number.c b/libnetdata/storage_number/tests/test_storage_number.c new file mode 100644 index 00000000..19309e5c --- /dev/null +++ b/libnetdata/storage_number/tests/test_storage_number.c @@ -0,0 +1,52 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../../libnetdata.h" +#include "../../required_dummies.h" +#include +#include + +static void test_number_printing(void **state) +{ + (void)state; + + char value[50]; + + print_netdata_double(value, 0); + assert_string_equal(value, "0"); + + print_netdata_double(value, 0.0000001); + assert_string_equal(value, "0.0000001"); + + print_netdata_double(value, 0.00000009); + assert_string_equal(value, "0.0000001"); + + print_netdata_double(value, 0.000000001); + assert_string_equal(value, "0"); + + print_netdata_double(value, 99.99999999999999999); + assert_string_equal(value, "100"); + + print_netdata_double(value, -99.99999999999999999); + assert_string_equal(value, "-100"); + + print_netdata_double(value, 123.4567890123456789); + assert_string_equal(value, "123.456789"); + + print_netdata_double(value, 9999.9999999); + assert_string_equal(value, "9999.9999999"); + + print_netdata_double(value, -9999.9999999); + assert_string_equal(value, "-9999.9999999"); + + print_netdata_double(value, unpack_storage_number(pack_storage_number(16.777218L, SN_DEFAULT_FLAGS))); + assert_string_equal(value, "16.77722"); +} + +int main(void) +{ + const struct CMUnitTest tests[] = { + cmocka_unit_test(test_number_printing) + }; + + return cmocka_run_group_tests_name("storage_number", tests, NULL, NULL); +} -- cgit v1.2.3