From patchwork Fri Mar 1 05:36:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 208653 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2097:b0:108:e6aa:91d0 with SMTP id gs23csp876042dyb; Thu, 29 Feb 2024 21:37:42 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCWLAauR+1ddACXx2JgB5sG1khiUoQX7IBMmD2TOYI1slrEcelg7GP6QD7xmCbs0p5QjAlwsSVbBKn0TV9FoNb0cVUDqvQ== X-Google-Smtp-Source: AGHT+IFjYOvwGIiaHQno6Rgftp+tAcRmwXao1pZwGYsmDDAyqWLj4+i6xXTnGRyGQaeo6fEMkzd4 X-Received: by 2002:a05:622a:243:b0:42e:c2fd:5748 with SMTP id c3-20020a05622a024300b0042ec2fd5748mr883602qtx.0.1709271462408; Thu, 29 Feb 2024 21:37:42 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709271462; cv=pass; d=google.com; s=arc-20160816; b=QoVVhoCdK9ckZNEySsuWR+dRDPUnbg5NZPvjlin6qCJk5Mf/fnUVYfDmXVTUE/Xq1y d5H6UnXN9wV97l3IxNKLlYkhHz45gxBoyswbgb0rcCU5rFM1h7G+3nkjD31xSFoQbiGf 4iRW04laV2okhTQ1eoVxkvDDmKnIQF1o8J1GabDROOCqo1UzEh+2ZTvZl7WAEuZG9K7z U6irvkQ5rBqtBLBhGlsOLSYrkf8vr4dEDpFXl6z5136g/z2sujiaQwh5Lsl9AVpDL6G2 xvK+QwfZ4oD1hpn4uhyzHkESkHdOtMw0ciUIlgmEMAg0SHB+Pok29EyK4faLhuUqS3xc Ow6g== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=eHNbX5Xyi/VqeebJOw+lK9eWaYZye24FQe0AyXZlgyM=; fh=mCzYfL24NoKdYsbJOTqLao+z/Jx0C5ajeSi6DF0yKD8=; b=TRzU7bteH/HsSBSn/aFJEyN0BXKJHmuGjiKEwF6F1abC4DT1mPumV8Nt0G9ZAeDrZQ ZEr/09B0esCiQYlZ3oNTe5rdQM1Wnl1eNTedsK8xwtOGhM9hXv+QSbZZoIcouSP6cIBo S5+zXHCur+84j5ZIelMEnyj+mJIn2ZTzc8cttjOBRZoakD7DAq7KlGF3iZNJGfnsPryp hVQXgJwbTdJ9b5v1hOxuayMaqdV1SGSAVt307Bj3vSehmww2pwxTSucuRY0tbdgR3nT6 PEk7FoFLoe/jwM1cNwVIOCLoCsrWEq6X5xaRGPsNZru829UvBDJDHKIbkGqptEWBe0Nc UEtQ==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="yN7KMJk/"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87931-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87931-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id j12-20020ac85c4c000000b0042eb87223bdsi3178791qtj.621.2024.02.29.21.37.42 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Feb 2024 21:37:42 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-87931-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="yN7KMJk/"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87931-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87931-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id 008461C20FF8 for ; Fri, 1 Mar 2024 05:37:42 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 68EFE537E3; Fri, 1 Mar 2024 05:37:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="yN7KMJk/" Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) (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 B48AE524DC for ; Fri, 1 Mar 2024 05:36:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271418; cv=none; b=Efr6sdheOtF3iqmS8mAQBxWx5DgFQk4OFMV+UWd8sFzlXFUlh07UYfdvwj2QKNf6z2URytk3CYWxbms54GT/Xi2sJZZV6funUqJ9xYvw/Rmbnvf8W5HHgy1YZTwe0U1zaCNTeqkC+6Q6x6AXnLYjYa+ooBOpz8pkhHNsVCfEHt4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271418; c=relaxed/simple; bh=soASIs7D8iQcX2U2s2M4JC6RaqIvyHatWg6UktdKnSI=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=H4YqecEeGXRwKqR43M6kApAMjx05amQfi3IonNhTM2nGocxWUURPlTTI1rp4eLRwrOzoHBoObMkfkVSKZCX5X4Y7PpihUwaH5HgyLgLClrvjzX1hsAW9YIyWRRZjVSvx5AYY+sZ9umzpXlWLkUSwB7/7Gy3MYJaMdy8j+/o2AJU= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=yN7KMJk/; arc=none smtp.client-ip=209.85.128.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-607e8e8c2f1so29944327b3.3 for ; Thu, 29 Feb 2024 21:36:56 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709271416; x=1709876216; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=eHNbX5Xyi/VqeebJOw+lK9eWaYZye24FQe0AyXZlgyM=; b=yN7KMJk/IHZ+SdUXNslVSy2elnT6d/xwvd0JH4r6vu66eSR5ydG4HVIi75O3BlwTNL Uwbo94ENq5eW5S90oqq09DQW7csC+fcbD8dqOhDKP+bAdOquKxYNlDsJ31AA4iWYxHpY W1D5+P9j0ImqaXsUgkbPKGJg5swOOEbWF1oFAqSRG8eOem/TFaqy555JwMvYf7qncDJW mI5KM92xfgaLSUDX+B0xaPBjQxAs6Q7kDh8IO3LLUEfRQIlmdfWFnw3ZChKthuNRBMV3 c4dy8zILmVp+xFYbA4kvg5SYvHtRNbJbPpYaBYqmP8yn3yAQfZ6+1nc3fNnWEp54qiX1 teIA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709271416; x=1709876216; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=eHNbX5Xyi/VqeebJOw+lK9eWaYZye24FQe0AyXZlgyM=; b=FTPQegILu1gsxmPtnbo4EjqimJSzQCvc5wJFw5Z7bxQNW9THP0RdOV6URwq9sPaKKV 9Dwu3f1PRU+KH9d692AJnwDOf2fEJA+icVTu5iPAJMRl/uxslgEPhVbmM5AAneXV2mpN ic+t1R+kFbh2ebQZlk5O/sS2Jqrdbu1nz/Y/oc47CfSy41FJaEIBAu0ONDkyOlfc+U+N KwOdilSyFU0zQXwps7DoWR8kn6heEgTqs22cNLMtxv3+2cglRD/XhxQVDkxZ0hCsuGlJ R4GTz5fg7CHA20gdaj6KonnUWAhs3oRU8c3bg4FNLEdTz8SEfGiWbUJYdjYs853eInNF qcww== X-Forwarded-Encrypted: i=1; AJvYcCVEjQUkwaoFf60f18mIiWN2g8XZwfKrj5XqWUM8GMVyUq5tuKdBtvXTBYApCYY1mT/tRcimS+jUYNkH+1e05OFKBWof0zv8XJMg6rMh X-Gm-Message-State: AOJu0YywelTtjFm9mOf7gs7neqOj8bxSnglr9EfU9Egzy3yUOYM1vE7W nJh6D0qAZIGl9yszksspJamhRmIaUi1aG1MVWuEGfb0ZM48w+NgNNUedKS/bpySo2SEaeiNKeZ5 yExcXpQ== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:af4b:7fc1:b7be:fcb7]) (user=irogers job=sendgmr) by 2002:a81:9950:0:b0:609:4d6f:7c0b with SMTP id q77-20020a819950000000b006094d6f7c0bmr114933ywg.4.1709271415925; Thu, 29 Feb 2024 21:36:55 -0800 (PST) Date: Thu, 29 Feb 2024 21:36:40 -0800 In-Reply-To: <20240301053646.1449657-1-irogers@google.com> Message-Id: <20240301053646.1449657-3-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240301053646.1449657-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.278.ge034bb2e1d-goog Subject: [PATCH v4 2/7] perf trace: Ignore thread hashing in summary From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Oliver Upton , Yang Jihong , linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1792301032473406744 X-GMAIL-MSGID: 1792301032473406744 Commit 91e467bc568f ("perf machine: Use hashtable for machine threads") made the iteration of thread tids unordered. The perf trace --summary output sorts and prints each hash bucket, rather than all threads globally. Change this behavior by turn all threads into a list, sort the list by number of trace events then by tids, finally print the list. This also allows the rbtree in threads to be not accessed outside of machine. Signed-off-by: Ian Rogers --- tools/perf/builtin-trace.c | 41 +++++++++++++++++++++---------------- tools/perf/util/rb_resort.h | 5 ----- 2 files changed, 23 insertions(+), 23 deletions(-) diff --git a/tools/perf/builtin-trace.c b/tools/perf/builtin-trace.c index 109b8e64fe69..90eaff8c0f6e 100644 --- a/tools/perf/builtin-trace.c +++ b/tools/perf/builtin-trace.c @@ -74,6 +74,7 @@ #include #include #include +#include #include #include #include @@ -4312,34 +4313,38 @@ static unsigned long thread__nr_events(struct thread_trace *ttrace) return ttrace ? ttrace->nr_events : 0; } -DEFINE_RESORT_RB(threads, - (thread__nr_events(thread__priv(a->thread)) < - thread__nr_events(thread__priv(b->thread))), - struct thread *thread; -) +static int trace_nr_events_cmp(void *priv __maybe_unused, + const struct list_head *la, + const struct list_head *lb) { - entry->thread = rb_entry(nd, struct thread_rb_node, rb_node)->thread; + struct thread_list *a = list_entry(la, struct thread_list, list); + struct thread_list *b = list_entry(lb, struct thread_list, list); + unsigned long a_nr_events = thread__nr_events(thread__priv(a->thread)); + unsigned long b_nr_events = thread__nr_events(thread__priv(b->thread)); + + if (a_nr_events != b_nr_events) + return a_nr_events < b_nr_events ? -1 : 1; + + /* Identical number of threads, place smaller tids first. */ + return thread__tid(a->thread) < thread__tid(b->thread) + ? -1 + : (thread__tid(a->thread) > thread__tid(b->thread) ? 1 : 0); } static size_t trace__fprintf_thread_summary(struct trace *trace, FILE *fp) { size_t printed = trace__fprintf_threads_header(fp); - struct rb_node *nd; - int i; - - for (i = 0; i < THREADS__TABLE_SIZE; i++) { - DECLARE_RESORT_RB_MACHINE_THREADS(threads, trace->host, i); + LIST_HEAD(threads); - if (threads == NULL) { - fprintf(fp, "%s", "Error sorting output by nr_events!\n"); - return 0; - } + if (machine__thread_list(trace->host, &threads) == 0) { + struct thread_list *pos; - resort_rb__for_each_entry(nd, threads) - printed += trace__fprintf_thread(fp, threads_entry->thread, trace); + list_sort(NULL, &threads, trace_nr_events_cmp); - resort_rb__delete(threads); + list_for_each_entry(pos, &threads, list) + printed += trace__fprintf_thread(fp, pos->thread, trace); } + thread_list__delete(&threads); return printed; } diff --git a/tools/perf/util/rb_resort.h b/tools/perf/util/rb_resort.h index 376e86cb4c3c..d927a0d25052 100644 --- a/tools/perf/util/rb_resort.h +++ b/tools/perf/util/rb_resort.h @@ -143,9 +143,4 @@ struct __name##_sorted *__name = __name##_sorted__new DECLARE_RESORT_RB(__name)(&__ilist->rblist.entries.rb_root, \ __ilist->rblist.nr_entries) -/* For 'struct machine->threads' */ -#define DECLARE_RESORT_RB_MACHINE_THREADS(__name, __machine, hash_bucket) \ - DECLARE_RESORT_RB(__name)(&__machine->threads[hash_bucket].entries.rb_root, \ - __machine->threads[hash_bucket].nr) - #endif /* _PERF_RESORT_RB_H_ */ From patchwork Fri Mar 1 05:36:42 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 208654 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2097:b0:108:e6aa:91d0 with SMTP id gs23csp876261dyb; Thu, 29 Feb 2024 21:38:34 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUA5KA+ULQXZTpvE2JOvbqp11+SYk6MGiO4adMXrF1jxgT7e9zfT6sT8gmzjlbO6XDC4ZC0tsP18I+3Xljx9NdzdBZAfw== X-Google-Smtp-Source: AGHT+IER82HXirPK5mYLydZzxyynYaiOrpb9bky+n2rz7ThXiPWoPEGLsHJrpgmwisT64pc9DeAZ X-Received: by 2002:a05:6402:1ac9:b0:565:7ce5:abdc with SMTP id ba9-20020a0564021ac900b005657ce5abdcmr359973edb.10.1709271514649; Thu, 29 Feb 2024 21:38:34 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709271514; cv=pass; d=google.com; s=arc-20160816; b=Tv13sPzNE6gezroBsGsWfd0CDNiGAlckGgJ3v/lr+ywQ4wsTaH/HJO17nJ5Lck/xJ6 NA3jdFHP9881IZodLKQ7AW3hKVE8tYj77+d0zSAN/B9t4LBh6CwWpmQonTvZk2cdI83t +53wZCpb1XtLQFCrTGr0PeQtMPony9zN1e+7qQIzzvLf4uYSJCeoFudAWgXUM0vbbCUM /Fwi1Mhvimj9ySzLp2puJ+veK2jDYrgdI1iRpK2Sdyl3EKgjr+6hWjjgvWKgxSaYz39v CBEf64LtFQKBRtqXkB6TUgKOKyEv/rtdpV335eMMjLkIHeuuIl4ACCCdFh3JSnNae/u/ cHNg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=Yj/vjiBWUOYkXpVUJ7tJ/QYC18JIl7FM2VJjItok3Cs=; fh=Ia2uuOcNXs3bZKmJWO2v5+F7bCTbcCKQmLz0d76PaGg=; b=NS5TV+6jiLj6Ymf5HEFS4GkXelO1zeabqCJ9sZAooXSjF2QQKyyalOwC2DnE+xTLZs LuVbqilGGUHgkrrzjOrS96MaNZo/BGO4CEEOkiFbCCEstdywdOeaJU6IZR5yV8xEgLQN kdQ29u94jtOkflTNq7bsttyqVoL1/G9ZfPcWmDkLx2KTu0ASJ591Kr8n4z6bmTfc/2iX hBIfpTyXneHpN2Uq03df021RKlURuJYRd7hFoQ7voxzF+dxhsU0wI15fWjSQbj0I6tz2 0CJEHnRCNqpb0VvWzwr+X480rWWL0LMsKl26mkOZKEyoe2KaInDNAb4hICFwye/Mpim7 bl2Q==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=20uIoqtE; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87933-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87933-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [2604:1380:4601:e00::3]) by mx.google.com with ESMTPS id b89-20020a509f62000000b00566d6cfda92si152615edf.475.2024.02.29.21.38.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Feb 2024 21:38:34 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-87933-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=20uIoqtE; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87933-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87933-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id 10EEF1F22F5A for ; Fri, 1 Mar 2024 05:38:34 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id A95CF55C36; Fri, 1 Mar 2024 05:37:10 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="20uIoqtE" Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (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 B70A7537F0 for ; Fri, 1 Mar 2024 05:37:01 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271423; cv=none; b=Qk3g4iX68vefml2MOLGEjJnVT2twNBj9kAs7xMA1fnblJxXdRIRXJUB5ZTuUQXboxwC8GUWLnA1+f22waVryIEgfuZ1FDyCToPlsviXhubBxLGA8W9RXHMIVmxhZJ+c0XAQfKFr4tGcD43c15Rm8QTf7VF0VL1zHGvpFsiud9yw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271423; c=relaxed/simple; bh=fBqMdgvBqvnAASN42/FlvI+/RXHkBdraQJ/XUtdnEI0=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=e8P+g6wfvrYWkeS7KnqArE/Igujv+cwYLECS4usibdge7cKnkVcopPEO2Vnx48N2iIOAj8GdH/eXRcmC5gn2qB49Rg1pJPFp3feI8efd9gJaeP4mHhKYPoBtdHyfiTl3EO4zev8hsiEJVAboXWs2pQ3PQvhQ++x8MF8GGds88F0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=20uIoqtE; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-dc6ceade361so2986939276.0 for ; Thu, 29 Feb 2024 21:37:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709271421; x=1709876221; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=Yj/vjiBWUOYkXpVUJ7tJ/QYC18JIl7FM2VJjItok3Cs=; b=20uIoqtEdLVwH+SH8ZxBPQ7FRu6fI9GkAKR9aNsJ02ebh/7o5oiRHK5jF73gBjaUDA IeuSkQkRoQladik3h/BY+YQppf/B5NJ2fZ2dVfrPRTaKG9MlvZfLbkZ7w5T+pSx7pbTh thMNTKFKJziDC3DCqK9MbubSabryixtoyRCOloLdrQbJ93C93aIbJBk8bk3JwjM1v3j2 /s1L36ssMu9w6bw/8wBjyukND9CGlsqhkMV5qeZ0lezyJhV/TLVsMqPYloiBPY9PTnLR VnSxI7zDVro2TjDno+mxTqxc/K/yY3mMAG86JmaD9iVuFWLpYGrPQglFQMFlX19yNKur FPWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709271421; x=1709876221; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=Yj/vjiBWUOYkXpVUJ7tJ/QYC18JIl7FM2VJjItok3Cs=; b=PMm6BkMPBQ3ALxq1b9EEPuSAUWnLuIaQI4DGkO7Yf4SvMdA6BYwhbqaKS79sjWcEGB G/Vuvkj4CeU6db4D4xHx8FArEGfQF9BZGu7wrFbJ1gx/oDXoJ3djORmVW2+xIYMllO3b zC14JIl2Cj6ltsHRN1uhLZVDwK/oP6wvDjEC0wj4zTzXRqX+SvO5lWSD26nIMeFGZzhM wxf9Hq6G9DnC84zw00GweT4AfP1X4QuL/nML6qJk9hz49hmOwWICD4NGPl2IoWmhAEEK yZALskzAaNU/dgh35063gPf7cLKVZ8Vw5ce0/GT592APEsOKTN1UiVVQuQtxmh/wObia iEfA== X-Forwarded-Encrypted: i=1; AJvYcCWcLfGJBDHjgjVYcnNKY/y9G2BRQImvqLTnKjhFmQA0g2GGhcPDLuDPGdnb3K/liJsVkXFHXwgpH8e3TxD/oa1kheTTViDyboIMpr73 X-Gm-Message-State: AOJu0YxJNOSZOueDeaM+aXO68l1cATEc2H03qfvGXwLEjK/WT35oB04q akIm8kC2H2iatX2rzBDcYoH2doKJE5wxlMzlcA5j3zi/pA3Oo35Jc9UyjczxEwRCoZ4a5dEBOzn ensvY5w== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:af4b:7fc1:b7be:fcb7]) (user=irogers job=sendgmr) by 2002:a05:6902:100a:b0:dc7:5aad:8965 with SMTP id w10-20020a056902100a00b00dc75aad8965mr157192ybt.0.1709271420887; Thu, 29 Feb 2024 21:37:00 -0800 (PST) Date: Thu, 29 Feb 2024 21:36:42 -0800 In-Reply-To: <20240301053646.1449657-1-irogers@google.com> Message-Id: <20240301053646.1449657-5-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240301053646.1449657-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.278.ge034bb2e1d-goog Subject: [PATCH v4 4/7] perf machine: Move machine's threads into its own abstraction From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Oliver Upton , Yang Jihong , linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1792301087779192162 X-GMAIL-MSGID: 1792301087779192162 Move thread_rb_node into the machine.c file. This hides the implementation of threads from the rest of the code allowing for it to be refactored. Locking discipline is tightened up in this change. As the lock is now encapsulated in threads, the findnew function requires holding it (as it already did in machine). Rather than do conditionals with locks based on whether the thread should be created (which could potentially be error prone with a read lock match with a write unlock), have a separate threads__find that won't create the thread and only holds the read lock. This effectively duplicates the findnew logic, with the existing findnew logic only operating under a write lock assuming creation is necessary as a previous find failed. The creation may still fail with the write lock due to another thread. The duplication is removed in a later next patch that delegates the implementation to hashtable. Signed-off-by: Ian Rogers --- tools/perf/util/bpf_lock_contention.c | 4 +- tools/perf/util/machine.c | 408 ++++++++++++++------------ tools/perf/util/machine.h | 26 +- tools/perf/util/thread.c | 2 +- tools/perf/util/thread.h | 6 - 5 files changed, 243 insertions(+), 203 deletions(-) diff --git a/tools/perf/util/bpf_lock_contention.c b/tools/perf/util/bpf_lock_contention.c index 3549180c7885..b4cb3fe5cc25 100644 --- a/tools/perf/util/bpf_lock_contention.c +++ b/tools/perf/util/bpf_lock_contention.c @@ -328,7 +328,7 @@ static const char *lock_contention_get_name(struct lock_contention *con, /* do not update idle comm which contains CPU number */ if (pid) { - struct thread *t = __machine__findnew_thread(machine, /*pid=*/-1, pid); + struct thread *t = machine__findnew_thread(machine, /*pid=*/-1, pid); if (t == NULL) return name; @@ -422,7 +422,7 @@ int lock_contention_read(struct lock_contention *con) account_end_timestamp(con); if (con->aggr_mode == LOCK_AGGR_TASK) { - struct thread *idle = __machine__findnew_thread(machine, + struct thread *idle = machine__findnew_thread(machine, /*pid=*/0, /*tid=*/0); thread__set_comm(idle, "swapper", /*timestamp=*/0); diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index e072b2115b64..224b53b4bfe2 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -43,8 +43,16 @@ #include #include -static void __machine__remove_thread(struct machine *machine, struct thread_rb_node *nd, - struct thread *th, bool lock); +struct thread_rb_node { + struct rb_node rb_node; + struct thread *thread; +}; + +static struct threads_table_entry *threads__table(struct threads *threads, pid_t tid) +{ + /* Cast it to handle tid == -1 */ + return &threads->table[(unsigned int)tid % THREADS__TABLE_SIZE]; +} static struct dso *machine__kernel_dso(struct machine *machine) { @@ -58,35 +66,18 @@ static void dsos__init(struct dsos *dsos) init_rwsem(&dsos->lock); } -static void machine__threads_init(struct machine *machine) +void threads__init(struct threads *threads) { - int i; + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; - for (i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads *threads = &machine->threads[i]; - threads->entries = RB_ROOT_CACHED; - init_rwsem(&threads->lock); - threads->nr = 0; - threads->last_match = NULL; + table->entries = RB_ROOT_CACHED; + init_rwsem(&table->lock); + table->nr = 0; + table->last_match = NULL; } } -static int thread_rb_node__cmp_tid(const void *key, const struct rb_node *nd) -{ - int to_find = (int) *((pid_t *)key); - - return to_find - (int)thread__tid(rb_entry(nd, struct thread_rb_node, rb_node)->thread); -} - -static struct thread_rb_node *thread_rb_node__find(const struct thread *th, - struct rb_root *tree) -{ - pid_t to_find = thread__tid(th); - struct rb_node *nd = rb_find(&to_find, tree, thread_rb_node__cmp_tid); - - return rb_entry(nd, struct thread_rb_node, rb_node); -} - static int machine__set_mmap_name(struct machine *machine) { if (machine__is_host(machine)) @@ -120,7 +111,7 @@ int machine__init(struct machine *machine, const char *root_dir, pid_t pid) RB_CLEAR_NODE(&machine->rb_node); dsos__init(&machine->dsos); - machine__threads_init(machine); + threads__init(&machine->threads); machine->vdso_info = NULL; machine->env = NULL; @@ -219,29 +210,51 @@ static void dsos__exit(struct dsos *dsos) exit_rwsem(&dsos->lock); } -void machine__delete_threads(struct machine *machine) +static void __threads_table_entry__set_last_match(struct threads_table_entry *table, + struct thread *th); + +void threads__remove_all_threads(struct threads *threads) { - struct rb_node *nd; - int i; + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + struct rb_node *nd; - for (i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads *threads = &machine->threads[i]; - down_write(&threads->lock); - nd = rb_first_cached(&threads->entries); + down_write(&table->lock); + __threads_table_entry__set_last_match(table, NULL); + nd = rb_first_cached(&table->entries); while (nd) { struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); nd = rb_next(nd); - __machine__remove_thread(machine, trb, trb->thread, false); + thread__put(trb->thread); + rb_erase_cached(&trb->rb_node, &table->entries); + RB_CLEAR_NODE(&trb->rb_node); + --table->nr; + + free(trb); } - up_write(&threads->lock); + assert(table->nr == 0); + up_write(&table->lock); } } -void machine__exit(struct machine *machine) +void machine__delete_threads(struct machine *machine) { - int i; + threads__remove_all_threads(&machine->threads); +} + +void threads__exit(struct threads *threads) +{ + threads__remove_all_threads(threads); + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + + exit_rwsem(&table->lock); + } +} +void machine__exit(struct machine *machine) +{ if (machine == NULL) return; @@ -254,12 +267,7 @@ void machine__exit(struct machine *machine) zfree(&machine->current_tid); zfree(&machine->kallsyms_filename); - machine__delete_threads(machine); - for (i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads *threads = &machine->threads[i]; - - exit_rwsem(&threads->lock); - } + threads__exit(&machine->threads); } void machine__delete(struct machine *machine) @@ -526,7 +534,7 @@ static void machine__update_thread_pid(struct machine *machine, if (thread__pid(th) == thread__tid(th)) return; - leader = __machine__findnew_thread(machine, thread__pid(th), thread__pid(th)); + leader = machine__findnew_thread(machine, thread__pid(th), thread__pid(th)); if (!leader) goto out_err; @@ -565,78 +573,88 @@ static void machine__update_thread_pid(struct machine *machine, * so most of the time we dont have to look up * the full rbtree: */ -static struct thread* -__threads__get_last_match(struct threads *threads, struct machine *machine, - int pid, int tid) +static struct thread *__threads_table_entry__get_last_match(struct threads_table_entry *table, + pid_t tid) { - struct thread *th; + struct thread *th, *res = NULL; - th = threads->last_match; + th = table->last_match; if (th != NULL) { - if (thread__tid(th) == tid) { - machine__update_thread_pid(machine, th, pid); - return thread__get(th); - } - thread__put(threads->last_match); - threads->last_match = NULL; + if (thread__tid(th) == tid) + res = thread__get(th); } - - return NULL; + return res; } -static struct thread* -threads__get_last_match(struct threads *threads, struct machine *machine, - int pid, int tid) +static void __threads_table_entry__set_last_match(struct threads_table_entry *table, + struct thread *th) { - struct thread *th = NULL; - - if (perf_singlethreaded) - th = __threads__get_last_match(threads, machine, pid, tid); - - return th; + thread__put(table->last_match); + table->last_match = thread__get(th); } -static void -__threads__set_last_match(struct threads *threads, struct thread *th) +static void threads_table_entry__set_last_match(struct threads_table_entry *table, + struct thread *th) { - thread__put(threads->last_match); - threads->last_match = thread__get(th); + down_write(&table->lock); + __threads_table_entry__set_last_match(table, th); + up_write(&table->lock); } -static void -threads__set_last_match(struct threads *threads, struct thread *th) +struct thread *threads__find(struct threads *threads, pid_t tid) { - if (perf_singlethreaded) - __threads__set_last_match(threads, th); + struct threads_table_entry *table = threads__table(threads, tid); + struct rb_node **p; + struct thread *res = NULL; + + down_read(&table->lock); + res = __threads_table_entry__get_last_match(table, tid); + if (res) + return res; + + p = &table->entries.rb_root.rb_node; + while (*p != NULL) { + struct rb_node *parent = *p; + struct thread *th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; + + if (thread__tid(th) == tid) { + res = thread__get(th); + break; + } + + if (tid < thread__tid(th)) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + up_read(&table->lock); + if (res) + threads_table_entry__set_last_match(table, res); + return res; } -/* - * Caller must eventually drop thread->refcnt returned with a successful - * lookup/new thread inserted. - */ -static struct thread *____machine__findnew_thread(struct machine *machine, - struct threads *threads, - pid_t pid, pid_t tid, - bool create) +struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created) { - struct rb_node **p = &threads->entries.rb_root.rb_node; + struct threads_table_entry *table = threads__table(threads, tid); + struct rb_node **p; struct rb_node *parent = NULL; - struct thread *th; + struct thread *res = NULL; struct thread_rb_node *nd; bool leftmost = true; - th = threads__get_last_match(threads, machine, pid, tid); - if (th) - return th; - + *created = false; + down_write(&table->lock); + p = &table->entries.rb_root.rb_node; while (*p != NULL) { + struct thread *th; + parent = *p; th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; if (thread__tid(th) == tid) { - threads__set_last_match(threads, th); - machine__update_thread_pid(machine, th, pid); - return thread__get(th); + __threads_table_entry__set_last_match(table, th); + res = thread__get(th); + goto out_unlock; } if (tid < thread__tid(th)) @@ -646,74 +664,76 @@ static struct thread *____machine__findnew_thread(struct machine *machine, leftmost = false; } } + nd = malloc(sizeof(*nd)); + if (nd == NULL) + goto out_unlock; + res = thread__new(pid, tid); + if (!res) + free(nd); + else { + *created = true; + nd->thread = thread__get(res); + rb_link_node(&nd->rb_node, parent, p); + rb_insert_color_cached(&nd->rb_node, &table->entries, leftmost); + ++table->nr; + __threads_table_entry__set_last_match(table, res); + } +out_unlock: + up_write(&table->lock); + return res; +} - if (!create) - return NULL; - - th = thread__new(pid, tid); - if (th == NULL) - return NULL; +/* + * Caller must eventually drop thread->refcnt returned with a successful + * lookup/new thread inserted. + */ +static struct thread *__machine__findnew_thread(struct machine *machine, + pid_t pid, + pid_t tid, + bool create) +{ + struct thread *th = threads__find(&machine->threads, tid); + bool created; - nd = malloc(sizeof(*nd)); - if (nd == NULL) { - thread__put(th); - return NULL; + if (th) { + machine__update_thread_pid(machine, th, pid); + return th; } - nd->thread = th; - rb_link_node(&nd->rb_node, parent, p); - rb_insert_color_cached(&nd->rb_node, &threads->entries, leftmost); - /* - * We have to initialize maps separately after rb tree is updated. - * - * The reason is that we call machine__findnew_thread within - * thread__init_maps to find the thread leader and that would screwed - * the rb tree. - */ - if (thread__init_maps(th, machine)) { - pr_err("Thread init failed thread %d\n", pid); - rb_erase_cached(&nd->rb_node, &threads->entries); - RB_CLEAR_NODE(&nd->rb_node); - free(nd); - thread__put(th); + if (!create) return NULL; - } - /* - * It is now in the rbtree, get a ref - */ - threads__set_last_match(threads, th); - ++threads->nr; - return thread__get(th); -} + th = threads__findnew(&machine->threads, pid, tid, &created); + if (created) { + /* + * We have to initialize maps separately after rb tree is + * updated. + * + * The reason is that we call machine__findnew_thread within + * thread__init_maps to find the thread leader and that would + * screwed the rb tree. + */ + if (thread__init_maps(th, machine)) { + pr_err("Thread init failed thread %d\n", pid); + threads__remove(&machine->threads, th); + thread__put(th); + return NULL; + } + } else + machine__update_thread_pid(machine, th, pid); -struct thread *__machine__findnew_thread(struct machine *machine, pid_t pid, pid_t tid) -{ - return ____machine__findnew_thread(machine, machine__threads(machine, tid), pid, tid, true); + return th; } -struct thread *machine__findnew_thread(struct machine *machine, pid_t pid, - pid_t tid) +struct thread *machine__findnew_thread(struct machine *machine, pid_t pid, pid_t tid) { - struct threads *threads = machine__threads(machine, tid); - struct thread *th; - - down_write(&threads->lock); - th = __machine__findnew_thread(machine, pid, tid); - up_write(&threads->lock); - return th; + return __machine__findnew_thread(machine, pid, tid, /*create=*/true); } struct thread *machine__find_thread(struct machine *machine, pid_t pid, pid_t tid) { - struct threads *threads = machine__threads(machine, tid); - struct thread *th; - - down_read(&threads->lock); - th = ____machine__findnew_thread(machine, threads, pid, tid, false); - up_read(&threads->lock); - return th; + return __machine__findnew_thread(machine, pid, tid, /*create=*/false); } /* @@ -1127,13 +1147,17 @@ static int machine_fprintf_cb(struct thread *thread, void *data) return 0; } -static size_t machine__threads_nr(const struct machine *machine) +size_t threads__nr(struct threads *threads) { size_t nr = 0; - for (int i = 0; i < THREADS__TABLE_SIZE; i++) - nr += machine->threads[i].nr; + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + down_read(&table->lock); + nr += table->nr; + up_read(&table->lock); + } return nr; } @@ -1143,7 +1167,7 @@ size_t machine__fprintf(struct machine *machine, FILE *fp) .fp = fp, .printed = 0, }; - size_t ret = fprintf(fp, "Threads: %zu\n", machine__threads_nr(machine)); + size_t ret = fprintf(fp, "Threads: %zu\n", threads__nr(&machine->threads)); machine__for_each_thread(machine, machine_fprintf_cb, &args); return ret + args.printed; @@ -2069,36 +2093,42 @@ int machine__process_mmap_event(struct machine *machine, union perf_event *event return 0; } -static void __machine__remove_thread(struct machine *machine, struct thread_rb_node *nd, - struct thread *th, bool lock) +void threads__remove(struct threads *threads, struct thread *thread) { - struct threads *threads = machine__threads(machine, thread__tid(th)); - - if (!nd) - nd = thread_rb_node__find(th, &threads->entries.rb_root); + struct rb_node **p; + struct threads_table_entry *table = threads__table(threads, thread__tid(thread)); + pid_t tid = thread__tid(thread); - if (threads->last_match && RC_CHK_EQUAL(threads->last_match, th)) - threads__set_last_match(threads, NULL); + down_write(&table->lock); + if (table->last_match && RC_CHK_EQUAL(table->last_match, thread)) + __threads_table_entry__set_last_match(table, NULL); - if (lock) - down_write(&threads->lock); - - BUG_ON(refcount_read(thread__refcnt(th)) == 0); - - thread__put(nd->thread); - rb_erase_cached(&nd->rb_node, &threads->entries); - RB_CLEAR_NODE(&nd->rb_node); - --threads->nr; - - free(nd); + p = &table->entries.rb_root.rb_node; + while (*p != NULL) { + struct rb_node *parent = *p; + struct thread_rb_node *nd = rb_entry(parent, struct thread_rb_node, rb_node); + struct thread *th = nd->thread; + + if (RC_CHK_EQUAL(th, thread)) { + thread__put(nd->thread); + rb_erase_cached(&nd->rb_node, &table->entries); + RB_CLEAR_NODE(&nd->rb_node); + --table->nr; + free(nd); + break; + } - if (lock) - up_write(&threads->lock); + if (tid < thread__tid(th)) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + up_write(&table->lock); } void machine__remove_thread(struct machine *machine, struct thread *th) { - return __machine__remove_thread(machine, NULL, th, true); + return threads__remove(&machine->threads, th); } int machine__process_fork_event(struct machine *machine, union perf_event *event, @@ -3228,27 +3258,35 @@ int thread__resolve_callchain(struct thread *thread, return ret; } -int machine__for_each_thread(struct machine *machine, - int (*fn)(struct thread *thread, void *p), - void *priv) +int threads__for_each_thread(struct threads *threads, + int (*fn)(struct thread *thread, void *data), + void *data) { - struct threads *threads; - struct rb_node *nd; - int rc = 0; - int i; + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + struct rb_node *nd; - for (i = 0; i < THREADS__TABLE_SIZE; i++) { - threads = &machine->threads[i]; - for (nd = rb_first_cached(&threads->entries); nd; - nd = rb_next(nd)) { + down_read(&table->lock); + for (nd = rb_first_cached(&table->entries); nd; nd = rb_next(nd)) { struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); + int rc = fn(trb->thread, data); - rc = fn(trb->thread, priv); - if (rc != 0) + if (rc != 0) { + up_read(&table->lock); return rc; + } } + up_read(&table->lock); } - return rc; + return 0; + +} + +int machine__for_each_thread(struct machine *machine, + int (*fn)(struct thread *thread, void *p), + void *priv) +{ + return threads__for_each_thread(&machine->threads, fn, priv); } int machines__for_each_thread(struct machines *machines, diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h index b738ce84817b..5b425b70140e 100644 --- a/tools/perf/util/machine.h +++ b/tools/perf/util/machine.h @@ -31,13 +31,28 @@ struct vdso_info; #define THREADS__TABLE_BITS 8 #define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS) -struct threads { +struct threads_table_entry { struct rb_root_cached entries; struct rw_semaphore lock; unsigned int nr; struct thread *last_match; }; +struct threads { + struct threads_table_entry table[THREADS__TABLE_SIZE]; +}; + +void threads__init(struct threads *threads); +void threads__exit(struct threads *threads); +size_t threads__nr(struct threads *threads); +struct thread *threads__find(struct threads *threads, pid_t tid); +struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created); +void threads__remove_all_threads(struct threads *threads); +void threads__remove(struct threads *threads, struct thread *thread); +int threads__for_each_thread(struct threads *threads, + int (*fn)(struct thread *thread, void *data), + void *data); + struct machine { struct rb_node rb_node; pid_t pid; @@ -48,7 +63,7 @@ struct machine { char *root_dir; char *mmap_name; char *kallsyms_filename; - struct threads threads[THREADS__TABLE_SIZE]; + struct threads threads; struct vdso_info *vdso_info; struct perf_env *env; struct dsos dsos; @@ -69,12 +84,6 @@ struct machine { bool trampolines_mapped; }; -static inline struct threads *machine__threads(struct machine *machine, pid_t tid) -{ - /* Cast it to handle tid == -1 */ - return &machine->threads[(unsigned int)tid % THREADS__TABLE_SIZE]; -} - /* * The main kernel (vmlinux) map */ @@ -220,7 +229,6 @@ bool machine__is(struct machine *machine, const char *arch); bool machine__normalized_is(struct machine *machine, const char *arch); int machine__nr_cpus_avail(struct machine *machine); -struct thread *__machine__findnew_thread(struct machine *machine, pid_t pid, pid_t tid); struct thread *machine__findnew_thread(struct machine *machine, pid_t pid, pid_t tid); struct dso *machine__findnew_dso_id(struct machine *machine, const char *filename, struct dso_id *id); diff --git a/tools/perf/util/thread.c b/tools/perf/util/thread.c index c59ab4d79163..1aa8962dcf52 100644 --- a/tools/perf/util/thread.c +++ b/tools/perf/util/thread.c @@ -26,7 +26,7 @@ int thread__init_maps(struct thread *thread, struct machine *machine) if (pid == thread__tid(thread) || pid == -1) { thread__set_maps(thread, maps__new(machine)); } else { - struct thread *leader = __machine__findnew_thread(machine, pid, pid); + struct thread *leader = machine__findnew_thread(machine, pid, pid); if (leader) { thread__set_maps(thread, maps__get(thread__maps(leader))); diff --git a/tools/perf/util/thread.h b/tools/perf/util/thread.h index df344262eaee..8b4a3c69bad1 100644 --- a/tools/perf/util/thread.h +++ b/tools/perf/util/thread.h @@ -3,7 +3,6 @@ #define __PERF_THREAD_H #include -#include #include #include #include @@ -29,11 +28,6 @@ struct lbr_stitch { struct callchain_cursor_node *prev_lbr_cursor; }; -struct thread_rb_node { - struct rb_node rb_node; - struct thread *thread; -}; - DECLARE_RC_STRUCT(thread) { /** @maps: mmaps associated with this thread. */ struct maps *maps; From patchwork Fri Mar 1 05:36:43 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 208657 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2097:b0:108:e6aa:91d0 with SMTP id gs23csp876876dyb; Thu, 29 Feb 2024 21:40:34 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCU2Z6sh04lDapStgvxPiJeA49Ni0i9//VB6isGNWTOJIMV41dEW20qGiihLiOFv8dMbDgiWYVwrWQkd5r9M0CqjQlrkvA== X-Google-Smtp-Source: AGHT+IHjorZX9d1lSx+BCj7kDjrmzqtAicl4bMdfdPJJZ3jVh90Zf0SUOY3LMWxc/ycA6E8f8jyZ X-Received: by 2002:a05:6a00:22d2:b0:6e5:55b9:b64 with SMTP id f18-20020a056a0022d200b006e555b90b64mr911305pfj.1.1709271634237; Thu, 29 Feb 2024 21:40:34 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709271634; cv=pass; d=google.com; s=arc-20160816; b=wYM+P5FP9wp8fu2WCzFf1fmKsN20JtMcb91c8accro5hierjUHXlfJEHp1xhR1jMWb Cp7t4izxVp3fPrExyJucOxz2LAUdK82uhGHtv7LbyXK/Gav32+9bm+cBp/D6KNu0k/xh zwlIFq6QvMCfAhq1kxcZrL+8ChVlO/CmFh6dqRGT+DZBF89WIRzRU4scxDXwbZMhpAVk gTJcSKANp8oSSxh/KlT4j3dJ/ezWCraOpkDW90yPuinzAg/W1j2NNiQaRa1I1+SPujAB Gcmxw5lFNqfugLieM2gzru2LULo8Jdj1qhKEGnLaicl1SRAlA6cN2YUh/TCexVA7Wo8b bI5Q== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=ROSXDwUomvqQuML9PMkfq2AQvT85kKoIeIu9nBJaVks=; fh=NFckPPbsApO3V16+2bQEAzeFiTV72w+p/TarMk1E8VE=; b=bbPApqvba7ChHh+QgGUtEcv6Z6RMP6LaYSMWHI6bgsfOdbkhfqLwD+48qck77HswkC 6KCmlq/RyAUFvdaY5+5n+oXyhseJEK4OlFruBaL4JQYtlwn/7azHry2nOD6m9d/USPAG 7+xoqXvFcI5f1+pjdemN5ZR/qQHNPfCErTqi4xv4bFiGzqNG2HyXs+GkR45VzmkMdJbf zjZ1RCBvi9Eq7pR63RSknGbU1MHOb/6j5gs16UQeeyL3KBtFo5nbtfN9uTNbegid+mJP 7JQHvSojzRxkxAIlvCCVWVj1EguJv0JCPI1WY8nnoVRgeezxVP1WQeNR951wLS+nxbH/ Z61Q==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=roPXcHyq; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87934-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87934-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [147.75.48.161]) by mx.google.com with ESMTPS id fe15-20020a056a002f0f00b006e5bd8bd9d6si613277pfb.18.2024.02.29.21.40.33 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Feb 2024 21:40:34 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-87934-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=roPXcHyq; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87934-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87934-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sy.mirrors.kernel.org (Postfix) with ESMTPS id 89098B24F26 for ; Fri, 1 Mar 2024 05:38:50 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 6DB6855C2C; Fri, 1 Mar 2024 05:37:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="roPXcHyq" Received: from mail-yw1-f202.google.com (mail-yw1-f202.google.com [209.85.128.202]) (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 195C453807 for ; Fri, 1 Mar 2024 05:37:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271426; cv=none; b=QZyDqIpac+cjjhlrvXGuYxeOKK9KutgU5Mz6kZI8lR8QLBsMNKcBKeSb0r4CTgp7Jg30OiK8QNdXIHBzvdD5nOZ/Exb/Mjzhk+EXgO40HeEHwtDGMrFEUgl9ajNqMu41MA8M0jlglF6CMPqzhw4Ds5YCoDvnhjQqUc/gBdajQ4c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271426; c=relaxed/simple; bh=aOKvNCw0mP/aSzwrAr6tjIXHYZ6WOqSdyo+aZpChxCA=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=QMGyKrckwudfKh9C0coZYunaWAY1DKoO60Q/YMXFMUlw1chHZvwzE9j/2Bsh7NYYILt8yzoDgXm0zVI/wxlO15XPJ9xxWY/+yI+V5+FaPMO96U+f2dNzbwO0XfbsL7LnleOsUcMKBnS0y0gFeIVCF00yeG80TS2LuOfdDulF60o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=roPXcHyq; arc=none smtp.client-ip=209.85.128.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Received: by mail-yw1-f202.google.com with SMTP id 00721157ae682-6093f75fc81so31046637b3.1 for ; Thu, 29 Feb 2024 21:37:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709271423; x=1709876223; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=ROSXDwUomvqQuML9PMkfq2AQvT85kKoIeIu9nBJaVks=; b=roPXcHyqgy8Gk6nnFgvnnRHDuYdbOT9ZL4WhuO3V+sUOYDZCBsVHyn0rE4XLrt30XH 9gT3Dh2Ya8OP+jBsgjeVbDqinInIOXajpjMrDggRRue0mNvuU6m37V9afQwHemaRSPcP DU7YSE1NbXqA00uXJ2wMX6zSnatmseXQ/ym7KAfIosa4z0D5v4PUMT6UwcmQp1A0qRNZ RD7Q/XVrRnBuYE3BojWXQDZ3gKzv3e3tFz/JwmeiWNNo56c8E63jPlsXioU48j7rFGdk uF5yOR2bU/P5gwOkc2/e7wZ/Z5Fvj2IDj7YHrkWPLpnqfDn11+NIcNlVSLkbVLxRDNyU tpWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709271423; x=1709876223; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=ROSXDwUomvqQuML9PMkfq2AQvT85kKoIeIu9nBJaVks=; b=m+gf5Xzvmisp9XINGfz3Zhdf1ay05UorYF6zXittuPx3UxIE3x+mjvAWn3N/XSsxOd 0mTHMZGmYBd3q+u90dp6lLEHRU+aR6+2Q+yG/KUsYeNgTf8yW4GBsF4WkMxhRy9EFpw/ iPJgsbPbeocVNLOIqEBxXlVNegHWCZp1nLHynetDCzZ1vksYdm3X+fBKRof8ZoIAbEOc yP1FcTrlToAw8Be509ZVNnHpKtLvouebwE5VphC1xIubLT2jWH+3BXMMNtfzxRKyjpkb 38rY1QOLp7Ctiy3exFYBIyjQvME7V9mtL4/MfOTFPyhpXzP2ryCHt/b83fbwRdHJU1WM 8cQw== X-Forwarded-Encrypted: i=1; AJvYcCVOoWbDt1UxcZuXyiRL3DlQT9fOdEryuo4xoC3vMaktrjvfqkCTSANWjwA6h82syKKYRaxDhAub3Cay83fbDGpWV7xG22PYEVcg3tGO X-Gm-Message-State: AOJu0YwFQtMkVkxKtMVVOEdmPDyFQen4EhShACExMBvpOzOglg0fGqpr GDPrjChglPbZ1YwmGbEVSsDxhp5DgTY6R2f2XhRIqlvlqQ+p5LVKGWWdCN1wmmWIsRiwc6OsSC1 ONC2FIA== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:af4b:7fc1:b7be:fcb7]) (user=irogers job=sendgmr) by 2002:a05:690c:c86:b0:608:ce23:638c with SMTP id cm6-20020a05690c0c8600b00608ce23638cmr174942ywb.4.1709271423168; Thu, 29 Feb 2024 21:37:03 -0800 (PST) Date: Thu, 29 Feb 2024 21:36:43 -0800 In-Reply-To: <20240301053646.1449657-1-irogers@google.com> Message-Id: <20240301053646.1449657-6-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240301053646.1449657-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.278.ge034bb2e1d-goog Subject: [PATCH v4 5/7] perf threads: Move threads to its own files From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Oliver Upton , Yang Jihong , linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1792301213303317380 X-GMAIL-MSGID: 1792301213303317380 Move threads out of machine and into its own file. Signed-off-by: Ian Rogers --- tools/perf/util/Build | 1 + tools/perf/util/machine.c | 248 -------------------------------------- tools/perf/util/machine.h | 26 +--- tools/perf/util/threads.c | 248 ++++++++++++++++++++++++++++++++++++++ tools/perf/util/threads.h | 35 ++++++ 5 files changed, 285 insertions(+), 273 deletions(-) create mode 100644 tools/perf/util/threads.c create mode 100644 tools/perf/util/threads.h diff --git a/tools/perf/util/Build b/tools/perf/util/Build index 2cbeeb79b6ef..e0a723e24503 100644 --- a/tools/perf/util/Build +++ b/tools/perf/util/Build @@ -72,6 +72,7 @@ perf-y += ordered-events.o perf-y += namespaces.o perf-y += comm.o perf-y += thread.o +perf-y += threads.o perf-y += thread_map.o perf-y += parse-events-flex.o perf-y += parse-events-bison.o diff --git a/tools/perf/util/machine.c b/tools/perf/util/machine.c index 224b53b4bfe2..527517db3182 100644 --- a/tools/perf/util/machine.c +++ b/tools/perf/util/machine.c @@ -43,17 +43,6 @@ #include #include -struct thread_rb_node { - struct rb_node rb_node; - struct thread *thread; -}; - -static struct threads_table_entry *threads__table(struct threads *threads, pid_t tid) -{ - /* Cast it to handle tid == -1 */ - return &threads->table[(unsigned int)tid % THREADS__TABLE_SIZE]; -} - static struct dso *machine__kernel_dso(struct machine *machine) { return map__dso(machine->vmlinux_map); @@ -66,18 +55,6 @@ static void dsos__init(struct dsos *dsos) init_rwsem(&dsos->lock); } -void threads__init(struct threads *threads) -{ - for (int i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads_table_entry *table = &threads->table[i]; - - table->entries = RB_ROOT_CACHED; - init_rwsem(&table->lock); - table->nr = 0; - table->last_match = NULL; - } -} - static int machine__set_mmap_name(struct machine *machine) { if (machine__is_host(machine)) @@ -210,49 +187,11 @@ static void dsos__exit(struct dsos *dsos) exit_rwsem(&dsos->lock); } -static void __threads_table_entry__set_last_match(struct threads_table_entry *table, - struct thread *th); - -void threads__remove_all_threads(struct threads *threads) -{ - for (int i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads_table_entry *table = &threads->table[i]; - struct rb_node *nd; - - down_write(&table->lock); - __threads_table_entry__set_last_match(table, NULL); - nd = rb_first_cached(&table->entries); - while (nd) { - struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); - - nd = rb_next(nd); - thread__put(trb->thread); - rb_erase_cached(&trb->rb_node, &table->entries); - RB_CLEAR_NODE(&trb->rb_node); - --table->nr; - - free(trb); - } - assert(table->nr == 0); - up_write(&table->lock); - } -} - void machine__delete_threads(struct machine *machine) { threads__remove_all_threads(&machine->threads); } -void threads__exit(struct threads *threads) -{ - threads__remove_all_threads(threads); - for (int i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads_table_entry *table = &threads->table[i]; - - exit_rwsem(&table->lock); - } -} - void machine__exit(struct machine *machine) { if (machine == NULL) @@ -568,121 +507,6 @@ static void machine__update_thread_pid(struct machine *machine, goto out_put; } -/* - * Front-end cache - TID lookups come in blocks, - * so most of the time we dont have to look up - * the full rbtree: - */ -static struct thread *__threads_table_entry__get_last_match(struct threads_table_entry *table, - pid_t tid) -{ - struct thread *th, *res = NULL; - - th = table->last_match; - if (th != NULL) { - if (thread__tid(th) == tid) - res = thread__get(th); - } - return res; -} - -static void __threads_table_entry__set_last_match(struct threads_table_entry *table, - struct thread *th) -{ - thread__put(table->last_match); - table->last_match = thread__get(th); -} - -static void threads_table_entry__set_last_match(struct threads_table_entry *table, - struct thread *th) -{ - down_write(&table->lock); - __threads_table_entry__set_last_match(table, th); - up_write(&table->lock); -} - -struct thread *threads__find(struct threads *threads, pid_t tid) -{ - struct threads_table_entry *table = threads__table(threads, tid); - struct rb_node **p; - struct thread *res = NULL; - - down_read(&table->lock); - res = __threads_table_entry__get_last_match(table, tid); - if (res) - return res; - - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct rb_node *parent = *p; - struct thread *th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; - - if (thread__tid(th) == tid) { - res = thread__get(th); - break; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } - up_read(&table->lock); - if (res) - threads_table_entry__set_last_match(table, res); - return res; -} - -struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created) -{ - struct threads_table_entry *table = threads__table(threads, tid); - struct rb_node **p; - struct rb_node *parent = NULL; - struct thread *res = NULL; - struct thread_rb_node *nd; - bool leftmost = true; - - *created = false; - down_write(&table->lock); - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct thread *th; - - parent = *p; - th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; - - if (thread__tid(th) == tid) { - __threads_table_entry__set_last_match(table, th); - res = thread__get(th); - goto out_unlock; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else { - p = &(*p)->rb_right; - leftmost = false; - } - } - nd = malloc(sizeof(*nd)); - if (nd == NULL) - goto out_unlock; - res = thread__new(pid, tid); - if (!res) - free(nd); - else { - *created = true; - nd->thread = thread__get(res); - rb_link_node(&nd->rb_node, parent, p); - rb_insert_color_cached(&nd->rb_node, &table->entries, leftmost); - ++table->nr; - __threads_table_entry__set_last_match(table, res); - } -out_unlock: - up_write(&table->lock); - return res; -} - /* * Caller must eventually drop thread->refcnt returned with a successful * lookup/new thread inserted. @@ -699,7 +523,6 @@ static struct thread *__machine__findnew_thread(struct machine *machine, machine__update_thread_pid(machine, th, pid); return th; } - if (!create) return NULL; @@ -1147,20 +970,6 @@ static int machine_fprintf_cb(struct thread *thread, void *data) return 0; } -size_t threads__nr(struct threads *threads) -{ - size_t nr = 0; - - for (int i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads_table_entry *table = &threads->table[i]; - - down_read(&table->lock); - nr += table->nr; - up_read(&table->lock); - } - return nr; -} - size_t machine__fprintf(struct machine *machine, FILE *fp) { struct machine_fprintf_cb_args args = { @@ -2093,39 +1902,6 @@ int machine__process_mmap_event(struct machine *machine, union perf_event *event return 0; } -void threads__remove(struct threads *threads, struct thread *thread) -{ - struct rb_node **p; - struct threads_table_entry *table = threads__table(threads, thread__tid(thread)); - pid_t tid = thread__tid(thread); - - down_write(&table->lock); - if (table->last_match && RC_CHK_EQUAL(table->last_match, thread)) - __threads_table_entry__set_last_match(table, NULL); - - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct rb_node *parent = *p; - struct thread_rb_node *nd = rb_entry(parent, struct thread_rb_node, rb_node); - struct thread *th = nd->thread; - - if (RC_CHK_EQUAL(th, thread)) { - thread__put(nd->thread); - rb_erase_cached(&nd->rb_node, &table->entries); - RB_CLEAR_NODE(&nd->rb_node); - --table->nr; - free(nd); - break; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } - up_write(&table->lock); -} - void machine__remove_thread(struct machine *machine, struct thread *th) { return threads__remove(&machine->threads, th); @@ -3258,30 +3034,6 @@ int thread__resolve_callchain(struct thread *thread, return ret; } -int threads__for_each_thread(struct threads *threads, - int (*fn)(struct thread *thread, void *data), - void *data) -{ - for (int i = 0; i < THREADS__TABLE_SIZE; i++) { - struct threads_table_entry *table = &threads->table[i]; - struct rb_node *nd; - - down_read(&table->lock); - for (nd = rb_first_cached(&table->entries); nd; nd = rb_next(nd)) { - struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); - int rc = fn(trb->thread, data); - - if (rc != 0) { - up_read(&table->lock); - return rc; - } - } - up_read(&table->lock); - } - return 0; - -} - int machine__for_each_thread(struct machine *machine, int (*fn)(struct thread *thread, void *p), void *priv) diff --git a/tools/perf/util/machine.h b/tools/perf/util/machine.h index 5b425b70140e..e28c787616fe 100644 --- a/tools/perf/util/machine.h +++ b/tools/perf/util/machine.h @@ -7,6 +7,7 @@ #include "maps.h" #include "dsos.h" #include "rwsem.h" +#include "threads.h" struct addr_location; struct branch_stack; @@ -28,31 +29,6 @@ extern const char *ref_reloc_sym_names[]; struct vdso_info; -#define THREADS__TABLE_BITS 8 -#define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS) - -struct threads_table_entry { - struct rb_root_cached entries; - struct rw_semaphore lock; - unsigned int nr; - struct thread *last_match; -}; - -struct threads { - struct threads_table_entry table[THREADS__TABLE_SIZE]; -}; - -void threads__init(struct threads *threads); -void threads__exit(struct threads *threads); -size_t threads__nr(struct threads *threads); -struct thread *threads__find(struct threads *threads, pid_t tid); -struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created); -void threads__remove_all_threads(struct threads *threads); -void threads__remove(struct threads *threads, struct thread *thread); -int threads__for_each_thread(struct threads *threads, - int (*fn)(struct thread *thread, void *data), - void *data); - struct machine { struct rb_node rb_node; pid_t pid; diff --git a/tools/perf/util/threads.c b/tools/perf/util/threads.c new file mode 100644 index 000000000000..db52d233c2de --- /dev/null +++ b/tools/perf/util/threads.c @@ -0,0 +1,248 @@ +// SPDX-License-Identifier: GPL-2.0 +#include "threads.h" +#include "machine.h" +#include "thread.h" + +struct thread_rb_node { + struct rb_node rb_node; + struct thread *thread; +}; + +static struct threads_table_entry *threads__table(struct threads *threads, pid_t tid) +{ + /* Cast it to handle tid == -1 */ + return &threads->table[(unsigned int)tid % THREADS__TABLE_SIZE]; +} + +void threads__init(struct threads *threads) +{ + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + + table->entries = RB_ROOT_CACHED; + init_rwsem(&table->lock); + table->nr = 0; + table->last_match = NULL; + } +} + +void threads__exit(struct threads *threads) +{ + threads__remove_all_threads(threads); + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + + exit_rwsem(&table->lock); + } +} + +size_t threads__nr(struct threads *threads) +{ + size_t nr = 0; + + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + + down_read(&table->lock); + nr += table->nr; + up_read(&table->lock); + } + return nr; +} + +/* + * Front-end cache - TID lookups come in blocks, + * so most of the time we dont have to look up + * the full rbtree: + */ +static struct thread *__threads_table_entry__get_last_match(struct threads_table_entry *table, + pid_t tid) +{ + struct thread *th, *res = NULL; + + th = table->last_match; + if (th != NULL) { + if (thread__tid(th) == tid) + res = thread__get(th); + } + return res; +} + +static void __threads_table_entry__set_last_match(struct threads_table_entry *table, + struct thread *th) +{ + thread__put(table->last_match); + table->last_match = thread__get(th); +} + +static void threads_table_entry__set_last_match(struct threads_table_entry *table, + struct thread *th) +{ + down_write(&table->lock); + __threads_table_entry__set_last_match(table, th); + up_write(&table->lock); +} + +struct thread *threads__find(struct threads *threads, pid_t tid) +{ + struct threads_table_entry *table = threads__table(threads, tid); + struct rb_node **p; + struct thread *res = NULL; + + down_read(&table->lock); + res = __threads_table_entry__get_last_match(table, tid); + if (res) + return res; + + p = &table->entries.rb_root.rb_node; + while (*p != NULL) { + struct rb_node *parent = *p; + struct thread *th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; + + if (thread__tid(th) == tid) { + res = thread__get(th); + break; + } + + if (tid < thread__tid(th)) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + up_read(&table->lock); + if (res) + threads_table_entry__set_last_match(table, res); + return res; +} + +struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created) +{ + struct threads_table_entry *table = threads__table(threads, tid); + struct rb_node **p; + struct rb_node *parent = NULL; + struct thread *res = NULL; + struct thread_rb_node *nd; + bool leftmost = true; + + *created = false; + down_write(&table->lock); + p = &table->entries.rb_root.rb_node; + while (*p != NULL) { + struct thread *th; + + parent = *p; + th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; + + if (thread__tid(th) == tid) { + __threads_table_entry__set_last_match(table, th); + res = thread__get(th); + goto out_unlock; + } + + if (tid < thread__tid(th)) + p = &(*p)->rb_left; + else { + leftmost = false; + p = &(*p)->rb_right; + } + } + nd = malloc(sizeof(*nd)); + if (nd == NULL) + goto out_unlock; + res = thread__new(pid, tid); + if (!res) + free(nd); + else { + *created = true; + nd->thread = thread__get(res); + rb_link_node(&nd->rb_node, parent, p); + rb_insert_color_cached(&nd->rb_node, &table->entries, leftmost); + ++table->nr; + __threads_table_entry__set_last_match(table, res); + } +out_unlock: + up_write(&table->lock); + return res; +} + +void threads__remove_all_threads(struct threads *threads) +{ + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + struct rb_node *nd; + + down_write(&table->lock); + __threads_table_entry__set_last_match(table, NULL); + nd = rb_first_cached(&table->entries); + while (nd) { + struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); + + nd = rb_next(nd); + thread__put(trb->thread); + rb_erase_cached(&trb->rb_node, &table->entries); + RB_CLEAR_NODE(&trb->rb_node); + --table->nr; + + free(trb); + } + assert(table->nr == 0); + up_write(&table->lock); + } +} + +void threads__remove(struct threads *threads, struct thread *thread) +{ + struct rb_node **p; + struct threads_table_entry *table = threads__table(threads, thread__tid(thread)); + pid_t tid = thread__tid(thread); + + down_write(&table->lock); + if (table->last_match && RC_CHK_EQUAL(table->last_match, thread)) + __threads_table_entry__set_last_match(table, NULL); + + p = &table->entries.rb_root.rb_node; + while (*p != NULL) { + struct rb_node *parent = *p; + struct thread_rb_node *nd = rb_entry(parent, struct thread_rb_node, rb_node); + struct thread *th = nd->thread; + + if (RC_CHK_EQUAL(th, thread)) { + thread__put(nd->thread); + rb_erase_cached(&nd->rb_node, &table->entries); + RB_CLEAR_NODE(&nd->rb_node); + --table->nr; + free(nd); + break; + } + + if (tid < thread__tid(th)) + p = &(*p)->rb_left; + else + p = &(*p)->rb_right; + } + up_write(&table->lock); +} + +int threads__for_each_thread(struct threads *threads, + int (*fn)(struct thread *thread, void *data), + void *data) +{ + for (int i = 0; i < THREADS__TABLE_SIZE; i++) { + struct threads_table_entry *table = &threads->table[i]; + struct rb_node *nd; + + down_read(&table->lock); + for (nd = rb_first_cached(&table->entries); nd; nd = rb_next(nd)) { + struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); + int rc = fn(trb->thread, data); + + if (rc != 0) { + up_read(&table->lock); + return rc; + } + } + up_read(&table->lock); + } + return 0; + +} diff --git a/tools/perf/util/threads.h b/tools/perf/util/threads.h new file mode 100644 index 000000000000..ed67de627578 --- /dev/null +++ b/tools/perf/util/threads.h @@ -0,0 +1,35 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef __PERF_THREADS_H +#define __PERF_THREADS_H + +#include +#include "rwsem.h" + +struct thread; + +#define THREADS__TABLE_BITS 8 +#define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS) + +struct threads_table_entry { + struct rb_root_cached entries; + struct rw_semaphore lock; + unsigned int nr; + struct thread *last_match; +}; + +struct threads { + struct threads_table_entry table[THREADS__TABLE_SIZE]; +}; + +void threads__init(struct threads *threads); +void threads__exit(struct threads *threads); +size_t threads__nr(struct threads *threads); +struct thread *threads__find(struct threads *threads, pid_t tid); +struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created); +void threads__remove_all_threads(struct threads *threads); +void threads__remove(struct threads *threads, struct thread *thread); +int threads__for_each_thread(struct threads *threads, + int (*fn)(struct thread *thread, void *data), + void *data); + +#endif /* __PERF_THREADS_H */ From patchwork Fri Mar 1 05:36:44 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 208655 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2097:b0:108:e6aa:91d0 with SMTP id gs23csp876322dyb; Thu, 29 Feb 2024 21:38:48 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCV7D7DWU3KWMWkIw/g0eRWC/H3uw5IzRUlGM6gFuZvnVcdAS2gC/cXy6PPMeA9Ysv21u04FSwhAeJwFwthdRkJssXknNQ== X-Google-Smtp-Source: AGHT+IFvIXCdB7ByMW1fhL0ueF8taA1wsLhL81NsTt/7BpOyG8YnShOkZfVGAoTPZnZmEEMfOHJI X-Received: by 2002:a17:906:57c8:b0:a3e:ba73:8341 with SMTP id u8-20020a17090657c800b00a3eba738341mr445480ejr.19.1709271528719; Thu, 29 Feb 2024 21:38:48 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709271528; cv=pass; d=google.com; s=arc-20160816; b=Ck1AosMqD3fHJAguDGgftzXDCVhu0/+tdX+a1l1dntaoD0AfQhdHygTH2QaQzxZkVM NswJSS+fphAv4n9d6enuLoB9lM8KcT2haD5cv+U98xSS18F13yFdCKiev6XHxuWe8V6B NWuM/A5xtbsqbU48+zJ2GzFR5prrYRWXUnSd6O+gkiBHUUfUk12TdAPfnGxiz8GiKCWD 5s5oZ5bhDzdL6/++A7Eu4YCkPSiXZj0kfDAoUgFgkn2tnDB34h3Qk4SDdshJtyrMyDN/ VMlQsFxZklRrPys9quAMCfW4GugjZz4hTAtm7q/PBQtQBQtRyHYD+rhzPD784AOzehPx yAfw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=G4IHp+rWZ6m2tdq1gZNE1l7uOaHQfZu8fsR6pOr+kRs=; fh=bPrJoycnokOM5CEVHaxHAhFeQbHbp3oO206wWMVk2dQ=; b=YVjRoSqjJgkXTGTNYI0196T0JUqvPXeTocF3WdDdm9eUfXiIF9whV/FSkeJvUaQ6o7 jRm54DbwBChZT6dlg/BMnDPdpAzJZ4LbooYzUyMklsHofWO5LEmnjN3681Cr0C7MfzUJ gBbCAN/Z0miDBRbmPXSqP2d5XccbOkj8NeDWshgC0eGS24mRyqzatRJNmMP8ZYydmOTe ob3Hq+3b9PXiCDCT/UCqFJe4rfR2hzs0PVLdWSxbr+jLeGq41Z9GOJ9E8XPvQGQlPfb1 Ka56miBl1twRo9W5Dn/wNwHGCiQAt3R/UTAY1B8A14EKDcYHr6WaoRZOn9jU0CtAE0To 0+dA==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="JsDqkn//"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87935-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87935-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [2604:1380:4601:e00::3]) by mx.google.com with ESMTPS id nc22-20020a1709071c1600b00a3e34ecee31si1202857ejc.1049.2024.02.29.21.38.48 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Feb 2024 21:38:48 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-87935-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b="JsDqkn//"; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87935-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87935-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id 30E2F1F2380F for ; Fri, 1 Mar 2024 05:38:48 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 56AD0537F0; Fri, 1 Mar 2024 05:37:12 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="JsDqkn//" Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (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 6C7C854737 for ; Fri, 1 Mar 2024 05:37:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271428; cv=none; b=XeyjPkeYD/efwzHcsOMv3iFm4UtlnmfXAbuMCybNx0ZnzTR+FYCaz4b0n2KGlij0pLxhH1x+dx7ppD9FPahf/zRBQE+zdzyZwXP219vB8IuiIhpIxOxJdKHCenqrnLCyysiQsXOHonfbuPyL9KKdkRAbdF0fJGZPGN6Z0UqX/C0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271428; c=relaxed/simple; bh=SCdyCRIW2q68p5P5XIiezVRdNMVzHuD+AJIgIjGCWXw=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=FiDmKpcYgUOYVhjPrqdKROaYDT9eI1I0haAH37pf5KGXZlWxxKqdWSjb9Z/r7E7ElvKuPqOQsU7Ig2U/zHvm1pwqZjxfTQQ01lVgDid+xvjMMHhewQA2efTMqYoo/kCuvT7ZeXjqXGO1cmb6XMhGZKSQ20hOrGkbaaN2s0B09jg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=JsDqkn//; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-dc693399655so3255764276.1 for ; Thu, 29 Feb 2024 21:37:06 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709271425; x=1709876225; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=G4IHp+rWZ6m2tdq1gZNE1l7uOaHQfZu8fsR6pOr+kRs=; b=JsDqkn//YlCBTmY+LxfyxyBNgms6u3MC0PQDXERBEVsj08UmXLaTdbQtXUGUmdumo7 Vg52LO9qSLQoE827beREGu8hvcMA8P1ZwPeETtwK2OQkojV0SWCgTg/5HZk/tOJhnnKt Nti+co1hamuw0ZuXhKmW6v7GBL2v8XewKtAugbbqbbDift03Pc0tAbub3FT+ucCgic5J 71AxLqXFjUFyJkHktTwvPplFw84LtEwKzuAkAceqmPA+V6WfXdhT5YrBBeHYVKlijzHU nIj4Kq8cQMpGsFdHtX7E4xzVTQYGx8DyK1s/3m6UVINGmd89OBRSqjyzrlWu1yrVa7aI YD8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709271425; x=1709876225; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=G4IHp+rWZ6m2tdq1gZNE1l7uOaHQfZu8fsR6pOr+kRs=; b=S6hcSD1Bq+3/sE04rp+X05io6zgkbeikYqLf1izVvhMCOTDi43qIKgkjdUGGoJKEyB +yvWhPhNkvQQgsBpg6Y4/MjKs98+As+4iuLMWcX4Q6Ss1FwCp9E675bvc9afwLmV71Qc Fj2QUdJ1FN0nKX28izK4+80SvjL75g6GljwvyVt1C7cl3nqOiKqsn7rtrTYS8NImOdla z9eCDMFBwq/SDjgfoSlYRLfrTQUAC826rx9Sca29NnypMf2xrvDCvBwwpDz1pyE97Opt eXG+vYNQ5Ac5IMs5u+CkInT8bfThclqG/n4GCj5n6Dcjr1Ge5HqqJVrz2wNorsthtOTA XNDg== X-Forwarded-Encrypted: i=1; AJvYcCUn3U4bpoVuLv3A6NEnukiQnRh9VZq/ly/hxp7cAQNKnvddBUk/KJ4XLvqTTg+DlbXlPL+P1HppbtyHt1F9wSVqfN4iCMrlrJU5YPf0 X-Gm-Message-State: AOJu0YxEvhPne/vjS/Hl1Z8JdGNpKizTaH/IPVjvWuHqq0DQvcayt8p7 nRxNUs9QccsNSr9U1q7unp67P6QePGfMP2cjcVyzftC0/AUKD52WWvBYKKr2UvEGI3u30xXNs/S a/smWLg== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:af4b:7fc1:b7be:fcb7]) (user=irogers job=sendgmr) by 2002:a05:6902:154d:b0:dcf:411d:67b9 with SMTP id r13-20020a056902154d00b00dcf411d67b9mr137956ybu.5.1709271425461; Thu, 29 Feb 2024 21:37:05 -0800 (PST) Date: Thu, 29 Feb 2024 21:36:44 -0800 In-Reply-To: <20240301053646.1449657-1-irogers@google.com> Message-Id: <20240301053646.1449657-7-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240301053646.1449657-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.278.ge034bb2e1d-goog Subject: [PATCH v4 6/7] perf threads: Switch from rbtree to hashmap From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Oliver Upton , Yang Jihong , linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1792301102601981644 X-GMAIL-MSGID: 1792301102601981644 The rbtree provides a sorting on entries but this is unused. Switch to using hashmap for O(1) rather than O(log n) find/insert/remove complexity. Signed-off-by: Ian Rogers --- tools/perf/util/threads.c | 146 ++++++++++++-------------------------- tools/perf/util/threads.h | 6 +- 2 files changed, 47 insertions(+), 105 deletions(-) diff --git a/tools/perf/util/threads.c b/tools/perf/util/threads.c index db52d233c2de..ff2b169e0085 100644 --- a/tools/perf/util/threads.c +++ b/tools/perf/util/threads.c @@ -3,25 +3,30 @@ #include "machine.h" #include "thread.h" -struct thread_rb_node { - struct rb_node rb_node; - struct thread *thread; -}; - static struct threads_table_entry *threads__table(struct threads *threads, pid_t tid) { /* Cast it to handle tid == -1 */ return &threads->table[(unsigned int)tid % THREADS__TABLE_SIZE]; } +static size_t key_hash(long key, void *ctx __maybe_unused) +{ + /* The table lookup removes low bit entropy, but this is just ignored here. */ + return key; +} + +static bool key_equal(long key1, long key2, void *ctx __maybe_unused) +{ + return key1 == key2; +} + void threads__init(struct threads *threads) { for (int i = 0; i < THREADS__TABLE_SIZE; i++) { struct threads_table_entry *table = &threads->table[i]; - table->entries = RB_ROOT_CACHED; + hashmap__init(&table->shard, key_hash, key_equal, NULL); init_rwsem(&table->lock); - table->nr = 0; table->last_match = NULL; } } @@ -32,6 +37,7 @@ void threads__exit(struct threads *threads) for (int i = 0; i < THREADS__TABLE_SIZE; i++) { struct threads_table_entry *table = &threads->table[i]; + hashmap__clear(&table->shard); exit_rwsem(&table->lock); } } @@ -44,7 +50,7 @@ size_t threads__nr(struct threads *threads) struct threads_table_entry *table = &threads->table[i]; down_read(&table->lock); - nr += table->nr; + nr += hashmap__size(&table->shard); up_read(&table->lock); } return nr; @@ -86,28 +92,13 @@ static void threads_table_entry__set_last_match(struct threads_table_entry *tabl struct thread *threads__find(struct threads *threads, pid_t tid) { struct threads_table_entry *table = threads__table(threads, tid); - struct rb_node **p; - struct thread *res = NULL; + struct thread *res; down_read(&table->lock); res = __threads_table_entry__get_last_match(table, tid); - if (res) - return res; - - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct rb_node *parent = *p; - struct thread *th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; - - if (thread__tid(th) == tid) { - res = thread__get(th); - break; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; + if (!res) { + if (hashmap__find(&table->shard, tid, &res)) + res = thread__get(res); } up_read(&table->lock); if (res) @@ -118,49 +109,25 @@ struct thread *threads__find(struct threads *threads, pid_t tid) struct thread *threads__findnew(struct threads *threads, pid_t pid, pid_t tid, bool *created) { struct threads_table_entry *table = threads__table(threads, tid); - struct rb_node **p; - struct rb_node *parent = NULL; struct thread *res = NULL; - struct thread_rb_node *nd; - bool leftmost = true; *created = false; down_write(&table->lock); - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct thread *th; - - parent = *p; - th = rb_entry(parent, struct thread_rb_node, rb_node)->thread; - - if (thread__tid(th) == tid) { - __threads_table_entry__set_last_match(table, th); - res = thread__get(th); - goto out_unlock; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else { - leftmost = false; - p = &(*p)->rb_right; - } - } - nd = malloc(sizeof(*nd)); - if (nd == NULL) - goto out_unlock; res = thread__new(pid, tid); - if (!res) - free(nd); - else { - *created = true; - nd->thread = thread__get(res); - rb_link_node(&nd->rb_node, parent, p); - rb_insert_color_cached(&nd->rb_node, &table->entries, leftmost); - ++table->nr; - __threads_table_entry__set_last_match(table, res); + if (res) { + if (hashmap__add(&table->shard, tid, res)) { + /* Add failed. Assume a race so find other entry. */ + thread__put(res); + res = NULL; + if (hashmap__find(&table->shard, tid, &res)) + res = thread__get(res); + } else { + res = thread__get(res); + *created = true; + } + if (res) + __threads_table_entry__set_last_match(table, res); } -out_unlock: up_write(&table->lock); return res; } @@ -169,57 +136,32 @@ void threads__remove_all_threads(struct threads *threads) { for (int i = 0; i < THREADS__TABLE_SIZE; i++) { struct threads_table_entry *table = &threads->table[i]; - struct rb_node *nd; + struct hashmap_entry *cur, *tmp; + size_t bkt; down_write(&table->lock); __threads_table_entry__set_last_match(table, NULL); - nd = rb_first_cached(&table->entries); - while (nd) { - struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); - - nd = rb_next(nd); - thread__put(trb->thread); - rb_erase_cached(&trb->rb_node, &table->entries); - RB_CLEAR_NODE(&trb->rb_node); - --table->nr; + hashmap__for_each_entry_safe((&table->shard), cur, tmp, bkt) { + struct thread *old_value; - free(trb); + hashmap__delete(&table->shard, cur->key, /*old_key=*/NULL, &old_value); + thread__put(old_value); } - assert(table->nr == 0); up_write(&table->lock); } } void threads__remove(struct threads *threads, struct thread *thread) { - struct rb_node **p; struct threads_table_entry *table = threads__table(threads, thread__tid(thread)); - pid_t tid = thread__tid(thread); + struct thread *old_value; down_write(&table->lock); if (table->last_match && RC_CHK_EQUAL(table->last_match, thread)) __threads_table_entry__set_last_match(table, NULL); - p = &table->entries.rb_root.rb_node; - while (*p != NULL) { - struct rb_node *parent = *p; - struct thread_rb_node *nd = rb_entry(parent, struct thread_rb_node, rb_node); - struct thread *th = nd->thread; - - if (RC_CHK_EQUAL(th, thread)) { - thread__put(nd->thread); - rb_erase_cached(&nd->rb_node, &table->entries); - RB_CLEAR_NODE(&nd->rb_node); - --table->nr; - free(nd); - break; - } - - if (tid < thread__tid(th)) - p = &(*p)->rb_left; - else - p = &(*p)->rb_right; - } + hashmap__delete(&table->shard, thread__tid(thread), /*old_key=*/NULL, &old_value); + thread__put(old_value); up_write(&table->lock); } @@ -229,12 +171,12 @@ int threads__for_each_thread(struct threads *threads, { for (int i = 0; i < THREADS__TABLE_SIZE; i++) { struct threads_table_entry *table = &threads->table[i]; - struct rb_node *nd; + struct hashmap_entry *cur; + size_t bkt; down_read(&table->lock); - for (nd = rb_first_cached(&table->entries); nd; nd = rb_next(nd)) { - struct thread_rb_node *trb = rb_entry(nd, struct thread_rb_node, rb_node); - int rc = fn(trb->thread, data); + hashmap__for_each_entry((&table->shard), cur, bkt) { + int rc = fn((struct thread *)cur->pvalue, data); if (rc != 0) { up_read(&table->lock); diff --git a/tools/perf/util/threads.h b/tools/perf/util/threads.h index ed67de627578..d03bd91a7769 100644 --- a/tools/perf/util/threads.h +++ b/tools/perf/util/threads.h @@ -2,7 +2,7 @@ #ifndef __PERF_THREADS_H #define __PERF_THREADS_H -#include +#include "hashmap.h" #include "rwsem.h" struct thread; @@ -11,9 +11,9 @@ struct thread; #define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS) struct threads_table_entry { - struct rb_root_cached entries; + /* Key is tid, value is struct thread. */ + struct hashmap shard; struct rw_semaphore lock; - unsigned int nr; struct thread *last_match; }; From patchwork Fri Mar 1 05:36:45 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ian Rogers X-Patchwork-Id: 208656 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:2097:b0:108:e6aa:91d0 with SMTP id gs23csp876340dyb; Thu, 29 Feb 2024 21:38:53 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCXulVCBu+irxcibfVnCR0P3H2BExm0gSk3MeKnI06WYyYB4JtPxFliZ1wDgmcEw4ptQZ0D7GYc9e3yKov9D4Y0k1OVi2w== X-Google-Smtp-Source: AGHT+IGU91Rq3Hz0a34/LapOcLl4kI9j0k6B+H31gKgq5HH6o2DJ2k+ZRvcCWMZ/24hjtxpKm2Il X-Received: by 2002:a05:6a00:14c9:b0:6e5:7045:59b1 with SMTP id w9-20020a056a0014c900b006e5704559b1mr875639pfu.19.1709271533034; Thu, 29 Feb 2024 21:38:53 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1709271533; cv=pass; d=google.com; s=arc-20160816; b=YdSa1ClFsGXJg/E2/CZidyfFcFBSZjIKFu3CzoZShA7nnjQV4Py9slDVHN00KW3JWl 1m1w7h8e6OSWqhM/03QjN3USwZWu4/v+84xHqyg+p2jEqQLuP61lO+xqDGtN0XH9EKqP 2+hpGuADrzwoQcHnrrdReBsZGoc8/bAF1q3nGBppBIA9NIv1tFSzTFdhf2BujIgcirZs +8GdJ4lkXXIWQ9vBav33Zj/OJupX8ZSyUTFNv2+tpd9xgZsXx3669wJB3OFgpue/ZPxC KtiiYPGNsGNg8+MZ3qJZu/hmvPefQ2BKwi1ej5HC7h5ehpLpsK6IZCx8S5uAJ4I4MVKd YaeA== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:from:subject:references:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:message-id:in-reply-to:date :dkim-signature; bh=h3EeOnj2LJFuh4Gzgf1odB7yRFHxb61zXSqdlmTf/sY=; fh=uVDBLhy7UdESYcC/ExNCNSmRx2u5ioObXYKUSnQlmxE=; b=xp0PyyWfJ1XARNwYtlTZ/q5yI/YeV3zKm4+kw5RcO+bCl+m/FeKsU8Vl71FkIayS5e Om065zT9X9K+DdStR5eW0i8eQixeuvmgdzDpOB3YJ10NY488WjAdrlKZaGCDndleQAb4 dt86dj3IpAjoGsboSlLe2T5C3m6kLifx7oXpprPG4RmFQOQjJywQPQk6fULcwCxWjTh+ 5QeWlJ/6GAhdAWfQY6WJBavagAsR6D9FyQLxEMorU8FWEW5Rvuv5BJ1phk3tloDTT9Qh ayuH8kzOaJIma0r7nx1yDQSzETyV8NvkMDRIc32tB/qFv3Z9rsK69l7q6pW3jLd1mhBN BxQg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=xQLSYKDJ; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87936-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87936-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [139.178.88.99]) by mx.google.com with ESMTPS id w2-20020a636202000000b005dbec3481efsi2870518pgb.91.2024.02.29.21.38.52 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 29 Feb 2024 21:38:53 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-87936-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20230601 header.b=xQLSYKDJ; arc=pass (i=1 spf=pass spfdomain=flex--irogers.bounces.google.com dkim=pass dkdomain=google.com dmarc=pass fromdomain=google.com); spf=pass (google.com: domain of linux-kernel+bounces-87936-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-87936-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id D35CF28376E for ; Fri, 1 Mar 2024 05:38:52 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 00FF656756; Fri, 1 Mar 2024 05:37:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="xQLSYKDJ" Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.201]) (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 B298554BFC for ; Fri, 1 Mar 2024 05:37:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271430; cv=none; b=KjWWl29lRotJbmej+aXiWnhZCpHkoIqn5w6FxKV1z3d34noQLCgYjYFV4AHMejKkNjD8qvSsz0gpgBs37ctlu6TtM7PSWGE2GxNwpDVQonnOGpnWLK3k/H+5Bjk37U+9svxTLy7r71o5Q99wH9+gMXPKUJxFD5aVfWQpHN7I0Jg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1709271430; c=relaxed/simple; bh=GIegngHqtLjHARUsBjYE1nUvvYzurvCdwBU55T25Zws=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=tfJmZsougO3t0uGs7ymIe4kf0sHMfA1TuD4Ymg/grxcW03l2htl1RxGlZ+z2Sf2byy2lywubZ3/TMoa9PtQXsfGzHF8ZF3mwDcj47+lUqRDya0Ds7v9yjnOliQM73t/9zWC1El7+ECcONOG1R0+eoA2+F9tqRgWwNdmp4ilGG1w= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=xQLSYKDJ; arc=none smtp.client-ip=209.85.128.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--irogers.bounces.google.com Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-6087ffdac8cso26288767b3.2 for ; Thu, 29 Feb 2024 21:37:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1709271427; x=1709876227; darn=vger.kernel.org; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :from:to:cc:subject:date:message-id:reply-to; bh=h3EeOnj2LJFuh4Gzgf1odB7yRFHxb61zXSqdlmTf/sY=; b=xQLSYKDJmoaE+yJNvdjYjShfCm7eK04b3GLGi2U3N5GvAS9YcB8vCk7OpmItFobhts 195HdHsABF1tJrM4Bh1DlxbnjDClsKPi/EBzuwfmvOo2JpRXoF6pGIB1DgwxZ8eJJ0N7 CklgfszI1bqzu19u3ftFqEZB1edr00ki94uK8WaTnVcVmj51booCGqpfjzrwLhF2pBsV xxgQT3Ip7mi5zeAtgP9o8sYqF6IvW8WEzWDWFd1HELnTgHOtJwA1HwMmfpY8gADj7T0P obIEV+00Ihr42PS5GNDphI2YNA+7meByKQ/Wc9Mn4APnr9JFJ0C44WW3hlikRxzXIPSF DmQA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1709271427; x=1709876227; h=to:from:subject:references:mime-version:message-id:in-reply-to:date :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=h3EeOnj2LJFuh4Gzgf1odB7yRFHxb61zXSqdlmTf/sY=; b=Lalglhs8nVshL2VQhlSodGKppLRUkWN4i+HauC4sXreSNFAR3wOIAoatyr05CXPGVX Bu5x0Qyq7pXEoCqsvYmyI/EzZaNslTXwfpQ9UrnSXuoTWrWgyyIh6oNrLIHaH1C8axie Z2iyghCRrpmLeOhuRi4/zmkRZBoTDc6T7goqYG6etMkS7nUfTTtx+ajRt9gUpwhnNImq 7Olpg6PyUk6wVlGjaC0Nv+NEi3D4b8hr7rPFXHtYT79Sd8Dbh7ekSimMWgmZBheMmDjs 6+1fdZPP9ycndS7y/WpGm4Anxxi2i9iaRFKzPsjOjmltjiBCpo/IuYhKMU+IgvO1O/+h o0Pg== X-Forwarded-Encrypted: i=1; AJvYcCXc/9LijPozSai6GdZiPpawDZpPxM5wM4AgaWIqnVx4iQmd0B8zScBLksOzrE9WTFNVlCoTASA0S4js7I56cLztW430Xzghu0DmWZi9 X-Gm-Message-State: AOJu0Yy1wnTYkCGjfyD11rqh52XCYz/Gq9Cfk8UR7DrG+Oj1ir2GYMgL IbeWgST3SLTHIZfN0fCQRvksVWvh5XYkeARqfFhOW0KbVDNxFTrCpRDrrM5Vi1+CDacSUvvnuyq c6lLbDg== X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:af4b:7fc1:b7be:fcb7]) (user=irogers job=sendgmr) by 2002:a05:6902:72f:b0:dc7:68b5:4f3d with SMTP id l15-20020a056902072f00b00dc768b54f3dmr130791ybt.11.1709271427758; Thu, 29 Feb 2024 21:37:07 -0800 (PST) Date: Thu, 29 Feb 2024 21:36:45 -0800 In-Reply-To: <20240301053646.1449657-1-irogers@google.com> Message-Id: <20240301053646.1449657-8-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240301053646.1449657-1-irogers@google.com> X-Mailer: git-send-email 2.44.0.278.ge034bb2e1d-goog Subject: [PATCH v4 7/7] perf threads: Reduce table size from 256 to 8 From: Ian Rogers To: Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Oliver Upton , Yang Jihong , linux-kernel@vger.kernel.org, linux-perf-users@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1792301106658480327 X-GMAIL-MSGID: 1792301106658480327 The threads data structure is an array of hashmaps, previously rbtrees. The two levels allows for a fixed outer array where access is guarded by rw_semaphores. Commit 91e467bc568f ("perf machine: Use hashtable for machine threads") sized the outer table at 256 entries to avoid future scalability problems, however, this means the threads struct is sized at 30,720 bytes. As the hashmaps allow O(1) access for the common find/insert/remove operations, lower the number of entries to 8. This reduces the size overhead to 960 bytes. Signed-off-by: Ian Rogers --- tools/perf/util/threads.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tools/perf/util/threads.h b/tools/perf/util/threads.h index d03bd91a7769..da68d2223f18 100644 --- a/tools/perf/util/threads.h +++ b/tools/perf/util/threads.h @@ -7,7 +7,7 @@ struct thread; -#define THREADS__TABLE_BITS 8 +#define THREADS__TABLE_BITS 3 #define THREADS__TABLE_SIZE (1 << THREADS__TABLE_BITS) struct threads_table_entry {