From patchwork Fri May 24 15:29:43 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673270 Received: from mail-pj1-f51.google.com (mail-pj1-f51.google.com [209.85.216.51]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E63C412E1ED for ; Fri, 24 May 2024 15:30:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.51 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564614; cv=none; b=WVTuV7fyt61VS9PWAlIIzHbSmtkTO+o56UxaWyl5ODXO7jPF7eEAxi4CmFG1gonLRPHSx22Al4CrGFkvyy+6BD65H1OSvAuKmd0Ghv7uWtJvoDSpwThBNRygrLh5RZw0Ed3/Sofm3F1/Y5UDIIW+6ObwE8l30R7N5HX4I8vNEA4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564614; c=relaxed/simple; bh=Vb+x/ZZbyvOZEx4tZHTKF+8NUAMDYHXMfePXFUeJ064=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=S98koyxykmvhEVH6vlnIO/2tHJuxLiQl24e8eZ6PBKCyA3VinjiU4yBD5rCCSs/yBsrRIEm+7tudRdFuDddBmPAbuh2eBq81mqANYrkgz6EZRzpCri1SonGE5XbRaFfDAHCkkhjpKWBqlkF3LvTri6J61mT46Y3DnQ9lFJbmu8I= 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=BaMaV8/u; arc=none smtp.client-ip=209.85.216.51 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BaMaV8/u" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-2bf5bb3508fso182729a91.1 for ; Fri, 24 May 2024 08:30:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564612; x=1717169412; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=yA2giIirIzyk3qPOvNZ+vbWO0ihNMW8s6ZdoXXb+0f0=; b=BaMaV8/ulBJc9yRW0OXMjcTl6BnV5/IQxgRJViq72b3VZPE0ZZwovBgR0PEO1/o9AE nfGPtlhqMy2e26euQXqilcIEBPXAolIu/5TyLXofpHKHTrogFv+TseYldfwOkm2GHv0x Q/2jAI/bcJDLA3+y+Vtq5I1Gjv+GCXzc4bZDV3lgxbbjZ4Kcfnii37QeeFh+nHBxn1N8 9YwjLhoUBzFXf0aiS2L+C/ic7/s03OMY/H/Hi3JqdBPEiSaQHOcXNStt52dVPhQhD164 sC2cQLVeT8y9AApwNX180VJ9iENwRFo1viB4HQdFialtJNbGU7afoPbT/XTaYxaDLg4o y5Zg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564612; x=1717169412; 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=yA2giIirIzyk3qPOvNZ+vbWO0ihNMW8s6ZdoXXb+0f0=; b=Zr16FjFJqEOClrf1jD1gcPDKudk7FnMZr8KTjmv4JUO7t/dmMW4JjiTooJaNI/owpE KdmbKS9Y9Uzm/KhtUCQBrzo0azEUlLZqy/B84x0ZhCvmFKDkO0bHRiRKVPGM843GrzHr Wimj2ubL/ie73ql0QmgEzoHmc0IAMyqg50h9X6guq7LOLN3vuVtz1Mg13yL9TkXxsqJg /2pLIMp4Wui33uyXR+sdLlVwhushWD0K45YduPK1mPnxW4oV8Vc7mrjfrRGUeUx2m/O9 InsISEtL3eScqsIPBb93R3YvibdySSImpcB/ogACr8p9oyTvZFR8tYD2ZRCwfns37Xp5 bGHQ== X-Forwarded-Encrypted: i=1; AJvYcCVsPNqqcFdpr98o2Y0zDQVGAA4E6P3F3IwD+qQRh//pIj0ny8OVGGGtOL+Il+z2l8Kl511j0zdQS3llZeEtKHqdIZExcsQS2D4= X-Gm-Message-State: AOJu0YwkKD+JGknvO1QAQarZCPI64RFczyau4GTVus2LXx8wFNM07fxm i0CVKgv2weu+cuFkCZCDCqFvn23CJXtNd3jcVwqkqceWV8jvNpGm X-Google-Smtp-Source: AGHT+IGLArb7OqWEB6CrXg11EyYlnXTDni6xakbN7NY6EO02Mt7rz76EsWl65GGah93FseFaBLmQUg== X-Received: by 2002:a17:90a:df13:b0:2bd:7e73:6628 with SMTP id 98e67ed59e1d1-2bf5e0c1bc4mr2586413a91.0.1716564612133; Fri, 24 May 2024 08:30:12 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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 , Randy Dunlap Subject: [PATCH v6 01/16] perf/core: Fix several typos Date: Fri, 24 May 2024 23:29:43 +0800 Message-Id: <20240524152958.919343-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace '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 f0128c5ff278..5e4ad32aeb71 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); /* - * 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 = 0; /* - * 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 = 1; css; css = css->parent) From patchwork Fri May 24 15:29:44 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673271 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 26DD912EBE4 for ; Fri, 24 May 2024 15:30:17 +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=1716564619; cv=none; b=GZCjhw7Eew5JnC4lAdsPZh0YbMBs8o2kkd1mvRkKv0OYg1CbWEBSQFS5t9Zm+un+iJxGYKTOXdhggTXv/VZGGSkJAvLlMdjFtkmSaGvONCmmr5MLe/0VJqfaA/rgolFEZ9XuIlcyZ1XzWEr4skERtMQkez40XAWXi6DVVT+AyM4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564619; c=relaxed/simple; bh=UN1Xetleeq5Nz5tLKfuxk8/opVO9kM/FjVJ/CVGswXI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=CQbHdIGkn94GZSVq74akq/pdl5ECb8JUSd5Fzmxh9bTyqggARuJN3QvjolRB0uSDiX5NAY0IBlM7IEVxd3746SUq49DhGsOo0UeppQAmjm3JbZI5Mpl6uwdb3gdorTYEXhrC9nyAX92mJN07PM1vhIty8W4Q7IwA/XY1yRIIyek= 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=jLWS6woj; 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="jLWS6woj" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2bf5baa5b76so103224a91.0 for ; Fri, 24 May 2024 08:30:17 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564617; x=1717169417; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=/7grr21+dk77QDv4Gfk7ePfGBs40BXM1/CLzaulLK98=; b=jLWS6woj+oBgqOb4+StxysnxlEWQaOXWvSW2PcV8q4TNxmNTaHsx23lL5TDOUhYTub 4GtvKj9vIxCPhO+BZeupG/MVeI7zAH3G5EzxRDJOidrzaT8M9ryabcvyPpOQ2JdA2vLq BSo6a1B9I5mCbdC97grPWur+Hx6jZMccwBprqz1SftJq63vjLPn+vIyrxz7i1FUzFf9d kBhjvsbQNVQF6Oc56A1c5kTkxpl9mhyq1IIN7gzCiH/WXNyY2Lm6jHBDFMqrgr4gHJfu cmBeuQ1c3yNNAlt35WzAsVpxykG3nQnDyLHW7bnod/6tZhJeYyMebnvAa1YrHxutOkPh Ul5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564617; x=1717169417; 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=q/rSksTBqTQjsWi1cW5EZkfK5/zYEVFDLJU7ZUi496qFMy0UwmcCDrwDBT9wUAysvJ jTqKyOLIo6UjLQFgurRzyk6Sw/e7mlEfXWCuyRianMMWlah0Ypc6t2g5dT/Y9+GjZZAT rHIJYMoFu7r/lKE5wCGqvI5ssvivdu2lKWqokXHw3eRnU7e9fb4LltyMsF/TckNJwYHo Sx26qN3odSiJfhhXOYobhhD+xbRlUoOfX/28RBx+dV5kvik63rFeAeRr4aYTzcg/c27Q Dqysi+5/NaNKQROHxPrKtlAnIc55OB5Df8LC4Fh7wkmywRGaBhxr4n1Vj22+dfcSNEoA GVXQ== X-Forwarded-Encrypted: i=1; AJvYcCVU4MZwDOMBNWnCQD/ESepoYFhOeYwaMM6EcDVKBB9sNqv9rR2Ii7QAGTHkG8rAesSiz1v5C9RRgEpXAMqjy9mnn+n3T9/ZQPI= X-Gm-Message-State: AOJu0Yw+F/lI+IPPPzKVrAdBZ+/GYeAHvL1ZSjm6483jAtGnBOcIBaN7 VSHQRU3whQRtrSpcWg9LW3OIPPGZ8z2lX/d7h98ta3jj/W9ak9cJ X-Google-Smtp-Source: AGHT+IHJimdIMmMybcJm9rH5sITCKczMXcjO3LFGPLj00xSs2zLYla0SwJEjxRlWlGP0XYpBUqSPBA== X-Received: by 2002:a17:90b:24c:b0:2b4:329e:eac5 with SMTP id 98e67ed59e1d1-2bf5f202ac5mr2504048a91.2.1716564617341; Fri, 24 May 2024 08:30:17 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.13 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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 , Randy Dunlap Subject: [PATCH v6 02/16] bcache: Fix typo Date: Fri, 24 May 2024 23:29:44 +0800 Message-Id: <20240524152958.919343-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace '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. From patchwork Fri May 24 15:29:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673272 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 CE99512D77C for ; Fri, 24 May 2024 15:30:22 +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=1716564624; cv=none; b=XQs5KktkYlAVmzLpYhCWO6D/tWg11e98tC5DS/h0voW07OQ4n0AY4oFq0KJKNDbV4QoHyKyMKxWKTfM+gdMVPdTivN67jn+TCfigXHmv4BB1aIhU/+oDxfveet8a5bOn4xnde4llZs7Qml8L8rhNiHLlJJAuwpVOrQL+Mk9AQDE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564624; c=relaxed/simple; bh=QITT4KyTCrPxTa74Hi4WwUV4Z/BKsxAIzezFgyBB9RY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ivlf+s6XAg3bsq9MCnGxzdLwxQeJdxREykqlJ2ErR4R4uECJbZQI2speXUZ1c2JTKZw5J4TWST/qvsL7vZc0u4Tp4v2WXYWUJrB9L5VG00oEl87cywOlw3UspcqBcdgsVAjZDZWQ0qFG9VZBE6LvooldBp4FV3qVXUHUq/G987s= 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=ecUgcZtq; 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="ecUgcZtq" Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-2bde32de7c6so339671a91.0 for ; Fri, 24 May 2024 08:30:22 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564622; x=1717169422; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7KHs5Ddv3q6AjsWj+2TI+65ShPcrkPx2MBMg1+BRFwU=; b=ecUgcZtq04kfcHBuoZccR+VOUXGGxZo3LOy1cKAV5lNpUwZ4G7qyWuTDYjQF98hj+J 8N2fMGhuJJ7RpsHPTp5YfGn1jds81NQQ5eKBxVVMM0viBZmdE/R0b8FMFcmiJJhBo3ch 0Vzljn06P/j9BbIF2xaorlIIB2hBbeAx1ZqnG8lloFI2kBKwJi3phupOzMwYLThVDHLx mA/hQNeem/A9Oehb1R4ExlJs9+vhLgmynKDmElgUtq3D0llHOmoDCWoyLwV+UrGgZ0W/ Zih7fftdb/LjJ8XhEEtbKLT30a1Zo/IKxD7YHlM5EKTX/UzvE1mi+M+2oxAQfXwsOpCK vqcQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564622; x=1717169422; 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=7KHs5Ddv3q6AjsWj+2TI+65ShPcrkPx2MBMg1+BRFwU=; b=BAQOedZkBMZn9feWPrRika4EZ9SzzLmmVcra9a8eXwJJwY0HmOajb8Mdt8R7JpdGKR U/AutR4Q3ed3jOEH0oiogWaf5SiLHNr4bpT+Lmp0LV2/NgX90b8AI4oh3S6AtQP0h6cn GhrLYHjpQp8KcOMrnv15NaOvHl6LP2s+363YpTNGxtLsuXtedsRlGZTeNIhVjSRnwi94 nkycs+nOkeU9C79M7FTV5UUIAr6zmNjlW3+XVvoC6A73ybNJE9gT6p8IeREQl1VWA70K 6J9sMCHjgUCwQSWpah6X4eLsUnnOcBuIcRJuUXYtfp9sD81yAjfQ19qoKDDkLpd476UE +xfA== X-Forwarded-Encrypted: i=1; AJvYcCVkLvBP6VJgHsclWod0eQiA43zkfxxPGsZNbtIghmx2teiaZshoy7CepktK3KqbUmhgkEOoVmdLRkifTJrE/py83Q9Djbclmx4= X-Gm-Message-State: AOJu0Yzn9kusQ4S/Q9rTlJ/UmpG9spKKDi9YWhUvn49sBL08DqTfT0HB IugsmiiIXmMIn55DrI828RNJ+N1BrHG+REeGj9pyfDqI1E7+Yl9f X-Google-Smtp-Source: AGHT+IFVINOfwr0HWjlNIswXxzjjUbfsZzMCUUBzLvajmMapEMWFdTSr6TxSvcR9NlquE4fAbl3ZAw== X-Received: by 2002:a17:90a:ac05:b0:2bd:f770:f95e with SMTP id 98e67ed59e1d1-2bf5e068cd9mr2464878a91.0.1716564622110; Fri, 24 May 2024 08:30:22 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.18 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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 , Randy Dunlap Subject: [PATCH v6 03/16] bcachefs: Fix typo Date: Fri, 24 May 2024 23:29:45 +0800 Message-Id: <20240524152958.919343-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Replace '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 de331dec2a99..65d42206703c 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. From patchwork Fri May 24 15:29:46 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673273 Received: from mail-pj1-f53.google.com (mail-pj1-f53.google.com [209.85.216.53]) (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 E19DF12E1F0 for ; Fri, 24 May 2024 15:30:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564629; cv=none; b=pMSd8xht0h2yG+X/Cl0QkYzRdWIUu5zQWoQwc+WxYP4GPGSrYsPN9XRWhK5a40IQd6CPkgDi9n8rM0I4KU2yUmqt6R/c2Q3c3ixv2xP6A09+7/r08O1uFYARgaATN5nyslEM/LYoaEIopVaS8nSGOiLghrV2pvG8iX1HqyUGBdw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564629; c=relaxed/simple; bh=ePi8L1Dgp9M/7rNmWmbd88wo37MGpDoo2T93Fy5mlRE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fl8VyOcwnBi4ZGPhTxHTptsJ5oROhxpj1oTDrbR/eDjLHC6hFHmrPAteZqXmH6zwxTCk3cbjCrnqDamLWvxAfWp5ZSB6MOnowHS3/9IOjyLGgYsaXzoKduKcwuWcyt4dlXLmq5ZhOiNiMHvmrSxu5jWgpS/zJeoJPQEope/pbKg= 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=PMwxaH3Z; arc=none smtp.client-ip=209.85.216.53 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="PMwxaH3Z" Received: by mail-pj1-f53.google.com with SMTP id 98e67ed59e1d1-2bda88e2b23so405756a91.1 for ; Fri, 24 May 2024 08:30:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564627; x=1717169427; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=YZOhw1zTk3nl6+RUSDFXGPLEVykYLCbUVY2/3joTnBw=; b=PMwxaH3ZiNFLOqlbusPs61fu49TeySzpG0Pc0tFfJKfzpfpW1Qu6Lsjh8jgR4QClVF QV+nwfreooqAkQcmqHebRIkVJs0fD7AeW8Q8iPWNO8ghoSlCRF4rSgPWNqIW2DTMZAkW 34Jf6GHvQayXppjxlGEttQNYIJHPx0Z8Oh1fj+Bvr6fC3/dA1mDQdrSGhnGtpgRHDQlj IWUwPPYaJIdMyElWqF6iwPtGoTMSFr93aB4LPaRhjhk1kTDOJlRL3gvMSVtc3fTZ9vCj x1Kgx8CMMJCTxCKrVtAkqqvmY7iHneU69tv4+X7pXfVo1GB3Sjxt20Rpr+MA0bAGBTJP kNaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564627; x=1717169427; 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=YZOhw1zTk3nl6+RUSDFXGPLEVykYLCbUVY2/3joTnBw=; b=QRPTG5i9FwfzpEQwg7QzTZJ0E1wi/kbQkWeaDA33GiB0ASsHOkVB5nUicjH2uS2bN5 IUQilLzMgHRMAP7vX2rej6h0pknycrgETTQEjersDr3OjmJFOk2xa2eT84uj2uqJ+2E/ q471sJDNle0eUn/ihpCy5O2+FRFO9rWt9gxiI9e/TmNALwvI0st99g1PDZJ4q8QT1ll6 eAhduIhrajDDpNmzF1W+D42bXCRB/pd0KIAp2kB7Qq91zSWlUXN+i7Pnywv/ONtOTgKI 3yZJ7bU44WhwWwfE80qA3Krf7ZWpV5R003RSjTQcvt56G88NvX4vUIpuxAcC1+x9X5vY 1H4g== X-Forwarded-Encrypted: i=1; AJvYcCXQqY0brlTTCmr2nTfsO8ldMtHcL9do/WfsxqJjESoRlFFZS2UcRPbCShtwQY2xKUW4xZ7NEpOpS+BC4EUYy3R6OKXaJ29wi4w= X-Gm-Message-State: AOJu0YzYu/5KEnjAlnQR6kqUB2FtybAiIoyUIJE69ACq1P/184wwTxkn 4Ls3hMNW7f9qtmfywlycmn7afA4X8orVWtD/0RBenNox8YCExzh+ X-Google-Smtp-Source: AGHT+IEm0DAELitU2xTpSXIl0owMJuCUhEg4Hzj7wSLb3bLHlQBpbX9eRpm7XSFnoEn2iXFvJv/mSw== X-Received: by 2002:a17:90b:30d8:b0:2b2:4bff:67b7 with SMTP id 98e67ed59e1d1-2bf5f20893dmr2409291a91.3.1716564626935; Fri, 24 May 2024 08:30:26 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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: [PATCH v6 04/16] lib min_heap: Add type safe interface Date: Fri, 24 May 2024 23:29:46 +0800 Message-Id: <20240524152958.919343-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- Changes in v6: - Rename the MIN_HEAP() macro to DEFINE_MIN_HEAP(). 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..e8ad611fe7c1 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; }; +DEFINE_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 over 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) } static const struct min_heap_callbacks repair_min_heap = { - .elem_size = sizeof(struct numbered_block_mapping), .less = mapping_is_less_than, .swp = swap_mappings, }; static struct numbered_block_mapping *sort_next_heap_element(struct repair_completion *repair) { - struct min_heap *heap = &repair->replay_heap; + struct replay_heap *heap = &repair->replay_heap; struct numbered_block_mapping *last; if (heap->nr == 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 = (struct min_heap) { + repair->replay_heap = (struct replay_heap) { .data = repair->entries, .nr = repair->block_map_entry_count, .size = 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..ef9a6e53109c 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 *item2) } static const struct min_heap_callbacks slab_status_min_heap = { - .elem_size = sizeof(struct slab_status), .less = slab_status_is_less_than, .swp = 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_allocator *allocator) { struct slab_status current_slab_status; - struct min_heap heap; + DEFINE_MIN_HEAP(struct slab_status, heap) heap; int result; struct slab_status *slab_statuses; struct slab_depot *depot = allocator->depot; @@ -3521,7 +3520,7 @@ static int __must_check vdo_prepare_slabs_for_allocation(struct block_allocator return result; /* Sort the slabs by cleanliness, then by emptiness hint. */ - heap = (struct min_heap) { + heap = (struct heap) { .data = slab_statuses, .nr = allocator->slab_count, .size = allocator->slab_count, diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d52daf45861b..92830f41642a 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -7,45 +7,53 @@ #include /** - * 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 DEFINE_MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0) + +typedef DEFINE_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]) /** * 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); }; /* 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 = heap->data; - void *root = data + pos * func->elem_size; + void *root = data + pos * elem_size; int i = pos, j; /* Find the sift-down path all the way to the leaves. */ for (;;) { if (i * 2 + 2 >= heap->nr) break; - left = data + (i * 2 + 1) * func->elem_size; - right = data + (i * 2 + 2) * func->elem_size; + left = data + (i * 2 + 1) * elem_size; + right = data + (i * 2 + 2) * elem_size; i = func->less(left, right) ? i * 2 + 1 : i * 2 + 2; } @@ -54,31 +62,37 @@ void min_heapify(struct min_heap *heap, int pos, i = i * 2 + 1; /* Backtrack to the correct location. */ - while (i != pos && func->less(root, data + i * func->elem_size)) + while (i != pos && func->less(root, data + i * elem_size)) i = (i - 1) / 2; /* Shift the element into its correct place. */ j = i; while (i != pos) { i = (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); } } +#define min_heapify(_heap, _pos, _func) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void min_heapify_all(struct min_heap *heap, +void __min_heapify_all(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { int i; for (i = heap->nr / 2 - 1; i >= 0; i--) - min_heapify(heap, i, func); + __min_heapify(heap, i, elem_size, func); } +#define min_heapify_all(_heap, _func) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) + /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void min_heap_pop(struct min_heap *heap, +void __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { void *data = heap->data; @@ -88,27 +102,33 @@ void min_heap_pop(struct min_heap *heap, /* 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); } +#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); } +#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 = heap->data; @@ -120,17 +140,20 @@ void min_heap_push(struct min_heap *heap, const void *element, /* Place at the end of data. */ pos = heap->nr; - memcpy(data + (pos * func->elem_size), element, func->elem_size); + memcpy(data + (pos * elem_size), element, elem_size); heap->nr++; /* Sift child at pos up. */ for (; pos > 0; pos = (pos - 1) / 2) { - child = data + (pos * func->elem_size); - parent = data + ((pos - 1) / 2) * func->elem_size; + child = data + (pos * elem_size); + parent = data + ((pos - 1) / 2) * elem_size; if (func->less(parent, child)) break; func->swp(parent, child); } } +#define min_heap_push(_heap, _element, _func) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) + #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 5e4ad32aeb71..47cb17adf858 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3701,13 +3701,14 @@ static void swap_ptr(void *l, void *r) swap(*lp, *rp); } +DEFINE_MIN_HEAP(struct perf_event *, perf_event_min_heap); + static const struct min_heap_callbacks perf_min_heap = { - .elem_size = sizeof(struct perf_event *), .less = perf_less_group_idx, .swp = swap_ptr, }; -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 = heap->data; @@ -3741,7 +3742,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, struct perf_cpu_context *cpuctx = 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; @@ -3750,7 +3751,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, if (!ctx->task) { cpuctx = this_cpu_ptr(&perf_cpu_context); - event_heap = (struct min_heap){ + event_heap = (struct perf_event_min_heap){ .data = cpuctx->heap, .nr = 0, .size = cpuctx->heap_size, @@ -3763,7 +3764,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, css = &cpuctx->cgrp->css; #endif } else { - event_heap = (struct min_heap){ + event_heap = (struct perf_event_min_heap){ .data = itrs, .nr = 0, .size = ARRAY_SIZE(itrs), diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 7b01b4387cfb..52efab9fb2f1 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -11,6 +11,8 @@ #include #include +DEFINE_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) } 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 = heap->data; @@ -63,13 +65,12 @@ static __init int test_heapify_all(bool min_heap) { int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; - struct min_heap heap = { + struct min_heap_test heap = { .data = values, .nr = ARRAY_SIZE(values), .size = ARRAY_SIZE(values), }; struct min_heap_callbacks funcs = { - .elem_size = sizeof(int), .less = min_heap ? less_than : greater_than, .swp = swap_ints, }; @@ -96,13 +97,12 @@ static __init int test_heap_push(bool min_heap) const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap = { + struct min_heap_test heap = { .data = values, .nr = 0, .size = ARRAY_SIZE(values), }; struct min_heap_callbacks funcs = { - .elem_size = sizeof(int), .less = min_heap ? less_than : greater_than, .swp = swap_ints, }; @@ -129,13 +129,12 @@ static __init int test_heap_pop_push(bool min_heap) const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap = { + struct min_heap_test heap = { .data = values, .nr = 0, .size = ARRAY_SIZE(values), }; struct min_heap_callbacks funcs = { - .elem_size = sizeof(int), .less = min_heap ? less_than : greater_than, .swp = swap_ints, }; From patchwork Fri May 24 15:29:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673274 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 8097013048C for ; Fri, 24 May 2024 15:30:32 +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=1716564633; cv=none; b=qBKadgoo8TyYVIYwTQopsZva/6sjoY6c7pTuYKaNAOT+ZzJX+lCcfsl2lpRURgTSAOlL1fYBinNGRRAlFUTWD4idJ3q68y/8kXFQNjDHIqrRtmtz33SXhDwGnRVlWLMyb+PwxTcL6qGieCEBvBoMBmUK2Ks3JKp+RscdOk9JWyc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564633; c=relaxed/simple; bh=3Cv/NEYxtL7rses18dsQW99Ih1hbxSO8VST7jRlzjCU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GsGRT7I3UBf3+QUz0wWLItOwsqWsJ4bAib2Z8FoakGRFTzvM60qyJiKIidfvYOMd4pNV+GbdlwtV/oMGRSLSAoDZeIrSWG8JHjtZ5zSk61MmoDAtYIBgwtvSUPkEHJIYqK+3ZAS40ZvgsKRR1KYIKgaoDH7G8Ei4IOkZQJXBbZM= 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=FuTuJO2D; 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="FuTuJO2D" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2bdf439c664so314755a91.3 for ; Fri, 24 May 2024 08:30:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564632; x=1717169432; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=T0fYqR9rcSvYbrkD+sBe/h5jrjzbrTBXD1r+tuRTAZk=; b=FuTuJO2DB/zF301QpjfcAEhFydBM0MDlPK7ikszCM1J+0b/C16IDDw7NVraQirG/mL OJo/quwoPbYq1NtHFfy0EOORgbL0EWFe8zRJgH9gMkLoSmqggd8ZKhpaWQJYPKwdHkme ESvjb4GbR7Keyl4GVyAITJgFK1Dh0agLiu9/82DAHPpmvQZ++oLzPrtDnvRuvJVw4L+A Ts+yxxQhjv6mvrHOdJGLoAKD0bPOllYwF05jToVVYJOy6faDrLZ70IRml8+iHSPCF4jF jtvmHUBoFl9ypMKFCm1kUGErZVNs0TQqoiHNnFJlZckD03c5D6XG+sS+vZlPg6hw8mpW vWrw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564632; x=1717169432; 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=T0fYqR9rcSvYbrkD+sBe/h5jrjzbrTBXD1r+tuRTAZk=; b=J4VqFs3dl2Y8FR9dlqDaD6ZKb8utbqtZQS1ZUc5OW4Fovr+UO/i5MYfEnVCPPgN3Uy Kgrgks3VDGwD92N++Iky+wPFA0/MPqi9aLPB+VshGjuiXxXWCNUTtgsVFMNfyCw1/ENr VsTpQVkOFsz04kbio0142TFIgL9l/uFKUdLb0FT3JkdZxl1NTm4fUIK4ZdOrg4rajMVD wka4ZwH3tsqa6kbXt9Q9vr0mSRxgmz0HkPtNY6wIjqJDHM/6jsacc44cra1cR9bYukTZ Z7olgLN0zGA6seKmSYtuR9YupPC2DJzs95u5OLI0tlUN1tRGoLS955GEsrv14PcU3avU 1dKA== X-Forwarded-Encrypted: i=1; AJvYcCWb+z1+v2fQoB0IvxgHNupS6u88Hewg43qEeE5Tl0g/ltX49YeWXK2iu6vbEq+oVjDFXgnszkTWkY9wF8VicXDc5t6O3qjvX3Y= X-Gm-Message-State: AOJu0Yzxo6VHLb7N+QcP8tc4NB5eLpEKZdxL1f0Z1hdoVJOfsSk3xhWh FsNo3/fp3OuxOLbGhmEH/Tou8yMT1frRnjvU2YvYov24Ku6XlJTt X-Google-Smtp-Source: AGHT+IF8luE1cdHm1AfcM0WoDjZHudhzFqofZ1FcFKJ69yRGqwL7AZUhIIsbkDXV3LM7TdHAleFXCQ== X-Received: by 2002:a17:90b:230e:b0:2bd:76ee:48c2 with SMTP id 98e67ed59e1d1-2bf5e0a7a56mr2494152a91.0.1716564631729; Fri, 24 May 2024 08:30:31 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.28 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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: [PATCH v6 05/16] lib min_heap: Add min_heap_init() Date: Fri, 24 May 2024 23:29:47 +0800 Message-Id: <20240524152958.919343-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 92830f41642a..b384a4ea2afa 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); }; +/* Initialize a min-heap. */ +static __always_inline +void __min_heap_init(min_heap_char *heap, void *data, int size) +{ + heap->nr = 0; + heap->size = size; + if (data) + heap->data = data; + else + heap->data = 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, From patchwork Fri May 24 15:29:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673275 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 8897512E1D0 for ; Fri, 24 May 2024 15:30:37 +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=1716564638; cv=none; b=aY9YVR9GftTjo3Ar0zVZBE6NYJrqTBG34d4KZkT35N+UBCmCkTkLmNKrVF2SqAYKcCphTPt3XCjXHLXt1G5TOUqRDj9wU2mtfg5xHWlzMO6sno+m5OgO3cmK9rohBCDQ5bzdxzGL3qWDRaRwhQhqnEJUPRt1tZ8u06Bw2bUQkJU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564638; c=relaxed/simple; bh=CtmjnUhCovWSsS0eLtHZkP1gRg/+o2/rih6xjavgouM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=PqUd5ZYSCM7HX+FmvLkrtZxKM1Qu7d2Ih6ncvajH7lkjvEF+1gzVrAtVzviDpjTCaTZPLXxmu9+wKB1Id96BTL7ESiI9q/DkBQanVCoNnhY4RPl2vemtWxYpsz2iFo8qT22h9X7OS0fRHpCV+T7XhWsxTbWvQqtSg/AwGFvuAkw= 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=jPWNVd7p; 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="jPWNVd7p" Received: by mail-pj1-f50.google.com with SMTP id 98e67ed59e1d1-2bf5baa5b76so103285a91.0 for ; Fri, 24 May 2024 08:30:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564637; x=1717169437; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=cYJrwbsUSMlgZtHUd20UudtqnzPzA+Nu3Je7Gypyz6k=; b=jPWNVd7p/Pf6jqdXRhT+B5OuIbwVf6nhRLEgh1YF2jsnmVyj9QeZgIDpvmU3a0XQkU AlYU95zKUw8iOOy7hWhiB1Agvc3TTjEGyXpBf2OX35kN7LPQzOk63+s/BG7+q6Hl+F5H K2hJbL2+dP5k27IFYuTojGCbK7zaqoKIZHnbpNQwUsRRKr7G9aokZ8l8FNNjVvjZmjI9 ue75J1tjrRQpOhE8WaAfVi4SD6q+reZHzfugWqOjpJyajlNtwdvKc9nvEYYwu7R+zeF8 X5dpGxeLGNRjulOOGkoHYDGlm4dgwQ+zhdvUmBSuGw4RDBYC7IKeaWgMYa/49qQJVZqo obJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564637; x=1717169437; 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=cYJrwbsUSMlgZtHUd20UudtqnzPzA+Nu3Je7Gypyz6k=; b=bNtsPWUYQa6KvVHua/kebObhg0GkzdqlpNL8fOMZXhJ8h9xWgjxhVbo4uumy14hRV9 nqXqwc3NkgHfIRfsxdWnzYVWO+DGLKB9K8KpxltqWeP/A8wGWcNe5cgsSDi+SlqSsv7k D/HddCLAFVGPTx/80Xw4rzSkwpQVz/unbU2gLbizKvWyPUFrcU3f3WSzYDKra/hPerma X/R+6kSVZ790vM0uOc5LswzAxi5eRtOPY7NC3dNKTIgFsr2ajz7DselrFRtHdlvFzLlg qJ5gf4toaL5e72IdLiybG7Uln8IlvJg3FJl6QrqoWEmg9c5d5TSJpfr8siQQNJBW72u+ Rt1A== X-Forwarded-Encrypted: i=1; AJvYcCVNCm6/P1ZAv4kEDa86JaxRtHMpPfUpK6a9ztLpIc0VCq7sTtOVj/52ZA+RbYRw8FT36+SRIHlDmkENl5IWSvrhseJy7PKTfoI= X-Gm-Message-State: AOJu0YwH5RjbOWjajgBxU808WDKCUpzCVfW0EWA76Ms67IVwIeR/j8Fw i+hqejDL8TqnZyOp8HnB837yfw+bwmbPy4ZZ/Tt8UYCRxj5sDB2W X-Google-Smtp-Source: AGHT+IHoYwOCUaxc1eEkPVdFwpRkMAzYQsOk0wv11TzpiDNFWzl8TbRA7I/ssjXw7Wzjhb+pC2mgVw== X-Received: by 2002:a17:90b:2286:b0:2bd:e806:49e4 with SMTP id 98e67ed59e1d1-2bf5f511c5amr2497068a91.4.1716564636772; Fri, 24 May 2024 08:30:36 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.33 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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: [PATCH v6 06/16] lib min_heap: Add min_heap_peek() Date: Fri, 24 May 2024 23:29:48 +0800 Message-Id: <20240524152958.919343-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 b384a4ea2afa..d9c4ae7ad0cc 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, int size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init((min_heap_char *)_heap, _data, _size) +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct min_heap_char *heap) +{ + 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, From patchwork Fri May 24 15:29:49 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673276 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 17A0A130ACD for ; Fri, 24 May 2024 15:30:41 +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=1716564643; cv=none; b=btESUjBXtO1c/s12uQf4LSY6u1s7SlRc8O+qJNWLpYZBS4S41lCPaIHQcam2sR+WZdwE7kS7c0WrMuzNtWDOgT7StlS6xxkkTQCtCITDCyTIIea2qaG1H7NTmwbZ/WP0oUr/B6Jts3sokDDN2ZRccS9OWBLkxC/swwNpbuX2V3M= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564643; c=relaxed/simple; bh=KituFP5FWvyk4tf0TCLoKJP1Ug399E1uez9KXSPSXO0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=fsPzdOs8fGcqDSKHm6KZ76HeeBU2cQh9f1tRDPLVZmwfDVIu9yU70w51EanBI7UV3ssmNNe42xppATNFa9f1ORSj/oVOPI0LJ3KzFJuQsPIHgU60wZFYJi/f2n7krMbIhYJbLFoiGJAHcAjEck6yTwPSBFI56d5T2rHJQs+8Hxs= 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=mDwrx+C7; 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="mDwrx+C7" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-2bded7f6296so212162a91.1 for ; Fri, 24 May 2024 08:30:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564641; x=1717169441; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=L6wGqg1Bkc6VloO/r5wptzdiAzti723DW6TYEbY9ymY=; b=mDwrx+C7oOLhrRHMok1mf5wq+TFJP7JP5NhnNzrjFbPawN0i0tRmcDkDVrBHKTrq3c P6R+imlcdWzsb5u8S7jlfc5PMSKXHKDPJ0kgT8z5BfVv9BbvSvu8WZ7czdN4PrP8CQUZ 8lmTuyZwODSxn5Urs+ztkstzsbHtPu1Q/SHz00ojcncdeU+ZWk2vc5Yka/moBKFl4nY7 lJEFkd3auZOX4nNOfktsKdrLHE2sUbIwjBUzFKE7JVKNipu2/W0R4WsRSAH/BU5/K1bi 6wGyBcJHospw8iBp14AQQzmPV/phFRy5aYTfXsmdKH1UKpl8h27hwzpbr/zYLkXOZjpx gXtw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564641; x=1717169441; 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=L6wGqg1Bkc6VloO/r5wptzdiAzti723DW6TYEbY9ymY=; b=InUR6K+7Hvtk0tYPex+zL8tCvVUm1y/gltK+1b9XiiGZQEMiiTNmV1qWjlj6cbwYS+ MW842G0f23d3l8kIrTQ+kjZDIN0zJ2ABNZ1IhFQYFnReIukkcEBeYk7YGv5m+xes+mTO Y17Zpy+ANPxrS3jcqdSdnKNU7o26bWPx2A59E5ytAtM+gX8ZlsrDGElu9zA4KQP/FXSc m6FWRE34h92WJ6Yj8dUJVX4OprSB1bkg+WX7jrG/phqEoIcQg3hg3n1KqrgeNcVsL2lq h9+2cPcu/N31dIqzMBniVSXShnQODhHE2h0EHqOUE/NitdZIXPD1KjiTJZwN/m7D2iNz izPQ== X-Forwarded-Encrypted: i=1; AJvYcCXHL8nyiZqevrbGOWa9MHrekpS0iewoSIijx3jzZ1HeOFLOMoYxd3bARbC4NILalv58SyjisXKZUvVWO0lCvpxQ2lkcmjuWww8= X-Gm-Message-State: AOJu0YzimfDuA/rFhtXVn/d68cG8gy7HvbxSF3PSqFNf17LAoLCcrdVI iMjb8WRfIPTBzfzTtxezW0Ocm8r9Wasetg4jCvEFVSuJr0nU9of9 X-Google-Smtp-Source: AGHT+IEFZigwBsVU3DQ0U9XwesSc/pScEk6hYtsY4XibOuLDALe7YcoghUfWtHqjA5Lb2EftoZr+ZA== X-Received: by 2002:a17:90b:24c:b0:2b4:329e:eac5 with SMTP id 98e67ed59e1d1-2bf5f202ac5mr2505228a91.2.1716564641436; Fri, 24 May 2024 08:30:41 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30: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: [PATCH v6 07/16] lib min_heap: Add min_heap_full() Date: Fri, 24 May 2024 23:29:49 +0800 Message-Id: <20240524152958.919343-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 d9c4ae7ad0cc..f41898c05f5a 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)) +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(min_heap_char *heap) +{ + return heap->nr == 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, From patchwork Fri May 24 15:29:50 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673277 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 E7649130E34 for ; Fri, 24 May 2024 15:30:46 +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=1716564648; cv=none; b=WZV3vFZPm8E9n7R/XHQwlJCqD+eQhnsEU+HcxqQXhutH+h4lFIEAGqSktGgKe4DEt6VCH+MnW5aQVBzg2rOmLxrAGTlg2niltO+r8fGYKBBuuAC4jo8GITljKoKfMlnhvyS/QX4LZuZQzE79wgf8xb3t9wMTjvtqn/zWvSKPdbA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564648; c=relaxed/simple; bh=5JV2AA9diyVR/jhZ7mA96ORCdqkrw1iZVnaL99IKYaU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=eLec6fnijbNtTfn56+T0opyhghH2EzDIk+Kxczu5NY6eU0+74NWLyLDDsGVvDr+poGAswhLy/T0eG5ToCi29LU7ecAY60lvr07PCSvfPiIv4Q4bXZITjxSXNwC9WslQnSiMJGMUpU8J2/6KVizQprfVr/DQxg9DObqi6yQ7iH3E= 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=jPQ2PBC4; 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="jPQ2PBC4" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2bddbaae779so377095a91.2 for ; Fri, 24 May 2024 08:30:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564646; x=1717169446; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=RgdKTQ9TRzB3tK0yK840spkB6vBL+E81+KCmSeSmC9s=; b=jPQ2PBC4BSnMLIGuctLvS1QfJbWNwP1gJ1KR2npiAfIzqwru9y0aSx+BUIz4SDeJR3 m5K/uzVp3HePRglOZWkvDrUF963xzgzH0+iR2CCy37aszwCnGmknsiVJH/1SxrFkUs+0 Fdo+fcZm8YZPJCnbOolLYPxrzX5k1vxAz612Ho8iTI+nJOedxMJTponNe940puWYW0JJ HBbROV5Z+sqNa45B6yKVuyctLW0jbNLUhMvLg9bGkgsMJAcODVBeKLR/ki0GZ3ZRgvLS SWy2UCAEI73MHB1wiZLTM2rYiPMq4csItwUQspCc3/EDgN2IcD4fO23HHT/GhuJu+b2C UKQQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564646; x=1717169446; 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=RgdKTQ9TRzB3tK0yK840spkB6vBL+E81+KCmSeSmC9s=; b=asZoQ3u/ZToCx0Ngd0ueHIJD4mgtvP89iDhnHf6sPu25uaFagZ8ZtHJm+KG/s7rIT2 F2CKh2KJsEuFYuJgwiks9kP6v3Qaf5rtNEAm4KS/WR5b3Bpj2EzLXCHHsVM5w5c7jGGI aKvCmfx5f5a60Fvihu6YvneuEOw35MzBV4guMM3j1kpO2djE5RpIBkIH827mg13ziKhH LkhkT7Sk7vLTK/kMY8mGLAmgmKFb0EI0NR1Bf8NJCwDPBJcqKXM8b/X/7TKRJpKBR9bb easSItck4EGEx3y/vsW2aTL9Y6lUszA4iLcLxr9Il9hSE5aBQrDovT1chKXZCbW7xKTb jrhw== X-Forwarded-Encrypted: i=1; AJvYcCWPx0vy9Ut2m6MsGLI9NvW4qjhDv/R341tog5kL8VRCXCas87mvFzDblbkIONeSyAWrtnP+4IrgIPb76mC4bsl8rB0nWIkKj/Y= X-Gm-Message-State: AOJu0YyMXrvhLM57zwlm1N8IHzSRivE3qMEq6Ui+B1ef1ROd8gVko68a tpCobi28M6rN0c5f//yT8xcAVQ1zBHnwjoPmlUVy5RpbTZAngjTr X-Google-Smtp-Source: AGHT+IEGJ2+mzq88evUgGn5Sd4K8keindmtGW/gViVN8yChHqEhyKBZDlPxKuzfS8inrfZBzHsW2WQ== X-Received: by 2002:a17:90b:30d8:b0:2b2:4bff:67b7 with SMTP id 98e67ed59e1d1-2bf5f20893dmr2410233a91.3.1716564646105; Fri, 24 May 2024 08:30:46 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30:45 -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: [PATCH v6 08/16] lib min_heap: Add args for min_heap_callbacks Date: Fri, 24 May 2024 23:29:50 +0800 Message-Id: <20240524152958.919343-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 e8ad611fe7c1..eae990859db4 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 same 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, void __always_unused *args) { const struct numbered_block_mapping *mapping1 = (const struct numbered_block_mapping *) item1; @@ -156,7 +156,7 @@ static bool mapping_is_less_than(const void *item1, const void *item2) return 0; } -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 = item1; struct numbered_block_mapping *mapping2 = item2; @@ -182,8 +182,8 @@ static struct numbered_block_mapping *sort_next_heap_element(struct repair_compl * restore the heap invariant, and return a pointer to the popped element. */ last = &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; } @@ -1123,7 +1123,7 @@ static void recover_block_map(struct vdo_completion *completion) .nr = repair->block_map_entry_count, .size = repair->block_map_entry_count, }; - min_heapify_all(&repair->replay_heap, &repair_min_heap); + min_heapify_all(&repair->replay_heap, &repair_min_heap, NULL); 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 ef9a6e53109c..274f9ccd072f 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_allocator *allocator, * Thus, the ordering is reversed from the usual sense since min_heap returns 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 = item1; const struct slab_status *info2 = item2; @@ -3300,7 +3301,7 @@ static bool slab_status_is_less_than(const void *item1, const void *item2) return info1->slab_number < info2->slab_number; } -static void swap_slab_statuses(void *item1, void *item2) +static void swap_slab_statuses(void *item1, void *item2, void __always_unused *args) { struct slab_status *info1 = item1; struct slab_status *info2 = item2; @@ -3525,7 +3526,7 @@ static int __must_check vdo_prepare_slabs_for_allocation(struct block_allocator .nr = allocator->slab_count, .size = allocator->slab_count, }; - min_heapify_all(&heap, &slab_status_min_heap); + min_heapify_all(&heap, &slab_status_min_heap, NULL); while (heap.nr > 0) { bool high_priority; @@ -3533,7 +3534,7 @@ static int __must_check vdo_prepare_slabs_for_allocation(struct block_allocator struct slab_journal *journal; current_slab_status = slab_statuses[0]; - min_heap_pop(&heap, &slab_status_min_heap); + min_heap_pop(&heap, &slab_status_min_heap, NULL); slab = depot->slabs[current_slab_status.slab_number]; if ((depot->load_type == VDO_SLAB_DEPOT_REBUILD_LOAD) || diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f41898c05f5a..4acd0f4b3faf 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -34,8 +34,8 @@ typedef DEFINE_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); }; /* 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 = heap->data; @@ -89,7 +89,7 @@ void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, break; left = data + (i * 2 + 1) * elem_size; right = data + (i * 2 + 2) * elem_size; - i = func->less(left, right) ? i * 2 + 1 : i * 2 + 2; + i = func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; } /* 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 = i * 2 + 1; /* Backtrack to the correct location. */ - while (i != pos && func->less(root, data + i * elem_size)) + while (i != pos && func->less(root, data + i * elem_size, args)) i = (i - 1) / 2; /* Shift the element into its correct place. */ j = i; while (i != pos) { i = (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size); + func->swp(data + i * elem_size, data + j * elem_size, args); } } -#define min_heapify(_heap, _pos, _func) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func) +#define min_heapify(_heap, _pos, _func, _args) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { int i; for (i = heap->nr / 2 - 1; i >= 0; i--) - __min_heapify(heap, i, elem_size, func); + __min_heapify(heap, i, elem_size, func, args); } -#define min_heapify_all(_heap, _func) \ - __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, _args) /* 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 = heap->data; @@ -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); } -#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) /* * 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); } -#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) /* 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 = 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 = (pos - 1) / 2) { child = data + (pos * elem_size); parent = 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); } } -#define min_heap_push(_heap, _element, _func) \ - __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_heap), _func, _args) #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 47cb17adf858..c843af8fa6f0 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3686,7 +3686,7 @@ void __perf_event_task_sched_out(struct task_struct *task, perf_cgroup_switch(next); } -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 __always_unused *args) { const struct perf_event *le = *(const struct perf_event **)l; const struct perf_event *re = *(const struct perf_event **)r; @@ -3694,7 +3694,7 @@ static bool perf_less_group_idx(const void *l, const void *r) return le->group_index < re->group_index; } -static void swap_ptr(void *l, void *r) +static void swap_ptr(void *l, void *r, void __always_unused *args) { void **lp = l, **rp = r; @@ -3786,7 +3786,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } - min_heapify_all(&event_heap, &perf_min_heap); + min_heapify_all(&event_heap, &perf_min_heap, NULL); while (event_heap.nr) { ret = func(*evt, data); @@ -3795,9 +3795,9 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, *evt = 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); } return 0; diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 52efab9fb2f1..f59638cf5dfa 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -13,17 +13,17 @@ DEFINE_MIN_HEAP(int, min_heap_test); -static __init bool less_than(const void *lhs, const void *rhs) +static __init bool less_than(const void *lhs, const void *rhs, void __always_unused *args) { return *(int *)lhs < *(int *)rhs; } -static __init bool greater_than(const void *lhs, const void *rhs) +static __init bool greater_than(const void *lhs, const void *rhs, void __always_unused *args) { return *(int *)lhs > *(int *)rhs; } -static __init void swap_ints(void *lhs, void *rhs) +static __init void swap_ints(void *lhs, void *rhs, void __always_unused *args) { int temp = *(int *)lhs; @@ -40,7 +40,7 @@ static __init int pop_verify_heap(bool min_heap, int last; last = 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 = 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; /* Test with known set of values. */ - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); @@ -86,7 +86,7 @@ static __init int test_heapify_all(bool min_heap) for (i = 0; i < heap.nr; i++) values[i] = get_random_u32(); - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err += pop_verify_heap(min_heap, &heap, &funcs); return err; @@ -110,14 +110,14 @@ static __init int test_heap_push(bool min_heap) /* Test with known set of values copied from data. */ for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &data[i], &funcs); + min_heap_push(&heap, &data[i], &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); /* Test with randomly generated values. */ while (heap.nr < heap.size) { temp = get_random_u32(); - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); } err += pop_verify_heap(min_heap, &heap, &funcs); @@ -143,22 +143,22 @@ static __init int test_heap_pop_push(bool min_heap) /* Fill values with data to pop and replace. */ temp = min_heap ? 0x80000000 : 0x7FFFFFFF; for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); /* Test with known set of values copied from data. */ for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_pop_push(&heap, &data[i], &funcs); + min_heap_pop_push(&heap, &data[i], &funcs, NULL); err = pop_verify_heap(min_heap, &heap, &funcs); heap.nr = 0; for (i = 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); /* Test with randomly generated values. */ for (i = 0; i < ARRAY_SIZE(data); i++) { temp = get_random_u32(); - min_heap_pop_push(&heap, &temp, &funcs); + min_heap_pop_push(&heap, &temp, &funcs, NULL); } err += pop_verify_heap(min_heap, &heap, &funcs); From patchwork Fri May 24 15:29:51 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673278 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 6F0A9131192 for ; Fri, 24 May 2024 15:30:51 +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=1716564652; cv=none; b=gxQj8J6F1WnMv8ANyhKRuoqfNOUKa9D+h0cUDoE3YBUbbYK7ks4iAFb1d0Tvg6GIrlA7teTjdbs0WeayqU70F3FaJ+kjwlCH6yO+aSi1oj54ybUwFaHzskczVnyC7x7t7K0cr+OVDLzOOqft9Y77TkL0ncHcZUPUwUGbYRMai58= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564652; c=relaxed/simple; bh=tby2ZpUX+BlnLTwxvgk6fPnVU4TaOjJxMlCJa4gIREI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=eHjC8JWhFHakWcIB9uBNzsLAbMo0zDYCGVV7pZM5VxOhOzFOQw46TvsgnoQ44yGRZq3d+6L5JacbR4JFNs8B+6WvPUBJyCwNPc/aqeQhM5nMRrQwNHdmKlmRdQ93uWtGGWsyQARXO1CDHdm5AM+mmravOaJwKpjOqeGvz21ciXI= 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=A/MiqY5a; 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="A/MiqY5a" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2bf5baa5b76so103334a91.0 for ; Fri, 24 May 2024 08:30:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564651; x=1717169451; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Uvl2xRBhY8ekhTJXesACHkl46vqc2VrA3GO40P8QBlE=; b=A/MiqY5a8fJKeh8iTjPf92FtcvQxLX6Ank93mCIwOvH7wwFJHorhTMXWieyU7lPX8g SoZ2cUgPHIOglSZ41mhs8dfn065SYJMXiqVscFz8ubjqd8+oWHsS3S6SqMvxNLBvLMIK HbyRSRJjEPYvkOT+9shq7gIIUrO5Uva4QcxNS+1r5c1mKS3w+zaJMlwh5OIyaGFtopOU YG+/HhWnCE8lMqUrGlVOcMSDSnQAtaHFsJIAs9sSzxkfhp0dp2Af7xn7x0dQofaVV89G q1bJz1ZGtuQLSS620IeIueN200FywszFMlCWKuLhcHQbxrivb36fZ/Vf83GMf0whUQ67 zpPg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564651; x=1717169451; 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=Uvl2xRBhY8ekhTJXesACHkl46vqc2VrA3GO40P8QBlE=; b=clwV1s/dNh503rm/sM8MA9Gah3D7fiqhbBNUpVG/LTi97Q1/g/gonlWQxSD2KUmBmN xUIhMCnAAh3v1kZRS2YLGcRFZAeGtbbrPznUuRV2eywh06ZrGanrOJHgzzXt6L/Gl7Rr sZ8t7uWOVwxXJAsagfelFvja17zzs4Gw7WHqiYQgdzy2VFiZ/PQkZ10VLWXZWwLinrxN mOfWdvvmcu0TETtdeja3NNzg2/Em9b0LL3zaPk0bvQtIXQtVW2sEjSKbbgKOIIarmKH4 8jHhbxlIPiWeYIykYnhC6+Vv7kvLfq9ubeLg17RyEKB01S09yMtrvQx5KTMusAd5XGRd /wvA== X-Forwarded-Encrypted: i=1; AJvYcCWdIee1SPyNCuT+nUk1v2NCoBvJ8XFSU/mOQ1j8rsbvByS/LPYP0EiBghSaxItac3E5RIR8wlrXs3irAg38OaTij1Y+D5AFmqs= X-Gm-Message-State: AOJu0Yw3VQxVfU0wlVRZRhGStnBPNlu8dJlTmwp/0ANg8En6NEOYPvAY ccwJC3o+XBkkBPYBMTJjti/YGp/8v8g0CY6tvShqK+9/yNP2u7tc X-Google-Smtp-Source: AGHT+IFsxgebjZlr1dxx1chJSleAIrK43REkyeW81P4lfYkP9NwmgKQYjYTGz/eljOWV8fOLiCwwGQ== X-Received: by 2002:a17:90b:24c:b0:2b4:329e:eac5 with SMTP id 98e67ed59e1d1-2bf5f202ac5mr2505679a91.2.1716564650793; Fri, 24 May 2024 08:30:50 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.47 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30:50 -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: [PATCH v6 09/16] lib min_heap: Add min_heap_sift_up() Date: Fri, 24 May 2024 23:29:51 +0800 Message-Id: <20240524152958.919343-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 4acd0f4b3faf..ddd0186afb77 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), _func, _args) +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data = heap->data; + size_t parent; + + while (idx) { + parent = (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 = parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, From patchwork Fri May 24 15:29:52 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673279 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 3567F131195 for ; Fri, 24 May 2024 15:30:56 +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=1716564657; cv=none; b=D4Te7TDacYBgT3zVWYXEEbnu+1exxe15ZZ+X7KjO86BTM2bWCQafYNAUuU654GBiwkyqOj6KHooAkIpFfChPq1GZ0UR01mBTB6g0XD9pcFV+nd7k4qqwuGgHTtL7Gm5oYCeuLLgxp9tEBMKRorbDYPrq0CjlE9y+M4qvx+xFmx4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564657; c=relaxed/simple; bh=sJJvbSyrqr9RfqPlGBQxs9diGbsYUKhy8zMD1EMctXM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=X0swQvJQ+FSnHbaCXS1MpNKVF5MoXPB6u13fpHE+eHkpnUnhNF9/jlYYdyotx7NfcyBL7Y+UBro0O+1QMHOYd4RyIOv36aRtBj3uACMPnN1FscAb0d6ds7GEbnkz3Z5toczLsDKv69csWanCiY+D/UtMixoyn+WloYNsFq3+cqA= 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=mx9guNG8; 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="mx9guNG8" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2bf5baa5b76so103354a91.0 for ; Fri, 24 May 2024 08:30:56 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564655; x=1717169455; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=5lfmbsG5rvd+B8+9dE2AYffkU5kvksfUycCfh2ZKaE4=; b=mx9guNG8WlNz/2YUraB2IZEKAiyiTtPa9SAluKzIi77UZwu0A+Dms4/KImLOt9Kf64 LLi9kF0Ugf0wvBQjXVGvzj9VDw48Vp4feoDiZ5hNzttCBL3N/3pZP5HSSYEy7o3eK1Bw x5uKqhT/W/OF+k+2KXXOR2myBtNu24RgRLFk7Fx4+3uLj0ViKHn9fwid9tT7O7B7Z/Nc mUQjNAK1Z7BOxT4KV6vajnLtTBhEQfZACT2c25hr2qEHIvAjC5cGp4onLAXarnOFziOM DIcbL/I34yNACBwom82hcUAdxASarP3d7gFKjrgc39bielq9Q8YKYrcuLwWwiNYm86C+ XKhA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564655; x=1717169455; 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=5lfmbsG5rvd+B8+9dE2AYffkU5kvksfUycCfh2ZKaE4=; b=kz8GgQD1BGkRgfU9QBIXLAHkDhf9VsNuvQvMhwLj7lkhA9YMDf+uHcu+ry8dX95izp UbmaB+frQzlUJkCGTAF+cFnsYGxd89JlS3eEok1rLk9toBqm6C3wByIo3bp5A7CEXARv Vt54U8bYceoJ2LG8xY1u3Xfncd9/3SDBcBw3aB7+kYZfeSd5pM6/7DFwZXqpt5StC8fT JNHAhwMu/oJpuD2rJw6S8MHbqWb39bfUQFPmRXCxihGgkPIxAjXjuCYsKFfcnNEkdXBH pC5SHMbuK8wEIhi6YZyJaVwAg3cLeYiGipt1bZt8GvSd8L4VH4BitLzK5xnLhRV2nVhm cJnA== X-Forwarded-Encrypted: i=1; AJvYcCV+2QY6lHOwSSaL4FJ1DhT7dlamUJ1QwOiJpZrDUYfvgJpvIkz0w2u+bdm3aXwU7Pcu4iuS0VxhRVlOlgfYROnAUoCNwfPE3Qo= X-Gm-Message-State: AOJu0YxfluA0uqIAtNpkfp/B5WM0Q+U36DH4qDQP+k3W3eOVmv4YCfDh R9WgDSN5xfe98M3FMcZCB5fFMLRbLEnn2YBAV1TbBLpqQMp+c7+W X-Google-Smtp-Source: AGHT+IGLW9yYebnTwkf31N4DQ42MfzPeT3rNQKrGi7/d2boEiBvS/PxpOdbDpM6nd0O3UUnbvMIB5A== X-Received: by 2002:a17:90b:24c:b0:2b4:329e:eac5 with SMTP id 98e67ed59e1d1-2bf5f202ac5mr2505960a91.2.1716564655542; Fri, 24 May 2024 08:30:55 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.51 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30:55 -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: [PATCH v6 10/16] lib min_heap: Add min_heap_del() Date: Fri, 24 May 2024 23:29:52 +0800 Message-Id: <20240524152958.919343-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 ddd0186afb77..98e838195e7e 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(_heap), _func, _args) +/* Remove ith element from the heap, O(log2(nr)). */ +static __always_inline +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data = heap->data; + + if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) + return false; + + /* Place last element at the root (position 0) and then sift down. */ + heap->nr--; + if (idx == heap->nr) + return true; + func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); + __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 */ From patchwork Fri May 24 15:29:53 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673280 Received: from mail-pg1-f172.google.com (mail-pg1-f172.google.com [209.85.215.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 521D4131752 for ; Fri, 24 May 2024 15:31:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564663; cv=none; b=i3ay/sWps2hpytrGg7vbrO2tHi4yiIsGed9OUdq2E+0BX2GeOV2vehD4Rdj3agxovbV/KTLIryK5YdxLs1Bndwyq+vLE812bzTFrF15xihfAunD75AN70EBoKOFiMUIdtHhUUG8Zynb4h/awtE8T7JItRT3Cur44nudIQ05VTkQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564663; c=relaxed/simple; bh=FajLBoy+P54V5d595ptYE3zStWRI7+JF3jA/AgpkBC8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=jjcMYoekgvWsJx8XlaLp5Ichq2b90jKImfq6BDzWaDXkvee5afG1n/EoHmG1FlvvFkWOpRnG+VFecrbLwY6LQ7752w5Ra8xWy4FcqSTiqdErHQ23eIPGs2qSisUXS8Mn73koXlujJO+TNeux12QAW9uuBn/9CQGjKGjwUAWKSDc= 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=AQfhmZ43; arc=none smtp.client-ip=209.85.215.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="AQfhmZ43" Received: by mail-pg1-f172.google.com with SMTP id 41be03b00d2f7-64ecc2f111dso453237a12.2 for ; Fri, 24 May 2024 08:31:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564660; x=1717169460; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=fHh8oRo5IgsV+IU2cDnhd1mUOloCdZwamTIL5z7K9Kg=; b=AQfhmZ432p0MEv27C7P6RsMQY/Iyjw/utAA1A6k4cXadv+ns0guD9TwIwrVyY0UFFl o9CtA4IRfPb7RpzzIXIV1X/Av93KwfQlO47fFoJX6lRDuy7BXbjWHzEzOjWYmmgU3gLL F44IAVRQ/QUGMEagoM0EcfyUmgaGgnBcPi8ptmCDRTRvy6O3K5Yh8RiMxCfssWQ57kwa 3+07/W+wEA4q3YySm6T87ym8ACAogDfKjh559m/OklwOC9oeHJddgF3ZSSEUP07OvluW djLf/ByEg1oN3YbScZ57keVjoLkl1AhzhQPgE4/tCIaxvFObcNGy4vX3PgE8u7poYzxo sZrA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564660; x=1717169460; 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=fHh8oRo5IgsV+IU2cDnhd1mUOloCdZwamTIL5z7K9Kg=; b=v5iGqgT1xfvXzPo/3RbXEhijiyXFC6QrktRrKZOfWFKTr/5Yxq/hDdySqyySDhX7MP 6BX0rHUSI/pg/+uI8dqqs+Wbzu+hY81LT0D+hU7bhEop4XBl64iJ3KMC2neK0HjkeeT4 8+PtEszg9AQJHo4Vs/0eqE6ba7f6S0e/kEWmprw7felSQXQoIRbeJQ2yqFLT6jEbXAly gh0itNohPrTnRsZADSUYJp3B+vIR13ROrb9XaFaF8Y/AjM6k70MVWzo/3vxiuj/SFRJG DXJ0CwAznd+v+imVbqx8fciGDIqZwZEk5hKLuWyjFvhgIpD0NGzhmY27eEDeFSyjlEtS +Nmg== X-Forwarded-Encrypted: i=1; AJvYcCUeLSnBOSigXGY8TC93SffYg8V1Qk/wf80magpBr15eKbz+S6UX4v0f1EUEjlu/p3QGyk4CPE+ccWO7ShNhNP4CCHBdvKV5kls= X-Gm-Message-State: AOJu0YwmWigEr68MVsrwc1xToE0BSlS6oxfJQb/8d8nEAHt57MS2Cy4Y fuRTx0AK+cNn89CKL/s3TQt4JNl5HPkRkYPNb8MU14ssF6x5Ubi+ X-Google-Smtp-Source: AGHT+IFciQWF2Y7yTOkGCbHq/4hq/tcnGDrn20ayUbkM9iebbc5ly95hjv5xZNwCquKeXBM/4haULQ== X-Received: by 2002:a17:90b:230e:b0:2bd:76ee:48c2 with SMTP id 98e67ed59e1d1-2bf5e0a7a56mr2495670a91.0.1716564660327; Fri, 24 May 2024 08:31:00 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.30.56 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:30:59 -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: [PATCH v6 11/16] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Date: Fri, 24 May 2024 23:29:53 +0800 Message-Id: <20240524152958.919343-12-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 98e838195e7e..3410a5f907ad 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 elem_size, /* 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 = heap->data; if (WARN_ONCE(heap->nr <= 0, "Popping an empty heap")) - return; + return false; /* 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; } #define min_heap_pop(_heap, _func, _args) \ @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, /* 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 = heap->data; @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, int pos; if (WARN_ONCE(heap->nr >= heap->size, "Pushing on a full heap")) - return; + return false; /* Place at the end of data. */ pos = heap->nr; @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *element, size_t elem_size, break; func->swp(parent, child, args); } + + return true; } #define min_heap_push(_heap, _element, _func, _args) \ From patchwork Fri May 24 15:29:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673281 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 CB13C131BDB for ; Fri, 24 May 2024 15:31:05 +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=1716564667; cv=none; b=ij2nOLEBIghiHwwHKFNFEFvzb1unLMebZghfWiFpEOgBzG2576QpgqmEiWb22oOW1NkvYjxfdtT8EA16Y6s5v7CRiuC8EcJaMrcNR+jRkg9XlLFaw94YsrjI6cUOHTW7BeFIPIjJJKH/UIs3heb1UCx53ER6ONVJsSryhlqSIj8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564667; c=relaxed/simple; bh=XBbTFxTKTTd12S0apVryE3PcI4APeLL8xosQ1q7yRmI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=DzS+aX8Y5heC+xRXn2kn847Kngbz8K4OZdp5CuxiCrDbJmpDtH/W2lwHMwHmrvdkBtAWovfyAGBaVbfTtkzddFVQQ8/gVt1KcPox029qkHtEWMrNh91DYt3V4afr+zQ2hMfQL0GWXcbd7QklB8KCZHjyQ1D49Pi3M3EYsnLbgGs= 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=JNFhGm+V; 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="JNFhGm+V" Received: by mail-pj1-f44.google.com with SMTP id 98e67ed59e1d1-2bdf439c664so314843a91.3 for ; Fri, 24 May 2024 08:31:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564665; x=1717169465; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=eJxc7A3KFbtC/I5z6jADokbslyusd4Od8ho0PKKKHBc=; b=JNFhGm+VdvrxL3KSSHiaph4EnxLGJhOntIvekahr75gzPmhffetuiETUSuLsS/BwIn is4mJUBydK+9GmGZ+v+R2ctveTazyKKC/lwVFPFOTXuvUwojlGFuP4AecOtr9WOLNZqr A3HjngsFOxX+QIGafiSZTWSZr6TsX1bu3IHUFUz8T2Gy5rf7dYatOPz+Fwc0Gxf9oWsl FD7UtuvRqcJ4kK1kb/CCZWu1/0NVovnBGLv6t5XWk4qI5fcuyXxYVdUL5sB7TBdxE7f/ 3xNhOOn+lTvo6C57SxEXC5OL2ekbWdkYByiSALCDtEv5BxrMmGkB9j2favqODqhYvK8A KMXg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564665; x=1717169465; 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=eJxc7A3KFbtC/I5z6jADokbslyusd4Od8ho0PKKKHBc=; b=noCQ2XigeqXyKtuuW8LEdTyrhDTN9pf0COWgDu9fAK32knMrAcrnkZB3gOG+OecYzR UscMkLD0Nhxy9Yh4WE5isfSdr4AFyzRf49lgni3gF1i/TuNEXUY86R1VPmW4j9dWrNCv DUedctl6P6ji7ueqtNjx0S9wZSgRAQgDEYdJiutWekbpgqz/oFDBHvYKikR9LzLheBe0 tOsjwJQaJL/ED30c9+nMGN5ntruNOXrbYIZbrAuROPGLBwwXW76B79ShDdcYzHOPKDwm WWMkbhRQPyNTXdlujnKAJa2mXT3ZZO5eigxeAhhrGcxPkCu+V2TWT+VD/axtSOLZ5F0V imkA== X-Forwarded-Encrypted: i=1; AJvYcCVFulPMbUq3UL6tn+GHs7i1dgMC4y0vNEjuSSO8PbM+Pe7KZsfyi+cfpwL0fNf1u8yRjhKJRCHosgzn2Eabcl1ORAQ0UMQFx7k= X-Gm-Message-State: AOJu0YwTV9xRWVJl8scubnKL26JzcoDqMsicEFPw6M1fT+4aWwHFVXj6 swUUxBDqsAvxjm+P+rXniVYI9Gs3rC5qQSjfw0uzj7Ki48HxU6uI X-Google-Smtp-Source: AGHT+IEuU6jpX9orINJlPXkOYySiaFGvoUViUJAIEwsd0ETqDsNgaoXn1NDqH0zGyIfxWZx4lsu+oQ== X-Received: by 2002:a17:90b:4fc8:b0:2af:6b92:ff6a with SMTP id 98e67ed59e1d1-2bf5f30e8a2mr2443714a91.3.1716564665094; Fri, 24 May 2024 08:31:05 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.31.01 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:31:04 -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: [PATCH v6 12/16] lib min_heap: Rename min_heapify() to min_heap_sift_down() Date: Fri, 24 May 2024 23:29:54 +0800 Message-Id: <20240524152958.919343-13-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 After 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=fVcBAxt8Mw72=NCJPRJfjDaJcqk4rjbadgouAEAHz_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 eae990859db4..ff09e4a14333 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_element(struct repair_compl */ last = &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; } diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 3410a5f907ad..0baee5787247 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) /* 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, } } -#define min_heapify(_heap, _pos, _func, _args) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _func, _args) /* 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; for (i = heap->nr / 2 - 1; i >= 0; i--) - __min_heapify(heap, i, elem_size, func, args); + __min_heap_sift_down(heap, i, elem_size, func, args); } #define min_heapify_all(_heap, _func, _args) \ @@ -158,7 +158,7 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); 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); } #define min_heap_pop_push(_heap, _element, _func, _args) \ @@ -232,7 +232,7 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_size, 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); return true; } diff --git a/kernel/events/core.c b/kernel/events/core.c index c843af8fa6f0..fad272aaeb65 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3795,7 +3795,7 @@ static noinline int visit_groups_merge(struct perf_event_context *ctx, *evt = 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); } From patchwork Fri May 24 15:29:55 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673282 Received: from mail-pj1-f54.google.com (mail-pj1-f54.google.com [209.85.216.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A896F132484 for ; Fri, 24 May 2024 15:31:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564672; cv=none; b=Dfhmri8R93YzFI09SLPzFplv3J79iF+fs+cMZQeamX83sFHaJ0hob1Wkjn5Hm6rgAU9mlhd6RhgDpZHhuxKENBQ+EPcXpugyDA3EJ1FoD/RkhSfPsBsEueuRzXwUBXvtVNWTHzo/1h2MTKOYDA2GmkwUiZrm8kfsTXw1OHjz8Sw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564672; c=relaxed/simple; bh=77HUtebVrJzxuUnhxHqdoyCrlqlYVs7r4OSNokoaFRU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=BrrPsPUWeaYKNsyn05vBXt2yrJGMyM3hD0Sw2zzp+JoNjmDT38TK64Xrh2U5c6WReQ/Mo4za09MC1vSbHWRqgR/7SB/k6wVfrVKipj3HRH1tSuHq8AozSVJ0WLh5iMLpKt575TGz5HcLIEexzhhA4vCMp8CxS/6iX7umcv0QDaY= 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=L87ma+aR; arc=none smtp.client-ip=209.85.216.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="L87ma+aR" Received: by mail-pj1-f54.google.com with SMTP id 98e67ed59e1d1-2bf196037a7so247050a91.1 for ; Fri, 24 May 2024 08:31:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564670; x=1717169470; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=JeiLg0XMliHOkIglYnFk3DvCIMxfANwaibZSEhPQVEc=; b=L87ma+aRxElyfg1oaDJmOKiAh4a+WigJ0uYjac+r5NqaBHXKSstTtO30ZYfxYWtgod L/NpwEby4MrqgTAjR6OTM/AKwWT+NufS0UJIgr8lGkZSHsh5hdfxdGEzoER3l/1iUT8y ubHrKW+SbaiX1F5ycCXY6OZ/tg/wLX/iHDHeqcrai9Owk802pqVaaqn05QdQ4WX110lu AG1PXao7pELSxfbZG501UMAczTpWFpED9aSMiRXq2lefgA+HZ7b+IpL2UI88qnCrfYvi /+dbWwXcokaJviVm7fUbip6PE5hywPNtga+x22RGcwmIjAJAuqzHVeFQ3lFXUoyzqIdp ixAQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564670; x=1717169470; 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=JeiLg0XMliHOkIglYnFk3DvCIMxfANwaibZSEhPQVEc=; b=GSt7oEflf4MR/X86cZHwam9kYo8oH/Ewy2hjRObinloXngJGXTCgbr72H9iQtJsMqK 91TQxfD8EPUKuW6icHq9y2BkKJ4/iWYECXM5P2Y2gEyubtijiM4f3AReiVVmCT60RlF9 sY+atjUdS1cLV1iGbBsDs5DouGnS6ekel0znXIulMq2J5ZGYsY0+3CtBFFSY9FLOy/jt ZUmvMsA2KQe3O9o174KQs7iE+rUR0/XtQVbt73f3B2kXtDhaKIDMqlyxBwnYdDa2k3+1 gT4il/TvoQ1mMcOV1vxpfspt1tNZCclzRUQoJpSeTbNbFv2ZcdSf+AQHMm48OSYLJEza Qruw== X-Forwarded-Encrypted: i=1; AJvYcCWjC75P6MUoXRvRPFc2MhxvCB50Qjuy8xEOKXepVmwkPZjTjFrGgY2yX/g/BfzvwdArSaiHasA0FY7lyzrgpj8a11DcxbgVjgk= X-Gm-Message-State: AOJu0YwguUX/daWBYcld5ZfSlt9GVRe3UtHpHUUxwx3a/31FqjFsfbb6 JqgVCPAjWnB3bEIqMIx8Zy47YBV7vQHgVxWpWMrgyWPo0C045ZXn X-Google-Smtp-Source: AGHT+IHbcXWiDmwxfe4l1q+/LLknHHuRnxu4d+1rEJ1rLFTk0UBMcC74U6va1+XSc6Jx655Pg8nFDA== X-Received: by 2002:a17:90b:8b:b0:2bf:7c50:1f6c with SMTP id 98e67ed59e1d1-2bf7c502036mr785217a91.2.1716564670052; Fri, 24 May 2024 08:31:10 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.31.06 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:31:09 -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: [PATCH v6 13/16] lib min_heap: Update min_heap_push() to use min_heap_sift_up() Date: Fri, 24 May 2024 23:29:55 +0800 Message-Id: <20240524152958.919343-14-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 0baee5787247..43a7b9dcf15e 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 *element, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data = heap->data; - void *child, *parent; int pos; if (WARN_ONCE(heap->nr >= 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++; /* Sift child at pos up. */ - for (; pos > 0; pos = (pos - 1) / 2) { - child = data + (pos * elem_size); - parent = 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); return true; } From patchwork Fri May 24 15:29:56 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673283 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 C424312F36F for ; Fri, 24 May 2024 15:31:15 +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=1716564677; cv=none; b=CjVqj+3IkOFM1UXKoMcIC2CqMrWSyfTRqZxiP/KnE8hB2of1UxaQ8E2T+dlJb4vvDH8wwYLwom+UJ3TKN1Ptqznt/7Ff94f2t15OrIqYs65JmVQ6kaae/t+aciolTQTZPLiyPAGHqyLWwNzAbBYhw1xh7o28eVM1xyRpChzfkmk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564677; c=relaxed/simple; bh=C6lI1Yu2VUekRoVzlYxR8HKgrkH4BaCTdukv7Ke6t5U=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=DsgletLguZlSC/0RJH8gRAOWB6f87RM+2LTxnpVuzT65LVsF8laHn6p9vSv83Lt0IS1HM3Dl91wZjVJ6rQt9qac2XZLK/5MItMAtrMVDYAfopTM7Gysncsdhhmxo6vyBPZClDUOLxvW6w/t9BirYbqG8yPgsVWbHjKVrAcUHqTY= 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=BJNd8RZF; 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="BJNd8RZF" Received: by mail-pj1-f45.google.com with SMTP id 98e67ed59e1d1-2bde4d15867so247323a91.3 for ; Fri, 24 May 2024 08:31:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564675; x=1717169475; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=4zTq8cqNIQvJ49hOaLr5qxuS4444ShA09a0gTe29cD8=; b=BJNd8RZFnPkpe5qCAR8L7mUFEeCBUsqC/qqPHhsIA27nLdy6Trb7V9HxwPZ1Nd3r/E wCaSGmn/w7p8MowwgqLFUFpB64Hi8xtCZcMtIHjfl9EqShWmuTCdI1ENOn1GC8FCMe0q h7zaxfg+PlDwlzvop5NGUwNHd4I+n41e5SBJxFI6KiXHBn3UfRlClWSqBpCagofTEImn batuDf5rSKekzn5pKuEdLZqUR2X7Tk0VjA4gkyTwsqpI315LxYGcc5zHpgxndq1xSRqv hE0FTZyFYeCmvtnGZbx3QI/10U696TuzrYelDWkqMyO+gf8+qgY8t5u8YGy7l3MVfCK6 pnnQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564675; x=1717169475; 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=4zTq8cqNIQvJ49hOaLr5qxuS4444ShA09a0gTe29cD8=; b=UP5A4bAYncWxpyI8DAnQvjVWVW3UIm+Tu9mO07b52tU3vEFteh1nUoeiR2kQh16ukR NbLoJQsEr+s3swOYsIBqxEH/G0q1wooxEFIQBCkTfYQu3PMXyThoBQceCWybrHSJdRa8 ZMtVGCwGGG3T0kLmMpcmJOFAPyVgpAkLVnJVGJjkSZVgc8nJVh5O01i21dkSuuIuRnb+ 3SLxq6Iae2HZBKcwqQT1nmI3ZCwVVUg3ErWAS99sOGpP35refOt7yJoYEzi75lVdUjUj 0w3Pk4Cz9xjc/KIAPmb5G1yYm8Zwhat4XD6RgFWNxKlHy/lO/Xz/J5VLCKbK/NvgZT1M Zz5Q== X-Forwarded-Encrypted: i=1; AJvYcCXVW7ApV7GTyO1P2iGrijl+D8GsHDFuTJj0zD/hDSNQwpKsJ3d2p4VPzgBlAa2QUT+ecRmYHkQKdI9buPw7+WgNJ1LikDD2a84= X-Gm-Message-State: AOJu0Yz8msYyBgzZsPf+o1APk9sYnCChiWUunfCOUE7kt+Cli/vJ7W3g 4Cmavib/aQGXmUbFjqdGgCuQWPyN4lUZAuYYC/CJ4QM82aFVzT3z X-Google-Smtp-Source: AGHT+IEeQ+fm8GB2+MgEGzsYh4oQsjju6O48NEnmfaOO2wHIeT/FbppTUO/N8jps5HE+L8khfiX4jw== X-Received: by 2002:a17:90b:3d10:b0:2bd:feb6:b09b with SMTP id 98e67ed59e1d1-2bf5e161326mr2523612a91.1.1716564675125; Fri, 24 May 2024 08:31:15 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.31.11 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:31:14 -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: [PATCH v6 14/16] lib/test_min_heap: Add test for heap_del() Date: Fri, 24 May 2024 23:29:56 +0800 Message-Id: <20240524152958.919343-15-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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 f59638cf5dfa..9e1feb9b679c 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; } +static __init int test_heap_del(bool min_heap) +{ + int values[] = { 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 = ARRAY_SIZE(values); + struct min_heap_callbacks funcs = { + .less = min_heap ? less_than : greater_than, + .swp = swap_ints, + }; + int i, err; + + /* Test with known set of values. */ + min_heapify_all(&heap, &funcs, NULL); + for (i = 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err = pop_verify_heap(min_heap, &heap, &funcs); + + + /* Test with randomly generated values. */ + heap.nr = ARRAY_SIZE(values); + for (i = 0; i < heap.nr; i++) + values[i] = get_random_u32(); + min_heapify_all(&heap, &funcs, NULL); + + for (i = 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err += pop_verify_heap(min_heap, &heap, &funcs); + + return err; +} + static int __init test_min_heap_init(void) { int err = 0; @@ -175,6 +209,8 @@ static int __init test_min_heap_init(void) err += test_heap_push(false); err += test_heap_pop_push(true); err += test_heap_pop_push(false); + err += test_heap_del(true); + err += test_heap_del(false); if (err) { pr_err("test failed with %d errors\n", err); return -EINVAL; From patchwork Fri May 24 15:29:57 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673284 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 0F9F512F381 for ; Fri, 24 May 2024 15:31:20 +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=1716564684; cv=none; b=E+pHcbRJ11hOYTS2mBLYJt4XJm+UzC2fPwqFVg8pX+2eZRF6zzSmu9bfI4GdKlPC5CDtzifed6l7ytGC1XAMPl1+vJHL1HnB7JvGalMFkaZxPCykshRbHfgGUwXesI3+1mHg5gIMSqCJo4F7C0MLsbteIW0sXD4GLeYoPyo5FL4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564684; c=relaxed/simple; bh=8ni4GszjCg1d16gUtlXYLKOso948yR1YzfvIQYs3v1Y=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Y/m4DWr0s1QAl6OcmGKv7RUg0Vkd9AAEzXNK/WDIN8Fj0fa8F1CIFzXNjY3okV6S+LrNVIATHrjWEIuO1D8I/RnwXNCe+IsGATa42cfZCqSRIvR+PdwtculuONcicOCVwBTQVGFgHkj6PfrNex3EP4NQGpxSw/AhkYPISE7nLLE= 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=XbB1PQIt; 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="XbB1PQIt" Received: by mail-pj1-f52.google.com with SMTP id 98e67ed59e1d1-2bdd6b73a3aso384007a91.3 for ; Fri, 24 May 2024 08:31:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564680; x=1717169480; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=loEl3bDm1i3rglr+E7pMHIQM/WYUDmzuHJmkhLtvK58=; b=XbB1PQIthPHcgf525cs2BOAzM1PYoozmuJK7VvFbWg3aMP06x+7JUY8jW2aRzN4BNs JzsgCu4tb4YlujGTzc9SBjJc7Vza25RpdSK94otOJd7+rMc3rfL9rKfMD+mHhprBbAYl ZAH5NgQ44zTRJgrC37MFAAOLOKcufLd9Cly6CFPhqA5BKHZCEARkL2Pf5RzjLdrk/rEU 1ulqbPyNReL7KAw1x56atemWmRYbymF2nnnAlATO6lqA/MMAxFwFWDmzXQ5HuWBoxs8Q HrWIt4EZI7qiQt2XYZOVtlt0xSStdp+2tK9EGQOGskjQblnJrFoOwPXPG+Mz70ofLpOG 3yPQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564680; x=1717169480; 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=loEl3bDm1i3rglr+E7pMHIQM/WYUDmzuHJmkhLtvK58=; b=wCQLqDmPzT9x6iNYcSDH1mxfOTCl3NBzTKicKj4e0ydIWiqpuoRoOO9IeX0inFSR4P JOx5GoToyuJxPCwk/84LrXg016JSmVzgAWqu1tEtCwR7HkWlfJtc9yUUKIQAJzTuhCnT jLts1VJjWHFe4ZK0axPME3YmwzZRXAnYxYQHq6kG8TGoFghTACLX8Be/iugLYwL9565a 6tJJ6ADHIfhKANesB2mqIMNDk18KRqY4l1VADcmHLOPhD2wZM3/HCjBQ8OMaZE0gCIhT eOLYOlqhnM6jtG2AXwL06JByaiK23+evd5p3oTDb/xkofybhZ74WgRLQC4+TKUFBecAr XTTw== X-Forwarded-Encrypted: i=1; AJvYcCWZSkErvesY5mRrd2wx6w8lsKpX+Ga3OVp93t9nksn+ONePcyP4Q1709ynWFXoYPKEIhVxnIKHejvv5fmPjQeo19MB1LAR3Fzc= X-Gm-Message-State: AOJu0YxXUfisY+9ri2fjLE6L3XBCrl5FiiUdtZCKcrkSKGktxAs9YcI9 +NVTMm1ehd6z5zdVQKOGwutaSAM4Wp6oIIkf9gAXYv/cxgCy61li X-Google-Smtp-Source: AGHT+IEUrmf8Z35K242qMLJqeIL3rN/4RH5KOBL/mOgyJGBua28SrFZ793tEirU4bxPTRbl1ZL/b1g== X-Received: by 2002:a17:90a:b883:b0:2b6:208f:7ef0 with SMTP id 98e67ed59e1d1-2bf5f40b09fmr2542180a91.3.1716564680040; Fri, 24 May 2024 08:31:20 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.31.16 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:31:19 -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: [PATCH v6 15/16] bcache: Remove heap-related macros and switch to generic min_heap Date: Fri, 24 May 2024 23:29:57 +0800 Message-Id: <20240524152958.919343-16-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by: Coly Li --- Changes in v6: - Rename the MIN_HEAP() macro to DEFINE_MIN_HEAP(). 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 *ca, struct bucket *b) * prio is worth 1/8th of what INITIAL_PRIO is worth. */ -#define bucket_prio(b) \ -({ \ - unsigned int min_prio = (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 = (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 = (struct bucket **)l; + struct bucket **rhs = (struct bucket **)r; + struct cache *ca = args; + + return new_bucket_prio(ca, *lhs) > new_bucket_prio(ca, *rhs); +} -#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 = (struct bucket **)l; + struct bucket **rhs = (struct bucket **)r; + struct cache *ca = args; + + return new_bucket_prio(ca, *lhs) < new_bucket_prio(ca, *rhs); +} + +static inline void new_bucket_swap(void *l, void *r, void __always_unused *args) +{ + struct bucket **lhs = l, **rhs = r; + + swap(*lhs, *rhs); +} static void invalidate_buckets_lru(struct cache *ca) { struct bucket *b; - ssize_t i; + const struct min_heap_callbacks bucket_max_cmp_callback = { + .less = new_bucket_max_cmp, + .swp = new_bucket_swap, + }; + const struct min_heap_callbacks bucket_min_cmp_callback = { + .less = new_bucket_min_cmp, + .swp = new_bucket_swap, + }; - ca->heap.used = 0; + ca->heap.nr = 0; for_each_bucket(b, ca) { if (!bch_can_invalidate_bucket(ca, b)) continue; - 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] = b; - heap_sift(&ca->heap, 0, bucket_max_cmp); + min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca); } } - for (i = ca->heap.used / 2 - 1; i >= 0; --i) - heap_sift(&ca->heap, i, bucket_min_cmp); + min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca); 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 = min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca); bch_invalidate_one_bucket(ca, b); } diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h index 4e6afa89921f..654df8b7d344 100644 --- a/drivers/md/bcache/bcache.h +++ b/drivers/md/bcache/bcache.h @@ -457,7 +457,7 @@ struct cache { /* Allocation stuff: */ struct bucket *buckets; - DECLARE_HEAP(struct bucket *, heap); + DEFINE_MIN_HEAP(struct bucket *, cache_heap) heap; /* * 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 = 0; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k; + min_heap_init(&iter.heap, NULL, MAX_BSETS); + if (b->ops->is_extents) for_each_key(b, k, &iter) ret += 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 = NULL; - struct btree_iter_stack iter; + struct btree_iter iter; const char *err; + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key(b, k, &iter) { if (b->ops->is_extents) { err = "Keys out of order"; @@ -110,9 +114,9 @@ void __bch_check_keys(struct btree_keys *b, const char *fmt, ...) static void bch_btree_iter_next_check(struct btree_iter *iter) { - struct bkey *k = iter->data->k, *next = bkey_next(k); + struct bkey *k = iter->heap.data->k, *next = bkey_next(k); - 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 = BTREE_INSERT_STATUS_NO_INSERT; struct bset *i = bset_tree_last(b)->data; struct bkey *m, *prev = NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey preceding_key_on_stack = ZERO_KEY; struct bkey *preceding_key_p = &preceding_key_on_stack; BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); + 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); - m = bch_btree_iter_stack_init(b, &iter, preceding_key_p); + m = bch_btree_iter_init(b, &iter, preceding_key_p); - if (b->ops->insert_fixup(b, k, &iter.iter, replace_key)) + if (b->ops->insert_fixup(b, k, &iter, replace_key)) return status; status = BTREE_INSERT_STATUS_INSERT; @@ -1077,79 +1083,102 @@ struct bkey *__bch_bset_search(struct btree_keys *b, struct bset_tree *t, /* Btree iterator */ -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 = l; + const struct btree_iter_set *_r = r; + + return bkey_cmp(_l->k, _r->k) <= 0; +} -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 __always_unused *args) { - return bkey_cmp(l.k, r.k) > 0; + struct btree_iter_set *_iter1 = iter1; + struct btree_iter_set *_iter2 = iter2; + + swap(*_iter1, *_iter2); } static inline bool btree_iter_end(struct btree_iter *iter) { - return !iter->used; + return !iter->heap.nr; } void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end) { + const struct min_heap_callbacks callbacks = { + .less = new_btree_iter_cmp, + .swp = new_btree_iter_swap, + }; + if (k != 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)); } -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 = NULL; - iter->iter.size = ARRAY_SIZE(iter->stack_data); - iter->iter.used = 0; + iter->heap.size = ARRAY_SIZE(iter->heap.preallocated); + iter->heap.nr = 0; #ifdef CONFIG_BCACHE_DEBUG - iter->iter.b = b; + iter->b = b; #endif for (; start <= bset_tree_last(b); start++) { ret = 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)); } return ret; } -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); } 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 = NULL; + const struct min_heap_callbacks callbacks = { + .less = cmp, + .swp = new_btree_iter_swap, + }; if (!btree_iter_end(iter)) { bch_btree_iter_next_check(iter); - ret = iter->data->k; - iter->data->k = bkey_next(iter->data->k); + ret = iter->heap.data->k; + iter->heap.data->k = bkey_next(iter->heap.data->k); - 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 = iter->data->end; + iter->heap.data->k = iter->heap.data->end; } - if (iter->data->k == iter->data->end) - heap_pop(iter, b, cmp); + if (iter->heap.data->k == iter->heap.data->end) { + if (iter->heap.nr) { + b = 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); } return ret; @@ -1157,7 +1186,7 @@ static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, 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); } @@ -1195,16 +1224,18 @@ static void btree_mergesort(struct btree_keys *b, struct bset *out, struct btree_iter *iter, bool fixup, bool remove_stale) { - int i; struct bkey *k, *last = NULL; BKEY_PADDED(k) tmp; bool (*bad)(struct btree_keys *, const struct bkey *) = remove_stale ? bch_ptr_bad : bch_ptr_invalid; + const struct min_heap_callbacks callbacks = { + .less = b->ops->sort_cmp, + .swp = new_btree_iter_swap, + }; /* Heapify the iterator, using our comparison function */ - for (i = iter->used / 2 - 1; i >= 0; --i) - heap_sift(iter, i, b->ops->sort_cmp); + min_heapify_all(&iter->heap, &callbacks, NULL); while (!btree_iter_end(iter)) { if (b->ops->sort_fixup && fixup) @@ -1293,10 +1324,11 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, struct bset_sort_state *state) { size_t order = b->page_order, keys = 0; - struct btree_iter_stack iter; + struct btree_iter iter; int oldsize = bch_count_data(b); - __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]); if (start) { unsigned int i; @@ -1307,7 +1339,7 @@ void bch_btree_sort_partial(struct btree_keys *b, unsigned int start, order = get_order(__set_bytes(b->set->data, keys)); } - __btree_sort(b, &iter.iter, start, order, false, state); + __btree_sort(b, &iter, start, order, false, state); EBUG_ON(oldsize >= 0 && bch_count_data(b) != oldsize); } @@ -1323,11 +1355,13 @@ void bch_btree_sort_into(struct btree_keys *b, struct btree_keys *new, struct bset_sort_state *state) { uint64_t start_time = local_clock(); - struct btree_iter_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); - bch_btree_iter_stack_init(b, &iter, NULL); + bch_btree_iter_init(b, &iter, NULL); - btree_mergesort(b, new->set->data, &iter.iter, false, true); + btree_mergesort(b, new->set->data, &iter, false, true); bch_time_stats_update(&state->time, start_time); 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 { }; 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, }; +struct btree_iter_set { + struct bkey *k, *end; +}; + /* Btree key iteration */ struct btree_iter { - size_t size, used; #ifdef CONFIG_BCACHE_DEBUG struct btree_keys *b; #endif - struct btree_iter_set { - struct bkey *k, *end; - } data[]; -}; - -/* 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; }; 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_iter *iter, 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); 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 btree_keys *b, return search ? __bch_bset_search(b, t, search) : t->data->start; } -#define for_each_key_filter(b, k, stack_iter, filter) \ - for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ - ((k) = 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) = bch_btree_iter_next_filter((iter), (b), filter));) -#define for_each_key(b, k, stack_iter) \ - for (bch_btree_iter_stack_init((b), (stack_iter), NULL); \ - ((k) = bch_btree_iter_next(&((stack_iter)->iter)));) +#define for_each_key(b, k, iter) \ + for (bch_btree_iter_init((b), (iter), NULL); \ + ((k) = bch_btree_iter_next(iter));) /* Sorting */ 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 = "bad btree header"; struct bset *i = btree_bset_first(b); - struct btree_iter *iter; + struct btree_iter iter; /* * c->fill_iter can allocate an iterator with more memory space * than static MAX_BSETS. * See the comment arount cache_set->fill_iter. */ - iter = mempool_alloc(&b->c->fill_iter, GFP_NOIO); - iter->size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; - iter->used = 0; + iter.heap.data = mempool_alloc(&b->c->fill_iter, GFP_NOIO); + iter.heap.size = b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; + iter.heap.nr = 0; #ifdef CONFIG_BCACHE_DEBUG - iter->b = &b->keys; + iter.b = &b->keys; #endif if (!i->seq) @@ -199,7 +199,7 @@ void bch_btree_node_read_done(struct btree *b) if (i != b->keys.set[0].data && !i->keys) goto err; - bch_btree_iter_push(iter, i->start, bset_bkey_last(i)); + bch_btree_iter_push(&iter, i->start, bset_bkey_last(i)); b->written += set_blocks(i, block_bytes(b->c->cache)); } @@ -211,7 +211,7 @@ void bch_btree_node_read_done(struct btree *b) if (i->seq == b->keys.set[0].data->seq) goto err; - bch_btree_sort_and_fix_extents(&b->keys, iter, &b->c->sort); + bch_btree_sort_and_fix_extents(&b->keys, &iter, &b->c->sort); i = b->keys.set[0].data; err = "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, struct gc_stat *gc) uint8_t stale = 0; unsigned int keys = 0, good_keys = 0; struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; struct bset_tree *t; + min_heap_init(&iter.heap, NULL, MAX_BSETS); + gc->nodes++; for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { @@ -1570,9 +1572,11 @@ static int btree_gc_rewrite_node(struct btree *b, struct 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 = 0; + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) ret += bkey_u64s(k); @@ -1611,18 +1615,18 @@ static int btree_gc_recurse(struct btree *b, struct btree_op *op, int ret = 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 = r + ARRAY_SIZE(r) - 1; - 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); for (i = r; i < r + ARRAY_SIZE(r); i++) i->b = ERR_PTR(-EINTR); while (1) { - k = bch_btree_iter_next_filter(&iter.iter, &b->keys, - bch_ptr_bad); + k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad); if (k) { r->b = 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, struct btree_op *op) { int ret = 0; struct bkey *k, *p = NULL; - struct btree_iter_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); 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); if (b->level) { - bch_btree_iter_stack_init(&b->keys, &iter, NULL); + bch_btree_iter_init(&b->keys, &iter, NULL); do { - k = bch_btree_iter_next_filter(&iter.iter, &b->keys, + k = 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 = arg; struct btree_check_state *check_state = info->state; struct cache_set *c = check_state->c; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; @@ -1959,9 +1965,11 @@ static int bch_btree_check_thread(void *arg) cur_idx = prev_idx = 0; ret = 0; + 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 = bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad); + bch_btree_iter_init(&c->root->keys, &iter, NULL); + k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); BUG_ON(!k); p = k; @@ -1979,7 +1987,7 @@ static int bch_btree_check_thread(void *arg) skip_nr = cur_idx - prev_idx; while (skip_nr) { - k = bch_btree_iter_next_filter(&iter.iter, + k = 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 = 0; int i; struct bkey *k = NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct btree_check_state check_state; + 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, if (b->level) { struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; - 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); - while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, + while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { ret = bcache_btree(map_nodes_recurse, k, b, op, from, fn, flags); @@ -2581,12 +2592,12 @@ int bch_btree_map_keys_recurse(struct btree *b, struct btree_op *op, { int ret = MAP_CONTINUE; struct bkey *k; - struct btree_iter_stack iter; + struct btree_iter iter; - 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); - while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys, - bch_ptr_bad))) { + while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { ret = !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 = bkey_next(i->k); if (i->k == i->end) - *i = iter->data[--iter->used]; + *i = iter->heap.data[--iter->heap.nr]; } -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 = bkey_cmp(l.k, r.k); + struct btree_iter_set *_l = (struct btree_iter_set *)l; + struct btree_iter_set *_r = (struct btree_iter_set *)r; + int64_t c = bkey_cmp(_l->k, _r->k); - return c ? c > 0 : l.k < r.k; + return !(c ? c > 0 : _l->k < _r->k); } 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_keys *bk, } const struct btree_keys_ops bch_btree_keys_ops = { - .sort_cmp = bch_key_sort_cmp, + .sort_cmp = new_bch_key_sort_cmp, .insert_fixup = bch_btree_ptr_insert_fixup, .key_invalid = bch_btree_ptr_invalid, .key_bad = bch_btree_ptr_bad, @@ -255,22 +256,36 @@ const struct btree_keys_ops bch_btree_keys_ops = { * Necessary for btree_sort_fixup() - if there are multiple keys that compare * 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 __always_unused *args) +{ + struct btree_iter_set *_l = (struct btree_iter_set *)l; + struct btree_iter_set *_r = (struct btree_iter_set *)r; + int64_t c = 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 __always_unused *args) { - int64_t c = bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); + struct btree_iter_set *_iter1 = iter1; + struct btree_iter_set *_iter2 = iter2; - return c ? c > 0 : l.k < r.k; + swap(*_iter1, *_iter2); } static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { - while (iter->used > 1) { - struct btree_iter_set *top = iter->data, *i = top + 1; - - if (iter->used > 2 && - bch_extent_sort_cmp(i[0], i[1])) + const struct min_heap_callbacks callbacks = { + .less = new_bch_extent_sort_cmp, + .swp = new_btree_iter_swap, + }; + while (iter->heap.nr > 1) { + struct btree_iter_set *top = iter->heap.data, *i = top + 1; + + if (iter->heap.nr > 2 && + !new_bch_extent_sort_cmp(&i[0], &i[1], NULL)) i++; if (bkey_cmp(top->k, &START_KEY(i->k)) <= 0) @@ -278,7 +293,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, 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; } @@ -288,7 +303,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, else bch_cut_front(top->k, i->k); - 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, 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); return tmp; } else { @@ -618,7 +633,7 @@ static bool bch_extent_merge(struct btree_keys *bk, } const struct btree_keys_ops bch_extent_keys_ops = { - .sort_cmp = bch_extent_sort_cmp, + .sort_cmp = new_bch_extent_sort_cmp, .sort_fixup = bch_extent_sort_fixup, .insert_fixup = bch_extent_insert_fixup, .key_invalid = 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); } -static bool bucket_cmp(struct bucket *l, struct bucket *r) +static bool new_bucket_cmp(const void *l, const void *r, void __always_unused *args) { - return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); + struct bucket **_l = (struct bucket **)l; + struct bucket **_r = (struct bucket **)r; + + return GC_SECTORS_USED(*_l) >= GC_SECTORS_USED(*_r); +} + +static void new_bucket_swap(void *l, void *r, void __always_unused *args) +{ + struct bucket **_l = l; + struct bucket **_r = r; + + swap(*_l, *_r); } static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; - return (b = heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; + return (b = min_heap_peek(&ca->heap)[0]) ? GC_SECTORS_USED(b) : 0; } void bch_moving_gc(struct cache_set *c) @@ -199,6 +210,10 @@ void bch_moving_gc(struct cache_set *c) struct cache *ca = c->cache; struct bucket *b; unsigned long sectors_to_move, reserve_sectors; + const struct min_heap_callbacks callbacks = { + .less = new_bucket_cmp, + .swp = new_bucket_swap, + }; if (!c->copy_gc_enabled) return; @@ -209,7 +224,7 @@ void bch_moving_gc(struct cache_set *c) reserve_sectors = ca->sb.bucket_size * fifo_used(&ca->free[RESERVE_MOVINGGC]); - ca->heap.used = 0; + ca->heap.nr = 0; for_each_bucket(b, ca) { if (GC_MARK(b) == GC_MARK_METADATA || @@ -218,25 +233,31 @@ void bch_moving_gc(struct cache_set *c) atomic_read(&b->pin)) continue; - if (!heap_full(&ca->heap)) { + if (!min_heap_full(&ca->heap)) { sectors_to_move += 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 -= bucket_heap_top(ca); sectors_to_move += GC_SECTORS_USED(b); ca->heap.data[0] = b; - heap_sift(&ca->heap, 0, bucket_cmp); + min_heap_sift_down(&ca->heap, 0, &callbacks, NULL); } } while (sectors_to_move > reserve_sectors) { - heap_pop(&ca->heap, b, bucket_cmp); + if (ca->heap.nr) { + b = min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &callbacks, NULL); + } sectors_to_move -= GC_SECTORS_USED(b); } - while (heap_pop(&ca->heap, b, bucket_cmp)) + while (ca->heap.nr) { + b = min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &callbacks, NULL); SET_GC_MOVE(b, 1); + } mutex_unlock(&c->bucket_lock); diff --git a/drivers/md/bcache/super.c b/drivers/md/bcache/super.c index 4d11fc664cb0..1240d1b09e8c 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); - iter_size = sizeof(struct btree_iter) + - ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) * + iter_size = ((meta_bucket_pages(sb) * PAGE_SECTORS) / sb->block_size) * sizeof(struct btree_iter_set); c->devices = 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 = 0; struct bkey *k; struct btree *b; - struct btree_iter_stack iter; + struct btree_iter iter; + + min_heap_init(&iter.heap, NULL, MAX_BSETS); goto lock_root; 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; #endif -#define DECLARE_HEAP(type, name) \ - struct { \ - size_t size, used; \ - type *data; \ - } name - #define init_heap(heap, _size, gfp) \ ({ \ size_t _bytes; \ - (heap)->used = 0; \ + (heap)->nr = 0; \ (heap)->size = (_size); \ _bytes = (heap)->size * sizeof(*(heap)->data); \ (heap)->data = kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ @@ -52,64 +47,6 @@ do { \ (heap)->data = NULL; \ } while (0) -#define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j]) - -#define heap_sift(h, i, cmp) \ -do { \ - size_t _r, _j = i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j = _r) { \ - _r = _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 = (i - 1) / 2; \ - if (cmp((h)->data[i], (h)->data[p])) \ - break; \ - heap_swap(h, i, p); \ - i = p; \ - } \ -} while (0) - -#define heap_add(h, d, cmp) \ -({ \ - bool _r = !heap_full(h); \ - if (_r) { \ - size_t _i = (h)->used++; \ - (h)->data[_i] = d; \ - \ - heap_sift_down(h, _i, cmp); \ - heap_sift(h, _i, cmp); \ - } \ - _r; \ -}) - -#define heap_pop(h, d, cmp) \ -({ \ - bool _r = (h)->used; \ - if (_r) { \ - (d) = (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 == (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 = arg; struct bch_dirty_init_state *state = info->state; struct cache_set *c = state->c; - struct btree_iter_stack iter; + struct btree_iter iter; struct bkey *k, *p; int cur_idx, prev_idx, skip_nr; k = p = NULL; prev_idx = 0; - bch_btree_iter_stack_init(&c->root->keys, &iter, NULL); - k = 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 = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); BUG_ON(!k); p = k; @@ -930,7 +931,7 @@ static int bch_dirty_init_thread(void *arg) skip_nr = cur_idx - prev_idx; while (skip_nr) { - k = bch_btree_iter_next_filter(&iter.iter, + k = 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 = NULL; struct bkey *k = NULL; - struct btree_iter_stack iter; + struct btree_iter iter; struct sectors_dirty_init op; struct cache_set *c = d->c; struct bch_dirty_init_state state; + min_heap_init(&iter.heap, NULL, MAX_BSETS); + retry_lock: b = c->root; rw_lock(0, b, b->level); From patchwork Fri May 24 15:29:58 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Kuan-Wei Chiu X-Patchwork-Id: 13673285 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 5F4A312F362 for ; Fri, 24 May 2024 15:31:27 +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=1716564689; cv=none; b=s3u525HccxAUkgREh6GmHX7f5ymZLCjnP0tJa5WllMd7N9iLSjgZkcfXQX0YHTh8qUFH4dZGB/NC6IT7yyKPbnPwtFkwaKuR880c1Meo2XLAuGACoVwh1c2ZQ+BQ1/GZNya75u9qk6UiRgyKRIdT8vXnMENAgnRrAZtCviHFzKE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716564689; c=relaxed/simple; bh=A6nkXhDo3vRgC0ouJzd/jrZPACR0P+/9713U0Tn3QY0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GIQL49sSm94Slv76nDpWhuzUBCbUv3dZtlgb9E2mPSyEexoojey9diQwNAuiAQwJrc931Csp8WE9cbWuGYfFb9tQYncUVsd/Tu/j1Bfv4ZstXjsKah+L9Nirl9A77qU3hrk/WOJYFQMqfEDqZfjTkEpUFN1et2yxNwpuZSZ0TVA= 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=OdENswRs; 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="OdENswRs" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2ba0bbc7302so771685a91.2 for ; Fri, 24 May 2024 08:31:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1716564687; x=1717169487; darn=lists.linux.dev; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=5uL7niTDxIwgtvT483XQdSOjcKJiY9fkFNHM4CoL7As=; b=OdENswRsPbjzsUZuieDlVdqzxO7hdS0Cd7xbbeLi/HYx6EiEewqz5864UTn5BP7KmH kmViWtaP521hWNeGcCKbOYQktJLcIXX00aImOtWtf+SjcNS5pjOw+GyDRecjmw3BuBiO sc1GUkBYdHp7k7bLqCNquZPKiThpcU7AWuZyWmqg3XDexOJ+xvRetTi3gSuyFbROh/+V f/FapEf2PQTDpjtudBzrCPLu+Y60M0PVfkwxyU8JM4BRp3yTyoQP/5EPrW1ZqDlfDU2Z 53XTTvHWZ+fjQe3FcX1AYgJwuF6jdDwD4RUFoCTpkZ8EI8JC/h4+CPZ2MMYk+tZB57Ml BxwQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716564687; x=1717169487; 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=5uL7niTDxIwgtvT483XQdSOjcKJiY9fkFNHM4CoL7As=; b=EqyfAm9Nx9l8dMP15tdPnF+2JpX7zgXP1flLskEKkoF1GC9d4xeT5reHtDp66rbziL AFnMnkGfqpa9pHLqL2+LSue7erhPqecKv9jLvIm/G38j2MrAUoEwzomg5bZFb6vxv/uH RQLo2zKxPkwr4VAYuUO31u8DbtRg5Y9neD2ZRpsRwiWOoZhNqTk+1cuauXOnTSGpNyA5 dd0nR8bNYCKTWszF9Hz4if/Rnp3DY1/EWqoQmivraUnyDT/YpGsE38o3udZKHyzGHKMt GMrr4p644z+7RP1y4k+0HRzCU0/K6BAmd+usj9P3DiZzMBjpdTOq1c5VzyIKrkvhJ5v8 T4jQ== X-Forwarded-Encrypted: i=1; AJvYcCUf5U6P134styGVnqAnhBcnwv0zdrEoBlz9vEWy7vZBYx/ze+1G/W3Ygr/eRLZBavOVEXEX475YajpL3iBZDHPmEI5IytZG4/I= X-Gm-Message-State: AOJu0Yw+/zc9ICiQ5X+pAdf26j6XARPxUYlHPJYTQHjl3b/bqcfselRL tXlTR6RpX5A/Pbzj7U+Y3Wbeb+2SUGfJQImf2OZG4dOtHosFIV3y X-Google-Smtp-Source: AGHT+IGHGxs6xYS1pxOoTReksRT5lb2eG9Sec99+HTPhjDOGe5bGI7HQWqGqKuRY3Cvudglt4fu64g== X-Received: by 2002:a17:90b:3110:b0:2bd:8b85:d7ca with SMTP id 98e67ed59e1d1-2bf5e0a753emr2553910a91.0.1716564686682; Fri, 24 May 2024 08:31:26 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id 98e67ed59e1d1-2bf5f50d294sm1525556a91.20.2024.05.24.08.31.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 24 May 2024 08:31:24 -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: [PATCH v6 16/16] bcachefs: Remove heap-related macros and switch to generic min_heap Date: Fri, 24 May 2024 23:29:58 +0800 Message-Id: <20240524152958.919343-17-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240524152958.919343-1-visitorckw@gmail.com> References: <20240524152958.919343-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: dm-devel@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 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/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by: Kent Overstreet --- Changes in v6: - Rename the MIN_HEAP() macro to DEFINE_MIN_HEAP(). 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 -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 __always_unused *args) { - return l->expire - r->expire; + struct io_timer **_l = (struct io_timer **)l; + struct io_timer **_r = (struct io_timer **)r; + + return (*_l)->expire < (*_r)->expire; +} + +static inline void io_timer_swp(void *l, void *r, void __always_unused *args) +{ + struct io_timer **_l = (struct io_timer **)l; + struct io_timer **_r = (struct io_timer **)r; + + swap(*_l, *_r); } void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks = { + .less = io_timer_cmp, + .swp = io_timer_swp, + }; spin_lock(&clock->timer_lock); @@ -26,11 +39,11 @@ void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) return; } - for (i = 0; i < clock->timers.used; i++) + for (i = 0; i < clock->timers.nr; i++) if (clock->timers.data[i] == timer) goto out; - 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 io_timer *timer) void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks = { + .less = io_timer_cmp, + .swp = io_timer_swp, + }; spin_lock(&clock->timer_lock); - for (i = 0; i < clock->timers.used; i++) + for (i = 0; i < clock->timers.nr; i++) if (clock->timers.data[i] == timer) { - heap_del(&clock->timers, i, io_timer_cmp, NULL); + min_heap_del(&clock->timers, i, &callbacks, NULL); break; } @@ -131,12 +148,16 @@ static struct io_timer *get_expired_timer(struct io_clock *clock, unsigned long now) { struct io_timer *ret = NULL; + const struct min_heap_callbacks callbacks = { + .less = io_timer_cmp, + .swp = io_timer_swp, + }; spin_lock(&clock->timer_lock); - 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); spin_unlock(&clock->timer_lock); @@ -161,7 +182,7 @@ void bch2_io_timers_to_text(struct printbuf *out, struct io_clock *clock) spin_lock(&clock->timer_lock); now = atomic64_read(&clock->now); - for (i = 0; i < clock->timers.used; i++) + for (i = 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..f2c8a25b7079 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 -typedef HEAP(struct io_timer *) io_timer_heap; +typedef DEFINE_MIN_HEAP(struct io_timer *, io_timer_heap) io_timer_heap; struct io_clock { atomic64_t now; diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index b26dc7424662..797cb389cf3f 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -896,8 +896,8 @@ static int __ec_stripe_mem_alloc(struct bch_fs *c, size_t idx, gfp_t gfp) 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 = h->used; + memcpy(n.data, h->data, h->nr * sizeof(h->data[0])); + n.nr = h->nr; swap(*h, n); } mutex_unlock(&c->ec_stripes_heap_lock); @@ -988,7 +988,7 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) lockdep_assert_held(&c->ec_stripes_heap_lock); - if (h->used && + if (h->nr && h->data[0].blocks_nonempty == 0 && !bch2_stripe_is_open(c, h->data[0].idx)) return h->data[0].idx; @@ -996,14 +996,6 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) return 0; } -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) { @@ -1012,39 +1004,71 @@ static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h, genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx = i; } +static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void __always_unused *args) +{ + struct ec_stripe_heap_entry *_l = (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r = (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 = (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r = (struct ec_stripe_heap_entry *)r; + ec_stripes_heap *_h = (ec_stripes_heap *)h; + size_t i = _l - _h->data; + size_t j = _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 = &c->ec_stripes_heap; struct stripe *m = genradix_ptr(&c->stripes, idx); - BUG_ON(m->heap_idx >= h->used); + BUG_ON(m->heap_idx >= h->nr); BUG_ON(h->data[m->heap_idx].idx != idx); } void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks = { + .less = ec_stripes_heap_cmp, + .swp = ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); - 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); } void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks = { + .less = ec_stripes_heap_cmp, + .swp = ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); - BUG_ON(heap_full(&c->ec_stripes_heap)); + BUG_ON(min_heap_full(&c->ec_stripes_heap)); - heap_add(&c->ec_stripes_heap, ((struct ec_stripe_heap_entry) { + genradix_ptr(&c->stripes, idx)->heap_idx = c->ec_stripes_heap.nr; + min_heap_push(&c->ec_stripes_heap, &((struct ec_stripe_heap_entry) { .idx = idx, .blocks_nonempty = m->blocks_nonempty, }), - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + &callbacks, + &c->ec_stripes_heap); heap_verify_backpointer(c, idx); mutex_unlock(&c->ec_stripes_heap_lock); @@ -1053,6 +1077,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 = { + .less = ec_stripes_heap_cmp, + .swp = ec_stripes_heap_swap, + }; ec_stripes_heap *h = &c->ec_stripes_heap; bool do_deletes; size_t i; @@ -1063,10 +1091,8 @@ void bch2_stripes_heap_update(struct bch_fs *c, h->data[m->heap_idx].blocks_nonempty = m->blocks_nonempty; i = 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); heap_verify_backpointer(c, idx); @@ -1859,7 +1885,7 @@ static s64 get_existing_stripe(struct bch_fs *c, return -1; mutex_lock(&c->ec_stripes_heap_lock); - for (heap_idx = 0; heap_idx < h->used; heap_idx++) { + for (heap_idx = 0; heap_idx < h->nr; heap_idx++) { /* No blocks worth reusing, stripe will just be deleted: */ if (!h->data[heap_idx].blocks_nonempty) continue; @@ -2190,7 +2216,7 @@ void bch2_stripes_heap_to_text(struct printbuf *out, struct bch_fs *c) size_t i; mutex_lock(&c->ec_stripes_heap_lock); - for (i = 0; i < min_t(size_t, h->used, 50); i++) { + for (i = 0; i < min_t(size_t, h->nr, 50); i++) { m = genradix_ptr(&c->stripes, h->data[i].idx); 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..1df03dccfc72 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; }; -typedef HEAP(struct ec_stripe_heap_entry) ec_stripes_heap; +typedef DEFINE_MIN_HEAP(struct ec_stripe_heap_entry, ec_stripes_heap) ec_stripes_heap; #endif /* _BCACHEFS_EC_TYPES_H */ diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index 5d2c470a49ac..d0d99400f986 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); } -#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 = 0; \ + (heap)->nr = 0; \ (heap)->size = (_size); \ (heap)->data = kvmalloc((heap)->size * sizeof((heap)->data[0]),\ (gfp)); \ @@ -76,113 +69,6 @@ do { \ (heap)->data = NULL; \ } while (0) -#define heap_set_backpointer(h, i, _fn) \ -do { \ - void (*fn)(typeof(h), size_t) = _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 == (h)->size) - -#define heap_sift_down(h, i, cmp, set_backpointer) \ -do { \ - size_t _c, _j = i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j = _c) { \ - _c = _j * 2 + 1; \ - if (_c + 1 < (h)->used && \ - cmp(h, (h)->data[_c], (h)->data[_c + 1]) >= 0) \ - _c++; \ - \ - if (cmp(h, (h)->data[_c], (h)->data[_j]) >= 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 = (i - 1) / 2; \ - if (cmp(h, (h)->data[i], (h)->data[p]) >= 0) \ - break; \ - heap_swap(h, i, p, set_backpointer); \ - i = p; \ - } \ -} while (0) - -#define __heap_add(h, d, cmp, set_backpointer) \ -({ \ - size_t _i = (h)->used++; \ - (h)->data[_i] = 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 = !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)) >= 0) { \ - (h)->data[0] = 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 = (i); \ - \ - BUG_ON(_i >= (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 = (h)->used; \ - if (_r) { \ - (d) = (h)->data[0]; \ - heap_del(h, 0, cmp, set_backpointer); \ - } \ - _r; \ -}) - -#define heap_resort(heap, cmp, set_backpointer) \ -do { \ - ssize_t _i; \ - for (_i = (ssize_t) (heap)->used / 2 - 1; _i >= 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)