linux-kernel - Re: [PATCH v2 04/15] lib min_heap: Add type safe interface

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: <Zf42BA7EMCRI3hik@visitorckw-System-Product-Name>
Date: Sat, 23 Mar 2024 09:53:08 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Kent Overstreet <kent.overstreet@...ux.dev>
Cc: colyli@...e.de, msakai@...hat.com, peterz@...radead.org,
	mingo@...hat.com, acme@...nel.org, namhyung@...nel.org,
	akpm@...ux-foundation.org, bfoster@...hat.com, mark.rutland@....com,
	alexander.shishkin@...ux.intel.com, jolsa@...nel.org,
	irogers@...gle.com, adrian.hunter@...el.com, jserv@...s.ncku.edu.tw,
	dm-devel@...ts.linux.dev, linux-bcache@...r.kernel.org,
	linux-kernel@...r.kernel.org, linux-bcachefs@...r.kernel.org,
	linux-perf-users@...r.kernel.org
Subject: Re: [PATCH v2 04/15] lib min_heap: Add type safe interface

On Fri, Mar 22, 2024 at 02:23:26PM -0400, Kent Overstreet wrote:
> On Sat, Mar 23, 2024 at 01:02:29AM +0800, Kuan-Wei Chiu wrote:
> > On Thu, Mar 21, 2024 at 05:22:14PM -0400, Kent Overstreet wrote:
> > > On Thu, Mar 21, 2024 at 07:57:47PM +0800, Kuan-Wei Chiu wrote:
> > > > On Wed, Mar 20, 2024 at 04:56:57PM -0400, Kent Overstreet wrote:
> > > > > On Wed, Mar 20, 2024 at 10:54:06PM +0800, Kuan-Wei Chiu wrote:
> > > > > > Introduce a type-safe interface for min_heap by adding small macro
> > > > > > wrappers around functions and using a 0-size array to store type
> > > > > > information. This enables the use of __minheap_cast and
> > > > > > __minheap_obj_size macros for type casting and obtaining element size.
> > > > > > The implementation draws inspiration from generic-radix-tree.h,
> > > > > > eliminating the need to pass element size in min_heap_callbacks.
> > > > > 
> > > > > let's avoid the heap->heap.nr - darray (fs/bcachefs/darray.h) has a
> > > > > trick for that. All heaps have the same memory layout, so we can just
> > > > > cast to a void pointer heap to get something the C code can use.
> > > > >
> > > > If I understand correctly, you're suggesting adding APIs similar to
> > > > darray_top(), darray_first(), and darray_last() within min_heap and
> > > > having them return a pointer. However, some users are using heap.nr in
> > > > conditional statements instead of utilizing heap.nr for memory
> > > > operations, so returning pointers may not be as convenient. What about
> > > > adding get and set functions for nr instead?
> > > 
> > > No, I mean not having separate inner and outer types. Want me to sketch
> > > something out?
> > 
> > Based on your suggestion, I've come up with the following code snippet:
> > 
> > #define MIN_HEAP_PREALLOCATED(_type, _name, _nr) \
> > struct _name {  \
> >     int nr; \
> >     int size;   \
> >     _type *data;    \
> >     _type preallocated[_nr];    \
> > };
> > 
> > #define MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0)
> > 
> > typdef MIN_HEAP(char, _) min_heap_char;
> > 
> > static __always_inline
> > void min_heap_init(min_heap_char *heap, void *data, int size)
> > {
> > 	heap->nr = 0;
> > 	heap->size = size;
> >     heap->data = size <= ARRAY_SIZE(heap->preallocated) ? heap->preallocated : data;
> > }
> > 
> > But I'm not sure how to implement other inline functions like
> > min_heap_push or min_heap_pop if I do that, unless they are rewritten
> > using macros. Also, I'm not sure how to make the less and swp functions
> > in the min_heap_callbacks not use void * type parameters. Or perhaps I
> > misunderstood your meaning again. If you could sketch out your idea or
> > have a better approach, it would be a great help to me. Any guidance
> > would be greatly appreciated.
> 
> No, you're on the right track. To call C functions on different types of
> heaps you have to cast them all to a common type, say HEAP(char), also
> pass the element size as a paremeter (which you had to do previously
> anyways).

The other question I want to ask is, I'm not sure how this relates to
avoiding the heap->heap.nr. In cases where we need to know the current
number of elements in the heap, don't we still need to use the same
method to determine the number of elements?

Regards,
Kuan-Wei