diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2018-11-07 12:22:44 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2018-11-07 12:22:44 +0000 |
commit | 1e6c93250172946eeb38e94a92a1fd12c9d3011e (patch) | |
tree | 8ca5e16dfc7ad6b3bf2738ca0a48408a950f8f7e /libnetdata/adaptive_resortable_list | |
parent | Update watch file (diff) | |
download | netdata-1e6c93250172946eeb38e94a92a1fd12c9d3011e.tar.xz netdata-1e6c93250172946eeb38e94a92a1fd12c9d3011e.zip |
Merging upstream version 1.11.0+dfsg.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'libnetdata/adaptive_resortable_list')
-rw-r--r-- | libnetdata/adaptive_resortable_list/Makefile.am | 9 | ||||
-rw-r--r-- | libnetdata/adaptive_resortable_list/Makefile.in | 464 | ||||
-rw-r--r-- | libnetdata/adaptive_resortable_list/README.md | 93 | ||||
-rw-r--r-- | libnetdata/adaptive_resortable_list/adaptive_resortable_list.c | 280 | ||||
-rw-r--r-- | libnetdata/adaptive_resortable_list/adaptive_resortable_list.h | 138 |
5 files changed, 984 insertions, 0 deletions
diff --git a/libnetdata/adaptive_resortable_list/Makefile.am b/libnetdata/adaptive_resortable_list/Makefile.am new file mode 100644 index 000000000..1cb69ed99 --- /dev/null +++ b/libnetdata/adaptive_resortable_list/Makefile.am @@ -0,0 +1,9 @@ +# SPDX-License-Identifier: GPL-3.0-or-later + +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in + + +dist_noinst_DATA = \ + README.md \ + $(NULL) diff --git a/libnetdata/adaptive_resortable_list/Makefile.in b/libnetdata/adaptive_resortable_list/Makefile.in new file mode 100644 index 000000000..229511083 --- /dev/null +++ b/libnetdata/adaptive_resortable_list/Makefile.in @@ -0,0 +1,464 @@ +# Makefile.in generated by automake 1.14.1 from Makefile.am. +# @configure_input@ + +# Copyright (C) 1994-2013 Free Software Foundation, Inc. + +# This Makefile.in is free software; the Free Software Foundation +# gives unlimited permission to copy and/or distribute it, +# with or without modifications, as long as this notice is preserved. + +# This program is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY, to the extent permitted by law; without +# even the implied warranty of MERCHANTABILITY or FITNESS FOR A +# PARTICULAR PURPOSE. + +@SET_MAKE@ + +# SPDX-License-Identifier: GPL-3.0-or-later + +VPATH = @srcdir@ +am__is_gnu_make = test -n '$(MAKEFILE_LIST)' && test -n '$(MAKELEVEL)' +am__make_running_with_option = \ + case $${target_option-} in \ + ?) ;; \ + *) echo "am__make_running_with_option: internal error: invalid" \ + "target option '$${target_option-}' specified" >&2; \ + exit 1;; \ + esac; \ + has_opt=no; \ + sane_makeflags=$$MAKEFLAGS; \ + if $(am__is_gnu_make); then \ + sane_makeflags=$$MFLAGS; \ + else \ + case $$MAKEFLAGS in \ + *\\[\ \ ]*) \ + bs=\\; \ + sane_makeflags=`printf '%s\n' "$$MAKEFLAGS" \ + | sed "s/$$bs$$bs[$$bs $$bs ]*//g"`;; \ + esac; \ + fi; \ + skip_next=no; \ + strip_trailopt () \ + { \ + flg=`printf '%s\n' "$$flg" | sed "s/$$1.*$$//"`; \ + }; \ + for flg in $$sane_makeflags; do \ + test $$skip_next = yes && { skip_next=no; continue; }; \ + case $$flg in \ + *=*|--*) continue;; \ + -*I) strip_trailopt 'I'; skip_next=yes;; \ + -*I?*) strip_trailopt 'I';; \ + -*O) strip_trailopt 'O'; skip_next=yes;; \ + -*O?*) strip_trailopt 'O';; \ + -*l) strip_trailopt 'l'; skip_next=yes;; \ + -*l?*) strip_trailopt 'l';; \ + -[dEDm]) skip_next=yes;; \ + -[JT]) skip_next=yes;; \ + esac; \ + case $$flg in \ + *$$target_option*) has_opt=yes; break;; \ + esac; \ + done; \ + test $$has_opt = yes +am__make_dryrun = (target_option=n; $(am__make_running_with_option)) +am__make_keepgoing = (target_option=k; $(am__make_running_with_option)) +pkgdatadir = $(datadir)/@PACKAGE@ +pkgincludedir = $(includedir)/@PACKAGE@ +pkglibdir = $(libdir)/@PACKAGE@ +pkglibexecdir = $(libexecdir)/@PACKAGE@ +am__cd = CDPATH="$${ZSH_VERSION+.}$(PATH_SEPARATOR)" && cd +install_sh_DATA = $(install_sh) -c -m 644 +install_sh_PROGRAM = $(install_sh) -c +install_sh_SCRIPT = $(install_sh) -c +INSTALL_HEADER = $(INSTALL_DATA) +transform = $(program_transform_name) +NORMAL_INSTALL = : +PRE_INSTALL = : +POST_INSTALL = : +NORMAL_UNINSTALL = : +PRE_UNINSTALL = : +POST_UNINSTALL = : +build_triplet = @build@ +host_triplet = @host@ +subdir = libnetdata/adaptive_resortable_list +DIST_COMMON = $(srcdir)/Makefile.in $(srcdir)/Makefile.am \ + $(dist_noinst_DATA) +ACLOCAL_M4 = $(top_srcdir)/aclocal.m4 +am__aclocal_m4_deps = $(top_srcdir)/build/m4/ax_c___atomic.m4 \ + $(top_srcdir)/build/m4/ax_c__generic.m4 \ + $(top_srcdir)/build/m4/ax_c_lto.m4 \ + $(top_srcdir)/build/m4/ax_c_mallinfo.m4 \ + $(top_srcdir)/build/m4/ax_c_mallopt.m4 \ + $(top_srcdir)/build/m4/ax_check_compile_flag.m4 \ + $(top_srcdir)/build/m4/ax_gcc_func_attribute.m4 \ + $(top_srcdir)/build/m4/ax_pthread.m4 \ + $(top_srcdir)/build/m4/jemalloc.m4 \ + $(top_srcdir)/build/m4/tcmalloc.m4 $(top_srcdir)/configure.ac +am__configure_deps = $(am__aclocal_m4_deps) $(CONFIGURE_DEPENDENCIES) \ + $(ACLOCAL_M4) +mkinstalldirs = $(install_sh) -d +CONFIG_HEADER = $(top_builddir)/config.h +CONFIG_CLEAN_FILES = +CONFIG_CLEAN_VPATH_FILES = +AM_V_P = $(am__v_P_@AM_V@) +am__v_P_ = $(am__v_P_@AM_DEFAULT_V@) +am__v_P_0 = false +am__v_P_1 = : +AM_V_GEN = $(am__v_GEN_@AM_V@) +am__v_GEN_ = $(am__v_GEN_@AM_DEFAULT_V@) +am__v_GEN_0 = @echo " GEN " $@; +am__v_GEN_1 = +AM_V_at = $(am__v_at_@AM_V@) +am__v_at_ = $(am__v_at_@AM_DEFAULT_V@) +am__v_at_0 = @ +am__v_at_1 = +SOURCES = +DIST_SOURCES = +am__can_run_installinfo = \ + case $$AM_UPDATE_INFO_DIR in \ + n|no|NO) false;; \ + *) (install-info --version) >/dev/null 2>&1;; \ + esac +DATA = $(dist_noinst_DATA) +am__tagged_files = $(HEADERS) $(SOURCES) $(TAGS_FILES) $(LISP) +DISTFILES = $(DIST_COMMON) $(DIST_SOURCES) $(TEXINFOS) $(EXTRA_DIST) +ACLOCAL = @ACLOCAL@ +AMTAR = @AMTAR@ +AM_DEFAULT_VERBOSITY = @AM_DEFAULT_VERBOSITY@ +AUTOCONF = @AUTOCONF@ +AUTOHEADER = @AUTOHEADER@ +AUTOMAKE = @AUTOMAKE@ +AWK = @AWK@ +CC = @CC@ +CCDEPMODE = @CCDEPMODE@ +CFLAGS = @CFLAGS@ +CPP = @CPP@ +CPPFLAGS = @CPPFLAGS@ +CYGPATH_W = @CYGPATH_W@ +DEFS = @DEFS@ +DEPDIR = @DEPDIR@ +ECHO_C = @ECHO_C@ +ECHO_N = @ECHO_N@ +ECHO_T = @ECHO_T@ +EGREP = @EGREP@ +EXEEXT = @EXEEXT@ +GREP = @GREP@ +INSTALL = @INSTALL@ +INSTALL_DATA = @INSTALL_DATA@ +INSTALL_PROGRAM = @INSTALL_PROGRAM@ +INSTALL_SCRIPT = @INSTALL_SCRIPT@ +INSTALL_STRIP_PROGRAM = @INSTALL_STRIP_PROGRAM@ +IPMIMONITORING_CFLAGS = @IPMIMONITORING_CFLAGS@ +IPMIMONITORING_LIBS = @IPMIMONITORING_LIBS@ +LDFLAGS = @LDFLAGS@ +LIBCAP_CFLAGS = @LIBCAP_CFLAGS@ +LIBCAP_LIBS = @LIBCAP_LIBS@ +LIBMNL_CFLAGS = @LIBMNL_CFLAGS@ +LIBMNL_LIBS = @LIBMNL_LIBS@ +LIBOBJS = @LIBOBJS@ +LIBS = @LIBS@ +LTLIBOBJS = @LTLIBOBJS@ +MAINT = @MAINT@ +MAKEINFO = @MAKEINFO@ +MATH_CFLAGS = @MATH_CFLAGS@ +MATH_LIBS = @MATH_LIBS@ +MKDIR_P = @MKDIR_P@ +NFACCT_CFLAGS = @NFACCT_CFLAGS@ +NFACCT_LIBS = @NFACCT_LIBS@ +OBJEXT = @OBJEXT@ +OPTIONAL_IPMIMONITORING_CFLAGS = @OPTIONAL_IPMIMONITORING_CFLAGS@ +OPTIONAL_IPMIMONITORING_LIBS = @OPTIONAL_IPMIMONITORING_LIBS@ +OPTIONAL_LIBCAP_CFLAGS = @OPTIONAL_LIBCAP_CFLAGS@ +OPTIONAL_LIBCAP_LIBS = @OPTIONAL_LIBCAP_LIBS@ +OPTIONAL_MATH_CLFAGS = @OPTIONAL_MATH_CLFAGS@ +OPTIONAL_MATH_LIBS = @OPTIONAL_MATH_LIBS@ +OPTIONAL_NFACCT_CLFAGS = @OPTIONAL_NFACCT_CLFAGS@ +OPTIONAL_NFACCT_LIBS = @OPTIONAL_NFACCT_LIBS@ +OPTIONAL_UUID_CLFAGS = @OPTIONAL_UUID_CLFAGS@ +OPTIONAL_UUID_LIBS = @OPTIONAL_UUID_LIBS@ +OPTIONAL_ZLIB_CLFAGS = @OPTIONAL_ZLIB_CLFAGS@ +OPTIONAL_ZLIB_LIBS = @OPTIONAL_ZLIB_LIBS@ +PACKAGE = @PACKAGE@ +PACKAGE_BUGREPORT = @PACKAGE_BUGREPORT@ +PACKAGE_NAME = @PACKAGE_NAME@ +PACKAGE_RPM_RELEASE = @PACKAGE_RPM_RELEASE@ +PACKAGE_RPM_VERSION = @PACKAGE_RPM_VERSION@ +PACKAGE_STRING = @PACKAGE_STRING@ +PACKAGE_TARNAME = @PACKAGE_TARNAME@ +PACKAGE_URL = @PACKAGE_URL@ +PACKAGE_VERSION = @PACKAGE_VERSION@ +PATH_SEPARATOR = @PATH_SEPARATOR@ +PKG_CONFIG = @PKG_CONFIG@ +PKG_CONFIG_LIBDIR = @PKG_CONFIG_LIBDIR@ +PKG_CONFIG_PATH = @PKG_CONFIG_PATH@ +PTHREAD_CC = @PTHREAD_CC@ +PTHREAD_CFLAGS = @PTHREAD_CFLAGS@ +PTHREAD_LIBS = @PTHREAD_LIBS@ +SET_MAKE = @SET_MAKE@ +SHELL = @SHELL@ +SSE_CANDIDATE = @SSE_CANDIDATE@ +STRIP = @STRIP@ +UUID_CFLAGS = @UUID_CFLAGS@ +UUID_LIBS = @UUID_LIBS@ +VERSION = @VERSION@ +ZLIB_CFLAGS = @ZLIB_CFLAGS@ +ZLIB_LIBS = @ZLIB_LIBS@ +abs_builddir = @abs_builddir@ +abs_srcdir = @abs_srcdir@ +abs_top_builddir = @abs_top_builddir@ +abs_top_srcdir = @abs_top_srcdir@ +ac_ct_CC = @ac_ct_CC@ +am__include = @am__include@ +am__leading_dot = @am__leading_dot@ +am__quote = @am__quote@ +am__tar = @am__tar@ +am__untar = @am__untar@ +ax_pthread_config = @ax_pthread_config@ +bindir = @bindir@ +build = @build@ +build_alias = @build_alias@ +build_cpu = @build_cpu@ +build_os = @build_os@ +build_target = @build_target@ +build_vendor = @build_vendor@ +builddir = @builddir@ +cachedir = @cachedir@ +chartsdir = @chartsdir@ +configdir = @configdir@ +datadir = @datadir@ +datarootdir = @datarootdir@ +docdir = @docdir@ +dvidir = @dvidir@ +exec_prefix = @exec_prefix@ +has_jemalloc = @has_jemalloc@ +has_tcmalloc = @has_tcmalloc@ +host = @host@ +host_alias = @host_alias@ +host_cpu = @host_cpu@ +host_os = @host_os@ +host_vendor = @host_vendor@ +htmldir = @htmldir@ +includedir = @includedir@ +infodir = @infodir@ +install_sh = @install_sh@ +libconfigdir = @libconfigdir@ +libdir = @libdir@ +libexecdir = @libexecdir@ +localedir = @localedir@ +localstatedir = @localstatedir@ +logdir = @logdir@ +mandir = @mandir@ +mkdir_p = @mkdir_p@ +nodedir = @nodedir@ +oldincludedir = @oldincludedir@ +pdfdir = @pdfdir@ +pluginsdir = @pluginsdir@ +prefix = @prefix@ +program_transform_name = @program_transform_name@ +psdir = @psdir@ +pythondir = @pythondir@ +registrydir = @registrydir@ +sbindir = @sbindir@ +sharedstatedir = @sharedstatedir@ +srcdir = @srcdir@ +sysconfdir = @sysconfdir@ +target_alias = @target_alias@ +top_build_prefix = @top_build_prefix@ +top_builddir = @top_builddir@ +top_srcdir = @top_srcdir@ +varlibdir = @varlibdir@ +webdir = @webdir@ +AUTOMAKE_OPTIONS = subdir-objects +MAINTAINERCLEANFILES = $(srcdir)/Makefile.in +dist_noinst_DATA = \ + README.md \ + $(NULL) + +all: all-am + +.SUFFIXES: +$(srcdir)/Makefile.in: @MAINTAINER_MODE_TRUE@ $(srcdir)/Makefile.am $(am__configure_deps) + @for dep in $?; do \ + case '$(am__configure_deps)' in \ + *$$dep*) \ + ( cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh ) \ + && { if test -f $@; then exit 0; else break; fi; }; \ + exit 1;; \ + esac; \ + done; \ + echo ' cd $(top_srcdir) && $(AUTOMAKE) --gnu libnetdata/adaptive_resortable_list/Makefile'; \ + $(am__cd) $(top_srcdir) && \ + $(AUTOMAKE) --gnu libnetdata/adaptive_resortable_list/Makefile +.PRECIOUS: Makefile +Makefile: $(srcdir)/Makefile.in $(top_builddir)/config.status + @case '$?' in \ + *config.status*) \ + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh;; \ + *) \ + echo ' cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe)'; \ + cd $(top_builddir) && $(SHELL) ./config.status $(subdir)/$@ $(am__depfiles_maybe);; \ + esac; + +$(top_builddir)/config.status: $(top_srcdir)/configure $(CONFIG_STATUS_DEPENDENCIES) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh + +$(top_srcdir)/configure: @MAINTAINER_MODE_TRUE@ $(am__configure_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(ACLOCAL_M4): @MAINTAINER_MODE_TRUE@ $(am__aclocal_m4_deps) + cd $(top_builddir) && $(MAKE) $(AM_MAKEFLAGS) am--refresh +$(am__aclocal_m4_deps): +tags TAGS: + +ctags CTAGS: + +cscope cscopelist: + + +distdir: $(DISTFILES) + @srcdirstrip=`echo "$(srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + topsrcdirstrip=`echo "$(top_srcdir)" | sed 's/[].[^$$\\*]/\\\\&/g'`; \ + list='$(DISTFILES)'; \ + dist_files=`for file in $$list; do echo $$file; done | \ + sed -e "s|^$$srcdirstrip/||;t" \ + -e "s|^$$topsrcdirstrip/|$(top_builddir)/|;t"`; \ + case $$dist_files in \ + */*) $(MKDIR_P) `echo "$$dist_files" | \ + sed '/\//!d;s|^|$(distdir)/|;s,/[^/]*$$,,' | \ + sort -u` ;; \ + esac; \ + for file in $$dist_files; do \ + if test -f $$file || test -d $$file; then d=.; else d=$(srcdir); fi; \ + if test -d $$d/$$file; then \ + dir=`echo "/$$file" | sed -e 's,/[^/]*$$,,'`; \ + if test -d "$(distdir)/$$file"; then \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + if test -d $(srcdir)/$$file && test $$d != $(srcdir); then \ + cp -fpR $(srcdir)/$$file "$(distdir)$$dir" || exit 1; \ + find "$(distdir)/$$file" -type d ! -perm -700 -exec chmod u+rwx {} \;; \ + fi; \ + cp -fpR $$d/$$file "$(distdir)$$dir" || exit 1; \ + else \ + test -f "$(distdir)/$$file" \ + || cp -p $$d/$$file "$(distdir)/$$file" \ + || exit 1; \ + fi; \ + done +check-am: all-am +check: check-am +all-am: Makefile $(DATA) +installdirs: +install: install-am +install-exec: install-exec-am +install-data: install-data-am +uninstall: uninstall-am + +install-am: all-am + @$(MAKE) $(AM_MAKEFLAGS) install-exec-am install-data-am + +installcheck: installcheck-am +install-strip: + if test -z '$(STRIP)'; then \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + install; \ + else \ + $(MAKE) $(AM_MAKEFLAGS) INSTALL_PROGRAM="$(INSTALL_STRIP_PROGRAM)" \ + install_sh_PROGRAM="$(INSTALL_STRIP_PROGRAM)" INSTALL_STRIP_FLAG=-s \ + "INSTALL_PROGRAM_ENV=STRIPPROG='$(STRIP)'" install; \ + fi +mostlyclean-generic: + +clean-generic: + +distclean-generic: + -test -z "$(CONFIG_CLEAN_FILES)" || rm -f $(CONFIG_CLEAN_FILES) + -test . = "$(srcdir)" || test -z "$(CONFIG_CLEAN_VPATH_FILES)" || rm -f $(CONFIG_CLEAN_VPATH_FILES) + +maintainer-clean-generic: + @echo "This command is intended for maintainers to use" + @echo "it deletes files that may require special tools to rebuild." + -test -z "$(MAINTAINERCLEANFILES)" || rm -f $(MAINTAINERCLEANFILES) +clean: clean-am + +clean-am: clean-generic mostlyclean-am + +distclean: distclean-am + -rm -f Makefile +distclean-am: clean-am distclean-generic + +dvi: dvi-am + +dvi-am: + +html: html-am + +html-am: + +info: info-am + +info-am: + +install-data-am: + +install-dvi: install-dvi-am + +install-dvi-am: + +install-exec-am: + +install-html: install-html-am + +install-html-am: + +install-info: install-info-am + +install-info-am: + +install-man: + +install-pdf: install-pdf-am + +install-pdf-am: + +install-ps: install-ps-am + +install-ps-am: + +installcheck-am: + +maintainer-clean: maintainer-clean-am + -rm -f Makefile +maintainer-clean-am: distclean-am maintainer-clean-generic + +mostlyclean: mostlyclean-am + +mostlyclean-am: mostlyclean-generic + +pdf: pdf-am + +pdf-am: + +ps: ps-am + +ps-am: + +uninstall-am: + +.MAKE: install-am install-strip + +.PHONY: all all-am check check-am clean clean-generic cscopelist-am \ + ctags-am distclean distclean-generic distdir dvi dvi-am html \ + html-am info info-am install install-am install-data \ + install-data-am install-dvi install-dvi-am install-exec \ + install-exec-am install-html install-html-am install-info \ + install-info-am install-man install-pdf install-pdf-am \ + install-ps install-ps-am install-strip installcheck \ + installcheck-am installdirs maintainer-clean \ + maintainer-clean-generic mostlyclean mostlyclean-generic pdf \ + pdf-am ps ps-am tags-am uninstall uninstall-am + + +# Tell versions [3.59,3.63) of GNU make to not export all variables. +# Otherwise a system limit (for SysV at least) may be exceeded. +.NOEXPORT: diff --git a/libnetdata/adaptive_resortable_list/README.md b/libnetdata/adaptive_resortable_list/README.md new file mode 100644 index 000000000..0ba3ec9b5 --- /dev/null +++ b/libnetdata/adaptive_resortable_list/README.md @@ -0,0 +1,93 @@ + +# Adaptive Re-sortable List (ARL) + +This library allows netdata to read a series of `name - value` pairs +in the **fastest possible way**. + +ARLs are used all over netdata, as they are the most +CPU utilization efficient way to process `/proc` files. They are used to +process both vertical (csv like) and horizontal (one pair per line) `name - value` pairs. + +## How ARL works + +It maintains a linked list of all `NAME` (keywords), sorted in the +order found in the data source. The linked list is kept +sorted at all times - the data source may change at any time, the +linked list will adapt at the next iteration. + +### Initialization + +During initialization (just once), the caller: + +- calls `arl_create()` to create the ARL + +- calls `arl_expect()` multiple times to register the expected keywords + +The library will call the `processor()` function (given to +`arl_create()`), for each expected keyword found. +The default `processor()` expects `dst` to be an `unsigned long long *`. + +Each `name` keyword may have a different `processor()` (by calling +`arl_expect_custom()` instead of `arl_expect()`). + +### Data collection iterations + +For each iteration through the data source, the caller: + +- calls `arl_begin()` to initiate a data collection iteration. + This is to be called just ONCE every time the source is re-evaluated. + +- calls `arl_check()` for each entry read from the file. + +### Cleanup + +When the caller exits: + +- calls `arl_free()` to destroy this and free all memory. + +### Performance + +ARL maintains a list of `name` keywords found in the data source (even the ones +that are not useful for data collection). + +If the data source maintains the same order on the `name-value` pairs, for each +each call to `arl_check()` only an `strcmp()` is executed to verify the +expected order has not changed, a counter is incremented and a pointer is changed. +So, if the data source has 100 `name-value` pairs, and their order remains constant +over time, 100 successful `strcmp()` are executed. + +In the unlikely event that an iteration sees the data source with a different order, +for each out-of-order keyword, a full search of the remaining keywords is made. But +this search uses 32bit hashes, not string comparisons, so it should also be fast. + +When all expectations are satisfied (even in the middle of an iteration), +the call to `arl_check()` will return 1, to signal the caller to stop the loop, +saving valuable CPU resources for the rest of the data source. + +In the following test we used alternative methods to process, **1M times**, +a data source like `/proc/meminfo`, already tokenized, in memory, +to extract the same number of expected metrics: + +test|code|string comparison|number parsing|duration +:---:|:---:|:---:|:---:|:---:| +1|if-else-if-else-if|`strcmp()`|`strtoull()`|4630.337 ms +2|nested loops|inline `simple_hash()` and `strcmp()`|`strtoull()`|1597.481 ms +3|nested loops|inline `simple_hash()` and `strcmp()`|`str2ull()`|923.523 ms +4|if-else-if-else-if|inline `simple_hash()` and `strcmp()`|`strtoull()`| 854.574 ms +5|if-else-if-else-if|statement expression `simple_hash()` and `strcmp()`|`strtoull()`|912.013 ms +6|if-continue|inline `simple_hash()` and `strcmp()`|`strtoull()`|842.279 ms +7|if-else-if-else-if|inline `simple_hash()` and `strcmp()`|`str2ull()`|602.837 ms +8|ARL|ARL|`strtoull()`|350.360 ms +9|ARL|ARL|`str2ull()`|157.237 ms + +Compared to unoptimized code (test No 1: 4.6sec): + + - before ARL netdata was using test No **7** with hashing and a custom `str2ull()` to achieve 602ms. + - the current ARL implementation is test No **9** that needs only 157ms (29 times faster vs unoptimized code, about 4 times faster vs optimized code). + +[Check the source code of this test](../../tests/profile/benchmark-value-pairs.c). + +## Limitations + +Do not use ARL if the a name/keyword may appear more than once in the +source data. diff --git a/libnetdata/adaptive_resortable_list/adaptive_resortable_list.c b/libnetdata/adaptive_resortable_list/adaptive_resortable_list.c new file mode 100644 index 000000000..7f4c6c53d --- /dev/null +++ b/libnetdata/adaptive_resortable_list/adaptive_resortable_list.c @@ -0,0 +1,280 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../libnetdata.h" + +// the default processor() of the ARL +// can be overwritten at arl_create() +inline void arl_callback_str2ull(const char *name, uint32_t hash, const char *value, void *dst) { + (void)name; + (void)hash; + + register unsigned long long *d = dst; + *d = str2ull(value); + // fprintf(stderr, "name '%s' with hash %u and value '%s' is %llu\n", name, hash, value, *d); +} + +inline void arl_callback_str2kernel_uint_t(const char *name, uint32_t hash, const char *value, void *dst) { + (void)name; + (void)hash; + + register kernel_uint_t *d = dst; + *d = str2kernel_uint_t(value); + // fprintf(stderr, "name '%s' with hash %u and value '%s' is %llu\n", name, hash, value, (unsigned long long)*d); +} + +inline void arl_callback_ssize_t(const char *name, uint32_t hash, const char *value, void *dst) { + (void)name; + (void)hash; + + register ssize_t *d = dst; + *d = (ssize_t)str2ll(value, NULL); + // fprintf(stderr, "name '%s' with hash %u and value '%s' is %zd\n", name, hash, value, *d); +} + +// create a new ARL +ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks) { + ARL_BASE *base = callocz(1, sizeof(ARL_BASE)); + + base->name = strdupz(name); + + if(!processor) + base->processor = arl_callback_str2ull; + else + base->processor = processor; + + base->rechecks = rechecks; + + return base; +} + +void arl_free(ARL_BASE *arl_base) { + if(unlikely(!arl_base)) + return; + + while(arl_base->head) { + ARL_ENTRY *e = arl_base->head; + arl_base->head = e->next; + + freez(e->name); +#ifdef NETDATA_INTERNAL_CHECKS + memset(e, 0, sizeof(ARL_ENTRY)); +#endif + freez(e); + } + + freez(arl_base->name); + +#ifdef NETDATA_INTERNAL_CHECKS + memset(arl_base, 0, sizeof(ARL_BASE)); +#endif + + freez(arl_base); +} + +void arl_begin(ARL_BASE *base) { + +#ifdef NETDATA_INTERNAL_CHECKS + if(likely(base->iteration > 10)) { + // do these checks after the ARL has been sorted + + if(unlikely(base->relinkings > (base->expected + base->allocated))) + info("ARL '%s' has %zu relinkings with %zu expected and %zu allocated entries. Is the source changing so fast?" + , base->name, base->relinkings, base->expected, base->allocated); + + if(unlikely(base->slow > base->fast)) + info("ARL '%s' has %zu fast searches and %zu slow searches. Is the source really changing so fast?" + , base->name, base->fast, base->slow); + + /* + if(unlikely(base->iteration % 60 == 0)) { + info("ARL '%s' statistics: iteration %zu, expected %zu, wanted %zu, allocated %zu, fred %zu, relinkings %zu, found %zu, added %zu, fast %zu, slow %zu" + , base->name + , base->iteration + , base->expected + , base->wanted + , base->allocated + , base->fred + , base->relinkings + , base->found + , base->added + , base->fast + , base->slow + ); + // for(e = base->head; e; e = e->next) fprintf(stderr, "%s ", e->name); + // fprintf(stderr, "\n"); + } + */ + } +#endif + + if(unlikely(base->iteration > 0 && (base->added || (base->iteration % base->rechecks) == 0))) { + int wanted_equals_expected = ((base->iteration % base->rechecks) == 0); + + // fprintf(stderr, "\n\narl_begin() rechecking, added %zu, iteration %zu, rechecks %zu, wanted_equals_expected %d\n\n\n", base->added, base->iteration, base->rechecks, wanted_equals_expected); + + base->added = 0; + base->wanted = (wanted_equals_expected)?base->expected:0; + + ARL_ENTRY *e = base->head; + while(e) { + if(e->flags & ARL_ENTRY_FLAG_FOUND) { + + // remove the found flag + e->flags &= ~ARL_ENTRY_FLAG_FOUND; + + // count it in wanted + if(!wanted_equals_expected && e->flags & ARL_ENTRY_FLAG_EXPECTED) + base->wanted++; + + } + else if(e->flags & ARL_ENTRY_FLAG_DYNAMIC && !(base->head == e && !e->next)) { // not last entry + // we can remove this entry + // it is not found, and it was created because + // it was found in the source file + + // remember the next one + ARL_ENTRY *t = e->next; + + // remove it from the list + if(e->next) e->next->prev = e->prev; + if(e->prev) e->prev->next = e->next; + if(base->head == e) base->head = e->next; + + // free it + freez(e->name); + freez(e); + + // count it + base->fred++; + + // continue + e = t; + continue; + } + + e = e->next; + } + } + + if(unlikely(!base->head)) { + // hm... no nodes at all in the list #1700 + // add a fake one to prevent a crash + // this is better than checking for the existence of nodes all the time + arl_expect(base, "a-really-not-existing-source-keyword", NULL); + } + + base->iteration++; + base->next_keyword = base->head; + base->found = 0; + +} + +// register an expected keyword to the ARL +// together with its destination ( i.e. the output of the processor() ) +ARL_ENTRY *arl_expect_custom(ARL_BASE *base, const char *keyword, void (*processor)(const char *name, uint32_t hash, const char *value, void *dst), void *dst) { + ARL_ENTRY *e = callocz(1, sizeof(ARL_ENTRY)); + e->name = strdupz(keyword); + e->hash = simple_hash(e->name); + e->processor = (processor)?processor:base->processor; + e->dst = dst; + e->flags = ARL_ENTRY_FLAG_EXPECTED; + e->prev = NULL; + e->next = base->head; + + if(base->head) base->head->prev = e; + else base->next_keyword = e; + + base->head = e; + base->expected++; + base->allocated++; + + base->wanted = base->expected; + + return e; +} + +int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value) { + ARL_ENTRY *e; + + uint32_t hash = simple_hash(s); + + // find if it already exists in the data + for(e = base->head; e ; e = e->next) + if(e->hash == hash && !strcmp(e->name, s)) + break; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(base->next_keyword && e == base->next_keyword)) + fatal("Internal Error: e == base->last"); +#endif + + if(e) { + // found it in the keywords + + base->relinkings++; + + // run the processor for it + if(unlikely(e->dst)) { + e->processor(e->name, hash, value, e->dst); + base->found++; + } + + // unlink it - we will relink it below + if(e->next) e->next->prev = e->prev; + if(e->prev) e->prev->next = e->next; + + // make sure the head is properly linked + if(base->head == e) + base->head = e->next; + } + else { + // not found + + // create it + e = callocz(1, sizeof(ARL_ENTRY)); + e->name = strdupz(s); + e->hash = hash; + e->flags = ARL_ENTRY_FLAG_DYNAMIC; + + base->allocated++; + base->added++; + } + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely(base->iteration % 60 == 0 && e->flags & ARL_ENTRY_FLAG_FOUND)) + info("ARL '%s': entry '%s' is already found. Did you forget to call arl_begin()?", base->name, s); +#endif + + e->flags |= ARL_ENTRY_FLAG_FOUND; + + // link it here + e->next = base->next_keyword; + if(base->next_keyword) { + e->prev = base->next_keyword->prev; + base->next_keyword->prev = e; + + if(e->prev) + e->prev->next = e; + + if(base->head == base->next_keyword) + base->head = e; + } + else { + e->prev = NULL; + + if(!base->head) + base->head = e; + } + + // prepare the next iteration + base->next_keyword = e->next; + if(unlikely(!base->next_keyword)) + base->next_keyword = base->head; + + if(unlikely(base->found == base->wanted)) { + // fprintf(stderr, "FOUND ALL WANTED 1: found = %zu, wanted = %zu, expected %zu\n", base->found, base->wanted, base->expected); + return 1; + } + + return 0; +} diff --git a/libnetdata/adaptive_resortable_list/adaptive_resortable_list.h b/libnetdata/adaptive_resortable_list/adaptive_resortable_list.h new file mode 100644 index 000000000..011ee73d9 --- /dev/null +++ b/libnetdata/adaptive_resortable_list/adaptive_resortable_list.h @@ -0,0 +1,138 @@ +// SPDX-License-Identifier: GPL-3.0-or-later + +#include "../libnetdata.h" + +#ifndef NETDATA_ADAPTIVE_RESORTABLE_LIST_H +#define NETDATA_ADAPTIVE_RESORTABLE_LIST_H 1 + +#define ARL_ENTRY_FLAG_FOUND 0x01 // the entry has been found in the source data +#define ARL_ENTRY_FLAG_EXPECTED 0x02 // the entry is expected by the program +#define ARL_ENTRY_FLAG_DYNAMIC 0x04 // the entry was dynamically allocated, from source data + +typedef struct arl_entry { + char *name; // the keywords + uint32_t hash; // the hash of the keyword + + void *dst; // the dst to pass to the processor + + uint8_t flags; // ARL_ENTRY_FLAG_* + + // the processor to do the job + void (*processor)(const char *name, uint32_t hash, const char *value, void *dst); + + // double linked list for fast re-linkings + struct arl_entry *prev, *next; +} ARL_ENTRY; + +typedef struct arl_base { + char *name; + + size_t iteration; // incremented on each iteration (arl_begin()) + size_t found; // the number of expected keywords found in this iteration + size_t expected; // the number of expected keywords + size_t wanted; // the number of wanted keywords + // i.e. the number of keywords found and expected + + size_t relinkings; // the number of relinkings we have made so far + + size_t allocated; // the number of keywords allocated + size_t fred; // the number of keywords cleaned up + + size_t rechecks; // the number of iterations between re-checks of the + // wanted number of keywords + // this is only needed in cases where the source + // is having less lines over time. + + size_t added; // it is non-zero if new keywords have been added + // this is only needed to detect new lines have + // been added to the file, over time. + +#ifdef NETDATA_INTERNAL_CHECKS + size_t fast; // the number of times we have taken the fast path + size_t slow; // the number of times we have taken the slow path +#endif + + // the processor to do the job + void (*processor)(const char *name, uint32_t hash, const char *value, void *dst); + + // the linked list of the keywords + ARL_ENTRY *head; + + // since we keep the list of keywords sorted (as found in the source data) + // this is next keyword that we expect to find in the source data. + ARL_ENTRY *next_keyword; +} ARL_BASE; + +// create a new ARL +extern ARL_BASE *arl_create(const char *name, void (*processor)(const char *, uint32_t, const char *, void *), size_t rechecks); + +// free an ARL +extern void arl_free(ARL_BASE *arl_base); + +// register an expected keyword to the ARL +// together with its destination ( i.e. the output of the processor() ) +extern ARL_ENTRY *arl_expect_custom(ARL_BASE *base, const char *keyword, void (*processor)(const char *name, uint32_t hash, const char *value, void *dst), void *dst); +#define arl_expect(base, keyword, dst) arl_expect_custom(base, keyword, NULL, dst) + +// an internal call to complete the check() call +extern int arl_find_or_create_and_relink(ARL_BASE *base, const char *s, const char *value); + +// begin an ARL iteration +extern void arl_begin(ARL_BASE *base); + +extern void arl_callback_str2ull(const char *name, uint32_t hash, const char *value, void *dst); +extern void arl_callback_str2kernel_uint_t(const char *name, uint32_t hash, const char *value, void *dst); +extern void arl_callback_ssize_t(const char *name, uint32_t hash, const char *value, void *dst); + +// check a keyword against the ARL +// this is to be called for each keyword read from source data +// s = the keyword, as collected +// src = the src data to be passed to the processor +// it is defined in the header file in order to be inlined +static inline int arl_check(ARL_BASE *base, const char *keyword, const char *value) { + ARL_ENTRY *e = base->next_keyword; + +#ifdef NETDATA_INTERNAL_CHECKS + if(unlikely((base->fast + base->slow) % (base->expected + base->allocated) == 0 && (base->fast + base->slow) > (base->expected + base->allocated) * base->iteration)) + info("ARL '%s': Did you forget to call arl_begin()?", base->name); +#endif + + // it should be the first entry (pointed by base->next_keyword) + if(likely(!strcmp(keyword, e->name))) { + // it is + +#ifdef NETDATA_INTERNAL_CHECKS + base->fast++; +#endif + + e->flags |= ARL_ENTRY_FLAG_FOUND; + + // execute the processor + if(unlikely(e->dst)) { + e->processor(e->name, e->hash, value, e->dst); + base->found++; + } + + // be prepared for the next iteration + base->next_keyword = e->next; + if(unlikely(!base->next_keyword)) + base->next_keyword = base->head; + + // stop if we collected all the values for this iteration + if(unlikely(base->found == base->wanted)) { + // fprintf(stderr, "FOUND ALL WANTED 2: found = %zu, wanted = %zu, expected %zu\n", base->found, base->wanted, base->expected); + return 1; + } + + return 0; + } + +#ifdef NETDATA_INTERNAL_CHECKS + base->slow++; +#endif + + // we read from source, a not-expected keyword + return arl_find_or_create_and_relink(base, keyword, value); +} + +#endif //NETDATA_ADAPTIVE_RESORTABLE_LIST_H |