From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) (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 6664414A4DD; Thu, 25 Apr 2024 14:18:40 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054723; cv=none; b=IJrqO+Mkw4dflh+cD9dMWjn8cS63bODupdvjeUCvoXKr7tvsJSecZ0gLeZPT+EWOqGL/3EYj2XrXW9b27GX9tSxlA5fGGm48WHCWtpq5r/mvNXGbwbWDhFTzqWAUrrxMvNPOiJ/rR+67q2Js0OK0D5bJtohrHWwy+tF9/0B4JTQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054723; c=relaxed/simple; bh=5eMBfUoMBCijCucBrYyXb5iM12NH5j3cQUyWi3Km8qU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ATb9aJO1nl6zNHJBOPOwjM/k8LQKYqaWbouyW2LQEmqpAC0l62SCsQl4H9Yn+NC1sveUUiwU9iIQcpTDCeEXJ3vQQ671vnU3aUJ0zz4hiwOHc2el1rmjJY4HjcKScyLHDilxoiUl+Vq3Mi8DL665OP3rnDZnU9/chyUQAGZd8k0= 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=LQyGM5tk; arc=none smtp.client-ip=209.85.214.176 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="LQyGM5tk" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-1e825c89532so162465ad.2; Thu, 25 Apr 2024 07:18:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054720; x=1714659520; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=VJIN0mq5LX930XVge9ngeqBSR6yoC+cL9OxlPKOkaa8=; b=LQyGM5tkXvxPv4zOSYAhfi29xScO4Ivx1TJpN8hkYyFCsGhWwXSvz2WknZ0L41Qgu9 5wwhMZSshyTKuzIIvhV4yVx+JnKuN2RUBMHCS4lOORcLvmWjikPxwZZa/0lnRiQ/fjbz anosOI8F/iiTIyxHQ/HtL56/ugdE8+fz7JuZKR8OrnsbrIIRPhTmdurA4MY8CCtyvJsW ZjjeJT1PWFF2PtTjAEc6qoVK420q0v6t9rkOZuEmatLE7QLAsb6ogZonPE3vioSRlIBr rAKAoQPZ+1XblyCE5h+488hYX3FcktPYvKdMlg0DrXdV5718exSlrnhela5jtIQciUfv Y2Tg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054720; x=1714659520; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=VJIN0mq5LX930XVge9ngeqBSR6yoC+cL9OxlPKOkaa8=; b=asW7/gYklwwTbqPXnPR6w/Huv7cY6HChaQL/sHay80Pf9Hgr6pqB5HssoqXEehvOSO O41PSeYJ1jVCyqjcT+22WxPaXo4iQxqdtKy0FKlRq/dYpj/KaiNXKljnoPMqYiXqMKJ3 IzfZtAvdpjITO62UWMwg3rU+44WPMFB7ocdMPitqRLqdYdBqpzFYrxSrhlqozobHU4Q5 xxEzZ28QCctGHFprnpOuix4yW8LYpnlg+ssvj6zoJzSMiofN3/5yjJV8ozrVdVrbRyeo G+M2NOWuzD3ixCJRMiJ1UPsA9AOz7eF5oJOX8s7BXJZozpP+Wn2QlU337EpAaGy6Ba66 d7Hg== X-Forwarded-Encrypted: i=1; AJvYcCXjyZhzCAHJ1KztQgpjZa4+G0UaHtAg6UwRRWExS1clRGNtqwVkBZGW3o2zpueKMoL198Dn/w2cI1zGNsZrrBR2igB8swAXECYLGh0dkS2QqLx1JyNiAmtBRVrMtASVU3zruNgFDdXCRslNDwHEa6An1qazbeaAYTpb59qgjkA2Lv9zYmhMUX4wA0Ge7dFjQB43zIEnHvcJtteT5ciQ7RbwRVHun5i3UHbog562 X-Gm-Message-State: AOJu0YyfcuNWSbi9go/kIQyNWXXSJU2YnqW8FvIATw17bVclnKBusJ2O qmKxiPraGBzBY2514mx98v+CLPk8nCv3NhvVJ9Nmi9fHh/bLJ0wt X-Google-Smtp-Source: AGHT+IGQTJjuEcM6aEJrfwoGu0krNnwqsY1Gws+dsheyTKe47mC9goJtJ6zOFSf/pjdMiEkhR/vqNw== X-Received: by 2002:a05:6a20:12cb:b0:1ad:8df7:6127 with SMTP id v11-20020a056a2012cb00b001ad8df76127mr4572257pzg.0.1714054719469; Thu, 25 Apr 2024 07:18:39 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:18:38 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 01/16] perf/core: Fix several typos Date: Thu, 25 Apr 2024 22:18:11 +0800 Message-Id: <20240425141826.840077-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'artifically' with 'artificially'. Replace 'irrespecive' with 'irrespective'. Replace 'futher' with 'further'. Replace 'sufficent' with 'sufficient'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap Acked-by tag has been added to the repository mentioned above and --- kernel/events/core.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/kernel/events/core.c b/kernel/events/core.c index 724e6d7e128f..10ac2db83f14 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -534,7 +534,7 @@ void perf_sample_event_took(u64 sample_len_ns) __this_cpu_write(running_sample_length, running_len); =20 /* - * Note: this will be biased artifically low until we have + * Note: this will be biased artificially low until we have * seen NR_ACCUMULATED_SAMPLES. Doing it this way keeps us * from having to maintain a count. */ @@ -596,10 +596,10 @@ static inline u64 perf_event_clock(struct perf_event = *event) * * Event groups make things a little more complicated, but not terribly so= . The * rules for a group are that if the group leader is OFF the entire group = is - * OFF, irrespecive of what the group member states are. This results in + * OFF, irrespective of what the group member states are. This results in * __perf_effective_state(). * - * A futher ramification is that when a group leader flips between OFF and + * A further ramification is that when a group leader flips between OFF and * !OFF, we need to update all group member times. * * @@ -891,7 +891,7 @@ static int perf_cgroup_ensure_storage(struct perf_event= *event, int cpu, heap_size, ret =3D 0; =20 /* - * Allow storage to have sufficent space for an iterator for each + * Allow storage to have sufficient space for an iterator for each * possibly nested cgroup plus an iterator for events with no cgroup. */ for (heap_size =3D 1; css; css =3D css->parent) --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 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 C6B2114B08F; Thu, 25 Apr 2024 14:18:44 +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=1714054727; cv=none; b=C/HiddxS9G5vcFhY8U4+HFrpuVlMiy/T3TZzTedxI8CtGUsMTD0epgG/KS8UzwLkmWWPuilAzQE2pAK7RrFc8bOLajWG7QBF9Nu7OM+VautiL9Te04MN0PI61hqNEvnQ0DbiXT+kG6fQuQldSy+OCgg1nxyAoBJ2NdSOYoGoXvg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054727; c=relaxed/simple; bh=UN1Xetleeq5Nz5tLKfuxk8/opVO9kM/FjVJ/CVGswXI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=cchGpGjHvnS0qFM+iJQgCmlAD3VlqcqK75hgRhE7XtVs9+8si5JjzF+DBuQRtHAWLWC0PMS0XpU+iLivLxgU5xlfeV/GOHwrloJFdCFYsWWLr8CfPjcVzg5bdUUgqESlbG5yON+TeNqorFd8Sk7WykiV21KOPvnnEW2sygGh4dI= 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=PY5QkQkE; 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="PY5QkQkE" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-2af71daeec1so279645a91.0; Thu, 25 Apr 2024 07:18:44 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054724; x=1714659524; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=/7grr21+dk77QDv4Gfk7ePfGBs40BXM1/CLzaulLK98=; b=PY5QkQkEbMlCIyLkp7UL6aA4dQvBNyAA6ZXOqUqyEfjhC1uqotPo3r/I0Gc3GqoCrW 8v5VZHPjGrG8ax1TkdwuZIHrATLGi9VQeCgZp3gfxoQVJXFA7+N4doR4Yig5HjXgEROJ WkrAtj7zauB+Cs+JAldbyxeoUjWEBDNoV+ZrmRsM5ORpPqzxgLuNt7Y7EgNHRJmKfSdE zwFWqItzicgsI2YjXBbI1KxVjcROfgpmIUildGcBu6wyY6VJWioNDwTbBKmSrrD6Tkb0 m1ENsStgacUiAt1NiFNtJLilUgmw1yKTAzrDWWs6iW5kGxt/bHySQg2MlNMQkZsLjIaY /KdQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054724; x=1714659524; 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=MUKDfCESSut6AUzH5yCz0fcr09buW5JWfIutINNuT83AI9ZWJiK/bUKOSDDkLv69yn k+ZCGOe9ipP/cVjyKSR0BQZdoTQrtT05FWkwTh9/buunOUmxwn6iDbrXieww3MM+GxlB 1VMcAF7qOJw74XH3jtGSBK+XLflMQGZ+9cA9kOx4/u7lY/oY0SbZcID0MKQCjZlFdeOC 0RFdi0uH3xgMq8/cbEWz/i4SsbJrGXxvPqT2s2NXmujf3ajBvnzxuwTc27cL+r549FhO 5bjVJtW3sGRmjN6YsVKiLo/Y75rMbX5YpWWUem2+eSfEAyuq0qBbKoDD1eQA+GUJ2Tw4 xLIQ== X-Forwarded-Encrypted: i=1; AJvYcCVkyY6n1B6HI9P91VP1xoMVhBXUwRIBRrLXYlP3cWS2CQ380Ms6KjfZyIb8J55SgIwAz6I0cMK4hl9mFCyriPUkOfZZXVT79HMn57DZiHCSzulytrQFe5u7774M6xa/zj+XVDzer7jIReP5yKERJKauf828jul3KZIEfJnWt3BV5nYHZWZa6R8ezEpkej1J6myLbBF67r8fXpnO+M6JtWanhy8E0zOdavAUPZ8T X-Gm-Message-State: AOJu0Yxg9jO7JXPpEbkejTOBCf+7YJaK1F4Sk1h9Y0pVwc3JklT7WLxO wFiU7yDQpzdxrB+8Sa6PUnyh7rLpbPTGD6cFU9q7Cd9wF3qzckkr X-Google-Smtp-Source: AGHT+IEQD11OltUE11ifdg6XbUXWB+Wv3EwPvaLgQGSfd4UJ7AD3kkEQJxgz0+FjABEIMkzUpKhT0w== X-Received: by 2002:aa7:8d15:0:b0:6ec:f5d2:f641 with SMTP id j21-20020aa78d15000000b006ecf5d2f641mr6842102pfe.1.1714054724050; Thu, 25 Apr 2024 07:18:44 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.40 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:18:43 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 02/16] bcache: Fix typo Date: Thu, 25 Apr 2024 22:18:12 +0800 Message-Id: <20240425141826.840077-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap Acked-by tag has been added to the repository mentioned above and --- drivers/md/bcache/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c index ae380bc3992e..410d8cb49e50 100644 --- a/drivers/md/bcache/util.c +++ b/drivers/md/bcache/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f179.google.com (mail-pl1-f179.google.com [209.85.214.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9346E14C5BA; Thu, 25 Apr 2024 14:18:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054730; cv=none; b=j0oB9zvTnmRDtCgRMM+lSoVbiVSoHf2vNR98OLOEgaIFlkDxjoBQlc9x5XAhi5FvHaiyb/+vnWM7bw+SU8sB0sP2E2DDCLKYIAsDsh+nfW4XP9M7thBCpwhqry8IPj4TRzt8IWIaIi/V5f/h4vM9YxnIdPLWPBWgVEzr2+uED74= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054730; c=relaxed/simple; bh=F4H9nDZNXyr/ZsFI+cCJhr3OYw8PynR+1AAuPVXPV9M=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=VD9xaV7edg3lpA0j/teanCs0ie8I/2N+j5MEwzc3TBsrzDNHXhxv6qpJl6N0z+XpvkaLLLxk/0US0eF2T4efWvDZPTdFJYnJyUX7TTQui1OTmzTrUtx9Ug439RF1Zpb5Ovhjfyr0jt2USq9g4h8RH7yuhyivbVYPgaqJi3hBmSI= 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=nMrMJ25G; arc=none smtp.client-ip=209.85.214.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nMrMJ25G" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1e7af7eb4ccso504645ad.1; Thu, 25 Apr 2024 07:18:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054729; x=1714659529; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=6mL/EL0d7nL6m0RFDxHa1SNm7xjXj5OmWxYW9IhbyI0=; b=nMrMJ25G1+GVM77ZhRT/z0f6RSJRzMEKlZMka6576JaQdU9h58CqXwi0wElgYoZtSs PbWv9e1ipA3eqpK9yxfTUGAJED9ypNaKr/CqDDMRM2pJ77AmJmZ7Eys2yyOBotdmd85q zG5g9btmIAXdD6orYrbkgMieQjWktWWpD04Xtd/iBLiZSr1kxungYVWy4R4QA8QBnnW1 ZgwZHvmFO+qmLFqdZGLVZIBBqVJ9z1nQOSsWNONAOzhBvNjTNwtmP3p8IqnBGbnu9fLO o2LnGK0aTbH/+plOSTujZtDKnrtDoAvbkUdxjEW78RLfmMTAAzXPDavGSNm+X+wTGSaE H7kA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054729; x=1714659529; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=6mL/EL0d7nL6m0RFDxHa1SNm7xjXj5OmWxYW9IhbyI0=; b=H4Ye8lkpOb3E1PyxFI7kVy270Lqd+7yquFL7UUnHuqSzO49KEAS140W0RsDdkGq0+u hLzrtpzyUt5miNCrKXrrRGNZTq5xV4F/C6MqhCLa0GBpHw1yNEX55OHmANbu/OZL7ZjV 3t+jqFGPd/UwG3NHO1qX9T4yobi/HJPDElHbNGbgspev6TBgeLjA3YrCBe+hn0C03vlZ li8f41znGed0mUNqyyxriZqim5DMHR9telmOK3M1myJSLL6gxxcyb2Odts7/jccIylHh QgsM/Lt+Q3CBPcb8/1QxwzXGPg4JBGEJQIO9zWSGMDiiY3Jx6ZGV0I2G6eS+WFdFzgbe DGYA== X-Forwarded-Encrypted: i=1; AJvYcCW8WWbmns6gcowxTjwW2RvfP36t567BXkaoiVJZ8TyC7ei3PEaiUGsw8ZFccFmUyyNFlMzTNGr+l5ALqc3edy0dNASFqRP7tat11w2juHsmwRz4TsmMqGoC8t4wpReFSGu2GEO6vp9K9j/qvwJXbCGcU8GWAnSO+Jqs4QUUDyhm89zWh1cSHS8+jYTrT8c8dABQNR0i2YSeuw0e1XjodNDwtmH5tiAj+vkGPnfr X-Gm-Message-State: AOJu0YyraULuXjCzjqxA0PYjcsu5m0ylXVufMkR8kCvj7XS9FiWRmN1h tyPjqqjdv4b4mjUj702bDEDFgVDh2AXS8QwFkKYt8fzEPIySYjDu X-Google-Smtp-Source: AGHT+IFAco8SS+QgCQv0p+fueHlybivSKvhE5qQYuUi+dWforsZMvlEpw0tqxGG/Sh3EeDZa7lb0cg== X-Received: by 2002:a05:6a00:8985:b0:6ec:f406:ab17 with SMTP id hx5-20020a056a00898500b006ecf406ab17mr6515587pfb.0.1714054728656; Thu, 25 Apr 2024 07:18:48 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:18:48 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 03/16] bcachefs: Fix typo Date: Thu, 25 Apr 2024 22:18:13 +0800 Message-Id: <20240425141826.840077-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap Acked-by tag has been added to the repository mentioned above and --- fs/bcachefs/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 92c6ad75e702..05ac1b3b0604 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pf1-f176.google.com (mail-pf1-f176.google.com [209.85.210.176]) (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 43EB414D458; Thu, 25 Apr 2024 14:18:54 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054736; cv=none; b=jl0KQAM302FB3eKOH3po7BZGxM6uVhn+5J8qNUvIlpJYzWUfswl/bEs15gLnxsBcoMDHWfyFdTibvPOWm6yzUoQmh/lzOa1pkm8MnlE5xMdSF+RSqiFYtn5S01JtjYhKV5LkMdxXagWOBaqm/oxgAf7LWhDDtQbEG/a3y9lPKjY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054736; c=relaxed/simple; bh=UBPaGDck/ZA8B0UL+DhBHPe29q64aPeqGGeJM+dyuCI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=deQe+5oCK0GgB8unnZGtAeAdgAvVlAxX9laj3guithbe5ecOlLPsMkl1IfDyDCCf2cmGNoey944h7Nu0sQSt2I981ThOgTSYO8I8SNAGM7rkuvHRC3J+cvZjvZf1zh3HWvuE33tRQU7h4KG+Vr4dml4f14wJ8RMXMrNS3GXXDOk= 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=AYSBz15Y; arc=none smtp.client-ip=209.85.210.176 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="AYSBz15Y" Received: by mail-pf1-f176.google.com with SMTP id d2e1a72fcca58-6f055602a7aso60966b3a.2; Thu, 25 Apr 2024 07:18:54 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054734; x=1714659534; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=lTCyLQe7nDmHhot+qoQJ7m3IRrdaLewXsdsXjVzXU/A=; b=AYSBz15Ytuiq08/PrnZ/hs47WW+nLhFk4JWTeyUwRdUcrxH0fY78/r4TX9SIiMateZ FoJWiYEYMGSfr8jsKyTtXi2+UtLdmnddvXAfeuJFaNZlqRruQvPf6/ESexDiisPBqdbU Hg9wxMW9MQXyfxb/EVyuJp1buy4tGSvJryzBnC7eF3gNnCZSRO0PnO04E0X1A51BlDL7 0KkUVOmeeoL3uf2mkGE5kueE7J1U+7+adIZ8BwMRGfdBWxMHQ97t4UubaPBgmGVk4/lZ 85uMiXXXposjDJBWSp/Z9csxnbDa3YxZUP2DHyGQTbG1hx/ee5rWPCC7MxdHy+4K+Q3U WXTA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054734; x=1714659534; 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=lTCyLQe7nDmHhot+qoQJ7m3IRrdaLewXsdsXjVzXU/A=; b=Uiy/4GOv6KMRpgQV3H4+TOam5eelVVUwwhJLgEKVAO4nkNb0ry6dHjx7nIqxgSRN7x ILyZGAJPhyEYrsjkCbdRPwtBAI/ayrQx67hsBzJCtD5CmRUcpsHjyO+zeklwefQoeMkC AQgYzc1EPgc4eyYblP9WzuNZRePa6wF1hVExzjUCi4ICjYLWxwfOmVuqLIoaeGEwNDdc YcaGw9mxxg2Jc0OLR5He2yT5sM3+6cITw6KeFTUSQ9MWWOwGMQgoaUQW54xdx+YR9nRF qEwFZGin5hW1ChhBiio3Sf6RHHyxji7udpjgi2loKWO5ezQS4IFdTlmo1taKcC6yayzg gBcg== X-Forwarded-Encrypted: i=1; AJvYcCWa7e5fUgCWoKV1/xXDAxx9SlLTEPNLjJDOmTX+UZzJDwRDxtHxnhvj3Kl8z088BvXb/kjwBSjwJVnjLx6tNivGpduMsvtNEj8InewSgPpnYR/qGwX8te7eqOM3hOYBEOGKExLSo29qToa3NHhQnzph+yTX5/4S/68amU+1eRkdnFH4IBIk7ti1QCaUtN9+K98/34ZBJKxM4+5kLw8FGa1ix+NQXkpB1fMGHGZx X-Gm-Message-State: AOJu0YxDa1ooAtH3jIkFP+oMpdln4DcN612crOLgY0C/J6RoeaiuGE+y qDaWZPA3ZdtM1+qKgKVx70Kg4q4c+LFcRlhHY0aC6jSAhUga1YeS X-Google-Smtp-Source: AGHT+IGSbzNQ5Q2aqH8WFK/GHmRpJ8KMmzSOnYvA2G4nUIb6W2LU6jdyzHGGdGp79WdrjZhsPJZu3Q== X-Received: by 2002:a05:6a20:9055:b0:1a3:c621:da8d with SMTP id e21-20020a056a20905500b001a3c621da8dmr5190788pzc.1.1714054733442; Thu, 25 Apr 2024 07:18:53 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.49 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:18:52 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 04/16] lib min_heap: Add type safe interface Date: Thu, 25 Apr 2024 22:18:14 +0800 Message-Id: <20240425141826.840077-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Implement a type-safe interface for min_heap using strong type pointers instead of void * in the data field. This change includes adding small macro wrappers around functions, enabling the use of __minheap_cast and __minheap_obj_size macros for type casting and obtaining element size. This implementation removes the necessity of passing element size in min_heap_callbacks. Additionally, introduce the MIN_HEAP_PREALLOCATED macro for preallocating some elements. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- Changes in v4: - Change struct initializations to use designated initializers. drivers/md/dm-vdo/repair.c | 9 ++-- drivers/md/dm-vdo/slab-depot.c | 5 +-- include/linux/min_heap.h | 79 ++++++++++++++++++++++------------ kernel/events/core.c | 11 ++--- lib/test_min_heap.c | 13 +++--- 5 files changed, 70 insertions(+), 47 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index defc9359f10e..48c266fa07b6 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -51,6 +51,8 @@ struct recovery_point { bool increment_applied; }; =20 +MIN_HEAP(struct numbered_block_mapping, replay_heap); + struct repair_completion { /* The completion header */ struct vdo_completion completion; @@ -97,7 +99,7 @@ struct repair_completion { * order, then original journal order. This permits efficient iteration o= ver the journal * entries in order. */ - struct min_heap replay_heap; + struct replay_heap replay_heap; /* Fields tracking progress through the journal entries. */ struct numbered_block_mapping *current_entry; struct numbered_block_mapping *current_unfetched_entry; @@ -163,14 +165,13 @@ static void swap_mappings(void *item1, void *item2) } =20 static const struct min_heap_callbacks repair_min_heap =3D { - .elem_size =3D sizeof(struct numbered_block_mapping), .less =3D mapping_is_less_than, .swp =3D swap_mappings, }; =20 static struct numbered_block_mapping *sort_next_heap_element(struct repair= _completion *repair) { - struct min_heap *heap =3D &repair->replay_heap; + struct replay_heap *heap =3D &repair->replay_heap; struct numbered_block_mapping *last; =20 if (heap->nr =3D=3D 0) @@ -1117,7 +1118,7 @@ static void recover_block_map(struct vdo_completion *= completion) * Organize the journal entries into a binary heap so we can iterate over= them in sorted * order incrementally, avoiding an expensive sort call. */ - repair->replay_heap =3D (struct min_heap) { + repair->replay_heap =3D (struct replay_heap) { .data =3D repair->entries, .nr =3D repair->block_map_entry_count, .size =3D repair->block_map_entry_count, diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 46e4721e5b4f..f6ae6956f321 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3309,7 +3309,6 @@ static void swap_slab_statuses(void *item1, void *ite= m2) } =20 static const struct min_heap_callbacks slab_status_min_heap =3D { - .elem_size =3D sizeof(struct slab_status), .less =3D slab_status_is_less_than, .swp =3D swap_slab_statuses, }; @@ -3509,7 +3508,7 @@ static int get_slab_statuses(struct block_allocator *= allocator, static int __must_check vdo_prepare_slabs_for_allocation(struct block_allo= cator *allocator) { struct slab_status current_slab_status; - struct min_heap heap; + MIN_HEAP(struct slab_status, heap) heap; int result; struct slab_status *slab_statuses; struct slab_depot *depot =3D allocator->depot; @@ -3521,7 +3520,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator return result; =20 /* Sort the slabs by cleanliness, then by emptiness hint. */ - heap =3D (struct min_heap) { + heap =3D (struct heap) { .data =3D slab_statuses, .nr =3D allocator->slab_count, .size =3D allocator->slab_count, diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d52daf45861b..87737cadb9a5 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -7,45 +7,53 @@ #include =20 /** - * struct min_heap - Data structure to hold a min-heap. - * @data: Start of array holding the heap elements. + * Data structure to hold a min-heap. * @nr: Number of elements currently in the heap. * @size: Maximum number of elements that can be held in current storage. + * @data: Pointer to the start of array holding the heap elements. + * @preallocated: Start of the static preallocated array holding the heap = elements. */ -struct min_heap { - void *data; - int nr; - int size; -}; +#define MIN_HEAP_PREALLOCATED(_type, _name, _nr) \ +struct _name { \ + int nr; \ + int size; \ + _type *data; \ + _type preallocated[_nr]; \ +} + +#define MIN_HEAP(_type, _name) MIN_HEAP_PREALLOCATED(_type, _name, 0) + +typedef MIN_HEAP(char, min_heap_char) min_heap_char; + +#define __minheap_cast(_heap) (typeof((_heap)->data[0]) *) +#define __minheap_obj_size(_heap) sizeof((_heap)->data[0]) =20 /** * struct min_heap_callbacks - Data/functions to customise the min_heap. - * @elem_size: The nr of each element in bytes. * @less: Partial order function for this heap. * @swp: Swap elements function. */ struct min_heap_callbacks { - int elem_size; bool (*less)(const void *lhs, const void *rhs); void (*swp)(void *lhs, void *rhs); }; =20 /* Sift the element at pos down the heap. */ static __always_inline -void min_heapify(struct min_heap *heap, int pos, +void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func) { void *left, *right; void *data =3D heap->data; - void *root =3D data + pos * func->elem_size; + void *root =3D data + pos * elem_size; int i =3D pos, j; =20 /* Find the sift-down path all the way to the leaves. */ for (;;) { if (i * 2 + 2 >=3D heap->nr) break; - left =3D data + (i * 2 + 1) * func->elem_size; - right =3D data + (i * 2 + 2) * func->elem_size; + left =3D data + (i * 2 + 1) * elem_size; + right =3D data + (i * 2 + 2) * elem_size; i =3D func->less(left, right) ? i * 2 + 1 : i * 2 + 2; } =20 @@ -54,31 +62,37 @@ void min_heapify(struct min_heap *heap, int pos, i =3D i * 2 + 1; =20 /* Backtrack to the correct location. */ - while (i !=3D pos && func->less(root, data + i * func->elem_size)) + while (i !=3D pos && func->less(root, data + i * elem_size)) i =3D (i - 1) / 2; =20 /* Shift the element into its correct place. */ j =3D i; while (i !=3D pos) { i =3D (i - 1) / 2; - func->swp(data + i * func->elem_size, data + j * func->elem_size); + func->swp(data + i * elem_size, data + j * elem_size); } } =20 +#define min_heapify(_heap, _pos, _func) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline -void min_heapify_all(struct min_heap *heap, +void __min_heapify_all(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - min_heapify(heap, i, func); + __min_heapify(heap, i, elem_size, func); } =20 +#define min_heapify_all(_heap, _func) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c) + /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void min_heap_pop(struct min_heap *heap, +void __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -88,27 +102,33 @@ void min_heap_pop(struct min_heap *heap, =20 /* Place last element at the root (position 0) and then sift down. */ heap->nr--; - memcpy(data, data + (heap->nr * func->elem_size), func->elem_size); - min_heapify(heap, 0, func); + memcpy(data, data + (heap->nr * elem_size), elem_size); + __min_heapify(heap, 0, elem_size, func); } =20 +#define min_heap_pop(_heap, _func) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) + /* * Remove the minimum element and then push the given element. The * implementation performs 1 sift (O(log2(nr))) and is therefore more * efficient than a pop followed by a push that does 2. */ static __always_inline -void min_heap_pop_push(struct min_heap *heap, - const void *element, +void __min_heap_pop_push(min_heap_char *heap, + const void *element, size_t elem_size, const struct min_heap_callbacks *func) { - memcpy(heap->data, element, func->elem_size); - min_heapify(heap, 0, func); + memcpy(heap->data, element, elem_size); + __min_heapify(heap, 0, elem_size, func); } =20 +#define min_heap_pop_push(_heap, _element, _func) \ + __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), _func) + /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void min_heap_push(struct min_heap *heap, const void *element, +void __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, const struct min_heap_callbacks *func) { void *data =3D heap->data; @@ -120,17 +140,20 @@ void min_heap_push(struct min_heap *heap, const void = *element, =20 /* Place at the end of data. */ pos =3D heap->nr; - memcpy(data + (pos * func->elem_size), element, func->elem_size); + memcpy(data + (pos * elem_size), element, elem_size); heap->nr++; =20 /* Sift child at pos up. */ for (; pos > 0; pos =3D (pos - 1) / 2) { - child =3D data + (pos * func->elem_size); - parent =3D data + ((pos - 1) / 2) * func->elem_size; + child =3D data + (pos * elem_size); + parent =3D data + ((pos - 1) / 2) * elem_size; if (func->less(parent, child)) break; func->swp(parent, child); } } =20 +#define min_heap_push(_heap, _element, _func) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func) + #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 10ac2db83f14..55930479599b 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3698,13 +3698,14 @@ static void swap_ptr(void *l, void *r) swap(*lp, *rp); } =20 +MIN_HEAP(struct perf_event *, perf_event_min_heap); + static const struct min_heap_callbacks perf_min_heap =3D { - .elem_size =3D sizeof(struct perf_event *), .less =3D perf_less_group_idx, .swp =3D swap_ptr, }; =20 -static void __heap_add(struct min_heap *heap, struct perf_event *event) +static void __heap_add(struct perf_event_min_heap *heap, struct perf_event= *event) { struct perf_event **itrs =3D heap->data; =20 @@ -3738,7 +3739,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, struct perf_cpu_context *cpuctx =3D NULL; /* Space for per CPU and/or any CPU event iterators. */ struct perf_event *itrs[2]; - struct min_heap event_heap; + struct perf_event_min_heap event_heap; struct perf_event **evt; int ret; =20 @@ -3747,7 +3748,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 if (!ctx->task) { cpuctx =3D this_cpu_ptr(&perf_cpu_context); - event_heap =3D (struct min_heap){ + event_heap =3D (struct perf_event_min_heap){ .data =3D cpuctx->heap, .nr =3D 0, .size =3D cpuctx->heap_size, @@ -3760,7 +3761,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, css =3D &cpuctx->cgrp->css; #endif } else { - event_heap =3D (struct min_heap){ + event_heap =3D (struct perf_event_min_heap){ .data =3D itrs, .nr =3D 0, .size =3D ARRAY_SIZE(itrs), diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 7b01b4387cfb..dd5c0fa862ab 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -11,6 +11,8 @@ #include #include =20 +MIN_HEAP(int, min_heap_test); + static __init bool less_than(const void *lhs, const void *rhs) { return *(int *)lhs < *(int *)rhs; @@ -30,7 +32,7 @@ static __init void swap_ints(void *lhs, void *rhs) } =20 static __init int pop_verify_heap(bool min_heap, - struct min_heap *heap, + struct min_heap_test *heap, const struct min_heap_callbacks *funcs) { int *values =3D heap->data; @@ -63,13 +65,12 @@ static __init int test_heapify_all(bool min_heap) { int values[] =3D { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; - struct min_heap heap =3D { + struct min_heap_test heap =3D { .data =3D values, .nr =3D ARRAY_SIZE(values), .size =3D ARRAY_SIZE(values), }; struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -96,13 +97,12 @@ static __init int test_heap_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { + struct min_heap_test heap =3D { .data =3D values, .nr =3D 0, .size =3D ARRAY_SIZE(values), }; struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -129,13 +129,12 @@ static __init int test_heap_pop_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { + struct min_heap_test heap =3D { .data =3D values, .nr =3D 0, .size =3D ARRAY_SIZE(values), }; struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A2C6514D6FF; Thu, 25 Apr 2024 14:18:58 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054740; cv=none; b=G9cHScgwHVoNtrfjtVpV7qgUsxWN9dMl6YQ06+0GDRpNWDabGPiFfQIczmc9202XKdgKvYXnofjyKWeChFZf2WyyT1BxdWOy0K1mFKbaE46YtMNNUJlyFNVZjuqBHQfp1J1tUXtt2b0V7YIZ6SQTslzidWWCNDS2JvmiN4/Ls1s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054740; c=relaxed/simple; bh=b5Qix40IYcfncBwAyPvMRSLFUIF05YVbAb9l7ZjOFyY=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Z0fcDvvDGcXKgM1tJJNvUIJOutct38Q0j06EuZvD4mPb0jy5YjylgF0fJLRENmVOEFRKeNK6mafHZCarkto6aZ4hSLm2P9ZR4m3KSJEYGCSe13lB5GoYF4yTV/XJqNNP8aGBrsmJ9+Yl0Cwz7gKWT3VU5A8mVHQ04RQdOL0ExxM= 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=TZ5RK2Iq; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="TZ5RK2Iq" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-6f0556080a0so52321b3a.2; Thu, 25 Apr 2024 07:18:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054738; x=1714659538; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=BrRuPk05kgYWrNF6DoThYuAvcZ8CXsiyshk2gqZWuIc=; b=TZ5RK2IqGjQX4xM2GZFQwzN4Nh3AfrWz6BRHAOYsFqJ7I7Q0gifpjpZbS+6uV+kFu0 vcKGdGfj4FIkD7mBjlvdmEdyMo3UWz98ymqbeczwyqA/tmzeoJqzyTFdpUYjLQY/jDyS PE1CvtAVz1ujV4AvGFUHzYqM3krwV/zfwa1UaogbzeZdWbFt0Fs9ByH1fryrEeGVSXEt nsjIT1qxnLRZc/3vahcho+0kFfaakI+TZo7qjp0lieHrhYBOv4t0d7VXkBPvnVNat/4N zj9+AVtmMbc7tOYegd31C5D+ieYwrpXzFbXgqVJKJx1IIkFxIUD4jS+KDyPN4xldXIyD M8jg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054738; x=1714659538; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=BrRuPk05kgYWrNF6DoThYuAvcZ8CXsiyshk2gqZWuIc=; b=U5voa94Agee2jy5IWSJnkxWGjJhMEx1II+MWI3eQTL4V4EF0XU6BBARemZ6tQvkZEz 3olhifEBCMPT8siVFdHDopAzSwSrqfdsbrX1iFedOoYT2cgv3w+ASzdxC60oqVj7+qA0 05yelDjQbtByiH4MtlRnwBTHMMYajHFkXREO9fKTXy7uE9rXsMddScs6i/ESLLy6REHj AQwjsizEk8ySebNgujG3xV1scAdYQSQHAqz/idUmeZ/XxQV2pS9HEoWrtXviJ6zU5HGb sUiHfG90EVfAesAFJjjJBz2o1u6ZcrgAJgQUpMB53XggUOLw+BQ5yJX5UW/LPzl16ztd cBlA== X-Forwarded-Encrypted: i=1; AJvYcCV/zb603JWZaLSTxvbtpAYOU25eEUmaFkTi5uubk51lMr4i+nSS2AMe5dbEzCQGOSn7mZcQJ79nGRwdR7lHp6GQsxFqJjIEEz8wZbevtdB5UZMe+ERBX+PjWk+TFhMqc8B47edgzAzSmyU32t4yMLbJOztq8vxvstj1qXpSC61+dWu9b7K/ZTiJxoMqG3PjsrbaCR+Q7tF1PazNJwhB0vVVNKkT1Yf8/qoU5xgr X-Gm-Message-State: AOJu0Yzjs8jZIEzf0ipIQcj2FHyGdfEtiwbzC8/bw0IJHZBriUWr5g1R TNEamY8GE1xShVknzUV46ZUGQNZcq09j/Te5g5qxfxqsTnF8ItqQ X-Google-Smtp-Source: AGHT+IGXAZ+ZP5Nps5IYlgwSWGtymGMbytP6tQx4Ugz1Rte5D4xcYm+mR/lUyzNPTJOSXRVvfLBAGA== X-Received: by 2002:a05:6a00:99a:b0:6ed:cc50:36cd with SMTP id u26-20020a056a00099a00b006edcc5036cdmr6925931pfg.2.1714054737797; Thu, 25 Apr 2024 07:18:57 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.54 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:18:57 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 05/16] lib min_heap: Add min_heap_init() Date: Thu, 25 Apr 2024 22:18:15 +0800 Message-Id: <20240425141826.840077-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_init() for initializing heap with data, nr, and size. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 15 +++++++++++++++ 1 file changed, 15 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 87737cadb9a5..f6b07fb8b2d3 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -38,6 +38,21 @@ struct min_heap_callbacks { void (*swp)(void *lhs, void *rhs); }; =20 +/* Initialize a min-heap. */ +static __always_inline +void __min_heap_init(min_heap_char *heap, void *data, int size) +{ + heap->nr =3D 0; + heap->size =3D size; + if (data) + heap->data =3D data; + else + heap->data =3D heap->preallocated; +} + +#define min_heap_init(_heap, _data, _size) \ + __min_heap_init((min_heap_char *)_heap, _data, _size) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 278B814E2D2; Thu, 25 Apr 2024 14:19:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054744; cv=none; b=YABO8QgALBUoquyJwHh0uRYrV0GauhkE5+EEV6GUPVaD9cyoYGUkNOKT59ucmYf9pLVgKkAJyR+Gf1GtgQgwuzdFsADj51fI4gf7uoJQKjmMd2xA2Bq8zylL77Kx1+fcWRUiRhda0XNqHmTjUJ7iH2BjE/fQ1exj5vb6/l6j5y8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054744; c=relaxed/simple; bh=9tjNBJoFW/M4N3UyhM3SbO6qdcqZWdxAoa5Ri1G9BtM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=adFqn0/IrX1xklOWzagA/SSS7pYn2hwOZf38lJn8fjg2/i+G+XmGBf0P2qY0rCjfDYmIJI/0OwUKTYprYfVwolGBhgmjl8M6qD4+w6OhlM0sGqG/St1lj1YoltFpnVeKWGFspQMshi5o2QgaIM/LyMjX8hkC0sjzBJwSM5kS2j0= 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=nl3eAChe; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="nl3eAChe" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1e825c89532so163495ad.2; Thu, 25 Apr 2024 07:19:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054742; x=1714659542; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=0J0f9A/bhPWWSuBlnbsdq0jeNHFHB9IJoCtvcFhHPOw=; b=nl3eAChe4R2s4eRxYoU6+gkuTEcVMxtF1kkL1wiUHBZRjWmTP8rq2oTwB4ypSlatXs L+T4KdwSFLAcaOYDyOwq2G3O1DIC4a1TjAspUY96KlIZWyZ+XgBHOlPTAWmtvsJ9i4Tm rEhT3zl3TXnQblk0oPMVYJ7lzXAOyoWsmZj6bwTpLVVKaMM2BFCQi5aD0OpSJjG4Pw9f EI8bUSkjrpg++Rx7rGugaBYvo/6RWhKbtcXzZ//OF6oPIeTDD3MZN+1aGyzV+WpgiHRI ZLl4AhkFhiOMKrTiJx+xM3t15QjzDb/AruF+jBs691TjPduEkFzWR7l2MmBUfUPrXlmP UKFg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054742; x=1714659542; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=0J0f9A/bhPWWSuBlnbsdq0jeNHFHB9IJoCtvcFhHPOw=; b=tgxyB6ooTMkihaldLIbr0ZxZl62FEf0JDQwHhINEFiVtn/B9SeU4Mp0CTrejX/JJDi iCJ18dACbj2VHeyyZgczHp9F/5TVV2XxjTFzcNIBPyQytbvQbPl86UU73/ixC9cesF/x uK0TOhDirxzsjGie8JgU4f5crUlEx8EM4zJmO+Rqni1eAuqFnjzos2MGM87tOHEPSWZY slSMBYzHJ3uORt172w3YsDR1YSDBV7oLh8auHuEI3wRhfQsUOBVDVfC7iDcdSB6SAIXw 17Pw+kdxBV5zUH8EtOFqLCrljLtddaYWh0ip/V3ao3nhZwzvlb4QQbGiPGmsRed9+lEj uJ6g== X-Forwarded-Encrypted: i=1; AJvYcCV09xKwtON05ZxTWqdOOmU687n+Fce9/fWJEakfS+gsQ+FBu0F4IbPMIszy9SrHkiwTQ1aV+qYDQRCe7pP2dBFIBsTIvdQAz1UTaxGGWevcnuBaERWz6BrrJpFVgJbwL3nGhdMvGDCq4pQzjVkYm2gPvP5KObqSw76N9lIh3eCpfWJl+onzEZVGSJwfMRFPhKbPl0kZ4+Zl5ajsdyfWMeuEm7u2nEwRCcScaESZ X-Gm-Message-State: AOJu0Yy0sTVZ567CWw+/Swx7Ia4h9PcLoR8DasIb8fUoYMmj9ldJ506E h7L+uaQFPN2subo7jD+PHlMqIxX1ziLUX7eEt1xFOGuILa560T1c X-Google-Smtp-Source: AGHT+IFDcj8+z0jNjqj12s9jll0rXA6fAY20FeZPShgwWxxNRxyTRdtb76w4a8W5EzTpPoYKO1G3kw== X-Received: by 2002:a05:6a20:86a1:b0:1ae:3504:c5e with SMTP id k33-20020a056a2086a100b001ae35040c5emr472761pze.4.1714054742438; Thu, 25 Apr 2024 07:19:02 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.18.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:01 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 06/16] lib min_heap: Add min_heap_peek() Date: Thu, 25 Apr 2024 22:18:16 +0800 Message-Id: <20240425141826.840077-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_peek() function to retrieve a pointer to the smallest element. The pointer is cast to the appropriate type of heap elements. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f6b07fb8b2d3..043de539bf71 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -53,6 +53,16 @@ void __min_heap_init(min_heap_char *heap, void *data, in= t size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init((min_heap_char *)_heap, _data, _size) =20 +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct min_heap_char *heap) +{ + return heap->nr ? heap->data : NULL; +} + +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com [209.85.215.179]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D1F7814E2F7; Thu, 25 Apr 2024 14:19:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.179 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054749; cv=none; b=I9+tUMORKzmabhe/p9Ph/Oi2VNtJKoK0XpxpjK3A4WMrYNHc4KY+0eBwbFOZ57IF4RL6VN8b4bcXkJta2WctcRuuGbBKMoj7xHbSe1l8zADS/FzWeHi1WChkU+BqfFWizzmUxpSG/7M6VXOUkiu+/4K/7WO+vyL8nRGWzKeSrOc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054749; c=relaxed/simple; bh=45DqO8bF1UCi5bfdHVSu4s8AvmjNFknYLPsfVsf4ic0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HayMj6IjByWOcZOoQNPFJuSFuprKt4prEm/u0wBB9MAg9dowiQt/q/m2wKOa0h/x/IKaJ7UnkLv9uvwu/fqM0gBMpXAoJJP5oInR9fBJ/raZ87xWDArp1gV0ncsSnk9jPaCPH9QoOdyC/M6GCzSZBxaOPLVgdqjpbLWukynjEXk= 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=lc2fCxJv; arc=none smtp.client-ip=209.85.215.179 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lc2fCxJv" Received: by mail-pg1-f179.google.com with SMTP id 41be03b00d2f7-5fcf7352086so2144a12.2; Thu, 25 Apr 2024 07:19:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054747; x=1714659547; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vKi/lHC5XFLRvEUBusUUTA5MCG5n2IA6GUULUt/TPRk=; b=lc2fCxJvVSABJ3ZcBbMeIttAn5L5VRz8YvWYgLz3gUU+PU5JAK3Gf5TlY/C/pLkj58 B247lTKa98c7b3UlPrc+CPhttnrAFF2TUSd4eeKN/7Tc5HPuwD0c26IATZFwfPDz3Z+X oOM4ywJVEk0WWZRGsRNGyvVbzy71YXQ0DBT7znc31xlCw1reXhMvdiFOHapvxm3eYwGl ej0/smWSUs28aYroCmeJVz5gL3cJWR2EHaGJhJqCgx2GqqUku/8tYcZE1I5cfh2M8Lyp CiwAuVP0s4KCb2iLt6u1nTk4GUJIyM6VhEYUkJ/E9tTizHdXQUDAW34qQIBaSSsOvcTP YhDA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054747; x=1714659547; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vKi/lHC5XFLRvEUBusUUTA5MCG5n2IA6GUULUt/TPRk=; b=KZcEXTAjikvmsryyjQySHXZHYcHvmPH2LB9fcvaXNKFVir6WqpOtRmEDgvFSF31BHQ ZAiqAk+EICNCu1n9GOjzSL/bgCKaqI4spKy7GexWe1+QWn5fMa8CMCyJ4fv7078BJy1+ CM/vJM3DPMcrLP/NIIwWMqSnaTU1DOGAwv8JIAVH6Ubm19H0rNY1lCcMERQQ1tLWVG8i 7v5Cr3wy5bss3HO10WOnQ212eGT/gffL23TfqDewZD7jUVOLfw7NIT8X+OTyRAvX9b74 IaYd/mS52t0dWJFpb7iSOWwY8Iy9mMpFW+ZXReW26ayH1bkE9dCHiUI5DdCDcdv2Dd4K VJ1g== X-Forwarded-Encrypted: i=1; AJvYcCX/pnlXjxuFANUpSztHEPvwHH4c6ynjETYLGDMiGZ+A0Kac17AnhTSHqBeKrKYtHC1m3RARY+FXi00Q6wJoPD4ajLGMQmBk8mcIwhqEdDTHEgaDZvUJxtpOYJIntudVIuoHufzY+QHNoyc2UI0CS23Gs7ywkiIgS1bjuAQGrm+kiktoXBJEZqXZ3c7amozyde0Mna+3zn7zLG6tr40iK7+L2XvcenaPbgzsygzS X-Gm-Message-State: AOJu0YzntjgFaCSCi/zsHZYGnHbB5bsM6o1sXDrp8EcoVdBWE5v9n+YS cJuX4zO8dn0BK+V2C06zssVz19SCo8l3UGXW0B+I0Dc+H/m3a0Dv X-Google-Smtp-Source: AGHT+IHbFk/N9guTteitPafMYA5bav92kY4dltbvdi7nyN6glbatnc04gQtL0rpO2VJnaOdbsFB4Wg== X-Received: by 2002:a05:6a00:1792:b0:6ec:ee44:17bb with SMTP id s18-20020a056a00179200b006ecee4417bbmr6445854pfg.2.1714054747037; Thu, 25 Apr 2024 07:19:07 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:06 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v4 07/16] lib min_heap: Add min_heap_full() Date: Thu, 25 Apr 2024 22:18:17 +0800 Message-Id: <20240425141826.840077-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_full() which returns a boolean value indicating whether the heap has reached its maximum capacity. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 043de539bf71..d4ec7e749280 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -63,6 +63,16 @@ void *__min_heap_peek(struct min_heap_char *heap) #define min_heap_peek(_heap) \ (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) =20 +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(min_heap_char *heap) +{ + return heap->nr =3D=3D heap->size; +} + +#define min_heap_full(_heap) \ + __min_heap_full((min_heap_char *)_heap) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pj1-f46.google.com (mail-pj1-f46.google.com [209.85.216.46]) (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 5B2F714EC65; Thu, 25 Apr 2024 14:19:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054754; cv=none; b=Pr48R2ZRh7OEYJFl6tzM6ns+q9K2Pa/PsedC4oeUgqljo2741uTObOHMbERd28ddib1Vu0eJrLWDL7/ralGyQeNC3+IoyJJsOleKJwWKFUUThL0cIrg9cBPr2S+FjHQ/N+G+4ghGqM8lgGsm0YwQ67gL1Q4dYPceq5E3YyjWUbk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054754; c=relaxed/simple; bh=00KH2f809CEXeklo+9a6PeGPW2v5ORHI9eZgRU7gLTQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=O0z+JBfCtw8sXoPehDNAjKLM/uXWYYz76l+qD39PknDTDcJYHLJhp4TN63LS+tl/ujd3AYC+hsOmj//gO7xN5KC6s0NyS1z/SBuFNH0il9zvt42zVjS2Bfbb7GiLhgy1OrcyLnYrLlm4d3P0jW3S68JZUxbe7kDcuN/0jnluy4U= 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=hdBShEoW; arc=none smtp.client-ip=209.85.216.46 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="hdBShEoW" Received: by mail-pj1-f46.google.com with SMTP id 98e67ed59e1d1-2ab936993abso275466a91.3; Thu, 25 Apr 2024 07:19:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054751; x=1714659551; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=G2ZkCe3L0WTN4eDU8EG8GGd4mOKJnXr9AQ1ChGE8nos=; b=hdBShEoWirBfAQkgVWGv2Wc7Ja4849iPrNYjP0TMRF5Ow7SDT5/1zY4DvU4KM8Ny8A zYZ4Kyqp4L1vMPvlA12mxmlbCufe8/sLHe+Oraiy3B61O0I2IpY+UP7F0fFgABg34+Yh SRDR3HSP0qAdVUSkcmQlhb+7cByKiE7Y5D/vfeNOuC7f+NjAXMlhtFUOYg47LRgNrkh9 QeRYcf+01x2DTIk6cQO4XYlO5r7eFve1D5wWZXBeQ28iB46D2q5Az8rdVXLyN9p0fbP7 GT/HqTxJYKrJb0V7Am3F5rjb44Af63/2tas0UDQttmPkphWW4olukru6YA8Vybrmlm/F NCaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054752; x=1714659552; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=G2ZkCe3L0WTN4eDU8EG8GGd4mOKJnXr9AQ1ChGE8nos=; b=A7bGqzjw7CEJr1ZyvS+UkxhXJukPqUjnF4dOCnPYwAIkRz2v2R4b5NefO9izT+dnB/ Ka5V6nkNmNrGRDwE1I7JZzYGLF72VeWrcBWly2EKKU7+vzPgFTat+0jsotn+l/syOuQp LyPgUcOrUOhfFD5nf04d5GZ0/zIH8ThFn8sN7Eb2MbX/ybVoJ8S6htgp61iLVsP3TxwN uBc2H19czmWqcfzOmpy9q/CW3+wcwyRAuz0dbdFxxjau55PQKP25SOvEtEFBO4HActmm obU10/wKabDINEAiB+ddlW8du4s75DmeN4r3oVMZX7V8IBJN8cY8ZKqz/VlcoKI6+WLl kR3w== X-Forwarded-Encrypted: i=1; AJvYcCW6DKyGmYp5LWUOsu5mS8PYs/XT6dcnsklICwo7RlTyo6y4dNGy7HIaq2sPzqKWnczhkpjYaeGwZpnLDz3BfnrepVHnHrLvbrm4tpxK4edL0P1EXWHGVg6tL7rqxvbf4ZEZ659AcmoXuA6VqaBxawTo7LJXBYyTtQXfIE23ebwmKCFgHlZxVxgcIqHFE/uyILUzsjAYgsEUTJPHi4hSd7Z8sJOn2cFxsnW44oKE X-Gm-Message-State: AOJu0YzMVuiPAoMQ21Uh8beNkpZ6SZu1UNzoZWZKvkWCqV/xtJ7VbClg Zkn0GndHQpmTwBjfRqcF8ToK20cnOaQLqvSvZVrm6Ayw4FijlyJ/ X-Google-Smtp-Source: AGHT+IFweNbsshiPfGQ561gGsKZAQ2sChKP/jXB6OKLQJfo+kJel1hX0+ot0R9ZMnWRynP0ZAN/e7w== X-Received: by 2002:a62:840b:0:b0:6ea:8604:cb1d with SMTP id k11-20020a62840b000000b006ea8604cb1dmr6892127pfd.0.1714054751538; Thu, 25 Apr 2024 07:19:11 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:11 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 08/16] lib min_heap: Add args for min_heap_callbacks Date: Thu, 25 Apr 2024 22:18:18 +0800 Message-Id: <20240425141826.840077-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add a third parameter 'args' for the 'less' and 'swp' functions in the 'struct min_heap_callbacks'. This additional parameter allows these comparison and swap functions to handle extra arguments when necessary. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- drivers/md/dm-vdo/repair.c | 10 +++---- drivers/md/dm-vdo/slab-depot.c | 9 +++--- include/linux/min_heap.h | 51 +++++++++++++++++----------------- kernel/events/core.c | 10 +++---- lib/test_min_heap.c | 26 ++++++++--------- 5 files changed, 54 insertions(+), 52 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index 48c266fa07b6..c1ed3ae823bf 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -137,7 +137,7 @@ struct repair_completion { * to sort by slot while still ensuring we replay all entries with the sam= e slot in the exact order * as they appeared in the journal. */ -static bool mapping_is_less_than(const void *item1, const void *item2) +static bool mapping_is_less_than(const void *item1, const void *item2, voi= d __always_unused *args) { const struct numbered_block_mapping *mapping1 =3D (const struct numbered_block_mapping *) item1; @@ -156,7 +156,7 @@ static bool mapping_is_less_than(const void *item1, con= st void *item2) return 0; } =20 -static void swap_mappings(void *item1, void *item2) +static void swap_mappings(void *item1, void *item2, void __always_unused *= args) { struct numbered_block_mapping *mapping1 =3D item1; struct numbered_block_mapping *mapping2 =3D item2; @@ -182,8 +182,8 @@ static struct numbered_block_mapping *sort_next_heap_el= ement(struct repair_compl * restore the heap invariant, and return a pointer to the popped element. */ last =3D &repair->entries[--heap->nr]; - swap_mappings(heap->data, last); - min_heapify(heap, 0, &repair_min_heap); + swap_mappings(heap->data, last, NULL); + min_heapify(heap, 0, &repair_min_heap, NULL); return last; } =20 @@ -1123,7 +1123,7 @@ static void recover_block_map(struct vdo_completion *= completion) .nr =3D repair->block_map_entry_count, .size =3D repair->block_map_entry_count, }; - min_heapify_all(&repair->replay_heap, &repair_min_heap); + min_heapify_all(&repair->replay_heap, &repair_min_heap, NULL); =20 vdo_log_info("Replaying %zu recovery entries into block map", repair->block_map_entry_count); diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index f6ae6956f321..2739f5b1f8bd 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3288,7 +3288,8 @@ int vdo_release_block_reference(struct block_allocato= r *allocator, * Thus, the ordering is reversed from the usual sense since min_heap retu= rns smaller elements * before larger ones. */ -static bool slab_status_is_less_than(const void *item1, const void *item2) +static bool slab_status_is_less_than(const void *item1, const void *item2, + void __always_unused *args) { const struct slab_status *info1 =3D item1; const struct slab_status *info2 =3D item2; @@ -3300,7 +3301,7 @@ static bool slab_status_is_less_than(const void *item= 1, const void *item2) return info1->slab_number < info2->slab_number; } =20 -static void swap_slab_statuses(void *item1, void *item2) +static void swap_slab_statuses(void *item1, void *item2, void __always_unu= sed *args) { struct slab_status *info1 =3D item1; struct slab_status *info2 =3D item2; @@ -3525,7 +3526,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator .nr =3D allocator->slab_count, .size =3D allocator->slab_count, }; - min_heapify_all(&heap, &slab_status_min_heap); + min_heapify_all(&heap, &slab_status_min_heap, NULL); =20 while (heap.nr > 0) { bool high_priority; @@ -3533,7 +3534,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator struct slab_journal *journal; =20 current_slab_status =3D slab_statuses[0]; - min_heap_pop(&heap, &slab_status_min_heap); + min_heap_pop(&heap, &slab_status_min_heap, NULL); slab =3D depot->slabs[current_slab_status.slab_number]; =20 if ((depot->load_type =3D=3D VDO_SLAB_DEPOT_REBUILD_LOAD) || diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index d4ec7e749280..9391f7cc9da9 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -34,8 +34,8 @@ typedef MIN_HEAP(char, min_heap_char) min_heap_char; * @swp: Swap elements function. */ struct min_heap_callbacks { - bool (*less)(const void *lhs, const void *rhs); - void (*swp)(void *lhs, void *rhs); + bool (*less)(const void *lhs, const void *rhs, void *args); + void (*swp)(void *lhs, void *rhs, void *args); }; =20 /* Initialize a min-heap. */ @@ -76,7 +76,7 @@ bool __min_heap_full(min_heap_char *heap) /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *left, *right; void *data =3D heap->data; @@ -89,7 +89,7 @@ void __min_heapify(min_heap_char *heap, int pos, size_t e= lem_size, break; left =3D data + (i * 2 + 1) * elem_size; right =3D data + (i * 2 + 2) * elem_size; - i =3D func->less(left, right) ? i * 2 + 1 : i * 2 + 2; + i =3D func->less(left, right, args) ? i * 2 + 1 : i * 2 + 2; } =20 /* Special case for the last leaf with no sibling. */ @@ -97,38 +97,38 @@ void __min_heapify(min_heap_char *heap, int pos, size_t= elem_size, i =3D i * 2 + 1; =20 /* Backtrack to the correct location. */ - while (i !=3D pos && func->less(root, data + i * elem_size)) + while (i !=3D pos && func->less(root, data + i * elem_size, args)) i =3D (i - 1) / 2; =20 /* Shift the element into its correct place. */ j =3D i; while (i !=3D pos) { i =3D (i - 1) / 2; - func->swp(data + i * elem_size, data + j * elem_size); + func->swp(data + i * elem_size, data + j * elem_size, args); } } =20 -#define min_heapify(_heap, _pos, _func) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc) +#define min_heapify(_heap, _pos, _func, _args) \ + __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) =20 /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heapify(heap, i, elem_size, func); + __min_heapify(heap, i, elem_size, func, args); } =20 -#define min_heapify_all(_heap, _func) \ - __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c) +#define min_heapify_all(_heap, _func, _args) \ + __min_heapify_all((min_heap_char *)_heap, __minheap_obj_size(_heap), _fun= c, _args) =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline void __min_heap_pop(min_heap_char *heap, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 @@ -138,11 +138,11 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_= size, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop(_heap, _func) \ - __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func) +#define min_heap_pop(_heap, _func, _args) \ + __min_heap_pop((min_heap_char *)_heap, __minheap_obj_size(_heap), _func, = _args) =20 /* * Remove the minimum element and then push the given element. The @@ -152,19 +152,20 @@ void __min_heap_pop(min_heap_char *heap, size_t elem_= size, static __always_inline void __min_heap_pop_push(min_heap_char *heap, const void *element, size_t elem_size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, + void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func); + __min_heapify(heap, 0, elem_size, func, args); } =20 -#define min_heap_pop_push(_heap, _element, _func) \ - __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), _func) +#define min_heap_pop_push(_heap, _element, _func, _args) \ + __min_heap_pop_push((min_heap_char *)_heap, _element, __minheap_obj_size(= _heap), _func, _args) =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline void __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, - const struct min_heap_callbacks *func) + const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; void *child, *parent; @@ -182,13 +183,13 @@ void __min_heap_push(min_heap_char *heap, const void = *element, size_t elem_size, for (; pos > 0; pos =3D (pos - 1) / 2) { child =3D data + (pos * elem_size); parent =3D data + ((pos - 1) / 2) * elem_size; - if (func->less(parent, child)) + if (func->less(parent, child, args)) break; - func->swp(parent, child); + func->swp(parent, child, args); } } =20 -#define min_heap_push(_heap, _element, _func) \ - __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func) +#define min_heap_push(_heap, _element, _func, _args) \ + __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) =20 #endif /* _LINUX_MIN_HEAP_H */ diff --git a/kernel/events/core.c b/kernel/events/core.c index 55930479599b..dfd7b5748cbb 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3683,7 +3683,7 @@ void __perf_event_task_sched_out(struct task_struct *= task, perf_cgroup_switch(next); } =20 -static bool perf_less_group_idx(const void *l, const void *r) +static bool perf_less_group_idx(const void *l, const void *r, void __alway= s_unused *args) { const struct perf_event *le =3D *(const struct perf_event **)l; const struct perf_event *re =3D *(const struct perf_event **)r; @@ -3691,7 +3691,7 @@ static bool perf_less_group_idx(const void *l, const = void *r) return le->group_index < re->group_index; } =20 -static void swap_ptr(void *l, void *r) +static void swap_ptr(void *l, void *r, void __always_unused *args) { void **lp =3D l, **rp =3D r; =20 @@ -3783,7 +3783,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } =20 - min_heapify_all(&event_heap, &perf_min_heap); + min_heapify_all(&event_heap, &perf_min_heap, NULL); =20 while (event_heap.nr) { ret =3D func(*evt, data); @@ -3792,9 +3792,9 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap); + min_heapify(&event_heap, 0, &perf_min_heap, NULL); else - min_heap_pop(&event_heap, &perf_min_heap); + min_heap_pop(&event_heap, &perf_min_heap, NULL); } =20 return 0; diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index dd5c0fa862ab..0b5037b4bd68 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -13,17 +13,17 @@ =20 MIN_HEAP(int, min_heap_test); =20 -static __init bool less_than(const void *lhs, const void *rhs) +static __init bool less_than(const void *lhs, const void *rhs, void __alwa= ys_unused *args) { return *(int *)lhs < *(int *)rhs; } =20 -static __init bool greater_than(const void *lhs, const void *rhs) +static __init bool greater_than(const void *lhs, const void *rhs, void __a= lways_unused *args) { return *(int *)lhs > *(int *)rhs; } =20 -static __init void swap_ints(void *lhs, void *rhs) +static __init void swap_ints(void *lhs, void *rhs, void __always_unused *a= rgs) { int temp =3D *(int *)lhs; =20 @@ -40,7 +40,7 @@ static __init int pop_verify_heap(bool min_heap, int last; =20 last =3D values[0]; - min_heap_pop(heap, funcs); + min_heap_pop(heap, funcs, NULL); while (heap->nr > 0) { if (min_heap) { if (last > values[0]) { @@ -56,7 +56,7 @@ static __init int pop_verify_heap(bool min_heap, } } last =3D values[0]; - min_heap_pop(heap, funcs); + min_heap_pop(heap, funcs, NULL); } return err; } @@ -77,7 +77,7 @@ static __init int test_heapify_all(bool min_heap) int i, err; =20 /* Test with known set of values. */ - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 =20 @@ -86,7 +86,7 @@ static __init int test_heapify_all(bool min_heap) for (i =3D 0; i < heap.nr; i++) values[i] =3D get_random_u32(); =20 - min_heapify_all(&heap, &funcs); + min_heapify_all(&heap, &funcs, NULL); err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 return err; @@ -110,14 +110,14 @@ static __init int test_heap_push(bool min_heap) =20 /* Test with known set of values copied from data. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &data[i], &funcs); + min_heap_push(&heap, &data[i], &funcs, NULL); =20 err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 /* Test with randomly generated values. */ while (heap.nr < heap.size) { temp =3D get_random_u32(); - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); } err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 @@ -143,22 +143,22 @@ static __init int test_heap_pop_push(bool min_heap) /* Fill values with data to pop and replace. */ temp =3D min_heap ? 0x80000000 : 0x7FFFFFFF; for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); =20 /* Test with known set of values copied from data. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_pop_push(&heap, &data[i], &funcs); + min_heap_pop_push(&heap, &data[i], &funcs, NULL); =20 err =3D pop_verify_heap(min_heap, &heap, &funcs); =20 heap.nr =3D 0; for (i =3D 0; i < ARRAY_SIZE(data); i++) - min_heap_push(&heap, &temp, &funcs); + min_heap_push(&heap, &temp, &funcs, NULL); =20 /* Test with randomly generated values. */ for (i =3D 0; i < ARRAY_SIZE(data); i++) { temp =3D get_random_u32(); - min_heap_pop_push(&heap, &temp, &funcs); + min_heap_pop_push(&heap, &temp, &funcs, NULL); } err +=3D pop_verify_heap(min_heap, &heap, &funcs); =20 --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pf1-f181.google.com (mail-pf1-f181.google.com [209.85.210.181]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C577514EC6D; Thu, 25 Apr 2024 14:19:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.181 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054758; cv=none; b=l7m1pZCYGhp5SiBlictCoKgQoia6mh4qAJqbe76CtAn6mVLiP7ROYX/0eVs9nXu3KHXjcqRB4R0P0J7/1ugLxvyNlEu5FeIC8UAWRfHX6xwE8ReP2/KZ1VaJjNGRd39cWO6S7k4wKNuRmAXf6dbquqIlFZoz3zM6F2RvG4gLACI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054758; c=relaxed/simple; bh=4BdmZ42eGYqkHh7DqsaJJxnA5TQhEtJiFDSi25byrow=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=R3wDVdDbsdjUQS73glUsc2nK7WR8afCxh4cvPxnt9wLPVIM2LK01N0MYa5FfudezzWT+MjZlTiEzOc8+WnOhUVS58KYsvX1aOeLinmGpzt/KjV2DuGmhv9SWjWvgxKy/PJCq5hiJEZyUby06i1xyL9FY/myRkYoZ2g1D4SCNeqY= 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=dJrIm4Rb; arc=none smtp.client-ip=209.85.210.181 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="dJrIm4Rb" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-6f055602a7aso61025b3a.2; Thu, 25 Apr 2024 07:19:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054756; x=1714659556; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=zYBPuzAS4rfB8ctDvp2HjPAauLmNAXnRoi+vJxjVmnw=; b=dJrIm4Rbp2MsCnm3P4uO8Trt4y+/HyVxf76Tg0Pu3D2G/4K2xxXqntI+iSnOsbEXlV 3k/26TTa4ftjDl2bTCEyFRcaJbODhK1DARU5zPpAsWbQVPaQcopY2y8A3j2OW3VG3loc nG1U7kzwypr5PxbWE40BFBGQ8gWdDNV9C4epCFqLehG710FIW1G7EBxzxK2KazfvdNU/ CTXYFWUUIooA55D5mkoPTl7FlJP3+cWKSa3G22AWgWRL9q2Is7d/kkSJz6xP0t+Zms5y 6l18VOK2AnqBmkIeBpN0Du+F8mOvYW6V9FmurQel6NLlFRaghoeWC1X0BeXxqMh6WEM6 ubLQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054756; x=1714659556; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=zYBPuzAS4rfB8ctDvp2HjPAauLmNAXnRoi+vJxjVmnw=; b=YtrCKeoq6dyxdFTYNPTqkzlBQh8NaH/XvvLen2cbTAa2rchA0qe+7wqSaEiC/pwm8B OfDYbUhyzoYm8xi4eEp3S+MekgSt58Q1cZgcGQ6DlGkX3FqA4/jtBndJOUOuSaBeWpcz tA9jKPqkErLQOVx8dRj6gMyz3xNySP3igu52yEbsMmFaYyrJ7JexMFtvQDd4EyYcpvBo eWVC1I1JOxs8YLRxpTZxk+Qpe3OEOtqJG5B53gE+yBYKO2ickOSCnPmNvfW82IOufGbd 5VCX54dNbFO3ikq1bwuz+NRihn2TdRhuJaX7g7WR94vn+IeNuQ04uGUrp9c4g39MmJ2m 8lDQ== X-Forwarded-Encrypted: i=1; AJvYcCV/xGNS+1Pzlfj+RAVReLOwdQ500xrymY7BPFL6M1LQ/qs5BObN9GTJU5i2Dv32VIveEDXGGHSVPppW2NU9LlM6JKUGuYFbixizvUcTCTpKw3DBSW3L22xFW+uV6YpkbqfTzDFpm/AfWvjE9ySsu00l6lO1I/C88qOEE1yrnMBlvDclqr37qnSwJI8z5Wuzns53P9+VJMZGCdpGdaSH2AiIzyd+/HouhMXU/9SM X-Gm-Message-State: AOJu0Yzi12XNUnRohA+lxiuyGMnLc9YVy3Rk5fDRL4gS1YASP5wdX9at 3ubHurXO7aP2lEfQCQSMWi794CeHkC2dftGTpNmwUKqZ4CALXVkrGCanUkGI X-Google-Smtp-Source: AGHT+IHCs2mP2PBWPDpj/ZpcI0qR5WUF5wl8AmiCcNh9Yd7tWrXz9C1cdR5glM/73f83lz2U/XWXhQ== X-Received: by 2002:a05:6a20:a3a0:b0:1ad:cdc1:a418 with SMTP id w32-20020a056a20a3a000b001adcdc1a418mr876921pzk.5.1714054756137; Thu, 25 Apr 2024 07:19:16 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:15 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 09/16] lib min_heap: Add min_heap_sift_up() Date: Thu, 25 Apr 2024 22:18:19 +0800 Message-Id: <20240425141826.840077-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_sift_up() to sift up the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 9391f7cc9da9..201f59cb3558 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_= t elem_size, #define min_heapify(_heap, _pos, _func, _args) \ __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) =20 +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + size_t parent; + + while (idx) { + parent =3D (idx - 1) / 2; + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + break; + func->swp(data + parent * elem_size, data + idx * elem_size, args); + idx =3D parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _id= x, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 894EC14A4DC; Thu, 25 Apr 2024 14:19:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054763; cv=none; b=mk9YHO0qnzcr0SZRtWMu1m3gTC0xOHaDWKTTrddtL24YtqNx03lES+EDtI2wb3XMaheoKT4T6tqfE0zkSnZeiu5YqIuLIDvFpQgjEdmqKVbIuCcte1xtGBeJuOOs9BBiVOpoCsWNDoQ1cgdi44rrEmPu24dQwRlKy7q2Yi65DUo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054763; c=relaxed/simple; bh=tJ7jRhX3JE0weNjdlxeuKf0kQodyCJ3KEJ6yl72FH+o=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=GxmmSLZjYvj7fZLvpDoqMpciubf0GlS0td3/Ruf16d0XSQNe/IhaTzChh+uAs9/x38w2f7qI5d4FDXXXF43sw8FWHSAM4bCTa0rXdTAveVPefs6iJIa1dx3YiUzHE45Lo4do1aLjL10FJMxAHJN1xfQuxNX7hV8szj+caqJovK8= 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=BlDx4JO+; arc=none smtp.client-ip=209.85.214.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="BlDx4JO+" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-1ead2c5f3f0so109905ad.0; Thu, 25 Apr 2024 07:19:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054761; x=1714659561; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=5hB1FNdY/u34MXPrD/nJEK2rp5x/YUSa36ZwVtrLJjE=; b=BlDx4JO+BNw8M0T8OOVyUrOWxVudQVcBA1GSqLNcRMktvMhBPlLAO7zWiXcy57mRq8 vxLIGKVLptjuwWPrcxa1qZiqIul/1wlkbEf2D6D1alAOdboH8VryGk149HpbXzubeQAR PKuwvkq/8b+wYAFIJ+UNfCykMLWUZkHQB71U4lh2ypU30yvm5u0gQCxIi/t/SBIYmcX1 s6gaRHgKFJCUlj5bxthVZXNK2Hp1QpKdJvnTSrjcWhYWP/j+iz+Si00bdqrCbxY8Xobt Me1icMfQLuICmTbftVfVHiWXORStj/uhsEVqClM0k8iXpyFMVvJjc9m/NMv7YDxQyyRc cRRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054761; x=1714659561; 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=5hB1FNdY/u34MXPrD/nJEK2rp5x/YUSa36ZwVtrLJjE=; b=Z0SWJmLXVgGWsTywzW1QOFY1EDtQOYVpizJ3LYGWIY98AzErz4mjFXqOlcG9YsihsK WywVX4BgWeUrdhfB10o3dEEHWCajgYONkKWHsXf183iwb3GL9RGfLR1FxvUjL8tonDoR DQVeqk2Z395k3RwEAMlH00m6vqNaRQnJ7zu7068pONCnhBxKszDwfuuI6Ed0CxpCCr4I 97b5124uiUsBEyibCK91KjSTVRNsOU5Y/n0zq/xb1Os9OQMX0x3jpx3AY55dqSlWHEb2 2vuJ8QlpCGO0Rno9IuZwFKYD2XHWcMzFfE8BTw6Urj3pVKXJEovTsnWwGIWUtoKioLiX ju0Q== X-Forwarded-Encrypted: i=1; AJvYcCWCIr2U1AGDwwQt9r4V/yR+wx5edgIhRgoQ76V37vHTUhn6CmseozLjJj3fUZW0+jk1dsoYcXLabgiMM1iVgVuwo9Cx9BGFxrckuBWfiit0952iixsbK3hpyfi36OoVngGfJZbGZybaw49r3pUda8my2odPkUWVrhn8LqYwMvtKl9Cr63AyVq0V4jUxN5zA2f/BDbcJeH+PYmY5Nh0sV2evAfi2uJBpFZLQw9FV X-Gm-Message-State: AOJu0YyJu/a1AV0iiPiKtMRQa2IGvlb01mKpI8m3rB0U/4Ju9WTjqtQn PJKd7Rk3u5m06jIcHbC3J0aW7ROVfSy05CLztxRhQCgWsnKEQ7GE X-Google-Smtp-Source: AGHT+IGPJ9qEIg5OOvnVBaHQxsAeXsNBJGcq6V1gONZPwX1npRJHljeenUCpAetAla6YwfnwY4G9iQ== X-Received: by 2002:a05:6a20:12cb:b0:1ad:8df7:6127 with SMTP id v11-20020a056a2012cb00b001ad8df76127mr4575398pzg.0.1714054760834; Thu, 25 Apr 2024 07:19:20 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:20 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 10/16] lib min_heap: Add min_heap_del() Date: Thu, 25 Apr 2024 22:18:20 +0800 Message-Id: <20240425141826.840077-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_del() to delete the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- Changes in v4: - Replace memcpy() with func->swp() in heap_del() due to issues with set_backpointer in bcachefs when setting idx. include/linux/min_heap.h | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 201f59cb3558..c94f9d303205 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -212,4 +212,28 @@ void __min_heap_push(min_heap_char *heap, const void *= element, size_t elem_size, #define min_heap_push(_heap, _element, _func, _args) \ __min_heap_push((min_heap_char *)_heap, _element, __minheap_obj_size(_hea= p), _func, _args) =20 +/* Remove ith element from the heap, O(log2(nr)). */ +static __always_inline +bool __min_heap_del(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + + if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) + return false; + + /* Place last element at the root (position 0) and then sift down. */ + heap->nr--; + if (idx =3D=3D heap->nr) + return true; + func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); + __min_heap_sift_up(heap, elem_size, idx, func, args); + __min_heapify(heap, idx, elem_size, func, args); + + return true; +} + +#define min_heap_del(_heap, _idx, _func, _args) \ + __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _= func, _args) + #endif /* _LINUX_MIN_HEAP_H */ --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pf1-f170.google.com (mail-pf1-f170.google.com [209.85.210.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 762DD152166; Thu, 25 Apr 2024 14:19:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054767; cv=none; b=L5tlKRkjTwkcPOLKQ0nLPXlC0H7Y3S1H0xjCf24JfPbbDEMKfBNYOk+7UPoQqlPXR31ylCbv4dSsVPq2ia4wdLt3Sm62Y8JimDy/4PkPGRirUEDPeHDdrtQ4gllP70qFBTu+KK6f/XTvqkXNBcaeC6fJ13iTDmYe7tBPwgpkGso= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054767; c=relaxed/simple; bh=PtYRw7GsavxbiDyoXt/jBI3j/cXrR77rkoPNcWtU+qo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=sHjzfk8Kk7rFQXRZalrNe5kG1mJhSwekArvBaYIu+4fKu4xtkW4e7kzn57Ms/b85AdEXLeBBfpOmZ4olmMx6PFDPpjrLcq/Ii0ixvDGp3thoL1Kj7Fnloix//FOmO/H4qHqkkb7P1PmWyzWHM7HOv5TioIVBigJ8uonQgNYGt/o= 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=LVJZjucF; arc=none smtp.client-ip=209.85.210.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="LVJZjucF" Received: by mail-pf1-f170.google.com with SMTP id d2e1a72fcca58-6f055602a7bso56763b3a.3; Thu, 25 Apr 2024 07:19:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054766; x=1714659566; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=7EphJEt3KUebjz7mwKYHv22rhUher1RghPLhkx5N+uY=; b=LVJZjucFECV1tPH9qc0cv16djppOMXX9Mz6l9jG0eihKfBL2uGl0GNU81eLuTtkPVt SLbcgelqKMGAtgQSeg9im8Z1jbXLWhTxmypo271rMTmCHTxFMq+qm2ZdHByoKUZTUwuO 2fcOJ3yZfFYvKW3U7ANzl++2TUWXwEUXhiri8CrSfX7aFju2YbP9aMUYIeZnqjfz5OJ1 1x/E1xDQi0LHiKjaXZ4v5a+Rp1HIlMqMR1A7Tkf5FpZBhTyboEi/4fEzHyTVgt5VIL45 1nKBv2gWOnpsFLzN6C88NvY0kRv/swPJqSwVPORHLlGgekH9CfGx6ARdZN4fiR+fHTYK 25lw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054766; x=1714659566; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=7EphJEt3KUebjz7mwKYHv22rhUher1RghPLhkx5N+uY=; b=vrEl1wkRrpVe4CKdCXgDv7iAvDlQ3iOd6Fw6EmTsef8zYDGXun3jHruEDLY5OHHIov vP+nFeH9Catjpo8uWjfKQHvMBTJ/xN1QQIl/utbQtTXJ/d23Oi6Kf40nFJVUgH1SBFIa gaCaacnUUYtGuF7j87ytrHb5aL5iUoQ8dp+OePgUx5458xevQ4Bg4GDJanhF5pfbSbXH P43fGtwm9gOv/owAydhtgWYtxhw2hJGk6/7DN11E7wKZJ/SXyrhoOgvxoKe/6/nr5jSb CboGxM2KeSQjvX4scxrnJ5GPgRRfjfmHq2HEaMoy84Onoo/UFNB9e1X+JCLu0SqiMAMJ cpEg== X-Forwarded-Encrypted: i=1; AJvYcCWlYuJGMZDQwBkLl3HX+nHS6MvXgSSkC29g2M37hc087klNV1tO3TjLBTo501EUXiGpy7pBXG2sgg90/okzaKvg7ehTDYyOjOCza4kt/fzoP4IP9Zcy/PQ97BFPGDdW00Ppwuai1nLwOhISqBtIWdedGE/7VrBS9/Etu/2BidFO+MPtTRUkwbVJ92oAbPCoJBgpdlKQpRKIHUUkJzYv1rVjdwQRsmoaRervXxYR X-Gm-Message-State: AOJu0Yz3Kegjn1hvKTjuyoxcWvReZXHLw8oYdGWMfaJFqzzOEUvx4XhW emhsNgLBp9KXaXoIAbYBn73vHULODaRBCYAGxfH/As+mTGla+Bea X-Google-Smtp-Source: AGHT+IH3qvR8DEaNgNGZh5Udg5FgEG5PQHj+EW7uZq/SkmKUq2NA7t4laHBCtISEgyrlq7ewHbhqhA== X-Received: by 2002:a05:6a20:158c:b0:1aa:68c4:3271 with SMTP id h12-20020a056a20158c00b001aa68c43271mr7357457pzj.3.1714054765579; Thu, 25 Apr 2024 07:19:25 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.22 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:25 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 11/16] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Date: Thu, 25 Apr 2024 22:18:21 +0800 Message-Id: <20240425141826.840077-12-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Modify the min_heap_push() and min_heap_pop() to return a boolean value. They now return false when the operation fails and true when it succeeds. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index c94f9d303205..2d080f85ad0d 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -147,18 +147,20 @@ void __min_heapify_all(min_heap_char *heap, size_t el= em_size, =20 /* Remove minimum element from the heap, O(log2(nr)). */ static __always_inline -void __min_heap_pop(min_heap_char *heap, size_t elem_size, +bool __min_heap_pop(min_heap_char *heap, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; =20 if (WARN_ONCE(heap->nr <=3D 0, "Popping an empty heap")) - return; + return false; =20 /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); __min_heapify(heap, 0, elem_size, func, args); + + return true; } =20 #define min_heap_pop(_heap, _func, _args) \ @@ -184,7 +186,7 @@ void __min_heap_pop_push(min_heap_char *heap, =20 /* Push an element on to the heap, O(log2(nr)). */ static __always_inline -void __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, +bool __min_heap_push(min_heap_char *heap, const void *element, size_t elem= _size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; @@ -192,7 +194,7 @@ void __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, int pos; =20 if (WARN_ONCE(heap->nr >=3D heap->size, "Pushing on a full heap")) - return; + return false; =20 /* Place at the end of data. */ pos =3D heap->nr; @@ -207,6 +209,8 @@ void __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, break; func->swp(parent, child, args); } + + return true; } =20 #define min_heap_push(_heap, _element, _func, _args) \ --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 55AD4152166; Thu, 25 Apr 2024 14:19:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054773; cv=none; b=axgAZc+7ehqdCq8/qupa8LpKOWekW6CpBjbCjwmm7vMVKgiQ12UuDuZwcCcT6eamEapE0EjmEn8XhJsOG2WR04YYpRQJx9/LB26KCRcIHDG3wJYQ752LA+BqZiwr63jQuvKSbjCZYHfT8wJ93hCfZmm2ftd7YOisBcQ+05HStM4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054773; c=relaxed/simple; bh=5dPWx/XCuPpHn/JbswVAX4unB6CSgL3H/O4srtepiqI=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=DmZTnA4PmGv1tfvnjEYQNm85cV512pNSv05kfMO4BESlNzIt4QYyc+fHbzdPBpYA5IvHIz9xOUeWhE5krBGNvyQ1DP3j3s3gTdQX9wy1J5jm/l+6bRhPWc8xrelKlMo0zItm+cNuHV3S867kdJNwDJugM6OuyNCs2Sor40OD3p8= 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=TF+96Ggf; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="TF+96Ggf" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1e7af7eb4ccso508015ad.1; Thu, 25 Apr 2024 07:19:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054770; x=1714659570; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=qStH8dSNcDcItb1wA2JtX3YjxyreJTEee2fjqsXU5t0=; b=TF+96Ggfs/nQLY9BFcdcFWvzS2g2h6VfGzgiD0hbPKVxGLteihV4N0rUrvV1QUYM7U Ro13DP7DglIANAUQ2KzLYhMFzQtSFJ5ejvi48XbIZtAtTajvBjwG37Kv3fPvQHCT3HgC H0xI9Fnambpq0q8C8Akcr7VVB9VPXOw71p5M17n85Xtx5y1nyGSyKU79sT2d4hMv/Wj3 2ZS6YMIR06ExCGjF7ym+QU5t+hbEe8mUHoPzWMJ8poi75N3WgVMwjhXtx8OyBNhIzkQW nnbQrn2oumZARraU2w/9YOfKMef3o42ZFf9PPKGHG9tm6Nojd8jFiecLm1MeKUhf0Irx pxjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054770; x=1714659570; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=qStH8dSNcDcItb1wA2JtX3YjxyreJTEee2fjqsXU5t0=; b=XCf9PPsBxKRxzjzUxK0uU7AHjKITVUqmrSgN4nQjQaSsB3cZU4evVnocvf7ZCfbhRy rStSBO7tVRjJpFyKVwwEPwL0EndfcHvoRvasLatv3IHXFNiU2Q4ZM7TpNF1K5GKVAG4m j/rQZvq2P1viyesATX/tkL2lXr0XmQIxf4OsEBCHHkYJMfywGp8fgXK/FXav/JTkDMti U+WUdAVTwfSL+maTkco1giXpZL1WRcItJDjpvadU1iuuZpQnw+nfX7TgFsrmCfiUG4Yh OXKCFUVyq8KRpJPHOt20HqpLVyfoq1YCT7YufdlnCLBtg/Y01eXSd0JglZNaF5poRZzu awiA== X-Forwarded-Encrypted: i=1; AJvYcCUAPnJduhCnUhalWMPUQ67l1ofpeOhf2kebRRPCGuIewaXnuvnBB3aAMiOyLyApK5zmvgqWW2AQPfyKlboHAmoT/E5E96vKEqV6ZoZyQquS3UhvWwI9Q+mq/+eYJ3sPmkxjkP+VeHD4F7JDAaPwIYZJ0xk/HIc2Vvre6RnY7CB1I84OFnMFEL8cRAcrBrPdyeBAAzn5Kvqqi3T+caauNc/+X1A1NEXWFH1gtYPU X-Gm-Message-State: AOJu0YxZlXqcsaNeJ7ZEfbbXmX0oi2/WStLmxOUrAAnA9ojhkFT/FSMD Il5cxsqgNQJn7VI6e9/7t6aBcAtwwSApC/SxSCSSFA3GVampHvig X-Google-Smtp-Source: AGHT+IEGyEh1HXQB5D75l1NpiLH+qNvawfkhTxq9Yiz7LQYh6fcgF54wNcIjLptvO8b3R2IbMMWmHA== X-Received: by 2002:a05:6a00:718b:b0:6ea:df65:ff80 with SMTP id li11-20020a056a00718b00b006eadf65ff80mr6441795pfb.3.1714054770223; Thu, 25 Apr 2024 07:19:30 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:29 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 12/16] lib min_heap: Rename min_heapify() to min_heap_sift_down() Date: Thu, 25 Apr 2024 22:18:22 +0800 Message-Id: <20240425141826.840077-13-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" After adding min_heap_sift_up(), the naming convention has been adjusted to maintain consistency with the min_heap_sift_up(). Consequently, min_heapify() has been renamed to min_heap_sift_down(). Link: https://lkml.kernel.org/CAP-5=3DfVcBAxt8Mw72=3DNCJPRJfjDaJcqk4rjbadgo= uAEAHz_q1A@mail.gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- drivers/md/dm-vdo/repair.c | 2 +- include/linux/min_heap.h | 14 +++++++------- kernel/events/core.c | 2 +- 3 files changed, 9 insertions(+), 9 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index c1ed3ae823bf..941ac9eda8ca 100644 --- a/drivers/md/dm-vdo/repair.c +++ b/drivers/md/dm-vdo/repair.c @@ -183,7 +183,7 @@ static struct numbered_block_mapping *sort_next_heap_el= ement(struct repair_compl */ last =3D &repair->entries[--heap->nr]; swap_mappings(heap->data, last, NULL); - min_heapify(heap, 0, &repair_min_heap, NULL); + min_heap_sift_down(heap, 0, &repair_min_heap, NULL); return last; } =20 diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 2d080f85ad0d..f907c694e852 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -75,7 +75,7 @@ bool __min_heap_full(min_heap_char *heap) =20 /* Sift the element at pos down the heap. */ static __always_inline -void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, +void __min_heap_sift_down(min_heap_char *heap, int pos, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *left, *right; @@ -108,8 +108,8 @@ void __min_heapify(min_heap_char *heap, int pos, size_t= elem_size, } } =20 -#define min_heapify(_heap, _pos, _func, _args) \ - __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) +#define min_heap_sift_down(_heap, _pos, _func, _args) \ + __min_heap_sift_down((min_heap_char *)_heap, _pos, __minheap_obj_size(_he= ap), _func, _args) =20 /* Sift up ith element from the heap, O(log2(nr)). */ static __always_inline @@ -139,7 +139,7 @@ void __min_heapify_all(min_heap_char *heap, size_t elem= _size, int i; =20 for (i =3D heap->nr / 2 - 1; i >=3D 0; i--) - __min_heapify(heap, i, elem_size, func, args); + __min_heap_sift_down(heap, i, elem_size, func, args); } =20 #define min_heapify_all(_heap, _func, _args) \ @@ -158,7 +158,7 @@ bool __min_heap_pop(min_heap_char *heap, size_t elem_si= ze, /* Place last element at the root (position 0) and then sift down. */ heap->nr--; memcpy(data, data + (heap->nr * elem_size), elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); =20 return true; } @@ -178,7 +178,7 @@ void __min_heap_pop_push(min_heap_char *heap, void *args) { memcpy(heap->data, element, elem_size); - __min_heapify(heap, 0, elem_size, func, args); + __min_heap_sift_down(heap, 0, elem_size, func, args); } =20 #define min_heap_pop_push(_heap, _element, _func, _args) \ @@ -232,7 +232,7 @@ bool __min_heap_del(min_heap_char *heap, size_t elem_si= ze, size_t idx, return true; func->swp(data + (idx * elem_size), data + (heap->nr * elem_size), args); __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_heapify(heap, idx, elem_size, func, args); + __min_heap_sift_down(heap, idx, elem_size, func, args); =20 return true; } diff --git a/kernel/events/core.c b/kernel/events/core.c index dfd7b5748cbb..82f329c8caea 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3792,7 +3792,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap, NULL); + min_heap_sift_down(&event_heap, 0, &perf_min_heap, NULL); else min_heap_pop(&event_heap, &perf_min_heap, NULL); } --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pj1-f42.google.com (mail-pj1-f42.google.com [209.85.216.42]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2733F14AD22; Thu, 25 Apr 2024 14:19:35 +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=1714054778; cv=none; b=dSOfh1OMFeb4TWQBJF19aL2thgCxkgX0Ym7Kts/h6thCblZYkYdN2PCgQIkudRhShnc/qLFAkvAEjX3LLg7WlPUr6PgPkAh+yvgqXWhbo7mQe910m77RFwGubl0EsqIAlfKrNLC75r1heaW0uzTPDv7QIN6Atj7Gh+sFX0ISZsg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054778; c=relaxed/simple; bh=T8bV4BnctbyRNeSPAOZwi+czorsklhrFY1lqJqcqucQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=plAUO/V/l1cMWC27jxSrqhymDnG1uLeVTbSdaXncXdnVK2BP4ca4lwoBWbdHEUA++QKAkKu3ma9kHRF/zPwPlgRlfW/xLVerLNeIysWyLJ+Adi3OhoZTTaGd7Od6sscEGmLuA7i7nbJmdmUlgU+cHBVFGtX9CfbS8IIrIL6MvFM= 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=ZQ0CfyZH; 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="ZQ0CfyZH" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2af71daeec1so280007a91.0; Thu, 25 Apr 2024 07:19:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054775; x=1714659575; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8RRhCYNi4OEA45vqDvulwCxtOU91F7rHv4uIJxFLbAA=; b=ZQ0CfyZHjNknkxIgEEJvPpJbulMfVTC1E0QYQlYrR5iW4Zci6ZtLUpfsvygaltYCcw ScXidVa+iL3o/XqOZ3AcsFBw0RmfTqSIotT0CzyhtyLcPTEUAFlKRI0dzLDPc2NENFcU /ng73mVQe9j1OVV4pqPE61e866b8apHP9GCaMB7VcPllC19A/5eoREZuc/E2e3BBEKvJ 366xdAI9BS0tMcyVXJMIDMOyCul0+F0yoP5PLjvmhG9/BhcCeLFWahUiDL8QOY8eGxN2 icMP0ZJ70hWSQ0oeyuOfRKNQwH2AvcHVu2zV6kR0Wmb22NB+DPnzyO5KgBaJ0EReImJg 92zA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054775; x=1714659575; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8RRhCYNi4OEA45vqDvulwCxtOU91F7rHv4uIJxFLbAA=; b=A33uGoEJBYdeT8U1x+PfozOTHBHHEJ1bd8F12MPzVteQBdfdj7sQrORDbySU872+Om Kt/6sp3Nb78Vlwmz6uF/2SNViKdDU3zMBdV+OLlGMrm9TfSrBIX9l0wVlZtpiyGUi6xJ 1GsedqNRVUFN2bTDikNEIFNcyeI5fmdj4l6XFCZtTeXLED856kArZq0OY2LPTzne7cDJ 9zlN1qSrhZ40JVfTBTjTu87oNE+9OXysmFsKmajOk0ZUW50IYftAIvcqT3rICXTGUuUq z6nnaPClLygzhnUh9/ZHQaFXobHnCaVdLe9zXa2KU5s7fpP1C1qv2H177AIi9MzU4eqv nSMA== X-Forwarded-Encrypted: i=1; AJvYcCWLFIwtpJvjE0jWrm00XXgVLX548DCFjFe7Iw5nbe0Sg0NST063HB6NwLUcD1KiruUDX8DYJxSyiISABRs1nFIQ1u7vqjrBxC9B6Dor09q/G+30T8GOWY1QaZnVOu9lhtM1W3Xvmf4PxWdT80Ma164LH7cWMxNEv7bsjZndcT+4DWfFhJdcySCakB4oBJed9ZOwHaFs+5MOC/heWilSkVut7AJGODBTH/mfiQlv X-Gm-Message-State: AOJu0Yzc8wWvSfgAazDyQWamKx0/JR5RuxqiyCPaJQ5zwU9yNQ7pWW7g Uv6Xej5hLIFUlLMMaqP/5tNKZ5GqbmU+HIardZ6olGvnAF68iyEI X-Google-Smtp-Source: AGHT+IGBe8hgFGbuBC4ekuepdUwdxdD7VhNw1epIWU2Vo3BxbYXI3OtABFUKqTWAQLQkoTbbEGxrVA== X-Received: by 2002:aa7:8d15:0:b0:6ec:f5d2:f641 with SMTP id j21-20020aa78d15000000b006ecf5d2f641mr6845273pfe.1.1714054775411; Thu, 25 Apr 2024 07:19:35 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:34 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 13/16] lib min_heap: Update min_heap_push() to use min_heap_sift_up() Date: Thu, 25 Apr 2024 22:18:23 +0800 Message-Id: <20240425141826.840077-14-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Update min_heap_push() to use min_heap_sift_up() rather than its origin inline version. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- include/linux/min_heap.h | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f907c694e852..78de60f6ef1c 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -190,7 +190,6 @@ bool __min_heap_push(min_heap_char *heap, const void *e= lement, size_t elem_size, const struct min_heap_callbacks *func, void *args) { void *data =3D heap->data; - void *child, *parent; int pos; =20 if (WARN_ONCE(heap->nr >=3D heap->size, "Pushing on a full heap")) @@ -202,13 +201,7 @@ bool __min_heap_push(min_heap_char *heap, const void *= element, size_t elem_size, heap->nr++; =20 /* Sift child at pos up. */ - for (; pos > 0; pos =3D (pos - 1) / 2) { - child =3D data + (pos * elem_size); - parent =3D data + ((pos - 1) / 2) * elem_size; - if (func->less(parent, child, args)) - break; - func->swp(parent, child, args); - } + __min_heap_sift_up(heap, elem_size, pos, func, args); =20 return true; } --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pj1-f49.google.com (mail-pj1-f49.google.com [209.85.216.49]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DE60515380D; Thu, 25 Apr 2024 14:19:40 +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=1714054782; cv=none; b=nnhOPJyXaD8nNCl9Yo69t7KuLy48+j/du39hVEv6K9G3iEMm2s5Zycx7sQBkEg0r5L5qbum3LPI2W4Jm+cGs0SYH8FPhTC9AirrnFFk+0ipYXTWA/2qPMz39iITdpkTv7fGZUga8YtaTlm/WBxr4SRkmQ5xid1IHApSqw2U+BLY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054782; c=relaxed/simple; bh=6RI5jUBlTt+5u3rxYbD5uAwV2PYZJ9bmstimem/yPPk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=L0gAYll+KWdqtStLzBEXHTYW/LTWWadWTCJLgzwgwt6gkufZL20bIRlJphyRXMx8c/GLwzNajT4vryUO24SUFEPSUkqraM6GVcGUG6LCSN/JRxwBv2cm2g9l72nHgBOVIaqsX3t82CJyc/A8/3WtWHb/kS9aDk5YKxHihS9ZgoI= 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=Xmqio8+5; 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="Xmqio8+5" Received: by mail-pj1-f49.google.com with SMTP id 98e67ed59e1d1-2af71daeec1so280038a91.0; Thu, 25 Apr 2024 07:19:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054780; x=1714659580; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=nfNQplMLN+Frp8NNBnHt1wiGD5SxoB711mIx7353U+s=; b=Xmqio8+5bH6kqmIs9997MXyiKwfVNyhyYem1MwCDaOf35G2g858sjhRFQZGL1MQGVK gLRNOVDD4y/Lvv3CDxzjm1SQzhSHz1Pm0g1JIyvUW54rg2VVo1w0fHG8/OoNyALw+SoJ 7ZyNmo/U7qWFyYACs5VFRwOPNeyv0LFpF9A6qZbkmuVxhbq83A1Kqr8WMvnT+7OmHNBc S2nEkq1suNGymqAZzGhvOsupoLzdcLdjjyFVdpEj0F0FLhcImYQGQoKT4obrGNNfpCT3 wg5hXIVlVugZvyGaAqmPGlNH23JwyyY95u4t2vqTJbFpgsd6mglNRAqkErbTNgfPvpY7 Kigw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054780; x=1714659580; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=nfNQplMLN+Frp8NNBnHt1wiGD5SxoB711mIx7353U+s=; b=AECzI3tW7VSeTcTYSgSHur9GF7M3FyXTfqPiWr8G8pQHr7ZNW8M831ylXoHC1FaxFM O1fuYJ2iPJ9MmVnlaXiw2m1LzzBuG+QluJJdG59qqLoY7lKLAWirW8VKm9oJScVGr/1e OhmWXHPhAS5urQKJ13sVbEdOEqnQytfpCn97WDtcm4pyY82+YDx/c8rXVb8/rmNaDYPF DHIY7q8UNET2nmdWwo6e5gKK999Kt332l6qGMHyGoTA3x5A399EobnED8ViLZNi8LHzP qLBs1/DkDYxF896mJ0Kn0eeAm9FtVQ/S+2U9OxE/ECvs7+DPLdv4OxBWDsUwHRp/q5rl BblQ== X-Forwarded-Encrypted: i=1; AJvYcCUlxSLz4SsuqOYENd7rBQU7WlOwICcu4O4LzP0qofBPv5kUlROhv13OgNy8aLZRu2b4VWoQ2iGWtRmAI4wqKkg5FEtJAtT999jdQY7mSEcZOCwprtsZq0U85OeoqyA1z3G6QRGpqxTt30IZ2orzhDVrZQ3aCu40fQYAJbrZMuqLeYzaRz5NuAwV1I2WFb2yu/O4mWuSuz3Obyhx31CP3F9xR/1iExJg3X3lGevD X-Gm-Message-State: AOJu0YyV1fNlcJIkw09U8QC5ySCFXBEb0JcGNX8a8aKp1ONuvtksYAOH ft/SK0K/UNDiYWp1sHW4foNoyctkqC2nhmvB/fxYJcK9grbYHEgG X-Google-Smtp-Source: AGHT+IGLtr8gNAowqrhYxdb7nL/pPUMKK9j1lIpP3T8Y0HSP5yJ+WzDtVU99hrbxcwsvMSorDEfYsA== X-Received: by 2002:a05:6a20:2624:b0:1ac:41c7:d2e2 with SMTP id i36-20020a056a20262400b001ac41c7d2e2mr5389786pze.0.1714054780149; Thu, 25 Apr 2024 07:19:40 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:39 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 14/16] lib/test_min_heap: Add test for heap_del() Date: Thu, 25 Apr 2024 22:18:24 +0800 Message-Id: <20240425141826.840077-15-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add test cases for the min_heap_del() to ensure its functionality is thoroughly tested. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- lib/test_min_heap.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 0b5037b4bd68..d40851cfd824 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -165,6 +165,40 @@ static __init int test_heap_pop_push(bool min_heap) return err; } =20 +static __init int test_heap_del(bool min_heap) +{ + int values[] =3D { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, + -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; + struct min_heap_test heap; + + min_heap_init(&heap, values, ARRAY_SIZE(values)); + heap.nr =3D ARRAY_SIZE(values); + struct min_heap_callbacks funcs =3D { + .less =3D min_heap ? less_than : greater_than, + .swp =3D swap_ints, + }; + int i, err; + + /* Test with known set of values. */ + min_heapify_all(&heap, &funcs, NULL); + for (i =3D 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err =3D pop_verify_heap(min_heap, &heap, &funcs); + + + /* Test with randomly generated values. */ + heap.nr =3D ARRAY_SIZE(values); + for (i =3D 0; i < heap.nr; i++) + values[i] =3D get_random_u32(); + min_heapify_all(&heap, &funcs, NULL); + + for (i =3D 0; i < ARRAY_SIZE(values) / 2; i++) + min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); + err +=3D pop_verify_heap(min_heap, &heap, &funcs); + + return err; +} + static int __init test_min_heap_init(void) { int err =3D 0; @@ -175,6 +209,8 @@ static int __init test_min_heap_init(void) err +=3D test_heap_push(false); err +=3D test_heap_pop_push(true); err +=3D test_heap_pop_push(false); + err +=3D test_heap_del(true); + err +=3D test_heap_del(false); if (err) { pr_err("test failed with %d errors\n", err); return -EINVAL; --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pf1-f174.google.com (mail-pf1-f174.google.com [209.85.210.174]) (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 CBBAC14AD3A; Thu, 25 Apr 2024 14:19:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054789; cv=none; b=WAHFeDqxO0Osn/vFi0/CLG8lJpGLhON/6DkVewYLL+nGI+FiKfLqNu0lkIH4aDTr4IH76hculh2tSxRCd8Rtj4caL52nnfe5uT+hmuJ7ycfJ33/6eUYYl9+fDDzn9nB6kBkIWrbjIpDwRaehSrB0c94i0KT+J9PqwoDRGDrwclM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054789; c=relaxed/simple; bh=eBsSINQpfUw2knfqZ46/sz6JrgzrMA+szIiOKC8yAjo=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=hkzmOffs+a6v68RMHPyz/HP1Pxe2iOBaf6G+7ZApSwtjzdDLFE2E8rKOvOUBcrDoruYf47Xf+4wqavrEPdvQoNuJ4K5Wj/WHr86REwoiPkiPjd01ILcqJsKqxoeKsUsajMDAfivuvG4jKaENdpTeyOgCkYhFFed4j3kpMyNVe5o= 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=Tiki8xqT; arc=none smtp.client-ip=209.85.210.174 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="Tiki8xqT" Received: by mail-pf1-f174.google.com with SMTP id d2e1a72fcca58-6f013c304bbso76189b3a.1; Thu, 25 Apr 2024 07:19:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054785; x=1714659585; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=j1lt3vXCm88uSeUAOFNaV+qax3qBG7zS/iOIdgqCm+s=; b=Tiki8xqTN5WC4oD6lh0LAy2IilOpPA1dZsfFGU6JQSYcENKTBmKO9HkxHJ1I4YL1Zg q5KibuIgrspHqFsg4ZJSL8auuJricEhoYB455LtYBLhCcqMTzD/A8WHu0UaPNyajoVGR a713GMq26plC2gmtRWE31o59LdWi7nzNamUoDGIm9iZWPqtrKqQxQF243TL/Bx7cx1Zs geYVQPELfer4W49d+uMiakLqyOInMHIk0yD9bFwp+w5fmL4VkgkoRkP8sM6EJyVfLgiT k49hgrICrnhXkPSpMMIAyMNIujYm8ei412oe09mg2WjdJePeZ7NPiPq3uofrywOmZKuq dggQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054785; x=1714659585; 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=j1lt3vXCm88uSeUAOFNaV+qax3qBG7zS/iOIdgqCm+s=; b=b/ig8dnFjWd7z3S4ew0U++7XrMqbLgPUTDZ1flLL6J8iIjUbe+jZJvTPQI9BQI4qY4 nV9lbuFBU/wYkK7bxc3p9c3ehTL9RGrxJXep55+xBPNsjsG62S44nHYr3aWvg7mIWWRE YcdgwscOyYcjAoCsrs3fWGZJAR6PWdBd5vkfDVJnw/80vwXMNklNtKJJhk3QgDD3vUnD ShdCeEPa3G1rM8zwSFFZZIxFkFCR8+g/QjShctu46Kj0G0QZ7KzKg653difxgHS1I680 VOr5dZMa1I73OhmJKG3rLl8Mwq5lAmaVi5Uyhx6aC0L0rdYNDcsNBcSe980Vg1HnWLXa vAHA== X-Forwarded-Encrypted: i=1; AJvYcCWlmbAsiPgte7KkFkmj8/L3oI9l1bqS8HhNYyhyFvDWHvDPiFJ109+V33X+ll2xvqLy8uPVmCfBMckg7GCjMaz1OAyF2+QFQ4cqENlfPJQQ8P60dDJbFRKTS+OEscC9hPYbgAp5VcdXvELgBIOoqzrmEZd8t5BlX5uR9Kf3m+Dw+MAerXCfGT7uTZTrQgmZqJoqvshlYguctokBZLj3DAruC/BDiKfSc/aTNprp X-Gm-Message-State: AOJu0Ywz1bWewFcANJK2PBDmAMC3VOTT+tXygw5x5AJi3EKWT4H2Prsx 9rWIwX+09EQ6JrmlmhvU0puX0TEw/EbNFdiAWrKP366kMl2q2WwV X-Google-Smtp-Source: AGHT+IFa2LoTY8DvhCvOupa5u6JZdUu37oEXGEjx97qVXZ8or1FVRa6V6ToTglPVXJ+5Xn3lP6LtLA== X-Received: by 2002:a05:6a21:2717:b0:1ad:7e79:e291 with SMTP id rm23-20020a056a21271700b001ad7e79e291mr5983363pzb.0.1714054784850; Thu, 25 Apr 2024 07:19:44 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:44 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 15/16] bcache: Remove heap-related macros and switch to generic min_heap Date: Thu, 25 Apr 2024 22:18:25 +0800 Message-Id: <20240425141826.840077-16-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Drop the heap-related macros from bcache and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcache. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by: Coly Li Acked-by tag has been added to the repository mentioned above and --- drivers/md/bcache/alloc.c | 64 +++++++++++++++++++------- drivers/md/bcache/bcache.h | 2 +- drivers/md/bcache/bset.c | 84 ++++++++++++++++++++++++----------- drivers/md/bcache/bset.h | 14 +++--- drivers/md/bcache/btree.c | 17 ++++++- drivers/md/bcache/extents.c | 53 ++++++++++++++-------- drivers/md/bcache/movinggc.c | 41 ++++++++++++----- drivers/md/bcache/sysfs.c | 2 + drivers/md/bcache/util.h | 67 +--------------------------- drivers/md/bcache/writeback.c | 3 ++ 10 files changed, 202 insertions(+), 145 deletions(-) diff --git a/drivers/md/bcache/alloc.c b/drivers/md/bcache/alloc.c index ce13c272c387..8cfa15ea32b4 100644 --- a/drivers/md/bcache/alloc.c +++ b/drivers/md/bcache/alloc.c @@ -166,40 +166,68 @@ static void bch_invalidate_one_bucket(struct cache *c= a, struct bucket *b) * prio is worth 1/8th of what INITIAL_PRIO is worth. */ =20 -#define bucket_prio(b) \ -({ \ - unsigned int min_prio =3D (INITIAL_PRIO - ca->set->min_prio) / 8; \ - \ - (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); \ -}) +static inline unsigned int new_bucket_prio(struct cache *ca, struct bucket= *b) +{ + unsigned int min_prio =3D (INITIAL_PRIO - ca->set->min_prio) / 8; + + return (b->prio - ca->set->min_prio + min_prio) * GC_SECTORS_USED(b); +} + +static inline bool new_bucket_max_cmp(const void *l, const void *r, void *= args) +{ + struct bucket **lhs =3D (struct bucket **)l; + struct bucket **rhs =3D (struct bucket **)r; + struct cache *ca =3D args; + + return new_bucket_prio(ca, *lhs) > new_bucket_prio(ca, *rhs); +} =20 -#define bucket_max_cmp(l, r) (bucket_prio(l) < bucket_prio(r)) -#define bucket_min_cmp(l, r) (bucket_prio(l) > bucket_prio(r)) +static inline bool new_bucket_min_cmp(const void *l, const void *r, void *= args) +{ + struct bucket **lhs =3D (struct bucket **)l; + struct bucket **rhs =3D (struct bucket **)r; + struct cache *ca =3D args; + + return new_bucket_prio(ca, *lhs) < new_bucket_prio(ca, *rhs); +} + +static inline void new_bucket_swap(void *l, void *r, void __always_unused = *args) +{ + struct bucket **lhs =3D l, **rhs =3D r; + + swap(*lhs, *rhs); +} =20 static void invalidate_buckets_lru(struct cache *ca) { struct bucket *b; - ssize_t i; + const struct min_heap_callbacks bucket_max_cmp_callback =3D { + .less =3D new_bucket_max_cmp, + .swp =3D new_bucket_swap, + }; + const struct min_heap_callbacks bucket_min_cmp_callback =3D { + .less =3D new_bucket_min_cmp, + .swp =3D new_bucket_swap, + }; =20 - ca->heap.used =3D 0; + ca->heap.nr =3D 0; =20 for_each_bucket(b, ca) { if (!bch_can_invalidate_bucket(ca, b)) continue; =20 - if (!heap_full(&ca->heap)) - heap_add(&ca->heap, b, bucket_max_cmp); - else if (bucket_max_cmp(b, heap_peek(&ca->heap))) { + if (!min_heap_full(&ca->heap)) + min_heap_push(&ca->heap, &b, &bucket_max_cmp_callback, ca); + else if (!new_bucket_max_cmp(&b, min_heap_peek(&ca->heap), ca)) { ca->heap.data[0] =3D b; - heap_sift(&ca->heap, 0, bucket_max_cmp); + min_heap_sift_down(&ca->heap, 0, &bucket_max_cmp_callback, ca); } } =20 - for (i =3D ca->heap.used / 2 - 1; i >=3D 0; --i) - heap_sift(&ca->heap, i, bucket_min_cmp); + min_heapify_all(&ca->heap, &bucket_min_cmp_callback, ca); =20 while (!fifo_full(&ca->free_inc)) { - if (!heap_pop(&ca->heap, b, bucket_min_cmp)) { + if (!ca->heap.nr) { /* * We don't want to be calling invalidate_buckets() * multiple times when it can't do anything @@ -208,6 +236,8 @@ static void invalidate_buckets_lru(struct cache *ca) wake_up_gc(ca->set); return; } + b =3D min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &bucket_min_cmp_callback, ca); =20 bch_invalidate_one_bucket(ca, b); } diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h index 4e6afa89921f..575d1e3a5217 100644 --- a/drivers/md/bcache/bcache.h +++ b/drivers/md/bcache/bcache.h @@ -457,7 +457,7 @@ struct cache { /* Allocation stuff: */ struct bucket *buckets; =20 - DECLARE_HEAP(struct bucket *, heap); + MIN_HEAP(struct bucket *, cache_heap) heap; =20 /* * If nonzero, we know we aren't going to find any buckets to invalidate diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c index 2bba4d6aaaa2..bd97d8626887 100644 --- a/drivers/md/bcache/bset.c +++ b/drivers/md/bcache/bset.c @@ -57,6 +57,8 @@ int __bch_count_data(struct btree_keys *b) struct btree_iter iter; struct bkey *k; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + if (b->ops->is_extents) for_each_key(b, k, &iter) ret +=3D KEY_SIZE(k); @@ -70,6 +72,8 @@ void __bch_check_keys(struct btree_keys *b, const char *f= mt, ...) struct btree_iter iter; const char *err; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key(b, k, &iter) { if (b->ops->is_extents) { err =3D "Keys out of order"; @@ -110,9 +114,9 @@ void __bch_check_keys(struct btree_keys *b, const char = *fmt, ...) =20 static void bch_btree_iter_next_check(struct btree_iter *iter) { - struct bkey *k =3D iter->data->k, *next =3D bkey_next(k); + struct bkey *k =3D iter->heap.data->k, *next =3D bkey_next(k); =20 - if (next < iter->data->end && + if (next < iter->heap.data->end && bkey_cmp(k, iter->b->ops->is_extents ? &START_KEY(next) : next) > 0) { bch_dump_bucket(iter->b); @@ -885,6 +889,8 @@ unsigned int bch_btree_insert_key(struct btree_keys *b,= struct bkey *k, =20 BUG_ON(b->ops->is_extents && !KEY_SIZE(k)); =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* * If k has preceding key, preceding_key_p will be set to address * of k's preceding key; otherwise preceding_key_p will be set @@ -1077,27 +1083,42 @@ struct bkey *__bch_bset_search(struct btree_keys *b= , struct bset_tree *t, =20 /* Btree iterator */ =20 -typedef bool (btree_iter_cmp_fn)(struct btree_iter_set, - struct btree_iter_set); +typedef bool (new_btree_iter_cmp_fn)(const void *, const void *, void *); + +static inline bool new_btree_iter_cmp(const void *l, const void *r, void _= _always_unused *args) +{ + const struct btree_iter_set *_l =3D l; + const struct btree_iter_set *_r =3D r; + + return bkey_cmp(_l->k, _r->k) <=3D 0; +} =20 -static inline bool btree_iter_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __al= ways_unused *args) { - return bkey_cmp(l.k, r.k) > 0; + struct btree_iter_set *_iter1 =3D iter1; + struct btree_iter_set *_iter2 =3D iter2; + + swap(*_iter1, *_iter2); } =20 static inline bool btree_iter_end(struct btree_iter *iter) { - return !iter->used; + return !iter->heap.nr; } =20 void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k, struct bkey *end) { + const struct min_heap_callbacks callbacks =3D { + .less =3D new_btree_iter_cmp, + .swp =3D new_btree_iter_swap, + }; + if (k !=3D end) - BUG_ON(!heap_add(iter, - ((struct btree_iter_set) { k, end }), - btree_iter_cmp)); + BUG_ON(!min_heap_push(&iter->heap, + &((struct btree_iter_set) { k, end }), + &callbacks, + NULL)); } =20 static struct bkey *__bch_btree_iter_init(struct btree_keys *b, @@ -1107,8 +1128,8 @@ static struct bkey *__bch_btree_iter_init(struct btre= e_keys *b, { struct bkey *ret =3D NULL; =20 - iter->size =3D ARRAY_SIZE(iter->data); - iter->used =3D 0; + iter->heap.size =3D ARRAY_SIZE(iter->heap.preallocated); + iter->heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG iter->b =3D b; @@ -1130,26 +1151,34 @@ struct bkey *bch_btree_iter_init(struct btree_keys = *b, } =20 static inline struct bkey *__bch_btree_iter_next(struct btree_iter *iter, - btree_iter_cmp_fn *cmp) + new_btree_iter_cmp_fn *cmp) { struct btree_iter_set b __maybe_unused; struct bkey *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D cmp, + .swp =3D new_btree_iter_swap, + }; =20 if (!btree_iter_end(iter)) { bch_btree_iter_next_check(iter); =20 - ret =3D iter->data->k; - iter->data->k =3D bkey_next(iter->data->k); + ret =3D iter->heap.data->k; + iter->heap.data->k =3D bkey_next(iter->heap.data->k); =20 - if (iter->data->k > iter->data->end) { + if (iter->heap.data->k > iter->heap.data->end) { WARN_ONCE(1, "bset was corrupt!\n"); - iter->data->k =3D iter->data->end; + iter->heap.data->k =3D iter->heap.data->end; } =20 - if (iter->data->k =3D=3D iter->data->end) - heap_pop(iter, b, cmp); + if (iter->heap.data->k =3D=3D iter->heap.data->end) { + if (iter->heap.nr) { + b =3D min_heap_peek(&iter->heap)[0]; + min_heap_pop(&iter->heap, &callbacks, NULL); + } + } else - heap_sift(iter, 0, cmp); + min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); } =20 return ret; @@ -1157,7 +1186,7 @@ static inline struct bkey *__bch_btree_iter_next(stru= ct btree_iter *iter, =20 struct bkey *bch_btree_iter_next(struct btree_iter *iter) { - return __bch_btree_iter_next(iter, btree_iter_cmp); + return __bch_btree_iter_next(iter, new_btree_iter_cmp); =20 } =20 @@ -1195,16 +1224,18 @@ static void btree_mergesort(struct btree_keys *b, s= truct bset *out, struct btree_iter *iter, bool fixup, bool remove_stale) { - int i; struct bkey *k, *last =3D NULL; BKEY_PADDED(k) tmp; bool (*bad)(struct btree_keys *, const struct bkey *) =3D remove_stale ? bch_ptr_bad : bch_ptr_invalid; + const struct min_heap_callbacks callbacks =3D { + .less =3D b->ops->sort_cmp, + .swp =3D new_btree_iter_swap, + }; =20 /* Heapify the iterator, using our comparison function */ - for (i =3D iter->used / 2 - 1; i >=3D 0; --i) - heap_sift(iter, i, b->ops->sort_cmp); + min_heapify_all(&iter->heap, &callbacks, NULL); =20 while (!btree_iter_end(iter)) { if (b->ops->sort_fixup && fixup) @@ -1296,6 +1327,7 @@ void bch_btree_sort_partial(struct btree_keys *b, uns= igned int start, struct btree_iter iter; int oldsize =3D bch_count_data(b); =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); __bch_btree_iter_init(b, &iter, NULL, &b->set[start]); =20 if (start) { @@ -1325,6 +1357,8 @@ void bch_btree_sort_into(struct btree_keys *b, struct= btree_keys *new, uint64_t start_time =3D local_clock(); struct btree_iter iter; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + bch_btree_iter_init(b, &iter, NULL); =20 btree_mergesort(b, new->set->data, &iter, false, true); diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h index d795c84246b0..f79441acd4c1 100644 --- a/drivers/md/bcache/bset.h +++ b/drivers/md/bcache/bset.h @@ -187,8 +187,9 @@ struct bset_tree { }; =20 struct btree_keys_ops { - bool (*sort_cmp)(struct btree_iter_set l, - struct btree_iter_set r); + bool (*sort_cmp)(const void *l, + const void *r, + void *args); struct bkey *(*sort_fixup)(struct btree_iter *iter, struct bkey *tmp); bool (*insert_fixup)(struct btree_keys *b, @@ -312,16 +313,17 @@ enum { BTREE_INSERT_STATUS_FRONT_MERGE, }; =20 +struct btree_iter_set { + struct bkey *k, *end; +}; + /* Btree key iteration */ =20 struct btree_iter { - size_t size, used; #ifdef CONFIG_BCACHE_DEBUG struct btree_keys *b; #endif - struct btree_iter_set { - struct bkey *k, *end; - } data[MAX_BSETS]; + MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) = heap; }; =20 typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k); diff --git a/drivers/md/bcache/btree.c b/drivers/md/bcache/btree.c index 196cdacce38f..a2bb86d52ad4 100644 --- a/drivers/md/bcache/btree.c +++ b/drivers/md/bcache/btree.c @@ -157,8 +157,8 @@ void bch_btree_node_read_done(struct btree *b) * See the comment arount cache_set->fill_iter. */ iter =3D mempool_alloc(&b->c->fill_iter, GFP_NOIO); - iter->size =3D b->c->cache->sb.bucket_size / b->c->cache->sb.block_size; - iter->used =3D 0; + iter->heap.size =3D b->c->cache->sb.bucket_size / b->c->cache->sb.block_s= ize; + iter->heap.nr =3D 0; =20 #ifdef CONFIG_BCACHE_DEBUG iter->b =3D &b->keys; @@ -1312,6 +1312,8 @@ static bool btree_gc_mark_node(struct btree *b, struc= t gc_stat *gc) struct btree_iter iter; struct bset_tree *t; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + gc->nodes++; =20 for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) { @@ -1573,6 +1575,8 @@ static unsigned int btree_gc_count_keys(struct btree = *b) struct btree_iter iter; unsigned int ret =3D 0; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad) ret +=3D bkey_u64s(k); =20 @@ -1615,6 +1619,7 @@ static int btree_gc_recurse(struct btree *b, struct b= tree_op *op, struct gc_merge_info r[GC_MERGE_NODES]; struct gc_merge_info *i, *last =3D r + ARRAY_SIZE(r) - 1; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done); =20 for (i =3D r; i < r + ARRAY_SIZE(r); i++) @@ -1913,6 +1918,8 @@ static int bch_btree_check_recurse(struct btree *b, s= truct btree_op *op) struct bkey *k, *p =3D NULL; struct btree_iter iter; =20 + 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); =20 @@ -1958,6 +1965,8 @@ static int bch_btree_check_thread(void *arg) cur_idx =3D prev_idx =3D 0; ret =3D 0; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* root node keys are checked before thread created */ bch_btree_iter_init(&c->root->keys, &iter, NULL); k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); @@ -2054,6 +2063,8 @@ int bch_btree_check(struct cache_set *c) struct btree_iter iter; struct btree_check_state check_state; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + /* check and mark root node keys */ for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid) bch_initial_mark_key(c, c->root->level, k); @@ -2549,6 +2560,7 @@ static int bch_btree_map_nodes_recurse(struct btree *= b, struct btree_op *op, struct bkey *k; struct btree_iter iter; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); bch_btree_iter_init(&b->keys, &iter, from); =20 while ((k =3D bch_btree_iter_next_filter(&iter, &b->keys, @@ -2582,6 +2594,7 @@ int bch_btree_map_keys_recurse(struct btree *b, struc= t btree_op *op, struct bkey *k; struct btree_iter iter; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); bch_btree_iter_init(&b->keys, &iter, from); =20 while ((k =3D bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) { diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c index d626ffcbecb9..a7221e5dbe81 100644 --- a/drivers/md/bcache/extents.c +++ b/drivers/md/bcache/extents.c @@ -33,15 +33,16 @@ static void sort_key_next(struct btree_iter *iter, i->k =3D bkey_next(i->k); =20 if (i->k =3D=3D i->end) - *i =3D iter->data[--iter->used]; + *i =3D iter->heap.data[--iter->heap.nr]; } =20 -static bool bch_key_sort_cmp(struct btree_iter_set l, - struct btree_iter_set r) +static bool new_bch_key_sort_cmp(const void *l, const void *r, void *args) { - int64_t c =3D bkey_cmp(l.k, r.k); + struct btree_iter_set *_l =3D (struct btree_iter_set *)l; + struct btree_iter_set *_r =3D (struct btree_iter_set *)r; + int64_t c =3D bkey_cmp(_l->k, _r->k); =20 - return c ? c > 0 : l.k < r.k; + return !(c ? c > 0 : _l->k < _r->k); } =20 static bool __ptr_invalid(struct cache_set *c, const struct bkey *k) @@ -238,7 +239,7 @@ static bool bch_btree_ptr_insert_fixup(struct btree_key= s *bk, } =20 const struct btree_keys_ops bch_btree_keys_ops =3D { - .sort_cmp =3D bch_key_sort_cmp, + .sort_cmp =3D new_bch_key_sort_cmp, .insert_fixup =3D bch_btree_ptr_insert_fixup, .key_invalid =3D bch_btree_ptr_invalid, .key_bad =3D bch_btree_ptr_bad, @@ -255,22 +256,36 @@ const struct btree_keys_ops bch_btree_keys_ops =3D { * Necessary for btree_sort_fixup() - if there are multiple keys that comp= are * equal in different sets, we have to process them newest to oldest. */ -static bool bch_extent_sort_cmp(struct btree_iter_set l, - struct btree_iter_set r) + +static bool new_bch_extent_sort_cmp(const void *l, const void *r, void __a= lways_unused *args) +{ + struct btree_iter_set *_l =3D (struct btree_iter_set *)l; + struct btree_iter_set *_r =3D (struct btree_iter_set *)r; + int64_t c =3D bkey_cmp(&START_KEY(_l->k), &START_KEY(_r->k)); + + return !(c ? c > 0 : _l->k < _r->k); +} + +static inline void new_btree_iter_swap(void *iter1, void *iter2, void __al= ways_unused *args) { - int64_t c =3D bkey_cmp(&START_KEY(l.k), &START_KEY(r.k)); + struct btree_iter_set *_iter1 =3D iter1; + struct btree_iter_set *_iter2 =3D iter2; =20 - return c ? c > 0 : l.k < r.k; + swap(*_iter1, *_iter2); } =20 static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter, struct bkey *tmp) { - while (iter->used > 1) { - struct btree_iter_set *top =3D iter->data, *i =3D top + 1; - - if (iter->used > 2 && - bch_extent_sort_cmp(i[0], i[1])) + const struct min_heap_callbacks callbacks =3D { + .less =3D new_bch_extent_sort_cmp, + .swp =3D new_btree_iter_swap, + }; + while (iter->heap.nr > 1) { + struct btree_iter_set *top =3D iter->heap.data, *i =3D top + 1; + + if (iter->heap.nr > 2 && + !new_bch_extent_sort_cmp(&i[0], &i[1], NULL)) i++; =20 if (bkey_cmp(top->k, &START_KEY(i->k)) <=3D 0) @@ -278,7 +293,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, =20 if (!KEY_SIZE(i->k)) { sort_key_next(iter, i); - heap_sift(iter, i - top, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); continue; } =20 @@ -288,7 +303,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, else bch_cut_front(top->k, i->k); =20 - heap_sift(iter, i - top, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, i - top, &callbacks, NULL); } else { /* can't happen because of comparison func */ BUG_ON(!bkey_cmp(&START_KEY(top->k), &START_KEY(i->k))); @@ -298,7 +313,7 @@ static struct bkey *bch_extent_sort_fixup(struct btree_= iter *iter, =20 bch_cut_back(&START_KEY(i->k), tmp); bch_cut_front(i->k, top->k); - heap_sift(iter, 0, bch_extent_sort_cmp); + min_heap_sift_down(&iter->heap, 0, &callbacks, NULL); =20 return tmp; } else { @@ -618,7 +633,7 @@ static bool bch_extent_merge(struct btree_keys *bk, } =20 const struct btree_keys_ops bch_extent_keys_ops =3D { - .sort_cmp =3D bch_extent_sort_cmp, + .sort_cmp =3D new_bch_extent_sort_cmp, .sort_fixup =3D bch_extent_sort_fixup, .insert_fixup =3D bch_extent_insert_fixup, .key_invalid =3D bch_extent_invalid, diff --git a/drivers/md/bcache/movinggc.c b/drivers/md/bcache/movinggc.c index ebd500bdf0b2..7f482729c56d 100644 --- a/drivers/md/bcache/movinggc.c +++ b/drivers/md/bcache/movinggc.c @@ -182,16 +182,27 @@ err: if (!IS_ERR_OR_NULL(w->private)) closure_sync(&cl); } =20 -static bool bucket_cmp(struct bucket *l, struct bucket *r) +static bool new_bucket_cmp(const void *l, const void *r, void __always_unu= sed *args) { - return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); + struct bucket **_l =3D (struct bucket **)l; + struct bucket **_r =3D (struct bucket **)r; + + return GC_SECTORS_USED(*_l) >=3D GC_SECTORS_USED(*_r); +} + +static void new_bucket_swap(void *l, void *r, void __always_unused *args) +{ + struct bucket **_l =3D l; + struct bucket **_r =3D r; + + swap(*_l, *_r); } =20 static unsigned int bucket_heap_top(struct cache *ca) { struct bucket *b; =20 - return (b =3D heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; + return (b =3D min_heap_peek(&ca->heap)[0]) ? GC_SECTORS_USED(b) : 0; } =20 void bch_moving_gc(struct cache_set *c) @@ -199,6 +210,10 @@ void bch_moving_gc(struct cache_set *c) struct cache *ca =3D c->cache; struct bucket *b; unsigned long sectors_to_move, reserve_sectors; + const struct min_heap_callbacks callbacks =3D { + .less =3D new_bucket_cmp, + .swp =3D new_bucket_swap, + }; =20 if (!c->copy_gc_enabled) return; @@ -209,7 +224,7 @@ void bch_moving_gc(struct cache_set *c) reserve_sectors =3D ca->sb.bucket_size * fifo_used(&ca->free[RESERVE_MOVINGGC]); =20 - ca->heap.used =3D 0; + ca->heap.nr =3D 0; =20 for_each_bucket(b, ca) { if (GC_MARK(b) =3D=3D GC_MARK_METADATA || @@ -218,25 +233,31 @@ void bch_moving_gc(struct cache_set *c) atomic_read(&b->pin)) continue; =20 - if (!heap_full(&ca->heap)) { + if (!min_heap_full(&ca->heap)) { sectors_to_move +=3D GC_SECTORS_USED(b); - heap_add(&ca->heap, b, bucket_cmp); - } else if (bucket_cmp(b, heap_peek(&ca->heap))) { + min_heap_push(&ca->heap, &b, &callbacks, NULL); + } else if (!new_bucket_cmp(&b, min_heap_peek(&ca->heap), ca)) { sectors_to_move -=3D bucket_heap_top(ca); sectors_to_move +=3D GC_SECTORS_USED(b); =20 ca->heap.data[0] =3D b; - heap_sift(&ca->heap, 0, bucket_cmp); + min_heap_sift_down(&ca->heap, 0, &callbacks, NULL); } } =20 while (sectors_to_move > reserve_sectors) { - heap_pop(&ca->heap, b, bucket_cmp); + if (ca->heap.nr) { + b =3D min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &callbacks, NULL); + } sectors_to_move -=3D GC_SECTORS_USED(b); } =20 - while (heap_pop(&ca->heap, b, bucket_cmp)) + while (ca->heap.nr) { + b =3D min_heap_peek(&ca->heap)[0]; + min_heap_pop(&ca->heap, &callbacks, NULL); SET_GC_MOVE(b, 1); + } =20 mutex_unlock(&c->bucket_lock); =20 diff --git a/drivers/md/bcache/sysfs.c b/drivers/md/bcache/sysfs.c index 6956beb55326..e8f696cb58c0 100644 --- a/drivers/md/bcache/sysfs.c +++ b/drivers/md/bcache/sysfs.c @@ -662,6 +662,8 @@ static unsigned int bch_root_usage(struct cache_set *c) struct btree *b; struct btree_iter iter; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + goto lock_root; =20 do { diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h index f61ab1bada6c..539454d8e2d0 100644 --- a/drivers/md/bcache/util.h +++ b/drivers/md/bcache/util.h @@ -9,6 +9,7 @@ #include #include #include +#include #include #include #include @@ -30,16 +31,10 @@ struct closure; =20 #endif =20 -#define DECLARE_HEAP(type, name) \ - struct { \ - size_t size, used; \ - type *data; \ - } name - #define init_heap(heap, _size, gfp) \ ({ \ size_t _bytes; \ - (heap)->used =3D 0; \ + (heap)->nr =3D 0; \ (heap)->size =3D (_size); \ _bytes =3D (heap)->size * sizeof(*(heap)->data); \ (heap)->data =3D kvmalloc(_bytes, (gfp) & GFP_KERNEL); \ @@ -52,64 +47,6 @@ do { \ (heap)->data =3D NULL; \ } while (0) =20 -#define heap_swap(h, i, j) swap((h)->data[i], (h)->data[j]) - -#define heap_sift(h, i, cmp) \ -do { \ - size_t _r, _j =3D i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j =3D _r) { \ - _r =3D _j * 2 + 1; \ - if (_r + 1 < (h)->used && \ - cmp((h)->data[_r], (h)->data[_r + 1])) \ - _r++; \ - \ - if (cmp((h)->data[_r], (h)->data[_j])) \ - break; \ - heap_swap(h, _r, _j); \ - } \ -} while (0) - -#define heap_sift_down(h, i, cmp) \ -do { \ - while (i) { \ - size_t p =3D (i - 1) / 2; \ - if (cmp((h)->data[i], (h)->data[p])) \ - break; \ - heap_swap(h, i, p); \ - i =3D p; \ - } \ -} while (0) - -#define heap_add(h, d, cmp) \ -({ \ - bool _r =3D !heap_full(h); \ - if (_r) { \ - size_t _i =3D (h)->used++; \ - (h)->data[_i] =3D d; \ - \ - heap_sift_down(h, _i, cmp); \ - heap_sift(h, _i, cmp); \ - } \ - _r; \ -}) - -#define heap_pop(h, d, cmp) \ -({ \ - bool _r =3D (h)->used; \ - if (_r) { \ - (d) =3D (h)->data[0]; \ - (h)->used--; \ - heap_swap(h, 0, (h)->used); \ - heap_sift(h, 0, cmp); \ - } \ - _r; \ -}) - -#define heap_peek(h) ((h)->used ? (h)->data[0] : NULL) - -#define heap_full(h) ((h)->used =3D=3D (h)->size) - #define DECLARE_FIFO(type, name) \ struct { \ size_t front, back, size, mask; \ diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c index 8827a6f130ad..c1d28e365910 100644 --- a/drivers/md/bcache/writeback.c +++ b/drivers/md/bcache/writeback.c @@ -915,6 +915,7 @@ static int bch_dirty_init_thread(void *arg) k =3D p =3D NULL; prev_idx =3D 0; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); bch_btree_iter_init(&c->root->keys, &iter, NULL); k =3D bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad); BUG_ON(!k); @@ -984,6 +985,8 @@ void bch_sectors_dirty_init(struct bcache_device *d) struct cache_set *c =3D d->c; struct bch_dirty_init_state state; =20 + min_heap_init(&iter.heap, NULL, MAX_BSETS); + retry_lock: b =3D c->root; rw_lock(0, b, b->level); --=20 2.34.1 From nobody Sat Jul 11 14:54:38 2026 Received: from mail-pl1-f182.google.com (mail-pl1-f182.google.com [209.85.214.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id CE89314B065; Thu, 25 Apr 2024 14:19:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054791; cv=none; b=ZUfNLd9T88uTeZHw9RxS8q0aSiQg/ok6bBShEgf8Z7TbcX1+i394HeeoSVhdn6S+COSMR7+ODn3p49vAI2FdQakrC8o+yHYE/e98gtS6Bb10h8N00dUyhDICo2us3Fye9UKtppJ7rtvxZu7l+TMjUF92xdFIZq6TBO8I+MfTllc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714054791; c=relaxed/simple; bh=zdDqeX1+1QEGuoTmK2ZnrwD+LKYtS8f4ZXb8ed+Eme8=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=OWtK3gRmab4s7Ffoltf05fQOsXaLOHZ9wf5AfD77nzma1XUVcK0GDNjklkmdr9Va6SZMeB6qM4d5szeNN7vGUndWXgASAyCK/WRCTBIfR626pckDeh1v8pNCc72/lVhSe6K+mT6tvtejs61jJbNKIsNNtBrWlUTSxDFWAb43lH4= 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=Rp4QPFv2; arc=none smtp.client-ip=209.85.214.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Rp4QPFv2" Received: by mail-pl1-f182.google.com with SMTP id d9443c01a7336-1e825c65c9bso116605ad.2; Thu, 25 Apr 2024 07:19:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1714054789; x=1714659589; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=J6NqyQrctkzCfziO6/T6yC8PVEhcoyrj5OJlrdP0FjI=; b=Rp4QPFv2b5A6YzaKFkYYRsi+uoK8TcY/RJCI6VLLJvALP01OpL+IT4VtUAihaY2e/W xAHS1p+h9yGjdOYGQi1N4PEchlU+Ft/hzCE1YkAOeqz4OZjvBxfhpjikjqBlYTYtNSVe n25sdFHtnzQGad37k1JszhGujM6oX3YKPVFagBPFEFJJFK5I+Nohg45KQG2sWoiJU5ae u9hz44/tPhlxkRhX4sdM8rdeXpyoZN77ZXkZn/xsyAWA8TpqJs/1kqAgbV3cBPruyQWZ s7MztL8ekOxCH8QCkiFGRy7OqbLTj+RkECVMM/ghpoG/pYHhhJjmUQjgETxdlMb/FIWt r6WA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714054789; x=1714659589; 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=J6NqyQrctkzCfziO6/T6yC8PVEhcoyrj5OJlrdP0FjI=; b=JvF/roPB32yoVUSsAIHLYjD+YYzzhhmFOgcnwDahYiDImoIF9T7iDZPCJ2BIK7wvG5 c+SigA/MtCcDSiz4xuPBPmen+IpE27k97JETEM2jNvV3PWT3kZpy+6aD2ELQNrFer8kc TJhBN67Q1Xu7SVNX0qI8jjO+Q1nP06sNXJ1oEpLwtrJlzqR7kBzvljZ1OXIxnP77U+Pc xPj1edxfcs/oMsA7Jy1Wg1Flk3gzgxk5EncqsDrW3NQ5WCZRYHsNUGiocLvayaDGyOUM xkygqis0m4CqdTvNiM9YXG8wjkN/OW/pwP156P/1QarhtSKE/VhLoHm2588k7f7xo0vY kpPw== X-Forwarded-Encrypted: i=1; AJvYcCWzuitaEYS5m8hguIBvpMFQj1WlADASHqyN2Sj2X4kBcDlBblfNesOjfkqwz0nbGqHFrTjKnpsxmZh8OQR13mi0oMQTk3l+iFdrqh0Of6pQwyHi1W66Ixhriqj4m9ZA+ORHjnEgXnuh4CMfkUYgc9hWeqhXkFiZjY1oTEYbSUZ0eMA+Wy8KOn19dNdZOxjQIZhp7k/QOw2q+53CYvfzzGm80nK0gkUhqrZdZ4QP X-Gm-Message-State: AOJu0YyaX8VuxaVqaBh4rjHMswIbl7KqJi9sLSO8SZo1l4O+S8SjZWRX e/AAH8n9JjBA7QTIJUfnnldfiOfLfGCs4F534g2WaUC8ambg5Urb X-Google-Smtp-Source: AGHT+IGR7S4gQOtrTx60AMKLS4Us1wyxOR35cVJGcCQLsECmLozBJyTOCovG6de7BwCtzwBjCkWqtA== X-Received: by 2002:a05:6a20:68a8:b0:1ad:df1:c05d with SMTP id n40-20020a056a2068a800b001ad0df1c05dmr5208221pzj.3.1714054789305; Thu, 25 Apr 2024 07:19:49 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id go20-20020a056a003b1400b006e6233563cesm13162397pfb.218.2024.04.25.07.19.45 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Apr 2024 07:19:48 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v4 16/16] bcachefs: Remove heap-related macros and switch to generic min_heap Date: Thu, 25 Apr 2024 22:18:26 +0800 Message-Id: <20240425141826.840077-17-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240425141826.840077-1-visitorckw@gmail.com> References: <20240425141826.840077-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Drop the heap-related macros from bcachefs and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcachefs. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by tag has been added to the repository mentioned above and --- Changes in v4: - Fix an error in ec_stripes_heap_swap() where ec_stripes_heap_set_backpointer() should be called after swapping. fs/bcachefs/clock.c | 43 ++++++++++---- fs/bcachefs/clock_types.h | 2 +- fs/bcachefs/ec.c | 76 ++++++++++++++++-------- fs/bcachefs/ec_types.h | 2 +- fs/bcachefs/util.h | 118 +------------------------------------- 5 files changed, 87 insertions(+), 154 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 363644451106..3ec64fe6a064 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -6,16 +6,29 @@ #include #include =20 -static inline long io_timer_cmp(io_timer_heap *h, - struct io_timer *l, - struct io_timer *r) +static inline bool io_timer_cmp(const void *l, const void *r, void __alway= s_unused *args) { - return l->expire - r->expire; + struct io_timer **_l =3D (struct io_timer **)l; + struct io_timer **_r =3D (struct io_timer **)r; + + return (*_l)->expire < (*_r)->expire; +} + +static inline void io_timer_swp(void *l, void *r, void __always_unused *ar= gs) +{ + struct io_timer **_l =3D (struct io_timer **)l; + struct io_timer **_r =3D (struct io_timer **)r; + + swap(*_l, *_r); } =20 void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 @@ -26,11 +39,11 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) return; } =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[i] =3D=3D timer) goto out; =20 - BUG_ON(!heap_add(&clock->timers, timer, io_timer_cmp, NULL)); + BUG_ON(!min_heap_push(&clock->timers, &timer, &callbacks, NULL)); out: spin_unlock(&clock->timer_lock); } @@ -38,12 +51,16 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[i] =3D=3D timer) { - heap_del(&clock->timers, i, io_timer_cmp, NULL); + min_heap_del(&clock->timers, i, &callbacks, NULL); break; } =20 @@ -131,12 +148,16 @@ static struct io_timer *get_expired_timer(struct io_c= lock *clock, unsigned long now) { struct io_timer *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - if (clock->timers.used && + if (clock->timers.nr && time_after_eq(now, clock->timers.data[0]->expire)) - heap_pop(&clock->timers, ret, io_timer_cmp, NULL); + min_heap_pop(&clock->timers, &callbacks, NULL); =20 spin_unlock(&clock->timer_lock); =20 @@ -161,7 +182,7 @@ void bch2_io_timers_to_text(struct printbuf *out, struc= t io_clock *clock) spin_lock(&clock->timer_lock); now =3D atomic64_read(&clock->now); =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) prt_printf(out, "%ps:\t%li\n", clock->timers.data[i]->fn, clock->timers.data[i]->expire - now); diff --git a/fs/bcachefs/clock_types.h b/fs/bcachefs/clock_types.h index 5fae0012d808..59716e148645 100644 --- a/fs/bcachefs/clock_types.h +++ b/fs/bcachefs/clock_types.h @@ -23,7 +23,7 @@ struct io_timer { /* Amount to buffer up on a percpu counter */ #define IO_CLOCK_PCPU_SECTORS 128 =20 -typedef HEAP(struct io_timer *) io_timer_heap; +typedef MIN_HEAP(struct io_timer *, io_timer_heap) io_timer_heap; =20 struct io_clock { atomic64_t now; diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index 556a217108d3..0831e745dd12 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -868,8 +868,8 @@ static int __ec_stripe_mem_alloc(struct bch_fs *c, size= _t idx, gfp_t gfp) =20 mutex_lock(&c->ec_stripes_heap_lock); if (n.size > h->size) { - memcpy(n.data, h->data, h->used * sizeof(h->data[0])); - n.used =3D h->used; + memcpy(n.data, h->data, h->nr * sizeof(h->data[0])); + n.nr =3D h->nr; swap(*h, n); } mutex_unlock(&c->ec_stripes_heap_lock); @@ -960,7 +960,7 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) =20 lockdep_assert_held(&c->ec_stripes_heap_lock); =20 - if (h->used && + if (h->nr && h->data[0].blocks_nonempty =3D=3D 0 && !bch2_stripe_is_open(c, h->data[0].idx)) return h->data[0].idx; @@ -968,14 +968,6 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) return 0; } =20 -static inline int ec_stripes_heap_cmp(ec_stripes_heap *h, - struct ec_stripe_heap_entry l, - struct ec_stripe_heap_entry r) -{ - return ((l.blocks_nonempty > r.blocks_nonempty) - - (l.blocks_nonempty < r.blocks_nonempty)); -} - static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h, size_t i) { @@ -984,39 +976,71 @@ static inline void ec_stripes_heap_set_backpointer(ec= _stripes_heap *h, genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx =3D i; } =20 +static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void = __always_unused *args) +{ + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + + return ((_l->blocks_nonempty > _r->blocks_nonempty) < + (_l->blocks_nonempty < _r->blocks_nonempty)); +} + +static inline void ec_stripes_heap_swap(void *l, void *r, void *h) +{ + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + ec_stripes_heap *_h =3D (ec_stripes_heap *)h; + size_t i =3D _l - _h->data; + size_t j =3D _r - _h->data; + + swap(*_l, *_r); + + ec_stripes_heap_set_backpointer(_h, i); + ec_stripes_heap_set_backpointer(_h, j); +} + static void heap_verify_backpointer(struct bch_fs *c, size_t idx) { ec_stripes_heap *h =3D &c->ec_stripes_heap; struct stripe *m =3D genradix_ptr(&c->stripes, idx); =20 - BUG_ON(m->heap_idx >=3D h->used); + BUG_ON(m->heap_idx >=3D h->nr); BUG_ON(h->data[m->heap_idx].idx !=3D idx); } =20 void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); =20 - heap_del(&c->ec_stripes_heap, m->heap_idx, - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + min_heap_del(&c->ec_stripes_heap, m->heap_idx, &callbacks, &c->ec_stripes= _heap); mutex_unlock(&c->ec_stripes_heap_lock); } =20 void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); - BUG_ON(heap_full(&c->ec_stripes_heap)); + BUG_ON(min_heap_full(&c->ec_stripes_heap)); =20 - heap_add(&c->ec_stripes_heap, ((struct ec_stripe_heap_entry) { + genradix_ptr(&c->stripes, idx)->heap_idx =3D c->ec_stripes_heap.nr; + min_heap_push(&c->ec_stripes_heap, &((struct ec_stripe_heap_entry) { .idx =3D idx, .blocks_nonempty =3D m->blocks_nonempty, }), - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + &callbacks, + &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); mutex_unlock(&c->ec_stripes_heap_lock); @@ -1025,6 +1049,10 @@ void bch2_stripes_heap_insert(struct bch_fs *c, void bch2_stripes_heap_update(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; ec_stripes_heap *h =3D &c->ec_stripes_heap; bool do_deletes; size_t i; @@ -1035,10 +1063,8 @@ void bch2_stripes_heap_update(struct bch_fs *c, h->data[m->heap_idx].blocks_nonempty =3D m->blocks_nonempty; =20 i =3D m->heap_idx; - heap_sift_up(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); - heap_sift_down(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + min_heap_sift_up(h, i, &callbacks, &c->ec_stripes_heap); + min_heap_sift_down(h, i, &callbacks, &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); =20 @@ -1830,7 +1856,7 @@ static s64 get_existing_stripe(struct bch_fs *c, return -1; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (heap_idx =3D 0; heap_idx < h->used; heap_idx++) { + for (heap_idx =3D 0; heap_idx < h->nr; heap_idx++) { /* No blocks worth reusing, stripe will just be deleted: */ if (!h->data[heap_idx].blocks_nonempty) continue; @@ -2161,7 +2187,7 @@ void bch2_stripes_heap_to_text(struct printbuf *out, = struct bch_fs *c) size_t i; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (i =3D 0; i < min_t(size_t, h->used, 50); i++) { + for (i =3D 0; i < min_t(size_t, h->nr, 50); i++) { m =3D genradix_ptr(&c->stripes, h->data[i].idx); =20 prt_printf(out, "%zu %u/%u+%u", h->data[i].idx, diff --git a/fs/bcachefs/ec_types.h b/fs/bcachefs/ec_types.h index 976426da3a12..2ed67431a81c 100644 --- a/fs/bcachefs/ec_types.h +++ b/fs/bcachefs/ec_types.h @@ -36,6 +36,6 @@ struct ec_stripe_heap_entry { unsigned blocks_nonempty; }; =20 -typedef HEAP(struct ec_stripe_heap_entry) ec_stripes_heap; +typedef MIN_HEAP(struct ec_stripe_heap_entry, ec_stripes_heap) ec_stripes_= heap; =20 #endif /* _BCACHEFS_EC_TYPES_H */ diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index 5cf885b09986..d5a1f1e29013 100644 --- a/fs/bcachefs/util.h +++ b/fs/bcachefs/util.h @@ -8,6 +8,7 @@ #include #include #include +#include #include #include #include @@ -54,17 +55,9 @@ static inline size_t buf_pages(void *p, size_t len) PAGE_SIZE); } =20 -#define HEAP(type) \ -struct { \ - size_t size, used; \ - type *data; \ -} - -#define DECLARE_HEAP(type, name) HEAP(type) name - #define init_heap(heap, _size, gfp) \ ({ \ - (heap)->used =3D 0; \ + (heap)->nr =3D 0; \ (heap)->size =3D (_size); \ (heap)->data =3D kvmalloc((heap)->size * sizeof((heap)->data[0]),\ (gfp)); \ @@ -76,113 +69,6 @@ do { \ (heap)->data =3D NULL; \ } while (0) =20 -#define heap_set_backpointer(h, i, _fn) \ -do { \ - void (*fn)(typeof(h), size_t) =3D _fn; \ - if (fn) \ - fn(h, i); \ -} while (0) - -#define heap_swap(h, i, j, set_backpointer) \ -do { \ - swap((h)->data[i], (h)->data[j]); \ - heap_set_backpointer(h, i, set_backpointer); \ - heap_set_backpointer(h, j, set_backpointer); \ -} while (0) - -#define heap_peek(h) \ -({ \ - EBUG_ON(!(h)->used); \ - (h)->data[0]; \ -}) - -#define heap_full(h) ((h)->used =3D=3D (h)->size) - -#define heap_sift_down(h, i, cmp, set_backpointer) \ -do { \ - size_t _c, _j =3D i; \ - \ - for (; _j * 2 + 1 < (h)->used; _j =3D _c) { \ - _c =3D _j * 2 + 1; \ - if (_c + 1 < (h)->used && \ - cmp(h, (h)->data[_c], (h)->data[_c + 1]) >=3D 0) \ - _c++; \ - \ - if (cmp(h, (h)->data[_c], (h)->data[_j]) >=3D 0) \ - break; \ - heap_swap(h, _c, _j, set_backpointer); \ - } \ -} while (0) - -#define heap_sift_up(h, i, cmp, set_backpointer) \ -do { \ - while (i) { \ - size_t p =3D (i - 1) / 2; \ - if (cmp(h, (h)->data[i], (h)->data[p]) >=3D 0) \ - break; \ - heap_swap(h, i, p, set_backpointer); \ - i =3D p; \ - } \ -} while (0) - -#define __heap_add(h, d, cmp, set_backpointer) \ -({ \ - size_t _i =3D (h)->used++; \ - (h)->data[_i] =3D d; \ - heap_set_backpointer(h, _i, set_backpointer); \ - \ - heap_sift_up(h, _i, cmp, set_backpointer); \ - _i; \ -}) - -#define heap_add(h, d, cmp, set_backpointer) \ -({ \ - bool _r =3D !heap_full(h); \ - if (_r) \ - __heap_add(h, d, cmp, set_backpointer); \ - _r; \ -}) - -#define heap_add_or_replace(h, new, cmp, set_backpointer) \ -do { \ - if (!heap_add(h, new, cmp, set_backpointer) && \ - cmp(h, new, heap_peek(h)) >=3D 0) { \ - (h)->data[0] =3D new; \ - heap_set_backpointer(h, 0, set_backpointer); \ - heap_sift_down(h, 0, cmp, set_backpointer); \ - } \ -} while (0) - -#define heap_del(h, i, cmp, set_backpointer) \ -do { \ - size_t _i =3D (i); \ - \ - BUG_ON(_i >=3D (h)->used); \ - (h)->used--; \ - if ((_i) < (h)->used) { \ - heap_swap(h, _i, (h)->used, set_backpointer); \ - heap_sift_up(h, _i, cmp, set_backpointer); \ - heap_sift_down(h, _i, cmp, set_backpointer); \ - } \ -} while (0) - -#define heap_pop(h, d, cmp, set_backpointer) \ -({ \ - bool _r =3D (h)->used; \ - if (_r) { \ - (d) =3D (h)->data[0]; \ - heap_del(h, 0, cmp, set_backpointer); \ - } \ - _r; \ -}) - -#define heap_resort(heap, cmp, set_backpointer) \ -do { \ - ssize_t _i; \ - for (_i =3D (ssize_t) (heap)->used / 2 - 1; _i >=3D 0; --_i) \ - heap_sift_down(heap, _i, cmp, set_backpointer); \ -} while (0) - #define ANYSINT_MAX(t) \ ((((t) 1 << (sizeof(t) * 8 - 2)) - (t) 1) * (t) 2 + (t) 1) =20 --=20 2.34.1