From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) (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 37D592868B8; Tue, 10 Jun 2025 21:55:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592546; cv=none; b=bSyJxSnq35lu9u7HQ+wDGAb+rdC7wU4vkL+pWzMb0FwJXSXMq8m+Vc+eDkmMVy0Gt8Oz5dmqQJDGJCPzPAMAH8NBPJFASs5sPWj2+qyF7+B+fJOApeyOiSL8En39uN/GGKSeH0ZYPfXK00WqT2wz97ry1GL+j71Fbg8EoB8Vaqs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592546; c=relaxed/simple; bh=xSFaRyhDOAam6TAkmDf6Ay5XVOGwTDA8ApGZTlJop40=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=oS12wUiPr7ywwAXbQrvpzma8qw09VseISC8hdrHAbgk9kv/Wu9Iy8WSgJanMrD/xRutUkW9WoYAektBjk93A4Z8JlggJiDXIVPjmX/bt1IMdHCATAiFHijp0wi7YzfPxBGO8yAG0gRBLxJceNbbumfgxkRK12EF+DMD/la48IlI= 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=SqbVU2WX; arc=none smtp.client-ip=209.85.210.171 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="SqbVU2WX" Received: by mail-pf1-f171.google.com with SMTP id d2e1a72fcca58-747e41d5469so6414324b3a.3; Tue, 10 Jun 2025 14:55:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592544; x=1750197344; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=WBfxcFZ5TJu43c65Lqw/lArQXlQRpXwLpryErfl271U=; b=SqbVU2WXCW/7zzG7rVXxgcK4BLmsTWa/SA7D5AcrnLgaIrFAuJpufexT0E+2/VQCD3 KUM8ZZwsEceRXNNcHabRvE27Y5xDS8DuU6br6s2hh8PQ8ZvbYyig+8yS3lIPSEjyQRgf effqcKdviFvMomlc7uBPNXHdJoxQs8QT7F66K+5icCIrSDpWE9cZjPb06YAqfCH/Mm2X bx73o3ZWg4NoinC7kIE0SNdHj75ncFgb6RAUvKU0M5GVywPkUBgW4qXicFGmaIQ3K8rw dtVLkegf2ldT5XYdvDl0SKLQPuz6rCHYgiwS1RXUPkMYLhQzNgPaBVvPG78zGBmk2K76 /+vw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592544; x=1750197344; 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=WBfxcFZ5TJu43c65Lqw/lArQXlQRpXwLpryErfl271U=; b=iSXHOSt2ehzK0nLhQyMKJQQzxb6wndECDQ1OYH+PvNwoX4G1zKwD2+z+4czVNB36j3 sN7VpKs/ewL3h5syRIIuvVVMfTDWUDjuWt+Kux69eicvMM6SpuCAXfG7DX13W69Z9Cod sbqLzH/SSvPo23zll9+SRM7QOT3GwvMZsnWb0f+3nFaDHFjShNxpLknXoT2eWPyDne9d ddT0LCxpmNwnJtYDbTsY8EXmy251L24PFSBI6+UrkBGo1UoIOSef6h/pKKI3VzSwIb9N 7EV1v2iPupdxzySJaPgDD68rw0IDf1bJB4gAeFZfWBD+unaHqR1AweMuCADZElbMS+Rz Pong== X-Forwarded-Encrypted: i=1; AJvYcCWYZ6N2wiPqSISQhyuHFOT3/9XG4vmuDoCP/IIOfnHWosdL/BXXrKGIhasSMnB6OYUk4UZnyLG5KjcB@vger.kernel.org, AJvYcCX7lRDeI7Fl0SNorA7HhrWwJtq+7U51OMNXM/nAYzkZcjZ1kO5P8OemkgroCyny5YnklvlxOPMHmtntMxk=@vger.kernel.org, AJvYcCXDV7XcDTTC/KNDDl7Mm4icPFAagveUrwGb8fFzmEq2jKfaiZ2kySpZz2tB638+P5FaeI2gmi1C@vger.kernel.org X-Gm-Message-State: AOJu0YxFZ/GFS8C+B8BaLpo1NLUusAus7axx/niy6MWg4Vi6uhGPG9G9 FpwFjTlVz4DeQlJ0bOzalhnctOUC37+44fOFgZEAMhWTI76cn73CDyqE X-Gm-Gg: ASbGncvsK8wPWWlvsAsuALn2xouLm3d2heGCxdntnQlk9yKxyWgUGZ/W2gm2sMRFwHF S1TewJVmRxgO4tp9pC0TXZzBWQv/4f2WpYNbXJgNfgHzCwgOppJG2ve+EWxR5HRDnGDBQdG/Ae9 dHkIN10JdD5mkJBtLIzg6PA2bqRIsMLk9ugiSbiHdTs1RR1CzAMRfAEu9m8nhgBUxRC30kZr+ZC 0Ct7MwNhjv8tkxHttStADaL1IyDIaGHI2wsBrUFM77drjMsmuQ92waxAxDzZ+gmtFr8K5tLrIeo DoF5tJaIxYaoKWVbaA08893Ob00a6SeztooHg4bhA51WjvbmuHHYBaWrIe/2SdqSzzxH1K76DZr WP8Zq4FLUtO3zuuIBj7uiHFKaleA= X-Google-Smtp-Source: AGHT+IHfwIigBjgibklgcJuguzrbWf6+UoX2nHOiZvQ6u6fCMZ4arEuQ36frRT0ygVJG9GPE/wUREg== X-Received: by 2002:a05:6a00:22cf:b0:736:a8db:93b4 with SMTP id d2e1a72fcca58-7486cb7f7c3mr1408485b3a.2.1749592544457; Tue, 10 Jun 2025 14:55:44 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:44 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 1/8] lib min_heap: Add equal-elements-aware sift_down variant Date: Wed, 11 Jun 2025 05:55:09 +0800 Message-Id: <20250610215516.1513296-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The existing min_heap_sift_down() uses the bottom-up heapify variant, which reduces the number of comparisons from ~2 * log2(n) to ~1 * log2(n) when all elements are distinct. However, in workloads where the heap contains many equal elements, this bottom-up variant can degenerate and perform up to 2 * log2(n) comparisons, while the traditional top-down variant needs only O(1) comparisons in such cases. To address this, introduce min_heap_sift_down_eqaware(), a top-down heapify variant optimized for scenarios with many equal elements. This variant avoids unnecessary comparisons and swaps when elements are already equal or in the correct position. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 51 ++++++++++++++++++++++++++++++++++++++++ lib/min_heap.c | 7 ++++++ 2 files changed, 58 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 79ddc0adbf2b..b0d603fe5379 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -292,6 +292,52 @@ void __min_heap_sift_down_inline(min_heap_char *heap, = size_t pos, size_t elem_si __min_heap_sift_down_inline(container_of(&(_heap)->nr, min_heap_char, nr)= , _pos, \ __minheap_obj_size(_heap), _func, _args) =20 +/* + * Sift the element at pos down the heap. + * + * Variants of heap functions using an equal-elements-aware sift_down. + * These may perform better when the heap contains many equal elements. + */ +static __always_inline +void __min_heap_sift_down_eqaware_inline(min_heap_char * heap, size_t pos,= size_t elem_size, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + void (*swp)(void *lhs, void *rhs, void *args) =3D func->swp; + /* pre-scale counters for performance */ + size_t a =3D pos * elem_size; + size_t b, c, smallest; + size_t n =3D heap->nr * elem_size; + + if (!swp) + swp =3D select_swap_func(data, elem_size); + + for (;;) { + b =3D 2 * a + elem_size; + c =3D b + elem_size; + smallest =3D a; + + if (b >=3D n) + break; + + if (func->less(data + b, data + smallest, args)) + smallest =3D b; + + if (c < n && func->less(data + c, data + smallest, args)) + smallest =3D c; + + if (smallest =3D=3D a) + break; + + do_swap(data + a, data + smallest, elem_size, swp, args); + a =3D smallest; + } +} + +#define min_heap_sift_down_eqaware_inline(_heap, _pos, _func, _args) \ + __min_heap_sift_down_inline(container_of(&(_heap)->nr, min_heap_char, nr)= , _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_inline(min_heap_char *heap, size_t elem_size, size= _t idx, @@ -433,6 +479,8 @@ 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, size_t pos, size_t elem_siz= e, const struct min_heap_callbacks *func, void *args); +void __min_heap_sift_down_eqaware(min_heap_char *heap, size_t 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, @@ -455,6 +503,9 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_si= ze, size_t idx, #define min_heap_sift_down(_heap, _pos, _func, _args) \ __min_heap_sift_down(container_of(&(_heap)->nr, min_heap_char, nr), _pos,= \ __minheap_obj_size(_heap), _func, _args) +#define min_heap_sift_down_eqaware(_heap, _pos, _func, _args) \ + __min_heap_sift_down_eqaware(container_of(&(_heap)->nr, min_heap_char, nr= ), _pos, \ + __minheap_obj_size(_heap), _func, _args) #define min_heap_sift_up(_heap, _idx, _func, _args) \ __min_heap_sift_up(container_of(&(_heap)->nr, min_heap_char, nr), \ __minheap_obj_size(_heap), _idx, _func, _args) diff --git a/lib/min_heap.c b/lib/min_heap.c index 96f01a4c5fb6..2225f40d0d7a 100644 --- a/lib/min_heap.c +++ b/lib/min_heap.c @@ -27,6 +27,13 @@ void __min_heap_sift_down(min_heap_char *heap, size_t po= s, size_t elem_size, } EXPORT_SYMBOL(__min_heap_sift_down); =20 +void __min_heap_sift_down_eqaware(min_heap_char *heap, size_t pos, size_t = elem_size, + const struct min_heap_callbacks *func, void *args) +{ + __min_heap_sift_down_eqaware_inline(heap, pos, elem_size, func, args); +} +EXPORT_SYMBOL(__min_heap_sift_down_eqaware); + void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, const struct min_heap_callbacks *func, void *args) { --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (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 581DD2882AA; Tue, 10 Jun 2025 21:55:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592549; cv=none; b=Hkuf9rDWEZNnj6YZKD9X5d1Vd82npeWC4QDY/LLvamEETUfilkjilcx7mzyKV0F72GVU+TTrBwYs1nyQC+d53SzsDPZjRGg5A/ROL+lQ4D9hiwKVLHI5zjjtjW5C/1wfBB8WNW+EQRAg0d577GPJmxNnamobPWAeos7+zgs64Ao= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592549; c=relaxed/simple; bh=CdFMvOh1D27GtMT3HsdTzWf6XCyndLLIlrXlv5JSftc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=JAR+45ESs1XxH19gjP7elbb0HqzjT2mCSq/HlrQv9KCF1NSpEUf/97C6nu+w84UDQXcrJnrtKSpb+I2bG+dvjHsh9azcqzJbM/Esndw3IYYIRtZAH/oDNRweY3B36jkjTsGB8t0Ec8yJcrt7KS7IUcZrbjB10EKGojk3AOKbD3Y= 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=iqXOimAH; arc=none smtp.client-ip=209.85.210.181 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="iqXOimAH" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-739b3fe7ce8so4694176b3a.0; Tue, 10 Jun 2025 14:55:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592547; x=1750197347; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=RYeWDvuYH1WzAk5I425o+mEgBxifUaXFRCTqxbugmfo=; b=iqXOimAHLptteW3Zt8Qmx6DyLZ50HtI8GhCIQ32GKr3N2XrUmdaF6//dOFhRmtppKE /8jPB+N4avklXzG6xC92nyREkLOCRBHZy0hQ9KUTKJ2qGAf/F+CjGyFDyd97Gcvy78rm FNa3z+gWZA/KJI+gXGriOzBNOi3S2UicbTfTeQIuPiqaSXlHlo78347h2aWZyQEswbkO 6I1V5dO9TXFtCY7ty5vyyfgjmyLeIzcyWaeWSEjb98IypiA/+uD2Z0uYnT2eZZdK9Fyh xP5CZMQ1dfVy/EvZJ/zXaoLdpUrxgIKitCEPKvnVBfuuwB+JlqxudOzWkawH3wRzjrW/ hMwA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592547; x=1750197347; 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=RYeWDvuYH1WzAk5I425o+mEgBxifUaXFRCTqxbugmfo=; b=WVZ/wps8Rp8Xj2OaQ2yDKQCba2cL484pEWBUK7YSqVbtRymeAeqVLwa/Ed/2ryhaeU a3HOwXunCSfkdPklbebTIBmaznfT+MnH26jvB271m6QBHDEVMlIs8y235bSw8HJcUtvK qJGlZ5IGiNm7A+A2ARdpSYYaAaWKdRhnv3E4212rfKt+1jz6xzqtViDcFlzmfw7NC8Cs 1iKXdJ4pGe5jvI/k2dwL0LOBn+bcjfdz4QD+VM92oDEu4YP9WTD+2pd3WkRTqldR2zhW Fbe6KqA+kJLd/Ew9K9lielez+ptgoAHucUEOUgS4OscnhHeCJt12P7pkPTQuoYFeFQR6 /tsg== X-Forwarded-Encrypted: i=1; AJvYcCUKh9yGjku0bmSFwGAb1x7Z8zUtijXpLoDWNnf+3INzK8Cl66W99OLb8uX4ceRpNKuK9mXTqty7md7I@vger.kernel.org, AJvYcCUO1bmdy1H0XTPvbZNdNUMHUbiqrxZDitOgvuwqBt+VhKZSkOdoh/iuarorUljIxkwCyeFVVnpF4YAKYp8=@vger.kernel.org, AJvYcCVzNvQwCvKyGyVd02h4G9uU8EXjQRnXPuHOSPy6VXJ1yZnfrx8Yhu0KRwstbh0jQXDNN/ylkHOa@vger.kernel.org X-Gm-Message-State: AOJu0YzPwq2lc1jZXxRn1B5GtKQdva0Q7aPgt8LuySzgp9aEYvnpGwFG z01in+ZBFyaKZKh/iV7zw7j5+MjvnW4Twmz6oftMrdirkZA+dmQLDSFJ X-Gm-Gg: ASbGnctnFNILlAlznhf88kIo5JhweotwPivpNCBwSagbN9KDbd1JtgW83RN7ayl6JE7 7ZvzeQrhOgcCSWJDGeMNCsSqmoTzOZtsohGyJ5hs8AtFmgl3P7VI1ve5FuhLDYbcHTs8QSNpJZr QPQNjRf0XV0X+GAW/9N8jWdSfAF+uxkcc0RL4N5NXMm4UcxJ9fiT+1JGPT4E3ruFn30os6paJJQ usD6QogtV6gLRlcjxQSu8m2cKUm1Jf4EOhfm83Ua1D5Xupj1ElwTjA7ownZyVsU5y5vG2PHFliA +z5bj0YHalEHVL9/BzLN15ZZuA235PpMvsuOXC4KhFYE4CS/dv7BoduRt+3neHDqPsT9cB59pZ5 9t81jcSn9E0QoF5a+ X-Google-Smtp-Source: AGHT+IHjIoIASCOJJKdd+gaGt1nQQ0c4Mj1lsywbLZDyvnJgWu+4KNEegczHkPEWFba1gcpeYAbhjA== X-Received: by 2002:a05:6a00:3d0a:b0:746:cc71:cc0d with SMTP id d2e1a72fcca58-7486cbbf67cmr1474821b3a.12.1749592547517; Tue, 10 Jun 2025 14:55:47 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:47 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 2/8] lib min_heap: Add typedef for sift_down function pointer Date: Wed, 11 Jun 2025 05:55:10 +0800 Message-Id: <20250610215516.1513296-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Several min-heap operations such as min_heapify_all(), min_heap_pop(), min_heap_pop_push(), and min_heap_del() use min_heap_sift_down() internally. With the addition of the equal-elements-aware variant min_heap_sift_down_eqaware(), these functions now need to choose between multiple sift_down implementations. Introduce a siftdown_fn_t typedef to represent the function pointer type for sift_down routines. This avoids repeating verbose function pointer declarations and simplifies code that dynamically selects the appropriate implementation based on heap characteristics. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 3 +++ 1 file changed, 3 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index b0d603fe5379..4cd8fd9db259 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -49,6 +49,9 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs, void *args); }; =20 +typedef void (*siftdown_fn_t)(min_heap_char *heap, size_t pos, size_t elem= _size, + const struct min_heap_callbacks *func, void *args); + /** * is_aligned - is this pointer & size okay for word-wide copying? * @base: pointer to data --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) (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 84040288C00; Tue, 10 Jun 2025 21:55:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592553; cv=none; b=Gl/YTgqxdXIwwq+ZY+mCqbKIKcZAyILYMAffCuo9k1L5e943wExLAydSnccTGMpgqGOcuhWqOMtcE+mX5ZQljFnIIrx5g5w/8FS5CMe9TrUBFma0lCdcKYmmDqk1js0k3xru8xLmi99D3xJUXkSrewHGpqIVMun9nMmBSgBTE7M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592553; c=relaxed/simple; bh=Y+UPitxuPnSQD3MhPw5JIcyU1vXDtlvyzvdhusxr2Fk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=AeGzn75/o3NUb6Ep7SkkDW++XNPyBnrsXIO5/DMFrmEvvrApESgJrJ/JIaQFkID5xgdVcIrw4ZJLg9vDkLt/98ka+tDxbQ3KqT4ppmcxYOaIjhQMUlmRQVI5OdhrBs9t/BEILdu5j9cTqbv8qc/TVBrM07tT6KDfzWlLlo+FBm0= 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=fxDzqCcd; arc=none smtp.client-ip=209.85.210.172 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="fxDzqCcd" Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-745fe311741so6536299b3a.0; Tue, 10 Jun 2025 14:55:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592551; x=1750197351; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=2TAQRQZLsTcJLvoXFgshBC4GHe/WMIKfuLkFw+VPiR0=; b=fxDzqCcduxN2i8DM/GGfM7lg0ZbZ5+e4h1/wK1ZZwmbNZpb0WJ9weQuXcxGnFxDVWB VTenomm1DmXY0CrjIpRr8QRJMVaCMJBwzj9wsDacbP+EiRKyTGjQk93JvsFaguH0678S rSQ/aWf2vVE66Oe8kwtNUY/eroMhEFhIWjbuC1gKAof9TCnLxvZ1Pk5NAWb+cWEhcXL5 WGRwCUv7jN3aCKKCwKpe+hixXvFe7qKHL0cwPVkPVQ98aVl7mh1qNvTa0SxufumqOLf0 W7erqP/X4Ik1W3cqNgKq+AnWSnzctxfpCBAS/gM85ic5mHNDCxMsDuqFfWE09l/6dQJq WLAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592551; x=1750197351; 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=2TAQRQZLsTcJLvoXFgshBC4GHe/WMIKfuLkFw+VPiR0=; b=PK+zVlgM29X4EGlQrYBtVAhn6MWVWIuOJ9pOZvMmkldjdvDk3iaLhs56KZXKhkfoKK 5wpUiEi/qiTJ4FGwhWSLit8Jy/g8q/bzJFFILsOZYvbYpkpP+oOpGDEjPWcfRwqPXF5Z +yODOwtKUhrKSAP3yX430cBrfga87i5eweMuIL854LkzsLj3yBGf8+Zy4RP5ZD7EnKDv 6U62i8ruU9ezKi+RUQFgJWYA4wMsn7TxbYxG4eLbWs/BGpv38/42kQIDnRobYJI95uXv yP3Z7s2ZVy3eguRjt1i3FpZK2KFv/nNwfaqntfYeutfA1Ww2D+HgPI8fP1H3mFqt1PjH KYog== X-Forwarded-Encrypted: i=1; AJvYcCV4hkyFYhH9xX2YNQjVEptk0sjXL0QsdPo6i4sOQveqNLZt2auZH6JHkIPqIpzY31sZuPp4tjkyCTpe@vger.kernel.org, AJvYcCWSRTmLJxCHtPDEm52v/2NToNVWMCvJIehhFGFYwJKYUxHrwyjdR/HZc+w76qkD1DC1L605rAiW@vger.kernel.org, AJvYcCXkM7jsq5pngaarNlPQXvIWp/9ugoZ9Rsr+UJ2tuWjqr2uNES+AH9GBmrwSEItqWThUYJAzrR4Afn4rrjU=@vger.kernel.org X-Gm-Message-State: AOJu0YxZJhmN0gcUSWaLSEYRevVPjr1I4HV/cVdXmXegqPcbSw7WADyW HcpLE3H7murWPMEvhTH513XbvsqZ0ROA0jDylfB0eMzmnczo8Q9hVg3r X-Gm-Gg: ASbGnctEHKGzvzxaaAh7wmZhZLUSCE60I3zFB+H2FJm1mcYC4qAsjPJX1o5ORVPTWWL f9Q7rDZ+qOWLVDZLhrEjHMY14Bz4qYdn9CGo4W+Vp0bklMn8XXtE4c5t/FBbnV0hbhhQOjmkOSt kJHeLfg/gmAFgM5L3MYMmFlS4azofRBjSst3OMScwfkegn4htBjUkl4xkbxM4lj/nuh0z3vkWKP qXzLP1E3Hm9zTJJar81hkrYAsBG22HGuwNMkzbu0vvZhRMRv13If4COnmtVDBf3oq20iCFxMrYS kpWsbqxQMCvmeYTysmUx5jKcEcS9YMsoLAEQRBCPo/rp5cD+uhZXH3osmbQRRTxAEDxbRzAPsrt 2LNI4C4ReX0jLW7Lr X-Google-Smtp-Source: AGHT+IFW06kBchqN/i7/VJIqNBJDn3AyaGauP4nINNREfEpW9XlqotbLEMye0niWS0kAsKlPX18+kA== X-Received: by 2002:a05:6a20:9146:b0:21f:4ecc:11b7 with SMTP id adf61e73a8af0-21f86752068mr1854118637.36.1749592550617; Tue, 10 Jun 2025 14:55:50 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:50 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 3/8] lib min_heap: add eqaware variant of min_heapify_all() Date: Wed, 11 Jun 2025 05:55:11 +0800 Message-Id: <20250610215516.1513296-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce min_heapify_all_eqaware() as a variant of min_heapify_all() that uses the equality-aware version of sift_down, which is implemented in a top-down manner. This top-down sift_down reduces the number of comparisons from O(log2(n)) to O(1) in cases where many elements have equal priority. It enables more efficient heap construction when the heap contains a large number of equal elements. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 19 ++++++++++++++----- lib/min_heap.c | 4 ++-- 2 files changed, 16 insertions(+), 7 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 4cd8fd9db259..c2f6e1450505 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -371,17 +371,23 @@ void __min_heap_sift_up_inline(min_heap_char *heap, s= ize_t elem_size, size_t idx /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all_inline(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { ssize_t i; + siftdown_fn_t sift_down =3D eqaware ? __min_heap_sift_down_eqaware_inline= : + __min_heap_sift_down_inline; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heap_sift_down_inline(heap, i, elem_size, func, args); + sift_down(heap, i, elem_size, func, args); } =20 #define min_heapify_all_inline(_heap, _func, _args) \ __min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) + +#define min_heapify_all_eqaware_inline(_heap, _func, _args) \ + __min_heapify_all_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, true) =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline @@ -487,7 +493,7 @@ void __min_heap_sift_down_eqaware(min_heap_char *heap, = size_t pos, size_t elem_s 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); + const struct min_heap_callbacks *func, void *args, bool eqaware); 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, @@ -514,7 +520,10 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_s= ize, size_t idx, __minheap_obj_size(_heap), _idx, _func, _args) #define min_heapify_all(_heap, _func, _args) \ __min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) +#define min_heapify_all_eqaware(_heap, _func, _args) \ + __min_heapify_all(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, true) #define min_heap_pop(_heap, _func, _args) \ __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \ __minheap_obj_size(_heap), _func, _args) diff --git a/lib/min_heap.c b/lib/min_heap.c index 2225f40d0d7a..a422cfaff196 100644 --- a/lib/min_heap.c +++ b/lib/min_heap.c @@ -42,9 +42,9 @@ void __min_heap_sift_up(min_heap_char *heap, size_t elem_= size, size_t idx, EXPORT_SYMBOL(__min_heap_sift_up); =20 void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { - __min_heapify_all_inline(heap, elem_size, func, args); + __min_heapify_all_inline(heap, elem_size, func, args, eqaware); } EXPORT_SYMBOL(__min_heapify_all); =20 --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7D643288C97; Tue, 10 Jun 2025 21:55:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592556; cv=none; b=giGiZ1C3hOe6IS0g+wLUHxGRcJu6qp6cvDJ+q+SxP32v6L7IjkfKBmNqRFDSTtQOg61eqaphYxalUtX6sHnW2weciPHBVRw73e0mhoxmymYH+yIiOu04gZkNYAokWDn342KilLD+hxtO4nJ5x8rZ4kEtt0mBMAubHgVErAc7VgQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592556; c=relaxed/simple; bh=fUeS6/Vyn/oNJQVYOs02gdftCzFaXcIHbY3SNFQncaM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ZsPbdq0OAobfD+9nnBLoISjVqwUF4nbOZCtI+BYpsdSGGItvAI3ws8Cs0bt1tRKTXPN4SZkSjpHZvTAuLSUyJmBd2zC/10gj2r1a7KJB9eGrwRYlzOLNszTapUQbajevWMYy9Eei/21bbdmTtETTMAN8S++F4sjDKDilN/M94oM= 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=dmjRq7R8; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dmjRq7R8" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-747fba9f962so287374b3a.0; Tue, 10 Jun 2025 14:55:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592554; x=1750197354; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=1G7eaRRqGjkGvebk6j0la3Mkm/63JnRkY3vM18k9jZI=; b=dmjRq7R86Q4vqFppa91ebNXCylNsXlE+67kBVfAiryeK+n3qxmU/Ani6Ej2sbM/S3X rHImkpd04nSARyXVskSq77phjmlfguzxith+FBGwCsHzPVt5iOH1wCHUavI6ol7GdD/q R9v4q6CMkhohvQO8GS1/BrEP3lWc19hRkWAfnuRNTMKm3FPNFcHkIFGTwKxdJcg0VHb4 JUp/B9TYmyTC6xzfeMbBlltoYzgmgXrCPhHCaP4Iz4ROa4Yg0uKvnzEzkd/q9w6T++Kp atAWldDR1v8xJ4R26UWC47ylEZ5Rws9a6PFo+DogNBdxvysv/br8PKdOm8Hl9+TA+8R+ zfUQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592554; x=1750197354; 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=1G7eaRRqGjkGvebk6j0la3Mkm/63JnRkY3vM18k9jZI=; b=nGPmg0C/9Q2ky/0rn57wZlzYgy4YDUDxqIWCzwTAwFoqUllpSEc0z6gMXMy1y+/iBn kwbBfxVfbWwqNT82eyNArAK18FB01tOGMbELz2aF24msYxuk1xBrfFjoIjhEE5AAH8yu S3YlKbpfuwdcyA2cs9tv4/dPcIfXJwq/c+o4EJtHBIfuF7X7Vh+TyRh7X7Cc3YDOv1OW SlEyJGa878VrjKc+/bMzcm3GUgpU9aOVlwQ3NPbAVgVo1tSUuhfczG9a09rSTPdZNqH7 S28m6BHJrettvnDzFbWG2a9+s+K2AWI/SS+w0O1q1wg4DXQHsB1BRFUQ/HoamaIAtTEa rdOw== X-Forwarded-Encrypted: i=1; AJvYcCVwnxJsTcJehJiWh6iDtbtpHsQn1+cufSUHdMrP11XEOeRBed4j/tXec0lRA55QACx44xPCq8aCn0xH@vger.kernel.org, AJvYcCWMj7QD4cKOFmAcJGHYagPYXAEVw4pOHscgmfinpxxY/Ll1SL3C+NIbnmKDLwxN/LWxT9l+/I/JP5nzDEY=@vger.kernel.org, AJvYcCXuiOfGm6AwWG0MK1ue9jku8a5Opf/FlWJHvhcRzu5cQzhggbLDQX1l0wsWrgqkqWsHA0XwMGOL@vger.kernel.org X-Gm-Message-State: AOJu0YzuXoMUD4RC74tu0vc/OsJwANEwOj/j2U0pC2t0wRzfxZB5FIGj jvasxW3R/QOd68M6k8LtGEl8qVDA6yQro5aE6m8poDRJQGLYUCoi0uAT X-Gm-Gg: ASbGncvwu08aW/Wu4um9IBbIPqcp8r3BaZTkEsDpCCRdpQ6ULlPJ1HQrkjDUwoDqbXl jMqsu/x8k45mj27xUOuHv8s2Duk5OCsEmn0KaI+akAw6nEFMv7M5hzDx9fsB80Gkx/VMudrMR8Z K1ajhL40TxhMWhNMf+zArYsYqEdOmYGwWs5uvQZm2W6ADCtcZ5dW1XvoQCEGmAtJPEgKVkDdlYu J49A67nam41GbGnrtRsKZj9AUqWxO7z5F+amTkka04Sy0V4Ksf6r25aD+atYv7CHItQ+y9Jh0Mb hOq+Ph29kRubrDWa6SjXNi4EYmAgc62b6Du6SMmqv/gpq9wGGtn9tMSI/LKnUQS+Lj+Z/238TJh 4Qs3v0Zv89qwH7HXD X-Google-Smtp-Source: AGHT+IHyIdD3/Aq06IxXb9ae11pBBcRrtkebaArhqrFX1tAmaLQXcbx/2DQWgBoMZ17+AqWIBY0ksQ== X-Received: by 2002:a05:6a20:3d8b:b0:215:d41d:9183 with SMTP id adf61e73a8af0-21f86ddf674mr1409019637.1.1749592553691; Tue, 10 Jun 2025 14:55:53 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:53 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 4/8] lib min_heap: add eqaware variant of min_heap_pop() Date: Wed, 11 Jun 2025 05:55:12 +0800 Message-Id: <20250610215516.1513296-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce min_heap_pop_eqaware() as a variant of min_heap_pop() that uses the equality-aware version of sift_down, which is implemented in a top-down manner. This top-down sift_down reduces the number of comparisons from O(log2(n)) to O(1) in cases where many elements have equal priority. It enables more efficient heap construction when the heap contains a large number of equal elements. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 19 ++++++++++++++----- lib/min_heap.c | 4 ++-- 2 files changed, 16 insertions(+), 7 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index c2f6e1450505..6c45d617b027 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -392,9 +392,11 @@ void __min_heapify_all_inline(min_heap_char *heap, siz= e_t elem_size, /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline bool __min_heap_pop_inline(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { void *data =3D heap->data; + siftdown_fn_t sift_down =3D eqaware ? __min_heap_sift_down_eqaware_inline= : + __min_heap_sift_down_inline; =20 if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) return false; @@ -402,14 +404,18 @@ bool __min_heap_pop_inline(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_inline(heap, 0, elem_size, func, args); + sift_down(heap, 0, elem_size, func, args); =20 return true; } =20 #define min_heap_pop_inline(_heap, _func, _args) \ __min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) + +#define min_heap_pop_eqaware_inline(_heap, _func, _args) \ + __min_heap_pop_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, true) =20 /* * Remove the minimum element and then push the given element. The @@ -495,7 +501,7 @@ void __min_heap_sift_up(min_heap_char *heap, size_t ele= m_size, size_t idx, void __min_heapify_all(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args, bool eqaware); bool __min_heap_pop(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args); + const struct min_heap_callbacks *func, void *args, bool eqaware); 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, @@ -526,7 +532,10 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_s= ize, size_t idx, __minheap_obj_size(_heap), _func, _args, true) #define min_heap_pop(_heap, _func, _args) \ __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) +#define min_heap_pop_eqaware(_heap, _func, _args) \ + __min_heap_pop(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _func, _args, true) #define min_heap_pop_push(_heap, _element, _func, _args) \ __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _eleme= nt, \ __minheap_obj_size(_heap), _func, _args) diff --git a/lib/min_heap.c b/lib/min_heap.c index a422cfaff196..dae3ed39421a 100644 --- a/lib/min_heap.c +++ b/lib/min_heap.c @@ -49,9 +49,9 @@ void __min_heapify_all(min_heap_char *heap, size_t elem_s= ize, EXPORT_SYMBOL(__min_heapify_all); =20 bool __min_heap_pop(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { - return __min_heap_pop_inline(heap, elem_size, func, args); + return __min_heap_pop_inline(heap, elem_size, func, args, eqaware); } EXPORT_SYMBOL(__min_heap_pop); =20 --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f177.google.com (mail-pf1-f177.google.com [209.85.210.177]) (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 65C6F28980E; Tue, 10 Jun 2025 21:55:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592559; cv=none; b=W4kH5U1F/aNrKQkNDMpM9qcVIlkeY8vgB9yclYAUT3wi/k+3NqvJzq4IJL2NGmu51QZM7BfzxOPvHHSPyU2o6gPaOBihyael3Yh3yYVthI7Hy9MjJ2LTzFqW6TycRHtwNuy9yth+w3lPYdn0vXSyZD8KQMKPpA45FyacI6zpZKU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592559; c=relaxed/simple; bh=hW2fZUEDQaFktP5Vtr+9Yl7P4kGi1EPcEwv3Y16UAYk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=LonWYLcIOObYhdjAS/d9e9y0Ot/JoM/7mpOhvxIbFiYS7e2MXsOWbuGmaubJzwjLWoLKzBcWc4conMcgtlqFXyiahmIpOfiigMpkL2BXE9s2Cc3p6CV1N0VVIJtGFTMsJoLMjHypjeEapwRUoW+H8b2sJWoYe05/kdBr/NjVOfo= 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=aJ/M21Q7; arc=none smtp.client-ip=209.85.210.177 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="aJ/M21Q7" Received: by mail-pf1-f177.google.com with SMTP id d2e1a72fcca58-742c73f82dfso4916705b3a.2; Tue, 10 Jun 2025 14:55:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592557; x=1750197357; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=BtakGyg52Wz02P8YR6DX5ZIEzU9byszu4duVnMtZc5w=; b=aJ/M21Q7pP0oR2neaCVA+cH1EvzT12Th7ipLQfN6Gtpe+SHn7a6imB1KxcStvjKohD 7zXeeTn1st3058RrIv7aOAnEqtyHj7+VUfWG0X12ZEjpeCcH3ar7BPTvkKU4PjaGrUhB kL22Vm1ih+8V/5nOHQzXLxIJQEC6KAip1I4ISaj9mpsYuExClScE86uUEtyg1ZR/sM6i OnY8SelMxoRHujHzKKtF9gJh7P53zh937SAzjlaB0F7z5omogOU7iqQhqKwg97O0PiyN gQDo/Sdj6kiQB7YaaiHP1hT1pKbxxwPx2HOmSQv0BA+IZRvPZQ9x6zeqVPVnBvdsWlVZ Ayqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592557; x=1750197357; 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=BtakGyg52Wz02P8YR6DX5ZIEzU9byszu4duVnMtZc5w=; b=r6Md0MVtZBERmUT8bC0PTspnJVwVJ9FimUg5JhLkBgk7m0D4VW5zEoB0Flc1w/rtWf jJzWykURSPkG48CaWfYbD46DZsPKb9bpwInq4LLJFlpPaE6nlWPc2rzqAfMaEsmT4Fly 4l5drtKxGKYG4dR+m7Nc0CL5pQA/y6Ln49BEPw1jUPiqSaqP2Zkcuj1b+HQmWP/GVK4C +t9cgJPMx73i4PmFiOZHdVQ9IM0pEUD/G8/fLYtg8rnaDTOz/bNKl7uuAhxt9mAq6jvE lSeS6JNaZ19klvG4iy/9Kv/JK5x8FMN7rs3GGJSQ1D7GpCtsQQO0aId3Z4ii3hIyasF2 tYSQ== X-Forwarded-Encrypted: i=1; AJvYcCWgZewhgasD8emEDjGTAiCiX8PgtRRUDNKP9H+TqJX8wRrlG7+or1LHuVTVImCfM7MU2OpkmXlx@vger.kernel.org, AJvYcCXhtYuir3gHwcOQL/sjIK5DwlbzbvEZ6myqy7lDxdt39XepjKmYh4FxnVBjW7zl1HH5tEDf668JGZiAucU=@vger.kernel.org, AJvYcCXhxnDQDcaPEPcwqHPikyXMj53MacKTGzQuTYDd0/8hD2hmNfEUcGmgKdPxi+xAmRU25Oh1VWKVSZNF@vger.kernel.org X-Gm-Message-State: AOJu0YwaByl9EVpcoi1dMGiU2WKptclfFh79eMsrW2ixtSyneG68YsWS OAkyHPn5cvFGuFvo5xGNgcCc51J3D2u6AQAobUuebgLUu+bzaOOv/yqN X-Gm-Gg: ASbGncvXSsWTRxldNNtua6pjZWAMirGE3TvOPau54nsrrC0RfZm/SSJy/oHWy3f3/Ad An8ZGn/Jj3H2Cda6X01RTn/Vg0me7VQSHiGk9MhgQETtSuoncVMcXdUYz7ELS8Op/idKfBNFBov Y82WXq4IWE5rkGDmUqgumW/N4iTMtjsl76fk1abL99ViGFJc6kxBv5MyCcHQhf6JDdc5xoNhZVD sKd4DAcH0DOfQshzLT/+HCxElkK+MVwMd2mycH8I30O/HSZboRGmipCKZU0hlyNYfbUfF+/ajzV qD3QD0LWG/Mg7aTGuqqOfWeumUUdYjJalbwaadL0F7pO1wQVmq2HA5O/5NDUp73prAN1I0bsGdf ZqVU6NxqPLkMjDX7sKte1SC4ri7k= X-Google-Smtp-Source: AGHT+IGQHld1qf30FkznFT4c/oq1R9BvUHCzEDFJUwbNqEzD2CIQqJSwKoOf8lub0QtTer7TZsWN2A== X-Received: by 2002:a05:6a20:3ca5:b0:218:bb70:bd23 with SMTP id adf61e73a8af0-21f86746e08mr1315798637.42.1749592556661; Tue, 10 Jun 2025 14:55:56 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:56 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 5/8] lib min_heap: add eqaware variant of min_heap_pop_push() Date: Wed, 11 Jun 2025 05:55:13 +0800 Message-Id: <20250610215516.1513296-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce min_heap_pop_push_eqaware() as a variant of min_heap_pop_push() that uses the equality-aware version of sift_down, which is implemented in a top-down manner. This top-down sift_down reduces the number of comparisons from O(log2(n)) to O(1) in cases where many elements have equal priority. It enables more efficient heap construction when the heap contains a large number of equal elements. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 20 +++++++++++++++----- lib/min_heap.c | 4 ++-- 2 files changed, 17 insertions(+), 7 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 6c45d617b027..d7bf8dd0f6b1 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -424,15 +424,22 @@ bool __min_heap_pop_inline(min_heap_char *heap, size_= t elem_size, */ static __always_inline 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) + const struct min_heap_callbacks *func, void *args, bool eqaware) { + siftdown_fn_t sift_down =3D eqaware ? __min_heap_sift_down_eqaware_inline= : + __min_heap_sift_down_inline; + memcpy(heap->data, element, elem_size); - __min_heap_sift_down_inline(heap, 0, elem_size, func, args); + sift_down(heap, 0, elem_size, func, args); } =20 #define min_heap_pop_push_inline(_heap, _element, _func, _args) \ __min_heap_pop_push_inline(container_of(&(_heap)->nr, min_heap_char, nr),= _element, \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) + +#define min_heap_pop_push_eqaware_inline(_heap, _element, _func, _args) \ + __min_heap_pop_push_inline(container_of(&(_heap)->nr, min_heap_char, nr),= _element, \ + __minheap_obj_size(_heap), _func, _args, true) =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline @@ -503,7 +510,7 @@ void __min_heapify_all(min_heap_char *heap, size_t elem= _size, bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args, bool eqaware); void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t = elem_size, - const struct min_heap_callbacks *func, void *args); + const struct min_heap_callbacks *func, void *args, bool eqaware); 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, @@ -538,7 +545,10 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_s= ize, size_t idx, __minheap_obj_size(_heap), _func, _args, true) #define min_heap_pop_push(_heap, _element, _func, _args) \ __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _eleme= nt, \ - __minheap_obj_size(_heap), _func, _args) + __minheap_obj_size(_heap), _func, _args, false) +#define min_heap_pop_push_eqaware(_heap, _element, _func, _args) \ + __min_heap_pop_push(container_of(&(_heap)->nr, min_heap_char, nr), _eleme= nt, \ + __minheap_obj_size(_heap), _func, _args, true) #define min_heap_push(_heap, _element, _func, _args) \ __min_heap_push(container_of(&(_heap)->nr, min_heap_char, nr), _element, \ __minheap_obj_size(_heap), _func, _args) diff --git a/lib/min_heap.c b/lib/min_heap.c index dae3ed39421a..a69d8b80d443 100644 --- a/lib/min_heap.c +++ b/lib/min_heap.c @@ -56,9 +56,9 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_size, EXPORT_SYMBOL(__min_heap_pop); =20 void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t = elem_size, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { - __min_heap_pop_push_inline(heap, element, elem_size, func, args); + __min_heap_pop_push_inline(heap, element, elem_size, func, args, eqaware); } EXPORT_SYMBOL(__min_heap_pop_push); =20 --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 56EDF289E0D; Tue, 10 Jun 2025 21:56:00 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592562; cv=none; b=VGnP0dAguGUluDjs6riEt+MDT2LUH+JCCpQZWs5OJSdGcmg1bkdDYRasacv06rXYl6/B06WUL0jsw+B/1JnR767dYZaxomLna/uMrf3K6kgPy5q+27Cobt5WuvZt+GMzGgp8lxrMjFZITk28gotEQlq7pfUy5nK3RCea/7UReFA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592562; c=relaxed/simple; bh=6FjiVADOpffTB4OKsgReq4RSKaWa9lCG0AbMrz33DJw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Qj9jiwXXbCyYktJlbR//UBUn/LuRH8sba+IDVAhAkFsfH3IarjHizx5g6kmheqUfSUL5Wb3S9ORFs4UEb9mgHfydZlglYt1ySVkzw0XxxRqiyMUH2TdoYGryiXHfPsVVE3z3Jyi/uwK6IXWsfuxA5TBsJql+sX2xcyFE8Gv9EVI= 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=iFdMN45S; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iFdMN45S" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-747fc7506d4so5645673b3a.0; Tue, 10 Jun 2025 14:56:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592560; x=1750197360; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=V6jmS0+ScxTBm8NjCp8+r15uCKiXE5fpNNx5LvrjUOY=; b=iFdMN45Sa7WRyBguyICP4UjFXQcGu+hToqlvju+LcaowlJ0tiNv3qpD7UZKjv3/21l nJZiZ2muB4r/1Cf88Lra+M+76XmMv3hyhlxBr41iM2Y+KTRG7jgzpJmwK2RDOBP7LacS +qcxMcrkRuJPsyClsLpV/8pPb126meaW5gEZgWyixA9K4cRyyf2/99m8dwr1b8+oXAvh 3bj6Cz2PRuZOodsMGRK9ML0kI0kC/uUlyAJYFdbyKPKQ2wP7SMVLVYVLkTVUbrv01lYq yLXnew+uZKqFpZcIWGCfYUTC4UzbCqgY1xJF5mc/jbsXTMYw4HIbsXyMazd9L4vQvEcY 53RQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592560; x=1750197360; 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=V6jmS0+ScxTBm8NjCp8+r15uCKiXE5fpNNx5LvrjUOY=; b=FUPnnIJdfcJht7+NoOJC2c39F3m/GYNVazBf9aUhvt9qtFjyF5l+9UG/g8+e0+gZeL v8M83oGujkvjSXyJug/4IcTLH1KLAO2ZV+oAC6Pz44YaeFii/QWNCnMECa3NqAE0ubL7 pCa5zjzzcla8KWd4mEpimNC3Q40JmAgnG1OwJt6ZHXn8+ypfOpSlGE8DN/PswWytImMM 8HQdXc1XZTGx8jzU51Uj43/xttKcWGN478rgg08Mc4LKlPdE1DXR7Sf59CVBRdYwvAx8 lWqP/qZhtAL3lKfz6quheDS4m09jFAIzLw2UJs6bbectQvhy3GvXa+FuTnfTnN8702Fd XOjg== X-Forwarded-Encrypted: i=1; AJvYcCUaebO6B8tfF8vgTBFox8XonWOZ7di7I7N21nU8rBKlAVCekaz5r4D/5wGvJXJL8JnTF8E4MOqDCCqD@vger.kernel.org, AJvYcCWAYw5S9aH2UwnPhecFprJukbrfDV5dFdSoM/DQb/5OrlI+cTd1QKkV84dZKhwz+S8GWZ0fO2ubv8OfQ3c=@vger.kernel.org, AJvYcCXFKLjAV0ouK8MaBQoj3/VaanotSOB7n2wjdE9WIi7vr21D5vqsQTntJdsmjMBELfJBPtLtA4MF@vger.kernel.org X-Gm-Message-State: AOJu0YyO9ITp1cgxR143/wM7ThqEj0itBmKmQ8dI3qA/9XMvj8o8gmGw x56oLbImoJQa1Ye9y1+VV4EOlMYjCs3Prs4H4djqCgLKIhMz9a7v7qyP X-Gm-Gg: ASbGncs42T1i/JVmpW/FwSSTSqJ9XE1zzXiChBuhHwCyu3e9p4nOJkLe4BigwvG4sRN H08OdaU5GlyQqPG+iprgeU30YD4YRnOV2fyDv5Ad6prMDFA+VAgICOUwbpRU96JoQJVdRxAKyp6 PN5jUn5wonBHQXG7h9zJ6n49dpNOhdyWMMe9Okg2hSzdNG2yf57pezxO+siRprZkaxCm02SRRX6 wLGFx15N3YjU9U0hLCkw+SWQPk5q35YVd5kdVOvVPY1okeg9sTlfxUs+2QCYHH/IxNUewyn8gjU HNLzfbLkq9siQYH0lBdJGKYClup50tbmHCOHPSmq64PkHodi64nZD2pYYjF+ZrAqIkHY1q3V0dk 1VGF62LSzNdlhU2qmbxOOh6lbE0g= X-Google-Smtp-Source: AGHT+IFEWtDIB4I39e5rga0i+J3zViT0j9OTc1015dCmQIyX4iRajsViaEtHKF0u5yu+QSDAX7Uhxw== X-Received: by 2002:a05:6a00:b91:b0:746:2a0b:3dc8 with SMTP id d2e1a72fcca58-7486ce65e9bmr1210787b3a.17.1749592559698; Tue, 10 Jun 2025 14:55:59 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.55.57 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:55:59 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 6/8] lib min_heap: add eqaware variant of min_heap_del() Date: Wed, 11 Jun 2025 05:55:14 +0800 Message-Id: <20250610215516.1513296-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Introduce min_heap_del_eqaware() as a variant of min_heap_del() that uses the equality-aware version of sift_down, which is implemented in a top-down manner. This top-down sift_down reduces the number of comparisons from O(log2(n)) to O(1) in cases where many elements have equal priority. It enables more efficient heap construction when the heap contains a large number of equal elements. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 19 ++++++++++++++----- lib/min_heap.c | 4 ++-- 2 files changed, 16 insertions(+), 7 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d7bf8dd0f6b1..f34df8dd2e17 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -470,10 +470,12 @@ bool __min_heap_push_inline(min_heap_char *heap, cons= t void *element, size_t ele /* Remove ith element from the heap, O(log2(nr)). */ static __always_inline bool __min_heap_del_inline(min_heap_char *heap, size_t elem_size, size_t i= dx, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { void *data =3D heap->data; void (*swp)(void *lhs, void *rhs, void *args) =3D func->swp; + siftdown_fn_t sift_down =3D eqaware ? __min_heap_sift_down_eqaware_inline= : + __min_heap_sift_down_inline; =20 if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) return false; @@ -487,14 +489,18 @@ bool __min_heap_del_inline(min_heap_char *heap, size_= t elem_size, size_t idx, return true; do_swap(data + (idx * elem_size), data + (heap->nr * elem_size), elem_siz= e, swp, args); __min_heap_sift_up_inline(heap, elem_size, idx, func, args); - __min_heap_sift_down_inline(heap, idx, elem_size, func, args); + sift_down(heap, idx, elem_size, func, args); =20 return true; } =20 #define min_heap_del_inline(_heap, _idx, _func, _args) \ __min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _idx, _func, _args) + __minheap_obj_size(_heap), _idx, _func, _args, false) + +#define min_heap_del_eqaware_inline(_heap, _idx, _func, _args) \ + __min_heap_del_inline(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, true) =20 void __min_heap_init(min_heap_char *heap, void *data, size_t size); void *__min_heap_peek(struct min_heap_char *heap); @@ -514,7 +520,7 @@ void __min_heap_pop_push(min_heap_char *heap, const voi= d *element, size_t elem_s 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); + const struct min_heap_callbacks *func, void *args, bool eqaware); =20 #define min_heap_init(_heap, _data, _size) \ __min_heap_init(container_of(&(_heap)->nr, min_heap_char, nr), _data, _si= ze) @@ -554,6 +560,9 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_si= ze, size_t idx, __minheap_obj_size(_heap), _func, _args) #define min_heap_del(_heap, _idx, _func, _args) \ __min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \ - __minheap_obj_size(_heap), _idx, _func, _args) + __minheap_obj_size(_heap), _idx, _func, _args, false) +#define min_heap_del_eqaware(_heap, _idx, _func, _args) \ + __min_heap_del(container_of(&(_heap)->nr, min_heap_char, nr), \ + __minheap_obj_size(_heap), _idx, _func, _args, true) =20 #endif /* _LINUX_MIN_HEAP_H */ diff --git a/lib/min_heap.c b/lib/min_heap.c index a69d8b80d443..50f224f174d5 100644 --- a/lib/min_heap.c +++ b/lib/min_heap.c @@ -70,8 +70,8 @@ bool __min_heap_push(min_heap_char *heap, const void *ele= ment, size_t elem_size, EXPORT_SYMBOL(__min_heap_push); =20 bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, - const struct min_heap_callbacks *func, void *args) + const struct min_heap_callbacks *func, void *args, bool eqaware) { - return __min_heap_del_inline(heap, elem_size, idx, func, args); + return __min_heap_del_inline(heap, elem_size, idx, func, args, eqaware); } EXPORT_SYMBOL(__min_heap_del); --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A05B528A1E7; Tue, 10 Jun 2025 21:56:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592565; cv=none; b=a1XoN5qfzuaAHO6L2I1CLoJo91NjIpDxQe0wMfzqUGW04UIFmBv/Y8pngpF1zoQcLdAR9nnzu0o8G51Re2WYtsHGAMUl5CbvwSmfplEK55ao4ceNNzuYEokTK8LTqCaIwtBnL41xZDd4TzB3ME9Wee/WV/u6VKrbTB4bWDSS0Xc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592565; c=relaxed/simple; bh=P4f9UyqY3XMRd7kyJ9Xc5lVXzggwFJyamBL2GuKNAuc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=NaSMrxk6p2cCIO1MXlYD0pPil+qyqDmv9P1VvVUSCBXaXxo6QrtGZEyoE8V3AbQn15PA6UCSpdc2Jubo2VEU6s2xHRy7sYsXqPY+8SQP7YyyPT8TnqC0ITutdJB6cWYl5FOjOtmg8APq8Z/rDRBeCpKABR4KmUiBFeG1KNyEiiU= 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=CAhvHlFl; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="CAhvHlFl" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-7481600130eso5867960b3a.3; Tue, 10 Jun 2025 14:56:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592563; x=1750197363; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fQiG2QS349Zbsw1Gl+byeM8NPhOPj/a1U4vce7IWCWA=; b=CAhvHlFlX08SB9iy+WeNLfyYwOIcuBXix2DzGTXCfltr7nl2E/cKTn4H8okSJ/jL4b xFf+ZDA93E0jBT7l9mFNqKdTMhdXFzo/uE2BuvE7d5ixbqTYC3nbjXRiuzFFUCvV7XGl VenjNZWZzrtAtqde305dThKJokzuWCWjeQXceABZpimjW8ACcmfnXWT3+c4OnTXVfwCJ RE/vfJ7G3SZkv+cihHnw87pL/csuXubmi82hOyscqTsvhAtIP/zDQrKh7buSiSQ5VPlh O31QMNRiApiM4bQ2JPy0txsyp0wdXkesYnCyp6a1UZhY/vKNzYW1JGxHtGHd6iEhlFTs 6Q9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592563; x=1750197363; 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=fQiG2QS349Zbsw1Gl+byeM8NPhOPj/a1U4vce7IWCWA=; b=tLrMoloBhiH0GZxBOsYALEzS5ZCeZjrJlUfpt8MPAIQ/3rcAvw9NwQu6xMh47zg0VE YdDeokCYis57rAf1IWRsBDpC0nAdzfZNVeMFl+I7xRivsmslNHc2/wR83OPU8JWajeCC zmpNbLoJc8Ostml4s3+W8dBUVt2vt24K0t01ZCsM7DMI1UU6g9peMra4o85WSAbCr53D qPPpqnVH0fB5IPXY30J4xMPNmGobgZh4O6jZv1vNgsPeriqkTs985He7+mLkXJw1Kll1 bwemNc1dYf82WQNJTSuCNYtIMeFAITA0PiEAhJ66S9wnoDX/vXsEsHFlGPMdq7h0digR 2oDA== X-Forwarded-Encrypted: i=1; AJvYcCURKXKr8LmB8YkrZO54BBfvGdVCaUwrEB08wBaswK/8mvJW/6pva/8D7Ym0a0uZ2jehWLqYmxZnWk7dBAQ=@vger.kernel.org, AJvYcCW4Odm5Z+/Clou8XeLHkbnSzlJD4B6bFk7cboBGthzZa+guJ9Tm5QZ+IXWfFynFD5fbiGOVrTtldXpg@vger.kernel.org, AJvYcCXjJF/xvh2aTKK41kJtnm861Z3spKSKg5+uQ+K7iHyGyuhu48R6rQW7Wd7OiUCdw88q3d6tcd4h@vger.kernel.org X-Gm-Message-State: AOJu0Yx0KOLm8CO0iaoutzoHLcBe9Gt7lLSQuv6Q7AJSXw7mVUnzKk7L zR2dUnfQ35Wzj3FemM/CCWZilR/Vmi1lpWWfWRGLdmJJ4FKV2raLjLOY X-Gm-Gg: ASbGncvVaOQ9xxV5r6i30pMtmGENLmZlCbbFZaSK/tRKXCXVMtMlz5HZ82FsvkCy3bY F4xB1nqCmIH37Vuf9lm4nfJBxlQEJ0hPE2PmdZp5vU5EkS0nUxOwHdI7wTqI1H86TbHIWFiKYN2 gir9B8Sr7sPvHom9BGBnTWJH2osmu3A98HzztBUT1Mdh5DGld/6wfvSdWN/ZRrnYvkJGomNSSt6 yAWpmy4WAVR5yHNM36aV38dqtgACS7kuHSVssVcA8LAIxdS2pooF7VYceyOeuRZMz0sjuYDClQr V6b8r1NojBFqnildX/McBv/uiq9J6RN99kRv7R5w4BUoxMS0ubXIHl3S0joKjvvof8ie6o+19xC fYv/hDoRutstbpgZ9 X-Google-Smtp-Source: AGHT+IGgnTbVwuFawaz+uk3VdqNa3Ux4CpdL5YEtdYtPi8oUtZ1UAFN4k98bv6I5ilgpOUIWb/NCXA== X-Received: by 2002:a05:6a00:848:b0:73e:598:7e5b with SMTP id d2e1a72fcca58-7486facfb03mr491064b3a.1.1749592562718; Tue, 10 Jun 2025 14:56:02 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.56.00 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:56:02 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 7/8] Documentation/core-api: min_heap: Document _eqaware variants of min-heap APIs Date: Wed, 11 Jun 2025 05:55:15 +0800 Message-Id: <20250610215516.1513296-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add documentation for equality-aware variants of min-heap maintenance functions, which use a top-down sift_down strategy. These variants, suffixed with _eqaware, reduce the number of comparisons to O(1) in workloads with many elements of equal priority and can be used as drop-in replacements for their standard counterparts. Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- Documentation/core-api/min_heap.rst | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/Documentation/core-api/min_heap.rst b/Documentation/core-api/m= in_heap.rst index 9f57766581df..012c82038b46 100644 --- a/Documentation/core-api/min_heap.rst +++ b/Documentation/core-api/min_heap.rst @@ -30,6 +30,26 @@ more expensive. As with the non-inline versions, it is i= mportant to use the macro wrappers for inline functions instead of directly calling the functi= ons themselves. =20 +Equality-Aware Heap Maintenance +------------------------------- + +In some workloads, a large number of elements in the heap may be equal und= er +the user-defined comparison function. For such cases, the standard +``min_heap_sift_down()`` implementation, which uses the bottom-up heapify +strategy, can be inefficient. While bottom-up heapify reduces the number of +comparisons by approximately 50% for randomly ordered data, it may perform= up +to :math:`2 \times \log_2(n)` comparisons in the presence of many equal +elements. + +To address this, equality-aware versions of heap maintenance APIs are prov= ided. +These versions use the traditional top-down heapify strategy, which perfor= ms +better - sometimes requiring only :math:`\mathcal{O}(1)` comparisons - when +many elements are equal. + +The equality-aware APIs are suffixed with ``_eqaware``, and serve as drop-= in +replacements for their standard counterparts when equal elements are expec= ted. + + Data Structures =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =20 --=20 2.34.1 From nobody Sat Oct 11 08:27:34 2025 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (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 695962874EA; Tue, 10 Jun 2025 21:56:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592567; cv=none; b=r6nNy0PzlJ0x8PURTbHblr4qBJ1VtVCiK1rKW8HNQLrsh+gH9cqVTfxZn8sMPh+bsW0cMy+T/dw9Wv/4ibmIJWQa4y2Llaj9rSpGqzm9tydx4M6vy5ENN56KR8fXAYuCuD0CuTodEXcZ5sLbuSVFdNFZAizF/AStsAKWcCaKDN0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1749592567; c=relaxed/simple; bh=BcO/N3oLniwVCzGot81EJud0xDOAiwYCU0xsTlvrqoI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Roev8hdIxnhG8Eoj0YAU0ZxLWlO4iT9CT+hv6cHjsczwmDcRtNEELjdWvElpy8MYlz2M5CtyrwDOtzFQQ/c4/oX4U3C1mYqkkwUC6K8v7kJfvJ9/qKALuM+zLDa2RQa/9DXj1ZV8vEKWSJO6IPhkz3LscMFfqtIi2UnAzVjAY6Q= 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=GtwohTrZ; arc=none smtp.client-ip=209.85.210.181 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="GtwohTrZ" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-7390d21bb1cso4910010b3a.2; Tue, 10 Jun 2025 14:56:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1749592566; x=1750197366; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Mh8dL2G7ps6auhPCbV2SxnoFMaxmQBWO6t4lRq5+ZGg=; b=GtwohTrZJEWHeNo8T4XyRbfdMjetNE+2tvnQIHG3Bn6WxGBKIL8+efmZM6R1jeIK5o oHOfp+gd0xMVbJsolR71hAizt8JyhL6NC4Kwq4oKVl2L/EMd7SKV3y9xvhJiHIvPHqUa HAGOegSq8BPFuuQy9rpyzSFdzkeKV/42Ho+a2RgVff2yr31Yk1Rs1KYu99fLrIij0wUX UNqoshrRGVXQ07YtL6SbIArDCe6Fp4ft4BMWbbMRvAkN2mZMvIQFX4H31UK1UAwpg+Vs M/Z2u8YdbZqhIfmYc4zYtuncD7cREb+ChCOhwaGhHqFc+AIKAHTkkl7rsbPVsQrNFFOu L07A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1749592566; x=1750197366; 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=Mh8dL2G7ps6auhPCbV2SxnoFMaxmQBWO6t4lRq5+ZGg=; b=DVyYe8vxro0zaGQZazQBX1bf48YaqSjQZCJtm0y4Uzw2o4QdLES9vCCyXcYyPMsAFT msRPHc1dcyHuDYOjNAdmqPtfPhGsOBAiY8cKC4574nsAY+KrDCpdRsI13+NDaes0XZAS T0tRIv2FuayORe1CxHBacKhPWlaE6x3GsqFMqyMp3KDoAzFb4CcX5Kzi+XbYIs+3gPxE F7kVMVb/AEvO5UMinEEPEQl2i18ZZ5DME16hc+oniYNrhiEOtMSjt5+lt1/DYtxoSEmZ MqV2P4fcYpL5eMhprBAmubq4QGkp/1xHS96m+X2o2qE9haQAOIMcnSCGhoNFVI9TI+II 72nA== X-Forwarded-Encrypted: i=1; AJvYcCVB36YQy0O/KpdPVLX/jOPTcIJ0SsBvtgnAXg92GIw/VUxC9CYEAAN4Hw8R9C5VhPlV9x4TI2W3@vger.kernel.org, AJvYcCVEHeQM41tN+ynmdPypglkL+Jgu+rY2LC//Dk9OzirpdiSuYCVU5XUHv/VlCeayE/kQ0LLdcnVoQe0X@vger.kernel.org, AJvYcCVL2CZ44aOeFgHSPXB8GKuWu2gmHoVWXJnwQ/rW0WxAW6Rwhh060RSpa0XXbnHgIUR8ZQDc6dGg6v9jntw=@vger.kernel.org X-Gm-Message-State: AOJu0Yyhdsdo+aKKTxPZoO85lreUpBFsoyzb3RAHvHUiL3WggNCKvOXN KKBoxFTN01BK1DXNjE8sojy9zq1YeYtbNgkrW7PSoj/i0LmksgUu54VX X-Gm-Gg: ASbGncvHtktUnI5YZD4BibN4psP175zRKY8kBnxLZJTjJsK+uKKX8Krv7r8ikj03mXW kzR3xo8PkRufNFQLfUjAxvsa1KT1VgATn7TCGmfqTf9GhnstoXTajyDNMZ6e+4pcjuwZppBUetJ jYrRCQTDM9QbTOL+j+DImlWZ/XzJuw5bppYeSDl0Al8Jr3Cu5PqEfVwPTx0uwzKOjnt2KPo3bBc Gf88FvdQJhPwNf1A/PQHYiy935pqIrIkirrUL5skQO8ZKD68VqZR6MOiq06GN5MWHCrJXmp46HY BVYqWt/j8MXNzblMeaZ2V3H+GJCT3Jj7HG0sLVQpNtVSP0pw/Kl08C6B8qZA0Hmx7BjTbqGnURW dmFMIy59akN5LHVeNzMhJIwASJzs= X-Google-Smtp-Source: AGHT+IF50qUKlnQbr9poW8unnzpE8c0mhNlT5avVy2a6dY7Fsb+ssIhW5QF+vzmXtbCwaGQl4JUDKw== X-Received: by 2002:a05:6a00:17a4:b0:736:b101:aed3 with SMTP id d2e1a72fcca58-7486cb44948mr1406040b3a.1.1749592565674; Tue, 10 Jun 2025 14:56:05 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-7482af3a165sm8173936b3a.11.2025.06.10.14.56.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 10 Jun 2025 14:56:05 -0700 (PDT) From: Kuan-Wei Chiu To: corbet@lwn.net, colyli@kernel.org, kent.overstreet@linux.dev, akpm@linux-foundation.org, robertpang@google.com Cc: linux-kernel@vger.kernel.org, linux-doc@vger.kernel.org, linux-bcache@vger.kernel.org, jserv@ccns.ncku.edu.tw, Kuan-Wei Chiu , stable@vger.kernel.org Subject: [PATCH 8/8] bcache: Fix the tail IO latency regression by using equality-aware min heap API Date: Wed, 11 Jun 2025 05:55:16 +0800 Message-Id: <20250610215516.1513296-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20250610215516.1513296-1-visitorckw@gmail.com> References: <20250610215516.1513296-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Commit 866898efbb25 ("bcache: remove heap-related macros and switch to generic min_heap") replaced the original top-down heap macros in bcache with the generic min heap library, which uses a bottom-up heapify strategy. However, in scenarios like invalidate_buckets_lru() - especially before the cache is fully populated - many buckets remain unfilled. This causes new_bucket_prio() to frequently return zero, leading to a high rate of equal comparisons. Bottom-up sift_down performs up to 2 * log2(n) comparisons in such cases, resulting in a performance regression. Switch to the _eqaware variants of the min heap API to restore the original top-down sift_down behavior, which requires only O(1) comparisons when many elements are equal. Also use the inline versions of the heap functions to avoid performance degradation introduced by commit 92a8b224b833 ("lib/min_heap: introduce non-inline versions of min heap API functions"), as invalidate_buckets_lru() is on a performance-critical hot path. Fixes: 866898efbb25 ("bcache: remove heap-related macros and switch to gene= ric min_heap") Fixes: 92a8b224b833 ("lib/min_heap: introduce non-inline versions of min he= ap API functions") Reported-by: Robert Pang Closes: https://lore.kernel.org/linux-bcache/CAJhEC06F_AtrPgw2-7CvCqZgeStgC= titbD-ryuPpXQA-JG5XXw@mail.gmail.com Cc: stable@vger.kernel.org # 6.11+ Signed-off-by: Kuan-Wei Chiu --- drivers/md/bcache/alloc.c | 15 ++++++++------- 1 file changed, 8 insertions(+), 7 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index 8998e61efa40..625c5c4eb962 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -207,15 +207,16 @@ static void invalidate_buckets_lru(struct cache *ca) if (!bch_can_invalidate_bucket(ca, b)) continue; =20 - if (!min_heap_full(&ca->heap)) - min_heap_push(&ca->heap, &b, &bucket_max_cmp_callback, ca); - else if (!new_bucket_max_cmp(&b, min_heap_peek(&ca->heap), ca)) { + if (!min_heap_full_inline(&ca->heap)) + min_heap_push_inline(&ca->heap, &b, &bucket_max_cmp_callback, ca); + else if (!new_bucket_max_cmp(&b, min_heap_peek_inline(&ca->heap), ca)) { ca->heap.data[0] =3D b; - min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca); + min_heap_sift_down_eqaware_inline(&ca->heap, 0, &bucket_max_cmp_callbac= k, + ca); } } =20 - min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca); + min_heapify_all_eqaware_inline(&ca->heap, &bucket_min_cmp_callback, ca); =20 while (!fifo_full(&ca->free_inc)) { if (!ca->heap.nr) { @@ -227,8 +228,8 @@ static void invalidate_buckets_lru(struct cache *ca) wake_up_gc(ca->set); return; } - b =3D min_heap_peek(&ca->heap)[0]; - min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca); + b =3D min_heap_peek_inline(&ca->heap)[0]; + min_heap_pop_eqaware_inline(&ca->heap, &bucket_min_cmp_callback, ca); =20 bch_invalidate_one_bucket(ca, b); } --=20 2.34.1