| Message ID | 20240406164727.577914-1-visitorckw@gmail.com (mailing list archive) |
|---|---|
| Headers | show |
| Series | treewide: Refactor heap related implementation | expand |
On Sun, Apr 07, 2024 at 12:47:10AM +0800, Kuan-Wei Chiu wrote: > This patch series focuses on several adjustments related to heap > implementation. Firstly, a type-safe interface has been added to the > min_heap, along with the introduction of several new functions to > enhance its functionality. Additionally, the heap implementation for > bcache and bcachefs has been replaced with the generic min_heap > implementation from include/linux. Furthermore, several typos have been > corrected. > > Previous discussion with Kent Overstreet: > https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu > > Regards, > Kuan-Wei pointing test automation at it now: https://evilpiepirate.org/~testdashboard/ci?branch=refactor-heap-v3 Coli, could I get some acks from you?
> 2024年4月9日 11:40，Kent Overstreet <kent.overstreet@linux.dev> 写道： > > On Sun, Apr 07, 2024 at 12:47:10AM +0800, Kuan-Wei Chiu wrote: >> This patch series focuses on several adjustments related to heap >> implementation. Firstly, a type-safe interface has been added to the >> min_heap, along with the introduction of several new functions to >> enhance its functionality. Additionally, the heap implementation for >> bcache and bcachefs has been replaced with the generic min_heap >> implementation from include/linux. Furthermore, several typos have been >> corrected. >> >> Previous discussion with Kent Overstreet: >> https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu >> >> Regards, >> Kuan-Wei > > pointing test automation at it now: > https://evilpiepirate.org/~testdashboard/ci?branch=refactor-heap-v3 > > Coli, could I get some acks from you? Yes, the code tested and Acked-by sent. Thanks. Coly Li
On Sun, Apr 07, 2024 at 12:47:10AM +0800, Kuan-Wei Chiu wrote: > This patch series focuses on several adjustments related to heap > implementation. Firstly, a type-safe interface has been added to the > min_heap, along with the introduction of several new functions to > enhance its functionality. Additionally, the heap implementation for > bcache and bcachefs has been replaced with the generic min_heap > implementation from include/linux. Furthermore, several typos have been > corrected. > > Previous discussion with Kent Overstreet: > https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu > > Regards, > Kuan-Wei We need to get this into -next, where are you at with v4?
On Mon, Apr 22, 2024 at 04:20:28PM -0400, Kent Overstreet wrote: > On Sun, Apr 07, 2024 at 12:47:10AM +0800, Kuan-Wei Chiu wrote: > > This patch series focuses on several adjustments related to heap > > implementation. Firstly, a type-safe interface has been added to the > > min_heap, along with the introduction of several new functions to > > enhance its functionality. Additionally, the heap implementation for > > bcache and bcachefs has been replaced with the generic min_heap > > implementation from include/linux. Furthermore, several typos have been > > corrected. > > > > Previous discussion with Kent Overstreet: > > https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu > > > > Regards, > > Kuan-Wei > > We need to get this into -next, where are you at with v4? Apologies for the delay; I've just returned from a long trip to Seattle where I attended the Open Source Summit. After reviewing the bcachefs CI testing results for v3, it appears that my patch has caused some Kernel panic and soft lockup issues in bcachefs. However, I haven't been able to reproduce these problems in my qemu testing environment, so I'm unsure where I went wrong to cause these errors. Regards, Kuan-Wei
This patch series focuses on several adjustments related to heap implementation. Firstly, a type-safe interface has been added to the min_heap, along with the introduction of several new functions to enhance its functionality. Additionally, the heap implementation for bcache and bcachefs has been replaced with the generic min_heap implementation from include/linux. Furthermore, several typos have been corrected. Previous discussion with Kent Overstreet: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu Regards, Kuan-Wei --- You can preview this patch series on the 'refactor-heap-v3' branch of the repository at the following link: https://github.com/visitorckw/linux.git Changes in v3: - Avoid heap->heap.nr to eliminate the nested types. - Add MIN_HEAP_PREALLOCATED macro for preallocating some elements. - Use min_heap_sift_up() in min_heap_push(). - Fix a bug in heap_del() where we should copy the last element to 'data + idx * element_size' instead of 'data'. - Add testcases for heap_del(). - Fix bugs in bcache/bcachefs patches where the parameter types in some compare functions should have been 'type **', but were mistakenly written as 'type *'. Changes in v2: - Add attribute __always_unused to the compare and swap functions that do not use the args parameter. - Rename min_heapify() to min_heap_sift_down(). - Update lib/test_min_heap.c to use min_heap_init(). - Refine the commit message for bcache and bcachefs. - Adjust the order of patches in the patch series. Link to v2: https://lore.kernel.org/20240320145417.336208-1-visitorckw@gmail.com Link to v1: https://lkml.kernel.org/20240319180005.246930-1-visitorckw@gmail.com Kuan-Wei Chiu (17): perf/core: Fix several typos bcache: Fix typo bcachefs: Fix typo lib min_heap: Add type safe interface lib min_heap: Add min_heap_init() lib min_heap: Add min_heap_peek() lib min_heap: Add min_heap_full() lib min_heap: Add args for min_heap_callbacks lib min_heap: Add min_heap_sift_up() lib min_heap: Add min_heap_del() lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values lib min_heap: Rename min_heapify() to min_heap_sift_down() lib min_heap: Update min_heap_push() to use min_heap_sift_up() lib/test_min_heap: Use min_heap_init() for initializing lib/test_min_heap: Add test for heap_del() bcache: Remove heap-related macros and switch to generic min_heap bcachefs: Remove heap-related macros and switch to generic min_heap drivers/md/bcache/alloc.c | 64 ++++++++--- drivers/md/bcache/bcache.h | 2 +- drivers/md/bcache/bset.c | 84 ++++++++++----- drivers/md/bcache/bset.h | 14 +-- drivers/md/bcache/btree.c | 17 ++- drivers/md/bcache/extents.c | 53 ++++++---- drivers/md/bcache/movinggc.c | 41 +++++-- drivers/md/bcache/sysfs.c | 2 + drivers/md/bcache/util.c | 2 +- drivers/md/bcache/util.h | 67 +----------- drivers/md/bcache/writeback.c | 3 + drivers/md/dm-vdo/repair.c | 25 +++-- drivers/md/dm-vdo/slab-depot.c | 20 ++-- fs/bcachefs/clock.c | 43 ++++++-- fs/bcachefs/clock_types.h | 2 +- fs/bcachefs/ec.c | 76 ++++++++----- fs/bcachefs/ec_types.h | 2 +- fs/bcachefs/util.c | 2 +- fs/bcachefs/util.h | 118 +-------------------- include/linux/min_heap.h | 188 +++++++++++++++++++++++++-------- kernel/events/core.c | 41 ++++--- lib/test_min_heap.c | 94 +++++++++++------ 22 files changed, 537 insertions(+), 423 deletions(-)