linux-kernel - Re: [PATCH v6 2/6] lib: introduce generic min-heap

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200217162919.GO14879@hirez.programming.kicks-ass.net>
Date:   Mon, 17 Feb 2020 17:29:19 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     Ian Rogers <irogers@...gle.com>
Cc:     Ingo Molnar <mingo@...hat.com>,
        Arnaldo Carvalho de Melo <acme@...nel.org>,
        Mark Rutland <mark.rutland@....com>,
        Alexander Shishkin <alexander.shishkin@...ux.intel.com>,
        Jiri Olsa <jolsa@...hat.com>,
        Namhyung Kim <namhyung@...nel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Randy Dunlap <rdunlap@...radead.org>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        Shuah Khan <skhan@...uxfoundation.org>,
        Krzysztof Kozlowski <krzk@...nel.org>,
        Kees Cook <keescook@...omium.org>,
        "Paul E. McKenney" <paulmck@...nel.org>,
        Masami Hiramatsu <mhiramat@...nel.org>,
        Marco Elver <elver@...gle.com>,
        Kent Overstreet <kent.overstreet@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Ard Biesheuvel <ardb@...nel.org>,
        Gary Hook <Gary.Hook@....com>,
        Kan Liang <kan.liang@...ux.intel.com>,
        linux-kernel@...r.kernel.org,
        Stephane Eranian <eranian@...gle.com>,
        Andi Kleen <ak@...ux.intel.com>
Subject: Re: [PATCH v6 2/6] lib: introduce generic min-heap

On Thu, Feb 13, 2020 at 11:51:29PM -0800, Ian Rogers wrote:
> Supports push, pop and converting an array into a heap. If the sense of
> the compare function is inverted then it can provide a max-heap.

+whitespace

> Based-on-work-by: Peter Zijlstra (Intel) <peterz@...radead.org>
> 
-whitespace

> Signed-off-by: Ian Rogers <irogers@...gle.com>
> ---
>  include/linux/min_heap.h | 135 +++++++++++++++++++++++++++
>  lib/Kconfig.debug        |  10 ++
>  lib/Makefile             |   1 +
>  lib/test_min_heap.c      | 194 +++++++++++++++++++++++++++++++++++++++
>  4 files changed, 340 insertions(+)
>  create mode 100644 include/linux/min_heap.h
>  create mode 100644 lib/test_min_heap.c
> 
> diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h
> new file mode 100644
> index 000000000000..0f04f49c0779
> --- /dev/null
> +++ b/include/linux/min_heap.h
> @@ -0,0 +1,135 @@
> +/* SPDX-License-Identifier: GPL-2.0 */
> +#ifndef _LINUX_MIN_HEAP_H
> +#define _LINUX_MIN_HEAP_H
> +
> +#include <linux/bug.h>
> +#include <linux/string.h>
> +#include <linux/types.h>
> +
> +/**
> + * struct min_heap - Data structure to hold a min-heap.
> + * @data: Start of array holding the heap elements.
> + * @size: Number of elements currently in the heap.
> + * @cap: Maximum number of elements that can be held in current storage.
> + */
> +struct min_heap {
> +	void *data;
> +	int size;
> +	int cap;
> +};
> +
> +/**
> + * struct min_heap_callbacks - Data/functions to customise the min_heap.
> + * @elem_size: The size of each element in bytes.
> + * @cmp: Partial order function for this heap 'less'/'<' for min-heap,
> + *       'greater'/'>' for max-heap.

Since the thing is now called min_heap, 's/cmp/less/g'. cmp in C is a
-1,0,1 like thing.

> + * @swp: Swap elements function.
> + */
> +struct min_heap_callbacks {
> +	int elem_size;
> +	bool (*cmp)(const void *lhs, const void *rhs);
> +	void (*swp)(void *lhs, void *rhs);
> +};
> +
> +/* Sift the element at pos down the heap. */
> +static __always_inline
> +void min_heapify(struct min_heap *heap, int pos,
> +		const struct min_heap_callbacks *func)
> +{
> +	void *left_child, *right_child, *parent, *large_or_smallest;

's/large_or_smallest/smallest/g' ?

> +	u8 *data = (u8 *)heap->data;

void * has byte sized arithmetic

> +
> +	for (;;) {
> +		if (pos * 2 + 1 >= heap->size)
> +			break;
> +
> +		left_child = data + ((pos * 2 + 1) * func->elem_size);
> +		parent = data + (pos * func->elem_size);

> +		large_or_smallest = parent;
> +		if (func->cmp(left_child, large_or_smallest))
> +			large_or_smallest = left_child;

		smallest = parent;
		if (func->less(left_child, smallest);
			smallest = left_child;

Makes sense, no?

> +
> +		if (pos * 2 + 2 < heap->size) {
> +			right_child = data + ((pos * 2 + 2) * func->elem_size);
> +			if (func->cmp(right_child, large_or_smallest))
> +				large_or_smallest = right_child;
> +		}
> +		if (large_or_smallest == parent)
> +			break;
> +		func->swp(large_or_smallest, parent);
> +		if (large_or_smallest == left_child)
> +			pos = (pos * 2) + 1;
> +		else
> +			pos = (pos * 2) + 2;

> +/*
> + * Remove the minimum element and then push the given element. The
> + * implementation performs 1 sift (O(log2(size))) and is therefore more
> + * efficient than a pop followed by a push that does 2.
> + */
> +static __always_inline
> +void min_heap_pop_push(struct min_heap *heap,
> +		const void *element,
> +		const struct min_heap_callbacks *func)
> +{
> +	memcpy(heap->data, element, func->elem_size);
> +	min_heapify(heap, 0, func);
> +}

I still think this is a mightly weird primitive. I think I simply did:

	*evt = perf_event_group(next);
	if (*evt)
		min_heapify(..);