From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (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 6512E4A99C; Wed, 20 Mar 2024 14:54:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946472; cv=none; b=NryDspZJwiyC9t2o3KBcCJ6EkGO91cRkhz+T7NP5dVG1LvFTV0H6RWDKKbtDBIekwrC4O2+6lernKdOV+JMEE7hfZ3JebLGHge7zUykmD+zq9wYooeAkKJPkga3AThJ2imor9UCioT7XKsSJ8Tn8W2l0xZYaKDB0ckoUhkgalcM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946472; c=relaxed/simple; bh=4n3PXoq7ifTVripzMWtTfmPNaw+I1mTBtc6mbpGaWSs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=OFbBt3lVSShgh4uY/peqcnInKqbuYKSAFB3Q/l1qOJ3Nz9vbXsVo2/lI0zisvW4cRHkzi09YY/9mdMFLtRP4cZycSLaSWvdBEw8QXjPYod3yTy04g67aZf6Vo9H+878/g1OO+aMaabmCKtiS+cII9CMO3Ub5n1XegB0w5ufUwmc= 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=nT7bx/0H; arc=none smtp.client-ip=209.85.214.169 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="nT7bx/0H" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-1dde367a10aso4786155ad.0; Wed, 20 Mar 2024 07:54:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946470; x=1711551270; 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=QdmOvG2jwhJ+3WEh/LmFh3bdry4XeMTeGj+wdIbS7uw=; b=nT7bx/0HIuewf+hoy8NYoheKmQcgxKFem38IncPv+bKa26fIjvIP8T5TNX0Fj2bEx3 jbq71jn6Te/ArBEt+mB1rhgUgmRYwyf0LMY1Sh1FSs/KIYRplKNDcSzO5OzhApW8fsFG dxwzdm9fHsBeFODep6OZOzDUYxygKBRaqmMyXFFvmWQZkwFYSOpu1QO0nGtyq8w5Hk5J D6TvsEyz67+BHWsDeR1ZBM5TRgWHyFZHIePJ6RaODKGm19mJe0D3Abljwd2+PBlML1JE eeQpy9ZXXiGvj4iQj/KWU4XCoAnJEndmNldM3xTxJslstkl8K6Qd+4UNXtdRNUfRj1hm yAoQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946470; x=1711551270; 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=QdmOvG2jwhJ+3WEh/LmFh3bdry4XeMTeGj+wdIbS7uw=; b=FrgDFR7gwlui26jP+kS4tpLFAJFS59SC8S1xVwqO4yR7DS3CdjSJ/aoyy7FMoGWKf4 cAMjSk5MgmeR79Vu7NGtJWtYC1j9vyLm+8MtY7ZhCuEF2W2bQk50Ze9iZ9SnSqea8n11 8op6PakKyrP8tPfeEAbLz2mCdSjV1dgRt3JLgpIotgdw06sqEAPPyh6gvIALN+c68keQ 2eIpg1NBwDnr4khlM1krOdeLbuhhNv6S9RyFvOfKNcYdhf5zhG40miEB3YqLWmas/piT uvA9ab0Iw4r4V3xRr3ol4bfvp/vGUEi2PICL8ckefMRwA6k+zbCs72+22WnRSTuw3w8y puow== X-Forwarded-Encrypted: i=1; AJvYcCXulaw4wIgQ5loG5GGlTMwE1VvxJ0GoKfwUDlv1+a/sLzGxIQHg/8S0uw0x6hYX+ZKMuBB8JHYAIAWOMh6rlBOP0u2ewE/3B81kjp7jWk+/oyCdr0IFaTVWy/W+P0B1dmDNDE0Bzz6tRzXQabh7CIbpqSSGCc4pwPTrQG+yGR8rp7mH/eI2a2zG3n5ZEud+vJKSlRPQeDznjf5yUClz08jtumeJZMilBWjBe7wn X-Gm-Message-State: AOJu0YxbthJHIhv1QrMqvtda9rbcMmwRSBqfc+mpigVhEoNHSe5RJSIu YxuZaFeZnN+dWrrlKum5gEJGdWszZS7nRilmSJqfIRqFYRoSvaWn X-Google-Smtp-Source: AGHT+IEmpQfc+LEIDAEcR53CezqUQZscGcnrsPciIpHwU9PJHh1fb/sTR++utbSjALwem23U0uwdmw== X-Received: by 2002:a17:902:d2ca:b0:1df:fbc3:d130 with SMTP id n10-20020a170902d2ca00b001dffbc3d130mr1970515plc.1.1710946469727; Wed, 20 Mar 2024 07:54:29 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:29 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 01/15] perf/core: Fix several typos Date: Wed, 20 Mar 2024 22:54:03 +0800 Message-Id: <20240320145417.336208-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Replace 'artifically' with 'artificially'. Replace 'irrespecive' with 'irrespective'. Replace 'futher' with 'further'. Replace 'sufficent' with 'sufficient'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- kernel/events/core.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/kernel/events/core.c b/kernel/events/core.c index 724e6d7e128f..10ac2db83f14 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -534,7 +534,7 @@ void perf_sample_event_took(u64 sample_len_ns) __this_cpu_write(running_sample_length, running_len); =20 /* - * Note: this will be biased artifically low until we have + * Note: this will be biased artificially low until we have * seen NR_ACCUMULATED_SAMPLES. Doing it this way keeps us * from having to maintain a count. */ @@ -596,10 +596,10 @@ static inline u64 perf_event_clock(struct perf_event = *event) * * Event groups make things a little more complicated, but not terribly so= . The * rules for a group are that if the group leader is OFF the entire group = is - * OFF, irrespecive of what the group member states are. This results in + * OFF, irrespective of what the group member states are. This results in * __perf_effective_state(). * - * A futher ramification is that when a group leader flips between OFF and + * A further ramification is that when a group leader flips between OFF and * !OFF, we need to update all group member times. * * @@ -891,7 +891,7 @@ static int perf_cgroup_ensure_storage(struct perf_event= *event, int cpu, heap_size, ret =3D 0; =20 /* - * Allow storage to have sufficent space for an iterator for each + * Allow storage to have sufficient space for an iterator for each * possibly nested cgroup plus an iterator for events with no cgroup. */ for (heap_size =3D 1; css; css =3D css->parent) --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (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 138B051C50; Wed, 20 Mar 2024 14:54:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946476; cv=none; b=EDuV7L9fJna4VNPcPfHPdZjbfG/FRJsuDDA/ppIse6qYLDigy28uOM5AfEhyk/b/LDCFBQlEiwbUe1WziGcsCjSX30MsKyteIYZc2hCva016C1eBety5z6c7fsClTswQ2xBdjaB72y4nvhzz1hBqIMmMs3s9jJVXrvNxCbPqKYs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946476; c=relaxed/simple; bh=ccFsqSUbNmoZfjXj/UyIC9+OiMIUuYR/yY6H+xsWda4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=MCl4J82Lw+nuqDaRHdHk5Ys5PfMVL7O8/UrTnhnke5t+WluDFOjHpVPH8LLMEn1y3YZczjlkERjjuqL6hiPRgc8/DUxbLAQU9473Cio8BDn//A54TuMwqHBRNmkiYFb0ZeNoEnQD7ciADoWFQGHULgWtGDQGJngZghgHgiAXZrg= 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=GfAu5X43; arc=none smtp.client-ip=209.85.214.179 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="GfAu5X43" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1e0678265b3so617515ad.0; Wed, 20 Mar 2024 07:54:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946474; x=1711551274; 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=vCMluLf0OPIP5MvhSlBnewMLss6iSf4B08EHRoBbLMI=; b=GfAu5X43mJ7Y1Rl4AlGJdKu9keWS5qNXHfXwdZsd6jrUyqFRz62I78y8BgIkVEM3xL 4Ilf8tfIdSLx7wTtXxAa/IazxRNPMUAIMnoQnsiYLykxw2DG5poELK4VTRTnqC1KEVnJ hUh+Nhgvziy3ktM+D7KHG4Je0PfNjXUsKuj2wlngC7CdL2fDfIm0S5+8fSDhlWLmWOQQ xtaY05mLxaD5LVFaUFvGS6c5wNp2w/CmtjroIsha1UB6ea1TadG0kmvGloLYUIqmFA1D Av8WVw/eH2ajhSXJ82nOMsKkd4OeYqPdms+ZQO+XE6KGPMcuM0YLxGtkULFVA/Bj4Rod sKJA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946474; x=1711551274; 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=vCMluLf0OPIP5MvhSlBnewMLss6iSf4B08EHRoBbLMI=; b=Ef+yhBE31ePjF9l2Ur0m723jPoB5+UV6mwTDvrCW9pPCBy6kdIenOT4qpi425ScD1g scBItUNSH9uei0wGD4vE7IGcQZu0PyHZVLBgcFzoGboYMLxInAmOIdKlbFPa17InS5lO BSLKjNPworz4vYDV3wOXh+KhKoIATJLbzEkBip6Wsn4/QfnGD34+FaGB2yz9L/Gyx9QI J6iINV2cilmfJ1+VHVZ45dw9n/gl7ijNAl7TZn6sZCw+2u/QV0+vcg4YG5Py6+PFGdK9 b9nc5cnmoHIObGdmilJR8XWRq3vLqO8U4z7p7LYIBppCUIvmd2n3iCbPeiuLDEkQV0Ox hBdA== X-Forwarded-Encrypted: i=1; AJvYcCW9k2AAfoMPvFwp486GcktfpjV4qFLoJqyegfqMejs1gRq2QHHTtP9zQ0UEogdCnSLKcE5gReSlFG+sDAiZ8EeZLwYVYeupiZ+30JIp3u3qmmFjj0ZENprXzBOaBm8Q+JYI7QjemQRpE1X1NHUWBgZV+aBuFCRtBrntpR/0jY2EHNbxsQ7B1ciEi6djpsmlb3QAKmiK9gC2GSmaGY4wB9wAWsbfoSOFcSmR4jhk X-Gm-Message-State: AOJu0Yzs2+os9HGvAcUzviFJ16Fhnk37p+TeGiufLgMGbwT3rA0Xt5jr vWSe3qF0rNHwpyj2hHMPBN+ZOHLPC/ARbiKOfOFQXeDH4zo3kW+jeJE+501l67w3tQ== X-Google-Smtp-Source: AGHT+IEnN4HYZbE2rHcsFmRm8DkhdOasT2m/ZrfFc02i9m2gwbsINOw3gtS3SpqFPr7j1X9xPow9nw== X-Received: by 2002:a17:902:ce91:b0:1dc:df03:ad86 with SMTP id f17-20020a170902ce9100b001dcdf03ad86mr20347085plg.2.1710946474388; Wed, 20 Mar 2024 07:54:34 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:33 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 02/15] bcache: Fix typo Date: Wed, 20 Mar 2024 22:54:04 +0800 Message-Id: <20240320145417.336208-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/bcache/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c index ae380bc3992e..410d8cb49e50 100644 --- a/drivers/md/bcache/util.c +++ b/drivers/md/bcache/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pg1-f181.google.com (mail-pg1-f181.google.com [209.85.215.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 723AC1799B; Wed, 20 Mar 2024 14:54:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946480; cv=none; b=GYjnIgBaYu1PyrVuowfvFK/aJii3frN+QE6kUQj2qWlFKExhGssdZRlyxvIqL0rarCyHwS1M4X89tr52voG8Yiw9VL7UHCUL4mWxQvhMMDfecEAC94qTUS6T7RJwW4ijI9UviJkmIruko1jqqwPZGnCIVQMYCKIdZ9soIc0r4Fg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946480; c=relaxed/simple; bh=06vCmwEx1RrMDZDf+vtsHJ5OiX/iBIhb0hcMuWL3G6A=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GLrUf4N8+rwS67ASZtsFMak3ugVFPrpFfVViENizl+SHFxrgPjHJYmTZfg5oR8oqE2oJyyvwxCdo6opRrteYCmNZO7c/y1PYxWT4E8rJbVJwuX7yqqRqTF4tCnq+v45635vOKNfkQy0N7AcclKRKBooxXRgMAHhNagaRx1zblbE= 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=man5qzQT; arc=none smtp.client-ip=209.85.215.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="man5qzQT" Received: by mail-pg1-f181.google.com with SMTP id 41be03b00d2f7-55b5a37acb6so1194119a12.0; Wed, 20 Mar 2024 07:54:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946479; x=1711551279; 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=NTsQEVNVJaaM77/A8IxlTDaKS3O7Y7L1hXdgoCCnWBw=; b=man5qzQTvQ25D7dJ1BedJgaHEbFheCltWsrw/Td8C+Yc1m/4SF/Hy7cJ/Up/pJwqA/ PAuBUyvUqN/4SovDVejsEN7PraRALA4Vj7dqhTJysLSBmV0iC/ZFT5kt+RsjfsqUz4Sr yrV7W7tZk1e9bCnnEn/1L+Uy972JV3pEX5SFXbJbLUvMiTSyMzJ2AkCfvIj0fGnAuMh6 O6Z5aXVXy8o8ot+X7QL0xVk5YlUGPfkcSbLor41SVunkl+lfa0TXcP4gUbcPBCReT0Qp g7ZGHYoa5cQqTpeisALsNvHOSyjEdJj0QrEDZ3eiiZmwMdzndL0n585jRYsEj1U3L4VJ dM/w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946479; x=1711551279; 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=NTsQEVNVJaaM77/A8IxlTDaKS3O7Y7L1hXdgoCCnWBw=; b=uzEg+YDKhXO6qYjYcGw8o1bkxsWAGYLpurTjvXNbL7wlv3Znkcn7NyG/eo5fHomDhJ +7FjXedoIs8EChyR80iEh6SemrUKR9bylXvPQhpzurKB0TG5+oV+nppN56/xlmYjarDF 7W1dY7S3zqt0GbKD1qDQOXHzY71zIRXyGG7AYEwR6xbrdhNUhv1XURrTE8ooAxzB+OvU iCLMdkUjx95aZnDBQQRCnK3ObLq2E67CHvOhZvY3nJr6OqOaF9MEo3ES5G6NgJyb6RkW c1qfSBO+mHrI6m9bDs63zNJf5vSFcjfkNwtgEop0xQyCmBOvb/qg1r/QeS5Xse+o6h0m OCRw== X-Forwarded-Encrypted: i=1; AJvYcCVzYmawAxymVo/ejw4fM7nRAMShEdLnk7ElMV542LBeQFJqkfRyGb/a/zWj84g5+9oXVPh/m9Vj34w6IvkM+8lh6YiycRXubIRsWMd/YvI7xRwNj307IqWkeQKh2lLvrqYFcYr3y6jUYKCow/RzV4ydCalPq3tOJoyTutc3xPPPc9BoqZoC59sg4JO6kruTWBC3p/TSv2gNDcq67nSecprPXpx12EQ2/1DIYNho X-Gm-Message-State: AOJu0YwvBBZmjAB3YY1tJtrYfG5KSHhj1eZxOWBJy20xazfnR5jd1GCR 2+hbHyfHZBo4Y0MZ8aBCHmFNvjfxAfN7lUle2NcyHKb0Uv4uxcJt X-Google-Smtp-Source: AGHT+IGB07JOeLXyWGxhruoog8ATzipnYUw/ZWM4f99QwxnPadWqwP8bL4PFsFnlu/KaSWs0YM/T5Q== X-Received: by 2002:a17:903:2290:b0:1dd:7350:29f6 with SMTP id b16-20020a170903229000b001dd735029f6mr1956561plh.3.1710946478818; Wed, 20 Mar 2024 07:54:38 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:38 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 03/15] bcachefs: Fix typo Date: Wed, 20 Mar 2024 22:54:05 +0800 Message-Id: <20240320145417.336208-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- fs/bcachefs/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 216fadf16928..f5a16ad65424 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) (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 7DC5654BE8; Wed, 20 Mar 2024 14:54:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946487; cv=none; b=oQ4BlFxJnIKT9toRGqXOTJ3HmZw9iDXHqq01Wnyhil3LQbQB6eysjr9Pa7BCrFgLmdHM9s3hQ452jqB/ensxbjN5qvjsYzrWgA51f2gaP/5lgZecBOn/vVK5Zj1iDtyLYNh+5/x25ljlFthER19hk9c7U8UqsArTjkKXcWKGQc8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946487; c=relaxed/simple; bh=JaNYkoxO7r1B7Zx5LUOW9tQ9euz0Qs5qGwUUQSB2JLY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=I4jc2UI7lHCYZkYFejQRx1JjMc8xJc6Gb8WxS1o6IDHqOmGlChTcEaEu/PorQiFLG4Cmp8fQO0tQiVaiKJpiFPZj3VfCYvPOwwToaevcKpFZagwVeRm0/vTVAWk7KdyZYbTN6k93uO7oo7AxO4TYwIHs1LAwfjI0NVKyQx+mxW8= 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=kLCibePe; arc=none smtp.client-ip=209.85.214.173 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="kLCibePe" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1e0678265b3so617875ad.0; Wed, 20 Mar 2024 07:54:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946484; x=1711551284; 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=HBm65YX/b6ZbML2YrG4Mac39XWOyxvJJGteRmERwfdo=; b=kLCibePe6LiVI5BS8jXzQm8rPQhjcJo6NlLxZCfYjDMGdwDSg7+nMQbgaBdgPbAao1 cYB8bY3ZJl1CO3rGOJlG39vNKLyP/0/QtZ+/qOoIbpdGMg3YtUVFJiZ4uPpWQihsey/s oHMREZt/4leCtoWx7C5wxaaMEGt30CSi4a2T7uVXH17UGLX6GkKCq6JR9HOpT2ahNMxq K4oUVobcvXtTTje8eznz0XMATuFHnIka6aiwX9nkcPPvI1xBWKYLqZacGU+5d1mQqudU bsO6p6joHmDJ7a//dsug68Y4BVLTx3h91Lw6Qj4jnkIO5i4CfVCOm4pfFnipnSdl75Oy M4dQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946484; x=1711551284; 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=HBm65YX/b6ZbML2YrG4Mac39XWOyxvJJGteRmERwfdo=; b=QAykyKLgeLcEUFhx5Kxj2CwEKAwWTvzSo5ZsH8Ly/f31SlLim7RZ/kAvEJi4qhAp6r NeXlulzNSlI9ZfjSBqsbBwIZVS+LwVj9Wdqvxj+btnyeiiPA+7PanxxBV0ljLZ7jQCCl /LvKNDn5YpZ51wnSzrjp11zzCXR2+IjuyCb6sjdDo7Ocl74zsiSsaHmAYtItPTqltk/W s+h5mCaGAgeia2vC0i1wqf6/4qtzb9jeHwsCX7LSwRQ/n3BqBZYMqmqsGdMrOBN/BJst 3EGHUZxVHzZfxzkHgH8XQtfLO7wp8dK5ZyytELahvgf/YqVliiu0qpUlhITTL6nPDMrQ KB1w== X-Forwarded-Encrypted: i=1; AJvYcCVDbRYejP6Dcggq8BmduTyVfOV1Za5Dit9XGmRsGo+M3qw9uK7GI8puPDwGUKHLRyg9zhaW7IjPJoyC/pl7jzDIaoZDLrbPXNVqZ2Md+TMfVyYEQllKf41rt87BVsmP9cFlJLeTxDPnuDbGmfghiQil37F/9wG5eulVpViZ67H39A/8pgk2VwOu8jblFqzGHSFu9KRyBQhEJQ4+d3gSgXFRAFf/VWPeLcyAxJSx X-Gm-Message-State: AOJu0Yy/w6JkrZH3QFk5CHZtkQHLayt7cFc3qXAVhNez+YOY2aM+OhWp E9CzwETu0b/B043YU5o6ryUqdNyrVIColYScMmBFS4gTtaD1VYVK X-Google-Smtp-Source: AGHT+IF2ugLrdSX290JiJEAWYeGRM2GOW4+e4oc8SAkBFLEF98k0SODvSVruRzVRXRHs1WGkp0VQXg== X-Received: by 2002:a17:902:ea03:b0:1dd:a3d6:3aff with SMTP id s3-20020a170902ea0300b001dda3d63affmr20470236plg.3.1710946483685; Wed, 20 Mar 2024 07:54:43 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:43 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 04/15] lib min_heap: Add type safe interface Date: Wed, 20 Mar 2024 22:54:06 +0800 Message-Id: <20240320145417.336208-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 a type-safe interface for min_heap by adding small macro wrappers around functions and using a 0-size array to store type information. This enables the use of __minheap_cast and __minheap_obj_size macros for type casting and obtaining element size. The implementation draws inspiration from generic-radix-tree.h, eliminating the need to pass element size in min_heap_callbacks. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/dm-vdo/repair.c | 21 +++++----- drivers/md/dm-vdo/slab-depot.c | 13 +++--- include/linux/min_heap.h | 75 +++++++++++++++++++++++----------- kernel/events/core.c | 35 ++++++++-------- lib/test_min_heap.c | 49 +++++++++++----------- 5 files changed, 107 insertions(+), 86 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index defc9359f10e..7663fa2098f4 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -51,6 +51,8 @@ struct recovery_point { bool increment_applied; }; =20 +MIN_HEAP(struct numbered_block_mapping *, replay_heap); + struct repair_completion { /* The completion header */ struct vdo_completion completion; @@ -97,7 +99,7 @@ struct repair_completion { * order, then original journal order. This permits efficient iteration o= ver the journal * entries in order. */ - struct min_heap replay_heap; + struct replay_heap replay_heap; /* Fields tracking progress through the journal entries. */ struct numbered_block_mapping *current_entry; struct numbered_block_mapping *current_unfetched_entry; @@ -163,25 +165,24 @@ static void swap_mappings(void *item1, void *item2) } =20 static const struct min_heap_callbacks repair_min_heap =3D { - .elem_size =3D sizeof(struct numbered_block_mapping), .less =3D mapping_is_less_than, .swp =3D swap_mappings, }; =20 static struct numbered_block_mapping *sort_next_heap_element(struct repair= _completion *repair) { - struct min_heap *heap =3D &repair->replay_heap; + struct replay_heap *heap =3D &repair->replay_heap; struct numbered_block_mapping *last; =20 - if (heap->nr =3D=3D 0) + if (heap->heap.nr =3D=3D 0) return NULL; =20 /* * Swap the next heap element with the last one on the heap, popping it o= ff the heap, * restore the heap invariant, and return a pointer to the popped element. */ - last =3D &repair->entries[--heap->nr]; - swap_mappings(heap->data, last); + last =3D &repair->entries[--heap->heap.nr]; + swap_mappings(heap->heap.data, last); min_heapify(heap, 0, &repair_min_heap); return last; } @@ -1117,11 +1118,9 @@ static void recover_block_map(struct vdo_completion = *completion) * Organize the journal entries into a binary heap so we can iterate over= them in sorted * order incrementally, avoiding an expensive sort call. */ - repair->replay_heap =3D (struct min_heap) { - .data =3D repair->entries, - .nr =3D repair->block_map_entry_count, - .size =3D repair->block_map_entry_count, - }; + repair->replay_heap.heap.data =3D repair->entries; + repair->replay_heap.heap.nr =3D repair->block_map_entry_count; + repair->replay_heap.heap.size =3D repair->block_map_entry_count; min_heapify_all(&repair->replay_heap, &repair_min_heap); =20 vdo_log_info("Replaying %zu recovery entries into block map", diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 46e4721e5b4f..3309480170c3 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3309,7 +3309,6 @@ static void swap_slab_statuses(void *item1, void *ite= m2) } =20 static const struct min_heap_callbacks slab_status_min_heap =3D { - .elem_size =3D sizeof(struct slab_status), .less =3D slab_status_is_less_than, .swp =3D swap_slab_statuses, }; @@ -3509,7 +3508,7 @@ static int get_slab_statuses(struct block_allocator *= allocator, static int __must_check vdo_prepare_slabs_for_allocation(struct block_allo= cator *allocator) { struct slab_status current_slab_status; - struct min_heap heap; + MIN_HEAP(struct slab_status *, heap) heap; int result; struct slab_status *slab_statuses; struct slab_depot *depot =3D allocator->depot; @@ -3521,14 +3520,12 @@ static int __must_check vdo_prepare_slabs_for_alloc= ation(struct block_allocator return result; =20 /* Sort the slabs by cleanliness, then by emptiness hint. */ - heap =3D (struct min_heap) { - .data =3D slab_statuses, - .nr =3D allocator->slab_count, - .size =3D allocator->slab_count, - }; + heap.heap.data =3D slab_statuses; + heap.heap.nr =3D allocator->slab_count; + heap.heap.size =3D allocator->slab_count; min_heapify_all(&heap, &slab_status_min_heap); =20 - while (heap.nr > 0) { + while (heap.heap.nr > 0) { bool high_priority; struct vdo_slab *slab; struct slab_journal *journal; diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d52daf45861b..c3635a7fdb88 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -7,45 +7,59 @@ #include =20 /** - * struct min_heap - Data structure to hold a min-heap. + * struct __min_heap - Data structure to hold a min-heap. * @data: Start of array holding the heap elements. * @nr: Number of elements currently in the heap. * @size: Maximum number of elements that can be held in current storage. */ -struct min_heap { +struct __min_heap { void *data; int nr; int size; }; =20 +/* + * We use a 0 size array to stash the type we're storing without taking any + * space at runtime - then the various accessor macros can use typeof() to= get + * to it for casts/sizeof - we also force the alignment so that storing a = type + * with a ridiculous alignment doesn't blow up the alignment or size of the + * min_heap. + */ +#define MIN_HEAP(_type, _name) \ +struct _name { \ + struct __min_heap heap; \ + _type type[0] __aligned(1); \ +} + +#define __minheap_cast(_heap) (typeof((_heap)->type[0]) *) +#define __minheap_obj_size(_heap) sizeof((_heap)->type[0]) + /** * struct min_heap_callbacks - Data/functions to customise the min_heap. - * @elem_size: The nr of each element in bytes. * @less: Partial order function for this heap. * @swp: Swap elements function. */ struct min_heap_callbacks { - int elem_size; bool (*less)(const void *lhs, const void *rhs); void (*swp)(void *lhs, void *rhs); }; =20 /* Sift the element at pos down the heap. */ static __always_inline -void min_heapify(struct min_heap *heap, int pos, +void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func) { void *left, *right; void *data =3D heap->data; - void *root =3D data + pos * func->elem_size; + void *root =3D data + pos * elem_size; int i =3D pos, j; =20 /* Find the sift-down path all the way to the leaves. */ for (;;) { if (i * 2 + 2 >=3D heap->nr) break; - left =3D data + (i * 2 + 1) * func->elem_size; - right =3D data + (i * 2 + 2) * func->elem_size; + left =3D data + (i * 2 + 1) * elem_size; + right =3D data + (i * 2 + 2) * elem_size; i =3D func->less(left, right) ? i * 2 + 1 : i * 2 + 2; } =20 @@ -54,31 +68,37 @@ void min_heapify(struct min_heap *heap, int pos, i =3D i * 2 + 1; =20 /* Backtrack to the correct location. */ - while (i !=3D pos && func->less(root, data + i * func->elem_size)) + while (i !=3D pos && func->less(root, data + i * elem_size)) i =3D (i - 1) / 2; =20 /* Shift the element into its correct place. */ j =3D i; while (i !=3D pos) { i =3D (i - 1) / 2; - func->swp(data + i * func->elem_size, data + j * func->elem_size); + func->swp(data + i * elem_size, data + j * elem_size); } } =20 +#define min_heapify(_heap, _pos, _func) \ + __min_heapify(&(_heap)->heap, _pos, __minheap_obj_size(_heap), _func) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void min_heapify_all(struct min_heap *heap, +void __min_heapify_all(struct __min_heap *heap, size_t elem_size, const struct min_heap_callbacks *func) { int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - min_heapify(heap, i, func); + __min_heapify(heap, i, elem_size, func); } =20 +#define min_heapify_all(_heap, _func) \ + __min_heapify_all(&(_heap)->heap, __minheap_obj_size(_heap), _func) + /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void min_heap_pop(struct min_heap *heap, +void __min_heap_pop(struct __min_heap *heap, size_t elem_size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -88,27 +108,33 @@ void min_heap_pop(struct min_heap *heap, =20 /* Place last element at the root (position 0) and then sift down. */ heap->nr--; - memcpy(data, data + (heap->nr * func->elem_size), func->elem_size); - min_heapify(heap, 0, func); + memcpy(data, data + (heap->nr * elem_size), elem_size); + __min_heapify(heap, 0, elem_size, func); } =20 +#define min_heap_pop(_heap, _func) \ + __min_heap_pop(&(_heap)->heap, __minheap_obj_size(_heap), _func) + /* * Remove the minimum element and then push the given element. The * implementation performs 1 sift (O(log2(nr))) and is therefore more * efficient than a pop followed by a push that does 2. */ static __always_inline -void min_heap_pop_push(struct min_heap *heap, - const void *element, +void __min_heap_pop_push(struct __min_heap *heap, + const void *element, size_t elem_size, const struct min_heap_callbacks *func) { - memcpy(heap->data, element, func->elem_size); - min_heapify(heap, 0, func); + memcpy(heap->data, element, elem_size); + __min_heapify(heap, 0, elem_size, func); } =20 +#define min_heap_pop_push(_heap, _element, _func) \ + __min_heap_pop_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), = _func) + /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void min_heap_push(struct min_heap *heap, const void *element, +void __min_heap_push(struct __min_heap *heap, const void *element, size_t = elem_size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -120,17 +146,20 @@ void min_heap_push(struct min_heap *heap, const void = *element, =20 /* Place at the end of data. */ pos =3D heap->nr; - memcpy(data + (pos * func->elem_size), element, func->elem_size); + memcpy(data + (pos * elem_size), element, elem_size); heap->nr++; =20 /* Sift child at pos up. */ for (; pos > 0; pos =3D (pos - 1) / 2) { - child =3D data + (pos * func->elem_size); - parent =3D data + ((pos - 1) / 2) * func->elem_size; + child =3D data + (pos * elem_size); + parent =3D data + ((pos - 1) / 2) * elem_size; if (func->less(parent, child)) break; func->swp(parent, child); } } =20 +#define min_heap_push(_heap, _element, _func) \ + __min_heap_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), _fun= c) + #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 10ac2db83f14..065dfaa8b009 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3698,19 +3698,20 @@ static void swap_ptr(void *l, void *r) swap(*lp, *rp); } =20 +MIN_HEAP(struct perf_event *, perf_event_min_heap); + static const struct min_heap_callbacks perf_min_heap =3D { - .elem_size =3D sizeof(struct perf_event *), .less =3D perf_less_group_idx, .swp =3D swap_ptr, }; =20 -static void __heap_add(struct min_heap *heap, struct perf_event *event) +static void __heap_add(struct perf_event_min_heap *heap, struct perf_event= *event) { - struct perf_event **itrs =3D heap->data; + struct perf_event **itrs =3D heap->heap.data; =20 if (event) { - itrs[heap->nr] =3D event; - heap->nr++; + itrs[heap->heap.nr] =3D event; + heap->heap.nr++; } } =20 @@ -3738,7 +3739,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, struct perf_cpu_context *cpuctx =3D NULL; /* Space for per CPU and/or any CPU event iterators. */ struct perf_event *itrs[2]; - struct min_heap event_heap; + struct perf_event_min_heap event_heap; struct perf_event **evt; int ret; =20 @@ -3747,11 +3748,9 @@ static noinline int visit_groups_merge(struct perf_e= vent_context *ctx, =20 if (!ctx->task) { cpuctx =3D this_cpu_ptr(&perf_cpu_context); - event_heap =3D (struct min_heap){ - .data =3D cpuctx->heap, - .nr =3D 0, - .size =3D cpuctx->heap_size, - }; + event_heap.heap.data =3D cpuctx->heap; + event_heap.heap.nr =3D 0; + event_heap.heap.size =3D cpuctx->heap_size; =20 lockdep_assert_held(&cpuctx->ctx.lock); =20 @@ -3760,15 +3759,13 @@ static noinline int visit_groups_merge(struct perf_= event_context *ctx, css =3D &cpuctx->cgrp->css; #endif } else { - event_heap =3D (struct min_heap){ - .data =3D itrs, - .nr =3D 0, - .size =3D ARRAY_SIZE(itrs), - }; + event_heap.heap.data =3D itrs; + event_heap.heap.nr =3D 0; + event_heap.heap.size =3D ARRAY_SIZE(itrs); /* Events not within a CPU context may be on any CPU. */ __heap_add(&event_heap, perf_event_groups_first(groups, -1, pmu, NULL)); } - evt =3D event_heap.data; + evt =3D event_heap.heap.data; =20 __heap_add(&event_heap, perf_event_groups_first(groups, cpu, pmu, NULL)); =20 @@ -3777,14 +3774,14 @@ static noinline int visit_groups_merge(struct perf_= event_context *ctx, __heap_add(&event_heap, perf_event_groups_first(groups, cpu, pmu, css->c= group)); #endif =20 - if (event_heap.nr) { + if (event_heap.heap.nr) { __link_epc((*evt)->pmu_ctx); perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } =20 min_heapify_all(&event_heap, &perf_min_heap); =20 - while (event_heap.nr) { + while (event_heap.heap.nr) { ret =3D func(*evt, data); if (ret) return ret; diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 7b01b4387cfb..af2e446034d8 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -11,6 +11,8 @@ #include #include =20 +MIN_HEAP(int, min_heap_test); + static __init bool less_than(const void *lhs, const void *rhs) { return *(int *)lhs < *(int *)rhs; @@ -30,16 +32,16 @@ static __init void swap_ints(void *lhs, void *rhs) } =20 static __init int pop_verify_heap(bool min_heap, - struct min_heap *heap, + struct min_heap_test *heap, const struct min_heap_callbacks *funcs) { - int *values =3D heap->data; + int *values =3D heap->heap.data; int err =3D 0; int last; =20 last =3D values[0]; min_heap_pop(heap, funcs); - while (heap->nr > 0) { + while (heap->heap.nr > 0) { if (min_heap) { if (last > values[0]) { pr_err("error: expected %d <=3D %d\n", last, @@ -63,13 +65,12 @@ static __init int test_heapify_all(bool min_heap) { int values[] =3D { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; - struct min_heap heap =3D { - .data =3D values, - .nr =3D ARRAY_SIZE(values), - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.heap.data =3D values; + heap.heap.nr =3D ARRAY_SIZE(values); + heap.heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -81,8 +82,8 @@ static __init int test_heapify_all(bool min_heap) =20 =20 /* Test with randomly generated values. */ - heap.nr =3D ARRAY_SIZE(values); - for (i =3D 0; i < heap.nr; i++) + heap.heap.nr =3D ARRAY_SIZE(values); + for (i =3D 0; i < heap.heap.nr; i++) values[i] =3D get_random_u32(); =20 min_heapify_all(&heap, &funcs); @@ -96,13 +97,12 @@ static __init int test_heap_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { - .data =3D values, - .nr =3D 0, - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.heap.data =3D values; + heap.heap.nr =3D 0; + heap.heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -115,7 +115,7 @@ static __init int test_heap_push(bool min_heap) err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 /* Test with randomly generated values. */ - while (heap.nr < heap.size) { + while (heap.heap.nr < heap.heap.size) { temp =3D get_random_u32(); min_heap_push(&heap, &temp, &funcs); } @@ -129,13 +129,12 @@ static __init int test_heap_pop_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { - .data =3D values, - .nr =3D 0, - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.heap.data =3D values; + heap.heap.nr =3D 0; + heap.heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -152,7 +151,7 @@ static __init int test_heap_pop_push(bool min_heap) =20 err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 - heap.nr =3D 0; + heap.heap.nr =3D 0; for (i =3D 0; i < ARRAY_SIZE(data); i++) min_heap_push(&heap, &temp, &funcs); =20 --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f169.google.com (mail-pl1-f169.google.com [209.85.214.169]) (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 F2C0554BFD; Wed, 20 Mar 2024 14:54:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946490; cv=none; b=ifTXbI4TNdc8t+z6rb9ZGjY/Ii3AOKor7rrSymoER6pcoet2qboUa2Ky3h10luJM4qL29CqSL1If6aRcjbHn3hIGKRIsTWFy70zUIQR0q8+9K1LzARhuU2JJ6pgHqP47gZ+yR3vUibD+iQXSa8LvSZlAHtH0ESwnDMDfaSZ+HF4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946490; c=relaxed/simple; bh=1kcI5O448ZoSUJqM7Fwo+CLjTMdYaBqUzIGDOV4I8Wc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=oqMih5p39KvVozBkmZi7lSJSnws0hInsoU2pM9pZ3JRq0qTOmpv/tKT0Xx8eLJFfKd5NGOztEehF3QS+Dq30uiCqDYq55N6hRDuYRS7m3MMcd10NbOHXLxLx6+7d9/kZwY33zNqCMJNLMaF0dpJfjJHY/UsG5ha0mbialW20egY= 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=IMu6Y8v0; arc=none smtp.client-ip=209.85.214.169 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="IMu6Y8v0" Received: by mail-pl1-f169.google.com with SMTP id d9443c01a7336-1def81ee762so9760245ad.0; Wed, 20 Mar 2024 07:54:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946488; x=1711551288; 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=wIY+iLTtXDqlHadPKUvUaL+ptK+GK0/HaTJmss4inJc=; b=IMu6Y8v0GfXtnfOVsPBV4wYmiQvoxlxDW/i8zST25L/EOpELz0uQOZE1BV62ADzGGl rAx0yhFaL4peXgtgSMifq0iK0U+oqOyI/HqZl3Oytl8NFYlCkCvqn2SV/ul1Xl1MFn+9 QoNUQTK6r9FiUaoGzkPUz+OHouJC572rI4x9hyV+fQzX0qJpvCjHykf55bS14HqNCKaP /E37SNDq7DrPk6gSHV/30VyQvv6cO5T2LGJzstJn3nFb3KTypKb4FEurV1MoLsps9Vfy wxI7ZQX0DSBo/YMrOUwgoGaR2xYqgMy3f5NB5/1TpIBD0eCBZpwpHiX2wnpqN97GDtCT dWzg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946488; x=1711551288; 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=wIY+iLTtXDqlHadPKUvUaL+ptK+GK0/HaTJmss4inJc=; b=eoNnhlcMFYhtV5LQ7pcyyUbwEST2IFPyHJ7W80pGk00rT3HKOrQSSr64I+eVbq1mEV 78vabdiCDgh1ot3gaEzipO8W/sOwLiso9b1BDkAxm6qaZMaRxh/lkR/CRijYJL2JxZDr YldDoct+AEA10RL51IiUbzDivpaFDuEjaJiYTMGwnelC4qc769M8nfBMJDJMioO4ftBZ oSqFtWtB4z+KdQ6p0MZ4Pw8SXcd6rvlTvTqGHfj8IIjqQ9gTLRK3pSJAP6XkuZoyCrDc 9sgaO3MRtKXvPaBXv4oq2rTC/sZWPbIDtfqFEpAf3yJnPeBeEvnuNBEhbELl++AsvED4 lDwA== X-Forwarded-Encrypted: i=1; AJvYcCWIi7cJAecUuenAfhLm2f90wIrKfXq+kX6UnBZJ2gst5yqCP22Hvw1QPZ52utysae9u6wtnWH+79yKPY42NQaGYQ2YvYKShH4Q/pVbaBXeSLOPuJ3/h4mZX/SWKnjwymfJ3LIZ47XsR97sfhkYA6QQ0QsUsejmEB0m70eGW9gxGFYJpbrLBIf7hwoQ7z/cK5tLHn8tx+x4T3Mg09B6dFjdKadzS7rnVRP4fkuBf X-Gm-Message-State: AOJu0YxB0CM2FljKwTXNqtJkASTxcMEyVSAhjYgbCbn176fER9/N6aj7 ZMoDuJundHbzIPgFY0+b1wVGGgZDVjESUqDOLySpzjtcbxLd+oQ8 X-Google-Smtp-Source: AGHT+IGcYha2L/klvjE95SX1NwjIcrrjx6lhQgqEP8rC4e+/MaAzigVjqy5yAHiaD5OOHjIki9QMLg== X-Received: by 2002:a17:902:d4d1:b0:1dd:6f1a:2106 with SMTP id o17-20020a170902d4d100b001dd6f1a2106mr6183213plg.0.1710946488296; Wed, 20 Mar 2024 07:54:48 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:47 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 05/15] lib min_heap: Add min_heap_init() Date: Wed, 20 Mar 2024 22:54:07 +0800 Message-Id: <20240320145417.336208-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 min_heap_init() for initializing heap with data, nr, and size. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index c3635a7fdb88..ed462f194b88 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -44,6 +44,18 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs); }; =20 +/* Initialize a min-heap. */ +static __always_inline +void __min_heap_init(struct __min_heap *heap, void *data, int size) +{ + heap->data =3D data; + heap->nr =3D 0; + heap->size =3D size; +} + +#define min_heap_init(_heap, _data, _size) \ + __min_heap_init(&(_heap)->heap, _data, _size) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (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 8F0DC5645B; Wed, 20 Mar 2024 14:54:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946495; cv=none; b=Q2IPkiT2zBhcDT83ML8gMD7xL8KWZZdb+YM4rt0XBSaZNJJccFhiz8e2xQyn+VfrsJMO/8AqRKRncKkKOdVmMv2bcpatVpFEKatFsTVcuy1m/gCTkLBV20CqxygzRL6AIwYd+zipWMx2R6LWXfEct5aP1yFEfnUrD0I5fQi+Uqk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946495; c=relaxed/simple; bh=8a68K+W3qZD++KgYqdJ8QFpXlGJ3ofQ9m/5i3nVK9u0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Xjar9W0Dp6Dc6GldK1R94zhZc8Tn4T4d5EXHSDnVEhzq2rBT0FjWsBa1HqRz/zIzMUqol4wDPm6/f9MgbHUtFlrA36JRJwGd+k9Qpu/vIZBtuUmlE2PMY2hGmcAIqdKXCOK3mEJ64XoN5+8NquAu21XMn/2Tbw2T2ShfjqaHBSs= 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=RQYiSXJo; arc=none smtp.client-ip=209.85.214.179 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="RQYiSXJo" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1dee6672526so6079185ad.1; Wed, 20 Mar 2024 07:54:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946493; x=1711551293; 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=g5/a5el4a61wFJIBzCgWNmWU3XZlSJ2PCR5OhDq59lw=; b=RQYiSXJoNzrTFJNriCDqofrrD38NwTxRhNaAAPZXA1Z1OTGi0oNAP18rp4rhWwLVHp fYNfKEry/ywdPVw5bv3Cv8mnSNSOxqCrUlGVTEh6Mi9rJOdd6TGC3kLZsoEDFMtLSPHd frfWsNRrv2Ep31Ie9uYxmVmcHSvUQDd1D2amVMu7WpLgVO9+NJZM5xzRbQyEon0dKg0m X8KdTHPswAOGV1WxcS+gu4YTRQmXLaJOvgyXadUNpUadeW6qW9lRF4jyTYzuVkeyg0zt hkEobPWyu4ktMP3PbRBsu7fbhnBRfA7+pqY/XwOKltBwPI1khifmIn0uk3iJ/WdCtngo VL1g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946493; x=1711551293; 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=g5/a5el4a61wFJIBzCgWNmWU3XZlSJ2PCR5OhDq59lw=; b=Af1kq0kmaqOSQfuoEQg3L40+ZfMAA7CBQNWZE/gQSyUYBS/A4TLNneZnv1YpD02JTb ZtVYgpfRS7M2nvVB/EJNf1sT9ypmzO/ehWzP6tswQQFdxyCtlv1jMnD6+o5FmN2ikDKl abKsWJKhzlSoPUgAxrX/UvOGrYVhvafV1ZIj7I7yQQO9BhwiBlIxdr+K2CX3yJU7JTkk 9JrOaosd74JV+UkX5neAvL3eDY81Vj1Yv1G6he7FbbcKtGm6MURVjcDO1iCWK/AvH8Nh RrlS6LHPu9jUUtOmDrfwoMH7+rqObGEW8Pad9HhaoE/WLEcniYKC4vyOIH9pC2WOdUaR WtlA== X-Forwarded-Encrypted: i=1; AJvYcCVL3fb4p6SfDaSOj/R2a7rl9j4kP32ouvTMey3pvrpqjYJuVr7L2f1okzMmQmnwyIB5fMHTCkANDXhr3HNz4S54dPMlhp3RnfDDRKV00SrLhYFpUqG5gtK2Ii6snI7J9mMhAnmkkQ/c4AY1RdVQIe0Tt1MngwwzenZrxKlxEwYwioYXn+ve4M77uPWqDqBEvF0CkkhhxO3SC5nFc+1b+piKpzRVVVpJXUqlDzEe X-Gm-Message-State: AOJu0YxHya9CNCFjtJT15OUaBHqpbTXAs0AZbm8Y0oU87N99i35qthmR 4tGnqb6+tn/PPmRVMpQDxh7bBe4M746d5nd7G0SFr7TVirGXDgZd X-Google-Smtp-Source: AGHT+IGvhyqndniFbkMNrKQajfiHJUdmj6ZvIM3gEC4yAeOXQXFolKTC1Reahvgx53VYp1rBgyowXg== X-Received: by 2002:a17:902:ce91:b0:1dc:df03:ad86 with SMTP id f17-20020a170902ce9100b001dcdf03ad86mr20347899plg.2.1710946492946; Wed, 20 Mar 2024 07:54:52 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:52 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 06/15] lib min_heap: Add min_heap_peek() Date: Wed, 20 Mar 2024 22:54:08 +0800 Message-Id: <20240320145417.336208-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 min_heap_peek() function to retrieve a pointer to the smallest element. The pointer is cast to the appropriate type of heap elements. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index ed462f194b88..7c1fd1ddc71a 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -56,6 +56,16 @@ void __min_heap_init(struct __min_heap *heap, void *data= , int size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init(&(_heap)->heap, _data, _size) =20 +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct __min_heap *heap) +{ + return heap->nr ? heap->data : NULL; +} + +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek(&(_heap)->heap)) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E83B54EB33; Wed, 20 Mar 2024 14:54:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946500; cv=none; b=TWJ9Gx3dleWiRTRCt4mQxs+62vbBJtUmYVe7iM/TdRjADONNyNAvnb2xWOki/LmN/Nso9vDzBrgSPSX7lyKb1/maYcBHa+Wod4EGNBSGx0iFkg69xsq4v7+Z7sM1PbMpy0ZDuTO9TkVHw76e9iiidXIui5R6iV6FsoHk9TKKkKI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946500; c=relaxed/simple; bh=87oXCcVzX378JZ7P9KHFZTxbp5kTVN7ioJ6nxJ/kTRs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=sPODTd6DSQ6UBv62fCqJsTZXQ6pOPhT4VIdo/UEaVPrcHG0ykwHgtBeCcJsbfsJ+KJ2sZTmzKcJNngKiMorbI7z2lmbRExs2UANMEmmlzk4SpUel3sGc/dy82G3ElKdQN7zBNsIZ6FY5KHVE/QeOpiRgEdGV76xPg1W5OuTjZuM= 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=GObgr9Rp; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="GObgr9Rp" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1dee6672526so6079395ad.1; Wed, 20 Mar 2024 07:54:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946498; x=1711551298; 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=6wlW/VG1bZr/fW5x2pRSDPzGgSGqgaQobdRLr7/yKpQ=; b=GObgr9RplSefgIPBiCrxRw2uf/gZUu4t1IPn100WhFP3AtkKuGaEGbhr3ZUYEez9uB tBOysu+U6G3uPp/yQB5JRC2UAsV9wY69BRQ1QpsLGSL2YN0BADvObmxYNomsaUQR9TWQ Nw0I1Yniu/rV2ivUFp9Bcbpv+xVsJPEQxVs1OM6cT0Sh+myCwfvRdBWMSS8fxDfmwCcK ohctW9IN6euEgRKM3KCbtGLZ9TgMfFx9Bh7MC8hrNRCNioQynotRBdHFUoA/wgOe6Ke4 OyOf29mFg5N3zqbXvYzDEVHXVXpcLbFtcdaOYaFLLLy8IXmaL1JhTi7BZp2V+IBo/ZrK C9oQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946498; x=1711551298; 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=6wlW/VG1bZr/fW5x2pRSDPzGgSGqgaQobdRLr7/yKpQ=; b=tnZRrhYWdeboOOqkcka3FWRTWcYK2dj+Xex1YKON9x3xhMr2QMBvi30N+JZjJ1O6+Y LIEE0aX+SOzTR/ogYABxC/E2oEaQeAWO8LBcVVj9MogDMuZ6I78ahA/tIsPrsW9dlJT+ 8tFMrM6qbZQYQ8M3yMVngS71preugo3Zde42XUVmC3L9ke4tKAU0LcHfCdWx8Sp7OyxM V3XF6CPvMGGSOhtegTRxgIK7aiOsuZqr5f53D/hul8Av2K4lTJwuTL11VYNpKoDTRnqD yrJ6tC11P04Sq6T1515sUcGKs659SAWyAJb9FUelj1cKT7rvvK6WsBU9YUPB9QqASvIo QJTg== X-Forwarded-Encrypted: i=1; AJvYcCWr0CtS90S2Bv6Q6eL6Ysru8OTG5GOiV1DufKZZ16cB1U0KlPh7rOgdv/WggqnXR6WWw0SqXd8mkV/wwvp12vuiErgEC3IU81dcO70ko904xeiB8Y0o6wGT+OudCiRD2IdFTsyY6RiswM3/ehZX3bHr4MFvHMyZVIVNFpFhEo9GPXvuYmEvIcfEIEPL7JyQZSa1bkugH/qInXTBFNIUNryWdZ0lpX67eU/mCg5C X-Gm-Message-State: AOJu0YxJGcjyCgIphcVrKCFOlEtW3McCTS0iSlMfGVP/UoGsUX8dbDkU Vde+KJpkZiCxMmoriiOLxQ6MJMG3OXzr4vw2/xBjeGgjzsFsMCZv X-Google-Smtp-Source: AGHT+IHPNXqxNRiHHdL94gEllLU3VLR0+ZSU1ayFv4vdbYAP2+XpkPoVncG1MrhmG5iQ5COCDdzKFQ== X-Received: by 2002:a17:903:1c1:b0:1dd:7c4c:c6b6 with SMTP id e1-20020a17090301c100b001dd7c4cc6b6mr19250306plh.5.1710946498281; Wed, 20 Mar 2024 07:54:58 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:54:57 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 07/15] lib min_heap: Add min_heap_full() Date: Wed, 20 Mar 2024 22:54:09 +0800 Message-Id: <20240320145417.336208-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 min_heap_full() which returns a boolean value indicating whether the heap has reached its maximum capacity. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 7c1fd1ddc71a..b1d874f4d536 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -66,6 +66,16 @@ void *__min_heap_peek(struct __min_heap *heap) #define min_heap_peek(_heap) \ (__minheap_cast(_heap) __min_heap_peek(&(_heap)->heap)) =20 +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(struct __min_heap *heap) +{ + return heap->nr =3D=3D heap->size; +} + +#define min_heap_full(_heap) \ + __min_heap_full(&(_heap)->heap) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f177.google.com (mail-pl1-f177.google.com [209.85.214.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 E65255730C; Wed, 20 Mar 2024 14:55:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946505; cv=none; b=VQaFgONDMuwigpJq8DKPZ9lY0yLCNj70kmPFFK1Vb4y5PbvEQVX4k2PTDc+hC06kbQIyk/I7RZRzSPG4SQziiLPjvj+ohJ9hsymLKFzw5K3Kj+JtNhhPzEx2AAXPH8cr/aCsHxg9S1vsAxfLpLKMV3ALIewMUy48Tngv/bcDfe4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946505; c=relaxed/simple; bh=qteByzsELspBqYOuIARYBU2Zdpp8cSKVC+Oyjn250gs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=rOWKuEwU1egLjLvYUndtCalgQaQaK82b2fUkYWl5qDB6BPWsbEFQrHnyw1jUo9tSlWzQhnIaGizM8d1KMbrx6pOwptSyLUIGPIPSxMaSwLD+3rW6F1pJOQ3i92oiKEcnY2yaM9FEBEr5JKPGUmkecJDEDdJz/qgaOg+jG/E5L8g= 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=bWrwRIa+; arc=none smtp.client-ip=209.85.214.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="bWrwRIa+" Received: by mail-pl1-f177.google.com with SMTP id d9443c01a7336-1dd8ee2441dso11936795ad.1; Wed, 20 Mar 2024 07:55:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946503; x=1711551303; 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=qQWgWJZiZRkB0L8mwTWbJhKi4LMazpagttqLDd/n3Ao=; b=bWrwRIa+VAQo+6LwHNKQlk1UhtYYgSo8OoF1+Sb0HAh/4nf/yrGBoiw4+FsN1KovBk e+JiVlTubeUMJU31Cpf/mUWr3vvBRvCU+3MknMX1uaEJeTvOxPos39b9fXZ9OEE5Bz3d n3vzsgobUao4ONeq/5fZL86cfMt0DfEPPLWm+XfoEq12gycojHhatHXk4TmLGPX0xAmh jp2GRNbIfOGlP4sejINPSD2X4iylZxr9ThEgISNerHg4iZeseNX2+VnyqY7sjkaRyO5J 4rMkM55i8sL2QjJN55Hbi3w9dTRfSUGbLDnmSb5U2HOPYdNboRh19pybSz1g+kNANrP8 QTwA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946503; x=1711551303; 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=qQWgWJZiZRkB0L8mwTWbJhKi4LMazpagttqLDd/n3Ao=; b=Zt6WUSsA1PXwOrJqJHnN01Pmtleqo/9iIZ03M8c0Jruf4ro8eGIhhz1BHKagpQjRUx TdRsYh1CoYINzDbreR5zVrIN4M0ISefXHXiWlziJu0XjE9TWfDat/2J/onAZL6s95566 Cd5bqgLfS46499/jvAGeUVwkOuvu7CK/JmNgw9gMVRFBVF/0O5D4ufr7X0zu069mfZ5I aC24VagKDOVtBXT2pl3Xk8Kw6yUkP54+D+bGZ3T+JWkjmoYqoNUxS25BB8gb/cUiZuI4 mqu5voczCTE65IAo6z8B9uTJl/GU06ION2GZAwXKsxJM19se+ENqaf+QfyxxFbGDl5mK 3Uig== X-Forwarded-Encrypted: i=1; AJvYcCUNqC1WTCFRlxMKxh9XSgRU4nt6mD0W12Bur4l5qZfe4nioVCW1PTx18JDr73kAKq48fgZ57ANrjefMcbPWyHWeRmzs7rr4LnJBvn93wYI+eVHxjXAqDXrp06lkRN9wE9ZhkbwOerTj9o+MjYzqjNiGl+kzBYovX6XgvMk9wCofSkWx8hm7ET+gnkiHSbuye7VG2uxdBvoU+ACyE6pp6nTLiA4nAkS7DJs66Iur X-Gm-Message-State: AOJu0Yws2hHBrrV9YPrA1DoUTzDlLMdVt+g+N55BM4lGuzwu4r2+qU24 ObXWCI2WCeaPb8RYPQnVSktB4h37vcI780+kPAyUJ4Hp8+u1DkBI X-Google-Smtp-Source: AGHT+IHQMu7VAPDiqxJgKvWwfBIcERpY9KKEw9e5I4279Pib64kSmLnENjmLOaIX8wFBH1sb7n9z5Q== X-Received: by 2002:a17:902:c94d:b0:1dc:e469:6f5d with SMTP id i13-20020a170902c94d00b001dce4696f5dmr6103504pla.4.1710946503210; Wed, 20 Mar 2024 07:55:03 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.54.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:02 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 08/15] lib min_heap: Add min_heap_del() Date: Wed, 20 Mar 2024 22:54:10 +0800 Message-Id: <20240320145417.336208-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 min_heap_del() to delete the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index b1d874f4d536..36023e0be232 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -194,4 +194,28 @@ void __min_heap_push(struct __min_heap *heap, const vo= id *element, size_t elem_s #define min_heap_push(_heap, _element, _func) \ __min_heap_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), _fun= c) =20 +/* Remove ith element from the heap, O(log2(nr)). */ +static __always_inline +bool __min_heap_del(struct __min_heap *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + + if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) + return false; + + /* Place last element at the root (position 0) and then sift down. */ + heap->nr--; + if (idx =3D=3D heap->nr) + return true; + memcpy(data, data + (heap->nr * elem_size), elem_size); + __min_heap_sift_up(heap, elem_size, idx, func, args); + __min_heapify(heap, idx, elem_size, func, args); + + return true; +} + +#define min_heap_del(_heap, _idx, _func, _args) \ + __min_heap_del(&(_heap)->heap, __minheap_obj_size(_heap), _idx, _func, _a= rgs) + #endif /* _LINUX_MIN_HEAP_H */ --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f173.google.com (mail-pl1-f173.google.com [209.85.214.173]) (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 A7D8D5730C; Wed, 20 Mar 2024 14:55:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946510; cv=none; b=jrzgLyM9ODlZbFUK7yCMnIPM93FhFzbAqM7HT406vXZBFFs6wQc5kspcJlizGmqKPmw2hr8dScT2g1X9EpnJkIId1pMRUEUFJNRicgLb5Xh8ZKdwYR9RgGKMLcEF1AJb+UMNdS1UZ7wjRM3WCbVGguDqagiCpWE7QCaFis7qB3Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946510; c=relaxed/simple; bh=3u7SHTx5BWR6PFeMX82UOtRGC+rWOaoSO0kUgAe6Dt4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Jamp1Y09y3mu9DBDbgN3wt789FwcFKgJoPrguhtoWC6vlgUIOaujjtBDyzaP8KXFg7v0PS3IkaOs4oT/IFyUQ+HOtBT88uG3SuDo0BB0NGBv1tS8eZFq8I/wTijtt2vVrku5ssEPXsGY8qtgx+rywKbyrTt4LQiwt74b2Ooilt8= 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=YhYVipQO; arc=none smtp.client-ip=209.85.214.173 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="YhYVipQO" Received: by mail-pl1-f173.google.com with SMTP id d9443c01a7336-1dee5daedf6so8924585ad.0; Wed, 20 Mar 2024 07:55:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946508; x=1711551308; 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=BaX+3tHSfR6Y1hlzEWAzFG8m2A4U3O7BTlzKixVR79s=; b=YhYVipQOajWgnE6rMetXJwNYrJS+OBn9AAFLiWtY5Uiqmjw6n01NmJ2NUcLFRgSBDA L5JmWteRldspjtev1qw1xjqVKjzUZJYtoqAp03gWZXW6YFyQFjN0IzUQnQOoslZVHEqd O+G7SYNWv7unmG4Jymgdzy2kzMqwrEYa0PFWFmG+dhrtfzyXo667Ha73x9zl+Qk3dlZF 9JqOp18CfmFK7oTjxlSXzVU3IZ09t/6GMBurIPl8cXY41xOOqGDi8KQqMI1YtqVNTPG2 7yUreZZxnmpw9G7fKHSbmLqevuuEUv5E9tH5+jE8CGDqILz9mgFp0jm/5Ob2RPjVA8mZ 30+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946508; x=1711551308; 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=BaX+3tHSfR6Y1hlzEWAzFG8m2A4U3O7BTlzKixVR79s=; b=XfKwkzx44gOCoS5qD7uS3h1FBKbROAJizC3U7AMfkd8a/CGesmk/f5HiEveY1IvQTP LPUPtAX4d/STSOe5V6CzbZ0k+jXoRUInr0ZKj75MMcX9CUeoj6WI6c/QTX5zL9WUJncy 7JpNkZ0/aYu8M2ddg17lihOAG4NW+j3IdaqIaZvYq0EWQc2foFOU7CC5cNJjxhlWU2yE WlOCb4x1g0Q/rgQQ5BfdnAXixf8vLjoBaBMUqJRp+IlO2fMBbp12xLHBVJKM1DOAeozp VyaTkaLRESOubU9zpxBCntD0Cv1orZ6McYoU+ItRP3RN5H18jXUNtUUTtPG2cDnQQd4x dK0w== X-Forwarded-Encrypted: i=1; AJvYcCU8A5Rg7ory3gYHjth8AKTjnLL748l89L3yaSZmZpGt5Eir3LIsYfRzM0wKj+m8AtjED3+z5aDoJVoaCFUD7ZbW9W1NZ8MK+5YGNmUd8vYc6Gu5UnqFSSVVAB9qDef/yeObAUqGxwXouAMQYOAhLGJ5Wrk69vT0/oCgyY/BT0mR5PbzYgOw2ywslOC5A5CXar6X58aSeyAPLTjM5ubHaCN9UCxcVIRcDz4LNxAX X-Gm-Message-State: AOJu0YxPh6L1dgYSTx0g8mxKKP5cpFWYtI1OAfCwT5sMYkEbTYkKcALn 4otUL9+xDz7Me5jx21E8LrzQ2HVg2uYwUi6l1MOnp23MVqJQaS/+ X-Google-Smtp-Source: AGHT+IGd6DO4qwAk4p4e7JmQ1R4ZPRJj4m0jMv3XVjEK0nV1sCafyICIXS1wY7+2qQE9k1iEQlC2Rw== X-Received: by 2002:a17:903:18e:b0:1dd:b54c:df51 with SMTP id z14-20020a170903018e00b001ddb54cdf51mr6005831plg.4.1710946507885; Wed, 20 Mar 2024 07:55:07 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.04 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:07 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 09/15] lib min_heap: Add min_heap_sift_up() Date: Wed, 20 Mar 2024 22:54:11 +0800 Message-Id: <20240320145417.336208-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 min_heap_sift_up() to sift up the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu --- include/linux/min_heap.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 36023e0be232..af12531474a4 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -194,6 +194,26 @@ void __min_heap_push(struct __min_heap *heap, const vo= id *element, size_t elem_s #define min_heap_push(_heap, _element, _func) \ __min_heap_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), _fun= c) =20 +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(struct __min_heap *heap, size_t elem_size, size_t = idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + size_t parent; + + while (idx) { + parent =3D (idx - 1) / 2; + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + break; + func->swp(data + parent * elem_size, data + idx * elem_size, args); + idx =3D parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up(&(_heap)->heap, __minheap_obj_size(_heap), _idx, _func= , _args) + /* Remove ith element from the heap, O(log2(nr)). */ static __always_inline bool __min_heap_del(struct __min_heap *heap, size_t elem_size, size_t idx, --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pf1-f180.google.com (mail-pf1-f180.google.com [209.85.210.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 2A0D458AAB; Wed, 20 Mar 2024 14:55:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946515; cv=none; b=CYFcwswUrVVkBYBqjPwvPjWHmn0M9Rcz4NQqPn1C/P8G4b6LVOuL9jhgIzF+t4+t/yZF9VftwsjmJVmpSrfRpOfymKwvdUQTyD6TMkk0TW74cpWcwG9i0c4+BpyFDMc9EuVnwg21ZsG5+9IkkXFVDyYKpn5csRW+U75gDaLxvxU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946515; c=relaxed/simple; bh=v2QDGboZDpSdtXVf/44hZgB01YixUJPmq1o6qcA+7gA=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=kR5UyvIOb6vU/o2xlHGA85UlfWzGz+aOSRsteU9G4O2/M8e0KXtqQICyhIA2odITU5HFBTjfU4byQjhnJkWPyva0g1T2pHGIegJ7WhQsf9FZXs+GOE74CwCNiSWWPfaOOWBJ4daN2YQaAm7TJ48GlOBXfyXpaSStE7WRhhDy86U= 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=g7KBIJ4d; arc=none smtp.client-ip=209.85.210.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="g7KBIJ4d" Received: by mail-pf1-f180.google.com with SMTP id d2e1a72fcca58-6e72123e12dso532630b3a.0; Wed, 20 Mar 2024 07:55:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946512; x=1711551312; 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=3j4BwpnzsCTFbTLEfHkq7OVaw0zB9zsQ8DozRNlNpcs=; b=g7KBIJ4dYsL3EOXdkGBbqQy2AkHQx5ojnLCroHj1hYsEotOAbQF9DFvchuxZKSjg3k Vbz0kCPI4W/RE+z0Hup7FA7fGBjNJ0fMdhhFSBvsSDPh+NKXvkOj4Agr5lBd9Ei9Vu9P Zk30D81HYlODCmruOybYrlCEiYE5LCCYWreMcSUbfvD5hObrtN0agHZt0KoBvbzUBDUJ dlZBqs7lAxewCB23ypzdnmq+4U7QikzUmmL54fj2NzbLDGEf9502Nrqk4JvZbcqsw78O esXq70I7hD6/NBsIkgh0LL3wZVzotHubnD06aWR4zMBNAKoK7fy90YI/8VupAiR1BXs9 69EQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946512; x=1711551312; 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=3j4BwpnzsCTFbTLEfHkq7OVaw0zB9zsQ8DozRNlNpcs=; b=cSlFPBH2HDmwcwWXdWh1MZqzuCwHtE3nSasOUoY+RgQO9bLbSuqsqf4OxbgxnrCpld cHzkQSBreKekpL+4dxJPSshutgO7TXP0FQyyJfkbS4Nfq4MPwGrUYxdIxhKpN3KtP4xz GiVdHtAOATe1I+dPzVflbPmMUhQgjvUcuDpGyIj6PqA+WCi3fMQbaUawRqu7Py2NJiI3 IhEi6PC8s1RbGA+77lPk+Sr0Dee0D80Uo2Y7bFh2Ukv4xqpsNKM9xQtaxZT2HC2AmbBr 6mu0fPoufpkdLUsAavsgMxvWDzoUFgtMe/UVKXqLWbYVpHreVzmLjwUy952ODWBOTJIV Iz4w== X-Forwarded-Encrypted: i=1; AJvYcCWePBpHUzhfs2phGbPBUGC13Gr+taGAzgp09w0solUe3A3wJOBQcCP6zvsmh8rSKlmkMoc3nZ6sd4Ob3scCiEQqUIm3LuYO1zWQfQR5hqYOUygmbrmnnYPcOvC5p1yERodJYihMUmX5ry/7QeoCR3/xOQpHE0fkRSMyuoD8tbargKCJQMufozWPV7xX7Bd+ZIQ2hdVeq02IhhGkM1e7bzOKscQl9YgjEr/HH2Kx X-Gm-Message-State: AOJu0Yz1vKFBnRq2IFPhdDpXu69DILQU49qbfW4nwyBXi+aOz2bbdVxN VhoZj1tOKHdtsKyNc3TXHiZeBYwC6M6fDZqcDFd1rzurVhJqGBql X-Google-Smtp-Source: AGHT+IEjtfUBQQINRHbNCFh+4mc0PM0bj31+zrpBMLrSahwyX96NxG1VTkI8k/KehbVPts8K4VsiIA== X-Received: by 2002:a05:6a20:7f8f:b0:1a3:4721:ded3 with SMTP id d15-20020a056a207f8f00b001a34721ded3mr6093871pzj.1.1710946512376; Wed, 20 Mar 2024 07:55:12 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:11 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 10/15] lib min_heap: Add args for min_heap_callbacks Date: Wed, 20 Mar 2024 22:54:12 +0800 Message-Id: <20240320145417.336208-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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 a third parameter 'args' for the 'less' and 'swp' functions in the 'struct min_heap_callbacks'. This additional parameter allows these comparison and swap functions to handle extra arguments when necessary. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- Changes in v2: - Add attribute __always_unused to the compare and swap functions that do not use the args parameter. drivers/md/dm-vdo/repair.c | 10 +++---- drivers/md/dm-vdo/slab-depot.c | 9 +++--- include/linux/min_heap.h | 51 +++++++++++++++++----------------- kernel/events/core.c | 10 +++---- lib/test_min_heap.c | 26 ++++++++--------- 5 files changed, 54 insertions(+), 52 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index 7663fa2098f4..6acaebcd305d 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -137,7 +137,7 @@ struct repair_completion { * to sort by slot while still ensuring we replay all entries with the sam= e slot in the exact order * as they appeared in the journal. */ -static bool mapping_is_less_than(const void *item1, const void *item2) +static bool mapping_is_less_than(const void *item1, const void *item2, voi= d __always_unused *args) { const struct numbered_block_mapping *mapping1 =3D (const struct numbered_block_mapping *) item1; @@ -156,7 +156,7 @@ static bool mapping_is_less_than(const void *item1, con= st void *item2) return 0; } =20 -static void swap_mappings(void *item1, void *item2) +static void swap_mappings(void *item1, void *item2, void __always_unused *= args) { struct numbered_block_mapping *mapping1 =3D item1; struct numbered_block_mapping *mapping2 =3D item2; @@ -182,8 +182,8 @@ static struct numbered_block_mapping *sort_next_heap_el= ement(struct repair_compl * restore the heap invariant, and return a pointer to the popped element. */ last =3D &repair->entries[--heap->heap.nr]; - swap_mappings(heap->heap.data, last); - min_heapify(heap, 0, &repair_min_heap); + swap_mappings(heap->heap.data, last, NULL); + min_heapify(heap, 0, &repair_min_heap, NULL); return last; } =20 @@ -1121,7 +1121,7 @@ static void recover_block_map(struct vdo_completion *= completion) repair->replay_heap.heap.data =3D repair->entries; repair->replay_heap.heap.nr =3D repair->block_map_entry_count; repair->replay_heap.heap.size =3D repair->block_map_entry_count; - min_heapify_all(&repair->replay_heap, &repair_min_heap); + min_heapify_all(&repair->replay_heap, &repair_min_heap, NULL); =20 vdo_log_info("Replaying %zu recovery entries into block map", repair->block_map_entry_count); diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 3309480170c3..102f492bb1f8 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3288,7 +3288,8 @@ int vdo_release_block_reference(struct block_allocato= r *allocator, * Thus, the ordering is reversed from the usual sense since min_heap retu= rns smaller elements * before larger ones. */ -static bool slab_status_is_less_than(const void *item1, const void *item2) +static bool slab_status_is_less_than(const void *item1, const void *item2, + void __always_unused *args) { const struct slab_status *info1 =3D item1; const struct slab_status *info2 =3D item2; @@ -3300,7 +3301,7 @@ static bool slab_status_is_less_than(const void *item= 1, const void *item2) return info1->slab_number < info2->slab_number; } =20 -static void swap_slab_statuses(void *item1, void *item2) +static void swap_slab_statuses(void *item1, void *item2, void __always_unu= sed *args) { struct slab_status *info1 =3D item1; struct slab_status *info2 =3D item2; @@ -3523,7 +3524,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator heap.heap.data =3D slab_statuses; heap.heap.nr =3D allocator->slab_count; heap.heap.size =3D allocator->slab_count; - min_heapify_all(&heap, &slab_status_min_heap); + min_heapify_all(&heap, &slab_status_min_heap, NULL); =20 while (heap.heap.nr > 0) { bool high_priority; @@ -3531,7 +3532,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator struct slab_journal *journal; =20 current_slab_status =3D slab_statuses[0]; - min_heap_pop(&heap, &slab_status_min_heap); + min_heap_pop(&heap, &slab_status_min_heap, NULL); slab =3D depot->slabs[current_slab_status.slab_number]; =20 if ((depot->load_type =3D=3D VDO_SLAB_DEPOT_REBUILD_LOAD) || diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index af12531474a4..879a9d12e030 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -40,8 +40,8 @@ struct _name { \ * @swp: Swap elements function. */ struct min_heap_callbacks { - bool (*less)(const void *lhs, const void *rhs); - void (*swp)(void *lhs, void *rhs); + bool (*less)(const void *lhs, const void *rhs, void *args); + void (*swp)(void *lhs, void *rhs, void *args); }; =20 /* Initialize a min-heap. */ @@ -79,7 +79,7 @@ bool __min_heap_full(struct __min_heap *heap) /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *left, *right; void *data =3D heap->data; @@ -92,7 +92,7 @@ void __min_heapify(struct __min_heap *heap, int pos, size= _t elem_size, break; left =3D data + (i * 2 + 1) * elem_size; right =3D data + (i * 2 + 2) * elem_size; - i =3D func->less(left, right) ? i * 2 + 1 : i * 2 + 2; + i =3D func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; } =20 /* Special case for the last leaf with no sibling. */ @@ -100,38 +100,38 @@ void __min_heapify(struct __min_heap *heap, int pos, = size_t elem_size, i =3D i * 2 + 1; =20 /* Backtrack to the correct location. */ - while (i !=3D pos && func->less(root, data + i * elem_size)) + while (i !=3D pos && func->less(root, data + i * elem_size, args)) i =3D (i - 1) / 2; =20 /* Shift the element into its correct place. */ j =3D i; while (i !=3D pos) { i =3D (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size); + func->swp(data + i * elem_size, data + j * elem_size, args); } } =20 -#define min_heapify(_heap, _pos, _func) \ - __min_heapify(&(_heap)->heap, _pos, __minheap_obj_size(_heap), _func) +#define min_heapify(_heap, _pos, _func, _args) \ + __min_heapify(&(_heap)->heap, _pos, __minheap_obj_size(_heap), _func, _ar= gs) =20 /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(struct __min_heap *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heapify(heap, i, elem_size, func); + __min_heapify(heap, i, elem_size, func, args); } =20 -#define min_heapify_all(_heap, _func) \ - __min_heapify_all(&(_heap)->heap, __minheap_obj_size(_heap), _func) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all(&(_heap)->heap, __minheap_obj_size(_heap), _func, _args) =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline void __min_heap_pop(struct __min_heap *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 @@ -141,11 +141,11 @@ void __min_heap_pop(struct __min_heap *heap, size_t e= lem_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_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop(_heap, _func) \ - __min_heap_pop(&(_heap)->heap, __minheap_obj_size(_heap), _func) +#define min_heap_pop(_heap, _func, _args) \ + __min_heap_pop(&(_heap)->heap, __minheap_obj_size(_heap), _func, _args) =20 /* * Remove the minimum element and then push the given element. The @@ -155,19 +155,20 @@ void __min_heap_pop(struct __min_heap *heap, size_t e= lem_size, static __always_inline void __min_heap_pop_push(struct __min_heap *heap, const void *element, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, + void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop_push(_heap, _element, _func) \ - __min_heap_pop_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), = _func) +#define min_heap_pop_push(_heap, _element, _func, _args) \ + __min_heap_pop_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), = _func, _args) =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline void __min_heap_push(struct __min_heap *heap, const void *element, size_t = elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; void *child, *parent; @@ -185,14 +186,14 @@ void __min_heap_push(struct __min_heap *heap, const v= oid *element, size_t elem_s for (; pos > 0; pos =3D (pos - 1) / 2) { child =3D data + (pos * elem_size); parent =3D data + ((pos - 1) / 2) * elem_size; - if (func->less(parent, child)) + if (func->less(parent, child, args)) break; - func->swp(parent, child); + func->swp(parent, child, args); } } =20 -#define min_heap_push(_heap, _element, _func) \ - __min_heap_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), _fun= c) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push(&(_heap)->heap, _element, __minheap_obj_size(_heap), _fun= c, _args) =20 /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline diff --git a/kernel/events/core.c b/kernel/events/core.c index 065dfaa8b009..c32a78c489f3 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3683,7 +3683,7 @@ void __perf_event_task_sched_out(struct task_struct *= task, perf_cgroup_switch(next); } =20 -static bool perf_less_group_idx(const void *l, const void *r) +static bool perf_less_group_idx(const void *l, const void *r, void __alway= s_unused *args) { const struct perf_event *le =3D *(const struct perf_event **)l; const struct perf_event *re =3D *(const struct perf_event **)r; @@ -3691,7 +3691,7 @@ static bool perf_less_group_idx(const void *l, const = void *r) return le->group_index < re->group_index; } =20 -static void swap_ptr(void *l, void *r) +static void swap_ptr(void *l, void *r, void __always_unused *args) { void **lp =3D l, **rp =3D r; =20 @@ -3779,7 +3779,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } =20 - min_heapify_all(&event_heap, &perf_min_heap); + min_heapify_all(&event_heap, &perf_min_heap, NULL); =20 while (event_heap.heap.nr) { ret =3D func(*evt, data); @@ -3788,9 +3788,9 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap); + min_heapify(&event_heap, 0, &perf_min_heap, NULL); else - min_heap_pop(&event_heap, &perf_min_heap); + min_heap_pop(&event_heap, &perf_min_heap, NULL); } =20 return 0; diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index af2e446034d8..062e908e9fa3 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -13,17 +13,17 @@ =20 MIN_HEAP(int, min_heap_test); =20 -static __init bool less_than(const void *lhs, const void *rhs) +static __init bool less_than(const void *lhs, const void *rhs, void __alwa= ys_unused *args) { return *(int *)lhs < *(int *)rhs; } =20 -static __init bool greater_than(const void *lhs, const void *rhs) +static __init bool greater_than(const void *lhs, const void *rhs, void __a= lways_unused *args) { return *(int *)lhs > *(int *)rhs; } =20 -static __init void swap_ints(void *lhs, void *rhs) +static __init void swap_ints(void *lhs, void *rhs, void __always_unused *a= rgs) { int temp =3D *(int *)lhs; =20 @@ -40,7 +40,7 @@ static __init int pop_verify_heap(bool min_heap, int last; =20 last =3D values[0]; - min_heap_pop(heap, funcs); + min_heap_pop(heap, funcs, NULL); while (heap->heap.nr > 0) { if (min_heap) { if (last > values[0]) { @@ -56,7 +56,7 @@ static __init int pop_verify_heap(bool min_heap, } } last =3D values[0]; - min_heap_pop(heap, funcs); + min_heap_pop(heap, funcs, NULL); } return err; } @@ -77,7 +77,7 @@ static __init int test_heapify_all(bool min_heap) int i, err; =20 /* Test with known set of values. */ - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 =20 @@ -86,7 +86,7 @@ static __init int test_heapify_all(bool min_heap) for (i =3D 0; i < heap.heap.nr; i++) values[i] =3D get_random_u32(); =20 - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 return err; @@ -110,14 +110,14 @@ static __init int test_heap_push(bool min_heap) =20 /* Test with known set of values copied from data. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &data[i], &funcs); + min_heap_push(&heap, &data[i], &funcs, NULL); =20 err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 /* Test with randomly generated values. */ while (heap.heap.nr < heap.heap.size) { temp =3D get_random_u32(); - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); } err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 @@ -143,22 +143,22 @@ static __init int test_heap_pop_push(bool min_heap) /* Fill values with data to pop and replace. */ temp =3D min_heap ? 0x80000000 : 0x7FFFFFFF; for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); =20 /* Test with known set of values copied from data. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_pop_push(&heap, &data[i], &funcs); + min_heap_pop_push(&heap, &data[i], &funcs, NULL); =20 err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 heap.heap.nr =3D 0; for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); =20 /* Test with randomly generated values. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) { temp =3D get_random_u32(); - min_heap_pop_push(&heap, &temp, &funcs); + min_heap_pop_push(&heap, &temp, &funcs, NULL); } err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f180.google.com (mail-pl1-f180.google.com [209.85.214.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 CD54E50249; Wed, 20 Mar 2024 14:55:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946519; cv=none; b=qZ8X+11laInzDHOUKNynAXet+9yJxprqTz4TyQhyAWUNqnzUFL2z0kVhnvr2x6+jWyE/Ze+ncfw4HpA4qnvl39PaF0ztaQyBJSDQ+9WbXra9rth9LIQdJ8WOEuujMLhuqBPFlcJCTCpB5J/bUyNEIXHpIHfN0DGb8OJzw+ky4hk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946519; c=relaxed/simple; bh=syfYOYnUwJ/5pwXO5mVU6Pp5rxMGLYlg5kt0rZBWh54=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=sE2R4QyS19swMh7Ian1/L6xTJuxM+5C2ETxQM7HXeMIU4OS4wTq2Vb6jLVpG2m96TBPDazOZjtM1Slqz9M6CnrlCOHqfcQQKzGDBdHcHW/wJg/6a0dKYwkzlKsFyMVkz9Xl4piVHr7o4Gv7aNsJNRybCemwbH2YHqOn0KQDIdrY= 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=mDdxyqsA; arc=none smtp.client-ip=209.85.214.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="mDdxyqsA" Received: by mail-pl1-f180.google.com with SMTP id d9443c01a7336-1def81ee762so9761025ad.0; Wed, 20 Mar 2024 07:55:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946517; x=1711551317; 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=cESTsZP2b4VWyk/Zv78LUG0DCiwWqDlR4UPH+ifArVI=; b=mDdxyqsAqH30h6hhKeEEnoiq49V1YJ+0agI6zENvZAZxWoaoHPfx9r6qEMJfWktF4L IucScylHFmSsyb5UfbxBc0Vq2+jTgACxdv6isAe/noQ3W/RtVWp8Yqwz0WWwvp+SaG+t WD1K1krEoYV4xmIxbJKuiyWufHZP30iYhs/QvAw9qEZWm01Cdldfdj4J/IUfDX9dtyCY x2dJTR5h8k3BBi49cvuBUViB7lXxWPau4459wj0W3hQIKX9E2TBVHrrDikYj1JN8IrmH kD54LBLboQYuyc13Kfhu7V23MaipTGVf/ITxTuNcArSvKGAirLB3DeDIbCOprMMyjqhp hwyw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946517; x=1711551317; 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=cESTsZP2b4VWyk/Zv78LUG0DCiwWqDlR4UPH+ifArVI=; b=o50FQM5RdmP7Ql5NDjpBUisqCaz79uKwOPGtZ1cJvdhuMvvg50//ILpdr3Qde1jkIz xKIXc4wx5XXxPJfIh20B+F880hg5Vuxcs5p7GBG+z0tt+hYGTs632K1asi0ObG4UVQ+0 3SPp10/BJDmvJytJi1T3g9cFq12ofp1S+XYfGTWVNgv2BjHR/4jJRTY/WwdGuzTVApMA 7TLkrO+DF6fJP2YF8+O3Bnc0HY/TEPiJ+wxBL0pAHogR1x/OkDf4MJNstKgq0JQOJF6S Oy7CzFD+vq14ul34yLZWTt3ISYyvVcrEeKaEKdh6lk1ipc17VVMxEnAZvQjiZ9Vbqu4j KXHA== X-Forwarded-Encrypted: i=1; AJvYcCWncLqloJZuepHnLcvfh3Zz9nV6kcRq/Skr7HlX5/lBd7cFrSOjxVUi7PFbszQKtD36c32Nq+hvlES44itBOewMp5y1i+wUMU3iR00NME/qK/DLJNGiq9ds7LX7AmHeeXO+WmXg/iLomDzSlBzh24fqq7vcmlglrSaYyB6SzfWw7CCrTCWblN/cXNfGQlzlqZ3cKzgB12TfIfmy2wjxoymxqOBIfcqFKuJ61Glr X-Gm-Message-State: AOJu0Yz4+fjSWZKwafIgfAxqtjXYf5oV1csrf7I+e+jec+EWefnx1z4g TSZxsl9gdFDCfUdekrCjX258X23ttdZ6Ihm8st97flQmnNC+d7Ky X-Google-Smtp-Source: AGHT+IFyBgv5oFc1N7tzqDalBpTJCZL08QL7Xi0JuKEsJZmPb5q63CmqPKSNUk+sFsubtLKiucyg1g== X-Received: by 2002:a17:903:2292:b0:1dd:5a49:7a98 with SMTP id b18-20020a170903229200b001dd5a497a98mr6117689plh.3.1710946517076; Wed, 20 Mar 2024 07:55:17 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:16 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 11/15] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Date: Wed, 20 Mar 2024 22:54:13 +0800 Message-Id: <20240320145417.336208-12-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Modify the min_heap_push() and min_heap_pop() to return a boolean value. They now return false when the operation fails and true when it succeeds. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 879a9d12e030..586965977104 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -130,18 +130,20 @@ void __min_heapify_all(struct __min_heap *heap, size_= t elem_size, =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_pop(struct __min_heap *heap, size_t elem_size, +bool __min_heap_pop(struct __min_heap *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) - return; + return false; =20 /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); __min_heapify(heap, 0, elem_size, func, args); + + return true; } =20 #define min_heap_pop(_heap, _func, _args) \ @@ -167,7 +169,7 @@ void __min_heap_pop_push(struct __min_heap *heap, =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void __min_heap_push(struct __min_heap *heap, const void *element, size_t = elem_size, +bool __min_heap_push(struct __min_heap *heap, const void *element, size_t = elem_size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; @@ -175,7 +177,7 @@ void __min_heap_push(struct __min_heap *heap, const voi= d *element, size_t elem_s int pos; =20 if (WARN_ONCE(heap->nr >=3D heap->size, "Pushing on a full heap")) - return; + return false; =20 /* Place at the end of data. */ pos =3D heap->nr; @@ -190,6 +192,8 @@ void __min_heap_push(struct __min_heap *heap, const voi= d *element, size_t elem_s break; func->swp(parent, child, args); } + + return true; } =20 #define min_heap_push(_heap, _element, _func, _args) \ --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (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 8CAB15FB9C; Wed, 20 Mar 2024 14:55:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946524; cv=none; b=Z8xgwHojBLRW3jeTn169YtzWMLHRZcVSO2g9PXqPuPk6UGaoXThzDta0SrAJzUi/HsPm4ToEvBsmY6iTPutlfWT1CFT3KujaPWhEbPB3b08bfu417EyrsOJt/O+Tbkvso5eolyUnlOsfLb7KxJifoM77PHPJzTlJQUnajbti9e4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946524; c=relaxed/simple; bh=nCQxYZsgsRAx/5f4AE04kZbnhBIilxiKGZiKSwq7sAs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fkuDRB/eC2WNUf9sacnHPSOfhw9oCyfWfScMwrxV22ObWFLbNhpoSjkb6EesyhW+93j4wnSVtKMY8XGBpO9Z9fsVh2dNpihFbhEv9gXRe6InZHKrQIEy8/IG9NSV2qUXOPr1nZjNT6mqWThf7RG2+z7NAusSp27N300WQUqopSc= 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=Pqzek390; arc=none smtp.client-ip=209.85.214.179 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="Pqzek390" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1def81ee762so9761165ad.0; Wed, 20 Mar 2024 07:55:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946522; x=1711551322; 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=HQTQoXpl9kZmZcCaoDjVcMBQxJEeqtUU5fbEvGOwL9A=; b=Pqzek3907vBez4C6PSU8c5k5qPitMFXDKkDx/0CDqia1xxxxcY9EU6rSavJLUq63CX 40cpRtaha3vdrFAMOibZE7wwdvLpVyyMZb4wXoOGn1JQfE2x+ykVPe6FtqnJmK42eeHu JBDXQA/IKHbfG7VUb8gJuxufHmia9cbycabL15Kkiw56qbdNpRAl5KO7mD0iMgmh2Xzj tHJ75L1pUj68hVycINwRX/G5+88V+PxWC4bo8eJV2tiOm1xQKaFLpmrHpMP0AJFUcljG Crg4XgBU1OAhNYOPsy700S+noOHpPrrsV8nc6Ixbmp8zF4yL8PXDns6z8z4AlpMvpl5n mbUA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946522; x=1711551322; 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=HQTQoXpl9kZmZcCaoDjVcMBQxJEeqtUU5fbEvGOwL9A=; b=ItnT1XroVrVFI8yiigvzTJOirGQARFZEitA+Jwe+6g7dNJSThpnpBiPKiELVOopOt1 5rlfR0ekuCKXSmVLU3KTQYYprBy+e11aH3lcV98C4JhlqduMcYxLnSLzobs0cqq++RHd ZsyPY2ejSdJhlLnG2gnnSxmeDL97aQCdP6Br4SvF2fw57mvSdeiseGtrSeT3uUQMH2Uw U0ph56iWkL3RMdHw7eW4YPHxiLQTAAsSsLz1Av7q0OFzhJoxQAMl7D7AnO24JGlJ9/YD WoN320wcQru/agvQRFGrDkzf5ZMhrGyw1C42Tmhsw8PEhjnS4WKqn/TnWcU3GaqRi3IG D4fg== X-Forwarded-Encrypted: i=1; AJvYcCVmuIm16/q2bceSu2gkc/P2jXNb2N39MCXqBhnB9r+Vetm/PvKf/XyUfGKIuGxyAQ3ytbc9g5cJ0glpFw7U0LpAn9VZOdzSA+9pGYq/tQf2pU+SJbAEn4bzQ57UdWfA0F2sOFf0MUX52TqJh0LcmupMhIC041VizSEUnTtTbWYkNP3QjK5tUxfHIn1WxuZs54vuNy7a+1Nv2+eqeybkbqFsB0OYUNxQNdoxk+JY X-Gm-Message-State: AOJu0Yz+lULmhkS5RXUEjR7w0QrohCyoK+WYUcQ59BO9gMk9N/PWSxpM T2NyzRBEffqdLKWwKRQPleXwUUVsmJwT1QEz/HCpCsv1nbQ5FtRn X-Google-Smtp-Source: AGHT+IEVgULr7fKahVSqb9Mn8wh/rmuWNNtX4qJfG3yVKS6HTCYRncGWrGCpJXxKSTFPl2pdaEjEKw== X-Received: by 2002:a17:902:c94d:b0:1dc:e469:6f5d with SMTP id i13-20020a170902c94d00b001dce4696f5dmr6104360pla.4.1710946521802; Wed, 20 Mar 2024 07:55:21 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:21 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 12/15] lib min_heap: Rename min_heapify() to min_heap_sift_down() Date: Wed, 20 Mar 2024 22:54:14 +0800 Message-Id: <20240320145417.336208-13-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" After adding min_heap_sift_up(), the naming convention has been adjusted to maintain consistency with the min_heap_sift_up(). Consequently, min_heapify() has been renamed to min_heap_sift_down(). Link: https://lkml.kernel.org/CAP-5=3DfVcBAxt8Mw72=3DNCJPRJfjDaJcqk4rjbadgo= uAEAHz_q1A@mail.gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/dm-vdo/repair.c | 2 +- include/linux/min_heap.h | 14 +++++++------- kernel/events/core.c | 2 +- 3 files changed, 9 insertions(+), 9 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index 6acaebcd305d..e99f908bbdb9 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -183,7 +183,7 @@ static struct numbered_block_mapping *sort_next_heap_el= ement(struct repair_compl */ last =3D &repair->entries[--heap->heap.nr]; swap_mappings(heap->heap.data, last, NULL); - min_heapify(heap, 0, &repair_min_heap, NULL); + min_heap_sift_down(heap, 0, &repair_min_heap, NULL); return last; } =20 diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 586965977104..436997070f4e 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -78,7 +78,7 @@ bool __min_heap_full(struct __min_heap *heap) =20 /* Sift the element at pos down the heap. */ static __always_inline -void __min_heapify(struct __min_heap *heap, int pos, size_t elem_size, +void __min_heap_sift_down(struct __min_heap *heap, int pos, size_t elem_si= ze, const struct min_heap_callbacks *func, void *args) { void *left, *right; @@ -111,8 +111,8 @@ void __min_heapify(struct __min_heap *heap, int pos, si= ze_t elem_size, } } =20 -#define min_heapify(_heap, _pos, _func, _args) \ - __min_heapify(&(_heap)->heap, _pos, __minheap_obj_size(_heap), _func, _ar= gs) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down(&(_heap)->heap, _pos, __minheap_obj_size(_heap), _fu= nc, _args) =20 /* Floyd's approach to heapification that is O(nr). */ static __always_inline @@ -122,7 +122,7 @@ void __min_heapify_all(struct __min_heap *heap, size_t = elem_size, int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heapify(heap, i, elem_size, func, args); + __min_heap_sift_down(heap, i, elem_size, func, args); } =20 #define min_heapify_all(_heap, _func, _args) \ @@ -141,7 +141,7 @@ bool __min_heap_pop(struct __min_heap *heap, size_t ele= m_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_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); =20 return true; } @@ -161,7 +161,7 @@ void __min_heap_pop_push(struct __min_heap *heap, void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); } =20 #define min_heap_pop_push(_heap, _element, _func, _args) \ @@ -235,7 +235,7 @@ bool __min_heap_del(struct __min_heap *heap, size_t ele= m_size, size_t idx, return true; memcpy(data, data + (heap->nr * elem_size), elem_size); __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_heapify(heap, idx, elem_size, func, args); + __min_heap_sift_down(heap, idx, elem_size, func, args); =20 return true; } diff --git a/kernel/events/core.c b/kernel/events/core.c index c32a78c489f3..314fb7ea4ec3 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3788,7 +3788,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap, NULL); + min_heap_sift_down(&event_heap, 0, &perf_min_heap, NULL); else min_heap_pop(&event_heap, &perf_min_heap, NULL); } --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (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 6DA315FDA7; Wed, 20 Mar 2024 14:55:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946528; cv=none; b=jUyse1GOOH2ldmUZQCYfR7Ujtj2fO6mmRfzsIhyiUal/JhSXtuNLotDUlNdxPzavP3ImdhDF1ZliUD6uRccyGp3jpekxvKVUDfjeJp3dTaSUfkDP/aMig7Bpz3y9KBdsrJ5lrdgN4Z/R7CttZowGPE/IehfJhYZ1GIwUSo1DnuA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946528; c=relaxed/simple; bh=GQUVsfUcpz8LUorm5To23Yew7xCHJVZumueYQTygjj8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=bRwEFiBfKxFslTswaYYIp3VyK4JIhjIoBY6fj1nDL+K8eHMq2SxGm4JsZ6zr9+HmGN5IeB/oJEXw1mMR1qXTrCqGbRVhsOqter4R4URCZHLQycIe4xdtokq88pOw1u7ihrpPWAx+MqnZAjCmh+CXYjqcMaRSCcbLXe5Bwh/Gyx0= 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=nqVyH86y; arc=none smtp.client-ip=209.85.214.175 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="nqVyH86y" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-1dee6672526so6080105ad.1; Wed, 20 Mar 2024 07:55:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946526; x=1711551326; 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=zmVSQEC3TeRF4GcV4dCeypJopsqrkB0AwEs9FDrz4eI=; b=nqVyH86yJct1WUode4SMJgT5vFb7XnuI05Ro7iDK/ad4PbdFPsZXfzbxVx8ivkIhxj gXG0PybtYydj/yuuIVGrvD10q6vu8WVPqU3cJ8Vjiqb7Gc4uUfQ0+XTAV23PBSVqshKy Ed2VgaJxOmvAQhCc8TQupzZ85lj7P1Ki1JOqOsRW2WkWk66cUHCItBsLilSO/r8CPFXZ P8A6FMCHf+Xj30IFpyirx13HtRvMSgpARyUVl+7rPzyn1d1kWj5mbTK6yo3dj0/I7SV+ pwZjYE+XJBocjUEwVCS/UbWrCnhLjDnxJcbNnxSfR0/jmlBjIqqZjeE/RKdPXNrI2XvC m15g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946526; x=1711551326; 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=zmVSQEC3TeRF4GcV4dCeypJopsqrkB0AwEs9FDrz4eI=; b=kj0zMCk5ZgRGySOyqlNeQ0myGX+hbc7ZK3qUtqwBq7GY8K6YiMuGG11lVJd+AIqWJb 6qOjcg/AelFwwK9jV7sOeIA5hpzoXaxvfDvdsbuJ2oFb9sND6eIag3L17nVfeURgi6HJ gtxJm/hFLZiwzVQW/N1xEWAMnF6aLd0sylZx82SkAxFs9XygepsZp3cxTxoJn8o75c4C 9VGkzRFCVBDxMwAGTXYfmXOYOUHS7L6pNOWp80i7YWX4+jK6iKDH0eHP0KaMoyqLZntN LAAAgkjm+8MtqAhbVLe2SIrxff7FQx3iIeVbBL/3qu5UFZayLwCTjJZ+4iFIQzMidIKd JvDA== X-Forwarded-Encrypted: i=1; AJvYcCXr7ajBnrZLgaV3iRre5K/lRsGGj83LQyXkMQbMi5aQDwuRATVUj6B2O9nYXYh0bzVNtZlZ9WQOngc+5H79pHWe10mTeNmf9H3k2lPUYuLSaAqxQApeQNaqyxHza3xTwOyUwpBQWhrPIPtYTcG8Qggw12GRWs1jAUrlRYORCFWpdCphb3nkHaVZL7L7hwh6FEUCKNKfNualgF98v9+75tsiIUB+5SHmB54H9PHa X-Gm-Message-State: AOJu0YwCHZy67y1CXU1OYEImGzM1Spy+SbAexhoxoW9sXbpYpIeMLIUk +gpzPang+1dJ4b1lYwbjO8BsiG7si24m5ILf2SMpNdEXvg5sY1jP X-Google-Smtp-Source: AGHT+IH+g3VQKU1UT+u7hlzLEfuAex2ovVYbYrYQpeOaTt68BlJN4QEvWb+lKyawL0mHCNYzU4yQXQ== X-Received: by 2002:a17:903:1c1:b0:1dd:7c4c:c6b6 with SMTP id e1-20020a17090301c100b001dd7c4cc6b6mr19251572plh.5.1710946526585; Wed, 20 Mar 2024 07:55:26 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:26 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 13/15] lib/test_min_heap: Use min_heap_init() for initializing Date: Wed, 20 Mar 2024 22:54:15 +0800 Message-Id: <20240320145417.336208-14-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Replace direct assignment of values to heap data members with min_heap_init() for better code readability and maintainability. Link: https://lkml.kernel.org/CAP-5=3DfW+FvUu8JL+KrtVv5uC++4AW=3DVhyEOgmdWz= pH1mswQNzw@mail.gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- lib/test_min_heap.c | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 062e908e9fa3..8d25fc8256db 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -67,9 +67,8 @@ static __init int test_heapify_all(bool min_heap) -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; struct min_heap_test heap; =20 - heap.heap.data =3D values; + min_heap_init(&heap, values, ARRAY_SIZE(values)); heap.heap.nr =3D ARRAY_SIZE(values); - heap.heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, @@ -99,9 +98,7 @@ static __init int test_heap_push(bool min_heap) int values[ARRAY_SIZE(data)]; struct min_heap_test heap; =20 - heap.heap.data =3D values; - heap.heap.nr =3D 0; - heap.heap.size =3D ARRAY_SIZE(values); + min_heap_init(&heap, values, ARRAY_SIZE(values)); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, @@ -131,9 +128,7 @@ static __init int test_heap_pop_push(bool min_heap) int values[ARRAY_SIZE(data)]; struct min_heap_test heap; =20 - heap.heap.data =3D values; - heap.heap.nr =3D 0; - heap.heap.size =3D ARRAY_SIZE(values); + min_heap_init(&heap, values, ARRAY_SIZE(values)); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pg1-f172.google.com (mail-pg1-f172.google.com [209.85.215.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 0A6AF5FDDB; Wed, 20 Mar 2024 14:55:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946534; cv=none; b=CkSleJWXfnUH+DUMwy966+FWMO7xp3JTiLAnUg4szxFUFNRrxUwFNbjaFHrpS6FtnWxPTMwfloryXzN6DxJ88Vg4CJxu+90EdbvtiAGYZWh0vCMPw6VbebYVz9xmKnzvJv5kcg0Y8rk6l3Qjg8ojEOD50qRQxJNCURXSemlDG+E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946534; c=relaxed/simple; bh=XPBSJLpKhIFdDr4h5vdSQJNEYqSbkGLLU2EsYDWg2NE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=u1TaSS99VQBEQuIT2GakBWybt/F0TmYzSYb5iu+NIEtOhwZ1Ys3SvktegneUBoczIv+kSu0WxG6iEd7+avCXju847mFresqOXd62CAT8DLXA3B+mykCWXaJ9YjEZydl8vrGMdhJKQA/khlf6Jsr3A3aSItptFE09H7AbvAcm6PQ= 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=Wp7fuEzJ; arc=none smtp.client-ip=209.85.215.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="Wp7fuEzJ" Received: by mail-pg1-f172.google.com with SMTP id 41be03b00d2f7-55b5a37acb6so1194291a12.0; Wed, 20 Mar 2024 07:55:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946531; x=1711551331; 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=+g/jsUIA9chYeIMSbZAKeaEXN1CLFxPlPEM36JCClAk=; b=Wp7fuEzJODPpb0IVUuZDKg4OK+T2HFFZ1/a72PYFeJmrdC4oQ1td+zD+xllayIdhtC 6mtko8Wuo30Rem4/D2Syg4Nbn+bV5NOUBHvpp/GrKdsWnUaGGv9i/Iem69gDO4opAoVX nhPqaJTjUtYSVB723Ei3JA+YkuQWlbYRlEUePo7Lawq53VF1Z1qCf7ag6/pchqwDbkdR pZXem53fcnOvgpe2YN1iyEjQWUDUCt2q8AKib5Y2JfLNDyon3aAfVN4GGeVRxi/FKewd JEl+oirn3RlTTtmaoORZouCsaVxnv9u/IeTLnDn/YSxDu2p6NiExzAwGUHj/H7sn/maJ QuMQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946531; x=1711551331; 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=+g/jsUIA9chYeIMSbZAKeaEXN1CLFxPlPEM36JCClAk=; b=ZD/xbwDIZoPR4kQBP+8vu40PuxEFuhnmMDwcZi6FEeTqFbfL7wAhKE3s4rEYG7JD4k kjlU/lCF9sas8OYwUVgP7lxGLp936IGKk7WRP505PPxEpomkRbUViYAXRuNwNd403UZs AxaHmhvRqoqv2h4B4grrVVuKKGVhJUWTOVZtxe67SS7nOb8WwrGjo2RPBCA5C6UxQL5K WK0kedWruMKbnsK8w9Bu32t9Z7xCbdJ/JKMSTg004Wrcvi7itF1jfU0sgHVN/WGvuPRy f/h11T+naQLDeyV4v5pgDAZV6rpUjeqxr3Oj9s1bYA0tG8nkA5oXagVoEt8m0PxMR3YN miog== X-Forwarded-Encrypted: i=1; AJvYcCUb3eCzDMI6n1xeEhlnfZIh5ryH3fmHBBxRPOs5JUmkaqrmSpxUL+4SznLE+CEY4KsLJ2aQYBwQrjioTzUYhGNSP4dD+42sW3Vy63uFpZwAEboUW1S3Qc0b7e0B7mAZvZeY3Bi4RpBBJOIDDhnSNYpUJP4deWf+8mZhnfaE8IIm7AOoxzrGZKIR8RoWs9TKlqYMG7WI1qPmz1rRAB7DM3qJNvY8eXufMxDQBn58 X-Gm-Message-State: AOJu0YxeK9DkU0aAmHSAJctPmRsQsvpqY8m9g+YJXbKtXsza3xEBOraa zjnhwSfwqvE2nGtwAnQgnEVGaNIhmPa01CYmvnINsyKGRo8HPtYZ X-Google-Smtp-Source: AGHT+IHkDB1QY/3dhJ7IXzrCL/CmyWyqTlolHGWu9SVFgpAGC1TE3r84KQbk3o5N3/1JKCL68wqydg== X-Received: by 2002:a17:902:da92:b0:1de:e8ce:9d7a with SMTP id j18-20020a170902da9200b001dee8ce9d7amr1938503plx.5.1710946531332; Wed, 20 Mar 2024 07:55:31 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.27 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:30 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 14/15] bcache: Remove heap-related macros and switch to generic min_heap Date: Wed, 20 Mar 2024 22:54:16 +0800 Message-Id: <20240320145417.336208-15-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Drop the heap-related macros from bcache and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcache. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- Changes in v2: - Add attribute __always_unused to the compare and swap functions that do not use the args parameter. - Rename min_heapify() to min_heap_sift_down(). - Refine the commit message. drivers/md/bcache/alloc.c | 66 +++++++++++++++++++++-------- drivers/md/bcache/bcache.h | 2 +- drivers/md/bcache/bset.c | 73 ++++++++++++++++++++++---------- drivers/md/bcache/bset.h | 38 ++++++++++------- drivers/md/bcache/btree.c | 27 +++++++++++- drivers/md/bcache/extents.c | 44 ++++++++++++-------- drivers/md/bcache/movinggc.c | 40 +++++++++++++----- drivers/md/bcache/super.c | 16 +++++++ drivers/md/bcache/sysfs.c | 3 ++ drivers/md/bcache/util.h | 81 +----------------------------------- 10 files changed, 224 insertions(+), 166 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index ce13c272c387..b27c0e25b661 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -166,40 +166,70 @@ static void bch_invalidate_one_bucket(struct cache *c= a, struct bucket *b) * prio is worth 1/8th of what INITIAL_PRIO is worth. */ =20 -#define bucket_prio(b) \ -({ \ - unsigned int min_prio =3D (INITIAL_PRIO - ca->set->min_prio) / 8; \ - \ - (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); \ -}) +static inline unsigned int bucket_prio(struct cache *ca, struct bucket *b) +{ + unsigned int min_prio =3D (INITIAL_PRIO - ca->set->min_prio) / 8; + + return (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); + +} + +static inline bool bucket_max_cmp(const void *l, const void *r, void *args) +{ + struct bucket *lhs =3D (struct bucket *)l; + struct bucket *rhs =3D (struct bucket *)r; + struct cache *ca =3D args; + + return bucket_prio(ca, lhs) > bucket_prio(ca, rhs); +} + +static inline bool bucket_min_cmp(const void *l, const void *r, void *args) +{ + struct bucket *lhs =3D (struct bucket *)l; + struct bucket *rhs =3D (struct bucket *)r; + struct cache *ca =3D args; + + return bucket_prio(ca, lhs) < bucket_prio(ca, rhs); +} + +static inline void bucket_swap(void *l, void *r, void __always_unused *arg= s) +{ + struct bucket *lhs =3D l, *rhs =3D r; =20 -#define bucket_max_cmp(l, r) (bucket_prio(l) < bucket_prio(r)) -#define bucket_min_cmp(l, r) (bucket_prio(l) > bucket_prio(r)) + swap(*lhs, *rhs); +} =20 static void invalidate_buckets_lru(struct cache *ca) { struct bucket *b; - ssize_t i; + const struct min_heap_callbacks bucket_max_cmp_callback =3D { + .less =3D bucket_max_cmp, + .swp =3D bucket_swap, + }; + const struct min_heap_callbacks bucket_min_cmp_callback =3D { + .less =3D bucket_min_cmp, + .swp =3D bucket_swap, + }; =20 - ca->heap.used =3D 0; + ca->heap.heap.nr =3D 0; =20 for_each_bucket(b, ca) { if (!bch_can_invalidate_bucket(ca, b)) continue; =20 - if (!heap_full(&ca->heap)) - heap_add(&ca->heap, b, bucket_max_cmp); - else if (bucket_max_cmp(b, heap_peek(&ca->heap))) { - ca->heap.data[0] =3D b; - heap_sift(&ca->heap, 0, bucket_max_cmp); + if (!min_heap_full(&ca->heap)) + min_heap_push(&ca->heap, b, &bucket_max_cmp_callback, ca); + else if (!bucket_max_cmp(b, min_heap_peek(&ca->heap), ca)) { + *min_heap_peek(&ca->heap) =3D b; + min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca); } } =20 - for (i =3D ca->heap.used / 2 - 1; i >=3D 0; --i) - heap_sift(&ca->heap, i, bucket_min_cmp); + min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca); =20 while (!fifo_full(&ca->free_inc)) { - if (!heap_pop(&ca->heap, b, bucket_min_cmp)) { + b =3D *min_heap_peek(&ca->heap); + if (!min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca)) { /* * We don't want to be calling invalidate_buckets() * multiple times when it can't do anything diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h index 4e6afa89921f..97b0a1768ba7 100644 --- a/drivers/md/bcache/bcache.h +++ b/drivers/md/bcache/bcache.h @@ -457,7 +457,7 @@ struct cache { /* Allocation stuff: */ struct bucket *buckets; =20 - DECLARE_HEAP(struct bucket *, heap); + MIN_HEAP(struct bucket *, heap) heap; =20 /* * If nonzero, we know we aren't going to find any buckets to invalidate diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index 2bba4d6aaaa2..6b1c8ac0f866 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -56,7 +56,9 @@ int __bch_count_data(struct btree_keys *b) unsigned int ret =3D 0; struct btree_iter iter; struct bkey *k; + struct btree_iter_set data[MAX_BSETS]; =20 + iter.heap.heap.data =3D data; if (b->ops->is_extents) for_each_key(b, k, &iter) ret +=3D KEY_SIZE(k); @@ -69,6 +71,9 @@ void __bch_check_keys(struct btree_keys *b, const char *f= mt, ...) struct bkey *k, *p =3D NULL; struct btree_iter iter; const char *err; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 for_each_key(b, k, &iter) { if (b->ops->is_extents) { @@ -110,9 +115,9 @@ void __bch_check_keys(struct btree_keys *b, const char = *fmt, ...) =20 static void bch_btree_iter_next_check(struct btree_iter *iter) { - struct bkey *k =3D iter->data->k, *next =3D bkey_next(k); + struct bkey *k =3D min_heap_peek(&iter->heap)->k, *next =3D bkey_next(k); =20 - if (next < iter->data->end && + if (next < min_heap_peek(&iter->heap)->end && bkey_cmp(k, iter->b->ops->is_extents ? &START_KEY(next) : next) > 0) { bch_dump_bucket(iter->b); @@ -882,6 +887,9 @@ unsigned int bch_btree_insert_key(struct btree_keys *b,= struct bkey *k, struct btree_iter iter; struct bkey preceding_key_on_stack =3D ZERO_KEY; struct bkey *preceding_key_p =3D &preceding_key_on_stack; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); =20 @@ -1077,27 +1085,34 @@ struct bkey *__bch_bset_search(struct btree_keys *b= , struct bset_tree *t, =20 /* Btree iterator */ =20 -typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, - struct btree_iter_set); +typedef bool (btree_iter_cmp_fn)(const void *, const void *, void *); =20 -static inline bool btree_iter_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static inline bool btree_iter_cmp(const void *l, const void *r, void __alw= ays_unused *args) { - return bkey_cmp(l.k, r.k) > 0; + const struct btree_iter_set *_l =3D l; + const struct btree_iter_set *_r =3D r; + + return bkey_cmp(_l->k, _r->k) <=3D 0; } =20 static inline bool btree_iter_end(struct btree_iter *iter) { - return !iter->used; + return !iter->heap.heap.nr; } =20 void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end) { + const struct min_heap_callbacks callbacks =3D { + .less =3D btree_iter_cmp, + .swp =3D btree_iter_swap, + }; + if (k !=3D end) - BUG_ON(!heap_add(iter, - ((struct btree_iter_set) { k, end }), - btree_iter_cmp)); + BUG_ON(!min_heap_push(&iter->heap, + &((struct btree_iter_set){ k, end }), + &callbacks, + NULL)); } =20 static struct bkey *__bch_btree_iter_init(struct btree_keys *b, @@ -1107,8 +1122,8 @@ static struct bkey *__bch_btree_iter_init(struct btre= e_keys *b, { struct bkey *ret =3D NULL; =20 - iter->size =3D ARRAY_SIZE(iter->data); - iter->used =3D 0; + iter->heap.heap.size =3D MAX_BSETS; + iter->heap.heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG iter->b =3D b; @@ -1134,22 +1149,28 @@ static inline struct bkey *__bch_btree_iter_next(st= ruct btree_iter *iter, { struct btree_iter_set b __maybe_unused; struct bkey *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D cmp, + .swp =3D btree_iter_swap, + }; =20 if (!btree_iter_end(iter)) { bch_btree_iter_next_check(iter); =20 - ret =3D iter->data->k; - iter->data->k =3D bkey_next(iter->data->k); + ret =3D min_heap_peek(&iter->heap)->k; + min_heap_peek(&iter->heap)->k =3D bkey_next(min_heap_peek(&iter->heap)->= k); =20 - if (iter->data->k > iter->data->end) { + if (min_heap_peek(&iter->heap)->k > min_heap_peek(&iter->heap)->end) { WARN_ONCE(1, "bset was corrupt!\n"); - iter->data->k =3D iter->data->end; + min_heap_peek(&iter->heap)->k =3D min_heap_peek(&iter->heap)->end; } =20 - if (iter->data->k =3D=3D iter->data->end) - heap_pop(iter, b, cmp); + if (min_heap_peek(&iter->heap)->k =3D=3D min_heap_peek(&iter->heap)->end= ) { + b =3D *min_heap_peek(&iter->heap); + min_heap_pop(&iter->heap, &callbacks, NULL); + } else - heap_sift(iter, 0, cmp); + min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); } =20 return ret; @@ -1195,16 +1216,18 @@ static void btree_mergesort(struct btree_keys *b, s= truct bset *out, struct btree_iter *iter, bool fixup, bool remove_stale) { - int i; struct bkey *k, *last =3D NULL; BKEY_PADDED(k) tmp; bool (*bad)(struct btree_keys *, const struct bkey *) =3D remove_stale ? bch_ptr_bad : bch_ptr_invalid; + const struct min_heap_callbacks callbacks =3D { + .less =3D b->ops->sort_cmp, + .swp =3D btree_iter_swap, + }; =20 /* Heapify the iterator, using our comparison function */ - for (i =3D iter->used / 2 - 1; i >=3D 0; --i) - heap_sift(iter, i, b->ops->sort_cmp); + min_heapify_all(&iter->heap, &callbacks, NULL); =20 while (!btree_iter_end(iter)) { if (b->ops->sort_fixup && fixup) @@ -1295,7 +1318,9 @@ void bch_btree_sort_partial(struct btree_keys *b, uns= igned int start, size_t order =3D b->page_order, keys =3D 0; struct btree_iter iter; int oldsize =3D bch_count_data(b); + struct btree_iter_set data[MAX_BSETS]; =20 + iter.heap.heap.data =3D data; __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); =20 if (start) { @@ -1324,7 +1349,9 @@ void bch_btree_sort_into(struct btree_keys *b, struct= btree_keys *new, { uint64_t start_time =3D local_clock(); struct btree_iter iter; + struct btree_iter_set data[MAX_BSETS]; =20 + iter.heap.heap.data =3D data; bch_btree_iter_init(b, &iter, NULL); =20 btree_mergesort(b, new->set->data, &iter, false, true); diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index d795c84246b0..e9559486a4c5 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -152,6 +152,19 @@ struct btree_iter; struct btree_iter_set; struct bkey_float; =20 +/* Btree key iteration */ + +struct btree_iter_set { + struct bkey *k, *end; +}; + +struct btree_iter { +#ifdef CONFIG_BCACHE_DEBUG + struct btree_keys *b; +#endif + MIN_HEAP(struct btree_iter_set, btree_iter_heap) heap; +}; + #define MAX_BSETS 4U =20 struct bset_tree { @@ -187,8 +200,9 @@ struct bset_tree { }; =20 struct btree_keys_ops { - bool (*sort_cmp)(struct btree_iter_set l, - struct btree_iter_set r); + bool (*sort_cmp)(const void *l, + const void *r, + void *args); struct bkey *(*sort_fixup)(struct btree_iter *iter, struct bkey *tmp); bool (*insert_fixup)(struct btree_keys *b, @@ -258,6 +272,14 @@ static inline unsigned int bset_sector_offset(struct b= tree_keys *b, return bset_byte_offset(b, i) >> 9; } =20 +static inline void btree_iter_swap(void *iter1, void *iter2, void __always= _unused *args) +{ + struct btree_iter_set *_iter1 =3D iter1; + struct btree_iter_set *_iter2 =3D iter2; + + swap(*_iter1, *_iter2); +} + #define __set_bytes(i, k) (sizeof(*(i)) + (k) * sizeof(uint64_t)) #define set_bytes(i) __set_bytes(i, i->keys) =20 @@ -312,18 +334,6 @@ enum { BTREE_INSERT_STATUS_FRONT_MERGE, }; =20 -/* Btree key iteration */ - -struct btree_iter { - size_t size, used; -#ifdef CONFIG_BCACHE_DEBUG - struct btree_keys *b; -#endif - struct btree_iter_set { - struct bkey *k, *end; - } data[MAX_BSETS]; -}; - typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); =20 struct bkey *bch_btree_iter_next(struct btree_iter *iter); diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c index 196cdacce38f..e7333a8c4819 100644 --- a/drivers/md/bcache/btree.c +++ b/drivers/md/bcache/btree.c @@ -157,8 +157,8 @@ void bch_btree_node_read_done(struct btree *b) * See the comment arount cache_set->fill_iter. */ iter =3D mempool_alloc(&b->c->fill_iter, GFP_NOIO); - iter->size =3D b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; - iter->used =3D 0; + iter->heap.heap.size =3D b->c->cache->sb.bucket_size / b->c->cache->sb.bl= ock_size; + iter->heap.heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG iter->b =3D &b->keys; @@ -1311,6 +1311,9 @@ static bool btree_gc_mark_node(struct btree *b, struc= t gc_stat *gc) struct bkey *k; struct btree_iter iter; struct bset_tree *t; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 gc->nodes++; =20 @@ -1572,6 +1575,9 @@ static unsigned int btree_gc_count_keys(struct btree = *b) struct bkey *k; struct btree_iter iter; unsigned int ret =3D 0; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) ret +=3D bkey_u64s(k); @@ -1614,6 +1620,9 @@ static int btree_gc_recurse(struct btree *b, struct b= tree_op *op, struct btree_iter iter; struct gc_merge_info r[GC_MERGE_NODES]; struct gc_merge_info *i, *last =3D r + ARRAY_SIZE(r) - 1; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); =20 @@ -1912,6 +1921,9 @@ static int bch_btree_check_recurse(struct btree *b, s= truct btree_op *op) int ret =3D 0; struct bkey *k, *p =3D NULL; struct btree_iter iter; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(b->c, b->level, k); @@ -1953,7 +1965,9 @@ static int bch_btree_check_thread(void *arg) struct btree_iter iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; + struct btree_iter_set data[MAX_BSETS]; =20 + iter.heap.heap.data =3D data; k =3D p =3D NULL; cur_idx =3D prev_idx =3D 0; ret =3D 0; @@ -2053,6 +2067,9 @@ int bch_btree_check(struct cache_set *c) struct bkey *k =3D NULL; struct btree_iter iter; struct btree_check_state check_state; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 /* check and mark root node keys */ for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) @@ -2548,6 +2565,9 @@ static int bch_btree_map_nodes_recurse(struct btree *= b, struct btree_op *op, if (b->level) { struct bkey *k; struct btree_iter iter; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 bch_btree_iter_init(&b->keys, &iter, from); =20 @@ -2581,6 +2601,9 @@ int bch_btree_map_keys_recurse(struct btree *b, struc= t btree_op *op, int ret =3D MAP_CONTINUE; struct bkey *k; struct btree_iter iter; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 bch_btree_iter_init(&b->keys, &iter, from); =20 diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index d626ffcbecb9..8279596004f5 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -32,16 +32,19 @@ static void sort_key_next(struct btree_iter *iter, { i->k =3D bkey_next(i->k); =20 - if (i->k =3D=3D i->end) - *i =3D iter->data[--iter->used]; + if (i->k =3D=3D i->end) { + struct btree_iter_set *data =3D iter->heap.heap.data; + *i =3D data[--iter->heap.heap.nr]; + } } =20 -static bool bch_key_sort_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static bool bch_key_sort_cmp(const void *l, const void *r, void *args) { - int64_t c =3D bkey_cmp(l.k, r.k); + struct btree_iter_set *_l =3D (struct btree_iter_set *)l; + struct btree_iter_set *_r =3D (struct btree_iter_set *)r; + int64_t c =3D bkey_cmp(_l->k, _r->k); =20 - return c ? c > 0 : l.k < r.k; + return !(c ? c > 0 : _l->k < _r->k); } =20 static bool __ptr_invalid(struct cache_set *c, const struct bkey *k) @@ -255,22 +258,29 @@ const struct btree_keys_ops bch_btree_keys_ops =3D { * Necessary for btree_sort_fixup() - if there are multiple keys that comp= are * equal in different sets, we have to process them newest to oldest. */ -static bool bch_extent_sort_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static bool bch_extent_sort_cmp(const void *l, const void *r, void __alway= s_unused *args) { - int64_t c =3D bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); + struct btree_iter_set *_l =3D (struct btree_iter_set *)l; + struct btree_iter_set *_r =3D (struct btree_iter_set *)r; + + int64_t c =3D bkey_cmp(&START_KEY(_l->k), &START_KEY(_r->k)); =20 - return c ? c > 0 : l.k < r.k; + return !(c ? c > 0 : _l->k < _r->k); } =20 static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { - while (iter->used > 1) { - struct btree_iter_set *top =3D iter->data, *i =3D top + 1; + const struct min_heap_callbacks callbacks =3D { + .less =3D bch_extent_sort_cmp, + .swp =3D btree_iter_swap, + }; + + while (iter->heap.heap.nr > 1) { + struct btree_iter_set *top =3D min_heap_peek(&iter->heap), *i =3D top + = 1; =20 - if (iter->used > 2 && - bch_extent_sort_cmp(i[0], i[1])) + if (iter->heap.heap.nr > 2 && + !bch_extent_sort_cmp(&i[0], &i[1], NULL)) i++; =20 if (bkey_cmp(top->k, &START_KEY(i->k)) <=3D 0) @@ -278,7 +288,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, =20 if (!KEY_SIZE(i->k)) { sort_key_next(iter, i); - heap_sift(iter, i - top, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); continue; } =20 @@ -288,7 +298,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, else bch_cut_front(top->k, i->k); =20 - heap_sift(iter, i - top, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); } else { /* can't happen because of comparison func */ BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k))); @@ -298,7 +308,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, =20 bch_cut_back(&START_KEY(i->k), tmp); bch_cut_front(i->k, top->k); - heap_sift(iter, 0, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); =20 return tmp; } else { diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index ebd500bdf0b2..0f50192fea2c 100644 --- a/drivers/md/bcache/movinggc.c +++ b/drivers/md/bcache/movinggc.c @@ -182,16 +182,27 @@ err: if (!IS_ERR_OR_NULL(w->private)) closure_sync(&cl); } =20 -static bool bucket_cmp(struct bucket *l, struct bucket *r) +static bool bucket_cmp(const void *l, const void *r, void __always_unused = *args) { - return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); + struct bucket *_l =3D (struct bucket *)l; + struct bucket *_r =3D (struct bucket *)r; + + return GC_SECTORS_USED(_l) >=3D GC_SECTORS_USED(_r); +} + +static void bucket_swap(void *l, void *r, void __always_unused *args) +{ + struct bucket *_l =3D l; + struct bucket *_r =3D r; + + swap(*_l, *_r); } =20 static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; =20 - return (b =3D heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; + return (b =3D *min_heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; } =20 void bch_moving_gc(struct cache_set *c) @@ -199,6 +210,10 @@ void bch_moving_gc(struct cache_set *c) struct cache *ca =3D c->cache; struct bucket *b; unsigned long sectors_to_move, reserve_sectors; + const struct min_heap_callbacks callbacks =3D { + .less =3D bucket_cmp, + .swp =3D bucket_swap, + }; =20 if (!c->copy_gc_enabled) return; @@ -209,7 +224,7 @@ void bch_moving_gc(struct cache_set *c) reserve_sectors =3D ca->sb.bucket_size * fifo_used(&ca->free[RESERVE_MOVINGGC]); =20 - ca->heap.used =3D 0; + ca->heap.heap.nr =3D 0; =20 for_each_bucket(b, ca) { if (GC_MARK(b) =3D=3D GC_MARK_METADATA || @@ -218,25 +233,28 @@ void bch_moving_gc(struct cache_set *c) atomic_read(&b->pin)) continue; =20 - if (!heap_full(&ca->heap)) { + if (!min_heap_full(&ca->heap)) { sectors_to_move +=3D GC_SECTORS_USED(b); - heap_add(&ca->heap, b, bucket_cmp); - } else if (bucket_cmp(b, heap_peek(&ca->heap))) { + min_heap_push(&ca->heap, b, &callbacks, NULL); + } else if (!bucket_cmp(b, min_heap_peek(&ca->heap), NULL)) { sectors_to_move -=3D bucket_heap_top(ca); sectors_to_move +=3D GC_SECTORS_USED(b); =20 - ca->heap.data[0] =3D b; - heap_sift(&ca->heap, 0, bucket_cmp); + *min_heap_peek(&ca->heap) =3D b; + min_heap_sift_down(&ca->heap, 0, &callbacks, NULL); } } =20 while (sectors_to_move > reserve_sectors) { - heap_pop(&ca->heap, b, bucket_cmp); + b =3D *min_heap_peek(&ca->heap); + min_heap_pop(&ca->heap, &callbacks, NULL); sectors_to_move -=3D GC_SECTORS_USED(b); } =20 - while (heap_pop(&ca->heap, b, bucket_cmp)) + while ((b =3D *min_heap_peek(&ca->heap))) { + min_heap_pop(&ca->heap, &callbacks, NULL); SET_GC_MOVE(b, 1); + } =20 mutex_unlock(&c->bucket_lock); =20 diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c index 330bcd9ea4a9..1c6aeeff2cc3 100644 --- a/drivers/md/bcache/super.c +++ b/drivers/md/bcache/super.c @@ -2193,6 +2193,22 @@ static const char *register_cache_set(struct cache *= ca) return err; } =20 +static inline bool init_heap(struct heap *heap, size_t size, gfp_t gfp) +{ + size_t bytes =3D size * sizeof(struct bucket *); + void *data =3D kvmalloc(bytes, (gfp) & GFP_KERNEL); + + min_heap_init(heap, data, size); + + return data; +} + +static inline void free_heap(struct heap *heap) +{ + kvfree(heap->heap.data); + heap->heap.data =3D NULL; +} + /* Cache device */ =20 /* When ca->kobj released */ diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c index 6956beb55326..eac2039c2cad 100644 --- a/drivers/md/bcache/sysfs.c +++ b/drivers/md/bcache/sysfs.c @@ -661,6 +661,9 @@ static unsigned int bch_root_usage(struct cache_set *c) struct bkey *k; struct btree *b; struct btree_iter iter; + struct btree_iter_set data[MAX_BSETS]; + + iter.heap.heap.data =3D data; =20 goto lock_root; =20 diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h index f61ab1bada6c..fa928d1d327a 100644 --- a/drivers/md/bcache/util.h +++ b/drivers/md/bcache/util.h @@ -7,6 +7,7 @@ #include #include #include +#include #include #include #include @@ -30,86 +31,6 @@ struct closure; =20 #endif =20 -#define DECLARE_HEAP(type, name) \ - struct { \ - size_t size, used; \ - type *data; \ - } name - -#define init_heap(heap, _size, gfp) \ -({ \ - size_t _bytes; \ - (heap)->used =3D 0; \ - (heap)->size =3D (_size); \ - _bytes =3D (heap)->size * sizeof(*(heap)->data); \ - (heap)->data =3D kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ - (heap)->data; \ -}) - -#define free_heap(heap) \ -do { \ - kvfree((heap)->data); \ - (heap)->data =3D NULL; \ -} while (0) - -#define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j]) - -#define heap_sift(h, i, cmp) \ -do { \ - size_t _r, _j =3D i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j =3D _r) { \ - _r =3D _j * 2 + 1; \ - if (_r + 1 < (h)->used && \ - cmp((h)->data[_r], (h)->data[_r + 1])) \ - _r++; \ - \ - if (cmp((h)->data[_r], (h)->data[_j])) \ - break; \ - heap_swap(h, _r, _j); \ - } \ -} while (0) - -#define heap_sift_down(h, i, cmp) \ -do { \ - while (i) { \ - size_t p =3D (i - 1) / 2; \ - if (cmp((h)->data[i], (h)->data[p])) \ - break; \ - heap_swap(h, i, p); \ - i =3D p; \ - } \ -} while (0) - -#define heap_add(h, d, cmp) \ -({ \ - bool _r =3D !heap_full(h); \ - if (_r) { \ - size_t _i =3D (h)->used++; \ - (h)->data[_i] =3D d; \ - \ - heap_sift_down(h, _i, cmp); \ - heap_sift(h, _i, cmp); \ - } \ - _r; \ -}) - -#define heap_pop(h, d, cmp) \ -({ \ - bool _r =3D (h)->used; \ - if (_r) { \ - (d) =3D (h)->data[0]; \ - (h)->used--; \ - heap_swap(h, 0, (h)->used); \ - heap_sift(h, 0, cmp); \ - } \ - _r; \ -}) - -#define heap_peek(h) ((h)->used ? (h)->data[0] : NULL) - -#define heap_full(h) ((h)->used =3D=3D (h)->size) - #define DECLARE_FIFO(type, name) \ struct { \ size_t front, back, size, mask; \ --=20 2.34.1 From nobody Sun Feb 8 17:37:15 2026 Received: from mail-pg1-f173.google.com (mail-pg1-f173.google.com [209.85.215.173]) (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 EDC2B53E1E; Wed, 20 Mar 2024 14:55:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946542; cv=none; b=rluGVee6CCO1BF3HNuXckn9qMt1Kxmz4HBp0TTDri+1Frag0s82nT2Jlo5q6EpZEBYFioJyxb9vpvLs+DQb6ZfIZ0zchRVz7HM4Z9C4+35Ux/O2XLQyYtIpDqCkCrm8fkjVrxfR4jAzRvG4sPZgjdYZXwTmDWXTpesjqorTsciQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1710946542; c=relaxed/simple; bh=KMFeHSmKU4CYqNneVApB6vY1jmQYmw8PyzHhws9RMTY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=hgNIPTfGJ49SlO9YHEq6ihSERTnf9oK4QOu2gPxOnUTxIyFEezggwMAFGY3gPEYDgBN5S2+iuJEpcnyL7bxsDDfl/pv7Xtdv71Q+Koo/XTnfIgedfg5e1ozsnx2t1k4KFJzOzk/5yWGN74T1AXFrE+6CX3AU0sCjyUQkHp2c9c0= 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=Q0PpDxiJ; arc=none smtp.client-ip=209.85.215.173 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="Q0PpDxiJ" Received: by mail-pg1-f173.google.com with SMTP id 41be03b00d2f7-5cfcf509fbdso1038468a12.1; Wed, 20 Mar 2024 07:55:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1710946537; x=1711551337; 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=KPLW0qG40wdUtTexwqA/kqkzCYXZBDRQddNxzWgaIi4=; b=Q0PpDxiJKRnAwD2Jxp0J6DK2NAwtCn0CdVDR7TI18vUqcRIudShwljTZN0ZIzXZvZa 05tjXtzHkoZndEcatULCGls07/Q3PLWgYJJU3eSSHynEbF5ZCY3eI0V7yd72FMXFrwFp tO9iC4l0YukYOfPrf2GkMS94F2Ryn57I+bcBI8q7MWXsHssjDv/urM3hsz0xLEi3vRs0 dEm7leql2cjKEMGbZZ9UnLCD4sbIo3/zdXElVaFT27DBbPrwyT+k3Cj8sdOkL4joq+Ox XuexoSMbFGEIvpjpnTkNVj4jiktcshUNcyVXdgKlGPlzkmwOea/bilvYo3QwdhsZm/FT +Q/g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1710946537; x=1711551337; 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=KPLW0qG40wdUtTexwqA/kqkzCYXZBDRQddNxzWgaIi4=; b=hdgqfiTCiBTHUsKMfP+ndYJ0zEHaTBWjYRGsBr060IZ1Qh6bzc++zzLGA8+DbctXAB KJ1QMZ1rSPwzBCCFtfzopokvUJZjOO11EXRFodBgl8Z2UrPNb/RV2frw6hzCEOHd0UcY TICwN6MMxpnb07zgpO212qkZ12bqeeiOTqQ9mVqyE9iauJY3X/9rysD0Um7Qnh0Bn0s1 7F9F7697lGTfrzB3TobtIgEx+6zZVQUH9vY8/f2AyNSIIXVJ07ZnvT+iB1S6rBT5bzrz rp0jFLLkFlVa1+QQfnugzppvhx9QyO9ukoasGsIA0g8vr/+FHLLLpsWi4Qua1iIPFqiZ TBHQ== X-Forwarded-Encrypted: i=1; AJvYcCUrNWspKJNj9WTAIe1IzlVrcIpPzw2FtusE8ryYPIhfliLjUUtJxPFchxq09bw/OilYVnhuQDj7dEaVsYNKF5IoHEiphlOM45gf40gyOSDFl1phOHf2UrqDgbEqRFBsAp/Is936qvvHu0NbTw90bKNeiyIWill23Tj7qeSkMD3crmbw77sng15+axqckABQlaMaA7jPORvoRi5jn2xhiDos6hvXfYMD+heKa4r3 X-Gm-Message-State: AOJu0YxJH4/JIY9lQcBmrE1jpQVwkydRRnP4KQgDAIFrHKueBWQL/hrC BEN04qsChQ7a719sDCRl8pwySkUQK7632lonzcv+8AtGE8rvF4VR X-Google-Smtp-Source: AGHT+IERhQnsr5WyFpp2s48qwEVuCnCYvaTAkc4lWuq6KuXLt75oDq0Oi+CsEeR8yPDirIraJHLJpA== X-Received: by 2002:a17:902:d2ca:b0:1df:fbc3:d130 with SMTP id n10-20020a170902d2ca00b001dffbc3d130mr1973394plc.1.1710946537229; Wed, 20 Mar 2024 07:55:37 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id la11-20020a170902fa0b00b001dc30f13e6asm13719989plb.137.2024.03.20.07.55.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 20 Mar 2024 07:55:36 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, dm-devel@lists.linux.dev, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [PATCH v2 15/15] bcachefs: Remove heap-related macros and switch to generic min_heap Date: Wed, 20 Mar 2024 22:54:17 +0800 Message-Id: <20240320145417.336208-16-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240320145417.336208-1-visitorckw@gmail.com> References: <20240320145417.336208-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" Drop the heap-related macros from bcachefs and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcachefs. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- Changes in v2: - Add attribute __always_unused to the compare and swap functions that do not use the args parameter. - Rename min_heapify() to min_heap_sift_down(). - Refine the commit message. fs/bcachefs/clock.c | 53 +++++++++++----- fs/bcachefs/clock_types.h | 2 +- fs/bcachefs/ec.c | 100 +++++++++++++++++++----------- fs/bcachefs/ec_types.h | 2 +- fs/bcachefs/util.h | 127 +++----------------------------------- 5 files changed, 110 insertions(+), 174 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 363644451106..e898f4693bd0 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -6,16 +6,29 @@ #include #include =20 -static inline long io_timer_cmp(io_timer_heap *h, - struct io_timer *l, - struct io_timer *r) +static inline bool io_timer_cmp(const void *l, const void *r, void __alway= s_unused *args) { - return l->expire - r->expire; + struct io_timer *_l =3D (struct io_timer *)l; + struct io_timer *_r =3D (struct io_timer *)r; + + return _l->expire >=3D _r->expire; +} + +static inline void io_timer_swp(void *l, void *r, void __always_unused *ar= gs) +{ + struct io_timer *_l =3D (struct io_timer *)l; + struct io_timer *_r =3D (struct io_timer *)r; + + swap(*_l, *_r); } =20 void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 @@ -26,11 +39,11 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) return; } =20 - for (i =3D 0; i < clock->timers.used; i++) - if (clock->timers.data[i] =3D=3D timer) + for (i =3D 0; i < clock->timers.heap.nr; i++) + if (min_heap_peek(&clock->timers)[i] =3D=3D timer) goto out; =20 - BUG_ON(!heap_add(&clock->timers, timer, io_timer_cmp, NULL)); + BUG_ON(!min_heap_push(&clock->timers, &timer, &callbacks, NULL)); out: spin_unlock(&clock->timer_lock); } @@ -38,12 +51,16 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - for (i =3D 0; i < clock->timers.used; i++) - if (clock->timers.data[i] =3D=3D timer) { - heap_del(&clock->timers, i, io_timer_cmp, NULL); + for (i =3D 0; i < clock->timers.heap.nr; i++) + if (min_heap_peek(&clock->timers)[i] =3D=3D timer) { + min_heap_pop(&clock->timers, &callbacks, NULL); break; } =20 @@ -131,12 +148,16 @@ static struct io_timer *get_expired_timer(struct io_c= lock *clock, unsigned long now) { struct io_timer *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - if (clock->timers.used && - time_after_eq(now, clock->timers.data[0]->expire)) - heap_pop(&clock->timers, ret, io_timer_cmp, NULL); + if (clock->timers.heap.nr && + time_after_eq(now, min_heap_peek(&clock->timers)[0]->expire)) + min_heap_pop(&clock->timers, &callbacks, NULL); =20 spin_unlock(&clock->timer_lock); =20 @@ -161,10 +182,10 @@ void bch2_io_timers_to_text(struct printbuf *out, str= uct io_clock *clock) spin_lock(&clock->timer_lock); now =3D atomic64_read(&clock->now); =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.heap.nr; i++) prt_printf(out, "%ps:\t%li\n", - clock->timers.data[i]->fn, - clock->timers.data[i]->expire - now); + min_heap_peek(&clock->timers)[i]->fn, + min_heap_peek(&clock->timers)[i]->expire - now); spin_unlock(&clock->timer_lock); --out->atomic; } diff --git a/fs/bcachefs/clock_types.h b/fs/bcachefs/clock_types.h index 5fae0012d808..b02b24b9d74f 100644 --- a/fs/bcachefs/clock_types.h +++ b/fs/bcachefs/clock_types.h @@ -23,7 +23,7 @@ struct io_timer { /* Amount to buffer up on a percpu counter */ #define IO_CLOCK_PCPU_SECTORS 128 =20 -typedef HEAP(struct io_timer *) io_timer_heap; +typedef MIN_HEAP(struct io_timer *, io_timer_heap) io_timer_heap; =20 struct io_clock { atomic64_t now; diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index 082075244e16..68c5e9e928a7 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -860,14 +860,15 @@ static int __ec_stripe_mem_alloc(struct bch_fs *c, si= ze_t idx, gfp_t gfp) { ec_stripes_heap n, *h =3D &c->ec_stripes_heap; =20 - if (idx >=3D h->size) { + if (idx >=3D h->heap.size) { if (!init_heap(&n, max(1024UL, roundup_pow_of_two(idx + 1)), gfp)) return -BCH_ERR_ENOMEM_ec_stripe_mem_alloc; =20 mutex_lock(&c->ec_stripes_heap_lock); - if (n.size > h->size) { - memcpy(n.data, h->data, h->used * sizeof(h->data[0])); - n.used =3D h->used; + if (n.heap.size > h->heap.size) { + memcpy(min_heap_peek(&n), min_heap_peek(h), + h->heap.nr * sizeof(*min_heap_peek(h))); + n.heap.nr =3D h->heap.nr; swap(*h, n); } mutex_unlock(&c->ec_stripes_heap_lock); @@ -958,20 +959,21 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) =20 lockdep_assert_held(&c->ec_stripes_heap_lock); =20 - if (h->used && - h->data[0].blocks_nonempty =3D=3D 0 && - !bch2_stripe_is_open(c, h->data[0].idx)) - return h->data[0].idx; + if (h->heap.nr && + min_heap_peek(h)->blocks_nonempty =3D=3D 0 && + !bch2_stripe_is_open(c, min_heap_peek(h)->idx)) + return min_heap_peek(h)->idx; =20 return 0; } =20 -static inline int ec_stripes_heap_cmp(ec_stripes_heap *h, - struct ec_stripe_heap_entry l, - struct ec_stripe_heap_entry r) +static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void = __always_unused *args) { - return ((l.blocks_nonempty > r.blocks_nonempty) - - (l.blocks_nonempty < r.blocks_nonempty)); + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + + return ((_l->blocks_nonempty > _r->blocks_nonempty) >=3D + (_l->blocks_nonempty < _r->blocks_nonempty)); } =20 static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h, @@ -979,7 +981,21 @@ static inline void ec_stripes_heap_set_backpointer(ec_= stripes_heap *h, { struct bch_fs *c =3D container_of(h, struct bch_fs, ec_stripes_heap); =20 - genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx =3D i; + genradix_ptr(&c->stripes, min_heap_peek(h)[i].idx)->heap_idx =3D i; +} + +static inline void ec_stripes_heap_swap(void *l, void *r, void *h) +{ + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + ec_stripes_heap *_h =3D (ec_stripes_heap *)h; + size_t i =3D _l - min_heap_peek(_h); + size_t j =3D _r - min_heap_peek(_h); + + ec_stripes_heap_set_backpointer(_h, i); + ec_stripes_heap_set_backpointer(_h, j); + + swap(*_l, *_r); } =20 static void heap_verify_backpointer(struct bch_fs *c, size_t idx) @@ -987,34 +1003,43 @@ static void heap_verify_backpointer(struct bch_fs *c= , size_t idx) ec_stripes_heap *h =3D &c->ec_stripes_heap; struct stripe *m =3D genradix_ptr(&c->stripes, idx); =20 - BUG_ON(m->heap_idx >=3D h->used); - BUG_ON(h->data[m->heap_idx].idx !=3D idx); + BUG_ON(m->heap_idx >=3D h->heap.nr); + BUG_ON(min_heap_peek(h)[m->heap_idx].idx !=3D idx); } =20 void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); =20 - heap_del(&c->ec_stripes_heap, m->heap_idx, - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + min_heap_del(&c->ec_stripes_heap, m->heap_idx, &callbacks, &c->ec_stripes= _heap); mutex_unlock(&c->ec_stripes_heap_lock); } =20 void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); - BUG_ON(heap_full(&c->ec_stripes_heap)); + BUG_ON(min_heap_full(&c->ec_stripes_heap)); =20 - heap_add(&c->ec_stripes_heap, ((struct ec_stripe_heap_entry) { + genradix_ptr(&c->stripes, idx)->heap_idx =3D c->ec_stripes_heap.heap.nr; + min_heap_push(&c->ec_stripes_heap, &((struct ec_stripe_heap_entry) { .idx =3D idx, .blocks_nonempty =3D m->blocks_nonempty, }), - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + &callbacks, + &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); mutex_unlock(&c->ec_stripes_heap_lock); @@ -1026,17 +1051,20 @@ void bch2_stripes_heap_update(struct bch_fs *c, ec_stripes_heap *h =3D &c->ec_stripes_heap; bool do_deletes; size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; =20 mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); =20 - h->data[m->heap_idx].blocks_nonempty =3D m->blocks_nonempty; + min_heap_peek(h)[m->heap_idx].blocks_nonempty =3D m->blocks_nonempty; =20 i =3D m->heap_idx; - heap_sift_up(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); - heap_sift_down(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + + min_heap_sift_up(h, i, &callbacks, &c->ec_stripes_heap); + min_heap_sift_down(h, i, &callbacks, &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); =20 @@ -1828,12 +1856,12 @@ static s64 get_existing_stripe(struct bch_fs *c, return -1; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (heap_idx =3D 0; heap_idx < h->used; heap_idx++) { + for (heap_idx =3D 0; heap_idx < h->heap.nr; heap_idx++) { /* No blocks worth reusing, stripe will just be deleted: */ - if (!h->data[heap_idx].blocks_nonempty) + if (!min_heap_peek(h)[heap_idx].blocks_nonempty) continue; =20 - stripe_idx =3D h->data[heap_idx].idx; + stripe_idx =3D min_heap_peek(h)[heap_idx].idx; =20 m =3D genradix_ptr(&c->stripes, stripe_idx); =20 @@ -2159,14 +2187,14 @@ void bch2_stripes_heap_to_text(struct printbuf *out= , struct bch_fs *c) size_t i; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (i =3D 0; i < min_t(size_t, h->used, 50); i++) { - m =3D genradix_ptr(&c->stripes, h->data[i].idx); + for (i =3D 0; i < min_t(size_t, h->heap.nr, 50); i++) { + m =3D genradix_ptr(&c->stripes, min_heap_peek(h)[i].idx); =20 - prt_printf(out, "%zu %u/%u+%u", h->data[i].idx, - h->data[i].blocks_nonempty, + prt_printf(out, "%zu %u/%u+%u", min_heap_peek(h)[i].idx, + min_heap_peek(h)[i].blocks_nonempty, m->nr_blocks - m->nr_redundant, m->nr_redundant); - if (bch2_stripe_is_open(c, h->data[i].idx)) + if (bch2_stripe_is_open(c, min_heap_peek(h)[i].idx)) prt_str(out, " open"); prt_newline(out); } diff --git a/fs/bcachefs/ec_types.h b/fs/bcachefs/ec_types.h index 976426da3a12..2ed67431a81c 100644 --- a/fs/bcachefs/ec_types.h +++ b/fs/bcachefs/ec_types.h @@ -36,6 +36,6 @@ struct ec_stripe_heap_entry { unsigned blocks_nonempty; }; =20 -typedef HEAP(struct ec_stripe_heap_entry) ec_stripes_heap; +typedef MIN_HEAP(struct ec_stripe_heap_entry, ec_stripes_heap) ec_stripes_= heap; =20 #endif /* _BCACHEFS_EC_TYPES_H */ diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index 175aee3074c7..e0c86ad04bf3 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -8,6 +8,7 @@ #include #include #include +#include #include #include #include @@ -54,134 +55,20 @@ static inline size_t buf_pages(void *p, size_t len) PAGE_SIZE); } =20 -#define HEAP(type) \ -struct { \ - size_t size, used; \ - type *data; \ -} - -#define DECLARE_HEAP(type, name) HEAP(type) name - #define init_heap(heap, _size, gfp) \ ({ \ - (heap)->used =3D 0; \ - (heap)->size =3D (_size); \ - (heap)->data =3D kvmalloc((heap)->size * sizeof((heap)->data[0]),\ - (gfp)); \ -}) - -#define free_heap(heap) \ -do { \ - kvfree((heap)->data); \ - (heap)->data =3D NULL; \ -} while (0) - -#define heap_set_backpointer(h, i, _fn) \ -do { \ - void (*fn)(typeof(h), size_t) =3D _fn; \ - if (fn) \ - fn(h, i); \ -} while (0) - -#define heap_swap(h, i, j, set_backpointer) \ -do { \ - swap((h)->data[i], (h)->data[j]); \ - heap_set_backpointer(h, i, set_backpointer); \ - heap_set_backpointer(h, j, set_backpointer); \ -} while (0) - -#define heap_peek(h) \ -({ \ - EBUG_ON(!(h)->used); \ - (h)->data[0]; \ -}) - -#define heap_full(h) ((h)->used =3D=3D (h)->size) - -#define heap_sift_down(h, i, cmp, set_backpointer) \ -do { \ - size_t _c, _j =3D i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j =3D _c) { \ - _c =3D _j * 2 + 1; \ - if (_c + 1 < (h)->used && \ - cmp(h, (h)->data[_c], (h)->data[_c + 1]) >=3D 0) \ - _c++; \ - \ - if (cmp(h, (h)->data[_c], (h)->data[_j]) >=3D 0) \ - break; \ - heap_swap(h, _c, _j, set_backpointer); \ - } \ -} while (0) - -#define heap_sift_up(h, i, cmp, set_backpointer) \ -do { \ - while (i) { \ - size_t p =3D (i - 1) / 2; \ - if (cmp(h, (h)->data[i], (h)->data[p]) >=3D 0) \ - break; \ - heap_swap(h, i, p, set_backpointer); \ - i =3D p; \ - } \ -} while (0) - -#define __heap_add(h, d, cmp, set_backpointer) \ -({ \ - size_t _i =3D (h)->used++; \ - (h)->data[_i] =3D d; \ - heap_set_backpointer(h, _i, set_backpointer); \ - \ - heap_sift_up(h, _i, cmp, set_backpointer); \ - _i; \ -}) - -#define heap_add(h, d, cmp, set_backpointer) \ -({ \ - bool _r =3D !heap_full(h); \ - if (_r) \ - __heap_add(h, d, cmp, set_backpointer); \ - _r; \ + void *data =3D kvmalloc(_size * sizeof(*min_heap_peek(heap)), (gfp));\ + min_heap_init(heap, data, _size); \ + min_heap_peek(heap); \ }) =20 -#define heap_add_or_replace(h, new, cmp, set_backpointer) \ -do { \ - if (!heap_add(h, new, cmp, set_backpointer) && \ - cmp(h, new, heap_peek(h)) >=3D 0) { \ - (h)->data[0] =3D new; \ - heap_set_backpointer(h, 0, set_backpointer); \ - heap_sift_down(h, 0, cmp, set_backpointer); \ - } \ -} while (0) =20 -#define heap_del(h, i, cmp, set_backpointer) \ +#define free_heap(_heap) \ do { \ - size_t _i =3D (i); \ - \ - BUG_ON(_i >=3D (h)->used); \ - (h)->used--; \ - if ((_i) < (h)->used) { \ - heap_swap(h, _i, (h)->used, set_backpointer); \ - heap_sift_up(h, _i, cmp, set_backpointer); \ - heap_sift_down(h, _i, cmp, set_backpointer); \ - } \ + kvfree((_heap)->heap.data); \ + (_heap)->heap.data =3D NULL; \ } while (0) =20 -#define heap_pop(h, d, cmp, set_backpointer) \ -({ \ - bool _r =3D (h)->used; \ - if (_r) { \ - (d) =3D (h)->data[0]; \ - heap_del(h, 0, cmp, set_backpointer); \ - } \ - _r; \ -}) - -#define heap_resort(heap, cmp, set_backpointer) \ -do { \ - ssize_t _i; \ - for (_i =3D (ssize_t) (heap)->used / 2 - 1; _i >=3D 0; --_i) \ - heap_sift_down(heap, _i, cmp, set_backpointer); \ -} while (0) =20 #define ANYSINT_MAX(t) \ ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1) --=20 2.34.1