linux-kernel - Re: [PATCH v3 02/10] lib: introduce generic min max 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: <7d369058842123c3038d10a631f5fa4c3e7472ff.camel@perches.com>
Date:   Sun, 17 Nov 2019 10:28:09 -0800
From:   Joe Perches <joe@...ches.com>
To:     Ian Rogers <irogers@...gle.com>,
        Peter Zijlstra <peterz@...radead.org>,
        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>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        Kees Cook <keescook@...omium.org>,
        Catalin Marinas <catalin.marinas@....com>,
        Petr Mladek <pmladek@...e.com>,
        Mauro Carvalho Chehab <mchehab+samsung@...nel.org>,
        Qian Cai <cai@....pw>, Joe Lawrence <joe.lawrence@...hat.com>,
        Tetsuo Handa <penguin-kernel@...ove.sakura.ne.jp>,
        Sri Krishna chowdary <schowdary@...dia.com>,
        "Uladzislau Rezki (Sony)" <urezki@...il.com>,
        Andy Shevchenko <andriy.shevchenko@...ux.intel.com>,
        Changbin Du <changbin.du@...el.com>,
        Ard Biesheuvel <ardb@...nel.org>,
        "David S. Miller" <davem@...emloft.net>,
        Kent Overstreet <kent.overstreet@...il.com>,
        Gary Hook <Gary.Hook@....com>, Arnd Bergmann <arnd@...db.de>,
        Kan Liang <kan.liang@...ux.intel.com>,
        linux-kernel@...r.kernel.org
Cc:     Stephane Eranian <eranian@...gle.com>,
        Andi Kleen <ak@...ux.intel.com>
Subject: Re: [PATCH v3 02/10] lib: introduce generic min max heap

On Wed, 2019-11-13 at 16:30 -0800, Ian Rogers wrote:
> Based-on-work-by: Peter Zijlstra (Intel) <peterz@...radead.org>

Perhaps some functions are a bit large for inline
and perhaps the function names are too generic?

> diff --git a/include/linux/min_max_heap.h b/include/linux/min_max_heap.h
[]
> +/* Sift the element at pos down the heap. */
> +static inline void heapify(struct min_max_heap *heap, int pos,
> +			const struct min_max_heap_callbacks *func) {
> +	void *left_child, *right_child, *parent, *large_or_smallest;
> +	char *data = (char *)heap->data;

The kernel already depends on void * arithmetic so it
seems char *data could just as well be void *data and
it might be more readable without the temporary at all.

> +
> +	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;
> +
> +		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;
> +	}
> +}

[]

> +static void heap_pop_push(struct min_max_heap *heap,
> +			const void *element,
> +			const struct min_max_heap_callbacks *func)
> +{
> +	char *data = (char *)heap->data;
> +
> +	memcpy(data, element, func->elem_size);
> +	heapify(heap, 0, func);
> +}

missing inline.

> +
> +/* Push an element on to the heap, O(log2(size)). */
> +static inline void
> +heap_push(struct min_max_heap *heap, const void *element,
> +	const struct min_max_heap_callbacks *func)
> +{
> +	void *child, *parent;
> +	int pos;
> +	char *data = (char *)heap->data;

Same comment about char * vs void * and unnecessary temporary.

> +
> +	if (WARN_ONCE(heap->size >= heap->cap, "Pushing on a full heap"))
> +		return;
> +
> +	/* Place at the end of data. */
> +	pos = heap->size;
> +	memcpy(data + (pos * func->elem_size), element, func->elem_size);
> +	heap->size++;
> +
> +	/* Sift up. */
> +	for (; pos > 0; pos = (pos - 1) / 2) {
> +		child = data + (pos * func->elem_size);
> +		parent = data + ((pos - 1) / 2) * func->elem_size;
> +		if (func->cmp(parent, child))
> +			break;
> +		func->swp(parent, child);
> +	}
> +}
> +
> +#endif /* _LINUX_MIN_MAX_HEAP_H */