[PATCH v4 1/2] member: implement NitroSketch mode

[Bruce Richardson]

On Thu, Sep 15, 2022 at 09:03:41PM +0800, Leyi Rong wrote:
> Sketching algorithm provide high-fidelity approximate measurements and
> appears as a promising alternative to traditional approaches such as
> packet sampling.
> 
> NitroSketch [1] is a software sketching framework that optimizes
> performance, provides accuracy guarantees, and supports a variety of
> sketches.
> 
> This commit adds a new data structure called sketch into
> membership library. This new data structure is an efficient
> way to profile the traffic for heavy hitters. Also use min-heap
> structure to maintain the top-k flow keys.
> 
> [1] Zaoxing Liu, Ran Ben-Basat, Gil Einziger, Yaron Kassner, Vladimir
> Braverman, Roy Friedman, Vyas Sekar, "NitroSketch: Robust and General
> Sketch-based Monitoring in Software Switches", in ACM SIGCOMM 2019.
> https://dl.acm.org/doi/pdf/10.1145/3341302.3342076
> 
> Signed-off-by: Alan Liu <zaoxingliu at gmail.com>
> Signed-off-by: Yipeng Wang <yipeng1.wang at intel.com>
> Signed-off-by: Leyi Rong <leyi.rong at intel.com>
> ---

Couple of comments below on the meson.build file.

/Bruce

>  lib/member/meson.build                |  42 +-
>  lib/member/rte_member.c               |  75 ++++
>  lib/member/rte_member.h               | 154 ++++++-
>  lib/member/rte_member_heap.h          | 424 ++++++++++++++++++
>  lib/member/rte_member_sketch.c        | 594 ++++++++++++++++++++++++++
>  lib/member/rte_member_sketch.h        |  97 +++++
>  lib/member/rte_member_sketch_avx512.c |  70 +++
>  lib/member/rte_member_sketch_avx512.h |  35 ++
>  lib/member/rte_xxh64_avx512.h         | 117 +++++
>  lib/member/version.map                |   9 +
>  10 files changed, 1613 insertions(+), 4 deletions(-)
>  create mode 100644 lib/member/rte_member_heap.h
>  create mode 100644 lib/member/rte_member_sketch.c
>  create mode 100644 lib/member/rte_member_sketch.h
>  create mode 100644 lib/member/rte_member_sketch_avx512.c
>  create mode 100644 lib/member/rte_member_sketch_avx512.h
>  create mode 100644 lib/member/rte_xxh64_avx512.h
> 
> diff --git a/lib/member/meson.build b/lib/member/meson.build
> index e06fddc240..3df0fbc7a6 100644
> --- a/lib/member/meson.build
> +++ b/lib/member/meson.build
> @@ -7,6 +7,46 @@ if is_windows
>      subdir_done()
>  endif
>  
> -sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c')
> +sources = files('rte_member.c', 'rte_member_ht.c', 'rte_member_vbf.c', 'rte_member_sketch.c')

At this point, with 4 entries I'd suggest reworking this to a vertical
list.

sources = files(
        'rte_member.c',
        ....
)

>  headers = files('rte_member.h')
>  deps += ['hash']
> +includes += include_directories('../hash', '../ring')
> +

Use dependencies rather than include-paths. Having a dependency on hash
means that your code will be compiled with the hash include paths already
present. Similarly you can add "ring" to the deps variable and drop this
line.

> +# compile AVX512 version if:
> +# we are building 64-bit binary AND binutils can generate proper code

I think this comment is no longer necessary. The condition itself is clear.
The following comment can be kept though as it explains what is being done
at a higher level than the code.

> +if dpdk_conf.has('RTE_ARCH_X86_64') and binutils_ok
> +    # compile AVX512 version if either:
> +    # a. we have AVX512 supported in minimum instruction set
> +    #    baseline
> +    # b. it's not minimum instruction set, but supported by
> +    #    compiler
> +    #
> +    # in former case, just add avx512 C file to files list
> +    # in latter case, compile c file to static lib, using correct
> +    # compiler flags, and then have the .o file from static lib
> +    # linked into main lib.
> +
> +    #check if all required flags already enabled
> +    sketch_avx512_flags = ['__AVX512F__', '__AVX512DQ__', '__AVX512IFMA__']
> +
> +    sketch_avx512_on = true
> +    foreach f:sketch_avx512_flags
> +        if cc.get_define(f, args: machine_args) == ''
> +            sketch_avx512_on = false
> +        endif
> +    endforeach
> +
> +    if sketch_avx512_on == true
> +	cflags += ['-DCC_AVX512_SUPPORT']
> +	sources += files('rte_member_sketch_avx512.c')
> +    elif cc.has_multi_arguments('-mavx512f', '-mavx512dq', '-mavx512ifma')
> +	sketch_avx512_tmp = static_library('sketch_avx512_tmp',
> +	    'rte_member_sketch_avx512.c',
> +	    include_directories: includes,
> +	    dependencies: static_rte_eal,
> +            c_args: cflags +
> +                ['-mavx512f', '-mavx512dq', '-mavx512ifma'])
> +	objs += sketch_avx512_tmp.extract_objects('rte_member_sketch_avx512.c')
> +	cflags += ['-DCC_AVX512_SUPPORT']

Logic looks correct here now, but beware of your indentation. You are
mixing tabs and spaces. Meson files should have spaces only, no tabs.

> +    endif
> +endif