summaryrefslogtreecommitdiffstats
path: root/libnetdata/storage_number
diff options
context:
space:
mode:
Diffstat (limited to 'libnetdata/storage_number')
-rw-r--r--libnetdata/storage_number/Makefile.am12
-rw-r--r--libnetdata/storage_number/README.md17
-rw-r--r--libnetdata/storage_number/storage_number.c231
-rw-r--r--libnetdata/storage_number/storage_number.h232
-rw-r--r--libnetdata/storage_number/tests/Makefile.am4
-rw-r--r--libnetdata/storage_number/tests/test_storage_number.c52
6 files changed, 548 insertions, 0 deletions
diff --git a/libnetdata/storage_number/Makefile.am b/libnetdata/storage_number/Makefile.am
new file mode 100644
index 0000000..c5f8450
--- /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 0000000..4cd19a9
--- /dev/null
+++ b/libnetdata/storage_number/README.md
@@ -0,0 +1,17 @@
+<!--
+title: "Netdata storage number"
+custom_edit_url: https://github.com/netdata/netdata/edit/master/libnetdata/storage_number/README.md
+-->
+
+# 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 0000000..7511f3a
--- /dev/null
+++ b/libnetdata/storage_number/storage_number.c
@@ -0,0 +1,231 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#include "../libnetdata.h"
+
+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
+ 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 );
+}
+*/
+
+int print_netdata_double(char *str, NETDATA_DOUBLE value) {
+ // info("printing number " NETDATA_DOUBLE_FORMAT, value);
+ char integral_str[50], fractional_str[50];
+
+ char *wstr = str;
+
+ if(unlikely(value < 0)) {
+ *wstr++ = '-';
+ value = -value;
+ }
+
+ NETDATA_DOUBLE integral, fractional;
+
+#ifdef STORAGE_WITH_MATH
+ fractional = modfndd(value, &integral) * 10000000.0;
+#else
+ integral = (NETDATA_DOUBLE)((unsigned long long)(value * 10000000ULL) / 10000000ULL);
+ fractional = (NETDATA_DOUBLE)((unsigned long long)(value * 10000000ULL) % 10000000ULL);
+#endif
+
+ unsigned long long integral_int = (unsigned long long)integral;
+ unsigned long long fractional_int = (unsigned long long)llrintndd(fractional);
+ if(unlikely(fractional_int >= 10000000)) {
+ integral_int += 1;
+ fractional_int -= 10000000;
+ }
+
+ // info("integral " NETDATA_DOUBLE_FORMAT " (%llu), fractional " NETDATA_DOUBLE_FORMAT " (%llu)", integral, integral_int, fractional, fractional_int);
+
+ char *istre;
+ if(unlikely(integral_int == 0)) {
+ integral_str[0] = '0';
+ istre = &integral_str[1];
+ }
+ else
+ // convert the integral part to string (reversed)
+ istre = print_number_llu_r_smart(integral_str, integral_int);
+
+ // copy reversed the integral string
+ istre--;
+ while( istre >= integral_str ) *wstr++ = *istre--;
+
+ if(likely(fractional_int != 0)) {
+ // add a dot
+ *wstr++ = '.';
+
+ // convert the fractional part to string (reversed)
+ char *fstre = print_number_llu_r_smart(fractional_str, fractional_int);
+
+ // prepend zeros to reach 7 digits length
+ int decimal = 7;
+ int len = (int)(fstre - fractional_str);
+ while(len < decimal) {
+ *wstr++ = '0';
+ len++;
+ }
+
+ char *begin = fractional_str;
+ while(begin < fstre && *begin == '0') begin++;
+
+ // copy reversed the fractional string
+ fstre--;
+ while( fstre >= begin ) *wstr++ = *fstre--;
+ }
+
+ *wstr = '\0';
+ // info("printed number '%s'", str);
+ return (int)(wstr - str);
+}
diff --git a/libnetdata/storage_number/storage_number.h b/libnetdata/storage_number/storage_number.h
new file mode 100644
index 0000000..faea477
--- /dev/null
+++ b/libnetdata/storage_number/storage_number.h
@@ -0,0 +1,232 @@
+// SPDX-License-Identifier: GPL-3.0-or-later
+
+#ifndef NETDATA_STORAGE_NUMBER_H
+#define NETDATA_STORAGE_NUMBER_H 1
+
+#include <math.h>
+#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_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)
+
+#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_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)
+
+#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
+
+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));
+
+int print_netdata_double(char *str, NETDATA_DOUBLE value);
+
+// 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;
+}
+
+static inline NETDATA_DOUBLE str2ndd(const char *s, char **endptr) {
+ int negative = 0;
+ const char *start = s;
+ unsigned long long integer_part = 0;
+ unsigned long decimal_part = 0;
+ size_t decimal_digits = 0;
+
+ switch(*s) {
+ case '-':
+ s++;
+ negative = 1;
+ break;
+
+ case '+':
+ s++;
+ break;
+
+ case 'n':
+ if(s[1] == 'a' && s[2] == 'n') {
+ if(endptr) *endptr = (char *)&s[3];
+ return NAN;
+ }
+ break;
+
+ case 'i':
+ if(s[1] == 'n' && s[2] == 'f') {
+ if(endptr) *endptr = (char *)&s[3];
+ return INFINITY;
+ }
+ break;
+
+ default:
+ break;
+ }
+
+ while (*s >= '0' && *s <= '9') {
+ integer_part = (integer_part * 10) + (*s - '0');
+ s++;
+ }
+
+ if(unlikely(*s == '.')) {
+ decimal_part = 0;
+ s++;
+
+ while (*s >= '0' && *s <= '9') {
+ decimal_part = (decimal_part * 10) + (*s - '0');
+ s++;
+ decimal_digits++;
+ }
+ }
+
+ if(unlikely(*s == 'e' || *s == 'E'))
+ return strtondd(start, endptr);
+
+ if(unlikely(endptr))
+ *endptr = (char *)s;
+
+ if(unlikely(negative)) {
+ if(unlikely(decimal_digits))
+ return -((NETDATA_DOUBLE)integer_part + (NETDATA_DOUBLE)decimal_part / powndd(10.0, decimal_digits));
+ else
+ return -((NETDATA_DOUBLE)integer_part);
+ }
+ else {
+ if(unlikely(decimal_digits))
+ return (NETDATA_DOUBLE)integer_part + (NETDATA_DOUBLE)decimal_part / powndd(10.0, decimal_digits);
+ else
+ return (NETDATA_DOUBLE)integer_part;
+ }
+}
+
+#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 0000000..babdcf0
--- /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 0000000..19309e5
--- /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 <setjmp.h>
+#include <cmocka.h>
+
+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);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-11 22:06:49 +0000