From patchwork Sun Oct 20 04:01:51 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842961 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (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 E5ED8EADA for ; Sun, 20 Oct 2024 04:02:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396949; cv=none; b=ZJYGiZnpYXfnuqRr12hDFKwbrKVgjQpkFk0UVrLVsG+FjskiAOFvi0/qwr1dtHqXo3KIPRkPtkO6U8ilp5rxkFsx3sh17dZh67lLkly7bNHwLdyETB2OAlWfaRbrHaQnh2mEddS7TUo9449cjnowj6LWsqm4lvuc77pXug1fe0M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396949; c=relaxed/simple; bh=AuW17kDORWd0KDHQZdR2xWDyCr+wDKId6jBES0rwfzA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=RUKYM8CTB82iOoL+sWb1yZcLkIZdhlIF6hPetU6KQhCy/pF4a5gDq6yhaliyC6Ly+GoDcEUqZOf9hAjgi7HS9HrzztUn0NVKHyxBSjIESVUMtV0e0BKGqLfp3ZJoORqWdxeL1Pp6XqaSgSjx7o0ExPSHVvO8jqggHoovhY4cKss= 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=XTCJSNQD; arc=none smtp.client-ip=209.85.216.49 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="XTCJSNQD" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2e30db524c2so2522425a91.1 for ; Sat, 19 Oct 2024 21:02:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396946; x=1730001746; darn=lists.linux.dev; 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=ocJAjO3VEDnwWXU1UORPzcLbPWZJaMhjLdoDnx0hezA=; b=XTCJSNQDt6SJBnEk+DjoKV0M6dMLIEzG64ABYIWfoUsjT27tbYs5NXj4+Fcntr+sVu FUVDGaUStwCXqyiZ7MLktLuMFTPD7fa1WOC0YfhxG3t2KlhFCVJ8+VxgQJwQS7LpYDne jh1zQr/DeFuQ0yA86PJJA+mgsdMFx3y6OAJS3epkTOlqxZJ0JzzY8kYpyJFo5rFn68D3 XSfmzaUUOiMUETpArJNtCTZHs9QQOsgO2PMThUo23gkRGL3bXwTjDtw3SLAhi8ROUIV8 17snqvnE6/x4ujqoNWWeVj/K2oncaaxhDYiytX57aAcBqoZRsVLwssWBdvogZobYrZe1 qtZQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396946; x=1730001746; 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=ocJAjO3VEDnwWXU1UORPzcLbPWZJaMhjLdoDnx0hezA=; b=qbJ07TKq9YQFEGkpUXkU75anvSz65mJX1myAxRgxbcE6gFXc42TmjJgv6ps/NonR8K iV1Am1CODJ4N6S2tJPVFXxUIj3zqoteCRt2p6mxm+HMjiBKUgqOrb2P0oxcvxSqMRyvc is19ljV+Hy2dN0VjGiCwwNyRmU+cglabAHGWLkFrdrStqifzk2UJ6FaHy6R/EAS78xjT WF0hC3YF4/y4eeFmGaKsuAnVbjMngcipvJbuzVnpCOoqSJCo5gA6YZRnCNW3pjdoiJO2 M080uU0NpwQO+pbO2JnLUrn6SL3YsBit+ufr0P72obN1qaIKS+XMsALRcRWcxlPbe3BK poew== X-Forwarded-Encrypted: i=1; AJvYcCVKjK7u0oU4VtzKA5zosZYfwLrH28RrGAmgemto+aQ+j1p/jZKkkUXDfvnrpCb7Le9pMzoo3jOq1A==@lists.linux.dev X-Gm-Message-State: AOJu0YwXQqg35WviP4XILIGMGgae3EDGUohaPkEy27aJF1j9MukVIDzK +5dntDDZ+8w/Ojq4I8dGTy6CtWLEnFVQP5IfpjSZPiEvij+SIhCysApaaw== X-Google-Smtp-Source: AGHT+IFVG/U8s3V87FeUqj8Nc4N7rb/VosY5/redFg5afiXWk0Rer4YIpFZdFk+EoegzMF4SH9tSTw== X-Received: by 2002:a17:90b:4b4a:b0:2e2:b211:a4da with SMTP id 98e67ed59e1d1-2e5616ec45bmr9059569a91.14.1729396945986; Sat, 19 Oct 2024 21:02:25 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:25 -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, willy@infradead.org, 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 v2 01/10] lib/min_heap: Introduce non-inline versions of min heap API functions Date: Sun, 20 Oct 2024 12:01:51 +0800 Message-Id: <20241020040200.939973-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 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 --- Code size for bcache: Before: text data bss dec hex filename 7257 302 0 7559 1d87 ./drivers/md/bcache/alloc.o 10786 515 0 11301 2c25 ./drivers/md/bcache/bset.o 33246 1596 8 34850 8822 ./drivers/md/bcache/btree.o 7195 256 0 7451 1d1b ./drivers/md/bcache/extents.o 3524 174 0 3698 e72 ./drivers/md/bcache/movinggc.o 17424 2816 0 20240 4f10 ./drivers/md/bcache/sysfs.o 8994 328 0 9322 246a ./drivers/md/bcache/writeback.o After: text data bss dec hex filename 6339 300 0 6639 19ef ./drivers/md/bcache/alloc.o 10428 537 0 10965 2ad5 ./drivers/md/bcache/bset.o 33134 1596 8 34738 87b2 ./drivers/md/bcache/btree.o 6619 264 0 6883 1ae3 ./drivers/md/bcache/extents.o 2958 152 0 3110 c26 ./drivers/md/bcache/movinggc.o 17408 2816 0 20224 4f00 ./drivers/md/bcache/sysfs.o 8962 328 0 9290 244a ./drivers/md/bcache/writeback.o Code size for bcachefs: Before: text data bss dec hex filename 2286 155 0 2441 989 ./fs/bcachefs/clock.o 41481 1634 20 43135 a87f ./fs/bcachefs/ec.o After: text data bss dec hex filename 1928 132 0 2060 80c ./fs/bcachefs/clock.o 40259 1624 20 41903 a3af ./fs/bcachefs/ec.o Code size for dm-vdo: Before: text data bss dec hex filename 14047 264 0 14311 37e7 ./drivers/md/dm-vdo/repair.o 37432 944 0 38376 95e8 ./drivers/md/dm-vdo/slab-depot.o After: text data bss dec hex filename 13697 264 0 13961 3689 ./drivers/md/dm-vdo/repair.o 37074 960 0 38034 9492 ./drivers/md/dm-vdo/slab-depot.o Code size for test_min_heap: Before: text data bss dec hex filename 5499 171 0 5670 1626 ./lib/test_min_heap.o After: text data bss dec hex filename 2581 96 0 2677 a75 ./lib/test_min_heap.o 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 { /* 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 = 0; heap->size = size; @@ -50,33 +50,33 @@ void __min_heap_init(min_heap_char *heap, void *data, int size) heap->data = heap->preallocated; } -#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) /* 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; } -#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)) /* 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 == heap->size; } -#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) /* 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 = heap->data; @@ -108,13 +108,14 @@ void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, } } -#define min_heap_sift_down(_heap, _pos, _func, _args) \ - __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) +#define min_heap_sift_down_inline(_heap, _pos, _func, _args) \ + __min_heap_sift_down_inline((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), \ + _func, _args) /* 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 = heap->data; size_t parent; @@ -128,27 +129,28 @@ void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, } } -#define min_heap_sift_up(_heap, _idx, _func, _args) \ - __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) +#define min_heap_sift_up_inline(_heap, _idx, _func, _args) \ + __min_heap_sift_up_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, \ + _func, _args) /* 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; for (i = heap->nr / 2 - 1; i >= 0; i--) - __min_heap_sift_down(heap, i, elem_size, func, args); + __min_heap_sift_down_inline(heap, i, elem_size, func, args); } -#define min_heapify_all(_heap, _func, _args) \ - __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args) +#define min_heapify_all_inline(_heap, _func, _args) \ + __min_heapify_all_inline((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args) /* 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 = heap->data; @@ -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); return true; } -#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) /* * 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); } -#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_obj_size(_heap), \ + _func, _args) /* 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 = 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++; /* 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); return true; } -#define min_heap_push(_heap, _element, _func, _args) \ - __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args) +#define min_heap_push_inline(_heap, _element, _func, _args) \ + __min_heap_push_inline((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), \ + _func, _args) /* 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 idx, + const struct min_heap_callbacks *func, void *args) { void *data = heap->data; @@ -224,12 +226,53 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, if (idx == 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); return true; } +#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(_heap), _func, _args) +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _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(_heap), _func, _args) #define min_heap_del(_heap, _idx, _func, _args) \ __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) 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_event_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } - min_heapify_all(&event_heap, &perf_min_heap, NULL); + min_heapify_all_inline(&event_heap, &perf_min_heap, NULL); while (event_heap.nr) { ret = func(*evt, data); @@ -3879,9 +3879,9 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, *evt = 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); } 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 config FIRMWARE_TABLE bool + +config MIN_HEAP + bool diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index 7312ae7c3cc5..c9e6ce184044 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 := ctype.o string.o vsprintf.o cmdline.o \ lib-$(CONFIG_PRINTK) += dump_stack.o lib-$(CONFIG_SMP) += cpumask.o +lib-$(CONFIG_MIN_HEAP) += min_heap.o lib-y += kobject.o klist.o obj-y += 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); From patchwork Sun Oct 20 04:01:52 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842962 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (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 1DEC1F9D6 for ; Sun, 20 Oct 2024 04:02:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396953; cv=none; b=sunsRMlkwm/5eqLJPgASBYfTS2YYGG1aaw1Cq7PNKxpace17+QmQ63JFHyMtmBUgn4JkdNwvsCjW6OaJqEe8Q09Mt7X+oO0s3CMRXl0PzXNAhlAzvlVbJES2ABC7Riq+fFOYONyZu8zF992+QODMW7f2omioS+MYcVwkO2D1sWw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396953; c=relaxed/simple; bh=bcureVGzcJTl4EGz6UOvdZmrS2DwQAd4xqIXv8oXxmU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=YCC28ynehzIMEDdqTs2losiUwZ3kjnFVLO7n1Pq72M162FE1l4ojbJ8UFZ2d+K3MglJIUnltllyBXaoPRFEuJhB/9gLGjqTayKECg/rvA48CneWJUscY/tJ6w93b+proz/8xHR6GDwUlKlO2cSnPyUofwBeQYTO4R5eBlE6SY9s= 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=Gg9fNQw4; arc=none smtp.client-ip=209.85.216.49 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="Gg9fNQw4" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2e2a97c2681so2548716a91.2 for ; Sat, 19 Oct 2024 21:02:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396951; x=1730001751; darn=lists.linux.dev; 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=kEpu7Ky7AWCWOFJdxOuINvLNFSfvYS/gqDPpnqne2TQ=; b=Gg9fNQw4eA3gGAsl4lHbo9kPtpVNgiPBEFPgBc2GMkkLtj2N4batJMh2NwHvMmGiR+ JuIeytXPfAKQSAnrQ4NUJFUtc22MwCWyLBjU8W0KVEWviFTaVi8EsXHLZ9IeJNerATDF 0h2aV8ST7+8J/UdDKXFYQP/5xVRwQeBpVr12GT/6UP7wyfgc2EotT3A6l4Anot5CBYf8 I0uRdF/gHMnenuLQtxb/lJiB+QPvQUkHFW8PL6rvFEa4zlScwaq9ABXEg2yYAv4oKOFd PBJAYT6FdREtGDYroaIHEbvOVnXMCKhl1BVO6voSNLTJe8BX+B+jLfc9knDKw6sj4+UN sQxg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396951; x=1730001751; 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=kEpu7Ky7AWCWOFJdxOuINvLNFSfvYS/gqDPpnqne2TQ=; b=S6Aw/rGMVQ5neaQCid0Ou6zzz4UNlew53S2ppcuIoImp391pIUNx7zbo862gXsHZUY c/NSRb+m8lz4EPxge/cvyl1+MY6CgOfvI8D1l/bW9whCrY661xX/QzfrsK2hLaHEr+Ad DiVXRpVjYNLucZPNcV0Xg9AeBbDuy5cAqQwWbd6lxIQVX7Yfx7bvpDOehyg3i5F/BkFy pQbVd6+zSW0WhE4qmanF8w6/PZbDB1++lRC0voGQPfrE+CF+okvSFoyuUnttx3974D/M 3tdNHCGJDZgwLhXs/QqTLqRLHgEMZF4JOiMoOQCmlSwwxBlmKruK1TcBt4lQQSuI1n+x PPTQ== X-Forwarded-Encrypted: i=1; AJvYcCWqlBKK23Br/LFdxJoSrNiSeLk67aNG8/89dWysURNSW8fGEsKvqnOzPWE304+/nu249kt7Nfcc6A==@lists.linux.dev X-Gm-Message-State: AOJu0YyXY4qZEOVoIByIkeQIo3IYeNOeXNcgwmktLt+OseBjEUP+IZy1 gzenpD8zJ8pAn0Ye29LDOk91/pCCbo7eqfFtWtlnveqg1G2BQ5LK X-Google-Smtp-Source: AGHT+IFk+ATyk4pJ+7WvwCX9XmFve66rkS7xXAujAtf2P3tgkVxx6WRk8TPvXLHd3k4vmtAoyRXaJA== X-Received: by 2002:a17:90a:ab0e:b0:2e0:74c9:ecf1 with SMTP id 98e67ed59e1d1-2e561718d7amr5493762a91.10.1729396951374; Sat, 19 Oct 2024 21:02:31 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:30 -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, willy@infradead.org, 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 v2 02/10] lib min_heap: Optimize min heap by prescaling counters for better performance Date: Sun, 20 Oct 2024 12:01:52 +0800 Message-Id: <20241020040200.939973-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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..41b092a14238 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -38,6 +38,32 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs, void *args); }; +/** + * 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 = @i/@size is simply + * (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 -= 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 -= size; + i -= size & -(i & lsbit); + return i / 2; +} + /* Initialize a min-heap. */ static __always_inline void __min_heap_init_inline(min_heap_char *heap, void *data, int size) @@ -78,33 +104,30 @@ 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 = elem_size & -elem_size; void *data = heap->data; - void *root = data + pos * elem_size; - int i = pos, j; + /* pre-scale counters for performance */ + size_t a = pos * elem_size; + size_t b, c, d; + size_t n = heap->nr * elem_size; /* Find the sift-down path all the way to the leaves. */ - for (;;) { - if (i * 2 + 2 >= heap->nr) - break; - left = data + (i * 2 + 1) * elem_size; - right = data + (i * 2 + 2) * elem_size; - i = func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; - } + for (b = a; c = 2 * b + elem_size, (d = c + elem_size) < n;) + b = func->less(data + c, data + d, args) ? c : d; /* Special case for the last leaf with no sibling. */ - if (i * 2 + 2 == heap->nr) - i = i * 2 + 1; + if (d == n) + b = c; /* Backtrack to the correct location. */ - while (i != pos && func->less(root, data + i * elem_size, args)) - i = (i - 1) / 2; + while (b != a && func->less(data + a, data + b, args)) + b = parent(b, lsbit, elem_size); /* Shift the element into its correct place. */ - j = i; - while (i != pos) { - i = (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size, args); + c = b; + while (b != a) { + b = parent(b, lsbit, elem_size); + func->swp(data + b, data + c, args); } } @@ -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 = elem_size & -elem_size; void *data = heap->data; - size_t parent; + /* pre-scale counters for performance */ + size_t a = idx * elem_size, b; - while (idx) { - parent = (idx - 1) / 2; - if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + while (a) { + b = 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 = parent; + func->swp(data + a, data + b, args); + a = b; } } From patchwork Sun Oct 20 04:01:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842963 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (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 0E55729415 for ; Sun, 20 Oct 2024 04:02:36 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396959; cv=none; b=ojn5AZnNQ/UUQZVSQCg9NHqfR7h/0d5KXaF0krz15G+6ekG6xv4Qi74QTRr1v5p2Oxe/9vRM8PSSGKIC91MNH0IkO9f1CRCD0gcJC5ZQ9KM/M4U3tdCRhsbw6TQKjY59f1AsZ2szjyUV401HKhc77Im0WWyosV8xe8xlvsY7A+o= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396959; c=relaxed/simple; bh=qw7hRUVQUjmF1vm384Re4kBa8L2DFdqc5hxtKTyAUBc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fpjYiJ+6vT4tHcFgi5g5AOF81gPc3PsSiN0VY4WIw5OPPJgcuuNavaspXMewG1g69rnIDxYtrYjCjScuBd/5rgFsfQaranPmXsBHdaYGc9IPspevGgn3Vy8UEobBTlTPQCR6Lj5xspfduzEMnbfMGWVc5vPd3r8Ye5bwHuVmWKE= 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=fuKow5kj; arc=none smtp.client-ip=209.85.216.49 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="fuKow5kj" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2e2cc469c62so2347185a91.2 for ; Sat, 19 Oct 2024 21:02:36 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396956; x=1730001756; darn=lists.linux.dev; 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=y6nVlRSYluEaO2jXun3j/1xuNdrqdaSLggEauAQK2do=; b=fuKow5kjzPaxonj32FgPwpSyyRl3Qg9fLI3CIj8I9STOATLuWw6RYtHkuP5KdYq/lY fHTh/beW0ESki8LLNy8TPr0z6/HiE6C6g05aBRtCWGFNeQAqx7cWta3j7I45+ZwHSmTB 71Wiwvz6Iu87swmlwavcq0k05PVlpr4Smef8SrOTA3f/jHThphQVXsG+DRid5fqpaIuk iEuPOdtgOw1LM8lrGRSx3kX+YZG8U5YCWeER1i8XTyUHY+YcyP6G7oBN2JAUWohCZ7jw +44Ofhgt1FmbKHciagK0c7ygUsl9xR/oVqyTi/gS8qvoF3L8lIEz/zofUeotxhfadDu/ ePXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396956; x=1730001756; 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=y6nVlRSYluEaO2jXun3j/1xuNdrqdaSLggEauAQK2do=; b=Jhg7vE8NrFD43yB/CoMCMVuT+Nb0weN2BPfyyY7nolEshL+3WQB9WFuNVURi96pJnD T7pUmAAoSu84PtoOOkpNvnT1ClG/uUbNyX3yzU3R0XwKGgN3uw5r9yYvKwdYhtYrKC+p wq1yY2rTeVfdHd+KQhDnzKf+WIGo8pSub0xut/QbduoGD20FTnnQc5IBRtCcWin/at0c IywbBYs4QhQcaRGCfbfetzRMEExW3v2pqhKaBA8aIYEylW9RgV9QtXXbf2g5wOXQJgsY LubgOrW9c1AJMts6JRZjHb39QJQJinPs6Vwz7/ftvKKkH0JpJjHlZghEKJVZVp36qzqL Bs4A== X-Forwarded-Encrypted: i=1; AJvYcCUjn32kFucCFiV3w8K5EqFvtuJAdOHcvdHTekmQEo1SM+Dynr1J80nVGOas9OIkAXVVTqDrc+RTZg==@lists.linux.dev X-Gm-Message-State: AOJu0Yw2WOtdaJPpHLXYZY2bpsStuJHvwg5wIx7lFPUQRhvnScQat1Be gFo+QjvMlilEa8Si6bVCt4EWQd3W19ZI57KjydtkQ8X2cLmp58ZC X-Google-Smtp-Source: AGHT+IGJ0QD1dssfSeCndTdayTApxMhbahdeVkUz635rlYogw/K2EEenKLVPZ19fI4axaD2q8F/SrA== X-Received: by 2002:a17:90b:1183:b0:2e1:ce7b:6069 with SMTP id 98e67ed59e1d1-2e56190237fmr8607444a91.33.1729396956275; Sat, 19 Oct 2024 21:02:36 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:35 -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, willy@infradead.org, 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 v2 03/10] lib min_heap: Avoid indirect function call by providing default swap Date: Sun, 20 Oct 2024 12:01:53 +0800 Message-Id: <20241020040200.939973-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 The non-inline min heap API can result in an indirect function call to the custom swap function. This becomes particularly costly when CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls are expensive in this case. To address this, copy the code from lib/sort.c and provide a default builtin swap implementation that performs element swaps based on the element size. This change allows most users to avoid the overhead of indirect function calls, improving efficiency. Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 159 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 156 insertions(+), 3 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 41b092a14238..e781727c8916 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -38,6 +38,147 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs, void *args); }; +/** + * is_aligned - is this pointer & size okay for word-wide copying? + * @base: pointer to data + * @size: size of each element + * @align: required alignment (typically 4 or 8) + * + * Returns true if elements can be copied using word loads and stores. + * The size must be a multiple of the alignment, and the base address must + * be if we do not have CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS. + * + * For some reason, gcc doesn't know to optimize "if (a & mask || b & mask)" + * to "if ((a | b) & mask)", so we do that by hand. + */ +__attribute_const__ __always_inline +static bool is_aligned(const void *base, size_t size, unsigned char align) +{ + unsigned char lsbits = (unsigned char)size; + + (void)base; +#ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS + lsbits |= (unsigned char)(uintptr_t)base; +#endif + return (lsbits & (align - 1)) == 0; +} + +/** + * swap_words_32 - swap two elements in 32-bit chunks + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size (must be a multiple of 4) + * + * Exchange the two objects in memory. This exploits base+index addressing, + * which basically all CPUs have, to minimize loop overhead computations. + * + * For some reason, on x86 gcc 7.3.0 adds a redundant test of n at the + * bottom of the loop, even though the zero flag is still valid from the + * subtract (since the intervening mov instructions don't alter the flags). + * Gcc 8.1.0 doesn't have that problem. + */ +static __always_inline +void swap_words_32(void *a, void *b, size_t n) +{ + do { + u32 t = *(u32 *)(a + (n -= 4)); + *(u32 *)(a + n) = *(u32 *)(b + n); + *(u32 *)(b + n) = t; + } while (n); +} + +/** + * swap_words_64 - swap two elements in 64-bit chunks + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size (must be a multiple of 8) + * + * Exchange the two objects in memory. This exploits base+index + * addressing, which basically all CPUs have, to minimize loop overhead + * computations. + * + * We'd like to use 64-bit loads if possible. If they're not, emulating + * one requires base+index+4 addressing which x86 has but most other + * processors do not. If CONFIG_64BIT, we definitely have 64-bit loads, + * but it's possible to have 64-bit loads without 64-bit pointers (e.g. + * x32 ABI). Are there any cases the kernel needs to worry about? + */ +static __always_inline +void swap_words_64(void *a, void *b, size_t n) +{ + do { +#ifdef CONFIG_64BIT + u64 t = *(u64 *)(a + (n -= 8)); + *(u64 *)(a + n) = *(u64 *)(b + n); + *(u64 *)(b + n) = t; +#else + /* Use two 32-bit transfers to avoid base+index+4 addressing */ + u32 t = *(u32 *)(a + (n -= 4)); + *(u32 *)(a + n) = *(u32 *)(b + n); + *(u32 *)(b + n) = t; + + t = *(u32 *)(a + (n -= 4)); + *(u32 *)(a + n) = *(u32 *)(b + n); + *(u32 *)(b + n) = t; +#endif + } while (n); +} + +/** + * swap_bytes - swap two elements a byte at a time + * @a: pointer to the first element to swap + * @b: pointer to the second element to swap + * @n: element size + * + * This is the fallback if alignment doesn't allow using larger chunks. + */ +static __always_inline +void swap_bytes(void *a, void *b, size_t n) +{ + do { + char t = ((char *)a)[--n]; + ((char *)a)[n] = ((char *)b)[n]; + ((char *)b)[n] = t; + } while (n); +} + +/* + * The values are arbitrary as long as they can't be confused with + * a pointer, but small integers make for the smallest compare + * instructions. + */ +#define SWAP_WORDS_64 ((void (*)(void *, void *, void *))0) +#define SWAP_WORDS_32 ((void (*)(void *, void *, void *))1) +#define SWAP_BYTES ((void (*)(void *, void *, void *))2) + +/* + * Selects the appropriate swap function based on the element size. + */ +static __always_inline +void *select_swap_func(const void *base, size_t size) +{ + if (is_aligned(base, size, 8)) + return SWAP_WORDS_64; + else if (is_aligned(base, size, 4)) + return SWAP_WORDS_32; + else + return SWAP_BYTES; +} + +static __always_inline +void do_swap(void *a, void *b, size_t size, void (*swap_func)(void *lhs, void *rhs, void *args), + void *priv) +{ + if (swap_func == SWAP_WORDS_64) + swap_words_64(a, b, size); + else if (swap_func == SWAP_WORDS_32) + swap_words_32(a, b, size); + else if (swap_func == SWAP_BYTES) + swap_bytes(a, b, size); + else + swap_func(a, b, priv); +} + /** * 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. @@ -106,11 +247,15 @@ void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem_size, { const unsigned long lsbit = elem_size & -elem_size; void *data = heap->data; + void (*swp)(void *lhs, void *rhs, void *args) = func->swp; /* pre-scale counters for performance */ size_t a = pos * elem_size; size_t b, c, d; size_t n = heap->nr * elem_size; + if (!swp) + swp = select_swap_func(data, elem_size); + /* Find the sift-down path all the way to the leaves. */ for (b = a; c = 2 * b + elem_size, (d = c + elem_size) < n;) b = func->less(data + c, data + d, args) ? c : d; @@ -127,7 +272,7 @@ void __min_heap_sift_down_inline(min_heap_char *heap, int pos, size_t elem_size, c = b; while (b != a) { b = parent(b, lsbit, elem_size); - func->swp(data + b, data + c, args); + do_swap(data + b, data + c, elem_size, swp, args); } } @@ -142,14 +287,18 @@ void __min_heap_sift_up_inline(min_heap_char *heap, size_t elem_size, size_t idx { const unsigned long lsbit = elem_size & -elem_size; void *data = heap->data; + void (*swp)(void *lhs, void *rhs, void *args) = func->swp; /* pre-scale counters for performance */ size_t a = idx * elem_size, b; + if (!swp) + swp = select_swap_func(data, elem_size); + while (a) { b = parent(a, lsbit, elem_size); if (func->less(data + b, data + a, args)) break; - func->swp(data + a, data + b, args); + do_swap(data + a, data + b, elem_size, swp, args); a = b; } } @@ -242,15 +391,19 @@ bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t idx, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; + void (*swp)(void *lhs, void *rhs, void *args) = func->swp; if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) return false; + if (!swp) + swp = select_swap_func(data, elem_size); + /* Place last element at the root (position 0) and then sift down. */ heap->nr--; if (idx == heap->nr) return true; - func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); + do_swap(data + (idx * elem_size), data + (heap->nr * elem_size), elem_size, swp, args); __min_heap_sift_up_inline(heap, elem_size, idx, func, args); __min_heap_sift_down_inline(heap, idx, elem_size, func, args); From patchwork Sun Oct 20 04:01:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842964 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) (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 EB8E640855 for ; Sun, 20 Oct 2024 04:02:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396964; cv=none; b=hl3Dvw4pUMrBepjN3Y4BgIi/NckPQh0JR9pKP9M73j3W8cz4dOCUaA8JNvsLmWBOA6jhEa6cxWUzPe2siR5wyPI2p+EW4bI3RpP/vw+l/tyxcxHmSK00y7dSg2kQioxdpvlx1u1ck7Af+Gkmr2uyRGq9g0oWTqDhYX6DnZoTPCc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396964; c=relaxed/simple; bh=uWD7X4+G72y+WuvTqwWeg7t00M9IRkb3ifQpqG/L/hM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=mU3BKeGqdOXPzy7+RL4tMFXGPzAZxCmMEz2gbDsShzDYzL9TeCzGuqUMOKNDLl/F8Rzq9RjQKjuaD0yfocdy8q1ezLS6jKB/hGsb8oIrdKLobasXTt6za/wol7naGHdH/cqJ05YsW+EI9AFbi5aLPTcM0a+LkIUVb2ai4VwSLCk= 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=QENr7SZB; arc=none smtp.client-ip=209.85.216.54 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="QENr7SZB" Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-2e2ed59a35eso2850457a91.0 for ; Sat, 19 Oct 2024 21:02:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396961; x=1730001761; darn=lists.linux.dev; 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=rSsO9eyAnWGRK9JqMw2hZIz60NRvRqk+DUJGCBdVXsc=; b=QENr7SZBiNRnyMrAkGJ8Gdl0f11a/ca0eMYClUXDHbm0PO0ffI8GHuRThnupfzBkUj St9dMauL4E88YYHsECm2PPT5ycwXMph2jqWHtFFXU+nRXK9IJAz6E30qLDR273CN7ioL GtrZCjMFnRU4KVssUcJjmZqDMWpx6Eddy8PzILTehU20Rpn7caD2ug5JT08jDqhcfVvx dx4qgWM5683ZagqgV75ZW+8xJ2H4yegqupMoqFF1SRSY72rAqevheJXPpEmlSEm4T3S/ 7aZlIE9M/HiUUcSGK1Crjut2Rl13uYzaLGWViGNqwzcOwhThaFo90xtsy2Q7G1P4BPDy HqOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396961; x=1730001761; 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=rSsO9eyAnWGRK9JqMw2hZIz60NRvRqk+DUJGCBdVXsc=; b=Ctuy3hgv5vle4tmGkqrXBQm2poKXwy7Y2a3hJFRA+l/BxS+gnxaCn9IAQ7Rxwqcx8U 8UXNsXKKoRghsApXtJDftZsufRw/vU4PMnHSBIY9t/tgBHJQEy/YWC+E+1XSct5SP2vq mPaHpBYPuEfoSGQAYmngyAmnkE7ycVk55cfCZFLnFxqsouFb8z3y2XY0NrrQU4GhG9fR Xx1LWD6OXqpDwKIsoDqXNPqOc7tuc9m7q/e8KLHgZxYJFjYCTARt2K43OTsT9ASlQ+rB E7eRNsMvSKWb6V5QD6c7bo4CBhpr8XFRIhZ2baeZY1VJZHqIyObdlrckcoFkh/lOla0S XUog== X-Forwarded-Encrypted: i=1; AJvYcCXqqA+fjJt0YEoSS6oItsxv7cJE3wdXgdxiFDBufPKFaGOS+Vg+Tr1pzEkEGCVY+y5WpfKvObRoLQ==@lists.linux.dev X-Gm-Message-State: AOJu0Yz028D4DrVdvGG6kf5kLOY4r6xrKkEylwS8DSUxrgWIgzb56cID Jz1qOXad4oNIe30Cx4uov9xAbscHsKh9rRIMLeoaciiwXONWT31t X-Google-Smtp-Source: AGHT+IGdWI08SJwvOyOfpihMxUYT3OOzFomu22UrUlY7s271MCitpKDj02EZ1IaoGzOFhlnHCnE38Q== X-Received: by 2002:a17:90b:3c47:b0:2e2:bd68:b8d8 with SMTP id 98e67ed59e1d1-2e5616dea4dmr8067411a91.8.1729396961160; Sat, 19 Oct 2024 21:02:41 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:40 -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, willy@infradead.org, 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 v2 04/10] lib/test_min_heap: Update min_heap_callbacks to use default builtin swap Date: Sun, 20 Oct 2024 12:01:54 +0800 Message-Id: <20241020040200.939973-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace the swp function pointer in the min_heap_callbacks of test_min_heap with NULL, allowing direct usage of the default builtin swap implementation. This modification simplifies the code and improves performance by removing unnecessary function indirection. Signed-off-by: Kuan-Wei Chiu --- Tested with test_min_heap module. lib/test_min_heap.c | 16 ++++------------ 1 file changed, 4 insertions(+), 12 deletions(-) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 64c877e73b64..e6fbb798558b 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -23,14 +23,6 @@ static __init bool greater_than(const void *lhs, const void *rhs, void __always_ return *(int *)lhs > *(int *)rhs; } -static __init void swap_ints(void *lhs, void *rhs, void __always_unused *args) -{ - int temp = *(int *)lhs; - - *(int *)lhs = *(int *)rhs; - *(int *)rhs = temp; -} - static __init int pop_verify_heap(bool min_heap, struct min_heap_test *heap, const struct min_heap_callbacks *funcs) @@ -72,7 +64,7 @@ static __init int test_heapify_all(bool min_heap) }; struct min_heap_callbacks funcs = { .less = min_heap ? less_than : greater_than, - .swp = swap_ints, + .swp = NULL, }; int i, err; @@ -104,7 +96,7 @@ static __init int test_heap_push(bool min_heap) }; struct min_heap_callbacks funcs = { .less = min_heap ? less_than : greater_than, - .swp = swap_ints, + .swp = NULL, }; int i, temp, err; @@ -136,7 +128,7 @@ static __init int test_heap_pop_push(bool min_heap) }; struct min_heap_callbacks funcs = { .less = min_heap ? less_than : greater_than, - .swp = swap_ints, + .swp = NULL, }; int i, temp, err; @@ -175,7 +167,7 @@ static __init int test_heap_del(bool min_heap) heap.nr = ARRAY_SIZE(values); struct min_heap_callbacks funcs = { .less = min_heap ? less_than : greater_than, - .swp = swap_ints, + .swp = NULL, }; int i, err; From patchwork Sun Oct 20 04:01:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842965 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) (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 CF29ABA2D for ; Sun, 20 Oct 2024 04:02:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396968; cv=none; b=lv/0P9EbRPLawEKZrmj6HofBOzfKytE7Y/7hXg7TAWlDZ5SPu6f6eshbL4hPXdE+XAXXz3l14inwoBR46z52b94I9DMf1MOk+fFxf2q7HUG5N+Fiwzs18JSZ4nB+jV+s2ivm+O4LLTapPT0Q6USz/jnLuaWJGwKEA8k1/kXitO4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396968; c=relaxed/simple; bh=gyiMjnOkGCmWLW5uchvMDnKTgZ6y7fEOmN1SFiFPiH4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=qXJ+E1P7KgAYq26apSoLC34bqXyHmcSoJHjI6pSAsK25+INyUv/kv/oB2b8TJPK5xipn+9qszAXYLu9g6RCqQj3LHTqhqku7JCykqNGLew9xHq9/XXczS5ZF3Hx9U2RzXnzqu+hU6BLMMI4sHXAjHHZkmKQ+xZgTlcDh3Asg2jQ= 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=h1mIQZg6; arc=none smtp.client-ip=209.85.216.50 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="h1mIQZg6" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-2e2ed2230d8so2532724a91.0 for ; Sat, 19 Oct 2024 21:02:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396966; x=1730001766; darn=lists.linux.dev; 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=6iUBoTJj+mB6KW0shlxuElBqdCTCqkeGFMIEQuiMOBQ=; b=h1mIQZg6h5hDSKjDKQWfa0ya5zx2bQ9SpkyomQaqID94U5vPLgRLqvLTA6bnJ0jAJK lpIkvDJ6X779NQptblJc9XuS9bnIkzZCuez8BptikRrYLJyo+E71QPouepT9+LcMDhe1 la5oUGEknmuv0kQilhPtUW0py7I4ZgbnWWYGt40zRIOfA7R65HmizQtdgV6XPicHr13E 6Zf9afSj38cAmX8T1ZEMd6lI3tL61d5II+UY/M4KxuysQiXY80TnyulM3dT2kta4+1b0 vTm68Hb+uYEuI1ibLsYpRV0Ep6hlW4dFFpHR0CXsbjAeN4H9Z4rtL8cuO9Otl3+gBZLH hgqg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396966; x=1730001766; 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=6iUBoTJj+mB6KW0shlxuElBqdCTCqkeGFMIEQuiMOBQ=; b=oekFtanO3b5wAKCPWSXi7KiSH0aRTIfypCXdp+JCJAJ8VkvRbn7HIcVqGXGxO/GxXT 1nyhC5dZXdmkQTnkmHARy/N8+R3h/xqreUNPcTiTCBNwyr3icHx5Wcv6E6o/mfwMb1xB 36cka8ERoRQHeLWfM79xUe+3U61BDXmhtJfETeK7KbzXvhPiPCShP7YFuPLUC8bCYzYt 3C6b4Z1psyOCXxQdoehXP57Z2jHLMTpT2eOLCRqvsFhayx7g7M6WjwQMKnPbvQ39SUAO HTKxLLnJkWVyQ6+QV6+ApFcn2JX30oX/YMJqr/BTT8wmuhemhLTRh4ogPIWRYSa4gNrq wTQw== X-Forwarded-Encrypted: i=1; AJvYcCWBT8E9l6TsC66cDYOn3SFLb2qf/AWIvbCeoI9oPFPXZxmrx6Ppdg5RdLpi+za+i0VHvEIczwEnHQ==@lists.linux.dev X-Gm-Message-State: AOJu0YyAPdxOQPBaY3HiwJDu+woBsTp5UvAo/zwSLbU2eV5zSpOh5y3O eI2BTXKNRqNyVg06lbtCR2LAeY8SrxjNSOLYlmm1GFb2ZqFPGEDh X-Google-Smtp-Source: AGHT+IFe5P6BuiYtbffd1mimYFoXtDFoEUK324MarnzRvMXI0QJHbhnkpia1+tu9/eVZZvKy7OgAww== X-Received: by 2002:a17:90b:4b4a:b0:2e2:b211:a4da with SMTP id 98e67ed59e1d1-2e5616ec45bmr9060331a91.14.1729396966000; Sat, 19 Oct 2024 21:02:46 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02: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, willy@infradead.org, 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 v2 05/10] perf/core: Update min_heap_callbacks to use default builtin swap Date: Sun, 20 Oct 2024 12:01:55 +0800 Message-Id: <20241020040200.939973-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 After introducing the default builtin swap implementation, update the min_heap_callbacks to replace the swp function pointer with NULL. This change allows the min heap to directly utilize the builtin swap, simplifying the code. Signed-off-by: Kuan-Wei Chiu --- kernel/events/core.c | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) diff --git a/kernel/events/core.c b/kernel/events/core.c index cbf365e67f6e..0e9be5b323e4 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3778,18 +3778,11 @@ static bool perf_less_group_idx(const void *l, const void *r, void __always_unus return le->group_index < re->group_index; } -static void swap_ptr(void *l, void *r, void __always_unused *args) -{ - void **lp = l, **rp = r; - - swap(*lp, *rp); -} - DEFINE_MIN_HEAP(struct perf_event *, perf_event_min_heap); static const struct min_heap_callbacks perf_min_heap = { .less = perf_less_group_idx, - .swp = swap_ptr, + .swp = NULL, }; static void __heap_add(struct perf_event_min_heap *heap, struct perf_event *event) From patchwork Sun Oct 20 04:01:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842966 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) (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 5FB9D748F for ; Sun, 20 Oct 2024 04:02:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396974; cv=none; b=evUk/R80W17BC9iudEac5vBg8u6DZJ/oUXAFjYzW0Pt2EpT2RvXNfhRpvrzmIjYcQCngFR7pxI5/94ElHzZiIc4TY9jKAcvrEtUF5dXYzmcdsf4xPBgVakV1OwkaTVIvAvKgoe37vQV5xN9W2lC7iyyxtROkDRTjMlnUE18f3Nc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396974; c=relaxed/simple; bh=/9mUaFvmlKksdPlONLh36cpvswwCLSGpPrI0BGH0Huo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ghsx+P7nb+0Llhqb3emXJTQJos73+/MYq46FcJK7r+CwyFwljVvBndzflcbpM0QFfqQLJX0X4756jtYhuGBazzqfRsep4jpGurVjxE41uzvh7f/4PRSvwDWwr+XhlBIIpteoR553HqOa1cVUIo0Guvuo+4wo6Rmtr70fDqZMvS0= 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=aNqyangk; arc=none smtp.client-ip=209.85.216.54 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="aNqyangk" Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-2e2e23f2931so2799925a91.0 for ; Sat, 19 Oct 2024 21:02:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396972; x=1730001772; darn=lists.linux.dev; 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=rziSmC5tfzn2cnt/wqwyaZwuuHhuMcA3Csb1Fp91fpY=; b=aNqyangkWV5MOusHaczzhOxFAiXRsPs4I7fPU24+InuDfyG6rUJM8mv6FSquI4I24F Z9wbzEGlUXDTcJAYGDAzgeuqZWyXH6o6u7QJ5SVy2s+Gn2mMON1BjWuupcrHHCrGXBje +7GTnhdoCbnEJul5+/QILpLPuo5M4YwL1zHPLv3pBetsVJx14TArHZPmVWceRh+j8tTw 4R8fKk0vkKyGTMEWZSisAiqbh8uy5tzieTnYLaAxbi3SvdEJONtmoFJ40MfbFaqaz5VW df71Oba7e+h87ihT8dW05ch3Tw0mHlHA0LhoE5mzSgn19B0DFcfCobmTJHDdDzK/bPgu zh4g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396972; x=1730001772; 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=rziSmC5tfzn2cnt/wqwyaZwuuHhuMcA3Csb1Fp91fpY=; b=t9eebm2uTt8VacdrhQ4NImHwliXRddJNN5JlxMq9VyZwjq2ge071SiMUfdqgQ9UuYX T7PUBua795GP+72EY0JzCEldLJVrSJp7B3Jeay/Dl6vT9a441m3yv/dup1gYYmxGmyEo W0ZVwhdQ3PiWLs5VpG9juK7VB1eXwqN/EJ2XwKLSq7UPakAnTY7yPJoZTeW2HcDBNuUi imAU5r/6FBDdpGhM1tZPscYQk7T53pasydkKutcscY01SunJUPgCrGLwCcnA5389Wu2Y AmCOJsUKew2Y9+XS8CzbXCtUN944JV/J6NlErNMhA8RI1fqlYFW09k9aWlsyvv1OLXu3 WJ9Q== X-Forwarded-Encrypted: i=1; AJvYcCXmXVRAC/lbt7OntxD5YKtHL9+W5S5PGP+aSomAZU1cZGfAGybOO8IvwQqimoBf0Or5lbf/CSkH3w==@lists.linux.dev X-Gm-Message-State: AOJu0YylpNffjGubtdbVcXqwpzFiJJai3L49x6S+/c6u5MZ2TW5xJgKP V3oKkqO2LNbfrFA0IuAEVIgY6Z1DN7hnt5+eWD3LKEJwhnRz953d X-Google-Smtp-Source: AGHT+IHMW+qjGNk25MwSR4+vnQ0D8s1Tp6FfxwQfHJa9nSOWn+djBGN5YnBTiCdS6y5VPlsk0p2NZQ== X-Received: by 2002:a17:90b:3658:b0:2e2:cd6b:c6ca with SMTP id 98e67ed59e1d1-2e5618f0839mr8748941a91.25.1729396971559; Sat, 19 Oct 2024 21:02:51 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:51 -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, willy@infradead.org, 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 v2 06/10] dm vdo: Update min_heap_callbacks to use default builtin swap Date: Sun, 20 Oct 2024 12:01:56 +0800 Message-Id: <20241020040200.939973-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace the swp function pointer in the min_heap_callbacks of dm-vdo with NULL, allowing direct usage of the default builtin swap implementation. This modification simplifies the code and improves performance by removing unnecessary function indirection. Signed-off-by: Kuan-Wei Chiu --- drivers/md/dm-vdo/repair.c | 2 +- drivers/md/dm-vdo/slab-depot.c | 10 +--------- 2 files changed, 2 insertions(+), 10 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index ffff2c999518..8c006fb3afcf 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -166,7 +166,7 @@ static void swap_mappings(void *item1, void *item2, void __always_unused *args) static const struct min_heap_callbacks repair_min_heap = { .less = mapping_is_less_than, - .swp = swap_mappings, + .swp = NULL, }; static struct numbered_block_mapping *sort_next_heap_element(struct repair_completion *repair) diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 274f9ccd072f..ccf7b2eac131 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3301,17 +3301,9 @@ static bool slab_status_is_less_than(const void *item1, const void *item2, return info1->slab_number < info2->slab_number; } -static void swap_slab_statuses(void *item1, void *item2, void __always_unused *args) -{ - struct slab_status *info1 = item1; - struct slab_status *info2 = item2; - - swap(*info1, *info2); -} - static const struct min_heap_callbacks slab_status_min_heap = { .less = slab_status_is_less_than, - .swp = swap_slab_statuses, + .swp = NULL, }; /* Inform the slab actor that a action has finished on some slab; used by apply_to_slabs(). */ From patchwork Sun Oct 20 04:01:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842967 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) (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 9841013C816 for ; Sun, 20 Oct 2024 04:02:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396980; cv=none; b=nGs9HPp483xJGKyx99gX6Ni714MD7oZepPpVLlQLn7MCQNm9wPcFZtYfEtge+Dx52ST3zzCcXa1CY+W2i+LaYXXCsWJNnNgZetiJrM90h/X5nfkMpK3hGib1Sfp0doheVLNPYY8fMVybJP2cSFq/HBdhakxR7lCiNU+iktcvpLM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396980; c=relaxed/simple; bh=FXrcKA4kv0Y0H6AHaICGqhxwnnRf14RLEiJ/iEAwoxU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=aihw4sNpVXe5Spn0QO5+oskQnpo1Fj2RXQApEyqGa0VbXi9Hh8AM1ftDbwnWC+7wjgdIDZAXTHugOTukUs52tWHuXr5GJzTTDcZiU+B+9+4Z7itvLwv0LHVK4cM3Rj7NRQHp6fgfv85HGO/sgOOjnWOJHJwrB0W/w4UQ6VNwrN0= 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=dHtnLxHb; arc=none smtp.client-ip=209.85.216.51 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="dHtnLxHb" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-2e2e8c8915eso2781164a91.3 for ; Sat, 19 Oct 2024 21:02:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396977; x=1730001777; darn=lists.linux.dev; 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=gLYYPN6VMSbce5qBI6UYe5zetX0JUYbruyELXEOs2l4=; b=dHtnLxHb5L5adq+J78kbpVTehYLqaletEB9Cd2ySiHTKHQ2y+sfKEeIurvFf2Nj24H ta6npY4gWu1/qXAzsgvXeGuWzsRgAQgoNxsFeSvXCCbc3hzfr3MgL99mebxZplW48m9M GxcEw6QZNTO6LyKTbI2PgbqFPOwWfcHR9bhgmGnREYMjVUv0RG8Bdefwter3Gkn136hr eGyfUPv6eAuGSPHyzUzruw3LUGKBaT3hbeGoSc+b0w9SSGTuvfe2CVut601Psa2bvv7S vdlwkPwf35qif/aP+UCh67MjH6rWbsbL4RdzknvU4fkKqSc4RGLGQlCsEhYpfRBuPuLM epBg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396977; x=1730001777; 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=gLYYPN6VMSbce5qBI6UYe5zetX0JUYbruyELXEOs2l4=; b=SZttyQ7x7mN0C0lNHLVelYhZC7V6RvFj6kByWfzDy7weU4yC2R2x2i5RaBh71KGDzr JN31kMVCfMcP/wO8k2NEAvMCH/baXqolpbe9CnzQAFI3LZfKELzD7CIh9Euir4sbeFzh KSJXpkkqeA32zcGEUxTn9VFQWHGqep6m1Vb6XnMkvuul1bnpj5ncRCApmTaBHBVVMhco ac2RN/RHUUNJN6wN2VSPCy3aWdsACsEImvaAeYCghe+6u218bcsIM5kHxZ/A30iscJrC O7qaDDLqD2HPF8v6euqvd73xOYtogP4giZ4vnMxJpw32/OA1aVvXKpnXr9XQ3Kuxt2xt bPEg== X-Forwarded-Encrypted: i=1; AJvYcCW7lZcExPKuqtsUycWtMwUtyC7eDK2gWQZXref/CtVQ6hafpNRq6SEiFV7OxMwHTYG/p0El/59uBg==@lists.linux.dev X-Gm-Message-State: AOJu0YyeoQvnFoBU6dEDV+IRDiIUhWkvIUXGUyVwCBtN2O+9TiBNI6/Q f4uo+1slp/VB0jXAZypGbYrgaqi3rdZAj3dCOZJQy4GQ7YaO5y/S X-Google-Smtp-Source: AGHT+IGmB89UrsezcJFZU2nJR9oDRLe6wYCSOkA1vdtsM80cdAb4yFIlb3IMQvYcc+0FOIBAkWPSGw== X-Received: by 2002:a17:90b:4b0c:b0:2e2:c681:51ce with SMTP id 98e67ed59e1d1-2e5616c6659mr9349283a91.1.1729396976634; Sat, 19 Oct 2024 21:02:56 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.52 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:02:56 -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, willy@infradead.org, 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 v2 07/10] bcache: Update min_heap_callbacks to use default builtin swap Date: Sun, 20 Oct 2024 12:01:57 +0800 Message-Id: <20241020040200.939973-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace the swp function pointer in the min_heap_callbacks of bcache with NULL, allowing direct usage of the default builtin swap implementation. This modification simplifies the code and improves performance by removing unnecessary function indirection. Signed-off-by: Kuan-Wei Chiu --- drivers/md/bcache/alloc.c | 11 ++--------- drivers/md/bcache/bset.c | 14 +++----------- drivers/md/bcache/extents.c | 10 +--------- drivers/md/bcache/movinggc.c | 10 +--------- 4 files changed, 7 insertions(+), 38 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index da50f6661bae..8998e61efa40 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -189,23 +189,16 @@ static inline bool new_bucket_min_cmp(const void *l, const void *r, void *args) return new_bucket_prio(ca, *lhs) < new_bucket_prio(ca, *rhs); } -static inline void new_bucket_swap(void *l, void *r, void __always_unused *args) -{ - struct bucket **lhs = l, **rhs = r; - - swap(*lhs, *rhs); -} - static void invalidate_buckets_lru(struct cache *ca) { struct bucket *b; const struct min_heap_callbacks bucket_max_cmp_callback = { .less = new_bucket_max_cmp, - .swp = new_bucket_swap, + .swp = NULL, }; const struct min_heap_callbacks bucket_min_cmp_callback = { .less = new_bucket_min_cmp, - .swp = new_bucket_swap, + .swp = NULL, }; ca->heap.nr = 0; diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index bd97d8626887..68258a16e125 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -1093,14 +1093,6 @@ static inline bool new_btree_iter_cmp(const void *l, const void *r, void __alway return bkey_cmp(_l->k, _r->k) <= 0; } -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) -{ - struct btree_iter_set *_iter1 = iter1; - struct btree_iter_set *_iter2 = iter2; - - swap(*_iter1, *_iter2); -} - static inline bool btree_iter_end(struct btree_iter *iter) { return !iter->heap.nr; @@ -1111,7 +1103,7 @@ void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, { const struct min_heap_callbacks callbacks = { .less = new_btree_iter_cmp, - .swp = new_btree_iter_swap, + .swp = NULL, }; if (k != end) @@ -1157,7 +1149,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, struct bkey *ret = NULL; const struct min_heap_callbacks callbacks = { .less = cmp, - .swp = new_btree_iter_swap, + .swp = NULL, }; if (!btree_iter_end(iter)) { @@ -1231,7 +1223,7 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, : bch_ptr_invalid; const struct min_heap_callbacks callbacks = { .less = b->ops->sort_cmp, - .swp = new_btree_iter_swap, + .swp = NULL, }; /* Heapify the iterator, using our comparison function */ diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index a7221e5dbe81..4b84fda1530a 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -266,20 +266,12 @@ static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __always_ return !(c ? c > 0 : _l->k < _r->k); } -static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args) -{ - struct btree_iter_set *_iter1 = iter1; - struct btree_iter_set *_iter2 = iter2; - - swap(*_iter1, *_iter2); -} - static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { const struct min_heap_callbacks callbacks = { .less = new_bch_extent_sort_cmp, - .swp = new_btree_iter_swap, + .swp = NULL, }; while (iter->heap.nr > 1) { struct btree_iter_set *top = iter->heap.data, *i = top + 1; diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index 7f482729c56d..ef6abf33f926 100644 --- a/drivers/md/bcache/movinggc.c +++ b/drivers/md/bcache/movinggc.c @@ -190,14 +190,6 @@ static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *a return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); } -static void new_bucket_swap(void *l, void *r, void __always_unused *args) -{ - struct bucket **_l = l; - struct bucket **_r = r; - - swap(*_l, *_r); -} - static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; @@ -212,7 +204,7 @@ void bch_moving_gc(struct cache_set *c) unsigned long sectors_to_move, reserve_sectors; const struct min_heap_callbacks callbacks = { .less = new_bucket_cmp, - .swp = new_bucket_swap, + .swp = NULL, }; if (!c->copy_gc_enabled) From patchwork Sun Oct 20 04:01:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842968 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (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 7D68917B421 for ; Sun, 20 Oct 2024 04:03:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396984; cv=none; b=B6W13x+2GVIfbEAaJm789BUroxgPCvjs+Ctt1VlGIOTmb40/RniT2azaLvu+1yW2Bl1p62GuPcFI64UzKd21tGJvssxCc1r4CWY6ySYVgwK76fPOxKHpHRHE3H9XT6o1Kl1I/IZB/iXZXtMURzwDvL9aqif9FqQyPl9cTqtXMOQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396984; c=relaxed/simple; bh=n8isBE3MN50NKJqA8PJEYk21R5urgQClhVIMe0Dv/fw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HBxsipTaWboB19k9qk3yVYjwq2YZpEsdv12RZh3TjdMawXlKgYBc8s2+CopV4DueH9pdKbDcCI5wdXuohCOL2lsfE7nsf7CtQZOCm59DM1xBOp16ruYCacjx9qly/o3DWcD+VtfbokajJ41uTiYNUmmYN3/rNzQe5yjIwNFDNEA= 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=ZxA7xr6U; arc=none smtp.client-ip=209.85.216.48 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="ZxA7xr6U" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2e5a0177531so312166a91.2 for ; Sat, 19 Oct 2024 21:03:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396982; x=1730001782; darn=lists.linux.dev; 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=y2WpY9CipWcCt1Q+dpvLbF+kv/AA/FlDoXHDWd/V5GE=; b=ZxA7xr6UwdrQYxYk8j5l6kolmma8igsiRln5RvpKC+M17AKTSs+Dcmc9N9nPZeAmpc PTyWMT54rGnC5/rxU99bwjwPIMA5h89Tk/UxpBCKIR0DRZxFCUGtVXOR/8pCtVpIaR3I DrcpTGuFCAI+br/do61UyiwU0t48h2gcdlDKUrRAhgJ7nycd3Mcj6UJxZzZmGxIoWzGU f5EROKjUnsB8BK9h0ZTJA5o+mO7dSkmDFhgrmPlRUZO9Ffh2h8CNXzPX4a+8RCFl/Dj3 ZAUZm5LfnxhpjSDFcMT5uCB3VZ9zmgGdMMKV7MLd2m9C1o7muFuzuK7aZuF0F7WXlnF6 XUKQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396982; x=1730001782; 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=y2WpY9CipWcCt1Q+dpvLbF+kv/AA/FlDoXHDWd/V5GE=; b=ToZUAIsB8Y/ReLcqXFkiMFcYn7luhpyzruAIcsRgpQ5Yz1E2sjn+OAuV0lY88HfkU/ I0T8EJU712IWCuYAwmFLAv1LlKTECfBND9EsPujrkDxQfmtHIiT0BlasDqkGqOmNZcM3 9sk14pAgGPBlrC+tXgXPElZz/19+rK8I9BgNdNOaTRquRbBokCzEc2xGcHjHrqmU7svE GX89oUILoT6ucHtAR6gXpbvAuoHnf+C6nfaWs3d47tM1A0P9TakaCIucPQqfTzmL+z+D 5/EJH5EEf2AKtC++MQojnNwKUhHsMH9Yi0X1AFE6gOK8tv9N5AX20QlUoZdYsqCYy174 wA2w== X-Forwarded-Encrypted: i=1; AJvYcCWnIcHqEPzXfZGGeYayMSokTF95NuKrn5XYw3df94yoO20lSm0Xx4w2IMmrUSwYRA55v5gtGVxxtw==@lists.linux.dev X-Gm-Message-State: AOJu0Yw+DWOjQ5S7p8L7+M4pzYa4GIXBrhkxvIj4F5xhctp43xTIJpFR pLNPQTgTbJJZ1dpgeKRj68QLbk8wL5zr4mzj+nj990OEpGklR+Sc X-Google-Smtp-Source: AGHT+IH54s8bJnfmuveWObV3S7Rz7YBN+EE45vAptSs0RDb+pOmoExhRB5pOMmx0MvRYyg7vgzn+7w== X-Received: by 2002:a17:90b:3002:b0:2e2:e6bf:534b with SMTP id 98e67ed59e1d1-2e56172c054mr7219281a91.40.1729396981742; Sat, 19 Oct 2024 21:03:01 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.02.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:03:01 -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, willy@infradead.org, 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 v2 08/10] bcachefs: Clean up duplicate min_heap_callbacks declarations Date: Sun, 20 Oct 2024 12:01:58 +0800 Message-Id: <20241020040200.939973-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Refactor the bcachefs code to remove multiple redundant declarations of min_heap_callbacks, ensuring that each unique declaration appears only once. Link: https://lore.kernel.org/20241017095520.GV16066@noisy.programming.kicks-ass.net Suggested-by: Peter Zijlstra Signed-off-by: Kuan-Wei Chiu --- fs/bcachefs/clock.c | 19 +++++-------------- fs/bcachefs/ec.c | 19 +++++-------------- 2 files changed, 10 insertions(+), 28 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 1d6b691e8da6..1fcfcb5fd44f 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -22,13 +22,13 @@ static inline void io_timer_swp(void *l, void *r, void __always_unused *args) swap(*_l, *_r); } +static const struct min_heap_callbacks callbacks = { + .less = io_timer_cmp, + .swp = io_timer_swp, +}; + void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; - spin_lock(&clock->timer_lock); if (time_after_eq64((u64) atomic64_read(&clock->now), timer->expire)) { @@ -48,11 +48,6 @@ void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; - spin_lock(&clock->timer_lock); for (size_t i = 0; i < clock->timers.nr; i++) @@ -142,10 +137,6 @@ void bch2_kthread_io_clock_wait(struct io_clock *clock, static struct io_timer *get_expired_timer(struct io_clock *clock, u64 now) { struct io_timer *ret = NULL; - const struct min_heap_callbacks callbacks = { - .less = io_timer_cmp, - .swp = io_timer_swp, - }; if (clock->timers.nr && time_after_eq64(now, clock->timers.data[0]->expire)) { diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index e410cfe37b1a..c88f10d0606f 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -1057,6 +1057,11 @@ static inline void ec_stripes_heap_swap(void *l, void *r, void *h) ec_stripes_heap_set_backpointer(_h, j); } +static const struct min_heap_callbacks callbacks = { + .less = ec_stripes_heap_cmp, + .swp = ec_stripes_heap_swap, +}; + static void heap_verify_backpointer(struct bch_fs *c, size_t idx) { ec_stripes_heap *h = &c->ec_stripes_heap; @@ -1069,11 +1074,6 @@ static void heap_verify_backpointer(struct bch_fs *c, size_t idx) void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; - mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); @@ -1084,11 +1084,6 @@ void bch2_stripes_heap_del(struct bch_fs *c, void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; - mutex_lock(&c->ec_stripes_heap_lock); BUG_ON(min_heap_full(&c->ec_stripes_heap)); @@ -1107,10 +1102,6 @@ void bch2_stripes_heap_insert(struct bch_fs *c, void bch2_stripes_heap_update(struct bch_fs *c, struct stripe *m, size_t idx) { - const struct min_heap_callbacks callbacks = { - .less = ec_stripes_heap_cmp, - .swp = ec_stripes_heap_swap, - }; ec_stripes_heap *h = &c->ec_stripes_heap; bool do_deletes; size_t i; From patchwork Sun Oct 20 04:01:59 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842969 Received: from mail-pg1-f180.google.com (mail-pg1-f180.google.com [209.85.215.180]) (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 B5C5718EFED for ; Sun, 20 Oct 2024 04:03:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396989; cv=none; b=ByokQgVRhLfklPxWjEEkEupLUHWS73C68IvZdjBw2prhmu3NOJIW/M/9bD+24Ialn+7JbIK3+LGVJVEjgKqSp8d1ulETJS0nLFfRE1kEa5/tcDhewRHxW9i7lRMBub94or84HS2niV2tfjDXWccOO3Z1jBvjEJwZuOzGcQBdMNo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396989; c=relaxed/simple; bh=6iG+P5m+bTysqxHfMQjYbIP6SmuhjAt2CP2aCR2eqWk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=TcEj9rveGJVhOf4BhEZzzU94yqk/goOiZJskBtVpDaJkwBmH5hIQEK0wd1z3Bb3s1H3MDZ9UzGwWFcVM7ZQa3YEOM/+jafLIfsIeiklbXTvW1KRno1le1uEvw3A7rxwyCIQjUQVjv+u47QJFzQSRFcOcnHYgEfmP2UVeQnPTdh4= 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=KrFCzC94; arc=none smtp.client-ip=209.85.215.180 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="KrFCzC94" Received: by mail-pg1-f180.google.com with SMTP id 41be03b00d2f7-7ea7d509e61so1536531a12.1 for ; Sat, 19 Oct 2024 21:03:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396987; x=1730001787; darn=lists.linux.dev; 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=IpkOmRAz/DQoNyfUWCSgBoembbEPvsuuea47lWbGPwA=; b=KrFCzC94szIrUIatGCJctzQV14Cg//EtiWOVZldRADTWlGdJZSHjJUSlZcxuwMncre QLfv4/n4aZAky0kQhwIpcJjkibDNKoVmvyeqydYdeMKIIVUb+tmtnu7NJq/2kuLzG/hb lmsyf3h066dz2X+TbRNnWtcb/sG625kvj8YUeb5uS8DHFqs5UVMbVSNURYzUDWXcgh7I L+0rMiMt5PsXdfHb8DMtj4F8t763hwybICsdVD0YpbUQImyR3JpzjM4HJjg3TFUzVHpQ GK8lSBrtDMNJa4M1C1xQhRRHAmgvEFO/Ub0i5XZC/wrzVILD+pHTuhrLhuP6gUeJypHh J5CA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396987; x=1730001787; 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=IpkOmRAz/DQoNyfUWCSgBoembbEPvsuuea47lWbGPwA=; b=YdWz5NYGOqAPlqLLVjrLsN621IXTsEx2M9WGi+1mktwXCeGC79JoH2QQhPNnHBsm8Q 57SBIYZOT9dvqzU76KeLSd4BrUqch4Ml+fN6HFz+WPcc6z9Z5j2asRcT9/dosvwlVhmM umk5QSGJIPBtI5I0qKnbFrabTGb3S6Y/SAgbL08scCe4ra5rodv3TfXEbUcTa6luRbkt y9SIwxD0T/9j81coCL+/n4sLmpePKmbBFU3L/xaGwTkrdIncUIgmPwQBenii9aEUEm5E KYvq/VQQNAhaABjCGbP5agwBpp6sFx7hzi+TrRBCB+hPg61C1/YtFrIahpJw0Y2k7HwH AQQw== X-Forwarded-Encrypted: i=1; AJvYcCWElsf+aVQhfOj9z2kMx0AKRnymX/xPlAiVy3ODsSRsYrwrQ0T113EpUZm4cfXvnn5EX+hf0mNhcQ==@lists.linux.dev X-Gm-Message-State: AOJu0Yxj2OJUm85brwSisUbpGPeaBSG62C5d7q2CXyxz5OJqTuEj/NBV EsBO72Uivo4f+dJ3dyOV5Z/t+DaqCY15Zy90v9hdexP1SAiUQx4j X-Google-Smtp-Source: AGHT+IHJf9nXrjmUo/+hBd+ZogFXKHjqpeJ0l0sVyl8/8bUCcHMXr+vmkofLASs6jl6dEFOEoGT9gw== X-Received: by 2002:a17:90b:1a88:b0:2d8:dd14:79ed with SMTP id 98e67ed59e1d1-2e561900d44mr8457372a91.31.1729396986825; Sat, 19 Oct 2024 21:03:06 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.03.02 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:03:06 -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, willy@infradead.org, 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 v2 09/10] bcachefs: Update min_heap_callbacks to use default builtin swap Date: Sun, 20 Oct 2024 12:01:59 +0800 Message-Id: <20241020040200.939973-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace the swp function pointer in the min_heap_callbacks of bcachefs with NULL, allowing direct usage of the default builtin swap implementation. This modification simplifies the code and improves performance by removing unnecessary function indirection. Signed-off-by: Kuan-Wei Chiu --- fs/bcachefs/clock.c | 10 +--------- 1 file changed, 1 insertion(+), 9 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 1fcfcb5fd44f..1f8e035d7119 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -14,17 +14,9 @@ static inline bool io_timer_cmp(const void *l, const void *r, void __always_unus return (*_l)->expire < (*_r)->expire; } -static inline void io_timer_swp(void *l, void *r, void __always_unused *args) -{ - struct io_timer **_l = (struct io_timer **)l; - struct io_timer **_r = (struct io_timer **)r; - - swap(*_l, *_r); -} - static const struct min_heap_callbacks callbacks = { .less = io_timer_cmp, - .swp = io_timer_swp, + .swp = NULL, }; void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) From patchwork Sun Oct 20 04:02:00 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13842970 Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) (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 CEB0419259F for ; Sun, 20 Oct 2024 04:03:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396994; cv=none; b=aRc5BGEZYZMKDFmqXXdzZaTFPvFolWBzIRFMjeEJF2MysZNmbF9M77HUb82KIe9bbxpDOCm99A59ySPAvgT/CbrNJvzsO6V8mIU2roJsy6eRaiZgvl2C3RsUct44FgiIKMC6BfuMPbgrFBY5UnFBGGnBpBDDXWvswhcc7mIjFc4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1729396994; c=relaxed/simple; bh=P8v7bl0HUC8PgdWG90Udu7/e7VMI09byj7xPkrgmymQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HGDDTJud4Wtwl/4Bd19UOijk4Rju4pT91izAPFXooy9RRrJf0eQEfCCSQIcIbH4lnzFOrb5EtlXasX4OEZz+DjUdsNyUWURLr3ZB+CjGHnJN2gvriuT5hq5wxV43f8S6Dyh0sFbD/gd/V0k6HfuQ8RQ+o33u5qJVB1tZGpoT7tE= 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=fNu8rUYF; arc=none smtp.client-ip=209.85.216.41 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="fNu8rUYF" Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2e2bb1efe78so2283298a91.1 for ; Sat, 19 Oct 2024 21:03:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729396992; x=1730001792; darn=lists.linux.dev; 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=PfhCaNqjkwqDBbL7z5yBWj9nWr3RVKAleAhUoJxmWMY=; b=fNu8rUYFnITldijiu1L5Rm8/x7gwWX/Z+lFjlMJ+hGvR4D8AJVnMWYC771uqU5M1iP Zl/IF9CUdCRU7oEzFu+BK8LCPcfFD2JkBvZ/UjvXDUpuO1FnTBrGwOPZZCDyZP1oGECp JBtyRC1x630r3IC9ngwwYoTYULYLW4jnOwY3CS4NzZ8mTbLh2IMNn9B9E592B0qucXxE Ga0MGqLiJNyOL8A2+AlNpfycI6scIMdfj0kzs6skekmAI3ykfCSsCacQecIxuJNIN+e9 iO1uzdu4OMxYk6I/KnKusemZ5yk3RAW1krNAU+URRApCaVfyynPPFRFRn7s02cqz2k6V 0gjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729396992; x=1730001792; 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=PfhCaNqjkwqDBbL7z5yBWj9nWr3RVKAleAhUoJxmWMY=; b=VrzBVO+mP7sxkla+xgDF7lybySxxiYjlJQ5Zu9e9t+FdyAflFOLdT0r1oiY6JdLDG1 GzE6U+DXneKap6QsQ2fKrMO/9hW6W8dADqmZY3oFYtUA0P56b0N+qdOII/Buxo+OSA44 qkDOBpuxlSGlrZvWWSrO9ZEZ/B0k98/0D7BKgVvWMEufKQQWW4+eTVQJmG+e0/itFRtL Z81DbEAAeW2dzjmerK5kheiqD+ytYrnOKplAIgM1Nk0Zcm2lans9dSh/7HBpshiuDs69 uylOynKFqw6eaI0t0ltYgNyKOjCoQK6mU1yqFzB3PXIk9UXqJToMDsI96BYmeV42fZ7/ Z1jQ== X-Forwarded-Encrypted: i=1; AJvYcCXuH0fPcYxC2Hxf/t0B6yx2c2YPYhmma4lxcjKG/XGf6uohzexGPxgdrtg88UwrpBROoNvX/BGV6Q==@lists.linux.dev X-Gm-Message-State: AOJu0Yw6MSlj93Bwr87s1OaL1+4LO9aVSMQDjQwdRqmK/fdavtMjh9t/ L++B+nz6rHKn3lSX4wHBrmt06z/Hh9fXHwLLSP8tEN8w0xUMnPFl X-Google-Smtp-Source: AGHT+IGRS93cFoJkaSz24BSwCStwXbRxjwOMLShcvR70iLhHYFKXqmS8/9zXr3Tt016pUsTc/n4+5g== X-Received: by 2002:a17:90b:4c12:b0:2e3:bc3e:feef with SMTP id 98e67ed59e1d1-2e5644991c9mr10156817a91.3.1729396991894; Sat, 19 Oct 2024 21:03:11 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2e5ad3678d3sm633668a91.24.2024.10.19.21.03.07 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 19 Oct 2024 21:03:11 -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, willy@infradead.org, 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 v2 10/10] Documentation/core-api: Add min heap API introduction Date: Sun, 20 Oct 2024 12:02:00 +0800 Message-Id: <20241020040200.939973-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20241020040200.939973-1-visitorckw@gmail.com> References: <20241020040200.939973-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 --- Changes in v2: - Wrapped lines at 80 columns. - Updated Example Usage. - Added documentation for the ability to pass NULL to the swp in min_heap_callbacks to use the builtin swap. Documentation/core-api/index.rst | 1 + Documentation/core-api/min_heap.rst | 300 ++++++++++++++++++++++++++++ 2 files changed, 301 insertions(+) create mode 100644 Documentation/core-api/min_heap.rst diff --git a/Documentation/core-api/index.rst b/Documentation/core-api/index.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 Low level entry and exit ======================== diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/min_heap.rst new file mode 100644 index 000000000000..0c636c8b7aa5 --- /dev/null +++ b/Documentation/core-api/min_heap.rst @@ -0,0 +1,300 @@ +.. SPDX-License-Identifier: GPL-2.0 + +============ +Min Heap API +============ + +Introduction +============ + +The Min Heap API provides a set of functions and macros for managing min-heaps +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 the root. + +This document provides a guide to the Min Heap API, detailing how to define and +use min-heaps. Users should not directly call functions with **__min_heap_*()** +prefixes, but should instead use the provided macro wrappers. + +In addition to the standard version of the functions, the API also includes a +set of inline versions for performance-critical scenarios. These inline +functions have the 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**. The inline versions allow +custom comparison and swap functions to be called directly, rather than through +indirect function calls. This can significantly reduce overhead, especially +when CONFIG_MITIGATION_RETPOLINE is enabled, as indirect function calls become +more expensive. As with the non-inline versions, it is important to use the +macro wrappers for inline functions instead of directly calling the functions +themselves. + +Data Structures +=============== + +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-heap 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, _name, 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 (`data`). Optionally, you can specify a static array for preallocated +heap storage using **MIN_HEAP_PREALLOCATED**. + +Min Heap Callbacks +------------------ + +The **struct min_heap_callbacks** provides customization options for ordering +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 elements. +- **swp** is a function for swapping elements in the heap. If swp is set to + NULL, the default swap function will be used, which swaps the elements based on their size + +Macro Wrappers +============== + +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 abstract 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 = 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 heap, 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 = min_heap_push(heap, element, callbacks, args); + +- **heap**: A pointer to the min-heap into which the element should be inserted. +- **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 insertion +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 = min_heap_pop(heap, callbacks, args); + +- **heap**: A pointer to the min-heap from which to remove the smallest element. +- **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 returns +`true` if the element was successfully removed, or `false` if the heap is +empty. The operation is **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 specified +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 specified +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 = 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 +=============== + +- **min_heap_full(heap)**: Checks whether the heap is full. + Complexity: **O(1)**. + +.. code-block:: c + + bool full = 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 = 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 +============= + +An example usage of the min-heap API would involve defining a heap structure, +initializing it, and inserting and removing elements as needed. + +.. code-block:: c + + #include + + int my_less_function(const void *lhs, const void *rhs, void *args) { + return (*(int *)lhs < *(int *)rhs); + } + + struct min_heap_callbacks heap_cb = { + .less = my_less_function, /* Comparison function for heap order */ + .swp = NULL, /* Use default swap function */ + }; + + void example_usage(void) { + /* Pre-populate the buffer with elements */ + int buffer[5] = {5, 2, 8, 1, 3}; + /* Declare a min-heap */ + DEFINE_MIN_HEAP(int, my_heap); + + /* Initialize the heap with preallocated buffer and size */ + min_heap_init(&my_heap, buffer, 5); + + /* Build the heap using min_heapify_all */ + my_heap.nr = 5; /* Set the number of elements in the heap */ + min_heapify_all(&my_heap, &heap_cb, NULL); + + /* Peek at the top element (should be 1 in this case) */ + int *top = min_heap_peek(&my_heap); + pr_info("Top element: %d\n", *top); + + /* Pop the top element (1) and get the new top (2) */ + min_heap_pop(&my_heap, &heap_cb, NULL); + top = min_heap_peek(&my_heap); + pr_info("New top element: %d\n", *top); + + /* Insert a new element (0) and recheck the top */ + int new_element = 0; + min_heap_push(&my_heap, &new_element, &heap_cb, NULL); + top = min_heap_peek(&my_heap); + pr_info("Top element after insertion: %d\n", *top); + }