From nobody Wed Nov 27 04:33:10 2024 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 85C5F14A4C1; Sun, 13 Oct 2024 18:47:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845254; cv=none; b=YK5sH+ApbVzEJzT+k6gFnba/jDrTUB6Rfr993txivrL0qNucTSKMrDshgVfQWcwD6g2dbx31SUTjWya9KPwZ5MOs0+7OSBFG/N58R7lk/A3gqATxY+U4pAVEYIGoJmX+wHjmKQ7MwPwzi+cyydjowxTtG4ZwcB5Rvn8Vlaz+iHw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845254; c=relaxed/simple; bh=EZ17iVx1S5EmAG0qSQL78S0bek1tN2ZbE1JpNX94hyo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=uEIMzfx7xXV+q6xS+bLvOA4lQVh5Rj3x1NW6DhqlP3rW4UmeaU0nafGG2FHWJfJ99THUEhTvaSuiOhtt8aKksKYwNN6kFEd5nqNjrZEkwSJIne3rGq6NJ1r8H7mLRd8yJQ6hHJbgU6RElHV1GRVdhlV/PN/22Apzpl8C6vuHl/U= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=jdTcsgmc; arc=none smtp.client-ip=209.85.214.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jdTcsgmc" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-20c77459558so27459095ad.0; Sun, 13 Oct 2024 11:47:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728845252; x=1729450052; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=x22YH2oKJ+m/PKql5G0+yADoV320o3RMXRRRh7K19Nk=; b=jdTcsgmc7KJglW1DkjFBuw6+FKi/9AuBdAV4mZONBk6nhUf4JhP+SJXEYTc/VhtXsk gCgcWWc8CkL1NNKKiVv6ysj+niZTY+KQ/JDRvWsmg7vKmAmOUEWbkd/zMdfy7mSqKTtA g3Q78d/L4EZ3QmTWMxabtZCtwxhvNBv3E8KKavLEjmEw2j7rL94LewYqN1hEqUetmJa+ Zgxr2S8TtBymY4q24Wq2BmI2QI0K/QHfnp0XG+9vRD47RUaHGOL60wrExALw82GX3Ltl iO4bW0ixcNmB7r8/8cO//yAHCfrKMY1YwulX2+9BuugeDyYlj9L82DbCo5ujDyhywTJZ XnIA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728845252; x=1729450052; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=x22YH2oKJ+m/PKql5G0+yADoV320o3RMXRRRh7K19Nk=; b=KCbRad94bS03e5oEcijaIM+L5rBKSKa+2yjLySqU/+T5uJN1x26h4dNN9AZUcXK0hY eis6znIlLk/jziKx/qbH6O1QQ3ctc6lcOr5QGVp7xuKm2UnlfRVMbTGPFgAXOGYOIW7D Z7HohMisI9iTvUwaMXurI5ZzmETevj/3/lCIICrwexiPaG8xBiyIezhMuvaAHgeM+kYN PZkf7hHvBIW+Cejp2cyRYXxafY4s+Wi9EpvaW9F1wJJx3387EqD0Uiomi+4SAr+35rsW 84zHz6kTCvL9oQVNW98iSkNjqPTLcq8YlReyW0r66vYuEJf3U2Lsk2lY7OqzeJkILavf xpIQ== X-Forwarded-Encrypted: i=1; AJvYcCUoRpfXpG2uHUzobtF7+eXst1mlhDFyg3GONu8FO7FCri9sg2JqJ2kDPCsTbkZDCDa4XVETfy/XGO+xWZlZOUg=@vger.kernel.org, AJvYcCUuLqQyQ1Xx64XP7Z8cV9tahrMT9neBd5/YjrA1+8nuiJwUpTgZ996SOCbX9kCz9LmiaDQ/dNU1z7GQ@vger.kernel.org, AJvYcCV7/liyCnaSi6pXr/RAVghDRDavNmgU5hzyjS2E7a75D5lmiLV8fpGsP3M3g84oP/GdvqLECT3F1oe1OXU=@vger.kernel.org, AJvYcCW24e17FmyA5Pjs1+gaAYWfda+GpNd5OdEIlO6su1Tuij9TjlIYs0GubbtPuBbsyURFLg1d8aUlYDCN53uu@vger.kernel.org, AJvYcCWYovufG4d3pWRDoTvCJC4ebWO3M/q+Roi0dbQKcRg3DBtOaX300dIMd3VKaq5hFmx7CyXypT/CS13GPCXXvx/jfg==@vger.kernel.org X-Gm-Message-State: AOJu0YzfrNGJNr47N86ueduA09yI9vouuTgOkQ7uricU6nQZYbQIwc5Z j4u4sYSRtZ7Fm1YkG/Ohn3jo+O94MZxl7wgVYhd8cDZwm8Lgeepb X-Google-Smtp-Source: AGHT+IFFjIiNZ6hVLt8fi/ZvTmt9fC1vLU7epNQVpG7NK03s1C2PpXEl0QeJIAPPQaOgf4wn+YZqSg== X-Received: by 2002:a17:902:c951:b0:20c:e65c:8c70 with SMTP id d9443c01a7336-20ce65c8e2dmr24446685ad.32.1728845251678; Sun, 13 Oct 2024 11:47:31 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c8c348f41sm52681965ad.289.2024.10.13.11.47.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 13 Oct 2024 11:47:31 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, corbet@lwn.net, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, kan.liang@linux.intel.com, jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, linux-bcache@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, linux-doc@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 1/3] lib/min_heap: Introduce non-inline versions of min heap API functions Date: Mon, 14 Oct 2024 02:47:01 +0800 Message-Id: <20241013184703.659652-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241013184703.659652-1-visitorckw@gmail.com> References: <20241013184703.659652-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" All current min heap API functions are marked with '__always_inline'. However, as the number of users increases, inlining these functions everywhere leads to a significant increase in kernel size. In performance-critical paths, such as when perf events are enabled and min heap functions are called on every context switch, it is important to retain the inline versions for optimal performance. To balance this, the original inline functions are kept, and additional non-inline versions of the functions have been added in lib/min_heap.c. Link: https://lore.kernel.org/20240522161048.8d8bbc7b153b4ecd92c50666@linux= -foundation.org Suggested-by: Andrew Morton Signed-off-by: Kuan-Wei Chiu --- drivers/md/bcache/Kconfig | 1 + drivers/md/dm-vdo/Kconfig | 1 + fs/bcachefs/Kconfig | 1 + include/linux/min_heap.h | 129 +++++++++++++++++++++++++------------- kernel/events/core.c | 6 +- lib/Kconfig | 3 + lib/Kconfig.debug | 1 + lib/Makefile | 1 + lib/min_heap.c | 70 +++++++++++++++++++++ 9 files changed, 167 insertions(+), 46 deletions(-) create mode 100644 lib/min_heap.c diff --git a/drivers/md/bcache/Kconfig b/drivers/md/bcache/Kconfig index b2d10063d35f..d4697e79d5a3 100644 --- a/drivers/md/bcache/Kconfig +++ b/drivers/md/bcache/Kconfig @@ -5,6 +5,7 @@ config BCACHE select BLOCK_HOLDER_DEPRECATED if SYSFS select CRC64 select CLOSURES + select MIN_HEAP help Allows a block device to be used as cache for other devices; uses a btree for indexing and the layout is optimized for SSDs. diff --git a/drivers/md/dm-vdo/Kconfig b/drivers/md/dm-vdo/Kconfig index 111ecd2c2a24..2400b2bc4bc7 100644 --- a/drivers/md/dm-vdo/Kconfig +++ b/drivers/md/dm-vdo/Kconfig @@ -7,6 +7,7 @@ config DM_VDO select DM_BUFIO select LZ4_COMPRESS select LZ4_DECOMPRESS + select MIN_HEAP help This device mapper target presents a block device with deduplication, compression and thin-provisioning. diff --git a/fs/bcachefs/Kconfig b/fs/bcachefs/Kconfig index 5bac803ea367..ab6c95b895b3 100644 --- a/fs/bcachefs/Kconfig +++ b/fs/bcachefs/Kconfig @@ -24,6 +24,7 @@ config BCACHEFS_FS select XXHASH select SRCU select SYMBOLIC_ERRNAME + select MIN_HEAP help The bcachefs filesystem - a modern, copy on write filesystem, with support for multiple devices, compression, checksumming, etc. diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 43a7b9dcf15e..0abb21173979 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -40,7 +40,7 @@ struct min_heap_callbacks { =20 /* Initialize a min-heap. */ static __always_inline -void __min_heap_init(min_heap_char *heap, void *data, int size) +void __min_heap_init_inline(min_heap_char *heap, void *data, int size) { heap->nr =3D 0; heap->size =3D size; @@ -50,33 +50,33 @@ void __min_heap_init(min_heap_char *heap, void *data, i= nt size) heap->data =3D heap->preallocated; } =20 -#define min_heap_init(_heap, _data, _size) \ - __min_heap_init((min_heap_char *)_heap, _data, _size) +#define min_heap_init_inline(_heap, _data, _size) \ + __min_heap_init_inline((min_heap_char *)_heap, _data, _size) =20 /* Get the minimum element from the heap. */ static __always_inline -void *__min_heap_peek(struct min_heap_char *heap) +void *__min_heap_peek_inline(struct min_heap_char *heap) { return heap->nr ? heap->data : NULL; } =20 -#define min_heap_peek(_heap) \ - (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) +#define min_heap_peek_inline(_heap) \ + (__minheap_cast(_heap) __min_heap_peek_inline((min_heap_char *)_heap)) =20 /* Check if the heap is full. */ static __always_inline -bool __min_heap_full(min_heap_char *heap) +bool __min_heap_full_inline(min_heap_char *heap) { return heap->nr =3D=3D heap->size; } =20 -#define min_heap_full(_heap) \ - __min_heap_full((min_heap_char *)_heap) +#define min_heap_full_inline(_heap) \ + __min_heap_full_inline((min_heap_char *)_heap) =20 /* Sift the element at pos down the heap. */ static __always_inline -void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, - const struct min_heap_callbacks *func, void *args) +void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem= _size, + const struct min_heap_callbacks *func, void *args) { void *left, *right; void *data =3D heap->data; @@ -108,13 +108,14 @@ void __min_heap_sift_down(min_heap_char *heap, int po= s, size_t elem_size, } } =20 -#define min_heap_sift_down(_heap, _pos, _func, _args) \ - __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_he= ap), _func, _args) +#define min_heap_sift_down_inline(_heap, _pos, _func, _args) \ + __min_heap_sift_down_inline((min_heap_char *)_heap, _pos, __minheap_obj_s= ize(_heap), \ + _func, _args) =20 /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, - const struct min_heap_callbacks *func, void *args) +void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size= _t idx, + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; size_t parent; @@ -128,27 +129,28 @@ void __min_heap_sift_up(min_heap_char *heap, size_t e= lem_size, size_t idx, } } =20 -#define min_heap_sift_up(_heap, _idx, _func, _args) \ - __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _id= x, _func, _args) +#define min_heap_sift_up_inline(_heap, _idx, _func, _args) \ + __min_heap_sift_up_inline((min_heap_char *)_heap, __minheap_obj_size(_hea= p), _idx, \ + _func, _args) =20 /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) +void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args) { int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heap_sift_down(heap, i, elem_size, func, args); + __min_heap_sift_down_inline(heap, i, elem_size, func, args); } =20 -#define min_heapify_all(_heap, _func, _args) \ - __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c, _args) +#define min_heapify_all_inline(_heap, _func, _args) \ + __min_heapify_all_inline((min_heap_char *)_heap, __minheap_obj_size(_heap= ), _func, _args) =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -bool __min_heap_pop(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) +bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 @@ -158,13 +160,13 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_= size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heap_sift_down(heap, 0, elem_size, func, args); + __min_heap_sift_down_inline(heap, 0, elem_size, func, args); =20 return true; } =20 -#define min_heap_pop(_heap, _func, _args) \ - __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, = _args) +#define min_heap_pop_inline(_heap, _func, _args) \ + __min_heap_pop_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), = _func, _args) =20 /* * Remove the minimum element and then push the given element. The @@ -172,22 +174,21 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_= size, * efficient than a pop followed by a push that does 2. */ static __always_inline -void __min_heap_pop_push(min_heap_char *heap, - const void *element, size_t elem_size, - const struct min_heap_callbacks *func, - void *args) +void __min_heap_pop_push_inline(min_heap_char *heap, const void *element, = size_t elem_size, + const struct min_heap_callbacks *func, void *args) { memcpy(heap->data, element, elem_size); - __min_heap_sift_down(heap, 0, elem_size, func, args); + __min_heap_sift_down_inline(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop_push(_heap, _element, _func, _args) \ - __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), _func, _args) +#define min_heap_pop_push_inline(_heap, _element, _func, _args) \ + __min_heap_pop_push_inline((min_heap_char *)_heap, _element, __minheap_ob= j_size(_heap), \ + _func, _args) =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, - const struct min_heap_callbacks *func, void *args) +bool __min_heap_push_inline(min_heap_char *heap, const void *element, size= _t elem_size, + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; int pos; @@ -201,18 +202,19 @@ bool __min_heap_push(min_heap_char *heap, const void = *element, size_t elem_size, heap->nr++; =20 /* Sift child at pos up. */ - __min_heap_sift_up(heap, elem_size, pos, func, args); + __min_heap_sift_up_inline(heap, elem_size, pos, func, args); =20 return true; } =20 -#define min_heap_push(_heap, _element, _func, _args) \ - __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) +#define min_heap_push_inline(_heap, _element, _func, _args) \ + __min_heap_push_inline((min_heap_char *)_heap, _element, __minheap_obj_si= ze(_heap), \ + _func, _args) =20 /* Remove ith element from the heap, O(log2(nr)). */ static __always_inline -bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, - const struct min_heap_callbacks *func, void *args) +bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t i= dx, + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 @@ -224,12 +226,53 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_= size, size_t idx, if (idx =3D=3D heap->nr) return true; func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); - __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_heap_sift_down(heap, idx, elem_size, func, args); + __min_heap_sift_up_inline(heap, elem_size, idx, func, args); + __min_heap_sift_down_inline(heap, idx, elem_size, func, args); =20 return true; } =20 +#define min_heap_del_inline(_heap, _idx, _func, _args) \ + __min_heap_del_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), = _idx, \ + _func, _args) + +void __min_heap_init(min_heap_char *heap, void *data, int size); +void *__min_heap_peek(struct min_heap_char *heap); +bool __min_heap_full(min_heap_char *heap); +void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, + const struct min_heap_callbacks *func, void *args); +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args); +void __min_heapify_all(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args); +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args); +void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t = elem_size, + const struct min_heap_callbacks *func, void *args); +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, + const struct min_heap_callbacks *func, void *args); +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args); + +#define min_heap_init(_heap, _data, _size) \ + __min_heap_init((min_heap_char *)_heap, _data, _size) +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) +#define min_heap_full(_heap) \ + __min_heap_full((min_heap_char *)_heap) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_he= ap), _func, _args) +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _id= x, _func, _args) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c, _args) +#define min_heap_pop(_heap, _func, _args) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, = _args) +#define min_heap_pop_push(_heap, _element, _func, _args) \ + __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), \ + _func, _args) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) #define min_heap_del(_heap, _idx, _func, _args) \ __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _= func, _args) =20 diff --git a/kernel/events/core.c b/kernel/events/core.c index e3589c4287cb..cbf365e67f6e 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3870,7 +3870,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } =20 - min_heapify_all(&event_heap, &perf_min_heap, NULL); + min_heapify_all_inline(&event_heap, &perf_min_heap, NULL); =20 while (event_heap.nr) { ret =3D func(*evt, data); @@ -3879,9 +3879,9 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heap_sift_down(&event_heap, 0, &perf_min_heap, NULL); + min_heap_sift_down_inline(&event_heap, 0, &perf_min_heap, NULL); else - min_heap_pop(&event_heap, &perf_min_heap, NULL); + min_heap_pop_inline(&event_heap, &perf_min_heap, NULL); } =20 return 0; diff --git a/lib/Kconfig b/lib/Kconfig index b38849af6f13..037a84731b7d 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -777,3 +777,6 @@ config POLYNOMIAL =20 config FIRMWARE_TABLE bool + +config MIN_HEAP + bool diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7315f643817a..a9b375cf9784 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2279,6 +2279,7 @@ config TEST_LIST_SORT config TEST_MIN_HEAP tristate "Min heap test" depends on DEBUG_KERNEL || m + select MIN_HEAP help Enable this to turn on min heap function tests. This test is executed only once during system boot (so affects only boot time), diff --git a/lib/Makefile b/lib/Makefile index 773adf88af41..e7ffee03e186 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -39,6 +39,7 @@ lib-y :=3D ctype.o string.o vsprintf.o cmdline.o \ =20 lib-$(CONFIG_PRINTK) +=3D dump_stack.o lib-$(CONFIG_SMP) +=3D cpumask.o +lib-$(CONFIG_MIN_HEAP) +=3D min_heap.o =20 lib-y +=3D kobject.o klist.o obj-y +=3D lockref.o diff --git a/lib/min_heap.c b/lib/min_heap.c new file mode 100644 index 000000000000..4485372ff3b1 --- /dev/null +++ b/lib/min_heap.c @@ -0,0 +1,70 @@ +// SPDX-License-Identifier: GPL-2.0 +#include +#include + +void __min_heap_init(min_heap_char *heap, void *data, int size) +{ + __min_heap_init_inline(heap, data, size); +} +EXPORT_SYMBOL(__min_heap_init); + +void *__min_heap_peek(struct min_heap_char *heap) +{ + return __min_heap_peek_inline(heap); +} +EXPORT_SYMBOL(__min_heap_peek); + +bool __min_heap_full(min_heap_char *heap) +{ + return __min_heap_full_inline(heap); +} +EXPORT_SYMBOL(__min_heap_full); + +void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, + const struct min_heap_callbacks *func, void *args) +{ + __min_heap_sift_down_inline(heap, pos, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heap_sift_down); + +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + __min_heap_sift_up_inline(heap, elem_size, idx, func, args); +} +EXPORT_SYMBOL(__min_heap_sift_up); + +void __min_heapify_all(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args) +{ + __min_heapify_all_inline(heap, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heapify_all); + +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, + const struct min_heap_callbacks *func, void *args) +{ + return __min_heap_pop_inline(heap, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heap_pop); + +void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t = elem_size, + const struct min_heap_callbacks *func, void *args) +{ + __min_heap_pop_push_inline(heap, element, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heap_pop_push); + +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, + const struct min_heap_callbacks *func, void *args) +{ + return __min_heap_push_inline(heap, element, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heap_push); + +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + return __min_heap_del_inline(heap, elem_size, idx, func, args); +} +EXPORT_SYMBOL(__min_heap_del); --=20 2.34.1 From nobody Wed Nov 27 04:33:10 2024 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4924714AD22; Sun, 13 Oct 2024 18:47:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845261; cv=none; b=L7cnt3oSx34ipx37wKY87bmQjRI4dNhOdMllx4AJtVYsWmCDfu24/d9VCnRbf0miHtWnx40M9CqB8iDE6RuXXnS2D44ER1qJmOvkmgxQSmwGXSYo2wVCqde969A2iGuEfSLoTQ3oRuGaiD9qa7d/7MxBF/rw/d8tiW8N0Wq/DFk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845261; c=relaxed/simple; bh=SNw/5o1lFuWyY9FK0pUzpASTqMzQQl0VMxj1R85JMxw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=LWkcmUmK5B1X2UJIyspPaY1IQgH78kKE48IYPN+xBAj3cN1WBJO1Wz0y43sHP8GDJrnH5DRv6LbEZSKqVjqY9o+HKcFSJrgxb4DDaAe/zVg+jswA/EgXEVvOGF0Utgx/sRF6DfCXCYRzUXRGXjlg6XLsJNCsmtMPhiJeK45NRFU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=ALsxcahm; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ALsxcahm" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-20c8b557f91so26393635ad.2; Sun, 13 Oct 2024 11:47:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728845259; x=1729450059; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=xSgBUVDuaaQJ7aL+4KpOG9PFNPzYSqa7wdB4/0F3UqU=; b=ALsxcahmY98DPQ9jM6tNhENpj17DuoAqOn30MBaNdbxns4+EChWb+JWEEDzDr3jg15 1vd+P8RFziQvCZ1qbLXgZJ6Ku2abHieYTHemGJH9GuMi6KUKoaMu8AwxaqSR4DR+rR0d EdBhTn9NBkEu3ZYfEpBNA4lK3y4IUv9EuxKIlyhTLiLY4PyGksRcbw6c1B5zPAelvl8Q 7LudEn5J/yDsd22YvEDCdHFiLeIfFYwZt3NFAjpAGlvw3c6M6Ujor+rCtP892X6Dx6/M qtEhsHTqumS+PFJG3p/NbLg5gnLNhloPKKjLrayHTsb6IWYGCZkoJkPhHditCvpo6Hru Pb0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728845259; x=1729450059; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=xSgBUVDuaaQJ7aL+4KpOG9PFNPzYSqa7wdB4/0F3UqU=; b=wzAwitmcNbDyi5IRj5AVKF3GJ3o8p5ERstK/3sLL5cgvqxUfzjbaPYfOYnyjY0Wx5p ksHYi+kCKsaFw9bPBLcEy8V9tTDrZ9lnqSIITdi86mgi4RAi7Jc7Ymr7Dq9Ci9eOkQZF 7JsDk12AQ1xkXZj6L3h19QI4DiMiwieteEK94kl1d9pmhUV1Et1yht81Gjjepf8eIAUw ziAoaQV6Q6Mx5t5UQwiFhiUVznEeNCRjg3bgLXCSG4J0yWomSIDPy5cWK4tWBaVAvm+u B6OITWwVFA6/F5prA+Zx8dC4/m28wSy4eg4avDaX6GSgJrxoe3y4cq62y8bV7eZKw34e r3pA== X-Forwarded-Encrypted: i=1; AJvYcCUkrD5Li5MxMOa/ZcER28ZNs55FiGlW24erJsyHgXI5g4jOLjIKdMzZWmng10G4GRMlWaiD1EIVpBtc2XPp9ig=@vger.kernel.org, AJvYcCUnDA6QWdEehasEednsNrXOrYwqyLnQEvjSsxd7IzsxQurp0e4wFz+2tp4UclqVUasxJzZd6TT+VZonVa8=@vger.kernel.org, AJvYcCVB9axldtF9/Ys8Zxd+HtDR+7niDzj2ZYySYxbjFndIrR2q9Csf8lAztfvLHzvWyTh6QcenrGTM0cpZlRSyBiJ4+Q==@vger.kernel.org, AJvYcCW0zuLj1o+3uU+FS9982lNqIaMTjamClfgDDtIGUOjiSPXNsVrtPhw5IJ7CaTXM2VkFDlT0VHDxl9q1D9Tm@vger.kernel.org, AJvYcCWWNvKm7itJ5eFBCQCXMFHvFYmlFCncByKe/b3VG2xEM0Jyrat91S5kjaTVcEDp/0waVN3euVWd6RlW@vger.kernel.org X-Gm-Message-State: AOJu0YwDE8LXHe32kQgdp2SS7/gD8S8EVjCP5QwB1Z7rLojB5OVbSKY/ AKazTOVRS3TWFzVJ+CkDLE5dHn6n+E0iT1Tkw2LiRocRpy5tiJIA X-Google-Smtp-Source: AGHT+IHOX5mN/TiSS+Vhti8hnnhr5pq0lj2xSJGRFkcy9EAu/5N5LW4pl2hse1P41xIM98wo4LcDNg== X-Received: by 2002:a17:902:da8e:b0:20c:d2e4:dc33 with SMTP id d9443c01a7336-20cd2e4ddc4mr67601575ad.14.1728845259628; Sun, 13 Oct 2024 11:47:39 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c8c348f41sm52681965ad.289.2024.10.13.11.47.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 13 Oct 2024 11:47:39 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, corbet@lwn.net, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, kan.liang@linux.intel.com, jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, linux-bcache@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, linux-doc@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 2/3] lib min_heap: Optimize min heap by prescaling counters for better performance Date: Mon, 14 Oct 2024 02:47:02 +0800 Message-Id: <20241013184703.659652-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241013184703.659652-1-visitorckw@gmail.com> References: <20241013184703.659652-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Improve the efficiency of the min heap by prescaling counters, eliminating the need to repeatedly compute 'index * element_size' when accessing elements. By doing so, we avoid the overhead associated with recalculating the byte offset for each heap operation. However, with prescaling, the calculation for the parent element's location is no longer as simple as '(i - 1) / 2'. To address this, we copy the parent function from 'lib/sort.c', which calculates the parent offset in a branchless manner without using any division instructions. This optimization should result in a more efficient heap implementation by reducing the computational overhead of finding parent and child offsets. Signed-off-by: Kuan-Wei Chiu --- Tested with test_min_heap module. include/linux/min_heap.h | 73 +++++++++++++++++++++++++++------------- 1 file changed, 49 insertions(+), 24 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 0abb21173979..bee28d7b6efc 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -73,38 +73,61 @@ bool __min_heap_full_inline(min_heap_char *heap) #define min_heap_full_inline(_heap) \ __min_heap_full_inline((min_heap_char *)_heap) =20 +/** + * parent - given the offset of the child, find the offset of the parent. + * @i: the offset of the heap element whose parent is sought. Non-zero. + * @lsbit: a precomputed 1-bit mask, equal to "size & -size" + * @size: size of each element + * + * In terms of array indexes, the parent of element j =3D @i/@size is simp= ly + * (j-1)/2. But when working in byte offsets, we can't use implicit + * truncation of integer divides. + * + * Fortunately, we only need one bit of the quotient, not the full divide. + * @size has a least significant bit. That bit will be clear if @i is + * an even multiple of @size, and set if it's an odd multiple. + * + * Logically, we're doing "if (i & lsbit) i -=3D size;", but since the + * branch is unpredictable, it's done with a bit of clever branch-free + * code instead. + */ +__attribute_const__ __always_inline +static size_t parent(size_t i, unsigned int lsbit, size_t size) +{ + i -=3D size; + i -=3D size & -(i & lsbit); + return i / 2; +} + /* Sift the element at pos down the heap. */ static __always_inline void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem= _size, const struct min_heap_callbacks *func, void *args) { - void *left, *right; + const unsigned long lsbit =3D elem_size & -elem_size; void *data =3D heap->data; - void *root =3D data + pos * elem_size; - int i =3D pos, j; + /* pre-scale counters for performance */ + size_t a =3D pos * elem_size; + size_t b, c, d; + size_t n =3D heap->nr * elem_size; =20 /* Find the sift-down path all the way to the leaves. */ - for (;;) { - if (i * 2 + 2 >=3D heap->nr) - break; - left =3D data + (i * 2 + 1) * elem_size; - right =3D data + (i * 2 + 2) * elem_size; - i =3D func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; - } + for (b =3D a; c =3D 2 * b + elem_size, (d =3D c + elem_size) < n;) + b =3D func->less(data + c, data + d, args) ? c : d; =20 /* Special case for the last leaf with no sibling. */ - if (i * 2 + 2 =3D=3D heap->nr) - i =3D i * 2 + 1; + if (d =3D=3D n) + b =3D c; =20 /* Backtrack to the correct location. */ - while (i !=3D pos && func->less(root, data + i * elem_size, args)) - i =3D (i - 1) / 2; + while (b !=3D a && func->less(data + a, data + b, args)) + b =3D parent(b, lsbit, elem_size); =20 /* Shift the element into its correct place. */ - j =3D i; - while (i !=3D pos) { - i =3D (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size, args); + c =3D b; + while (b !=3D a) { + b =3D parent(b, lsbit, elem_size); + func->swp(data + b, data + c, args); } } =20 @@ -117,15 +140,17 @@ static __always_inline void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size= _t idx, const struct min_heap_callbacks *func, void *args) { + const unsigned long lsbit =3D elem_size & -elem_size; void *data =3D heap->data; - size_t parent; + /* pre-scale counters for performance */ + size_t a =3D idx * elem_size, b; =20 - while (idx) { - parent =3D (idx - 1) / 2; - if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + while (a) { + b =3D parent(a, lsbit, elem_size); + if (func->less(data + b, data + a, args)) break; - func->swp(data + parent * elem_size, data + idx * elem_size, args); - idx =3D parent; + func->swp(data + a, data + b, args); + a =3D b; } } =20 --=20 2.34.1 From nobody Wed Nov 27 04:33:10 2024 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AC1C014A099; Sun, 13 Oct 2024 18:47:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845268; cv=none; b=c/vGwiH/czfGI78IxZ83JCmuqBLjf6M/MmgXgT3jG4T6/hCxH8j243d0lwPpjCyWCiEAyefrokoFxvgPZeTOJDMX7vDJrAkk+ceI/fo6dW9GX6BNZJlTAjSe3G6/BoNIoOTgRzshSJEnB3TCZjMKMT7BBiS/Ti5DM7Lwk5/fFb4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1728845268; c=relaxed/simple; bh=c7WKBTPrmngq9myKPpfy/pZOPQyNCg+U1tfIRJk85Bg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Q5eeb4N3/3c5mlE0IZ28yn0wjA/cDIua4AtBH911Q0gRUclcSRUk1xDGz9lnsK34oyUgyx6H+4R9JmZD1Cl0RICRIyuIvEhM01GYfYBhVRH3YgCeKr2Bn+uKhCUtizTvWUddlUKCkxrwMRgCG+vW/ld6FmQ1rIOaKQwIPs50LfM= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=SjTWfyHP; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="SjTWfyHP" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-20ce5e3b116so2379645ad.1; Sun, 13 Oct 2024 11:47:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1728845266; x=1729450066; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=1/mFOHpPMXuU8k7f+cnkaZVTuGcgYo1bsIZNqqH7oLs=; b=SjTWfyHPMjUOz65Ike3G3C+EiIVyK1bFFw1r0zBzapjMcY6re7jP2LOrmX5WtjIWpt lW1jWt6nBlujIbFEXgZpsQNNdBcK/97r15Gg9+r7gUcS865bwbh10TXYx9Nu/ENIvNio A0h7tVgEPrsBcA9RUvfz+EXB2Zu7LxIQACLvVlIDXh1ypsuUZk5iOqR50AiM+MGjtX7z t3eTcgOw7zycCWPzyy3FZlCh6I4Jc+TH6WhbSPYhmGpCNUC/v5uOWx57JA1kmUrZCyEK zTHhxz1IOA6/C22EAVODcS24zrSEiyuOfWMuimrB3goXJxUfyblDk2tY1c3cwVWPuIrp rAYA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1728845266; x=1729450066; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=1/mFOHpPMXuU8k7f+cnkaZVTuGcgYo1bsIZNqqH7oLs=; b=QbKzoFYwMfqCZkU9Qn1DGG22YptMGxodfD+gNUV1NxG0UiSw4/t6SXRYC9ofbSyWqb 0I9EI7Gzkfag01kbFJ7KmkwiuUd1xGUUlK6XNArCY/iDE7hJFYEpVZHyMBqV2eOtYaYT AoVAyXr5tbhw1xbdVWpA4A8+K4bp1bKt7h7zAcvLD/Xq933dJ/N1RhF60LjH5JpoVJU6 IquT+qDaAEHZKeVNc2iRPBt4vNlBMW/2far1qT5zG4MjhmhIdB9xJehO+ia/ZNNcxd2b 9IY9vVdNFCcOnlQaT4x1l+x4t2PKrvhU5ycnhTTtnFrOleMBl2k0X98tpyLblM4EC9fB 8s7A== X-Forwarded-Encrypted: i=1; AJvYcCUC7gkah3J3+u4gTISPTKSwQrh9zfI8ZHeoAhGS+9De2xaJxFSAF4c6vcGqS5AU28sf6Qhj9fC5opXWvXXqEdE=@vger.kernel.org, AJvYcCVFnV5+s+rnF4BiRscbyAL++2rE56OoO1frqTnwt+wi9FapX9MfrleIxVnfW/1U4NsuSwDcS9lXvoU/0iM0@vger.kernel.org, AJvYcCVHYlQEGNnt10ujCj2yuAr/od+FbCp9/6tlcwljZyNvpsSUInzo9HDZRL1P/0ZnLYOxDkuZMyFapNvZOuw=@vger.kernel.org, AJvYcCW7/Xf/PMrUvb3+dD7wjc81XdibSLJROMUPD2n0Z41k/hD3n8cSa8sDsC6yf0Zbuxe0FfWqI7A18Xbo@vger.kernel.org, AJvYcCW9JvGMjm3UVmcUykP9X6XRh5hT9Y7oj+8xG3EF8unzMbVn3nOhUQDYoMJ4aJ0zQZI3JwvJUdJvqW3F02u8oCc4pg==@vger.kernel.org X-Gm-Message-State: AOJu0YyZ3KrctzWX5Htka0fdAPEfO6bat6i5+Jp/CaOnpHB6T9cC3G+D 98EVckdIOtgp3ieQE8Kmn+FIY9UHWxzgXtV/1fagSIq/hW9bzOHO X-Google-Smtp-Source: AGHT+IHrJrJ/x7XXN2RAQDJ5hnFXXhKF8r06t7Er8uLmJc/maAa5w8TH/7bHy/qsVMx3a1vWpKIQSQ== X-Received: by 2002:a17:903:32c9:b0:20c:528d:7063 with SMTP id d9443c01a7336-20cbb196046mr94002585ad.19.1728845265938; Sun, 13 Oct 2024 11:47:45 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-20c8c348f41sm52681965ad.289.2024.10.13.11.47.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 13 Oct 2024 11:47:45 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, corbet@lwn.net, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, kan.liang@linux.intel.com, jserv@ccns.ncku.edu.tw, linux-kernel@vger.kernel.org, linux-bcache@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, linux-doc@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH 3/3] Documentation/core-api: Add min heap API introduction Date: Mon, 14 Oct 2024 02:47:03 +0800 Message-Id: <20241013184703.659652-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241013184703.659652-1-visitorckw@gmail.com> References: <20241013184703.659652-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce an overview of the min heap API, detailing its usage and functionality. The documentation aims to provide developers with a clear understanding of how to implement and utilize min heaps within the Linux kernel, enhancing the overall accessibility of this data structure. Signed-off-by: Kuan-Wei Chiu --- Documentation/core-api/index.rst | 1 + Documentation/core-api/min_heap.rst | 291 ++++++++++++++++++++++++++++ 2 files changed, 292 insertions(+) create mode 100644 Documentation/core-api/min_heap.rst diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/inde= x.rst index 6a875743dd4b..563b8fc0002f 100644 --- a/Documentation/core-api/index.rst +++ b/Documentation/core-api/index.rst @@ -52,6 +52,7 @@ Library functionality that is used throughout the kernel. wrappers/atomic_bitops floating-point union_find + min_heap =20 Low level entry and exit =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/m= in_heap.rst new file mode 100644 index 000000000000..dd2cc5a32fd7 --- /dev/null +++ b/Documentation/core-api/min_heap.rst @@ -0,0 +1,291 @@ +.. SPDX-License-Identifier: GPL-2.0 + +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D +Min Heap API +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Introduction +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +The Min Heap API provides a set of functions and macros for managing min-h= eaps in the Linux kernel. +A min-heap is a binary tree structure where the value of each node is less= than or equal to the +values of its children, ensuring that the smallest element is always at th= e root. + +This API supports efficient insertion, deletion, and access to the minimum= element. It is optimized +for use in systems with performance constraints and is suitable for scenar= ios where the minimum +element needs to be accessed or updated frequently. + +This document provides a guide to the Min Heap API, detailing how to defin= e and use min-heaps. +Please note that users should not directly call functions with **__min_hea= p_*()** names, but should +instead use the provided macro wrappers. + +In addition to the standard version of the functions, the API also include= s a set of inline +versions for performance-critical scenarios. These inline functions have t= he same names as their +non-inline counterparts but include an **_inline** suffix. For example, **= __min_heap_init_inline** +and its corresponding macro wrapper **min_heap_init_inline**. As with the = non-inline versions, it +is important to use the macro wrappers for inline functions instead of dir= ectly calling the +functions themselves. + +Data Structures +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +Min-Heap Definition +------------------- + +The core data structure for representing a min-heap is defined using the *= *MIN_HEAP_PREALLOCATED** +and **DEFINE_MIN_HEAP** macros. These macros allow you to define a min-hea= p with a preallocated +buffer or dynamically allocated memory. + +Example: + +.. code-block:: c + + #define MIN_HEAP_PREALLOCATED(_type, _name, _nr) + struct _name { + int nr; /* Number of elements in the heap */ + int size; /* Maximum number of elements that can be held */ + _type *data; /* Pointer to the heap data */ + _type preallocated[_nr]; /* Static preallocated array */ + } + + #define DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _na= me, 0) + +A typical heap structure will include a counter for the number of elements= (`nr`), the maximum +capacity of the heap (`size`), and a pointer to an array of elements (`dat= a`). Optionally, you can +specify a static array for preallocated heap storage using **MIN_HEAP_PREA= LLOCATED**. + +Min Heap Callbacks +------------------ + +The **struct min_heap_callbacks** provides customization options for order= ing +elements in the heap and swapping them. It contains two function pointers: + +.. code-block:: c + + struct min_heap_callbacks { + bool (*less)(const void *lhs, const void *rhs, void *args); + void (*swp)(void *lhs, void *rhs, void *args); + }; + +- **less** is the comparison function used to establish the order of eleme= nts. +- **swp** is a function for swapping elements in the heap. + +Macro Wrappers +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +The following macro wrappers are provided for interacting with the heap in= a user-friendly manner. +Each macro corresponds to a function that operates on the heap, and they a= bstract away direct calls +to internal functions. + +Each macro accepts various parameters that are detailed below. + +Heap Initialization +-------------------- + +.. code-block:: c + + min_heap_init(heap, data, size); + +- **heap**: A pointer to the min-heap structure to be initialized. +- **data**: A pointer to the buffer where the heap elements will be stored= . If `NULL`, the preallocated buffer within the heap structure will be used. +- **size**: The maximum number of elements the heap can hold. + +This macro initializes the heap, setting its initial state. If `data` is `= NULL`, the preallocated +memory inside the heap structure will be used for storage. Otherwise, the = user-provided buffer is +used. The operation is **O(1)**. + +**Inline Version:** min_heap_init_inline(heap, data, size) + +Accessing the Top Element +------------------------- + +.. code-block:: c + + element =3D min_heap_peek(heap); + +- **heap**: A pointer to the min-heap from which to retrieve the smallest = element. + +This macro returns a pointer to the smallest element (the root) of the hea= p, or `NULL` if the heap +is empty. The operation is **O(1)**. + +**Inline Version:** min_heap_peek_inline(heap) + +Heap Insertion +-------------- + +.. code-block:: c + + success =3D min_heap_push(heap, element, callbacks, args); + +- **heap**: A pointer to the min-heap into which the element should be ins= erted. +- **element**: A pointer to the element to be inserted into the heap. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro inserts an element into the heap. It returns `true` if the inse= rtion was successful and +`false` if the heap is full. The operation is **O(log n)**. + +**Inline Version:** min_heap_push_inline(heap, element, callbacks, args) + +Heap Removal +------------ + +.. code-block:: c + + success =3D min_heap_pop(heap, callbacks, args); + +- **heap**: A pointer to the min-heap from which to remove the smallest el= ement. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro removes the smallest element (the root) from the heap. It retur= ns `true` if the element +was successfully removed, or `false` if the heap is empty. The operation i= s **O(log n)**. + +**Inline Version:** min_heap_pop_inline(heap, callbacks, args) + +Heap Maintenance +---------------- + +You can use the following macros to maintain the heap's structure: + +.. code-block:: c + + min_heap_sift_down(heap, pos, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **pos**: The index from which to start sifting down. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro restores the heap property by moving the element at the specifi= ed index (`pos`) down the +heap until it is in the correct position. The operation is **O(log n)**. + +**Inline Version:** min_heap_sift_down_inline(heap, pos, callbacks, args) + +.. code-block:: c + + min_heap_sift_up(heap, idx, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **idx**: The index of the element to sift up. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro restores the heap property by moving the element at the specifi= ed index (`idx`) up the +heap. The operation is **O(log n)**. + +**Inline Version:** min_heap_sift_up_inline(heap, idx, callbacks, args) + +.. code-block:: c + + min_heapify_all(heap, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro ensures that the entire heap satisfies the heap property. It is= called when the heap is +built from scratch or after many modifications. The operation is **O(n)**. + +**Inline Version:** min_heapify_all_inline(heap, callbacks, args) + +Removing Specific Elements +-------------------------- + +.. code-block:: c + + success =3D min_heap_del(heap, idx, callbacks, args); + +- **heap**: A pointer to the min-heap. +- **idx**: The index of the element to delete. +- **callbacks**: A pointer to a `struct min_heap_callbacks` providing the = `less` and `swp` functions. +- **args**: Optional arguments passed to the `less` and `swp` functions. + +This macro removes an element at the specified index (`idx`) from the heap= and restores the heap +property. The operation is **O(log n)**. + +**Inline Version:** min_heap_del_inline(heap, idx, callbacks, args) + +Other Utilities +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +- **min_heap_full(heap)**: Checks whether the heap is full. Complexity: **= O(1)**. + +.. code-block:: c + + bool full =3D min_heap_full(heap); + +- `heap`: A pointer to the min-heap to check. + +This macro returns `true` if the heap is full, otherwise `false`. + +**Inline Version:** min_heap_full_inline(heap) + +- **min_heap_empty(heap)**: Checks whether the heap is empty. Complexity: = **O(1)**. + +.. code-block:: c + + bool empty =3D min_heap_empty(heap); + +- `heap`: A pointer to the min-heap to check. + +This macro returns `true` if the heap is empty, otherwise `false`. + +**Inline Version:** min_heap_empty_inline(heap) + +Example Usage +=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D + +An example usage of the min-heap API would involve defining a heap structu= re, +initializing it, and inserting and removing elements as needed. + +.. code-block:: c + + /* Define a preallocated heap for storing up to 10 elements */ + MIN_HEAP_PREALLOCATED(int, my_heap, 10); + + struct min_heap_callbacks callbacks =3D { + .less =3D my_less, /* Custom comparison function */ + .swp =3D my_swap, /* Custom swap function */ + }; + + /* Initialize the heap using the preallocated buffer */ + min_heap_init(&my_heap, NULL, ARRAY_SIZE(my_heap.preallocated)); + + /* If we have an external buffer, we can use it instead */ + int external_buffer[20]; + min_heap_init(&my_heap, external_buffer, ARRAY_SIZE(external_buffer)); + + /* Insert elements into the heap */ + int new_element =3D 5; + if (!min_heap_full(&my_heap)) { + min_heap_push(&my_heap, &new_element, &callbacks, NULL); + } + + /* Peek at the minimum element (without removing it) */ + int *min_element =3D min_heap_peek(&my_heap); + + /* Replace the root of the heap with a new element */ + int replacement_element =3D 3; + min_heap_pop_push(&my_heap, &replacement_element, &callbacks, NULL); + + /* Reorder the heap by sifting down from a given position */ + min_heap_sift_down(&my_heap, 0, &callbacks, NULL); + + /* Remove the minimum element from the heap */ + if (!min_heap_empty(&my_heap)) { + min_heap_pop(&my_heap, &callbacks, NULL); + } + + /* Insert more elements into the heap */ + new_element =3D 8; + if (!min_heap_full(&my_heap)) { + min_heap_push(&my_heap, &new_element, &callbacks, NULL); + } + + /* Delete an element from the heap at a specific index */ + int idx_to_delete =3D 2; + min_heap_del(&my_heap, idx_to_delete, &callbacks, NULL); + + /* Ensure the entire heap maintains heap order */ + min_heapify_all(&my_heap, &callbacks, NULL); --=20 2.34.1