From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f52.google.com (mail-pj1-f52.google.com [209.85.216.52]) (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 5497322F08; Tue, 14 May 2024 08:47:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676459; cv=none; b=e6BCT7uIq7Mm4V7MQKNPt47Ju5l4Frr0ThEEW6byI+DZHuuQ1vaiX0kVfR5rYzfklcIN25UDMH1FF2OwuY2orxYBdN5DxjbhbT7H9A/XP5blYDfY3KknPEmYjPX4gAIXnF3n8i2nQRT60ZE0aAK5AAxmWU0DAx+Lm02f17LDon8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676459; c=relaxed/simple; bh=5eMBfUoMBCijCucBrYyXb5iM12NH5j3cQUyWi3Km8qU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Go86sZIXdOtxjYvZcwsLpgcaqyFo9kmD1CghQnh4OEja1MNHd4oPlRtE7FOz4qbjNKfJ5CyrT70A9Oc4MJWXS/PNL9ltOeNVEFqDKGHtdjRiH97+e7kIbvMKKi2sVreIgJQaPy0bZHyprKOgffRuVdO+xAx8X5DfwV5hRePGd/0= 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=kXWBtID/; arc=none smtp.client-ip=209.85.216.52 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="kXWBtID/" Received: by mail-pj1-f52.google.com with SMTP id 98e67ed59e1d1-2b432d0252cso1341232a91.2; Tue, 14 May 2024 01:47:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676458; x=1716281258; 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=VJIN0mq5LX930XVge9ngeqBSR6yoC+cL9OxlPKOkaa8=; b=kXWBtID/0DrvA0TGd/qVl0F3ayg0A5KI1vPQgiV8obMV3+T2JvjhW44IQ7KCkGLkJP 1x99HeRmq3yfRaHedoHlNLyQQCqv23zs++x0zrIB01oK5/m0E8tZIFVFpa67SWDcVwWs 2VUz5TGjXGFJjiP1h+8x8DXFo0SqJNC4hSUmWMzu9kLX4JYXy3agmNIfO/z/4BhiZSIe 5tbcgWCANfCW1jCbNC1N8FrhXw8UpmAS1lSdVSSb8qbTUD0aB563hS6T+WTt30CC8Nq/ IHcCpcpkOR3yXxtqUA1pdmE7eru4vmetMWhL5YV7vb98DOFNW0h7Z1SLa7wCMSTdAbEf uxJg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676458; x=1716281258; 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=VJIN0mq5LX930XVge9ngeqBSR6yoC+cL9OxlPKOkaa8=; b=tHveM8UMbLh0hjiCTFBvOjZvrjmE1E1Tkh5BwrR6u9z/3CW+7TtnWPS0zVECVvnqyk I18VjHEcz8bWSafxKkGF2NR9hziw7EECaoTdqBZWrIhzELs+9nh3b8FjHGkIYn/PUFtE i8RrSqE237hr+kesIHrC2so52mumLMP1hiM9+Z/ClsyP0XiiRZOBlhOU0tRBUwwoZDFl dPzCAERBoNr5IXGOYNwiPk/bC9xSlQf1f2H40CVQxQegyIUs3vavvV4u1bDVz5osJIof vv5HQTAP6ombiz8QOdc7flYfA/h8qee3bwe4qBZszjQJ5I8kWHp0mjgGceNFvzFvCyYT mEgA== X-Forwarded-Encrypted: i=1; AJvYcCXHi6BLGpV5cDbYzi+mx/larrv1yQKXFrT3F1b1/V262lgDNxX9gbsxYAX4LEmhXpWmEC62KPd6oxsrFE0tMYaSt3F6h3QyHG/TlDDJ9knakBVOTtPmgdyieT8/MI5rLAwre2BssuBcLyxyca9h+sl+yQUcApLkZ+JxsSDaCH0yPFhr45Z+NAU+/HLbwub75sK4qST7ZYutT7kdb/EvDs0GEzJqPysIH1RMAtqM X-Gm-Message-State: AOJu0Yxn5J5Nx+OYDnwRnImBGDHeQG1teNvFz71+BkkC7WLO7se1PTxt hL4B0pkKbH/vGC1JFYibLOqHtijwAXtd1Ckfa5y0NVOb8ZWB40KJ X-Google-Smtp-Source: AGHT+IG03sin8CsXv9ZoBGudgY6bQBtBEMYZDMlC5AFiVRjrzKUMTKrBFfGO2gSMQoV+wDsSjXqlxQ== X-Received: by 2002:a05:6a20:3d81:b0:1af:93cc:860a with SMTP id adf61e73a8af0-1afde24da77mr15883169637.6.1715676457543; Tue, 14 May 2024 01:47:37 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:47: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu , Randy Dunlap Subject: [RESEND PATCH v5 01/16] perf/core: Fix several typos Date: Tue, 14 May 2024 16:47:09 +0800 Message-Id: <20240514084724.557100-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Reviewed-by: Randy Dunlap --- 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 Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) (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 5C3D2200C3; Tue, 14 May 2024 08:47:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676464; cv=none; b=NQiGvq7UYUN2J/D8cCnlAH7zzdRgAwNMp3TfZyj2QJdWyERiRmElKPSfA01a9xvM+oxAM34vDZVz8P0GdNcb/ExX05vfWjpp5zcP9NvMaKzWJi5PbvpKBNzsc/APPBy9I70Bc5hntV+5WMVzVD0Yok1iEViUk7Wbaww7r6y7cLY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676464; c=relaxed/simple; bh=UN1Xetleeq5Nz5tLKfuxk8/opVO9kM/FjVJ/CVGswXI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=AHd2AMCFrfBKI/kEqT4oOpW2XWhTotj7yaAVt7Ni0UwjCahSSEGMuf5Z68ywwBpqAMUOGcVUky8YJso+59Q+lU02lQjNWOTTUQyYyZKhG4R6FsqLuquy6XLblZ7JrrCm+XILgVWxYn95BHz5aXlAn0Eyp+tjex1KKBp96erRY30= 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=BuV0UYxY; arc=none smtp.client-ip=209.85.216.43 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="BuV0UYxY" Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-2b6215bcd03so1229299a91.1; Tue, 14 May 2024 01:47:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676463; x=1716281263; 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=/7grr21+dk77QDv4Gfk7ePfGBs40BXM1/CLzaulLK98=; b=BuV0UYxYjUplMYGuP5g3agOlb2JAk30NFmafFnXGPbM010iPOooVpXxs5QHhR2Rcmh dymUSqT437+QoiZkk/gngGtS3dljqz6eJmtVwC2O30u1R9y17aZPK6zz5Al+1QsA7kMg cOOpnvFOG7r47v+LAmopnFeblIUoEs/HdkzPi49MQ2EYFbSrZCE2Y/nJ1l9UWmGTB1dc XCrRIIYJmnZTpTt1jkcRCVFAAjBJqEtyc5FFrrMPXZtLA9EtZG3RbOhsjV0o7neFDezK XTDS7PgoslOJCgrI/ANO7fMEvFtsWLnlZu72dtZJJoirBOij3qT3EzEj1KGvrBTPL/ct rg7w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676463; x=1716281263; 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=/7grr21+dk77QDv4Gfk7ePfGBs40BXM1/CLzaulLK98=; b=KpKu8dx1cIbXoYv0PcObxH4r9dSqGbEt0MSrn0QJMjPMLiqb/KuQaOuoi/nNDRpwMr Q+O5rMZbzaCzSVvfssxjNfKSmsh/cx98kUoYviaxkBTuDlUTpx5WSHTpE0c71qsA7aRu oN2fzCmMbc4OMNcA86DW4TUnLKh2oG3dwubhdHH1K1sBuy3Rr8mGfC+zrDmzPA3W1wna mYW25ffnhlyYZIYjMy9zQHRmG3S/U2u0zZOBtg+nOHdo8Lu90uDNPEzjbEFjr1RcnxZu cvGPYgoNuIGEDPbE2Qj8zc6FSxp1UWhcZCBWv1I++9Nw6S+8HMJJMwImnloyU2A1pG0D 36YA== X-Forwarded-Encrypted: i=1; AJvYcCX+E2cKZfhyu3EUywRnxzBxAj9j8PcP3vMzvJgQXLhy+TkDMZUkm6oRIEY37eCtLpy676LtWbliLTIKHqZxcicja5fuOUe44FHQi/Qe5q1MGFL/saNfq22k9gJLqRVp4bmHbDxzZGPc1ldrEcaSoztvDyNNZWSv00Yu5Hqy3SCStHpDcuOMd8VcLnzXmBte+ERU+RMEzbd1qBaqm7UcbHt9iEY5crXc1+HsEsSE X-Gm-Message-State: AOJu0YwsWdX8lqABHo4l2h7qlO3bDPl47IWFxIyk6fOjwx3tPJEPjE4Q BN9jQZRu7vEgFKmNNNoTDI044ov/4FaJJ/nF4eNgbyX1yfo5Ki+c X-Google-Smtp-Source: AGHT+IEMUmx+37VSqc6GRGyY4pOmP+xoAi9mzpeZ5gYRml7jxeXeFDC0FyBMpm/Kb0QmMkl9TuNysw== X-Received: by 2002:a17:90a:3d83:b0:2b6:5b13:b3b0 with SMTP id 98e67ed59e1d1-2b6cd30d2c3mr11588329a91.4.1715676462694; Tue, 14 May 2024 01:47:42 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:47:42 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu , Randy Dunlap Subject: [RESEND PATCH v5 02/16] bcache: Fix typo Date: Tue, 14 May 2024 16:47:10 +0800 Message-Id: <20240514084724.557100-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Reviewed-by: Randy Dunlap --- 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 Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) (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 862BF37160; Tue, 14 May 2024 08:47:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676469; cv=none; b=kO2Qv9k5yq46l74LcINccov3JbIxAnb+ZIayk1nE2Ux6gXpcJznLUdDoBVqSp8MrNFuophXyZZONlxnTXL9H8MDL725X5Bx4sgYspuj6x6MUShaXEwfD1OEny8cuFBxS0FSVd9Tl8Gjwgd2VCMt7RBVy8Qaqd7Csw9ZMQVYBMys= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676469; c=relaxed/simple; bh=F4H9nDZNXyr/ZsFI+cCJhr3OYw8PynR+1AAuPVXPV9M=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=dEqoDRY8YTW+f/o8CVMyvXtF0obF1VLnwZMxgTIRXSnN4wU/rlpmnuLAhNlAn11LrmG6mBlyucH7cdi1sbIHYxmCGoo459uv0VsHwHqUU/fKvwtf/x8axs/xJwbCeCtqm3y5g2ACNSZeFHe/I5NTwwMCN1/fdCrpOqZfvrDKKSg= 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=j9DHORh/; arc=none smtp.client-ip=209.85.216.42 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="j9DHORh/" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2b33953a163so1332850a91.2; Tue, 14 May 2024 01:47:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676468; x=1716281268; 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=6mL/EL0d7nL6m0RFDxHa1SNm7xjXj5OmWxYW9IhbyI0=; b=j9DHORh/TfBQfUfCmINWevT9ZjTENN8quwfAKqCtL1kB/Z/tJCl9GsNA0T3KKph2vq qX+9qaxGWozH1GX8fFu9ZRrysEBxXbN3dzjrE4hqifOk35RuOjjduLGWQ2iGqyzjhxcI 1b84kI3ozwoSXSX93hdBhrqx+YuYRvB8QX+PT1MKcJUhbVqD8eDsRBfxA6E89nsqXC7F y7dEus1dmD/K1URdA/O8Hj6g7Fd2ZsCc5r1VY9smwe2Q26OjwwXgYG/32wKP2fYS8CNT P4SIG+IIFxDWiVbvb6c6Oct/B5fe0nCKif8f6KP7ajfuy5+WbKWq1mvxDXCydW6ntoJ8 diwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676468; x=1716281268; 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=6mL/EL0d7nL6m0RFDxHa1SNm7xjXj5OmWxYW9IhbyI0=; b=WIFS48uoWCQIrIaH/QkcffjFRAyzg6zQA3l1rJzYSB/EaOv+X518YYt8ml7LAE2yRc ZEajARNPnS6k1to0BbdXRPwlQAmzO7bmD2Q9C/C+vmGffqS0zNJq/EGh9KW3bc+65rgy 5DOGqu/nuPzssZch6FllSe6wat4/w8j3EkCs/79vRHYlmqt5VeQlY58rGJRhbrFqpSyR SNpP7PR3KAxBSn4qnXXJXq4GeYPFo7B0EdL+AiP9TNyro5/ebmdOUtnCSNGYqH6kNlS5 1Vita+5nLtamDv0zCdWM37P1/DPjq6vmNRRoSHDEETwJ2Pun5bcByYu6QJyazaGCx4BE NljQ== X-Forwarded-Encrypted: i=1; AJvYcCWVg5MsvxaDf9rIPj2aYTZ0PqwMpX6uUcnBdxpLWu3VcwPEpizbDftv5EzJHxfveQzTX7hl6lyWFuIs63T7bbyXIwNtNj3lgTB/g4Ns2eFWvDj6WWd2L2nyK8KQJDhfnI8MKUJ10Hud38c8ED/aLXEi7t9VeSkmWUMeHL4L/t/JDNrhntM5LTuyeUzZbtKZQKkExljwyXJVD28Gtn1TxpPvplW3L6zyVwVD7OBU X-Gm-Message-State: AOJu0YxxpDKR6NJSh6gH1vbgVgUeMJA/3PSo8pGfzfEJTns0O1vRwWC6 nvtIXR3Vel97ZmWeGmGH08iHq8HyCgMI3Iw7tZHi6P8gy7crI2Bj X-Google-Smtp-Source: AGHT+IHT5Fm+YDGnCec0X1e+f4cxpGHHD4p8mj7Rb98W/3AbFrtGCShFZxSTzr0614+V0BxS0fadUw== X-Received: by 2002:a17:90a:bd0f:b0:2b2:4bff:67b7 with SMTP id 98e67ed59e1d1-2b6ccef5a6emr11238648a91.3.1715676467913; Tue, 14 May 2024 01:47:47 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:47: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu , Randy Dunlap Subject: [RESEND PATCH v5 03/16] bcachefs: Fix typo Date: Tue, 14 May 2024 16:47:11 +0800 Message-Id: <20240514084724.557100-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Reviewed-by: Randy Dunlap --- 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 92c6ad75e702..05ac1b3b0604 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 Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9DD20381D1; Tue, 14 May 2024 08:47:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676475; cv=none; b=V523940nih06X1aOREq1cD5rnMIqTZ5ZnEgoBlQ2A9rIk7hqHLKVm5l/cfNj3oJJOMWTrv4nxMdjwqjoqNYcB1wmy1NxQ541y8i0GE+1bNZ/iw4EIGIS1DKIiAjxpYOY3S9ZPotreZ3IN0i4cujMAw1HCIWnJel/QCAPE1ZPocg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676475; c=relaxed/simple; bh=zC8ZPKx+XJMnAnBiu7A8UcUb7bpBs0b2sgXXTGX4mYs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=FfA8AsCfI0nvdWslB8EnH75oOYqBqp7yv8eHHhSO0IkuyZGy0wwNjKy6DBSmkC2OifOR/1Nuih2/P4elvCs+0dGTwyKR+J7f/90gsNqlgefJQ7GLB8/M/KuL+TvnxacJ2BvmWKye4Ws6fcxekX84n5hw44PLXOqwT4+ZZM+4VwQ= 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=BwbrD5FK; arc=none smtp.client-ip=209.85.216.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BwbrD5FK" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-2b345894600so1226964a91.2; Tue, 14 May 2024 01:47:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676473; x=1716281273; 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=xf+l/+ZrFdLUNiawy999A2pfV1CigGHvqtilnzgi+4U=; b=BwbrD5FK0o0+/VCfwremIa0oLojvUmHUc7pGk9aa+yHXdsGjif7+ntsmikfd01XL6A Zg7hilsyRnQzwAkH2/Pw3CqFrt8IHb2+UxpHqFdOnxq3JLlnZJPb8AqXcZZDVXkODZ+4 0xlsPYN6iqZCFhBnzXm8rbOAVjhl6mc8KZZb6N2wA0/Mh9RIPsb2GYjV9txidCz6zJwE 6FxqAJNv0cG9WvT2H9/7JWKtzyXDvJidrx8XZF5Pv+5eB0LM0mUuWCy6mmz4WI6/0UJY 1eR2/Ib26IISzVpQOkH93lgH6c/2P17h4PtenQj1/lUC/eSKBBwPqIsxPrkF2H1p4snQ 39wA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676473; x=1716281273; 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=xf+l/+ZrFdLUNiawy999A2pfV1CigGHvqtilnzgi+4U=; b=vuVkHUjRVwASFhAxTOGI7A3UIY+Y6m9FU7e4kZo/7poyEkzEBNMoMuHIF2FBw9dzKO ccyQ/3anWu+AFAnEgPvNVK20nmnlJGKt5SBQ3wv8MIwDthdNzF2Er92eXfzz+cK1wk76 Nhjm/nlidQkhNksrTSszvU8ttSEvVz9eU+RNlQ8W9OyfkbdEFP1zqjc4S+zoHSKqput4 q8VBmZNz2cUaNDvF7IqM9ewmaYVayaDZT9W3k7hzw/o6vucdDQrSFeqPROqYVaTq1v4v VdEQ/Mk+QjH6aJE2prGSvFVL9sy8abIt1I1+4hItm/ZV+EHBLTLsxCFctj297tRPOTXQ 5YoQ== X-Forwarded-Encrypted: i=1; AJvYcCUYuJGOfHXH2MCzmvtGVJuhAkmSi+LLALSchpj/tUVY7TMnuirdMSDbLQliXIi8YEfTygOBiO4fYHNMoGwbwkQ8LlLtS+f0fetrP5xrQABAAQl+yWYcrwXx/6i0sfHzlq2H6ghWBKvB7fbD6ZA0GfXgsEku/P3zAvKfwCSFVVVwv6hnzhVChipI7/xgdi66ngjhWZaARVYQ0muXBK5luOGOrMC1lQcTZ5YEW9yk X-Gm-Message-State: AOJu0YxMK5iy27JMik6pyOPuvwJwlt4gl2n6yBI8UEmcd+DZM00BQeZ8 UjWLsGVWCFzUvaf+LyFFK9QQTPXenGiGQpxayjKoIzyWi4sHI/zD X-Google-Smtp-Source: AGHT+IElAywWWhoJbXrt++YhlkHRzGVy1Yg16EeY0XU8/9VVtVZO1dlmItyKwYI+B+myvFj3xLrZHA== X-Received: by 2002:a17:90b:4b0a:b0:2b2:a1f1:22c0 with SMTP id 98e67ed59e1d1-2b6cd1eaf47mr11606138a91.3.1715676472874; Tue, 14 May 2024 01:47:52 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:47: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 04/16] lib min_heap: Add type safe interface Date: Tue, 14 May 2024 16:47:12 +0800 Message-Id: <20240514084724.557100-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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" Implement a type-safe interface for min_heap using strong type pointers instead of void * in the data field. This change includes adding small macro wrappers around functions, enabling the use of __minheap_cast and __minheap_obj_size macros for type casting and obtaining element size. This implementation removes the necessity of passing element size in min_heap_callbacks. Additionally, introduce the MIN_HEAP_PREALLOCATED macro for preallocating some elements. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/dm-vdo/repair.c | 9 ++-- drivers/md/dm-vdo/slab-depot.c | 5 +-- include/linux/min_heap.h | 79 ++++++++++++++++++++++------------ kernel/events/core.c | 11 ++--- lib/test_min_heap.c | 13 +++--- 5 files changed, 70 insertions(+), 47 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index defc9359f10e..48c266fa07b6 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,14 +165,13 @@ 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) @@ -1117,7 +1118,7 @@ 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) { + repair->replay_heap =3D (struct replay_heap) { .data =3D repair->entries, .nr =3D repair->block_map_entry_count, .size =3D repair->block_map_entry_count, diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 46e4721e5b4f..f6ae6956f321 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,7 +3520,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator return result; =20 /* Sort the slabs by cleanliness, then by emptiness hint. */ - heap =3D (struct min_heap) { + heap =3D (struct heap) { .data =3D slab_statuses, .nr =3D allocator->slab_count, .size =3D allocator->slab_count, diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d52daf45861b..87737cadb9a5 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -7,45 +7,53 @@ #include =20 /** - * struct min_heap - Data structure to hold a min-heap. - * @data: Start of array holding the heap elements. + * Data structure to hold a min-heap. * @nr: Number of elements currently in the heap. * @size: Maximum number of elements that can be held in current storage. + * @data: Pointer to the start of array holding the heap elements. + * @preallocated: Start of the static preallocated array holding the heap = elements. */ -struct min_heap { - void *data; - int nr; - int size; -}; +#define MIN_HEAP_PREALLOCATED(_type, _name, _nr) \ +struct _name { \ + int nr; \ + int size; \ + _type *data; \ + _type preallocated[_nr]; \ +} + +#define MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0) + +typedef MIN_HEAP(char, min_heap_char) min_heap_char; + +#define __minheap_cast(_heap) (typeof((_heap)->data[0]) *) +#define __minheap_obj_size(_heap) sizeof((_heap)->data[0]) =20 /** * 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(min_heap_char *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 +62,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((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void min_heapify_all(struct min_heap *heap, +void __min_heapify_all(min_heap_char *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((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c) + /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void min_heap_pop(struct min_heap *heap, +void __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -88,27 +102,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((min_heap_char *)_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(min_heap_char *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((min_heap_char *)_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(min_heap_char *heap, const void *element, size_t elem= _size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -120,17 +140,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((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func) + #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 10ac2db83f14..55930479599b 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3698,13 +3698,14 @@ 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; =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,7 +3748,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 if (!ctx->task) { cpuctx =3D this_cpu_ptr(&perf_cpu_context); - event_heap =3D (struct min_heap){ + event_heap =3D (struct perf_event_min_heap){ .data =3D cpuctx->heap, .nr =3D 0, .size =3D cpuctx->heap_size, @@ -3760,7 +3761,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, css =3D &cpuctx->cgrp->css; #endif } else { - event_heap =3D (struct min_heap){ + event_heap =3D (struct perf_event_min_heap){ .data =3D itrs, .nr =3D 0, .size =3D ARRAY_SIZE(itrs), diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 7b01b4387cfb..dd5c0fa862ab 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,7 +32,7 @@ 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; @@ -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 { + struct min_heap_test heap =3D { .data =3D values, .nr =3D ARRAY_SIZE(values), .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, }; @@ -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 { + struct min_heap_test heap =3D { .data =3D values, .nr =3D 0, .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, }; @@ -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 { + struct min_heap_test heap =3D { .data =3D values, .nr =3D 0, .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, }; --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pg1-f180.google.com (mail-pg1-f180.google.com [209.85.215.180]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AC2F023748; Tue, 14 May 2024 08:47:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.180 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676479; cv=none; b=YhVM6gZCxE1Qj2EL6MfVLhxccPj+qCLMszSOz6t4Gt7eZlNYG2/gGOw9G7Y2RCdvBjzc9wkmgZkWUPhU1bFbSq/6cGRpLSgIhwsywLWtJU2HPlleWfAfnDLXG+EWhWlka/TmXzeLGdXAPIZX1tnS4IScPydCzkRYcarjO0C04S0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676479; c=relaxed/simple; bh=b5Qix40IYcfncBwAyPvMRSLFUIF05YVbAb9l7ZjOFyY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=tFMZj2+iLzFvvsioj9nMiDFmfMiZq7fV1+FAZRj4ql9TG75NgBIMaCDI7Nst6K9yy9rnaKwG8acm+CZzqLo5WZPoEUbw77s6m3nD0lUSJxzcrt/MjInuaR/bSO37Oyic24QUoYnGyD2qeEEUx7/Rm23H3vMvvSuiDPZSdqmFcmc= 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=iD2qLwAa; arc=none smtp.client-ip=209.85.215.180 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="iD2qLwAa" Received: by mail-pg1-f180.google.com with SMTP id 41be03b00d2f7-64f12fc9661so65491a12.3; Tue, 14 May 2024 01:47:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676478; x=1716281278; 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=BrRuPk05kgYWrNF6DoThYuAvcZ8CXsiyshk2gqZWuIc=; b=iD2qLwAa3ERhvW+0J9cnaNLEQFHCOn7psY/Pl0tpkGb7Ak5ytJ5VCmxuzMiPHiWIBA ZpH0QxL+hU+UTUjUi7sN2yWCY+x+7E9ep42tYZ+I3J4VAgiqKbHcQoubhqwWa3Q109af 8MMByEJcaAV14R/2gRppQwH8qBwVN3+xPmNf3yJd43sj/O3A2qMYEpSoJOzx9hGtPzPY RYV41OPEiGF0BOwFO5SgutsS8Sgfg61s5OHFqh3usHz1r7y3FxA27LT2eYZMTs2+BsY2 NvyT29PXgdM4OYPX20hVmnIp5c8CADRZs+DaAK/FpuTe7qQ7F51LKFXwxx1L3vIfYFmF 3biw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676478; x=1716281278; 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=BrRuPk05kgYWrNF6DoThYuAvcZ8CXsiyshk2gqZWuIc=; b=gUQ7fPUSSn50Rs48AUHF4vy8jZjIxqlqG7fv0qjgw1GhDJFQyKuKJSTZbIEoYIp0Hi RZY5FV5ctpaAk58K9w3A9yZ5vkmO+HZHBATKjx1j0yzNLwpEMH3Xp4stK5Rl0blcYWWn r1k4g7fz9APo18inunU0dNuC2xOX1QLnYUnl2qag4gjr3mcwArSOTx/NP/e60/h3TYEa xmS6Y4sYOBT4941dH2c2pnV3fB2DdksvqOdNwru40+v/qozQvi3O758k7Db2zUhvprt+ e8kgEvrN2VnkMlEEeCEI54LbWMzh2P2rWR4dFjoEC7JN0AXKzDQgNh7cJzsSuKTArfc4 ZU2Q== X-Forwarded-Encrypted: i=1; AJvYcCVUqeke80y/Jj8ePaSO7VC6HgdddIqDdxepybPoDUfH8LhBLDCZ9OIasD7vO3R6YxNuB7dA8LLTQetKBP87FF6KspzVeWBNlj0zfhChAFuREc8Qb00i4eNxd+DmgIbmEMuNSTF6A/O/cStpJM9uL9Aodff98+KuCddPw0pOJMiCUDQcJEecd48pEXu9j3bPpAfXbASCITNyuZGWECjsqeoQqkyvSjK+QpY74sKA X-Gm-Message-State: AOJu0YxiiKZl/vDx2blZMp2jkLcIKYZICi719XYD4YCLoAFwCskg//5Y yjUi6571q/fWoeVMMY4x/t1gvhFFBf6rsLY+1K/c7DQF6Qe0PZNO X-Google-Smtp-Source: AGHT+IFna34DmfsGRr4HQsSkrsjPDrFZM+b+BeRj2Nqh3t73q4AJ1ts++l6Quzf18v9kLyQZ1vDgLg== X-Received: by 2002:a05:6a21:8191:b0:1af:d51a:1b9d with SMTP id adf61e73a8af0-1afde09ec47mr12142159637.1.1715676478018; Tue, 14 May 2024 01:47:58 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:47: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 05/16] lib min_heap: Add min_heap_init() Date: Tue, 14 May 2024 16:47:13 +0800 Message-Id: <20240514084724.557100-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 | 15 +++++++++++++++ 1 file changed, 15 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 87737cadb9a5..f6b07fb8b2d3 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -38,6 +38,21 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs); }; =20 +/* Initialize a min-heap. */ +static __always_inline +void __min_heap_init(min_heap_char *heap, void *data, int size) +{ + heap->nr =3D 0; + heap->size =3D size; + if (data) + heap->data =3D data; + else + heap->data =3D heap->preallocated; +} + +#define min_heap_init(_heap, _data, _size) \ + __min_heap_init((min_heap_char *)_heap, _data, _size) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) (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 81374286A6; Tue, 14 May 2024 08:48:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.42 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676484; cv=none; b=PcEt3IHpzcpqI/PA/rXtWBqwQ/4zNYlwTVuO8wwLEBuaKICtmnDFns4rvvK/EttOSZIvcudCTWdOIpsYBs2+eXKfOvk8ZBHUTyKob8KY8M+ju7geckCz64ZeJI4Gx31uKlawwYdEGmh3h6uYgXGEXwsE2gwz7lfSLrHkY+RwC+E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676484; c=relaxed/simple; bh=9tjNBJoFW/M4N3UyhM3SbO6qdcqZWdxAoa5Ri1G9BtM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=dJQgBQiBGVWCeNjGzPs0JhYjRclltIzNhY0BAtXFQTdxFeotphsTB3X1cb5B3mJ4LBSynt04lPYRBAzXz4fntXQCpzn1K+wDL6V+UdXmpOAg3SaH95jYitYI7wGDPNXGYaoTVdkaVtVWUaza6HiWF3K6pCd9z7dSA/gLE51luzo= 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=PXttNeeC; arc=none smtp.client-ip=209.85.216.42 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="PXttNeeC" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2b516b36acfso1394434a91.2; Tue, 14 May 2024 01:48:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676483; x=1716281283; 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=0J0f9A/bhPWWSuBlnbsdq0jeNHFHB9IJoCtvcFhHPOw=; b=PXttNeeCUzORSBKG7aSYMJYw1UmPuzK+ATYY7miXxlZgZ0qq+1pcp45lY2BO93nlCH rll7CkbiB29t285X2MyCklNj7BOuP3+0PQeTs159CHsX3HvmQxZtBjVFDJSUyil6aT+E pZWkdTaVALma1YvLT2u49UDGocOzh4pln5LlLIKKyF6CPflZCj7RrWtCRyWLFAe2HDhL 0rnVfipH4peWNDvAhpN163mhwPsJJzC/6tmLlRVg4QPP0JMBCeir/yzxs3hPihTAFAp2 JToNyVpSfJnnCJFDKjroGUvUGmBxgtKgzgMhr8jftaastsRyOUmeDc6TWlfNzjsgmlG/ GZjA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676483; x=1716281283; 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=0J0f9A/bhPWWSuBlnbsdq0jeNHFHB9IJoCtvcFhHPOw=; b=N6sV7fjWw8fOkQnnYZnAv+TGWQVaYGA/ACaMCjwcAkP1Syhi5Nz4LJg79iIlW2jyDr mQBBnafUDXWoAgFQOWmCQeqCiLk2AjcLGAV+3cBHxiYzQDs/cMrGyl9C3ijTDY6K5+Fr tQR+OvyG+7UDll1GrTwfSna97969ZB+zfS2zeGQhoqDkxFLPUAqxHtXPhZ52f16z1G5V ASshyJCb0vJNg1nw2317TKtORY+R579P5Ut8L2qzRx1U4GT41XfYgD3NZlZ620ZPFfkd QtLmZPS6X+E+2GrJSb/qPBjtZh/aMapnNcwQJILtrU3AApkCqw206Gym8tmHIW0t4KPz /Zjw== X-Forwarded-Encrypted: i=1; AJvYcCU4tEvNf/MyCK3MgoAHRoLsUQPyBpT0Dg6dZP9yAKLQvjsWlqPSUd/Yl+QGajxZMFt5RBjw8CFLaaBEYJg6dhvPqQOCGGp1Efj3ZMrIlSSS5PfoILPZDZbImBn1OomfGwFqhcAchUizHcBAXXZCrlSHOy8CSIbpOwtlb8fXhr1/JTlCwV91LzB0plvB1OMPymKqjv9x8k0I7onDbr/C5kKvRn7Z+Bn3Ck/gydvz X-Gm-Message-State: AOJu0YyKiyTanFJ+GsXlq5e5OPuZHR+HIyPaeo/nCy1g5CGlB2FsBzMg ZLMJYakkj7WI4YXFeu8w2fzIYtsodKka6KUTOB5jcVjvHTeDZHir X-Google-Smtp-Source: AGHT+IE1patJmPNchHUnX39Zems7iVVjiSomR0wHWIH7h7asJlDmxjS39dyTAxeWrilwIpfx2hdfuQ== X-Received: by 2002:a05:6a21:7896:b0:1ae:42c8:4f69 with SMTP id adf61e73a8af0-1afddf12a2cmr15147500637.0.1715676482845; Tue, 14 May 2024 01:48:02 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.47.59 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 06/16] lib min_heap: Add min_heap_peek() Date: Tue, 14 May 2024 16:47:14 +0800 Message-Id: <20240514084724.557100-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 f6b07fb8b2d3..043de539bf71 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -53,6 +53,16 @@ void __min_heap_init(min_heap_char *heap, void *data, in= t size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init((min_heap_char *)_heap, _data, _size) =20 +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct min_heap_char *heap) +{ + return heap->nr ? heap->data : NULL; +} + +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f44.google.com (mail-pj1-f44.google.com [209.85.216.44]) (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 3CDD93C092; Tue, 14 May 2024 08:48:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.44 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676489; cv=none; b=gIZS/6E0ChmNlyYnkbURA7D0p04uNca9F6qCZgpcamCtclpYgSLqDaaQC8iGwDiKw0VXxDhhbuzWLh3M/r0CpWWch7aiuPE9ig9IipBaAY28OeYow7i03c1jsoZN8DdenVACWbTW6xp6dPpMD6gmM2PU1/4fXSDIbOMq36yq3Ok= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676489; c=relaxed/simple; bh=45DqO8bF1UCi5bfdHVSu4s8AvmjNFknYLPsfVsf4ic0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ALVD6ZMzhZMtmBKQVLxAi5RoEqTew3xkIqY6EOe/uX9SXhhhjIgPs1O26JF2RF2n+kbWU/Rigo2ifbGZ5XGGmxQsPFqBEo1x+KyfISCsBuD1YI7v6JEZ5uKuyvDckZC9ka5zh+l+F/eiDur4nPFmqtDqMdlEV5/Fmolwd13Imow= 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=KqZxdO/9; arc=none smtp.client-ip=209.85.216.44 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="KqZxdO/9" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-2b345894600so1226989a91.2; Tue, 14 May 2024 01:48:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676487; x=1716281287; 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=vKi/lHC5XFLRvEUBusUUTA5MCG5n2IA6GUULUt/TPRk=; b=KqZxdO/9ZINYevd3me0+cRkUXGLq4zZ/ZVNPDKHKvihdLj4xx9pxoUlrNsADju+Q0d ysdvVZcZnojGJxFWxx1L9sAfCEfCWFsnr9xny8bprs9/ZCkvCXHFBTLPtI77ckANCWE2 63R9m213YtKf8SSwM2AhPWyOOPJz1vrNyIwzrVJN1oL3M+lYHlmhKoAL05NMUWvHMAtz NACK4xOtZ10znpUuvNJCj8rA9ilsIfNkINMnGfTRBHtRrN6dSfutSZfEJ/hD2yMAwzpb fkzRxDD2r4+eLJM/N9iBrPS68Es+JpaDajFbuId8QFhShgXBcGH5SpWqVKUjari0wU4s jzHQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676487; x=1716281287; 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=vKi/lHC5XFLRvEUBusUUTA5MCG5n2IA6GUULUt/TPRk=; b=X/Po6+dLuDd6ceuvjrYYHJccDWjEzn1JDea0tXdNY0yOmm5zr/uADlyP8op1YW9j0o OSIusKCFlbMad2lQM68iW0JmgnrmZ8HyulUup5wTjVO99B0bTj+Oyhxx75xoPbOffpYL 1JiW1GAin0XFyLyN8h3eU+/ltwG+iQPZ6mbQIlmE5e4pR6emCvSRZshgkjpMKmX3qosw nGiYU1qdi3372C4hDG0AJJpZeEu3uUmnY76TJcxK7XsY55CKmsCrmuM7xhCHfeSeAnRe 5XC/W6PWKnUbIeL13ZXDeBsI4eSZDlJmq5o0weODac0tYdxvDoOU/aqDoqoT+TznOrOV MhuQ== X-Forwarded-Encrypted: i=1; AJvYcCWqkxITC0BfP96ntCa/QyVUyHjvdds+jo7+4scN3Se69bM++o5/xzmg11q73+f27JjvheA3aHjPav2/hlFlYQjW8TqGkbnV+TuJ07RRzaM5/MZCJ8Jq9eOIRcNbMzQRKaYu3NIGZtKjcRfO+LtNDEo1nKtw+S4ABETv1RvV7DJU2HPi56cp460cL1bnNNRedrmauOjE+IDbHmqRp4lD49Z/Ou/I6oc7h4z/Uwgf X-Gm-Message-State: AOJu0YxhCHXndodq6ASOdhXZBaSy4lZpoyhZNRnSXUfrJQwbJMVJ6NUT R0cPVV7R35lMEwYFsmNGLEie9n5gmZQvWjj0hSON2nCs4HBkpp2ycUSQbw== X-Google-Smtp-Source: AGHT+IFfbcYjY4P31J+W01r/olfC4xhBU+O158w6dnsjPNmjyg3v+UZI7gGddaCiTE5ahTFLgPOTnQ== X-Received: by 2002:a17:90a:f3d3:b0:2b4:329e:eac5 with SMTP id 98e67ed59e1d1-2b6cceb5dd3mr11609526a91.2.1715676487641; Tue, 14 May 2024 01:48:07 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48:06 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 07/16] lib min_heap: Add min_heap_full() Date: Tue, 14 May 2024 16:47:15 +0800 Message-Id: <20240514084724.557100-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 043de539bf71..d4ec7e749280 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -63,6 +63,16 @@ void *__min_heap_peek(struct min_heap_char *heap) #define min_heap_peek(_heap) \ (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) =20 +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(min_heap_char *heap) +{ + return heap->nr =3D=3D heap->size; +} + +#define min_heap_full(_heap) \ + __min_heap_full((min_heap_char *)_heap) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 63CCB41C7F; Tue, 14 May 2024 08:48:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676495; cv=none; b=Qv8q7Ou6Bd+T8+uyYKiNeJA21GKCrt0DPzci6Gzvz+sQoKHeMF0tojssYzeKLAjOqAn6F8DXn4OJxGurbo8LzPjibhetb7Uw/TcR/QIvTbJshGqs1LVj04l6DBTcwbe0s8+Pgq5OHOB/vUvpu0Zy3WFurw63y00fsz2XWY1KLtc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676495; c=relaxed/simple; bh=00KH2f809CEXeklo+9a6PeGPW2v5ORHI9eZgRU7gLTQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=VM1QMX+LS4hS2cUNaaQsTVavPgLKV7UoOfL5Rvo4+BHH10cwlV+jUz1XWejZEa9H8x7+juug1ueEEvkiMl3H3E8MfTH/9kiS3Br5258xUZLQ7K87MhiGhG9fKKgxuxKCt52nWCDWBbMx4OG9qIxWw2Ui2dHlKpVwJU9DTIUDgH4= 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=EXN7/Dmn; arc=none smtp.client-ip=209.85.216.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="EXN7/Dmn" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2b516b36acfso1394465a91.2; Tue, 14 May 2024 01:48:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676493; x=1716281293; 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=G2ZkCe3L0WTN4eDU8EG8GGd4mOKJnXr9AQ1ChGE8nos=; b=EXN7/DmnWkE7YjQ2iehfcABsbjURc2iI5CwNX/8CG8l0vbyOggVMC659nrpUvkqLYj oCK/qR+nWRoL0sW4ox628IYEsw/annh0AFlux91n6BXLgGwvMZFj0usIF4cEpe99HH6r w8TEt6RUVyJKX4baoIN4lW4itnlEr25WmAT1xZsdAsu1582jPyl7MDE2GrdN2xlIiV2o w3YdwCZl6STc7QDUTILAbRK9XWdvObTON31+tVzDi9K+WI0cLV87rlYOdvAOi1VFnev+ ttYrmuIvsHpMfaeNTqaJM40G7J59kqMA4RlLbYu/84kklEHvZkSSAZc+6aaIZZMVnYkb QztQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676493; x=1716281293; 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=G2ZkCe3L0WTN4eDU8EG8GGd4mOKJnXr9AQ1ChGE8nos=; b=MqiCKGeFaWx0ItUlY24rc0yQRhCat+1boM5X+BSOuZmAYA5aquLD4mV7DL2CSXE18W 1mOoWZ5As8R7fUMgDvFl7FreqAikSJWNlTI8zaBOsELq9q+wch5AL24K61BjDSNDTBwG nloP31evuAMIsUmKSA3dsqq/4rIR1bIta6lIPRCywXe8ouMzrhEUO2KhqU3pjFu+iRGL T2BLDFXPoIs4jh6AFflHs85wFNa+Q10joX4k5QJ6ZD55mKedZ8vSJPzdQ6NVJWD4dn4h l3+t0W1yURhkDA/AiW6p2jNTlImLThsKapJahALcgrAFuACbw3wNOS5jqx/Z1m5hn//L NmiA== X-Forwarded-Encrypted: i=1; AJvYcCXhbntcAqpRuia8I/A7oxd8YYfFXtYwTmzYNwhMbjojRmJ9JapMmpxzfyBqGtEn8BFf3biSVVHeElnx3BYIXSytjKYtrVy/Ldm+OCAPHBBOEADAobYzXeksGwcaTpRkrolRknWhKzcPMQmuBiXFmrY1qKjMlbebwTB0M8G298Jm81Asw4zfU3I+QCmxGYJkllT/spHPqQ+rzRTKQkkhWEMtq3KOn2iOu77Efz8G X-Gm-Message-State: AOJu0YwuF14JGMb117Hqza/coqLsGOx6Il/hUrPjy19nFM4FNbJoK3qa NjOmkVeGfsdnkT4fdcsQL/5Y8lW0qVA0rQfqGnx7T/D57zkBT1UG X-Google-Smtp-Source: AGHT+IEUyPLqtOatrKnhNtRVbXrKj5y1n2fFFbIc8hTEjJdwM0RvOvmigeIWuhKOtFdM45/FzsuLjw== X-Received: by 2002:a17:90a:dc13:b0:2b2:78a7:1b02 with SMTP id 98e67ed59e1d1-2b6cc2448d8mr11185505a91.1.1715676492662; Tue, 14 May 2024 01:48:12 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 08/16] lib min_heap: Add args for min_heap_callbacks Date: Tue, 14 May 2024 16:47:16 +0800 Message-Id: <20240514084724.557100-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 --- 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 48c266fa07b6..c1ed3ae823bf 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->nr]; - swap_mappings(heap->data, last); - min_heapify(heap, 0, &repair_min_heap); + swap_mappings(heap->data, last, NULL); + min_heapify(heap, 0, &repair_min_heap, NULL); return last; } =20 @@ -1123,7 +1123,7 @@ static void recover_block_map(struct vdo_completion *= completion) .nr =3D repair->block_map_entry_count, .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 f6ae6956f321..2739f5b1f8bd 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; @@ -3525,7 +3526,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator .nr =3D allocator->slab_count, .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.nr > 0) { bool high_priority; @@ -3533,7 +3534,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 d4ec7e749280..9391f7cc9da9 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -34,8 +34,8 @@ typedef MIN_HEAP(char, min_heap_char) min_heap_char; * @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. */ @@ -76,7 +76,7 @@ bool __min_heap_full(min_heap_char *heap) /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *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; @@ -89,7 +89,7 @@ void __min_heapify(min_heap_char *heap, int pos, size_t e= lem_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. */ @@ -97,38 +97,38 @@ void __min_heapify(min_heap_char *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((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc) +#define min_heapify(_heap, _pos, _func, _args) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) =20 /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + 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((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c, _args) =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline void __min_heap_pop(min_heap_char *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 @@ -138,11 +138,11 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_= size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop(_heap, _func) \ - __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) +#define min_heap_pop(_heap, _func, _args) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, = _args) =20 /* * Remove the minimum element and then push the given element. The @@ -152,19 +152,20 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_= size, static __always_inline void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size, - const struct min_heap_callbacks *func) + 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((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), _func) +#define min_heap_pop_push(_heap, _element, _func, _args) \ + __min_heap_pop_push((min_heap_char *)_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(min_heap_char *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; @@ -182,13 +183,13 @@ void __min_heap_push(min_heap_char *heap, const void = *element, size_t elem_size, 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((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) =20 #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 55930479599b..dfd7b5748cbb 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 @@ -3783,7 +3783,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.nr) { ret =3D func(*evt, data); @@ -3792,9 +3792,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 dd5c0fa862ab..0b5037b4bd68 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->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.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.nr < 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.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 Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f52.google.com (mail-pj1-f52.google.com [209.85.216.52]) (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 2DC7D208CA; Tue, 14 May 2024 08:48:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.52 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676499; cv=none; b=i9r7ShmZAuqLdOzAMOOvmHC8MWD98oiJtV8i7oC7P0yuhKkHUSNy5SRjdRIrH5a9thEAtrQYOjAoclPAW4HFylPY8sTmDjk46tYO9B0ShyoEU6Wn18HyBwif/QD0ICR9Lh5Ew/nkR0769KL338cAwSoIq/hLwCabL961cXQjLoc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676499; c=relaxed/simple; bh=4BdmZ42eGYqkHh7DqsaJJxnA5TQhEtJiFDSi25byrow=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=t89TDqXxdSgOf3Hf0N/mTB32xPb8+5WP30AR6pmnYvPtJTKwOEvN6ak7+46lk0nfhtltwmMRKm17vpeNh3fkUFi5tZAtpRdYAAfskLU4Zc1snGelo3Hx9z9Lle/e9+py4QZ5xbLGOlLYFwJyMXoceMEdud92+UH44X7FsoPbfzg= 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=i+bj6yIh; arc=none smtp.client-ip=209.85.216.52 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="i+bj6yIh" Received: by mail-pj1-f52.google.com with SMTP id 98e67ed59e1d1-2b620b0662dso1336902a91.0; Tue, 14 May 2024 01:48:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676497; x=1716281297; 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=zYBPuzAS4rfB8ctDvp2HjPAauLmNAXnRoi+vJxjVmnw=; b=i+bj6yIhQnGeCDbQqc/ztYs5tfQRQXgXxklYWFEr7YxDy4zpAd16ruQzSv2DL7U1lr oel/fwpuDR8npabDbKMNB9Y8oElqBf1Ym0m5ODpUkmizUk7Orj3PlgEMdmV4uy+ZXC8A A1Q5MfE4AG+LzbRaTMtDCBw1roRwJUmy0Me+9DAafqU7G00LJBcfKY2yQqF9Zlg+4m5Z wwWZaMT6utpzPSob/g3BgaKjee++12sTx9bzHh5HJGuVQyloBkZJ47O3ZcDlHnYlU1Qm hw9g1g9eO08H60YqAC++zxMsxqqkcq2HCojwRNbnZ4UNvFvAqC/BB2RMnUATLNmo4sEA gkHA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676497; x=1716281297; 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=zYBPuzAS4rfB8ctDvp2HjPAauLmNAXnRoi+vJxjVmnw=; b=cZpaVYL1/Q/opAI52kWH+f0ONgQqOuWMSpMR/CYdRHdOQF0VPSZV9TZ0xEkPvxS71e +AZpJgvrkj8u1ZYhTqxbYJRbHBp0meCWeytJuWujjtY03Akhb0h0dTrK/CMIavVIE5lm HmlTlLx7psbpZ5A+9wdNkcoRoimzoOHOg5BUcdNjpAHupAiJwtXvPC8WWs0DQ9Uh/l1j 2Al5a5Yn+VcYmcaj3ju6w1VaxcvBQTgMYnpsLA/kfLb4Txp+Ygur8NzxzYMQCFdrrU6+ Ge+Xlnv720yVRXhcuFqv2cEhDJ0HBW+nDQZxSytHwwsTEH9kY4ld7SHGtqusWkyttW2m WSFQ== X-Forwarded-Encrypted: i=1; AJvYcCWWWKY2sElNgbP8Ur7DQT/FkHRKeSa25gsU3NEG37X5sIUpPqSZGuCFrALpKhYdsO7q8enoWerJ0fWw9DPGZHyWjM8ITV0gp2Dxd+TgGl8Aba+vZYLts5MbyxEEuXQuanZX0ej8oSc/IgxoQEMOmuVsyM9HF2LqgtMZ4bvA6IZfGU1KmssNRAAQ0lBgKqe6y1Vu2rpWvcML7/I6/luWiyiSzFHSU8d5648MS3YY X-Gm-Message-State: AOJu0YwFiusYLKJvl5Gjyc9j4vJvjXesRicNo89sxHX7ZxQ5Qmrh1k7E SmvQ6uCFOwsEGAbfbYUhJ/I79f0KrTWZgnoDoLGxTJIBsFyOR8/5 X-Google-Smtp-Source: AGHT+IF1tB3asVOcIehbdULs2Db+i3/DdCJln4N3P8SkwIhnJXqJQWr4URVvswDXe1xPOx3i62bGnQ== X-Received: by 2002:a05:6a21:329d:b0:1af:a5e8:d184 with SMTP id adf61e73a8af0-1afde224bd1mr14425374637.5.1715676497576; Tue, 14 May 2024 01:48:17 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 09/16] lib min_heap: Add min_heap_sift_up() Date: Tue, 14 May 2024 16:47:17 +0800 Message-Id: <20240514084724.557100-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Reviewed-by: Ian Rogers --- 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 9391f7cc9da9..201f59cb3558 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_= t elem_size, #define min_heapify(_heap, _pos, _func, _args) \ __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) =20 +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *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((min_heap_char *)_heap, __minheap_obj_size(_heap), _id= x, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f47.google.com (mail-pj1-f47.google.com [209.85.216.47]) (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 255E336126; Tue, 14 May 2024 08:48:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676504; cv=none; b=sG5U5TpLj4MAMJki2NicKn28dHJVLvjn6fRK0CxQapvIr34JiKdHdZB9HLVdc3uaRALJ8NS1hcTBJMpT4urO8gPtd/EHv1IMXMNJCfRetmddrRBjB13SLO2s02zkeYqiGLlqpswDXm7SmlxQzq7jfAESM73WXEzqrBFPCXtwVZw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676504; c=relaxed/simple; bh=8grIJogka79sG9/+DDK77OmBdavevP9vGHfoCgHyPhY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=YxKvD4hSri60fL3zQTsm/5SHKR2+3aifdqmc+kRbaggxjs4PyLUTn8vWQwFWhPGTXL2/mDnlgYJx1wFA6otTDiL6uPVQCA0sdWbg/ZuBaBSSUVOY9MB0ChBG+qdFzGHMNJS97OqDMTZvNst70gnl9r9/ZyguVgAZsTIngwO9DTM= 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=iLCSfCOj; arc=none smtp.client-ip=209.85.216.47 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="iLCSfCOj" Received: by mail-pj1-f47.google.com with SMTP id 98e67ed59e1d1-2b2aab2d46dso1233027a91.0; Tue, 14 May 2024 01:48:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676502; x=1716281302; 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=zSnssd6hPC3K4+9QwFoXbrNCoJbqsVd1VI58MolSit4=; b=iLCSfCOjKZJ463irV+9X/JMvFQB8sygWVtqMSR8fNoprVaDz0KNm9HiKed0xbQZ72K XMxc2w0Vho/DVbzb7UwYOOwFTshTnSTpD6pHYYKY9sFHCwt5J30uTBriOWpuXYVddctJ UVo5RcMh7EUvunbN9BmIEnSpYgWfmbncHola5tsmLfjvUB0VLO1ystYEnhf+3QHOr/0f 0IXxD2IbtYxWpI53nQSJqBvUZkCvXUQm1RK7czESJm4E8H7LiSU1690Pu1s7hDKfDxqE 82qVDIdgTAggFBeTFIcrhCjiA6WSXKu5pkD+6W4IFtD0CCLvHKEUdS+FyTpXDk3P40qk gGvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676502; x=1716281302; 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=zSnssd6hPC3K4+9QwFoXbrNCoJbqsVd1VI58MolSit4=; b=Q4SjMX63GNGYeRL27pqEO+TSjseWhSjh3fYfZsO1U5mIXV9nKGBpFInEHu3AevSQlc y3LDVKWjNNH/vFj+JpMw2YagzmYmU5xOqUV+Ygm1Ms3CmQvOTmXBaKSBa3BxNyATa/KC bwSfASA3YxCte7NjblZ2QpAsdXXoQ/bxvjbpJAl+VETb+LAfRN1XAv7RxAKzCDmh5S3k DRqiZWfpQcQud7IgH017NMrFS2wJ6XccnxV/qiqoM3ZU8kAMtxPgUUOyrPoCR+/Ds+mF aHMVLhlxOFaSyvn5XsyMqk87c1b0UYE63/chWA72hVC4MndqDQpcfiILmy5csUE5U7tI uopA== X-Forwarded-Encrypted: i=1; AJvYcCXV74e5/ATqLoiHwsQ5u1mQZF2B73viXxa7Mf2A6/+pLSzE6wqJ9XaoIuyYNw9DzvomKS2txvvPZ2t1YNeLLMNhsf7HV6GjMw2qR3qWgvAxxg249MvEpsFvTHMXvyWelJpK+Pvp16xVb+za5wIYXglKl1Jtv112UnRLqxDflBmPfelOmS3hseqnxHl4Ya2u6+aQEPUUxR4vkQOr+hnnF4wYEwbZF+aIoaY5IfVG X-Gm-Message-State: AOJu0Yx4dMrh0n7DcGbmfUlc52SdQ160DpMJAD8/5KmR6O3aYtJ/TI7q HsWfJcoNDJYcrnqqebZwc5NpMPl9uAmCVTlMrD4lCS9B3kSidGlF X-Google-Smtp-Source: AGHT+IFPNI9RtyTNoKPikm+afe8TVCRh8CRN1TwrBLiqKxWH2jb9eMRvsssng1X4+/efPHjACEXLew== X-Received: by 2002:a17:90b:354e:b0:2b5:fce8:59ef with SMTP id 98e67ed59e1d1-2b6cc452fb7mr11632747a91.1.1715676502501; Tue, 14 May 2024 01:48:22 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 10/16] lib min_heap: Add min_heap_del() Date: Tue, 14 May 2024 16:47:18 +0800 Message-Id: <20240514084724.557100-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 201f59cb3558..c94f9d303205 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -212,4 +212,28 @@ void __min_heap_push(min_heap_char *heap, const void *= element, size_t elem_size, #define min_heap_push(_heap, _element, _func, _args) \ __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) =20 +/* Remove ith element from the heap, O(log2(nr)). */ +static __always_inline +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + 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; + func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); + __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((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _= func, _args) + #endif /* _LINUX_MIN_HEAP_H */ --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4B7726BFA8; Tue, 14 May 2024 08:48:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.49 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676510; cv=none; b=Dh2P9A6/QXPg8VuNKy7U2+3hb/dG+/hXYEk4H9u3g0pB13YuXVp4N2/iX04YGhwMQDQNxjukzddwQr2ZC5QG+t6ETrbV2OZAPC0u2aYDjT3gj8Ve+tTvotvs5Ox9TtmA+f2xHqndizuciIPFKw48aFSWrsqXGLJewJHwRjJOhRk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676510; c=relaxed/simple; bh=PtYRw7GsavxbiDyoXt/jBI3j/cXrR77rkoPNcWtU+qo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=TQtSd2QKlUQx6yicxKQkUJ3LGxPULPrpsXHzwrlAcXtQCSMA6qgWux9uJPF12/98OX+5RQDEKWXWvzuMMwTw7AXyfjOJ7Q3Ng0scV0olAhZ6oN46RU7qnGHDA8TbhUy0B9BHPSd4dQ1FaOpr1m5bjGd4Ec4KWGRiVg+DQM/KStY= 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=KczmbKJf; arc=none smtp.client-ip=209.85.216.49 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="KczmbKJf" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2b432ae7dabso1398327a91.0; Tue, 14 May 2024 01:48:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676507; x=1716281307; 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=7EphJEt3KUebjz7mwKYHv22rhUher1RghPLhkx5N+uY=; b=KczmbKJfkJKLcFv/xaqOqEMRIwl4gaZso5N5q/RB2hXwuhg0nXnBLJ8RU00DWpGfVi cLH6YnNl91XjKskdlxn8+5ip2ztjEQ4enCRwlUx5dYvQS713Pj7jhI6K8UK3pi0fNK22 Z96wlJT6y5rf+VbtuZwOndnNuHn2rNG3FZKBqZgQ7cXJGh4JQvGcJrzA2gERvGOoNKJa Yd7sYi2lyxVQtJcQ9v0fWhMMTqDHsvRyA0WO/yz/92maaYxAlIovE6+iGX5aO10M1O8L Lz+KBMpH8fVgO36HtSvpghmk/2yw8GfzK6iGuyQm3qK8OJlXkBm4q29/kqbxvX8dLEXx oyDQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676507; x=1716281307; 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=7EphJEt3KUebjz7mwKYHv22rhUher1RghPLhkx5N+uY=; b=F7FC18dKyp1in47pZU2XlkkXi82iKKgz+UI6xVP3tFG+5JgGmd6oF1/DCyTjjjF/y2 mXX6aop24u0Sxp1TzyUph1Tv9IpCn5RjfDci0D72tGeyz+szu8G9Wq9ddxFjnvqWiByf RKEUyQsZeSuHFht6pQCMKOxxJi70NpROfHbVkC9JcPH5WkXid5Bx5JnY6u+QkzPy2yXc a1oymT3lWHm+OrvfVS8gv8Nx7ACIx2b6P2kP7H6qofDkSWmtqnRzC3s5D8n6EgFV/Nrt U3q54d4aWnVbQaTndbO1xPR+UMZnbyj9PQqDCRHeMdYBV+T/qa3eJqp6zv1H8jEHFcUy RGQA== X-Forwarded-Encrypted: i=1; AJvYcCW/QAvCBcNRHRm290r6+nOxQ1OE/s8sdjY9PC118MQ+5W1LW3LGnsvYnpFRTwznB1e/XsLS4GYmzEjngmYUuKaKGmghu/VkRUw7Vp9nfYbTtw0O1VPBAKn3/R1BXe0Gpmjv+mCnhE3QkFtWKIxV+wR6QexoZRCUIhsvjj3Z9AywsxMsFhI8f4DcOcrs8EkAsPmhQUIeQ0sqwxlnFdJ9fJuwlSDZmInpE0ckZxFS X-Gm-Message-State: AOJu0YwneqS/gfLVYVx8dDGTmmi7CrWmQ+AAg2tVRIqtTcKq7IGtHJDD gLmwYPedd84T9NKjqXinZzQcA9CCnZUw4nswcgSSSTo5ngl4O9Gm X-Google-Smtp-Source: AGHT+IGfQAYvZHJMtREHiuCy2r7Eecel/8/3etErb19WpLLlg8BfpElH6/usKz1uG/RUviA8uzRF3A== X-Received: by 2002:a17:90a:e2cd:b0:2b1:88bb:20ed with SMTP id 98e67ed59e1d1-2b6ccd69770mr11166476a91.2.1715676507633; Tue, 14 May 2024 01:48:27 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 11/16] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Date: Tue, 14 May 2024 16:47:19 +0800 Message-Id: <20240514084724.557100-12-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 c94f9d303205..2d080f85ad0d 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t el= em_size, =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_pop(min_heap_char *heap, size_t elem_size, +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { 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) \ @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, 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; @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, break; func->swp(parent, child, args); } + + return true; } =20 #define min_heap_push(_heap, _element, _func, _args) \ --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f43.google.com (mail-pj1-f43.google.com [209.85.216.43]) (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 4921734CE5; Tue, 14 May 2024 08:48:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676515; cv=none; b=NdL1T6cftDsBCmW7iomv6RMagmXG9NTM6zHkDGsMlvg1o+PrTys2IbiMrBenu1MvZ0u41n8X1SXVQXwwOsmY26bdP10BByueTfNZjQlSq00eee9FRUwwEvQOVV0bc1iUwHYZo3sRRDQpCZqSBMrrpr6PtpSgEGEmx+Wy4CbLwI0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676515; c=relaxed/simple; bh=5dPWx/XCuPpHn/JbswVAX4unB6CSgL3H/O4srtepiqI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=LbUkqX4sqFql3w5V+u+/AJAnYkjtEuzVVYS0TAKVGosUt9tHUZBYXl3umRB6YwwGeUAqpxSuX9kJ07VIMboxG84enybghOiWkN8c8Uqyn4wtLVpqPYARvxeZMJYdblt0XeRbXUx+0J25HR9tdS3DrAzY3ycZ6l7pvc0V3/nUJ2M= 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=PBu+EX1k; arc=none smtp.client-ip=209.85.216.43 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="PBu+EX1k" Received: by mail-pj1-f43.google.com with SMTP id 98e67ed59e1d1-2b6215bcd03so1229406a91.1; Tue, 14 May 2024 01:48:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676512; x=1716281312; 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=qStH8dSNcDcItb1wA2JtX3YjxyreJTEee2fjqsXU5t0=; b=PBu+EX1koj1DTkwA0/tjAmqR9kBa6OuIhRdM7SeXsoMGzHpSSAyIP5/8MguMXcT6Eo OdowTid81AWdG3AY+G+BcQUhCTyaalpp7bb5zHBdWTXHJUFSOH9siY9gYCwKSxuK1dzJ XokrWFnCCwqsCzD4sFRvF3pEvuSAy9koWQq7TXM7EIjf0UE6I6oktSCOITBVyC4AJUkP BE82ONShnuRMLhPYJc4lkbaNwylYi4BpcJ/VO37X1vr8aPbRaBD9tCaydT9Yw6Yrj7BL 5IDIs/zNYjdlCzFbcQj/MlFrixRQftNy75NU0lwAyblWs6Ek5OPzmrb+/0iFAvrg4elq Ja0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676512; x=1716281312; 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=qStH8dSNcDcItb1wA2JtX3YjxyreJTEee2fjqsXU5t0=; b=t4ZjIxl6t9W18Epro3UiMObC/M4gDEf4Osqllr+lN2TufZJik0/oTezoTiZ67VdBQW QcSbk8CgwK+a5EFk5iw6erUpwaDRhX21DA901DT19Oq2ghr6SfLxiFUJHbYZ7zrDoYAC sHIhvSQHd5Spy09CZFM+8cOVr9x8Jz9lcUZt37UpJQBXRbXnfhHlbnQCFOKcaeqVwTDL eKdoaI13z5Fz4ZDOK8OrXHXXf+mBdH9fuQt/ww2b5JAtC4pYY8ee8I0PTjRRiVNeDxkf ODIJIiDtxR5EcJNnQwyEmtFtTC111teY8z9zGLyJJj2H5laHMSydnPS8jl5lzrCBNcXr mEUA== X-Forwarded-Encrypted: i=1; AJvYcCXPHweic/uhd+lfTio4Ux0fG93y980UCSs+l6RBfVzGFMZbxLiTK7Lf2C7AUpe1y3I1CvZ+D1yJsCp3eJdcLh7BI3TpxY+LVu1gi7B1IECXw5AV/P9Lew/CIGyXHTc/pD4wVIlFD4g4wJ36lrTz03iQUMjzWT+Mw2sXhFN49u6g1s1hJeFX/YHXkgduk2EULwOINWqJQa7i8nm9I6ZxadFUovMY7lfZrQlnHZQa X-Gm-Message-State: AOJu0YwTS2ncrYRhElSSl2/kXaQLpJ/Q4fZ0yuSvSYhxD+0yZmLW2fLR rf+UyTIfksUUTDliOKG0ASy85JpFK0MGoFEc0jmk1lsuR7AdRw6w X-Google-Smtp-Source: AGHT+IHAEeLtnkJPSridXVxcM1Lek6wVLa4/x7IxnsemEK0CxdtUzekeg322+ZCpZ1YXDs/kefgzeA== X-Received: by 2002:a17:90b:354e:b0:2b5:fce8:59ef with SMTP id 98e67ed59e1d1-2b6cc452fb7mr11632999a91.1.1715676512627; Tue, 14 May 2024 01:48:32 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48:31 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 12/16] lib min_heap: Rename min_heapify() to min_heap_sift_down() Date: Tue, 14 May 2024 16:47:20 +0800 Message-Id: <20240514084724.557100-13-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 c1ed3ae823bf..941ac9eda8ca 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->nr]; swap_mappings(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 2d080f85ad0d..f907c694e852 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -75,7 +75,7 @@ bool __min_heap_full(min_heap_char *heap) =20 /* Sift the element at pos down the heap. */ static __always_inline -void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, +void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *left, *right; @@ -108,8 +108,8 @@ void __min_heapify(min_heap_char *heap, int pos, size_t= elem_size, } } =20 -#define min_heapify(_heap, _pos, _func, _args) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_he= ap), _func, _args) =20 /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline @@ -139,7 +139,7 @@ void __min_heapify_all(min_heap_char *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) \ @@ -158,7 +158,7 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_si= ze, /* 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; } @@ -178,7 +178,7 @@ void __min_heap_pop_push(min_heap_char *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) \ @@ -232,7 +232,7 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_si= ze, size_t idx, return true; func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_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 dfd7b5748cbb..82f329c8caea 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3792,7 +3792,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 Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f45.google.com (mail-pj1-f45.google.com [209.85.216.45]) (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 2194B6E615; Tue, 14 May 2024 08:48:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676519; cv=none; b=OXJvoA2a9ZqySgGecJAqkXds/zB1bLCrXnRTin2zQohML9mXtQ2JHibPGteIN5x8pz0Pbz1ippKqrVUpY/YtWwGNoN8bp5UCryCUAnjbncEfHWgH+G3F77U4IXoOrrfz0tOUppPT4QvKOXYLL5/vJ5NvPBn3Z2rKcEx5eNn4bjA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676519; c=relaxed/simple; bh=T8bV4BnctbyRNeSPAOZwi+czorsklhrFY1lqJqcqucQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=rFqDir17ZcIUAnfXUuQFKdTFHHeSwfjgUIZXgFRhywQrhzbP0KK6me9bv+4Wze/2X+wAxmTJ2sWT8Oq+USIWW7DIjFNMMM0xTO8t6oX1GiegjfZr3Exx+7U0vjyMoj5hfJU88fZYVclvX1D0Q/xNGtVBjRVumhtqcj0olkt49Yg= 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=B4wIXKS5; arc=none smtp.client-ip=209.85.216.45 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="B4wIXKS5" Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-2b8fb581e77so513567a91.1; Tue, 14 May 2024 01:48:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676517; x=1716281317; 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=8RRhCYNi4OEA45vqDvulwCxtOU91F7rHv4uIJxFLbAA=; b=B4wIXKS5Ih04dr4mB6VJVSiQvrAJTyI7ym1kQHCAbd7XVkDmdNa7tLin0V09XvEylx 4MQNqELPQmAlYiHsnjfHfdcnQ8/YQmK6pxggxqNJUn481n/f9OOxoGAaoMTBUIn2ub4t L3jZAVH4W3WcBJJ8VTH+X/xMJ7wFk2+o3gLuYMmv0ADm8b5OU/epb3hii1Symf17Z5LL z0TsbK9yZv4nvoi6tCD4x/F/wrdzKwDWnlxlD7t62c4KgeKsaRWIpEOuDSC1U+pYJSIU GDe2L4SNhvda1JogSC9jZK3kvdPZ9TpuBwu2dpDklDQeZyI2+XFf7jXdg5FmtZehYEt2 zevg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676517; x=1716281317; 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=8RRhCYNi4OEA45vqDvulwCxtOU91F7rHv4uIJxFLbAA=; b=ZHbO3CFnAg9Lz6LCxTeW3eKpHGr+1xSEqnDoZvQS/1GF/PWrgikeWqdHsMBLTAvbSB D8UpgQrWwsS0ZhoZLpywV52x8nBttY5V6BtWvNegkWn5rvqMiQ6umw8vTPr/pxH4oL6S 03H6+rlD++s4Bg4uRsgOwhp0Jd41JhNX8tPxY4HlvtRTRGJf7RSp4hoj9vyV1F+2sNPj ZBzGMOWUGZqan1G2dI06JeYUE0HrjdVu1pWnyJ6nSG1OXJt/zcPjzk238g00VQl8XZmL S9mQDgRQczUpexF4Be6/wu+3uUgXAbGByQ6500rr/pEjw374H/QuLQ/t5qiJZX8Mqe/E kmxw== X-Forwarded-Encrypted: i=1; AJvYcCXqjHtvB7k4nTsmPEqUHG47n+nfQSU7KFKUsIwKdH9CQgQAli7m2qOqkqrV/EF6QqNrNAPMgfMQa0lhwXsbk2+HeLyAAZ2lStTfDKlY5VHV0fneQXZlPiIrzE5TsOP3XW5klbRrrSO4OXoESktBbr5SCg+8LFIuKTx4RF26WTtPa2o9KeI2enpGt96L+Zsxs6/6m68+U27TwFOnzGDma2Acz924vtJZ7R1yf1Or X-Gm-Message-State: AOJu0Yw2hdwslVd9cDTHK9h6qGk6iLjgzkFysBTfBF0XjChOExXAoGxA zfCuBcSpGjtYI1EawNCscMtPmVTAIlKaWJSpkaxIaMP1k9B8hDle X-Google-Smtp-Source: AGHT+IEzlf/04lUJoXxSbnAU7zQCtwIAC9yXyQQEJzVOzxmc9j9IenXqL82SIeeytIkK98ac7sU06g== X-Received: by 2002:a17:90a:e2cd:b0:2b1:88bb:20ed with SMTP id 98e67ed59e1d1-2b6ccd69770mr11166692a91.2.1715676517541; Tue, 14 May 2024 01:48:37 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48: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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 13/16] lib min_heap: Update min_heap_push() to use min_heap_sift_up() Date: Tue, 14 May 2024 16:47:21 +0800 Message-Id: <20240514084724.557100-14-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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" Update min_heap_push() to use min_heap_sift_up() rather than its origin inline version. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f907c694e852..78de60f6ef1c 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -190,7 +190,6 @@ bool __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; - void *child, *parent; int pos; =20 if (WARN_ONCE(heap->nr >=3D heap->size, "Pushing on a full heap")) @@ -202,13 +201,7 @@ bool __min_heap_push(min_heap_char *heap, const void *= element, size_t elem_size, heap->nr++; =20 /* Sift child at pos up. */ - 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, args)) - break; - func->swp(parent, child, args); - } + __min_heap_sift_up(heap, elem_size, pos, func, args); =20 return true; } --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f41.google.com (mail-pj1-f41.google.com [209.85.216.41]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2EC3E381A4; Tue, 14 May 2024 08:48:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.41 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676524; cv=none; b=SzEy7Um+8hJvAhDtg+/ujXt0JLP7jkSCu6+fnRwPuX/8oYJBtYJSGnMCA7hebvByxhqk1Bpf/kgtKaI/kqN0x/Ob3rGLFfwLfvTpBVHfmBJ6f+c5C0oOinOI351ikynd6lsfKwIG6SoZ2a1X29CJmdBHINUMskQ33tYI8pqbl+A= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676524; c=relaxed/simple; bh=6RI5jUBlTt+5u3rxYbD5uAwV2PYZJ9bmstimem/yPPk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=XR7el/5Jx9T/nDguwfjcw1ukPWGItarSmjY9lkWIrwawTe+oxTqwXd/Shp2eF4NYLTQ23bvdnZ2+YR01T4EnZyB4/AdLjRZ8xq6EzWiWC+JUE95PEXvv1cfeOi/PTrOrCPAvRgSfGb7i9K/eb6FL9zAHbNNkpBYmRZkZ4zeqYxg= 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=bD4qyzc4; arc=none smtp.client-ip=209.85.216.41 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="bD4qyzc4" Received: by mail-pj1-f41.google.com with SMTP id 98e67ed59e1d1-2b370e63d96so1332569a91.3; Tue, 14 May 2024 01:48:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676522; x=1716281322; 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=nfNQplMLN+Frp8NNBnHt1wiGD5SxoB711mIx7353U+s=; b=bD4qyzc4uVivwLgRnlvoR+0qu+8pyybyLIPHNRVkKhx/0aTL4yzoILrGBPVPjFKiQ7 nm9K0/8B2yjCekHLNmppbSktifzr8dQYFUYGezTLRv8BKUJVNeT2TSUGTbSG2ZvotAbi N9kO8r0Gr+9syGJECZeNFoTj2tg9xGnI2x/ETvha+bzf56bTLPzf2TIKAXc4TnUdozbg WqInWyTNTsbW1arLGi2rG8JiNmz6YW4/+YjdukqvNPkpyjwpNT2GUDGJtDfLyFPn72Oh dfDm48gtSJKr/tZbUs9PCV6FekzDUtO824gEjVL+MDOzLj2DCyncoLvoS50MGozgawTO fMJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676522; x=1716281322; 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=nfNQplMLN+Frp8NNBnHt1wiGD5SxoB711mIx7353U+s=; b=Lnb9BPn9hb+t9ltj3RiK2R+HFO/jodWbumqOg5C42vKgJm5Vx3dgEdD3RtOCFbE17a 3Jef+8bWqBcGK1UZw3P4AAyGJtzAPSbtM1nMR9AhdsTNI27TrstgiSAKVUIRfxzCGa11 FnOuV5F92BpVebMVrRoCR9z05jGxgzRbjj+bmQVRdOLBYi+jHpd939lXoojdG+YJ1iN/ FCbdTjPEfadnW1enVrtVXn3ROqdEubHcZKRHwFv7ae7e+t+qGewWtS5UC1fgLdVD0+zb 85wWG4TNA8i8kcOlKNlm1YJptX4MRaHVqcFte3376D1CY0glCz/lq2M+QCVs8Wp748Lh PAsg== X-Forwarded-Encrypted: i=1; AJvYcCXaNJa8Pn6M1bR+6qCyFWcz36gpBcX/dx1M2mVfQKkK6P5Q6hHDyjg4ECXRrN/OZPgSZkmczAiU/GqgoDLenMuiQFKTl/NHpwAKveMJTAIBjyK0QeKhi7G/wABhTxdpxlBK1iU+/HlDC1jAjKZEpH7mTwzGcqXB7/pRITud0oRbG5cRUJWZ4A4m+5neXXsOrZRcqA0ZWL6sm2y070TAgBCZs9AZNzAt4iH9zcIt X-Gm-Message-State: AOJu0YwGc3fdIF7ZTxgieHyBBmxVc4SrNCa/Z5UI5C9SNOMaSKx7b5+Q hYWHxd3Nk4D98s4D76OSIBKWoP/mZUNLI6of/JdH35RYjxuLB6Zh X-Google-Smtp-Source: AGHT+IE/+k5Tsbp6nBIgFMfvySLFamCErRWzUfdGi9BOaWec59ZSeEqFgNaFrSCJw9WqKK0Y18a7cw== X-Received: by 2002:a05:6a21:7896:b0:1af:cefe:dba3 with SMTP id adf61e73a8af0-1afddee489emr15338579637.0.1715676522439; Tue, 14 May 2024 01:48:42 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.38 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48:41 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 14/16] lib/test_min_heap: Add test for heap_del() Date: Tue, 14 May 2024 16:47:22 +0800 Message-Id: <20240514084724.557100-15-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 test cases for the min_heap_del() to ensure its functionality is thoroughly tested. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- lib/test_min_heap.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 0b5037b4bd68..d40851cfd824 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -165,6 +165,40 @@ static __init int test_heap_pop_push(bool min_heap) return err; } =20 +static __init int test_heap_del(bool min_heap) +{ + int values[] =3D { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, + -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; + struct min_heap_test heap; + + min_heap_init(&heap, values, ARRAY_SIZE(values)); + heap.nr =3D ARRAY_SIZE(values); + struct min_heap_callbacks funcs =3D { + .less =3D min_heap ? less_than : greater_than, + .swp =3D swap_ints, + }; + int i, err; + + /* Test with known set of values. */ + min_heapify_all(&heap, &funcs, NULL); + for (i =3D 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err =3D pop_verify_heap(min_heap, &heap, &funcs); + + + /* Test with randomly generated values. */ + heap.nr =3D ARRAY_SIZE(values); + for (i =3D 0; i < heap.nr; i++) + values[i] =3D get_random_u32(); + min_heapify_all(&heap, &funcs, NULL); + + for (i =3D 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err +=3D pop_verify_heap(min_heap, &heap, &funcs); + + return err; +} + static int __init test_min_heap_init(void) { int err =3D 0; @@ -175,6 +209,8 @@ static int __init test_min_heap_init(void) err +=3D test_heap_push(false); err +=3D test_heap_pop_push(true); err +=3D test_heap_pop_push(false); + err +=3D test_heap_del(true); + err +=3D test_heap_del(false); if (err) { pr_err("test failed with %d errors\n", err); return -EINVAL; --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f50.google.com (mail-pj1-f50.google.com [209.85.216.50]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 8E439224CE; Tue, 14 May 2024 08:48:48 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.50 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676531; cv=none; b=mInKCpRQzgPTb2rdUXB80VCEx59gB8PtVmGjnAH3HVlsxNPr+1LBxVm8j4y0sc+2muWw2DhskDQbxy0UyZ6b9wM5zFBh3ac8o4B+dsy06gI26mOVGo6NPisZre4TMwK9yUV3Bvgu4V98FqXxidCsrab+/iWMhOhmEJfQPw83s/w= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676531; c=relaxed/simple; bh=oUBQ93RlORVgLLzujf/bPzqsBV7gnhox2bJaWTkJJcM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=UhiVD4OU0jABpXQ+AzJXAYsyH+vgSTbkniskHcc1jig8SwNWgddxoFJYrKdEe2XNB3oiec1cVE7la3KQtK+L/lLUQ40FzR1sWZf8OC7m5dkeZJGJMWDAMhRWcLbnI5ylvIbuajlB+wpfHuPZ6DAQZiUkfPNhhcG+1y6cLusu9m8= 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=ED0mPTpf; arc=none smtp.client-ip=209.85.216.50 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="ED0mPTpf" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-2b4b30702a5so1342853a91.1; Tue, 14 May 2024 01:48:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676528; x=1716281328; 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=kAQqvLmnTydFnAC2eV9eKYPVBSe1+sbe73fPu9TJR3o=; b=ED0mPTpfTln+E6MjqP4ZWyaTmTRm1wH3dyfXlb1WdtEQJQwnTvhlRxHBA5OzVXNQVU c8Xt97NopQXlCfarFecKLq/h81GP9cKBVe7ImPayQrnPi+0NlatBt/ZDlu6SLBlInxj+ vnkfrIIXaR9b7ScUh3QJAcsUv+U8a/+ulluP0a3p4gSvCg1VnDHJUpk98XCGlynhtf0g JC11fZrUNTNzYyAmAK1uBNe/wXYD7g2e8TKYeihsONuSAY1iXyw02kLPDK2gXn+DtMaD NPJ3M/5qGF5wljaaAkT5l27lLJJqVrn0d3qSIYzv9HYekCbQ89rAedtFVEXcSs9lx0+x ckxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676528; x=1716281328; 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=kAQqvLmnTydFnAC2eV9eKYPVBSe1+sbe73fPu9TJR3o=; b=TVwidiCOPEhjMYL2T1ij4S5qSIhiTdLFPyCDYC9DoOnlqVMVeOZ4eqq6GJYUuaialh WclowOl9yWIwYKzVaIxf0WjMaTdhM/WyOaJHi4arFybZE/I/o4hTvSSXmCfzzqTg9GVr Sy60L+YzOjKyDnD3ocJVxT4GdSGuZDgGTfK5IICYGkyE9r3XmuTLYCyk4W+rbYO/Tlcn IFkv6JHC7H1B2ztzxoRgAzoZpokJPuaXBN0zGZ3x7bo05QKt8WVPto0mNiyyTaT4FXnT LvsgRmt7o9t6mWGuSTSBgXynuo2Acnk+0JEYADzmBDKvmsgUtdLR1jsvrD8a56DE6oXs BQug== X-Forwarded-Encrypted: i=1; AJvYcCU4iNthomZc+QbLFBBCXn4O7V+k5xYSxjm1qs1YjemYYa+pl+Z0ikQntfMXFJzcwU/3D/wUTr97K2Gwr4PJ7MEH4EvxzTdeeklPwfkqwaLDyViMAvrY2HiTcWHTVuFT4T1rFAScU3ABpmmpc0i2X3xz+1uAu3zftxiU+mrjY8QF0CgtpGRiRmM4U9bf2Fghvw0w0Uo/4vwuZSgyRZ11LwTUJpB78z6+DIjSu1k1 X-Gm-Message-State: AOJu0Yypeli+GQ193rXFB/0XaR7wYT5IwGVwBAuU2ROlxgiGpKHdEeLs vWIRfNY1AGRzmRtGTVYXa9nDXVeove7TNY1Tp2FFTpQEZB1lxU3nV/G5Ag== X-Google-Smtp-Source: AGHT+IHWD4pNXGVxuwpDdsvPIK4+Z4KHjKYIxQH6YdLfOcCIhIPdY0VsL47/jkRUxblI2TA+IN4OTA== X-Received: by 2002:a05:6a21:6da1:b0:1af:cd45:59a9 with SMTP id adf61e73a8af0-1afde0b7213mr14735963637.2.1715676527366; Tue, 14 May 2024 01:48:47 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.43 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48:46 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 15/16] bcache: Remove heap-related macros and switch to generic min_heap Date: Tue, 14 May 2024 16:47:23 +0800 Message-Id: <20240514084724.557100-16-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Acked-by: Coly Li --- Changes in v5: - Rebase on the block tree to resolve the conflict in bcache. - Fix missing initialization for heap data pointer in bcache's bch_btree_node_read_done(). drivers/md/bcache/alloc.c | 64 +++++++++++++----- drivers/md/bcache/bcache.h | 2 +- drivers/md/bcache/bset.c | 124 ++++++++++++++++++++++------------ drivers/md/bcache/bset.h | 40 +++++------ drivers/md/bcache/btree.c | 69 +++++++++++-------- drivers/md/bcache/extents.c | 53 +++++++++------ drivers/md/bcache/movinggc.c | 41 ++++++++--- drivers/md/bcache/super.c | 3 +- drivers/md/bcache/sysfs.c | 4 +- drivers/md/bcache/util.h | 67 +----------------- drivers/md/bcache/writeback.c | 13 ++-- 11 files changed, 263 insertions(+), 217 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index ce13c272c387..8cfa15ea32b4 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -166,40 +166,68 @@ 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 new_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 new_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 new_bucket_prio(ca, *lhs) > new_bucket_prio(ca, *rhs); +} =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)) +static inline bool new_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 new_bucket_prio(ca, *lhs) < new_bucket_prio(ca, *rhs); +} + +static inline void new_bucket_swap(void *l, void *r, void __always_unused = *args) +{ + struct bucket **lhs =3D l, **rhs =3D 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 new_bucket_max_cmp, + .swp =3D new_bucket_swap, + }; + const struct min_heap_callbacks bucket_min_cmp_callback =3D { + .less =3D new_bucket_min_cmp, + .swp =3D new_bucket_swap, + }; =20 - ca->heap.used =3D 0; + ca->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))) { + if (!min_heap_full(&ca->heap)) + min_heap_push(&ca->heap, &b, &bucket_max_cmp_callback, ca); + else if (!new_bucket_max_cmp(&b, min_heap_peek(&ca->heap), ca)) { ca->heap.data[0] =3D b; - heap_sift(&ca->heap, 0, bucket_max_cmp); + 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)) { + if (!ca->heap.nr) { /* * We don't want to be calling invalidate_buckets() * multiple times when it can't do anything @@ -208,6 +236,8 @@ static void invalidate_buckets_lru(struct cache *ca) wake_up_gc(ca->set); return; } + b =3D min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca); =20 bch_invalidate_one_bucket(ca, b); } diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h index 4e6afa89921f..575d1e3a5217 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 *, cache_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 463eb13bd0b2..bd97d8626887 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -54,9 +54,11 @@ void bch_dump_bucket(struct btree_keys *b) int __bch_count_data(struct btree_keys *b) { unsigned int ret =3D 0; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + if (b->ops->is_extents) for_each_key(b, k, &iter) ret +=3D KEY_SIZE(k); @@ -67,9 +69,11 @@ void __bch_check_keys(struct btree_keys *b, const char *= fmt, ...) { va_list args; struct bkey *k, *p =3D NULL; - struct btree_iter_stack iter; + struct btree_iter iter; const char *err; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key(b, k, &iter) { if (b->ops->is_extents) { err =3D "Keys out of order"; @@ -110,9 +114,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 iter->heap.data->k, *next =3D bkey_next(k); =20 - if (next < iter->data->end && + if (next < iter->heap.data->end && bkey_cmp(k, iter->b->ops->is_extents ? &START_KEY(next) : next) > 0) { bch_dump_bucket(iter->b); @@ -879,12 +883,14 @@ unsigned int bch_btree_insert_key(struct btree_keys *= b, struct bkey *k, unsigned int status =3D BTREE_INSERT_STATUS_NO_INSERT; struct bset *i =3D bset_tree_last(b)->data; struct bkey *m, *prev =3D NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey preceding_key_on_stack =3D ZERO_KEY; struct bkey *preceding_key_p =3D &preceding_key_on_stack; =20 BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* * If k has preceding key, preceding_key_p will be set to address * of k's preceding key; otherwise preceding_key_p will be set @@ -895,9 +901,9 @@ unsigned int bch_btree_insert_key(struct btree_keys *b,= struct bkey *k, else preceding_key(k, &preceding_key_p); =20 - m =3D bch_btree_iter_stack_init(b, &iter, preceding_key_p); + m =3D bch_btree_iter_init(b, &iter, preceding_key_p); =20 - if (b->ops->insert_fixup(b, k, &iter.iter, replace_key)) + if (b->ops->insert_fixup(b, k, &iter, replace_key)) return status; =20 status =3D BTREE_INSERT_STATUS_INSERT; @@ -1077,79 +1083,102 @@ 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 (new_btree_iter_cmp_fn)(const void *, const void *, void *); + +static inline bool new_btree_iter_cmp(const void *l, const void *r, void _= _always_unused *args) +{ + 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_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __al= ways_unused *args) { - return bkey_cmp(l.k, r.k) > 0; + struct btree_iter_set *_iter1 =3D iter1; + struct btree_iter_set *_iter2 =3D iter2; + + swap(*_iter1, *_iter2); } =20 static inline bool btree_iter_end(struct btree_iter *iter) { - return !iter->used; + return !iter->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 new_btree_iter_cmp, + .swp =3D new_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_stack_init(struct btree_keys *b, - struct btree_iter_stack *iter, - struct bkey *search, - struct bset_tree *start) +static struct bkey *__bch_btree_iter_init(struct btree_keys *b, + struct btree_iter *iter, + struct bkey *search, + struct bset_tree *start) { struct bkey *ret =3D NULL; =20 - iter->iter.size =3D ARRAY_SIZE(iter->stack_data); - iter->iter.used =3D 0; + iter->heap.size =3D ARRAY_SIZE(iter->heap.preallocated); + iter->heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG - iter->iter.b =3D b; + iter->b =3D b; #endif =20 for (; start <=3D bset_tree_last(b); start++) { ret =3D bch_bset_search(b, start, search); - bch_btree_iter_push(&iter->iter, ret, bset_bkey_last(start->data)); + bch_btree_iter_push(iter, ret, bset_bkey_last(start->data)); } =20 return ret; } =20 -struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, - struct btree_iter_stack *iter, +struct bkey *bch_btree_iter_init(struct btree_keys *b, + struct btree_iter *iter, struct bkey *search) { - return __bch_btree_iter_stack_init(b, iter, search, b->set); + return __bch_btree_iter_init(b, iter, search, b->set); } =20 static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, - btree_iter_cmp_fn *cmp) + new_btree_iter_cmp_fn *cmp) { struct btree_iter_set b __maybe_unused; struct bkey *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D cmp, + .swp =3D new_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 iter->heap.data->k; + iter->heap.data->k =3D bkey_next(iter->heap.data->k); =20 - if (iter->data->k > iter->data->end) { + if (iter->heap.data->k > iter->heap.data->end) { WARN_ONCE(1, "bset was corrupt!\n"); - iter->data->k =3D iter->data->end; + iter->heap.data->k =3D iter->heap.data->end; } =20 - if (iter->data->k =3D=3D iter->data->end) - heap_pop(iter, b, cmp); + if (iter->heap.data->k =3D=3D iter->heap.data->end) { + if (iter->heap.nr) { + b =3D min_heap_peek(&iter->heap)[0]; + 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; @@ -1157,7 +1186,7 @@ static inline struct bkey *__bch_btree_iter_next(stru= ct btree_iter *iter, =20 struct bkey *bch_btree_iter_next(struct btree_iter *iter) { - return __bch_btree_iter_next(iter, btree_iter_cmp); + return __bch_btree_iter_next(iter, new_btree_iter_cmp); =20 } =20 @@ -1195,16 +1224,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 new_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) @@ -1293,10 +1324,11 @@ void bch_btree_sort_partial(struct btree_keys *b, u= nsigned int start, struct bset_sort_state *state) { size_t order =3D b->page_order, keys =3D 0; - struct btree_iter_stack iter; + struct btree_iter iter; int oldsize =3D bch_count_data(b); =20 - __bch_btree_iter_stack_init(b, &iter, NULL, &b->set[start]); + min_heap_init(&iter.heap, NULL, MAX_BSETS); + __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); =20 if (start) { unsigned int i; @@ -1307,7 +1339,7 @@ void bch_btree_sort_partial(struct btree_keys *b, uns= igned int start, order =3D get_order(__set_bytes(b->set->data, keys)); } =20 - __btree_sort(b, &iter.iter, start, order, false, state); + __btree_sort(b, &iter, start, order, false, state); =20 EBUG_ON(oldsize >=3D 0 && bch_count_data(b) !=3D oldsize); } @@ -1323,11 +1355,13 @@ void bch_btree_sort_into(struct btree_keys *b, stru= ct btree_keys *new, struct bset_sort_state *state) { uint64_t start_time =3D local_clock(); - struct btree_iter_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); =20 - bch_btree_iter_stack_init(b, &iter, NULL); + bch_btree_iter_init(b, &iter, NULL); =20 - btree_mergesort(b, new->set->data, &iter.iter, false, true); + btree_mergesort(b, new->set->data, &iter, false, true); =20 bch_time_stats_update(&state->time, start_time); =20 diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index 011f6062c4c0..f79441acd4c1 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -187,8 +187,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, @@ -312,23 +313,17 @@ enum { BTREE_INSERT_STATUS_FRONT_MERGE, }; =20 +struct btree_iter_set { + struct bkey *k, *end; +}; + /* Btree key iteration */ =20 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[]; -}; - -/* Fixed-size btree_iter that can be allocated on the stack */ - -struct btree_iter_stack { - struct btree_iter iter; - struct btree_iter_set stack_data[MAX_BSETS]; + MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) = heap; }; =20 typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); @@ -340,9 +335,9 @@ struct bkey *bch_btree_iter_next_filter(struct btree_it= er *iter, =20 void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end); -struct bkey *bch_btree_iter_stack_init(struct btree_keys *b, - struct btree_iter_stack *iter, - struct bkey *search); +struct bkey *bch_btree_iter_init(struct btree_keys *b, + struct btree_iter *iter, + struct bkey *search); =20 struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, const struct bkey *search); @@ -357,14 +352,13 @@ static inline struct bkey *bch_bset_search(struct btr= ee_keys *b, return search ? __bch_bset_search(b, t, search) : t->data->start; } =20 -#define for_each_key_filter(b, k, stack_iter, filter) = \ - for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ - ((k) =3D bch_btree_iter_next_filter(&((stack_iter)->iter), (b), \ - filter));) +#define for_each_key_filter(b, k, iter, filter) \ + for (bch_btree_iter_init((b), (iter), NULL); \ + ((k) =3D bch_btree_iter_next_filter((iter), (b), filter));) =20 -#define for_each_key(b, k, stack_iter) \ - for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ - ((k) =3D bch_btree_iter_next(&((stack_iter)->iter)));) +#define for_each_key(b, k, iter) \ + for (bch_btree_iter_init((b), (iter), NULL); \ + ((k) =3D bch_btree_iter_next(iter));) =20 /* Sorting */ =20 diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c index d011a7154d33..ce9d729bc8ff 100644 --- a/drivers/md/bcache/btree.c +++ b/drivers/md/bcache/btree.c @@ -149,19 +149,19 @@ void bch_btree_node_read_done(struct btree *b) { const char *err =3D "bad btree header"; struct bset *i =3D btree_bset_first(b); - struct btree_iter *iter; + struct btree_iter iter; =20 /* * c->fill_iter can allocate an iterator with more memory space * than static MAX_BSETS. * 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.data =3D mempool_alloc(&b->c->fill_iter, GFP_NOIO); + iter.heap.size =3D b->c->cache->sb.bucket_size / b->c->cache->sb.block_si= ze; + iter.heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG - iter->b =3D &b->keys; + iter.b =3D &b->keys; #endif =20 if (!i->seq) @@ -199,7 +199,7 @@ void bch_btree_node_read_done(struct btree *b) if (i !=3D b->keys.set[0].data && !i->keys) goto err; =20 - bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); + bch_btree_iter_push(&iter, i->start, bset_bkey_last(i)); =20 b->written +=3D set_blocks(i, block_bytes(b->c->cache)); } @@ -211,7 +211,7 @@ void bch_btree_node_read_done(struct btree *b) if (i->seq =3D=3D b->keys.set[0].data->seq) goto err; =20 - bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); + bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort); =20 i =3D b->keys.set[0].data; err =3D "short btree key"; @@ -223,7 +223,7 @@ void bch_btree_node_read_done(struct btree *b) bch_bset_init_next(&b->keys, write_block(b), bset_magic(&b->c->cache->sb)); out: - mempool_free(iter, &b->c->fill_iter); + mempool_free(iter.heap.data, &b->c->fill_iter); return; err: set_btree_node_io_error(b); @@ -1309,9 +1309,11 @@ static bool btree_gc_mark_node(struct btree *b, stru= ct gc_stat *gc) uint8_t stale =3D 0; unsigned int keys =3D 0, good_keys =3D 0; struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; struct bset_tree *t; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + gc->nodes++; =20 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { @@ -1570,9 +1572,11 @@ static int btree_gc_rewrite_node(struct btree *b, st= ruct btree_op *op, static unsigned int btree_gc_count_keys(struct btree *b) { struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; unsigned int ret =3D 0; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) ret +=3D bkey_u64s(k); =20 @@ -1611,18 +1615,18 @@ static int btree_gc_recurse(struct btree *b, struct= btree_op *op, int ret =3D 0; bool should_rewrite; struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; struct gc_merge_info r[GC_MERGE_NODES]; struct gc_merge_info *i, *last =3D r + ARRAY_SIZE(r) - 1; =20 - bch_btree_iter_stack_init(&b->keys, &iter, &b->c->gc_done); + min_heap_init(&iter.heap, NULL, MAX_BSETS); + bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); =20 for (i =3D r; i < r + ARRAY_SIZE(r); i++) i->b =3D ERR_PTR(-EINTR); =20 while (1) { - k =3D bch_btree_iter_next_filter(&iter.iter, &b->keys, - bch_ptr_bad); + k =3D bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); if (k) { r->b =3D bch_btree_node_get(b->c, op, k, b->level - 1, true, b); @@ -1912,7 +1916,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_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); =20 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(b->c, b->level, k); @@ -1920,10 +1926,10 @@ static int bch_btree_check_recurse(struct btree *b,= struct btree_op *op) bch_initial_mark_key(b->c, b->level + 1, &b->key); =20 if (b->level) { - bch_btree_iter_stack_init(&b->keys, &iter, NULL); + bch_btree_iter_init(&b->keys, &iter, NULL); =20 do { - k =3D bch_btree_iter_next_filter(&iter.iter, &b->keys, + k =3D bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); if (k) { btree_node_prefetch(b, k); @@ -1951,7 +1957,7 @@ static int bch_btree_check_thread(void *arg) struct btree_check_info *info =3D arg; struct btree_check_state *check_state =3D info->state; struct cache_set *c =3D check_state->c; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; =20 @@ -1959,9 +1965,11 @@ static int bch_btree_check_thread(void *arg) cur_idx =3D prev_idx =3D 0; ret =3D 0; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* root node keys are checked before thread created */ - bch_btree_iter_stack_init(&c->root->keys, &iter, NULL); - k =3D bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad); + bch_btree_iter_init(&c->root->keys, &iter, NULL); + k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); BUG_ON(!k); =20 p =3D k; @@ -1979,7 +1987,7 @@ static int bch_btree_check_thread(void *arg) skip_nr =3D cur_idx - prev_idx; =20 while (skip_nr) { - k =3D bch_btree_iter_next_filter(&iter.iter, + k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); if (k) @@ -2052,9 +2060,11 @@ int bch_btree_check(struct cache_set *c) int ret =3D 0; int i; struct bkey *k =3D NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct btree_check_state check_state; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* check and mark root node keys */ for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(c, c->root->level, k); @@ -2548,11 +2558,12 @@ static int bch_btree_map_nodes_recurse(struct btree= *b, struct btree_op *op, =20 if (b->level) { struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; =20 - bch_btree_iter_stack_init(&b->keys, &iter, from); + min_heap_init(&iter.heap, NULL, MAX_BSETS); + bch_btree_iter_init(&b->keys, &iter, from); =20 - while ((k =3D bch_btree_iter_next_filter(&iter.iter, &b->keys, + while ((k =3D bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { ret =3D bcache_btree(map_nodes_recurse, k, b, op, from, fn, flags); @@ -2581,12 +2592,12 @@ int bch_btree_map_keys_recurse(struct btree *b, str= uct btree_op *op, { int ret =3D MAP_CONTINUE; struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; =20 - bch_btree_iter_stack_init(&b->keys, &iter, from); + min_heap_init(&iter.heap, NULL, MAX_BSETS); + bch_btree_iter_init(&b->keys, &iter, from); =20 - while ((k =3D bch_btree_iter_next_filter(&iter.iter, &b->keys, - bch_ptr_bad))) { + while ((k =3D bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { ret =3D !b->level ? fn(op, b, k) : bcache_btree(map_keys_recurse, k, diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index d626ffcbecb9..a7221e5dbe81 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -33,15 +33,16 @@ 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]; + *i =3D iter->heap.data[--iter->heap.nr]; } =20 -static bool bch_key_sort_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static bool new_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) @@ -238,7 +239,7 @@ static bool bch_btree_ptr_insert_fixup(struct btree_key= s *bk, } =20 const struct btree_keys_ops bch_btree_keys_ops =3D { - .sort_cmp =3D bch_key_sort_cmp, + .sort_cmp =3D new_bch_key_sort_cmp, .insert_fixup =3D bch_btree_ptr_insert_fixup, .key_invalid =3D bch_btree_ptr_invalid, .key_bad =3D bch_btree_ptr_bad, @@ -255,22 +256,36 @@ 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 new_bch_extent_sort_cmp(const void *l, const void *r, void __a= lways_unused *args) +{ + 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)); + + return !(c ? c > 0 : _l->k < _r->k); +} + +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __al= ways_unused *args) { - int64_t c =3D bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); + struct btree_iter_set *_iter1 =3D iter1; + struct btree_iter_set *_iter2 =3D iter2; =20 - return c ? c > 0 : l.k < r.k; + swap(*_iter1, *_iter2); } =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; - - if (iter->used > 2 && - bch_extent_sort_cmp(i[0], i[1])) + const struct min_heap_callbacks callbacks =3D { + .less =3D new_bch_extent_sort_cmp, + .swp =3D new_btree_iter_swap, + }; + while (iter->heap.nr > 1) { + struct btree_iter_set *top =3D iter->heap.data, *i =3D top + 1; + + if (iter->heap.nr > 2 && + !new_bch_extent_sort_cmp(&i[0], &i[1], NULL)) i++; =20 if (bkey_cmp(top->k, &START_KEY(i->k)) <=3D 0) @@ -278,7 +293,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 +303,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 +313,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 { @@ -618,7 +633,7 @@ static bool bch_extent_merge(struct btree_keys *bk, } =20 const struct btree_keys_ops bch_extent_keys_ops =3D { - .sort_cmp =3D bch_extent_sort_cmp, + .sort_cmp =3D new_bch_extent_sort_cmp, .sort_fixup =3D bch_extent_sort_fixup, .insert_fixup =3D bch_extent_insert_fixup, .key_invalid =3D bch_extent_invalid, diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index ebd500bdf0b2..7f482729c56d 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 new_bucket_cmp(const void *l, const void *r, void __always_unu= sed *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 new_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)[0]) ? 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 new_bucket_cmp, + .swp =3D new_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.nr =3D 0; =20 for_each_bucket(b, ca) { if (GC_MARK(b) =3D=3D GC_MARK_METADATA || @@ -218,25 +233,31 @@ 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 (!new_bucket_cmp(&b, min_heap_peek(&ca->heap), ca)) { 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_sift_down(&ca->heap, 0, &callbacks, NULL); } } =20 while (sectors_to_move > reserve_sectors) { - heap_pop(&ca->heap, b, bucket_cmp); + if (ca->heap.nr) { + b =3D min_heap_peek(&ca->heap)[0]; + 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 (ca->heap.nr) { + b =3D min_heap_peek(&ca->heap)[0]; + 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 cba09660148a..c6f5592996a8 100644 --- a/drivers/md/bcache/super.c +++ b/drivers/md/bcache/super.c @@ -1914,8 +1914,7 @@ struct cache_set *bch_cache_set_alloc(struct cache_sb= *sb) INIT_LIST_HEAD(&c->btree_cache_freed); INIT_LIST_HEAD(&c->data_buckets); =20 - iter_size =3D sizeof(struct btree_iter) + - ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) * + iter_size =3D ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) * sizeof(struct btree_iter_set); =20 c->devices =3D kcalloc(c->nr_uuids, sizeof(void *), GFP_KERNEL); diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c index 826b14cae4e5..e8f696cb58c0 100644 --- a/drivers/md/bcache/sysfs.c +++ b/drivers/md/bcache/sysfs.c @@ -660,7 +660,9 @@ static unsigned int bch_root_usage(struct cache_set *c) unsigned int bytes =3D 0; struct bkey *k; struct btree *b; - struct btree_iter_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); =20 goto lock_root; =20 diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h index f61ab1bada6c..539454d8e2d0 100644 --- a/drivers/md/bcache/util.h +++ b/drivers/md/bcache/util.h @@ -9,6 +9,7 @@ #include #include #include +#include #include #include #include @@ -30,16 +31,10 @@ 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)->nr =3D 0; \ (heap)->size =3D (_size); \ _bytes =3D (heap)->size * sizeof(*(heap)->data); \ (heap)->data =3D kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ @@ -52,64 +47,6 @@ do { \ (heap)->data =3D NULL; \ } while (0) =20 -#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; \ diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c index 792e070ccf38..c1d28e365910 100644 --- a/drivers/md/bcache/writeback.c +++ b/drivers/md/bcache/writeback.c @@ -908,15 +908,16 @@ static int bch_dirty_init_thread(void *arg) struct dirty_init_thrd_info *info =3D arg; struct bch_dirty_init_state *state =3D info->state; struct cache_set *c =3D state->c; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; =20 k =3D p =3D NULL; prev_idx =3D 0; =20 - bch_btree_iter_stack_init(&c->root->keys, &iter, NULL); - k =3D bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad); + min_heap_init(&iter.heap, NULL, MAX_BSETS); + bch_btree_iter_init(&c->root->keys, &iter, NULL); + k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); BUG_ON(!k); =20 p =3D k; @@ -930,7 +931,7 @@ static int bch_dirty_init_thread(void *arg) skip_nr =3D cur_idx - prev_idx; =20 while (skip_nr) { - k =3D bch_btree_iter_next_filter(&iter.iter, + k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); if (k) @@ -979,11 +980,13 @@ void bch_sectors_dirty_init(struct bcache_device *d) int i; struct btree *b =3D NULL; struct bkey *k =3D NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct sectors_dirty_init op; struct cache_set *c =3D d->c; struct bch_dirty_init_state state; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + retry_lock: b =3D c->root; rw_lock(0, b, b->level); --=20 2.34.1 From nobody Wed Feb 11 01:27:22 2026 Received: from mail-pj1-f45.google.com (mail-pj1-f45.google.com [209.85.216.45]) (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 0AF51374D2; Tue, 14 May 2024 08:48:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.45 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676534; cv=none; b=JYrzGl2WhrKzzBAc7ewc+2eoH0Ol6pskPbc7PCBC7G4iQePxgNP6dfvKMvIzGZNt0/ZEPLqxP2ePqBXyHMnoKKk7AZ+KBjy7hQoZFAxwlD/yVWvZCXLT7rrTsrmQTZG5Z0tZMk4U1E3EYbfQA4uRoitx9NrPL2ec60LjMR3yVoA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1715676534; c=relaxed/simple; bh=CYJPttL+JF8N5/NTkoHY1q+LgvV7Sz6Pl1uxkoyDlPQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=sWcYhgNXN5F1J5CbJDvC8EE6CzGVumVrFYDAl8Sa5amk4Yz1qLQU4NhoduKA/X7SSRzx/J8RrGL6Y01CcTmvMGpNUPDkX2hjCt6v8ZGK5z1fZW/Us7nP52cmmys3SUMoA16wWcNDCZe7S0ZEe++NqXWkcTROc4O/ChWHi9eEXiY= 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=HrgcKoME; arc=none smtp.client-ip=209.85.216.45 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="HrgcKoME" Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-2b360096cc4so1334834a91.1; Tue, 14 May 2024 01:48:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1715676532; x=1716281332; 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=YsW/NrQIz4qgIL+42NXiwZPni65tkbkU75mwRevJWaw=; b=HrgcKoMEkVAYy+t0NQIYrScIyJQILx4leLSzQa+R+0OMxL3GojKF4R3KtWrW2MgvAo yjH2MT/jtbsKeOYXIjMD7ZojJOSwAVBuE2/Km1eHfuenMjtp1Tlfa9Kj+cJQijV+BAsi dMOCtG6t+C8ZFMnkWdWTBJm68fV6tmOnRSq2hjheuAN/0xPfBnltvgH315fv3XJHx+Yc VtvnThXqrolXKV7zhXtLCutcYE7eEqRWnkmmdgSF8dxqIA7tNFeIw6EkkenLhOL8Eoqc aXb5Q4KpO4gQDNhwjVWLdFgkixOgYm3eg4Dql/KJSze1MxTf/xIlJ/fFIpZEcr0/ICMy HxQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1715676532; x=1716281332; 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=YsW/NrQIz4qgIL+42NXiwZPni65tkbkU75mwRevJWaw=; b=QgB5b/8ZWcUwGtAuBWITGFkSsCTiG+7+z0r9Gaexq+dtHV6l/qipTdAC/LsNE/lgiH 3AJbnVhG6V2oMLw7+fjW+cIpUFd2+roZ2Dt0A2H2vXdAWC4EXtbZ9p0X5ZsypBxAJ57E NvLCiNqnoXc+O2QDB06VTKNexYeWW0XgP+B9FAHOYRI/CTnZxgcoy9s4jPQFJ/LBwXHA NUgeFeBfLTMhJd7ihL5lV6+tb2zoeHcivRfNtoQD5mWoH08GN9PFjFxefPg+NoJWgmO7 3xXItDo3QCBT1MIu/X/0tvgq038OtkK678KHur/veEPriUZDBtpVGZzc3EYgV9JsfgUc wydA== X-Forwarded-Encrypted: i=1; AJvYcCVPBPZRrjt7xgmap9iiK0xm6nGgUcD9uMK+sx+dSCtbYHrsFjT3gZPV/Hv/uXLL2ivvdHoD2lzlbzr2s50iVfrYyG4mtn5g1PsaK9zQZ/Tq5i77Y7PSfg4bLfgeb63ic6+qr14Fwky73SJjdySdbV9jWmYWB0QPgplc5qzLaM9KRKpYjTD6EOYmFhEwjqwA3pOvq8czMchZMD9Aq7vn1qBQj7d+ZAdYBExBkutW X-Gm-Message-State: AOJu0Yz8B6N73AjdYQ00pgnfhIk6x6mVxLLKN//39Z6oTZoaEOkKlnzB 8lRHododSG+eFGBIPrn66f/wYdm1Qyzg/hE07DSeJ2EM//LQ9LR/ X-Google-Smtp-Source: AGHT+IEZJBE4DY5W8seUtK7dDgv4H+R9ogDWxkvK6WzOdLPljg9hUEy4MyjVirQowRDmzupDGecTdQ== X-Received: by 2002:a05:6a21:329d:b0:1af:a5e8:d184 with SMTP id adf61e73a8af0-1afde224bd1mr14426210637.5.1715676532311; Tue, 14 May 2024 01:48:52 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2b6711660fdsm9195597a91.16.2024.05.14.01.48.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 14 May 2024 01:48:51 -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, bagasdotme@gmail.com, jserv@ccns.ncku.edu.tw, linux-bcache@vger.kernel.org, linux-kernel@vger.kernel.org, dm-devel@lists.linux.dev, linux-bcachefs@vger.kernel.org, linux-perf-users@vger.kernel.org, Kuan-Wei Chiu Subject: [RESEND PATCH v5 16/16] bcachefs: Remove heap-related macros and switch to generic min_heap Date: Tue, 14 May 2024 16:47:24 +0800 Message-Id: <20240514084724.557100-17-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240514084724.557100-1-visitorckw@gmail.com> References: <20240514084724.557100-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 Acked-by: Kent Overstreet --- fs/bcachefs/clock.c | 43 ++++++++++---- fs/bcachefs/clock_types.h | 2 +- fs/bcachefs/ec.c | 76 ++++++++++++++++-------- fs/bcachefs/ec_types.h | 2 +- fs/bcachefs/util.h | 118 +------------------------------------- 5 files changed, 87 insertions(+), 154 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 363644451106..3ec64fe6a064 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 < (*_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++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[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++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[i] =3D=3D timer) { - heap_del(&clock->timers, i, io_timer_cmp, NULL); + min_heap_del(&clock->timers, i, &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 && + if (clock->timers.nr && time_after_eq(now, clock->timers.data[0]->expire)) - heap_pop(&clock->timers, ret, io_timer_cmp, NULL); + min_heap_pop(&clock->timers, &callbacks, NULL); =20 spin_unlock(&clock->timer_lock); =20 @@ -161,7 +182,7 @@ void bch2_io_timers_to_text(struct printbuf *out, struc= t 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.nr; i++) prt_printf(out, "%ps:\t%li\n", clock->timers.data[i]->fn, clock->timers.data[i]->expire - now); diff --git a/fs/bcachefs/clock_types.h b/fs/bcachefs/clock_types.h index 5fae0012d808..59716e148645 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..ade65173898a 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -866,8 +866,8 @@ static int __ec_stripe_mem_alloc(struct bch_fs *c, size= _t idx, gfp_t gfp) =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; + memcpy(n.data, h->data, h->nr * sizeof(h->data[0])); + n.nr =3D h->nr; swap(*h, n); } mutex_unlock(&c->ec_stripes_heap_lock); @@ -958,7 +958,7 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) =20 lockdep_assert_held(&c->ec_stripes_heap_lock); =20 - if (h->used && + if (h->nr && h->data[0].blocks_nonempty =3D=3D 0 && !bch2_stripe_is_open(c, h->data[0].idx)) return h->data[0].idx; @@ -966,14 +966,6 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) 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) -{ - return ((l.blocks_nonempty > r.blocks_nonempty) - - (l.blocks_nonempty < r.blocks_nonempty)); -} - static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h, size_t i) { @@ -982,39 +974,71 @@ static inline void ec_stripes_heap_set_backpointer(ec= _stripes_heap *h, genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx =3D i; } =20 +static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void = __always_unused *args) +{ + 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) < + (_l->blocks_nonempty < _r->blocks_nonempty)); +} + +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 - _h->data; + size_t j =3D _r - _h->data; + + swap(*_l, *_r); + + ec_stripes_heap_set_backpointer(_h, i); + ec_stripes_heap_set_backpointer(_h, j); +} + 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(m->heap_idx >=3D h->nr); BUG_ON(h->data[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.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); @@ -1023,6 +1047,10 @@ void bch2_stripes_heap_insert(struct bch_fs *c, void bch2_stripes_heap_update(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; ec_stripes_heap *h =3D &c->ec_stripes_heap; bool do_deletes; size_t i; @@ -1033,10 +1061,8 @@ void bch2_stripes_heap_update(struct bch_fs *c, h->data[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,7 +1854,7 @@ 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->nr; heap_idx++) { /* No blocks worth reusing, stripe will just be deleted: */ if (!h->data[heap_idx].blocks_nonempty) continue; @@ -2159,7 +2185,7 @@ 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++) { + for (i =3D 0; i < min_t(size_t, h->nr, 50); i++) { m =3D genradix_ptr(&c->stripes, h->data[i].idx); =20 prt_printf(out, "%zu %u/%u+%u", h->data[i].idx, 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 5cf885b09986..d5a1f1e29013 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -8,6 +8,7 @@ #include #include #include +#include #include #include #include @@ -54,17 +55,9 @@ 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)->nr =3D 0; \ (heap)->size =3D (_size); \ (heap)->data =3D kvmalloc((heap)->size * sizeof((heap)->data[0]),\ (gfp)); \ @@ -76,113 +69,6 @@ do { \ (heap)->data =3D NULL; \ } while (0) =20 -#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; \ -}) - -#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) - -#define heap_del(h, i, cmp, set_backpointer) \ -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); \ - } \ -} while (0) - -#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) - #define ANYSINT_MAX(t) \ ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1) =20 --=20 2.34.1