From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pl1-f171.google.com (mail-pl1-f171.google.com [209.85.214.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 10FD040875; Sat, 6 Apr 2024 16:47:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422067; cv=none; b=eWnFQzDUJU0NzqxANF4BqR/D3fHHZY7qKB0v4VtymdhqCffLi/0dgKh7sKbeoVbMO2SQGw+an16LsGcpMfd8KeQYVPcgdWLU8Q4xxiKoC4hdLZAE99WWkepXyka4sv124UMmcpd7tmdgWplxPXLg+J52JDgYTW1S8En3KkLGJKY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422067; c=relaxed/simple; bh=4n3PXoq7ifTVripzMWtTfmPNaw+I1mTBtc6mbpGaWSs=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=YAJ2Y5mBHKWPLmIM7CdjH/H5wFMM0Vjq76zXF1Q9JCUF4Mew4pG4uZlheoI5Qc7kmfqyXxeGt3Pgsr9ATRUh/BquFrN0y7HBntJHsCQ+NXTy3/I7YV6zsyuMQSilGqQ8TSQFSa004/fn+xm9EQBQqvstL9gprjcy66g0S1QaB3w= 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=jUgy2+98; arc=none smtp.client-ip=209.85.214.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jUgy2+98" Received: by mail-pl1-f171.google.com with SMTP id d9443c01a7336-1e2ae3a3f66so5426385ad.0; Sat, 06 Apr 2024 09:47:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422065; x=1713026865; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=QdmOvG2jwhJ+3WEh/LmFh3bdry4XeMTeGj+wdIbS7uw=; b=jUgy2+98awm8yPFc4RoeM8QfYlL+IGsstiSg7oaz/zySEWO08nfdgTnLeGcp/ekHFu uKPBph77Mnj+KQVSu8PNMl92w/CQwbGApaFEyzgwuU5Z2IJTh1ByxcJrQa1nWDgx9ya0 c4dazHaXuLNXE/OtswBTMiNvD3UyV65N22/iqTBmSJjNMtsBbNbg643P2S+LhRfrhHYF tdjzr/SEI+p3UefwYAUpGRNA8w3uTsHczQS8T+qDxgnZ1nSwjuilhDryf0gJYRJW5vqi YVc6z8oQGVEXqe1wycwGJKdgJfjdMLvQ0Ba0HrN9fkCbe+w4K3Hl1L38CjC/r0XAEa6x xZFw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422065; x=1713026865; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=QdmOvG2jwhJ+3WEh/LmFh3bdry4XeMTeGj+wdIbS7uw=; b=pq6duHBBMB/l4exV5bZl+zd9CVP7FyP2cpsQdSEv4CPh+PSF0+OJQBXu3hpCjVzMMO IyxJZBXS2Kgde7a9st6uHLLrP8L46CZjuySRJszNj/WxBu0X6mIBiIL78NpFGFVU449b m9O0j44BqpguG61kPk7dE0TcL8wFxlqQzlv1W8DdIPoZ7E3R4GGOM6EpqzufKEH9muGq Qk3Ztt5RO0E/MvGLaDvbegTv62ZxVqJQzwvXMBOhJh34FchDe/ZWktwftCKTCNgT7qR9 iTgTBnRnWdubQ+KFEjM57QEGP9mZwiO+DVlPqXrUKWxcqL6NFZpHw0SWTU7UKISJVprT kr2Q== X-Forwarded-Encrypted: i=1; AJvYcCUZNX/4tCEm67BnaqZ1ZxbpngDOMU8TwwLIXEMkZScKtiArUmfesPcVDRH+NB8WbEs7A7Wrj9SqgAge0mldFUxCQ4Vcytd5shhKp+Zqealp2IEGkwmGltQY0akFo8V/kUp4Ds+8Dc7inA8oDn5kcctK4Rw7CMmcRDUUwfxIBuJQ8nR2wbA32ux8/hQUoQTZm9QZJAix95mL9Di+6mS97BHNxzkVlx+pPmJ7y6CF X-Gm-Message-State: AOJu0Yyow4eJ+TK2+PUPlsaMLwjwx+02Ol8HZxQMPEVMbCT/7WhPHOt9 +TWYGc1g7gHsRCQ6P4VUGV4c7B0B+jHFEmEKVJs88JZVcdcKX5/v X-Google-Smtp-Source: AGHT+IGWOuc9Ol7ysbO6FZhlZBOwsHS2RXhDQei5cJ5VQ0IsBFf7wE0rKclroa0qJR1vURSdXfR9/Q== X-Received: by 2002:a17:902:e5c1:b0:1e0:99b2:8a91 with SMTP id u1-20020a170902e5c100b001e099b28a91mr5337876plf.4.1712422065264; Sat, 06 Apr 2024 09:47:45 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.47.41 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:47: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 v3 01/17] perf/core: Fix several typos Date: Sun, 7 Apr 2024 00:47:11 +0800 Message-Id: <20240406164727.577914-2-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'artifically' with 'artificially'. Replace 'irrespecive' with 'irrespective'. Replace 'futher' with 'further'. Replace 'sufficent' with 'sufficient'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap --- kernel/events/core.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/kernel/events/core.c b/kernel/events/core.c index 724e6d7e128f..10ac2db83f14 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -534,7 +534,7 @@ void perf_sample_event_took(u64 sample_len_ns) __this_cpu_write(running_sample_length, running_len); =20 /* - * Note: this will be biased artifically low until we have + * Note: this will be biased artificially low until we have * seen NR_ACCUMULATED_SAMPLES. Doing it this way keeps us * from having to maintain a count. */ @@ -596,10 +596,10 @@ static inline u64 perf_event_clock(struct perf_event = *event) * * Event groups make things a little more complicated, but not terribly so= . The * rules for a group are that if the group leader is OFF the entire group = is - * OFF, irrespecive of what the group member states are. This results in + * OFF, irrespective of what the group member states are. This results in * __perf_effective_state(). * - * A futher ramification is that when a group leader flips between OFF and + * A further ramification is that when a group leader flips between OFF and * !OFF, we need to update all group member times. * * @@ -891,7 +891,7 @@ static int perf_cgroup_ensure_storage(struct perf_event= *event, int cpu, heap_size, ret =3D 0; =20 /* - * Allow storage to have sufficent space for an iterator for each + * Allow storage to have sufficient space for an iterator for each * possibly nested cgroup plus an iterator for events with no cgroup. */ for (heap_size =3D 1; css; css =3D css->parent) --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pj1-f47.google.com (mail-pj1-f47.google.com [209.85.216.47]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3068E40841; Sat, 6 Apr 2024 16:47:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.47 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422074; cv=none; b=bpXviYHuHkJtM6cfv7HP2zQpAzKrVLS3SZYLXTGro4Wv2glj34xKMdtgjtKOvdrsfnx8MAjvepCZdVRSPrOCTUNVAft4hDZYZaUw/XvvxccJZd589D9aBG/ISMYdTEMi7ZmXbO2AwpbZvalLz9sMFmKWeYR8CkB6osDnzg/xVj0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422074; c=relaxed/simple; bh=ccFsqSUbNmoZfjXj/UyIC9+OiMIUuYR/yY6H+xsWda4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Rx0wPDHzAU2rRmwNbvqtNEgvfdx/ttyt31UY0FJQfIcgoUCrtdt5XehzTPhTDdV8lVdqBoaFi/GgmM+NbzcfRAkwjbHEjF3uaUyzy4CTpzxweJF+zGDbs3MITC2jx0bEDYsVR1Q03OVGidOldJs4mku1hQfZ5g4CS3vsTJze+Ts= 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=IeYu5oTN; arc=none smtp.client-ip=209.85.216.47 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="IeYu5oTN" Received: by mail-pj1-f47.google.com with SMTP id 98e67ed59e1d1-2a2d2120284so590012a91.1; Sat, 06 Apr 2024 09:47:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422072; x=1713026872; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vCMluLf0OPIP5MvhSlBnewMLss6iSf4B08EHRoBbLMI=; b=IeYu5oTNWwsbOxTPjxqorL2lPyctLEELvS5hjsGKQ1hiYObgvjKROkFTGh8HKr3T/W u88uPrHZQ2aMSgaNwxCCAvvKePhlx0CO81+F2rTHXOy0bnlJyB+yNnzsSVEhospfDOqN hmrOoqWadETiCkvbuwBYlwugNBKLzNmkGbcnGdLyCfLdXCfzNoouW68Xgc2h13njmi/I 3CELdrNcRbLACpy1ZhqaUiAMVoO0ccSa8BAaotVbwbFSvVpg2y5H9KGF8xaGT3qKihPA 9RltYJazg7JNMW2rPXCcGsO3JD3pQ+5G6sv1W87dGk8yvMD17VXemdy8AzaCMV7uwF6Q Nirg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422072; x=1713026872; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vCMluLf0OPIP5MvhSlBnewMLss6iSf4B08EHRoBbLMI=; b=j8VqCoAX4x9G5a8M1cLzC8QEwIDlCrBvgoUrtdrqUoPylxLs760jGiYq6PpyWZPdfY DBm8HKMIGrkQt7maBXHWsnglShcFWaUH2ALTbexmYOMLQcLY11uOHNJ/L+De+ulUFAAp BZM4p+qFcXYTkGSgT1uyv/BCQpX3jgQxfznWSBUN+Ktf+mO01mCfmjlT9x7xpmRI1sf3 g/GJG+HfpVzhJDLGS6TVwUTNackA3rK1MhJlVm5Xfb0Xg8HOCe5pMRcKSMOR10shj0I/ yA2mB4MY0NEauYBEM87DihYfWgnxZuyIvLlwWi94OSwzIY1PkiyX2fYu2YS6JYyHxqvx IvKQ== X-Forwarded-Encrypted: i=1; AJvYcCWZYfOnwFbotqzIKSwIHKtkUjwqCbQd4kQxyDTaj6DjrutvgNmzQAvz4vQTkoob4uMVJ1WEguYIq77LUUYCSo120mq5His0E1YB1A/rUP0uPWvVvwopZK5xnmsFY2v7aXvHqfc4aRQS1555ajE8scd7TMt0ESib7ulTwZPeinA2A5lSrNunXN7o95DVWySHmPruXjBUV7rdIMeGQkE8E40ZFzb5tYmyIQyflOpe X-Gm-Message-State: AOJu0YyvzIvAXd7OhunqSx6uJo+5btOLWITWl3tuIxNsIlWms6EX+djY mlM9Uc8QGTu1N3lNE+JEUEGBmCi3LVdhN1LidEB3rF03Og8KIhvP X-Google-Smtp-Source: AGHT+IESrQr1BMS174R7mCr2kWozgHGWkRclCRX2j+JKeepJa2bhuAUkxjh7AUA1DUqBQHFdW+tuww== X-Received: by 2002:a17:902:e84f:b0:1de:ddc6:27a6 with SMTP id t15-20020a170902e84f00b001deddc627a6mr5190843plg.2.1712422072419; Sat, 06 Apr 2024 09:47:52 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.47.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:47:51 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 02/17] bcache: Fix typo Date: Sun, 7 Apr 2024 00:47:12 +0800 Message-Id: <20240406164727.577914-3-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap --- drivers/md/bcache/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/drivers/md/bcache/util.c b/drivers/md/bcache/util.c index ae380bc3992e..410d8cb49e50 100644 --- a/drivers/md/bcache/util.c +++ b/drivers/md/bcache/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pj1-f53.google.com (mail-pj1-f53.google.com [209.85.216.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D56D24CB45; Sat, 6 Apr 2024 16:47:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422079; cv=none; b=Kz8srmhDc6028MbrSCLPih67ULUexEGVy67S1o8I65bY3uymXpSaeQT0hVUOkc9OSX826erX024J1W795hqlDZ+eObPwVBBrA57Si5x5WbWIzXmm3BmRkLKRX7PsrWmtJnz0LsI84RyNNM2/vmtW+sgEXSy7uX29euVMzZ/5Y0E= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422079; c=relaxed/simple; bh=bbsjMLDh1vvuNiLRmMV+NcOuKuTi5AyduguPnnDUqk4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=CoSyCky/BtZJzsvrIsv/ifbOIV6ukNiBN96zRiidfbj8p2T2Yxa8NeCMrLZMkmyQgt2qB2hMP+N4NhfE6PKv+hPX2IW22ltIapkUrnpC4Kd+aPlqMNHoSNcNuhcaiHXQDV+abMl7xnlI3AG7h7Wm7tLQ9Rs0XPN0kJukm+nCfdo= 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=lkcdmXOV; arc=none smtp.client-ip=209.85.216.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="lkcdmXOV" Received: by mail-pj1-f53.google.com with SMTP id 98e67ed59e1d1-2a2f2cd61cdso662532a91.1; Sat, 06 Apr 2024 09:47:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422077; x=1713026877; 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=3/27PnbbqJIcKzLAMpl2qrWzQcCu2oyEBnQ8NZJ3fd4=; b=lkcdmXOVEPFPWwowoG5WOInz4E93qsB67RAT7AICkLGozTtEcqTobgHQxYob7to0ja VTt6qHf60ZMHXQ88Cd55GvzhbmD3Ai1KjrdezFJxN54WQFxE8NDurie3TfCaYcYUcQ3O UgNTtnF9EHAj/k/oaf/7E7YbGDHP4J8O0Y7mxxvstOi+U2n8xssKrqnttfxpOPXfogec C1qQTAyZgvyCWq0kfkaSr76Xfa/0a3oiqiVLeK80Zx1clfKjLqZ6Ywnl2nbxZOnmXib0 zNnPL1iv4ReMjjECHOu8V+03u1FdNnXDc539Dcw/mKTKjv0XZ3wQboMuS/+ukQrVNFJ9 r64g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422077; x=1713026877; 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=3/27PnbbqJIcKzLAMpl2qrWzQcCu2oyEBnQ8NZJ3fd4=; b=F59l8sKwDQMRKr7mTQbxxoHfvNXGE2HnAVjgjt2x/y0ldJkuoODM/kSiETgdfl4G43 q4qGlWy/B+esrNHYlrba/+7Iy6sJRIEjDDIBSZ6HEMvJOsm1nu7h+d2suacSnVtFqGeG YdyIeE4I2VRyARKfksbEALbUefl5V6wyoP8m4R4gSy5ceFX15DnfCPrKDcHovKIchqkN rq70magp1pi01Ux2GnsPqfus0uamMeku7yHrbPxzBcTGkoBuMlcJNazr7QZz7Jt13hJh VNtxifGB/vTIDBYitBQWIkftOvCS0o9VkIWS2298L+vqoYeit0N488llGvn2Zc8WO38g CwxQ== X-Forwarded-Encrypted: i=1; AJvYcCXI4klXjTbKs0t6C7imsSoItBPsaFjMiKk+ZpFR5Ju1BnTBM9jcr2T3qUxL6AQ12K2uI9ssiZ0JrNcVHLp6ZhcUWPLvN2Sg8ukznv0cTjD6y+k13KK288cjNw0yegpmfesWuk4CEcxXq9LnF7wq2UoLAcagw3qtOr8lUKbY+ZcuTcdtRqWqmpK6d7RXIyN3hgVGhqlNBNXg9EBPdAsyteuTNcrkvh9/B8LjrEhE X-Gm-Message-State: AOJu0YxEoFe76oTVRI2And9VlLfaVcNgzzxehb9jzw4qAnA9G9lCA9dV 1o0I+upH0jfhU4v2pvvjRmvAG0dq7SzbcEbuDMOVBOFEWu+1OwUi X-Google-Smtp-Source: AGHT+IFxbiwMKuKp6BX+v4dZDdOTLacbPLhfSVk+cPppFP1Rb7Pkm0sxtLz5sQ9Y+7QstP4MTMJZHg== X-Received: by 2002:a17:902:e5c1:b0:1e0:c91b:b950 with SMTP id u1-20020a170902e5c100b001e0c91bb950mr5605946plf.5.1712422077130; Sat, 06 Apr 2024 09:47:57 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.47.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:47:56 -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 v3 03/17] bcachefs: Fix typo Date: Sun, 7 Apr 2024 00:47:13 +0800 Message-Id: <20240406164727.577914-4-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace 'utiility' with 'utility'. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Reviewed-by: Randy Dunlap --- fs/bcachefs/util.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/fs/bcachefs/util.c b/fs/bcachefs/util.c index 92c6ad75e702..05ac1b3b0604 100644 --- a/fs/bcachefs/util.c +++ b/fs/bcachefs/util.c @@ -1,6 +1,6 @@ // SPDX-License-Identifier: GPL-2.0 /* - * random utiility code, for bcache but in theory not specific to bcache + * random utility code, for bcache but in theory not specific to bcache * * Copyright 2010, 2011 Kent Overstreet * Copyright 2012 Google, Inc. --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pf1-f169.google.com (mail-pf1-f169.google.com [209.85.210.169]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 06CBB3FBA7; Sat, 6 Apr 2024 16:48:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.169 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422084; cv=none; b=PUA3NN3fr18Dk2Vj+eZQGN2R8m4a+FTSHJCf+F7TyFwA06ktSOVyHWZ1s25zQ9E9VWA+egCnhwUDGyVGfcgXSZskckG+yFHj0C2ZogFOx/+o7uYFYE+wBhedsEEo1sJanL86qJHrRSGgY4ISlntvS79cr67VRJyYEPSOTOgR5+I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422084; c=relaxed/simple; bh=Kmi/WfJXrF9DmnDIPKVOruewhD/0hLZT0Rq7qSw+uTg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=cChwbFNtEFgptINH0PItvpRCVkDuLtl0RbADjHCFcFTEwu35U0QOwKcSPcCjjpYpUpaEn54AQuz7PU2ATiMV2Sx6Deoruh9mFUkq2AWnNVpORhflwX62DEDKKYiRbSP8eAE7F1z3kl00Ry7IRT/ZSfMJNJo4Lq8a/l1o3svZ4oY= 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=QeHLzAay; arc=none smtp.client-ip=209.85.210.169 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="QeHLzAay" Received: by mail-pf1-f169.google.com with SMTP id d2e1a72fcca58-6ecfea4f01cso484049b3a.0; Sat, 06 Apr 2024 09:48:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422082; x=1713026882; 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=dK09sdVm3FDc6WKxOeZ2eJalXfjQmceUyaajZx+IgEI=; b=QeHLzAayT0sw6/+FlgnV/oCpGntoxHm+6PjXK4GN0mwr3g5FQB+60lScEf8zcJj6B5 T8hyLYYWnepberPB0DzJ3FVbEHmh3Ts0Uxd1yEjqzvDlUvF1fSktyu5+oTd/t+Hkwd5R L2aQJx4UqlVCcWXFl11KsSnf6XEkLS7SYnwCfGcUOx67KMJq01YI1XQiu+mGgVT4vS2H jiQihIBivXVEAT1kjJFDsEdANlpsyi6sTIaL+N8Jz+vhIbxMLnpXQOU38plQ1ME+OZPf 9mPxH5ymMyrZAlG1DulQm3fNxmDub5S8Jgl48FFiOK457uP4KweqeV+UfOK8XdMaaqU+ AvaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422082; x=1713026882; 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=dK09sdVm3FDc6WKxOeZ2eJalXfjQmceUyaajZx+IgEI=; b=rdNSQVc5ZEkQ/VFl5VgTDvYn9Y4cx0mMRgjkEvWnq4mEUKYBKRZdijZBc+VLzfnfi4 aDvXfVTWTnwIF5DxbSYuzxtiAXRMKU8MTxilNb0K90y7GYruy8WJBraJKv7XXCINresQ qnSFRY+mKiftl/iDPLrK1wMRjwRV0IxESTEvqZxT2tmBAad54rJ7Fq/BNu1tnJAYOgGl VEkMdEC6rUdMMJM8LUHesIiDBRE3/kuZ6oXOq/0Z3ghOyPpOuHIMIlG51aktZI4x8S11 dsMr8zD7EgBqMLN5Pi1Esefb3feYLWWhd+lb0PbPBZwYUalhLw8poK2KdmepiQXDjHLU MZFQ== X-Forwarded-Encrypted: i=1; AJvYcCWe+xOiFlDrlJtekD/5vjVH0YdfjDmNWEG+Hh7KxiJ2TS54l7/jkdp0OSDhwIarvBFhW7c3KXI28wHF1MTQY4CQx6icA5s8uQhvFLGV4j1ytq2GZOqE6hLA4/siedRN8x9VhoEZ043Yhxo6Wd1geZ6ps1+Y3XcbB8mnyiQwF3oPR66G0W04mbVCUUYSSYaIBeknQy9uddq/HSy424HK1ibg0GxRt+R0WB0EG9wr X-Gm-Message-State: AOJu0YwDvhMrVSzNbrYXLcDcIFXMYORyWMY4kYPZhYUfHKhLTqRCvDIi qyWCIRwZcP2OfsBHWPRlVYVe1C1SGZtY9/RiWh4XXUNnfKFr5Otu X-Google-Smtp-Source: AGHT+IF6bSM9TvaOHZ1SxE6Lem5Gy66Hig9ApmIiEpbRWhnjYwG5p8fVQ2KN7omN/hwecz/4GFfmWA== X-Received: by 2002:a17:902:e5c1:b0:1e0:c91b:b950 with SMTP id u1-20020a170902e5c100b001e0c91bb950mr5606192plf.5.1712422082051; Sat, 06 Apr 2024 09:48:02 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.47.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48: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 v3 04/17] lib min_heap: Add type safe interface Date: Sun, 7 Apr 2024 00:47:14 +0800 Message-Id: <20240406164727.577914-5-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-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 --- Changes in v3: - Avoid heap->heap.nr to eliminate the nested types. - Add MIN_HEAP_PREALLOCATED macro for preallocating some elements. drivers/md/dm-vdo/repair.c | 15 +++---- drivers/md/dm-vdo/slab-depot.c | 11 ++--- include/linux/min_heap.h | 79 ++++++++++++++++++++++------------ kernel/events/core.c | 23 +++++----- lib/test_min_heap.c | 37 ++++++++-------- 5 files changed, 90 insertions(+), 75 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index defc9359f10e..1916dc284365 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,11 +1118,9 @@ static void recover_block_map(struct vdo_completion = *completion) * Organize the journal entries into a binary heap so we can iterate over= them in sorted * order incrementally, avoiding an expensive sort call. */ - repair->replay_heap =3D (struct min_heap) { - .data =3D repair->entries, - .nr =3D repair->block_map_entry_count, - .size =3D repair->block_map_entry_count, - }; + repair->replay_heap.data =3D repair->entries; + repair->replay_heap.nr =3D repair->block_map_entry_count; + repair->replay_heap.size =3D repair->block_map_entry_count; min_heapify_all(&repair->replay_heap, &repair_min_heap); =20 vdo_log_info("Replaying %zu recovery entries into block map", diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index 46e4721e5b4f..fb38e3b8befc 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,11 +3520,9 @@ static int __must_check vdo_prepare_slabs_for_alloca= tion(struct block_allocator return result; =20 /* Sort the slabs by cleanliness, then by emptiness hint. */ - heap =3D (struct min_heap) { - .data =3D slab_statuses, - .nr =3D allocator->slab_count, - .size =3D allocator->slab_count, - }; + heap.data =3D slab_statuses; + heap.nr =3D allocator->slab_count; + heap.size =3D allocator->slab_count; min_heapify_all(&heap, &slab_status_min_heap); =20 while (heap.nr > 0) { 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..4b6a50b0fef0 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,11 +3748,9 @@ static noinline int visit_groups_merge(struct perf_e= vent_context *ctx, =20 if (!ctx->task) { cpuctx =3D this_cpu_ptr(&perf_cpu_context); - event_heap =3D (struct min_heap){ - .data =3D cpuctx->heap, - .nr =3D 0, - .size =3D cpuctx->heap_size, - }; + event_heap.data =3D cpuctx->heap; + event_heap.nr =3D 0; + event_heap.size =3D cpuctx->heap_size; =20 lockdep_assert_held(&cpuctx->ctx.lock); =20 @@ -3760,11 +3759,9 @@ static noinline int visit_groups_merge(struct perf_e= vent_context *ctx, css =3D &cpuctx->cgrp->css; #endif } else { - event_heap =3D (struct min_heap){ - .data =3D itrs, - .nr =3D 0, - .size =3D ARRAY_SIZE(itrs), - }; + event_heap.data =3D itrs; + event_heap.nr =3D 0; + event_heap.size =3D ARRAY_SIZE(itrs); /* Events not within a CPU context may be on any CPU. */ __heap_add(&event_heap, perf_event_groups_first(groups, -1, pmu, NULL)); } diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 7b01b4387cfb..9e7642c3ef9e 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 { - .data =3D values, - .nr =3D ARRAY_SIZE(values), - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.data =3D values; + heap.nr =3D ARRAY_SIZE(values); + heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -96,13 +97,12 @@ static __init int test_heap_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { - .data =3D values, - .nr =3D 0, - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.data =3D values; + heap.nr =3D 0; + heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; @@ -129,13 +129,12 @@ static __init int test_heap_pop_push(bool min_heap) const int data[] =3D { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; int values[ARRAY_SIZE(data)]; - struct min_heap heap =3D { - .data =3D values, - .nr =3D 0, - .size =3D ARRAY_SIZE(values), - }; + struct min_heap_test heap; + + heap.data =3D values; + heap.nr =3D 0; + heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { - .elem_size =3D sizeof(int), .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, }; --=20 2.34.1 From nobody Sat Feb 7 19:41:25 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 4D6234437B; Sat, 6 Apr 2024 16:48:07 +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=1712422088; cv=none; b=pA4Kf+FCy+omFqRYLKBa63vMjijHpk23aehhnxEBHKqA/JltLMQx/ijVHAidJZPq7QtM2JKEP70SyrW+55E8rJVhzpp4mhfbKsGQF0CKC4YJVBBHmOGmvKhFl/n6RXJtvMvsyM7hyIGOCqWipzCKmEnliR/NMvIKwPUo8QR9Ym8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422088; c=relaxed/simple; bh=41wIMMrsMcV2JAh2IuFxgje7q/XR6YKUnX/6Mr8hZpU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=QKOoKPi+rW3Z/hlS8hT3n36zFxFZ+KPzguowzsnOsIO8L8jVXRW9OqvxfROWhE24742Nx5GUzIB+3nl0nX0pqegoYEJ9XL3Liy4SoMTo47lITreNkMtNApx1Tu1PDbyexxb+6tsMyYIx4+JMqntxSct/30YBzBVScA/ToaxTTvM= 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=YnEsgxtR; 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="YnEsgxtR" Received: by mail-pl1-f179.google.com with SMTP id d9443c01a7336-1e2a307902cso4970575ad.1; Sat, 06 Apr 2024 09:48:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422087; x=1713026887; 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=mUGTczp2Kn8XprLlzlIe26wHtjou4WYa/rxGIi1PK80=; b=YnEsgxtRVE7LGfHefhht1EoCIj/69mtTl/j2id6dGHkCn8CTjUd9IUmLyUl1S2G+oR zkx2UxMA36nKRONALOBn+h04yP6dDmfQZHRMbFMEtYvj2+XaQbevwSaMiMaacG2ER7mc KZUvNhG8ydtmxqosQ2ZKGc3TsaVSI1xS0vm1YepcRpUh4IkhfxSrwbkhwfRfY9AE2Etk NYLnFMWDlz/nbn5+SqX0Wc1NPDngnREKJcybpxyqPnj1xelebXYfubHZn8qjLJkLv8zm u9PdRmTVZO+RTbS85WwK+HfDMXWwRvTAXerq75xtQBQF6EHinnisFuM62bc02cpdGw90 LRww== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422087; x=1713026887; 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=mUGTczp2Kn8XprLlzlIe26wHtjou4WYa/rxGIi1PK80=; b=K3LBxJb/m/Ly7Mx4k6NgFoCHrxUgdlPPs8kCHVEFPYLFV0Lt+Izs8o9fkE1qLK2dTK b3itDhnOBeyRDDoyFh4lHsoQbXb+199xb4SveLlZK5xw2mpjFaZSnuAgBOByDqAVyLfu zr42su3eEkOmcy+dJg4Co3dLw7S6BgcpiImzdffsOy4EBcR9/sLJFnrDOXY8hDcwBjIZ O5PsnWP+7pyw1ULwg9TTqt5gKoIOhTSohEMhwBynby4MZJrjSfWfUiYR03M5X+75feGW MIKxuxleUHcCTwOmfwb0nRcYLjpbc8U+YHlnEAxOdhzvwVXxUgl4FW7Byf3/cQlZm7ib bDgA== X-Forwarded-Encrypted: i=1; AJvYcCVOBVIuvDg9L29zZmpmHvvLVBWY6qAe/adnJyJjPOTiTcnmRdzjU8EGAwH6285nxh7ZgRGQG5FIRcbuT3yxx/DlS1elggbg90rxSdP6Lb2MafJcTh8laC5HZb2NI5X9RMAxfjoaV5ZdKh6NCravsy6aQ6CijZUPirMzpjSDN562L9e8rK3+9YH6hKfYW94oF56QVJ0QIU/xDfa0X1TJlvnefkBIostRPsh/vEZv X-Gm-Message-State: AOJu0Yy5vziL3NZ9ylBmi9gMFb2XXQHw8LCzLxf9uxiAnh5X9my+MeMj EhESry1jqoJn/syFiNYpRfVczo2JLFMW5YrXXdSIq9XT/s2wFuc1 X-Google-Smtp-Source: AGHT+IEfdT0u+GNUvqc2IQqievgBGrYbYzE6csgkYg+ooNoxAHp4tOGUzoKNnscpqMdglSVxGHUWwA== X-Received: by 2002:a17:902:ea01:b0:1e2:c1ce:5b9d with SMTP id s1-20020a170902ea0100b001e2c1ce5b9dmr5303688plg.2.1712422086668; Sat, 06 Apr 2024 09:48:06 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.03 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:06 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 05/17] lib min_heap: Add min_heap_init() Date: Sun, 7 Apr 2024 00:47:15 +0800 Message-Id: <20240406164727.577914-6-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-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 --- Changes in v3: - If the 'data' parameter is NULL, we now make the data pointer in the heap point to the preallocated. 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 Feb 7 19:41:25 2026 Received: from mail-pj1-f53.google.com (mail-pj1-f53.google.com [209.85.216.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 742D04F201; Sat, 6 Apr 2024 16:48:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.53 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422093; cv=none; b=W3kraIrrzAWtPLi4Tpx3wFKHxXEqz7b8E2yA8vWLpXkA7GuCTz8Vf6CydYBXl7GeZENP2BBYpjNOBTwad1v3TLyGfowo+M7LuKh9BhQnSWVhj+nTToW53ncLe3skLMjxn8jNRR515wwROztD/khuHDLEolO143dTjdmT8lR+b5s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422093; c=relaxed/simple; bh=9tjNBJoFW/M4N3UyhM3SbO6qdcqZWdxAoa5Ri1G9BtM=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Oobgmu8hb9Cgguh8qJLNg9qu91OhchloGR/SPm90cRCcuyMrG6oV2mp1/QSwt2hmidIM6dMtswuB1ZLXTTFR9hSDagpREPXg3VIhu0evqITAmQ3PQ2KUobOzSKCJyarL3VNq51spOUWwGjJk+gDYw2ltrCxKU2Sk3mgmvB6QsIc= 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=UjsoCI/0; arc=none smtp.client-ip=209.85.216.53 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="UjsoCI/0" Received: by mail-pj1-f53.google.com with SMTP id 98e67ed59e1d1-2a49986efc0so371119a91.0; Sat, 06 Apr 2024 09:48:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422092; x=1713026892; 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=UjsoCI/0gHLMjML819DguWER5kw5ZuaZHnj9/D4maElnvuqNal3hCIvO4FoMKtTMpq yxHsUS7jOvtwhtp34q1vM7aUp+P5JQedZmHwfikSXH7eD6fKSSvZBCV62snn/j6mbjmC sXFrEi08Xfr7yKtn69Irc16jgM8ZWP/w8z3h5AVXn/f3EJhkHzcHI14z1BstIo4H+hmi 18ZZdegVQzYSC43HcbcAsWl4O+9fXF8ycvGTBFGqggz6t9rBhDEQXwpVZyQlauAsA4Ka fcWTrxkBqvwG2evFbN/LpwlaJkJ5wOTJaWwmnKC+Rb6BOIlQXed85q6QFU4MxYTByqYm BFOw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422092; x=1713026892; 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=PHktvlxH681GoTk/h+f/hQYyMg+a0j1vhcUvqeLrR7XQnvfG9Z/Tk07UITAXiQyWtB kLzH9ZwGHUO7K1OIJavExgG1xVM4Pme4YcDAz9nfm7l/N68KHeqHzH1ELBEZmdn+giJ0 OLSdXAzHFDio3RUc7FY3+YT98FdjZ9L4thQIFA1FZLuHqfjjKM0MF6OlVL2OcBIVfMyx wskzUctBKYSigOGAnzlfWWTcV8o3ohwABjDl78CeekoaLKe2c+cSnmxO7E+KhLZrKXGx 0MVA94rMLbjVzGneRGFw2DRhx7yYDUyJWcJZ/Ovfu19m+CuaOAQ0sA57OQ0a4LIkJhpS xCSw== X-Forwarded-Encrypted: i=1; AJvYcCW1fPSV9A/9v3Ul2LsRtiyBjEuVeVPBu40Rqx3+8mVI0v0JbURKxkpRlxE6J4+XMMy6RgzNHTACFUC/SEPJ/3k6uUIA5Q2XwTIMRjSiRD2klnIn68l1GcBNO+Gc79UKvvq6i9chj25lW97hbidLrQ+MeQHhdpcY1xWRpHMov++pSAS1bnynsUv+s0pt5zKYMcMC+0i84IcBdKzf20oib1i/FeI4FOM9bv7M0b/t X-Gm-Message-State: AOJu0YwnhtHhgmjv6PNqXqcW/XGZBp6pEqCVOyV4F084rHkBuTem9sy7 PX+OKCuQnyoCGFIvjxKfx7reAiETj/7KmrPc7OYPUZY94rPzGnNv X-Google-Smtp-Source: AGHT+IHNQdh+85x0jYef49alqMxJn+SN5Nch0RwAutvyCaUxP71hmbuD4ujDNqcWCeX9cqd56fRLlQ== X-Received: by 2002:a17:902:e5c1:b0:1e0:c91b:b950 with SMTP id u1-20020a170902e5c100b001e0c91bb950mr5606643plf.5.1712422091701; Sat, 06 Apr 2024 09:48:11 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.08 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:11 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 06/17] lib min_heap: Add min_heap_peek() Date: Sun, 7 Apr 2024 00:47:16 +0800 Message-Id: <20240406164727.577914-7-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_peek() function to retrieve a pointer to the smallest element. The pointer is cast to the appropriate type of heap elements. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index f6b07fb8b2d3..043de539bf71 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -53,6 +53,16 @@ void __min_heap_init(min_heap_char *heap, void *data, in= t size) #define min_heap_init(_heap, _data, _size) \ __min_heap_init((min_heap_char *)_heap, _data, _size) =20 +/* Get the minimum element from the heap. */ +static __always_inline +void *__min_heap_peek(struct min_heap_char *heap) +{ + return heap->nr ? heap->data : NULL; +} + +#define min_heap_peek(_heap) \ + (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sat Feb 7 19:41:25 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 D8F0950275; Sat, 6 Apr 2024 16:48: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=1712422099; cv=none; b=UK/lYNQ/8MLUNgruj3aSiMGIwxP45ny+MMiCrZCtGZhH9ZRRHiMiP8G3SBd33pePin2KTFGTE5DIx12kXP4xorxbHKyQCkUrM5XaPhwgbNM+ZC9TiS/HOZOPDcdUtLVBJFjCJh1Lt3urShKUtlaCbjN+aUJC+T78J6zoEjBXLCM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422099; c=relaxed/simple; bh=45DqO8bF1UCi5bfdHVSu4s8AvmjNFknYLPsfVsf4ic0=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=Cf2bqztRM7EYsA0sHXgwG7A9uJD+i4P9BrRrzyV/NwFLHA1oz0M2KQQbtSCCJVOiPXgpV1+Btr04KyzWVQw9NespkcfjioO0wI7TtXaRCHq0jpKnGXCE+THVZ8fafylxydD4TGXOQVN+I3Jm2dLAjSGo1smPrYoqVmr7HWhKjgA= 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=FrKBeobG; 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="FrKBeobG" Received: by mail-pf1-f181.google.com with SMTP id d2e1a72fcca58-6ecfea4f01cso484106b3a.0; Sat, 06 Apr 2024 09:48:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422096; x=1713026896; 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=FrKBeobGpvxDStCPzJSZgxbXcUBz/d3D7ddH52D8eln8/DR4lywyCros0oMIZozVwp GeyjzLKkLrR46Fm17YCcE9D+kwI5R3NdijM/RS3pHb3NwcMLDdbWsNGf/YyZiPoxJY4C uuPN0yNib4TOdGMa6Ym+C92ADcS2EDEPInynCZSs1JRNjBP+0n6BIBOWMV/Og/1vRp+c Z64+7lX43R9t+iswGamhmXTXyAhtQ1C2ohvWs1RAM67rPpB3r0cA2Kg0XCpHfotDNUOB J2Y8nc/xtaXNgdkVL2RMVI7Jv4vw+fdwu1gG+t30TWUgsC7hpOkInTUNUtx7HMGAmNhl P3Rg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422096; x=1713026896; 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=LwvA5nXc0dfxn+HvqEIEo/t+pdNY89LaQ3pNy4WtHThbH+B7eBEPp/QDrMwSrP+L2C yHHAD5JN7XQ0pXexsd/rPB/PI8fiuySFpCbfbLS1x3mQ/6dd/kWeEX4syLpMnXdDj2W+ u6R079ViKTgS5Cu9PkRgt8e4fEZfojgjF1MTzZjtxHS1oioWXArWXII6InmUgG91Q7I1 mU/qCjOSOupXJ411JhAHCMO6dMDC9u4rwNU4goKZl/HQzyhs1I0n83HgZ7H0ZqAcFy06 LxM9zPk8db7FlGDpiucshy6uWVvS4oyXGuA3CfXFgvSAxaTxRYCu58WPGnDElU3rOCXd jvuw== X-Forwarded-Encrypted: i=1; AJvYcCU6LpVkX9UZQYVVFA4TdGIVQ/bBEE06bsrDdL23lfKnRnyK8elWkGZf7hLRjJWlXnCRZW2wQzLFTS/fKqpo5ewKvriiXR/7rD4cm4FS2owVznRbQPcoJtWFbzEkcMsZHJ57NRe4zEIvf9t2gSBnd9V9/3xxOrkMJJy20OJlSAZqE+PyUXQIbYTJFWnke3mm8yaW+7jOqCoCCcVly89da9vTeRjrONYJWg4uXUNE X-Gm-Message-State: AOJu0YxsLCjqCDElB3T/HIuqdkCLu+HdXzqDjT3gS5JptBV1vDIdatId FJURgREOZxVv2DYBDbq5xNmETdxrh83kL7GA3yWAbvq5okqyeiHE X-Google-Smtp-Source: AGHT+IENEdTgv8ntqVO1lAQSXYbpZoDkpljQUWa9D+grA8nMWQft+HCdVeMd2pRFMDlJsaRZRQvFGg== X-Received: by 2002:a17:902:ce87:b0:1db:ce31:96b1 with SMTP id f7-20020a170902ce8700b001dbce3196b1mr5553914plg.6.1712422096122; Sat, 06 Apr 2024 09:48:16 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.12 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48: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 v3 07/17] lib min_heap: Add min_heap_full() Date: Sun, 7 Apr 2024 00:47:17 +0800 Message-Id: <20240406164727.577914-8-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_full() which returns a boolean value indicating whether the heap has reached its maximum capacity. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 10 ++++++++++ 1 file changed, 10 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 043de539bf71..d4ec7e749280 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -63,6 +63,16 @@ void *__min_heap_peek(struct min_heap_char *heap) #define min_heap_peek(_heap) \ (__minheap_cast(_heap) __min_heap_peek((min_heap_char *)_heap)) =20 +/* Check if the heap is full. */ +static __always_inline +bool __min_heap_full(min_heap_char *heap) +{ + return heap->nr =3D=3D heap->size; +} + +#define min_heap_full(_heap) \ + __min_heap_full((min_heap_char *)_heap) + /* Sift the element at pos down the heap. */ static __always_inline void __min_heapify(min_heap_char *heap, int pos, size_t elem_size, --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id A58C750A93; Sat, 6 Apr 2024 16:48:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422103; cv=none; b=JRNGH+levKE44stZbJfXBe+x41lunaxyEygPVqXDKxKEY7rtHp8+95rmtv+Ckqv8A2yi+82ezVW/PWIYoxeX5kXa9W2i+gJY1ufvB9VR2R3kGMWcTDdJJCvFrkA/tgiuKnmdJUXwoP6q0P7uOMth/0y4y0CKfvsW1JeTTs5UMqM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422103; c=relaxed/simple; bh=/AmmBN0swovd7yjdDE9yxeTedZElTpztFtdU0rR41vQ=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=HKZWujAAJvMdMCaxmNM/JIfPPj4JGI8cEH1nv9/Axd0KCY4/L9yr4B4MMCCVaJ9uRUwp67gyNzbv9FbGyl//NovcgOYv9VYKFY/mvMZywZK3lFfqbBfr3S9/uaSimymj5WqrU/qgehVYLTbL73lhQsvhhHTwUBTqdyt8s0XS+eM= 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=IMg1cXBk; arc=none smtp.client-ip=209.85.216.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="IMg1cXBk" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2a2f2cd61cdso662620a91.1; Sat, 06 Apr 2024 09:48:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422101; x=1713026901; 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=IeYjJ3tP2Mkj57jEBWqWjaqwemiQratvfaeM78zwZpM=; b=IMg1cXBkkl6fO128HJUvJy8wOXyBdsMjE5tJCOCiFkrqFxZ5FYdE0P/UgnsCWgkHSR YTGm2Kcgm4nB0p3y3mg1qvqraIoI6HlRkyRDrdey4ZozkGVaRCirw2cLSyOzv67D30C1 J4FhElhzaKDYXvdYBx8fDK95dVC9ITADux15A3PY1lpnRj+PrgwHxSqpzzXaoMYsipzd RUYF8Oogp48KFrpmQZnpyMuDtBFm43Mthn6493yjtEvD/vGjdlpGQGEQy79s4rlPuvGQ uKfeCv9DqwBxCfSgX/PjfvOGTSazAflFYHM48aRCnio/bJ9b4n22Y2VHYJoy2+bKyzEs q9cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422101; x=1713026901; 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=IeYjJ3tP2Mkj57jEBWqWjaqwemiQratvfaeM78zwZpM=; b=eBd1WgO2TxMZmryzKRmoYP+0nPiYksyDgymcDRjcMGNFM6rgULtoHIiTYDABeYpDDK r+NGVO4/BYM/zQS+V94ghsydebi0dHmn/ypocLZfl6xUdBtgOteiV5XUI6y+lmJu5mlL Rwdnke/lqJu4VYD5ZLqrb8YbrHNZf0UCPyqEVyc6OksawJJBd2GG05mX6HA2outnjPyU 6TFw4/5CDXNk0TnZEh2nm2AIMGURD3TZIBik+QQC3nKHRNdoO8xmUmq38a8AVt8LMNac gnX7vrdgSc3UTno8E8rpDWJPtKFFUZEjeEWv3rGTnE4MJxe40bPXwpgs4Uz0I36GJ72c 7Gwg== X-Forwarded-Encrypted: i=1; AJvYcCXSGeU18fEkkbJ4faAfHcJlRknhKJUYBU12L4amAyXtBWi5eqZoz3HZGkzHuB80GuGN4Tt7dt4Hcy7LqwALDNCPYuVoVPUioSAs0OjlWqSVD7TZRFf7dDg/wypLQufnRg1y0SyxzLFg0d4Im6Z9p7U/IBHwHuNTB6gC35+l0BJHV0oO6N7Cpskb+QlQAhhbqBV866aRzJTs49brVTOXUYCNdGnftznf3mr6OYQY X-Gm-Message-State: AOJu0YxMzuYaYoZXljo75ajG8hmikB/Ok5cum6p3D9YXHgwY9h9CAGs9 8uwesS4peuB4CPDWK0qQscSXFZC5JNbQAA97gOcGwRw8ajkfmZdS X-Google-Smtp-Source: AGHT+IFTxdzIGFM9w4wEnKPC6ujj5LA7L2qbuoeYunbJtbjBLGtppvpfm22WjgosSnHSGHRV3/q91A== X-Received: by 2002:a17:903:2352:b0:1e0:b5f2:3284 with SMTP id c18-20020a170903235200b001e0b5f23284mr5601771plh.0.1712422100895; Sat, 06 Apr 2024 09:48:20 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.17 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48: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 v3 08/17] lib min_heap: Add args for min_heap_callbacks Date: Sun, 7 Apr 2024 00:47:18 +0800 Message-Id: <20240406164727.577914-9-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add a third parameter 'args' for the 'less' and 'swp' functions in the 'struct min_heap_callbacks'. This additional parameter allows these comparison and swap functions to handle extra arguments when necessary. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/dm-vdo/repair.c | 10 +++---- drivers/md/dm-vdo/slab-depot.c | 9 +++--- include/linux/min_heap.h | 51 +++++++++++++++++----------------- kernel/events/core.c | 10 +++---- lib/test_min_heap.c | 26 ++++++++--------- 5 files changed, 54 insertions(+), 52 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index 1916dc284365..5fe93868b33b 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 @@ -1121,7 +1121,7 @@ static void recover_block_map(struct vdo_completion *= completion) repair->replay_heap.data =3D repair->entries; repair->replay_heap.nr =3D repair->block_map_entry_count; repair->replay_heap.size =3D repair->block_map_entry_count; - min_heapify_all(&repair->replay_heap, &repair_min_heap); + min_heapify_all(&repair->replay_heap, &repair_min_heap, NULL); =20 vdo_log_info("Replaying %zu recovery entries into block map", repair->block_map_entry_count); diff --git a/drivers/md/dm-vdo/slab-depot.c b/drivers/md/dm-vdo/slab-depot.c index fb38e3b8befc..93b43b7fddda 100644 --- a/drivers/md/dm-vdo/slab-depot.c +++ b/drivers/md/dm-vdo/slab-depot.c @@ -3288,7 +3288,8 @@ int vdo_release_block_reference(struct block_allocato= r *allocator, * Thus, the ordering is reversed from the usual sense since min_heap retu= rns smaller elements * before larger ones. */ -static bool slab_status_is_less_than(const void *item1, const void *item2) +static bool slab_status_is_less_than(const void *item1, const void *item2, + void __always_unused *args) { const struct slab_status *info1 =3D item1; const struct slab_status *info2 =3D item2; @@ -3300,7 +3301,7 @@ static bool slab_status_is_less_than(const void *item= 1, const void *item2) return info1->slab_number < info2->slab_number; } =20 -static void swap_slab_statuses(void *item1, void *item2) +static void swap_slab_statuses(void *item1, void *item2, void __always_unu= sed *args) { struct slab_status *info1 =3D item1; struct slab_status *info2 =3D item2; @@ -3523,7 +3524,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator heap.data =3D slab_statuses; heap.nr =3D allocator->slab_count; heap.size =3D allocator->slab_count; - min_heapify_all(&heap, &slab_status_min_heap); + min_heapify_all(&heap, &slab_status_min_heap, NULL); =20 while (heap.nr > 0) { bool high_priority; @@ -3531,7 +3532,7 @@ static int __must_check vdo_prepare_slabs_for_allocat= ion(struct block_allocator struct slab_journal *journal; =20 current_slab_status =3D slab_statuses[0]; - min_heap_pop(&heap, &slab_status_min_heap); + min_heap_pop(&heap, &slab_status_min_heap, NULL); slab =3D depot->slabs[current_slab_status.slab_number]; =20 if ((depot->load_type =3D=3D VDO_SLAB_DEPOT_REBUILD_LOAD) || diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 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 4b6a50b0fef0..80f497683cf9 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3683,7 +3683,7 @@ void __perf_event_task_sched_out(struct task_struct *= task, perf_cgroup_switch(next); } =20 -static bool perf_less_group_idx(const void *l, const void *r) +static bool perf_less_group_idx(const void *l, const void *r, void __alway= s_unused *args) { const struct perf_event *le =3D *(const struct perf_event **)l; const struct perf_event *re =3D *(const struct perf_event **)r; @@ -3691,7 +3691,7 @@ static bool perf_less_group_idx(const void *l, const = void *r) return le->group_index < re->group_index; } =20 -static void swap_ptr(void *l, void *r) +static void swap_ptr(void *l, void *r, void __always_unused *args) { void **lp =3D l, **rp =3D r; =20 @@ -3779,7 +3779,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, perf_assert_pmu_disabled((*evt)->pmu_ctx->pmu); } =20 - min_heapify_all(&event_heap, &perf_min_heap); + min_heapify_all(&event_heap, &perf_min_heap, NULL); =20 while (event_heap.nr) { ret =3D func(*evt, data); @@ -3788,9 +3788,9 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap); + min_heapify(&event_heap, 0, &perf_min_heap, NULL); else - min_heap_pop(&event_heap, &perf_min_heap); + min_heap_pop(&event_heap, &perf_min_heap, NULL); } =20 return 0; diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 9e7642c3ef9e..cc7219b49ba7 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 Feb 7 19:41:25 2026 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (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 D5D1B524A2; Sat, 6 Apr 2024 16:48:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422107; cv=none; b=thbE6sFKLlZbUbVg3f3xYCcpSuZKqtA5bHSVnmBAZmdD3RaBSH9odYUvKmfZbuesoUYbU+olTGM9brULAX7RuwSQFNjAWuGR3ImMRfjyoFn1Nax9Rp7PCIv/HdhOYwkOzz3S0+4ko5wWzg26wJWGGPQEFhC135bosaOxeUYtR5Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422107; c=relaxed/simple; bh=jqo3ElORw266U/MGKhXJRdr9MiE1XqbwT/kp886Mo2s=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=KEpZdFiMymOI9u8SFTvfHKOFhaz4m4D+FZ9PRQJ2JLnXwXI5aP/AhN9PdDEx70Z6EKBEKgFfqrlITZjAI4RHK5ge8jr1u2iMWESEUFISa1vPLRM5VRR9T97KmfN/n3mFFBRrZweVRV0t1H6RyCV1LJIHKF/s2jVBJCPM8F5/QO8= 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=jziC5GiP; arc=none smtp.client-ip=209.85.214.178 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="jziC5GiP" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1e2a307902cso4972795ad.1; Sat, 06 Apr 2024 09:48:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422105; x=1713026905; 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=kzwb7BmcuGuHI8BmCOZ60hhRkppr+jH4uHUv532UMj4=; b=jziC5GiPHi1U5CoEPSkA18Zxiq0K8BSW5q9DzOKP/pEIgFHr+p/+RbF9A/tIV9Q9Yo Q3IPNHTzxfwkXMfRkzbYN3c2q+LcADonvBtlmUepKO4Ow/Lhj+yGIbhd2XKdBdCsi18A nVXC9Sck3PlObgMv7qDsbpi7ZygRmz/e/l/m0DL/JU1JLIMbDILKTmdmCAHGXlk3I0zq T0Iw8yk2/EZl46P3tuAfbujnzXj9ty+aa6WRuIt9J+th8TdunQgPtyCp/Zx+4ZGB75fQ 1SyjCIRH18Q4OZr112IUe9l4Oy46YWbo6Nb3hnh2zXIgin1x7IEdu27bdy7bfkqM6dtI gDHg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422105; x=1713026905; 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=kzwb7BmcuGuHI8BmCOZ60hhRkppr+jH4uHUv532UMj4=; b=CkUO4NiYWq0eP3WQF1jNEGPkXbFNZ6THKYEm25fuOzX7S+t/CWSyEcifwL684QHcCP +VLsL1d9CZoCxIUQYWeTomSGpwHjhau9NvKgo+7YYXuSTMu5Fxw/LfW01EXQOQ98lH5H 5N0bwM0HQ0sjK8khJAafya0cvItaf1WzltKxUzwjv426wCjo+rFTeCR+eCOVFsSMokA3 IhQdF9uc3ViAMmfSypQrcxCZ4OpTQDMy7pWAHnSYmcVmOaI2hpG+eExpNt3C/hNnsWR2 o5xPR/Li9RZbYxLmk+QMgwuzpwFhP83dCF6r+3XIwKUbsynO+baoCIxsWd214XIkc8cq VOUg== X-Forwarded-Encrypted: i=1; AJvYcCVKURsezSwg1aXOiH1j3MPU1uZSBrIkKx3pzVvRZ4TV+CM5eeO/JeyMVB7PjKOffJ740pZIQUF5AxYObCKAMfN2Klk99LKxUNgFSSXj7L1xA18tA8C5HavFPUW6/wA7e5GarotdaagA9MfFHF67Hc871Z57DMIjVrftd+DNGWFb412SLMc4/Fjx2QHtrx3XN8EG/XcyhYZPXqcGcjVs5pk09kf3Vx13c5b6SMFV X-Gm-Message-State: AOJu0YxXfKwFGToVNhQI15a3QFPUauGyIsmKMVXI81lPGCaGIh3C0kXS MynAuMXlzToMv/aoXA/7ZLUzrSC5Wnap2Dr6OomwZu2wyBKaFyen X-Google-Smtp-Source: AGHT+IECRUIgpwBjY9GlZnxntOAI/Gdn79r75bpaZK5qjV3HmrL7hNrxJ0ZSi2AQZhcLSinS0naEIQ== X-Received: by 2002:a17:903:22c5:b0:1e3:e08e:d812 with SMTP id y5-20020a17090322c500b001e3e08ed812mr1765450plg.5.1712422105286; Sat, 06 Apr 2024 09:48:25 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.21 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:24 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 09/17] lib min_heap: Add min_heap_sift_up() Date: Sun, 7 Apr 2024 00:47:19 +0800 Message-Id: <20240406164727.577914-10-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add min_heap_sift_up() to sift up the element at index 'idx' in the heap. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 9391f7cc9da9..201f59cb3558 100644 --- a/include/linux/min_heap.h +++ b/include/linux/min_heap.h @@ -111,6 +111,26 @@ void __min_heapify(min_heap_char *heap, int pos, size_= t elem_size, #define min_heapify(_heap, _pos, _func, _args) \ __min_heapify((min_heap_char *)_heap, _pos, __minheap_obj_size(_heap), _f= unc, _args) =20 +/* Sift up ith element from the heap, O(log2(nr)). */ +static __always_inline +void __min_heap_sift_up(min_heap_char *heap, size_t elem_size, size_t idx, + const struct min_heap_callbacks *func, void *args) +{ + void *data =3D heap->data; + size_t parent; + + while (idx) { + parent =3D (idx - 1) / 2; + if (func->less(data + parent * elem_size, data + idx * elem_size, args)) + break; + func->swp(data + parent * elem_size, data + idx * elem_size, args); + idx =3D parent; + } +} + +#define min_heap_sift_up(_heap, _idx, _func, _args) \ + __min_heap_sift_up((min_heap_char *)_heap, __minheap_obj_size(_heap), _id= x, _func, _args) + /* Floyd's approach to heapification that is O(nr). */ static __always_inline void __min_heapify_all(min_heap_char *heap, size_t elem_size, --=20 2.34.1 From nobody Sat Feb 7 19:41:25 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 77CDF524A2; Sat, 6 Apr 2024 16:48:30 +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=1712422112; cv=none; b=ODPsATq/gkGhuPoOANJwdYsMv/Vd1w6R65U38OSo5W2lKmw0OI2MvjbcCsjVtnkFnTOmUx2wj7nkq/E1pJonIhoRVSR1v72hDkADJXMYtpQJN2MicGi+RdSszop44Y5pTvfycpGQ9qGhTHFEBXf38kRKMpvsgRxng5BMFcJpOZE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422112; c=relaxed/simple; bh=XnBpK2mdTSiNk8pOWsUbLfl/33hQsrGUFpWaVX3xAZw=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=lTcsTSNh34k93wxAiv0isiSX1Z1Hskt0jdwRNw76NoLHxCKl4DCh5h84TNc7p3A4QdrCSHwbnYhdsHzGEM33f18TbN6DEBBUx8/qGRdBAnzDUcztnW+NyoGL+y6Dof8nLI0+HzYLZ7yw8N+h9xgBqZoXS0yscBLZhrXr4nnydWU= 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=X3QzukkF; 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="X3QzukkF" Received: by mail-pj1-f42.google.com with SMTP id 98e67ed59e1d1-2a2cced7482so744167a91.0; Sat, 06 Apr 2024 09:48:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422110; x=1713026910; 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=cVjY2hsEP5GavYAiFg2PbPm4ktH1C0XXWqyfqIoZqfc=; b=X3QzukkFLGun4zBmXIQyXj02IOmTLcp5+b6UMPhmkvj/6nn2pCO0Xn5UhbhdwQGS4n AXHUQL5gydSRI32RAzgoPpH/VKcJK8Zn4cElHMoAS5+o+mKr/ceMhGVJXc5hpLUpXdML 5H6XKObTryas8vN4BItlAOeH5JGc7PnUQc1nihQQBcE8+ThqJApWXee8+o38DXLTJyHH JVdec2UPoxk0Ucq+AITs8q/VJyqsSZPM+yCBbCTBrqTEMSBxQYHVv5/vzqH8TH3mcDkA peBJMhfkySvHPRIhGBc7kegJoSea+S4U2g1JXj6qCmNeoAcit3dnTJVqyefSJ0gemhbA GDsg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422110; x=1713026910; 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=cVjY2hsEP5GavYAiFg2PbPm4ktH1C0XXWqyfqIoZqfc=; b=pArc1sIympHP7HBZzig60oU7pOi/F+/5nFGVpVPo3xSDtqNLjURL25rfqkui6kF1aT /lK0SjWU6xroB006I5Dedfe8WLVxxZUN/O4r8u9gUq1XL78jsjeddJbqSutZozXK19qJ B0C1S7+XV+GeIbJ74LT9DPAS48aaahmkwgdGvv4OaD4SGFxrsasSBPBCCh6hrnPuvVJw WTWqSzBM0Q0bKxBxOZFeR1IjVnl7y+bz1EGSbQ9/Kntx+uDqSDyTcJ4T0SCNbxyK9eH2 bE0Bcy/0d8g8hk1exLYBQL16QE+JAy4E4rwGpTzJ1bL7qEGPCi10oQoRmZ08ouqMwTBQ miKw== X-Forwarded-Encrypted: i=1; AJvYcCXAh1s4SqJRdEqOwbwWBmDRDBed+1BNvLfdw74muRrUR1ecvtrYnZG4G4JHFpZ8tdn7tAdMtZdhxpLFgwWJX30gjKn6sF/8kvXHw2OkloGGWdnlJUGPApZObdNXqj9adOMf5aFSapM8d3sMCIk8l7sgs+yirDRyriz6lmrp517gV98NaLZl66s5xyopD4c+AsP1SlgQFg1L6K43kO30/RuHGW2xlLJdLq1Xs+KB X-Gm-Message-State: AOJu0YxGQnCAx+O4tkdhIpK2zpY/lTpjcGe+u0vrj+SQxhBVkGZRRaWq vgAtgDsXa1TtQoBSCzJPMz5+fr50Qr9Gikll9c4Ve5hWFPJ/V8J0 X-Google-Smtp-Source: AGHT+IEcyJ578ps9gq2LX604ohNhbPbzLtuv6Y3D4F0mKoW9u6iZ8nNcsVBv7jisetv3NOIFQl16OA== X-Received: by 2002:a17:902:f68e:b0:1dd:a3d6:3aff with SMTP id l14-20020a170902f68e00b001dda3d63affmr5471402plg.3.1712422109909; Sat, 06 Apr 2024 09:48:29 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.26 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48: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 v3 10/17] lib min_heap: Add min_heap_del() Date: Sun, 7 Apr 2024 00:47:20 +0800 Message-Id: <20240406164727.577914-11-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-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 --- Changes in v3: - Fix a bug where we should copy the last element to 'data + idx * element_size' instead of 'data'. 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..2aee024ca883 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; + memcpy(data + (idx * elem_size), data + (heap->nr * elem_size), elem_size= ); + __min_heap_sift_up(heap, elem_size, idx, func, args); + __min_heapify(heap, idx, elem_size, func, args); + + return true; +} + +#define min_heap_del(_heap, _idx, _func, _args) \ + __min_heap_del((min_heap_char *)_heap, __minheap_obj_size(_heap), _idx, _= func, _args) + #endif /* _LINUX_MIN_HEAP_H */ --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pl1-f174.google.com (mail-pl1-f174.google.com [209.85.214.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 E0CDC537E4; Sat, 6 Apr 2024 16:48:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.174 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422116; cv=none; b=BeRTqUOR2fdy5F6rEkW6n0wI563cpkrD5Mf6HTTbpNSadxpk1Wvaxg6RE7MnJG800RrQq3d9kw4vERpBIe5qBYPMDUQbVLStr3uoJZahB4xeUqAjBz1c5RzuWidz09wyog2NO46jdsRgh6ZY0GuBhS6Yy2NlW//kBxi63sYDaKk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422116; c=relaxed/simple; bh=P6OD1w/ffLuZA93dq3GjSiXVcdPqNBMmEYdRRZgPTYU=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=c5ZEcDLI+ymZCFzP/MmZL1GN2U1dAw8enwxxudTsKnoliBXHlu5DqBOkRqK6d6PZdrjcD0wwChT3C/PpT3JHQ5kRl+UmZY5Lheb3foprYPHcHfGeGyQOlSZiR78W+RhzvmqPH4MYLDYKezsrTxCBHGmVaPCVGEIQWVJ5Pg8Y3Wg= 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=YrxlRi9L; arc=none smtp.client-ip=209.85.214.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="YrxlRi9L" Received: by mail-pl1-f174.google.com with SMTP id d9443c01a7336-1e2ae3a3f66so5428905ad.0; Sat, 06 Apr 2024 09:48:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422114; x=1713026914; 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=3v/S/N1hN0Q2k246igfeXq323YyFr+V6BvOJzuDRd68=; b=YrxlRi9LNfwm4aUasgZjBJRRCHLYnyiB+ltRyy2PCmAn2WYJ9IcmLIF6r/GEUb22I5 QwK8FwDscVC5CHS8L05KM5Tb8HR2TGCvvZmCQwjte0C0cVvIzTePBmSib/PZNbd5ulyJ BFouW81DsVq9vaRmBn7v0uVfNQciN6jOpAMJxpWqZBx3PUv9k8JYL7SwOyFixNUyPTK7 a4IKpe/IK3zpd5sclBt3TPtx/Qv6Gd6GoVvlExl0AY2R7sF7lK3XLu3MtsJSi8BDahb0 8eEDfVrS03QkWmfnzrBWnRKV7mBw5080pJAn0iwYn0L/1tSaGbAXN5FYfNY1GoW8oWG0 5aUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422114; x=1713026914; 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=3v/S/N1hN0Q2k246igfeXq323YyFr+V6BvOJzuDRd68=; b=sD6zIUj8/TCyQyjIeD2kXbgcmzARL7e+nPdZ+DoOhT94XXb2OZ/1rHSvg8Emk0I6JU OYVVljVw7e4Zpp3JG4K9kcjQJP3jOdQA9AXAlLWa5N+18EVMRruANrjww9Eq6Vc48//f ab3NAwqPF0Cn+XToh9/jjycoQW6MRRendFty7rflOybzAuDr6AH6nI2BlxxSSs4+hPGw /a7dlKFq4/JdNPIfg3fAjeDjcdTGkVF0sCU5faq9iOvjbwxR5nS2cs+7OK7KDVIf+QGM S9X3TV8IYB2DD+0F4WO93NzrnPdJ88UZkYZrQSO0TA4rTMn5iQ4WD4tzGcHZ1O749p+f jhYw== X-Forwarded-Encrypted: i=1; AJvYcCVERmMcmcY+MFA/BVDuqLHhBTNcOgjanXlmEoKI2DeY6XzvOYSTI7AwziNI2mZRepICl8PHohfemQUKpNk8tAJWonqbZ87H1a/4+G4qU+Wc2YrW2o3DjukDDTlAhB6FyZGrHSObtGH+85hzV/mH14kZGwu7Vj1E8DoHgLl/LCyLwis/5l1m0G0/iYMiU+DvDFlDb+JqQNO99GhrvRY7r2CCl8sN3RlCnsLsRA8S X-Gm-Message-State: AOJu0YzzLg5JHE1RtIPYfba+SAFwEYzRXZLykc1MuFmpZCsc7ivTmhbk 9IXTEHoIcXX6I4Ft8VMyrk62i66hL7rf0Im3ymPeMmOVOOUDhTPG X-Google-Smtp-Source: AGHT+IEnvMJdcT9OxwgIRlFw/EFRCmFP3zZM4r7rk+irBAJtT3Oz4tYkzVHkMXa+EYYD8N3SS8ILGQ== X-Received: by 2002:a17:902:e5c1:b0:1e0:99b2:8a91 with SMTP id u1-20020a170902e5c100b001e099b28a91mr5339831plf.4.1712422114345; Sat, 06 Apr 2024 09:48:34 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:33 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v3 11/17] lib min_heap: Update min_heap_push() and min_heap_pop() to return bool values Date: Sun, 7 Apr 2024 00:47:21 +0800 Message-Id: <20240406164727.577914-12-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Modify the min_heap_push() and min_heap_pop() to return a boolean value. They now return false when the operation fails and true when it succeeds. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 2aee024ca883..889d410862c7 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 Feb 7 19:41:25 2026 Received: from mail-pg1-f177.google.com (mail-pg1-f177.google.com [209.85.215.177]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5978E54663; Sat, 6 Apr 2024 16:48:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.177 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422120; cv=none; b=NE+ujU6tZVy+HNbb8eH2YlW4g1qwDqKYvqiaRaeLdiZs/K33XeJK0Tiu2Gl3gfHkmFqNTELkKbON0/stea5rysk/3GRfYgfBO+gqlEZ0TPXGifWv4zfC3y5KUnZgCO2VrkOOWGhx4fj6jiWuH8oBKQf4hmBHP/LNoJMR5b9Pn9s= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422120; c=relaxed/simple; bh=ILK0WtUWi96BNQKLJsyDtg90NnSDdPoSsO445/1dQII=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=P74e+rHdJzUYRjiv9yHCTr9PJ6zwIr6VAAjUdpCcFnDvv8LdOYvYbaeUYOvCDuQm5ERi41K08FQZEfJ7fBoQuyhLQFQ5dfykIhABNV0ypGVk3ycv11LMgvQHCXa7bLPp+4Dl6m+z4FMxebvVc9sG+RXvCwkPIyZUI8xtSTmIGy4= 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=H0ZdPBWG; arc=none smtp.client-ip=209.85.215.177 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="H0ZdPBWG" Received: by mail-pg1-f177.google.com with SMTP id 41be03b00d2f7-5d862e8b163so659553a12.1; Sat, 06 Apr 2024 09:48:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422119; x=1713026919; 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=Kgfux8MfAeQS6+qFfIDDQF2LPwPsL6hthHkisyhefZY=; b=H0ZdPBWGXd+TpmaN18NNwhN6Qi8rIE+XpoBXcxcahAK0tVuur+Js2QiBj27J3Z66vz /fqFqSKJE2wHM3PrKPgeIORyTzlW/RfxlVTVSdIb+A0leWexsj38PQH6388Rcgx3OT30 YaGl9yBXksdoITpnFWl5vjZV9ZQVDeaQJvsJA9YJICTI/ozcoDVVVmqMtVh5DWp7ARzk cZnV8vdSZwjUA+r9Q2YOMwvUHwKElHBZ5WYMsDzEBQubxLqrb8wsWGGG1ZQmYO50sH11 fgjc/6Hyq+qeDR6LDPtGqAA06pT9eY7qV5HZLMLW0V5kZwO1quqVTyN+dGnweXyVpWAm F06w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422119; x=1713026919; 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=Kgfux8MfAeQS6+qFfIDDQF2LPwPsL6hthHkisyhefZY=; b=Wfabntj1rlBdg/c0GZAw4j7fcDZgVwadwRRtcZjg/HbYxMCIJs3ZP+H6n8SrnDC1nT bpm+9h+O+fMwKFIfkQsTy745CFO+NFQVYNOOiSW71Y0bAZX3nCZsO+mIouo3YrohQQSN iUdEAKX2WI62CGht3lBgC0mQrRmttNczU3OXCAkLfEHtOtFmrC0LdfTOXJMPl7sRL8OZ W8an6jNC8VG8J7ZG4CSQPyBFDFf989LxLktqEgijbZ48KMdkt1+tm67nDaNuXXn2ahIS rdlD/zduWaP+BblQcN4zu3v9PSwsjaNnJjIfIYWR6wY25btf4DzfV7fVu+P1gm8+AtMX pBCA== X-Forwarded-Encrypted: i=1; AJvYcCV1NTLlVv9JaHPFoQugq/0MjhYqQFLi/GvBuTaXdvZP5AhIV0OYd4/2iXU2YkffDG7Kui4lH59ar4EVGbM8sFsZqJ2hs5fLlrmF744H1QQ5OqCjXc4dhZKUb8q7u4QTogwWKulc234UAy5vyKJos++MQKZMj5ypkjUczBUd1gHCk8Lw+UY16RS+MABX8p6S8KJFbZ3Mup1JKxLPndOiK83F8OohlI5LTgMkq1hA X-Gm-Message-State: AOJu0Ywl0oKNjLOzQCUewKAy3IERODlizJvUKOcZaUSVpbK+fzB4F87g 8a8MB4RZrBY02GKy1ghf5UaXGgztsPk07AEB8nZEcXaS7TVLTIkf X-Google-Smtp-Source: AGHT+IHzFYEQ+Y8lB65YH/xq+fXDSfemv04Nu9isKsBYZjxWX2yXJ9bDEy0Igzc2DcHRS0YhkyUIZw== X-Received: by 2002:a17:902:ecd2:b0:1dd:e128:16b1 with SMTP id a18-20020a170902ecd200b001dde12816b1mr5497792plh.6.1712422118743; Sat, 06 Apr 2024 09:48:38 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48: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 Subject: [PATCH v3 12/17] lib min_heap: Rename min_heapify() to min_heap_sift_down() Date: Sun, 7 Apr 2024 00:47:22 +0800 Message-Id: <20240406164727.577914-13-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" After adding min_heap_sift_up(), the naming convention has been adjusted to maintain consistency with the min_heap_sift_up(). Consequently, min_heapify() has been renamed to min_heap_sift_down(). Link: https://lkml.kernel.org/CAP-5=3DfVcBAxt8Mw72=3DNCJPRJfjDaJcqk4rjbadgo= uAEAHz_q1A@mail.gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- drivers/md/dm-vdo/repair.c | 2 +- include/linux/min_heap.h | 14 +++++++------- kernel/events/core.c | 2 +- 3 files changed, 9 insertions(+), 9 deletions(-) diff --git a/drivers/md/dm-vdo/repair.c b/drivers/md/dm-vdo/repair.c index 5fe93868b33b..b7a66bfab9e6 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 889d410862c7..3086612d7cd5 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; memcpy(data + (idx * elem_size), data + (heap->nr * elem_size), elem_size= ); __min_heap_sift_up(heap, elem_size, idx, func, args); - __min_heapify(heap, idx, elem_size, func, args); + __min_heap_sift_down(heap, idx, elem_size, func, args); =20 return true; } diff --git a/kernel/events/core.c b/kernel/events/core.c index 80f497683cf9..a64a8337d9df 100644 --- a/kernel/events/core.c +++ b/kernel/events/core.c @@ -3788,7 +3788,7 @@ static noinline int visit_groups_merge(struct perf_ev= ent_context *ctx, =20 *evt =3D perf_event_groups_next(*evt, pmu); if (*evt) - min_heapify(&event_heap, 0, &perf_min_heap, NULL); + min_heap_sift_down(&event_heap, 0, &perf_min_heap, NULL); else min_heap_pop(&event_heap, &perf_min_heap, NULL); } --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pg1-f176.google.com (mail-pg1-f176.google.com [209.85.215.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 176A554902; Sat, 6 Apr 2024 16:48:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.215.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422125; cv=none; b=Yd5Mu6tkGWEfbeOIJxQKX1UDMf0lOsnZ0GfuhOn/6D8Y4RCqkOGqOU6PcTigFBGGWunirfNpc7mKhFGDwbTyuMD7TjKqn8BDbK9VINo0lStroqacBrCGKusfTcDoiEm/eirz6zus0FsO6wgXIk+bfHv8engYKOeYJsdkG9qmy2Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422125; c=relaxed/simple; bh=jbKOXPA+Gl6IpPqMVqcysMX060d8McJnMIlICl/F5mc=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=r4GVd9LCDBLIQqHwHpKGZ6MUGl3yLMZKUy5PHyufeqkZy7wLaq2emPT+iSoVmyRvjXamSraJVh6GffvYf89DUE3UxZWHzTwyDjRnHl+GQkR3JzI6i38Q9FcTuQ6Ndd+TxpJG2ZwmCw+l8TNE7jdAZRmxOZ2Yp9U6mGZTsAGP7D0= 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=hrX741L5; arc=none smtp.client-ip=209.85.215.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="hrX741L5" Received: by mail-pg1-f176.google.com with SMTP id 41be03b00d2f7-5d862e8b163so659577a12.1; Sat, 06 Apr 2024 09:48:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422123; x=1713026923; 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=mVBRW4eof9PowDsAk296tfYzBeUuniogKOiljPXuw18=; b=hrX741L59lUj8Vi/FNMYjJI8iArVQ+BQoOFyI+L0SmWkUPf6+p/CgOMP4x2ztjG0Kr JwEpez10N4+yf4KY8Hq3qFIAstBAForyUi4Uto/I3RiN5TZiuOXRxApXanIMKs/2mx0t rB4c1uOYzvATfuWPPftg7qQAeN/uY/OrURAxYDuutPuZ5I3FCFc5aBcxOZ7bcIHBEaL/ 6ZnE7W4U0jxFB9O5PIP+c3n9bbOFKNOUlGKgDsoqzWDvDJyut0cj61Ln7ejHIlndX7TZ AwDVyQq7gcmo2uwKilDJNXSAPuprUJzkg0rYAHeK+JVR3t7DvqRudyMkYpswPPRW3ZGH Eq9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422123; x=1713026923; 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=mVBRW4eof9PowDsAk296tfYzBeUuniogKOiljPXuw18=; b=fV14PHpQ5MZWmcRZh5QYlpSdckeowxPchGL+JWnjPSLQD03P7eu0oQUW5AA5SWs/Jl ipZPJEVkVY+oF/t1FHntM/4INwMW1IYOdK3V5uF4OrTAaH/K2k+GFW4nc+wsTVetRzA+ 39Mhi1CilPYjAXxF6TVjGGOlHneJUC/rDjjZzIag2jbxE2HRN7+7NUumj1dk8PRmgK8s snDIm8Jp3MUn+kk4iqhmODkLFQEHkcGf28uau3OwLnepR4aRH2D/UsHCFoKitSv2tRHw MXTr7rP8OlNJgeodU7R5GnKMoIXO0uKM+VtMeuYHFJ4nUkNQV8yiLohM4CaozMtdIf9P JMYA== X-Forwarded-Encrypted: i=1; AJvYcCXy2effRe2SvKkfo3fhmc3d8hYocKmmTEvEEeOX2VdBd4/b3JkqQoZ9eFrQtcrndzLKd3+b3wybi3G7nbeg3c+j9vLtarQZWLKrTbVC9OxP5rqkGsnSV+cCGgE5loOlzazMkhy3ly/c6gOzjzA+aoTAy47xKU76nHbNtS/DFdm20YqX3HUtPyBkjLOxIynKt5U3gpUp64sGXhkkuNF2kDKxbxQ2QvzonEJA01c/ X-Gm-Message-State: AOJu0YztkSvx30amtW3QjMTIu5+FF8OPRFZ/pIkaS9FgUy9Uqb5W/VzV Yd31G0jvOmdPf+D7At/x/C5zJwS230izUuKZbXgRt+bNs1o/vJFo X-Google-Smtp-Source: AGHT+IERmlFQH0vffhtfBW7h0zEYLfp3+ry7ehJ/YlP1A2Hxhl1UdWDOsD2vemJY5geJTKGS8TJGYA== X-Received: by 2002:a17:902:cecf:b0:1dd:85eb:b11 with SMTP id d15-20020a170902cecf00b001dd85eb0b11mr5562644plg.1.1712422123243; Sat, 06 Apr 2024 09:48:43 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:42 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 13/17] lib min_heap: Update min_heap_push() to use min_heap_sift_up() Date: Sun, 7 Apr 2024 00:47:23 +0800 Message-Id: <20240406164727.577914-14-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Update min_heap_push() to use min_heap_sift_up() rather than its origin inline version. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- include/linux/min_heap.h | 9 +-------- 1 file changed, 1 insertion(+), 8 deletions(-) diff --git a/include/linux/min_heap.h b/include/linux/min_heap.h index 3086612d7cd5..fe037eb5952e 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 Feb 7 19:41:25 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 CF56654902; Sat, 6 Apr 2024 16:48:48 +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=1712422130; cv=none; b=h6YdSLy5m2cVr5w4ujCmPuSlbvhspz21MK5ZClraUCb15Pc/C9Uekem0sOTd7Z+qbJeilVshPKRvxwH/l++64BY4OBc/a3z1Y2tm3de/w4LoxJHBYUL3dsddrlOIp+7x01ezmIjyb1I1de9UiYC8OfNoewhAG1K/jPAVOFDjS28= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422130; c=relaxed/simple; bh=cUOXm8PUXZY6Fju9709/MeuRssUa9uu6mwCwvhFly6U=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=koxH7+gZvAXJp/QZr28at5OFK65yEcR2+D3p9ceBVG5jm0FnChVbpDWyeg2iszmE5EvL5TdDFdX5MuO7W9FOommmt7GzVQkBI5cJVjADXZkKqkVcsNu7BS80mcmirUzPkYmaYItpupVQRe86z+66ki3CwggqMIDQVAt1pDt1ue4= 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=FO4b3Yok; 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="FO4b3Yok" Received: by mail-pj1-f51.google.com with SMTP id 98e67ed59e1d1-2a49986efc0so371214a91.0; Sat, 06 Apr 2024 09:48:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422128; x=1713026928; 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=AHNxZpx8u+XjZvJ2GIg35GcXEPPNsfxng7fyYMZIxlQ=; b=FO4b3YokEl7VCyFG0xd5D7OpJcxw+cAkRwOTQYZh0aFkX6cmCLFPSLe3edSJJngPfD Qh4O+w/ukgASE3o0ZsQMOIeokEg3lRHrfFrtmkd2VIoDNB2osYj9WqUqgKzv++pF7fYp zprh4EobzPYfD67+FJUNTj7JUDq3SDy58wDHxkKeRIWm0WNeVgNgwvk661nxj3SDzltV Bbgy0UI0w7CJ7g8wkiNTFHTmZiMY+72slGNW+xjfveGXWmULXoUBuFzzuwAVdf/ut9SK bzvU3dl/dza6L7CqATogILX6XIwGfn1IQ1Uo1WMBMs0fLptGzRCwYPaC0UrJSgXV4/fV 1liw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422128; x=1713026928; 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=AHNxZpx8u+XjZvJ2GIg35GcXEPPNsfxng7fyYMZIxlQ=; b=DWH4Pr6qGQc6+U29z+2GWFHqmduKKXgH+y4l2QFIfVnhy1pTSMH8PwZqUv0dycy8JR YpjH+ZMkRLppL955ogiU5pL1bt/5wvrQFeltYTgDTxb+J0cRgAXhLeQ5DQmkTXCBFdIK 7IPa9K/RP9E2SGm1SM8CY6UFaVU1PXpLXUNbIyY3w1pA6RdJf+6+OL8TeVMIekp3mrMW w3Lq6u0sW5NLTnLAOPEVTnkX8YM8GLWOpWWDqLqk+e/70J90rzy9r4/fwH3mflcpR7i2 iEsQZQ5V+89UAB+H/8NdM50uidTJfCfzlMBQmx0mGwayUghgYAqkOA82MceHtUyvKLRJ q3Sw== X-Forwarded-Encrypted: i=1; AJvYcCXzih6Dp7+5OviPTStSRsM0ti/iv2PO99D+yy8LpO0Qp+rt/uz6pHqowWHmEWjehnGE2EJidvZ3yT7C4Pjklkq4MWtB6DT3cpDr5bcK/AanxuQL9bZlRfBiAiOtbop3SPnlg44f0t6dHS9hdQARCeX56DB/MdRpi6xPId9Bi1BH9l3CvcvtMD22rQvPrXpZ9L1neaOwKkz/mz7g1Dthvj+MZ0Pz6Y6ocjR4jl1X X-Gm-Message-State: AOJu0YySNTFiLKqxRFYk6sEjmDMADRzkv7zTo9nLw9GBqU+D/Uo+IK9I zC5oNWWBmjeZ5y+2u/pPnyUqMV6s+UueOxxYiEPNBI21K4igmUwG X-Google-Smtp-Source: AGHT+IERQEN3/6uksLr3AQKyXLHAVa4zgVwAOUohwmgfNl0NRAk+e2fuL1w5v1WlyH3tZ6/U0YsU8Q== X-Received: by 2002:a17:902:e811:b0:1e0:c887:f93f with SMTP id u17-20020a170902e81100b001e0c887f93fmr5627092plg.1.1712422127887; Sat, 06 Apr 2024 09:48:47 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:47 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, jserv@ccns.ncku.edu.tw, 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 v3 14/17] lib/test_min_heap: Use min_heap_init() for initializing Date: Sun, 7 Apr 2024 00:47:24 +0800 Message-Id: <20240406164727.577914-15-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Replace direct assignment of values to heap data members with min_heap_init() for better code readability and maintainability. Link: https://lkml.kernel.org/CAP-5=3DfW+FvUu8JL+KrtVv5uC++4AW=3DVhyEOgmdWz= pH1mswQNzw@mail.gmail.com Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- lib/test_min_heap.c | 11 +++-------- 1 file changed, 3 insertions(+), 8 deletions(-) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index cc7219b49ba7..67dd4f644f6c 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -67,9 +67,8 @@ static __init int test_heapify_all(bool min_heap) -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; struct min_heap_test heap; =20 - heap.data =3D values; + min_heap_init(&heap, values, ARRAY_SIZE(values)); heap.nr =3D ARRAY_SIZE(values); - heap.size =3D ARRAY_SIZE(values); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, @@ -99,9 +98,7 @@ static __init int test_heap_push(bool min_heap) int values[ARRAY_SIZE(data)]; struct min_heap_test heap; =20 - heap.data =3D values; - heap.nr =3D 0; - heap.size =3D ARRAY_SIZE(values); + min_heap_init(&heap, values, ARRAY_SIZE(values)); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, @@ -131,9 +128,7 @@ static __init int test_heap_pop_push(bool min_heap) int values[ARRAY_SIZE(data)]; struct min_heap_test heap; =20 - heap.data =3D values; - heap.nr =3D 0; - heap.size =3D ARRAY_SIZE(values); + min_heap_init(&heap, values, ARRAY_SIZE(values)); struct min_heap_callbacks funcs =3D { .less =3D min_heap ? less_than : greater_than, .swp =3D swap_ints, --=20 2.34.1 From nobody Sat Feb 7 19:41:25 2026 Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) (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 084D75810F; Sat, 6 Apr 2024 16:48:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.178 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422134; cv=none; b=O19VQ5qpUDv1Ml0XM2L1jJvxihB6HOYGRn6kLQVM635k4vu+g7ivXVK7qqQI2yiZV5veDMCqZCvuPGULt5gqFX2r1m41nfTSkXL6OLepVniMCL06/90DWjkrJkv/d9rWEFVrkFx+N+LEj70p0bv/2Xphcw5OlfAmSM44i0L9LYc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422134; c=relaxed/simple; bh=nGzZ5R9SZdgLiSQrHDAKei5XKniCC8VqmnZwC34Exuk=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=kOPvlEWi5jzbjVfr9h0yrUJNgoqW/KBgKk1pGsTNPmB0JMPZZYdJ7BEypbZRFEFqLeqBKiC9fIN08COWnr8+pehgcSD09Ay6kQbxOa2QlDruzNfgwgsp6jqSlpc91p5ROmySiHFkPjPqZ3+dnBsaEUaF6lmuIX7i47J83aFGmqM= 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=ZfhVTYTV; arc=none smtp.client-ip=209.85.214.178 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="ZfhVTYTV" Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-1e2a307902cso4973295ad.1; Sat, 06 Apr 2024 09:48:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422132; x=1713026932; 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=pUFbtjS0qmDCTon3KqdyHnzuILiHtuPCl7OJb9nludU=; b=ZfhVTYTVKzM6cpLoTfAkDZRZ/CGnp2MMlmFwnyo7dFa/u+YI3nyjgs9lS9H3jYMT9l KsYRn6wd4ejiK+WDXXZpiynd4xRhvRFxIH5SB2VyEzFmEQFJuclkwUEdF91Y8b3SBRwA 4emcswfnTiad9d0AWxtFHfj96P6ALb/VWQh2fwBAeTHg1HJeQ9PZgFQf6+TGl1U7jmXj ak/hm/5qi75QShZm5zOn2bY/BisHGLiyIN7ppUNtBIQN1fgOtfFHkuc3YaPVpw9iGei4 YIygflHuyxPtSsHBg9PXLlgkdIS9Y7CxwTGI7QPwXcal0fWah7NSJoN7yrYhGkzEp3kD RQPA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422132; x=1713026932; 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=pUFbtjS0qmDCTon3KqdyHnzuILiHtuPCl7OJb9nludU=; b=Hxgyj6FvvTPFLd+Vee+tw0SOdiFAKqVMaVKvSsQioPxEGLV2+4WOYpjcvjn6TiCQUD rznRI/6E66ZHkYC+rgU0GWY6QGgr9UwAbt4lw1/ihZiNd4tyGguPs2rxl80UhWxcmpX1 WH9Uh+LekPBJHa1BZdCLqe31kboyeN6p2FHDaEB3jpoQhSFlC7qeHHQE6hlYgvx3ttlK 6GHtSkLpZfyqNrNtzRh5CoCfg73NIdxQwQVdZEKlAFBUQN1sJXqwEb/BwKxn6F5mMwny 5KCD8I+nYyOIYIV8oeAjYpUb+W2KyfK8aYpDd6TjemXFH8pEOoEfIB6QCM56dvyxpPBY 1oyg== X-Forwarded-Encrypted: i=1; AJvYcCWKBCV48VmtVCGX5gLcCoXXRfwXtjetG3s7K7IK/+sCJ/ZO6f41zJGuvnLH6b/iIhnlZ34z6vXOfP3e3c8iqiQJABGtZJfEeSZh0BabozD5x+PskGCdTQkFH0PGWzpaKIEp1bNXc9zUpbYb2UwxZlzuPedmtKhHDi6oCLL5Toa+gPXRYTzK11FsyNHLqcSdJtjlPAz5PXWmmOKVA4oR+UhO5cwxImI/ixMksz5a X-Gm-Message-State: AOJu0YzI/7EqfkylQgs7efQuV3P8mFp8D9fMllkw+V636d8/6k6VvQrA iWoxEW7C+M/vptzxEybx42MFTjTkyEj4GVKeU72+0UqqNtwUj+Gr X-Google-Smtp-Source: AGHT+IFn7ROdpfvq4Af61VXP9NL1gvD2SbKlCYOri0wmXqQgy51gfkXMrEA0iklwvkQSiS1rBr8X0w== X-Received: by 2002:a17:902:e811:b0:1dd:da28:e5ca with SMTP id u17-20020a170902e81100b001ddda28e5camr5421423plg.0.1712422132369; Sat, 06 Apr 2024 09:48:52 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:51 -0700 (PDT) From: Kuan-Wei Chiu To: colyli@suse.de, kent.overstreet@linux.dev, msakai@redhat.com, peterz@infradead.org, mingo@redhat.com, acme@kernel.org, namhyung@kernel.org, akpm@linux-foundation.org Cc: bfoster@redhat.com, mark.rutland@arm.com, alexander.shishkin@linux.intel.com, jolsa@kernel.org, irogers@google.com, adrian.hunter@intel.com, 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 v3 15/17] lib/test_min_heap: Add test for heap_del() Date: Sun, 7 Apr 2024 00:47:25 +0800 Message-Id: <20240406164727.577914-16-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Add test cases for the min_heap_del() to ensure its functionality is thoroughly tested. Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- lib/test_min_heap.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/lib/test_min_heap.c b/lib/test_min_heap.c index 67dd4f644f6c..9d4bbb590a49 100644 --- a/lib/test_min_heap.c +++ b/lib/test_min_heap.c @@ -160,6 +160,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; @@ -170,6 +204,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 Feb 7 19:41:25 2026 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 28A494D9F5; Sat, 6 Apr 2024 16:48:57 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.171 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422140; cv=none; b=QgSgrMRzjIYy9xyxEp+TNsKAF2hPng2mnIIYzQQaP1Xp6kVyARQCQJLmdnVJA1VmaId4EthdciD/qMPm2A5nb6lfjlZr2bOtLkbRAJz8xGQRfq8R0sUu5slblGEmgVbwADwrHEAslXph9dtZIuajLP5sHmNTjTvq0waaIltHTPE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422140; c=relaxed/simple; bh=wcdtpXB0PbnqgecPm59k7MOSmCuVYxHfy+MUX111BVg=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=VKRISEZIXFe3IORzc4nm0aHDumufKzvzgAnC/mfrj9MPUf0oN1BWJGV3GHJxN+S4JvN43Rk0TbQTWg9ProXIxvwOpTB+ferREYf/Jd66py8R1BTMwT3jE/hKeN2K8PVS9q5OElyuuJZsqdIc63W05qZW56OOgPVMIi1W4K1/ifg= 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=Lwxp7l0D; arc=none smtp.client-ip=209.85.210.171 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Lwxp7l0D" Received: by mail-pf1-f171.google.com with SMTP id d2e1a72fcca58-6ea729f2e38so813089b3a.1; Sat, 06 Apr 2024 09:48:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422137; x=1713026937; 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=qYj6jFHb+C+MjLf8+OOH0efWmAy4362WY9wi7Orqq1A=; b=Lwxp7l0DufQuk62DitQswVhv+qTNH46hyc9COXEOAUerIar8QG8kJvTC3ozGJAXRYL 9lm0QM8RajG+IxXjNUtgjlawjEVlFycVxOQxv1EzHyTBQmzHHP/fjUx+8wweXJVnWiAO YOeAW8LpqUq6l4pDGOyNMJSNfliNmLuLr7jo8IXZb51tp2SXTojQ1tJukeOyxG7XxNRW 4P0km2Wl3LklsFenCB2a1khVE7IJ9C7a5igv9YTK7eSm/VwmJD1YlWQzjm3MnVH0ek2x JCX/OoT3qZ29KI8OYf5seHXnZshnUC9iS+ddphJavkNx/FU7hG6qZdTYKZ9QyL/x2EW1 2gUA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422137; x=1713026937; 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=qYj6jFHb+C+MjLf8+OOH0efWmAy4362WY9wi7Orqq1A=; b=CiMx4Ath+wQa8PeXSKyHLd5s+qhAPcf1AL0cR0sEwle7ZhWawsLFO2uKH18uIaZ3FT xRZxnVWD5WFVl+9PqvQhVqT03QKXiA2rnx9WgRQTj2daYCzlDU7Nhj/uMpSkdXWYLk1l zs9mGgY1qxGnarv/gfEgCKZCvoPn+4amT6+p/zRDmMXk82ofWr23v/BrbA3It+wREpxz JIYVWZw+NOet2MrcTpk7EE0vKL5EjUESpUNGP5v0u1yAfcgKwJljnByaIte6OmEuv9Le ze4xqV6tR9KjpmKKJ7regETgm7hfccFf3vq37I0l9W/86qPlEnHdWuPgrXMxrk4Y5qdP V5cQ== X-Forwarded-Encrypted: i=1; AJvYcCVqoHxHBH/cKdTfwySykZTlfzDu2VP/6u0mCGz3Q8+ES1KdBPxWM0YHS6EaBV0tWF2+iF3jU5qh3h4KuLz7MgABsgvAJJjUhxO8nd2NNDKSs0aUMt+pjQrgGuMAjOMJRurTiWpPzwUKk/qkD3v8CtZ1u7N4pw8YScEPBvavDuPyhj1s6uSFqCpdDWLdLBQHvSy2WpJ34QzhPwlHnhKdI7WdSfoKYhf94PT9wrSL X-Gm-Message-State: AOJu0Yzc/zijczV4RRj7iIBQKTp31A/EToZv0fJpweqeosgNwtjjgLSt +lUj6vJ9hvK98OpXFcri1bu5E1f5aGvJmCDgrSeSMh0pg/fOBaeh X-Google-Smtp-Source: AGHT+IFMT9J6wcj0gEWiH5hVy0GfyejqFkRBwX/LpzBKKZ3CFGaBQpL5SIZaP1CeJU4+a6bL7W9vcw== X-Received: by 2002:a17:902:e811:b0:1e0:c887:f93f with SMTP id u17-20020a170902e81100b001e0c887f93fmr5627529plg.1.1712422137342; Sat, 06 Apr 2024 09:48:57 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.53 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:48:56 -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 v3 16/17] bcache: Remove heap-related macros and switch to generic min_heap Date: Sun, 7 Apr 2024 00:47:26 +0800 Message-Id: <20240406164727.577914-17-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Drop the heap-related macros from bcache and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcache. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers Acked-by: Coly Li --- Changes in v3: - Correct bugs where the parameter types in some compare functions should have been 'type **', but were mistakenly written as 'type *'. 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 Feb 7 19:41:25 2026 Received: from mail-pf1-f172.google.com (mail-pf1-f172.google.com [209.85.210.172]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id ABD015D731; Sat, 6 Apr 2024 16:49:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.172 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422144; cv=none; b=giFYUbWIEA6WG2JLxcdp9R8+2aUPgag/rXYUrgKQPleHg/HrLNoG8MVkhXR+ldwv8VKKd13bE0y1Ba+v6EHxrhOJvg/JNPHBvYF0qVzrTv4nTl5ltJYGFYAt/9333DEJjau/WZWhhBlvWdH6XcPJhpzWIxMrloe41m0E60I833Y= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712422144; c=relaxed/simple; bh=h+XehoA9LdNS9hL8uunYNvcWW/80IE0+kfoE04EX+O4=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=qFyBCJEQhQw0RfpywsYSylIodiL6w923pKbZCUdCspQicCDoYJh7BV5+q3D9xD0oVjfn0M1SAhOTeXyLyM88PzhFaaWPb1U2vRWyxpnP+u9CxywO/ktjNezvqHV/0pGmxgeYauZuSGft+pg+Yf+2manz8TthiP11yiq6Ueb0cL4= 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=jov4Arrb; arc=none smtp.client-ip=209.85.210.172 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="jov4Arrb" Received: by mail-pf1-f172.google.com with SMTP id d2e1a72fcca58-6ecfea4f01cso484349b3a.0; Sat, 06 Apr 2024 09:49:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1712422142; x=1713026942; 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=vlGmXCtgzURGTERGLYtOc+iv3C8hNBiorsfShg0hSpU=; b=jov4ArrbaYUEKCSf+ZaKkwK+grIP9fx7ELV+SiLOORymN6OTZQeL8FCQGtMNflPKQY hcNhMSk7S+asDd6OIJEPWfzjdJZdyGgXSz3ekM3QIo3XLqYNp6Rksonak1Zxy+DHrgNl Jl4x4iBUFWAaVmbW9QJVf9mjzf6+jRVr6uhg3zy5RxVP1dtdF3kTxI+KjTet5Xm2O7rs mk9kF7mZDRPmYSCf2a1617VqVUmePgQHlhmkpHt+GnOmk12tqsuM874pwKfA1+t1Zm8f 7vg/SYrpfkj0xpjZsPLagdSPKYUnCtfE9PT25brXdSruzZsf7eSGWVNrMG0q1CYo7AoY plfw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712422142; x=1713026942; 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=vlGmXCtgzURGTERGLYtOc+iv3C8hNBiorsfShg0hSpU=; b=suFXB/FXjDQSI2EHf/gLOMXWdu231SbsK7riRWM0DxY51PfIRqJS+cw7KFXC5/ZRtn VcYWKx1I8Gfv5f87lOlKC4Vkob/CzVno8XUU6M/qfEm8ffcg6FkMCn03pQYgnO4DR6Dy +XxFuUm9PvvnvC3Ufg3n+ZdYMusL6J8qJzz7oQRXMS3n0o5Ou3qgo+vYHppJyMYq0oIQ t3jWr6CBSiLN3vzwKZsbFQrZaw4EU1sXVihegCP4pKxStdVi6Wcs0yK9TrnaEPyz2E9j LTQ3XQlqqZXWHACHfteN5MDLpK/DX9aoVMFLUSc7jDRnzIJXyXjQo8JZUlzi7XnoTH4t o0KA== X-Forwarded-Encrypted: i=1; AJvYcCXJ41WL2xM9i1YJrROS51GgRS1AjLvE5OyZxRFSl9eXWu01FLJHA05bnD5lnzGSQInZBGXYIQDkQT9JWEajqvc+Xy66Lo8zXDgINK2bIn+eab0igjihbbM2pbTWgIzLuPp4zo6i7WFnreqn2HwwdJke8vmOXDh3JqpnZF2JpjHw2yQ15S2AmKW+bG7hCWFW5MVsGJLnh9J2B9wgC+CZ7b5wcWiG71YvPU2Railk X-Gm-Message-State: AOJu0Yy8+TfKc6Evzd7b3b9C+OMvjmEPtAvvlFfYDAqaNbU5zNNzg+lh s01b1eB8rgAyprkzS4dBK3bC3+OzPph/bf+tSwmWyRbxbLJLlHcq X-Google-Smtp-Source: AGHT+IFCljFBOz2cdzxCQCqlN5fhikaRICtIKF/BhFfGVXGUpXsGXq1JPz2GF7MlkMaENuXBUZp3gg== X-Received: by 2002:a17:902:e5c1:b0:1e0:c91b:b950 with SMTP id u1-20020a170902e5c100b001e0c91bb950mr5608910plf.5.1712422141897; Sat, 06 Apr 2024 09:49:01 -0700 (PDT) Received: from visitorckw-System-Product-Name.. ([140.113.216.168]) by smtp.gmail.com with ESMTPSA id q14-20020a170902a3ce00b001e2b8c91f04sm3665068plb.22.2024.04.06.09.48.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 06 Apr 2024 09:49: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 v3 17/17] bcachefs: Remove heap-related macros and switch to generic min_heap Date: Sun, 7 Apr 2024 00:47:27 +0800 Message-Id: <20240406164727.577914-18-visitorckw@gmail.com> X-Mailer: git-send-email 2.34.1 In-Reply-To: <20240406164727.577914-1-visitorckw@gmail.com> References: <20240406164727.577914-1-visitorckw@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Drop the heap-related macros from bcachefs and replacing them with the generic min_heap implementation from include/linux. By doing so, code readability is improved by using functions instead of macros. Moreover, the min_heap implementation in include/linux adopts a bottom-up variation compared to the textbook version currently used in bcachefs. This bottom-up variation allows for approximately 50% reduction in the number of comparison operations during heap siftdown, without changing the number of swaps, thus making it more efficient. Link: https://lkml.kernel.org/ioyfizrzq7w7mjrqcadtzsfgpuntowtjdw5pgn4qhvsdp= 4mqqg@nrlek5vmisbu Signed-off-by: Kuan-Wei Chiu Reviewed-by: Ian Rogers --- Changes in v3: - Correct bugs where the parameter types in some compare functions should have been 'type **', but were mistakenly written as 'type *'. fs/bcachefs/clock.c | 43 ++++++++++---- fs/bcachefs/clock_types.h | 2 +- fs/bcachefs/ec.c | 76 ++++++++++++++++-------- fs/bcachefs/ec_types.h | 2 +- fs/bcachefs/util.h | 118 +------------------------------------- 5 files changed, 87 insertions(+), 154 deletions(-) diff --git a/fs/bcachefs/clock.c b/fs/bcachefs/clock.c index 363644451106..3ec64fe6a064 100644 --- a/fs/bcachefs/clock.c +++ b/fs/bcachefs/clock.c @@ -6,16 +6,29 @@ #include #include =20 -static inline long io_timer_cmp(io_timer_heap *h, - struct io_timer *l, - struct io_timer *r) +static inline bool io_timer_cmp(const void *l, const void *r, void __alway= s_unused *args) { - return l->expire - r->expire; + struct io_timer **_l =3D (struct io_timer **)l; + struct io_timer **_r =3D (struct io_timer **)r; + + return (*_l)->expire < (*_r)->expire; +} + +static inline void io_timer_swp(void *l, void *r, void __always_unused *ar= gs) +{ + struct io_timer **_l =3D (struct io_timer **)l; + struct io_timer **_r =3D (struct io_timer **)r; + + swap(*_l, *_r); } =20 void bch2_io_timer_add(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 @@ -26,11 +39,11 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) return; } =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[i] =3D=3D timer) goto out; =20 - BUG_ON(!heap_add(&clock->timers, timer, io_timer_cmp, NULL)); + BUG_ON(!min_heap_push(&clock->timers, &timer, &callbacks, NULL)); out: spin_unlock(&clock->timer_lock); } @@ -38,12 +51,16 @@ void bch2_io_timer_add(struct io_clock *clock, struct i= o_timer *timer) void bch2_io_timer_del(struct io_clock *clock, struct io_timer *timer) { size_t i; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) if (clock->timers.data[i] =3D=3D timer) { - heap_del(&clock->timers, i, io_timer_cmp, NULL); + min_heap_del(&clock->timers, i, &callbacks, NULL); break; } =20 @@ -131,12 +148,16 @@ static struct io_timer *get_expired_timer(struct io_c= lock *clock, unsigned long now) { struct io_timer *ret =3D NULL; + const struct min_heap_callbacks callbacks =3D { + .less =3D io_timer_cmp, + .swp =3D io_timer_swp, + }; =20 spin_lock(&clock->timer_lock); =20 - if (clock->timers.used && + if (clock->timers.nr && time_after_eq(now, clock->timers.data[0]->expire)) - heap_pop(&clock->timers, ret, io_timer_cmp, NULL); + min_heap_pop(&clock->timers, &callbacks, NULL); =20 spin_unlock(&clock->timer_lock); =20 @@ -161,7 +182,7 @@ void bch2_io_timers_to_text(struct printbuf *out, struc= t io_clock *clock) spin_lock(&clock->timer_lock); now =3D atomic64_read(&clock->now); =20 - for (i =3D 0; i < clock->timers.used; i++) + for (i =3D 0; i < clock->timers.nr; i++) prt_printf(out, "%ps:\t%li\n", clock->timers.data[i]->fn, clock->timers.data[i]->expire - now); diff --git a/fs/bcachefs/clock_types.h b/fs/bcachefs/clock_types.h index 5fae0012d808..59716e148645 100644 --- a/fs/bcachefs/clock_types.h +++ b/fs/bcachefs/clock_types.h @@ -23,7 +23,7 @@ struct io_timer { /* Amount to buffer up on a percpu counter */ #define IO_CLOCK_PCPU_SECTORS 128 =20 -typedef HEAP(struct io_timer *) io_timer_heap; +typedef MIN_HEAP(struct io_timer *, io_timer_heap) io_timer_heap; =20 struct io_clock { atomic64_t now; diff --git a/fs/bcachefs/ec.c b/fs/bcachefs/ec.c index 082075244e16..f2d00dd9ca33 100644 --- a/fs/bcachefs/ec.c +++ b/fs/bcachefs/ec.c @@ -866,8 +866,8 @@ static int __ec_stripe_mem_alloc(struct bch_fs *c, size= _t idx, gfp_t gfp) =20 mutex_lock(&c->ec_stripes_heap_lock); if (n.size > h->size) { - memcpy(n.data, h->data, h->used * sizeof(h->data[0])); - n.used =3D h->used; + memcpy(n.data, h->data, h->nr * sizeof(h->data[0])); + n.nr =3D h->nr; swap(*h, n); } mutex_unlock(&c->ec_stripes_heap_lock); @@ -958,7 +958,7 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) =20 lockdep_assert_held(&c->ec_stripes_heap_lock); =20 - if (h->used && + if (h->nr && h->data[0].blocks_nonempty =3D=3D 0 && !bch2_stripe_is_open(c, h->data[0].idx)) return h->data[0].idx; @@ -966,14 +966,6 @@ static u64 stripe_idx_to_delete(struct bch_fs *c) return 0; } =20 -static inline int ec_stripes_heap_cmp(ec_stripes_heap *h, - struct ec_stripe_heap_entry l, - struct ec_stripe_heap_entry r) -{ - return ((l.blocks_nonempty > r.blocks_nonempty) - - (l.blocks_nonempty < r.blocks_nonempty)); -} - static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h, size_t i) { @@ -982,39 +974,71 @@ static inline void ec_stripes_heap_set_backpointer(ec= _stripes_heap *h, genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx =3D i; } =20 +static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void = __always_unused *args) +{ + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + + return ((_l->blocks_nonempty > _r->blocks_nonempty) < + (_l->blocks_nonempty < _r->blocks_nonempty)); +} + +static inline void ec_stripes_heap_swap(void *l, void *r, void *h) +{ + struct ec_stripe_heap_entry *_l =3D (struct ec_stripe_heap_entry *)l; + struct ec_stripe_heap_entry *_r =3D (struct ec_stripe_heap_entry *)r; + ec_stripes_heap *_h =3D (ec_stripes_heap *)h; + size_t i =3D _l - _h->data; + size_t j =3D _r - _h->data; + + ec_stripes_heap_set_backpointer(_h, i); + ec_stripes_heap_set_backpointer(_h, j); + + swap(*_l, *_r); +} + static void heap_verify_backpointer(struct bch_fs *c, size_t idx) { ec_stripes_heap *h =3D &c->ec_stripes_heap; struct stripe *m =3D genradix_ptr(&c->stripes, idx); =20 - BUG_ON(m->heap_idx >=3D h->used); + BUG_ON(m->heap_idx >=3D h->nr); BUG_ON(h->data[m->heap_idx].idx !=3D idx); } =20 void bch2_stripes_heap_del(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); heap_verify_backpointer(c, idx); =20 - heap_del(&c->ec_stripes_heap, m->heap_idx, - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + min_heap_del(&c->ec_stripes_heap, m->heap_idx, &callbacks, &c->ec_stripes= _heap); mutex_unlock(&c->ec_stripes_heap_lock); } =20 void bch2_stripes_heap_insert(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; + mutex_lock(&c->ec_stripes_heap_lock); - BUG_ON(heap_full(&c->ec_stripes_heap)); + BUG_ON(min_heap_full(&c->ec_stripes_heap)); =20 - heap_add(&c->ec_stripes_heap, ((struct ec_stripe_heap_entry) { + genradix_ptr(&c->stripes, idx)->heap_idx =3D c->ec_stripes_heap.nr; + min_heap_push(&c->ec_stripes_heap, &((struct ec_stripe_heap_entry) { .idx =3D idx, .blocks_nonempty =3D m->blocks_nonempty, }), - ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + &callbacks, + &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); mutex_unlock(&c->ec_stripes_heap_lock); @@ -1023,6 +1047,10 @@ void bch2_stripes_heap_insert(struct bch_fs *c, void bch2_stripes_heap_update(struct bch_fs *c, struct stripe *m, size_t idx) { + const struct min_heap_callbacks callbacks =3D { + .less =3D ec_stripes_heap_cmp, + .swp =3D ec_stripes_heap_swap, + }; ec_stripes_heap *h =3D &c->ec_stripes_heap; bool do_deletes; size_t i; @@ -1033,10 +1061,8 @@ void bch2_stripes_heap_update(struct bch_fs *c, h->data[m->heap_idx].blocks_nonempty =3D m->blocks_nonempty; =20 i =3D m->heap_idx; - heap_sift_up(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); - heap_sift_down(h, i, ec_stripes_heap_cmp, - ec_stripes_heap_set_backpointer); + min_heap_sift_up(h, i, &callbacks, &c->ec_stripes_heap); + min_heap_sift_down(h, i, &callbacks, &c->ec_stripes_heap); =20 heap_verify_backpointer(c, idx); =20 @@ -1828,7 +1854,7 @@ static s64 get_existing_stripe(struct bch_fs *c, return -1; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (heap_idx =3D 0; heap_idx < h->used; heap_idx++) { + for (heap_idx =3D 0; heap_idx < h->nr; heap_idx++) { /* No blocks worth reusing, stripe will just be deleted: */ if (!h->data[heap_idx].blocks_nonempty) continue; @@ -2159,7 +2185,7 @@ void bch2_stripes_heap_to_text(struct printbuf *out, = struct bch_fs *c) size_t i; =20 mutex_lock(&c->ec_stripes_heap_lock); - for (i =3D 0; i < min_t(size_t, h->used, 50); i++) { + for (i =3D 0; i < min_t(size_t, h->nr, 50); i++) { m =3D genradix_ptr(&c->stripes, h->data[i].idx); =20 prt_printf(out, "%zu %u/%u+%u", h->data[i].idx, diff --git a/fs/bcachefs/ec_types.h b/fs/bcachefs/ec_types.h index 976426da3a12..2ed67431a81c 100644 --- a/fs/bcachefs/ec_types.h +++ b/fs/bcachefs/ec_types.h @@ -36,6 +36,6 @@ struct ec_stripe_heap_entry { unsigned blocks_nonempty; }; =20 -typedef HEAP(struct ec_stripe_heap_entry) ec_stripes_heap; +typedef MIN_HEAP(struct ec_stripe_heap_entry, ec_stripes_heap) ec_stripes_= heap; =20 #endif /* _BCACHEFS_EC_TYPES_H */ diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h index b7e7c29278fc..9757c2c1218e 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