From nobody Wed Feb 11 11:28:50 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.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 644DB3B1A1 for ; Tue, 21 May 2024 16:51:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716310282; cv=none; b=alO0p4XV0E/lNcQCtnadKNTt6ArK76y2Po53hTYMECuIOySYwJfHAdudiehytnSaOxviqSNTLmKp6jQ+Hrx+8Ap2kpisDQu9CqZUkhaTdf9DukrR+nK6GyFLiWoDpMcrrnpcIV8ZRQ9mVcdR63KswzD2o0mIsATZDu6PVeCfntU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716310282; c=relaxed/simple; bh=CQhX3rHzsitnHPfXKQHoTLwMmtFJKqDCMNaUjS6EnNA=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=YjuPQ4vEkJQQadb6wBi0wgvTXTBeWrWsz0hVAK4vsl1vBBF3usI8d1qFyVcLpPNNHKbcQRks9gOirovhtMLSF86Hb9NCfjitOyGAHNfyOVG+n7P1dmNEx95LDl1sN/3F5J8C5+ncs2L8lCuEl//ekjXkeorXKBe5McJrL77/nkk= 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=kqfsDjR/; arc=none smtp.client-ip=209.85.219.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 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="kqfsDjR/" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dc647f65573so28252138276.2 for ; Tue, 21 May 2024 09:51:21 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1716310280; x=1716915080; 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=kUfTujR33N1wGIzFWyd3IGvA2YqCHOAb96ZV/yApJRQ=; b=kqfsDjR/2+71WblNqgOHbu6WvgolPFFZXzwadOTz+ixKpdE1fmO8LljJVw4PvgZLM+ eA8vpInbpFeTvBaVBrdb9OiXiGDk10Wy7LJeNv4lb/k7+RzcbSJi7StK/WQxKA2A4Sxo K6ifexhv/tjEQZ37Vvm31UGFWfxmIPwJHutOpUvegUgBn6fzZu6UCFEQGhrbo/hgI3CX 3JV4KdYM8R/BWxH3kdmmWPNeGMoggqPudhuiLkLbIcUaZ/BnMr/CMXRxe3vBWlHiFFfT Aa55AlMn5YlFfYu05io32p3339wr0T7PFj9cfRYd70wl0ux8GV2zBQFsS2K5qZB7/N7g GsNQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716310280; x=1716915080; 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=kUfTujR33N1wGIzFWyd3IGvA2YqCHOAb96ZV/yApJRQ=; b=cnSn79econr+YT5nZgUDFFo+QL8X/SSRIuVNrJfH+ZHSO0bCZSJWYUWYb2JDH38YVa C4xT0xQeQXjBJ+g9YZCAdIPnHR4+d74duvweQxBqBDy23XfOQLZGDNr1++HGkZVubnwF fvX7MHRAcPG59viQpkInlw5T31VxgugjpdKo/tB+wBTeUHMWAiVHzTTauMx+wfjroWu9 ifJgglbWIurVe9Qbvqaq0/iV9ax5eWseXgvl06ZMtg6I+6IthFn27H4YcvZxMXcFnj3s qHnbi6zVsc9Fo2bBZaa6B2Sj81rav0mFQ1H6QSgDihhJCF7yxKr3t+PGN2YXlubrwmu3 xNkQ== X-Forwarded-Encrypted: i=1; AJvYcCX7mYEy6OZrmB3K0lrBn9jYV9jpdtdN0It6b39Q6p663UTvG6wQQD8sPR1rS87hMHD3kg5NpXv0fLBdw/Y8L0I9T2uKocvS7kH4bRvy X-Gm-Message-State: AOJu0YwkMn1BUz8+HaYZJ9vNt5BHF+DtxpVBVXaVS+yoQfYGPvblH8AT dIfsJDJQYFdSM9P24Vju1i8/OPL4fhBzYp4jUumyFO4NwU98nAAOuKEuWnZOEJqH3txleTbFm1S diRerxA== X-Google-Smtp-Source: AGHT+IEuLf9iy7F2mWUl3KPhny2cf+IIv1BpZOjLYfGWEbsRN5JmdbXDf2IAFJszFFLx+QPs+6hSVgUIXJLw X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:8533:b29a:936d:651a]) (user=irogers job=sendgmr) by 2002:a25:7486:0:b0:de5:2325:72a1 with SMTP id 3f1490d57ef6-dee4f192850mr8133573276.4.1716310280333; Tue, 21 May 2024 09:51:20 -0700 (PDT) Date: Tue, 21 May 2024 09:51:07 -0700 In-Reply-To: <20240521165109.708593-1-irogers@google.com> Message-Id: <20240521165109.708593-2-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240521165109.708593-1-irogers@google.com> X-Mailer: git-send-email 2.45.0.rc1.225.g2a3ae87e7f-goog Subject: [PATCH v1 1/3] perf maps: Fix use after free in __maps__fixup_overlap_and_insert From: Ian Rogers To: "Steinar H . Gunderson" , Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" In the case 'before' and 'after' are broken out from pos, maps_by_address may be changed by __maps__insert, as such it needs re-reading. Don't ignore the return value from __maps_insert. Fixes: 659ad3492b91 ("perf maps: Switch from rbtree to lazily sorted array = for addresses") Signed-off-by: Ian Rogers Reviewed-by: James Clark --- tools/perf/util/maps.c | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index 16b39db594f4..eaada3e0f5b4 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -741,7 +741,6 @@ static unsigned int first_ending_after(struct maps *map= s, const struct map *map) */ static int __maps__fixup_overlap_and_insert(struct maps *maps, struct map = *new) { - struct map **maps_by_address; int err =3D 0; FILE *fp =3D debug_file(); =20 @@ -749,12 +748,12 @@ static int __maps__fixup_overlap_and_insert(struct ma= ps *maps, struct map *new) if (!maps__maps_by_address_sorted(maps)) __maps__sort_by_address(maps); =20 - maps_by_address =3D maps__maps_by_address(maps); /* * Iterate through entries where the end of the existing entry is * greater-than the new map's start. */ for (unsigned int i =3D first_ending_after(maps, new); i < maps__nr_maps(= maps); ) { + struct map **maps_by_address =3D maps__maps_by_address(maps); struct map *pos =3D maps_by_address[i]; struct map *before =3D NULL, *after =3D NULL; =20 @@ -821,8 +820,10 @@ static int __maps__fixup_overlap_and_insert(struct map= s *maps, struct map *new) /* Maps are still ordered, go to next one. */ i++; if (after) { - __maps__insert(maps, after); + err =3D __maps__insert(maps, after); map__put(after); + if (err) + goto out_err; if (!maps__maps_by_address_sorted(maps)) { /* * Sorting broken so invariants don't @@ -851,7 +852,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) check_invariants(maps); } /* Add the map. */ - __maps__insert(maps, new); + err =3D __maps__insert(maps, new); out_err: return err; } --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Feb 11 11:28:50 2026 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 93A991482E8 for ; Tue, 21 May 2024 16:51:23 +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=1716310285; cv=none; b=hjlhtCQ5G0hxHX9Fpq+CM7gIwt9An1cIDGs5znPcrnLn/1agMr83m7+OBsfNkjZS5uUNYKhnX5L8L5GXnhLC6NG/Ve0DhSRnYK82HjSCXMkjgUVrXTx2l5XnZeIGGEAd65x4VocPN5AYtCHhQVTXg4lAIzu0xy6nW5rQBk1y97k= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716310285; c=relaxed/simple; bh=tPSaX4kgNdawUQHbzIdUZTi3pOEIe8Q/D+semVgAOx0=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=AdcBXJWNA1pdiLFzAinDICRtEwfM7EYjNNDM8jnOkhIeGSnI4ago/b83tZirGX65TGnPTPzpViPP0PjIrfg+9tju60OA6vWtbAMy5z8tuxFB1fso9MOtm8cP4E3dm69ZX8uO6XoW1fEcjC96+ZuwGrsLE85doOZuBo4DvYPxZTI= 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=oH5M9QeO; 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 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="oH5M9QeO" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-de54be7066bso22686513276.0 for ; Tue, 21 May 2024 09:51:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1716310282; x=1716915082; 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=GALuswTvDeGvafJWqEPTd/XeiOrV3kZLnFJgLvJhAUk=; b=oH5M9QeOWNJ5FA32CxInPMESnNIyVjCjh/aLTTsj6CqTrWrYTUuFj9iy8yHmUkJJ8E B9MeDbzvriMI11GPyS0TKouTQtBOWYKFRumAh96PoxEFUhISwzlKuKSWbdY3iXnboT+3 5rtZTI8Lsna1Y3UdX24N/V1aRzlO07p/sDupKgTBMBmaQ9dT+QirLKdzK5+4a4MbpLsv vgpXEldtscNcLE07NcfdDtJkEXVXLRtLVOeQu/QP2tMJQgL3xHNnIMdwn5lwa/2TsD3K 7tvtliCDI6aNBhWWwvMBeWGDjWLrRdO5JO4g7mFZe6K65TabhPBv4Av4z8+3W7isIGLJ zI0g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716310282; x=1716915082; 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=GALuswTvDeGvafJWqEPTd/XeiOrV3kZLnFJgLvJhAUk=; b=scVntJDgNhy4+k7iWIkED2P3FbmVtbYw9ZOSY9cIUatHbLmhsReGPKtiag1QVJEfHM TCAuKjd/ZttIZ0ymdz83FEi9UPnZO2qZGCQ/vUKFt5BYBC5lse8LCyrBouRhL1TAZVq/ qU/R405vl5y76c2oOPrsNcAgVEw0zqgl74EZ+T4BIpcI1Q46+1zFVLveGmn1oiQg07xK ikwurjvmw8X+ypt6ZK5QK2q/1r0Ax+t+rarqqtmJV2qADgMNQE982eW4tz0N2GHmb6+F TWF6H4ffzKlJd8EY+jLdqBRWckUXEGkqxVZYv18Da8SZ6Xko0NQg6kv9id+goewL5B8Q V1aQ== X-Forwarded-Encrypted: i=1; AJvYcCUn7r1edrHeVvSwlZRNGSNfFWnLQ5IUYa6i9SEWi2KsKJGdUSYQcRu+WSa8+NhRhqsCvSb6PZU2wcjJQNI4ALtjEgxDsgxf6h2YBLHX X-Gm-Message-State: AOJu0Yx1XFw9VoK2p5D09QLeuaFS0UoMF8191hWZi2zS6uXJvcjkEiPW 44s+k4w2WN1FgFhlzLs25JDOgWHjhk79T5/ENTX9T5dsT26sO8n/k6SXqQGvseoLYmRdXfr5MvN 6o02nVw== X-Google-Smtp-Source: AGHT+IHyxz1G47wF2s3bV2sJZ7BCwtJ5wIApcqKBerxN0xjf64+D1FZUO9DZ+jkVlmIRif26c1JY6TzDlsqS X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:8533:b29a:936d:651a]) (user=irogers job=sendgmr) by 2002:a05:6902:c10:b0:de6:1301:600a with SMTP id 3f1490d57ef6-dee4f374414mr8390517276.9.1716310282509; Tue, 21 May 2024 09:51:22 -0700 (PDT) Date: Tue, 21 May 2024 09:51:08 -0700 In-Reply-To: <20240521165109.708593-1-irogers@google.com> Message-Id: <20240521165109.708593-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: <20240521165109.708593-1-irogers@google.com> X-Mailer: git-send-email 2.45.0.rc1.225.g2a3ae87e7f-goog Subject: [PATCH v1 2/3] perf maps: Reduce sorting for overlapping mappings From: Ian Rogers To: "Steinar H . Gunderson" , Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" When an 'after' map is generated the 'new' map must be before it so terminate iterating and don't resort. If the entry 'pos' is entirely overlapped by the 'new' mapping then don't remove and insert the mapping, just replace - again to remove sorting. For a perf report on a perf.data file containing overlapping mappings the time numbers are: Before: real 0m9.856s user 0m9.637s sys 0m0.204s After: real 0m5.894s user 0m5.650s sys 0m0.231s Signed-off-by: Ian Rogers Reviewed-by: James Clark --- tools/perf/util/maps.c | 55 +++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 19 deletions(-) diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index eaada3e0f5b4..f6b6df82f4cf 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -744,7 +744,6 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) int err =3D 0; FILE *fp =3D debug_file(); =20 -sort_again: if (!maps__maps_by_address_sorted(maps)) __maps__sort_by_address(maps); =20 @@ -820,36 +819,54 @@ static int __maps__fixup_overlap_and_insert(struct ma= ps *maps, struct map *new) /* Maps are still ordered, go to next one. */ i++; if (after) { - err =3D __maps__insert(maps, after); - map__put(after); - if (err) - goto out_err; - if (!maps__maps_by_address_sorted(maps)) { - /* - * Sorting broken so invariants don't - * hold, sort and go again. - */ - goto sort_again; - } /* - * Maps are still ordered, skip after and go to - * next one (terminate loop). + * 'before' and 'after' mean 'new' split the + * 'pos' mapping and therefore there are no + * later mappings. */ - i++; + err =3D __maps__insert(maps, new); + if (!err) + err =3D __maps__insert(maps, after); + map__put(after); + check_invariants(maps); + return err; } + check_invariants(maps); } else if (after) { + /* + * 'after' means 'new' split 'pos' and there are no + * later mappings. + */ map__put(maps_by_address[i]); - maps_by_address[i] =3D after; - /* Maps are ordered, go to next one. */ - i++; + maps_by_address[i] =3D map__get(new); + err =3D __maps__insert(maps, after); + map__put(after); + check_invariants(maps); + return err; } else { + struct map *next =3D NULL; + + if (i + 1 < maps__nr_maps(maps)) + next =3D maps_by_address[i + 1]; + + if (!next || map__start(next) >=3D map__end(new)) { + /* + * Replace existing mapping and end knowing + * there aren't later overlapping or any + * mappings. + */ + map__put(maps_by_address[i]); + maps_by_address[i] =3D map__get(new); + check_invariants(maps); + return err; + } __maps__remove(maps, pos); + check_invariants(maps); /* * Maps are ordered but no need to increase `i` as the * later maps were moved down. */ } - check_invariants(maps); } /* Add the map. */ err =3D __maps__insert(maps, new); --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Feb 11 11:28:50 2026 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 78414148837 for ; Tue, 21 May 2024 16:51:25 +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=1716310287; cv=none; b=i37Uq9qpKJXqQsXNAcr8r9Bgfobn3NXaGLpR6/10ht38eVfOOohGt+hy1AHTbc8X60Ycwju2Wr0ET1xJEZUekdYkWIKYezhaPlAzwvPiKXF4oNgYFb7YXFJTigJbhPO01Wx8fbGNNPs4F/yYZUijW6YrKLitIiqVgg/FOreuf1I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1716310287; c=relaxed/simple; bh=Dhw2Jh5mBReYK2KdFz4zu0dZX2l7oWPnI/weHg4qPJE=; h=Date:In-Reply-To:Message-Id:Mime-Version:References:Subject:From: To:Content-Type; b=kcFD3q8AH4XDDqfEZ4lrcCV4pHuFUkYY05JfFekUKNPPZeRc9YgxnicPQUlI1XzWur/cXLpR43J3MyOFSVNIusTpbVxIi6wSpHJNsJ9ujV11HJxDKDzFOSGvleL38zTlXItgRQGK1jhegiYmqJEGMFd3IsdNyOp/6iWojUIOj3U= 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=yK8zbv7f; 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 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="yK8zbv7f" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-de468af2b73so23312062276.0 for ; Tue, 21 May 2024 09:51:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1716310284; x=1716915084; 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=PrE0BOJf8HvNnLMD4w6E9MqTE92sz3IiyAicOOYr1ws=; b=yK8zbv7fnnKrxUw0bdPK3liBpBANcPMlNCLuGxIGFX/f8eyTeirdtbmOYA8fX4y6E5 zJ8QsSXuLxsdVDLkzjvj/KuHCPI4bNu08ag7y1JOzHG5IahRCpQIQlT9s8ytzSkXgmTD IYaPKoQ8fSiISN70uF0p1IEYCyhuVnFkagzCll74ZgbnsN45q8vkFcec/qd9j0vcJO4q 6FQ6TnTHtxNR/TLMfoJyqiCnVqZEEtbgXHWRPGNEK1mTQCr2Kvzn/tjJjC3FJJ9VriTr dSW1YgheM+udjzN8B/oTcXj+KL16eXHkcRXZjd9ZBoGtDsi8BcEYXvgFSRZsggS83xev ZfCQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1716310284; x=1716915084; 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=PrE0BOJf8HvNnLMD4w6E9MqTE92sz3IiyAicOOYr1ws=; b=opisP/JBZWBeN/j0iJuGAfDyVBMjJCgYvKlBqrIYoZdGpLDk7T9qREIfH9AByeWUs5 G9+67+W48OuUslkMKWymDZAhcltWo3ClbyIwvUrSKbEQCvLcmhw6ClLKdJXzDM8tSwOh fevpoHCYXKlcRQE5mtj+2YxSACw/iM3iuYpwGImBiWU7sc5uEUWKKf0Sxbj3qKNkguhZ eAK+WsTI/hHBKx9CanW/djrYFeRnPHCWRyI9+oDTMx0QtirYbQUKI8vWGVljZ0A1G/8b aaw+W+eL+CtOj2MnFvbyOqXAPkkojl0aClFiNOcqOeI+TJ15+nudAdARIjBRAC1b9W1I 77Jw== X-Forwarded-Encrypted: i=1; AJvYcCVe8V5hpqeWx9hBTfamTjzouWsipxMocEMOAeZDU/fC6scXmAvsQ3zDF71gyr/fptM9dAA1GK6yEoUf7vQ27TLt/d5SqGcl4YuhIZF+ X-Gm-Message-State: AOJu0Yyx1Kp80jd3bctxD74CmqJCeHcHWt3Mt0ijb62tcOf38MKSJAZ9 yt8BgJwH2B3KfRqBdAL1/6aop50WH0K0g4qhSgr4VT00HErPf8nneWWiyryTAEGQy+4efFiOglk u/6mV9g== X-Google-Smtp-Source: AGHT+IHTBwsqs2wQ8TlnvMpoDM7P28140rp8Mfd1Iad6gC/LK63BwUOu/9UX9LlDgAfvx3yzOt1h8kHrBWwS X-Received: from irogers.svl.corp.google.com ([2620:15c:2a3:200:8533:b29a:936d:651a]) (user=irogers job=sendgmr) by 2002:a05:6902:100b:b0:df4:9b3d:66a9 with SMTP id 3f1490d57ef6-df49b3d9b15mr2457254276.10.1716310284725; Tue, 21 May 2024 09:51:24 -0700 (PDT) Date: Tue, 21 May 2024 09:51:09 -0700 In-Reply-To: <20240521165109.708593-1-irogers@google.com> Message-Id: <20240521165109.708593-4-irogers@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240521165109.708593-1-irogers@google.com> X-Mailer: git-send-email 2.45.0.rc1.225.g2a3ae87e7f-goog Subject: [PATCH v1 3/3] perf maps: Add/use a sorted insert for fixup overlap and insert From: Ian Rogers To: "Steinar H . Gunderson" , Peter Zijlstra , Ingo Molnar , Arnaldo Carvalho de Melo , Namhyung Kim , Mark Rutland , Alexander Shishkin , Jiri Olsa , Ian Rogers , Adrian Hunter , Kan Liang , linux-perf-users@vger.kernel.org, linux-kernel@vger.kernel.org Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Data may have lots of overlapping mmaps. The regular insert adds at the end and relies on a later sort. For data with overlapping mappings the sort will happen during a subsequent maps__find or __maps__fixup_overlap_and_insert, there's never a period where the inserted maps buffer up and a single sort happens. To avoid back to back sorts, maintain the sort order when fixing up and inserting. Previously the first_ending_after search was O(log n) where n is the size of maps, and the insert was O(1) but because of the continuous sorting was becoming O(n*log(n)). With maintaining sort order, the insert now becomes O(n) for a memmove. For a perf report on a perf.data file containing overlapping mappings the time numbers are: Before: real 0m5.894s user 0m5.650s sys 0m0.231s After: real 0m0.675s user 0m0.454s sys 0m0.196s Signed-off-by: Ian Rogers Reviewed-by: James Clark --- tools/perf/util/maps.c | 65 ++++++++++++++++++++++++++++++++++++++---- 1 file changed, 59 insertions(+), 6 deletions(-) diff --git a/tools/perf/util/maps.c b/tools/perf/util/maps.c index f6b6df82f4cf..432399cbe5dd 100644 --- a/tools/perf/util/maps.c +++ b/tools/perf/util/maps.c @@ -735,6 +735,60 @@ static unsigned int first_ending_after(struct maps *ma= ps, const struct map *map) return first; } =20 +static int __maps__insert_sorted(struct maps *maps, unsigned int first_aft= er_index, + struct map *new1, struct map *new2) +{ + struct map **maps_by_address =3D maps__maps_by_address(maps); + struct map **maps_by_name =3D maps__maps_by_name(maps); + unsigned int nr_maps =3D maps__nr_maps(maps); + unsigned int nr_allocate =3D RC_CHK_ACCESS(maps)->nr_maps_allocated; + unsigned int to_add =3D new2 ? 2 : 1; + + assert(maps__maps_by_address_sorted(maps)); + assert(first_after_index =3D=3D nr_maps || + map__end(new1) <=3D map__start(maps_by_address[first_after_index])= ); + assert(!new2 || map__end(new1) <=3D map__start(new2)); + assert(first_after_index =3D=3D nr_maps || !new2 || + map__end(new2) <=3D map__start(maps_by_address[first_after_index])= ); + + if (nr_maps + to_add > nr_allocate) { + nr_allocate =3D !nr_allocate ? 32 : nr_allocate * 2; + + maps_by_address =3D realloc(maps_by_address, nr_allocate * sizeof(new1)); + if (!maps_by_address) + return -ENOMEM; + + maps__set_maps_by_address(maps, maps_by_address); + if (maps_by_name) { + maps_by_name =3D realloc(maps_by_name, nr_allocate * sizeof(new1)); + if (!maps_by_name) { + /* + * If by name fails, just disable by name and it will + * recompute next time it is required. + */ + __maps__free_maps_by_name(maps); + } + maps__set_maps_by_name(maps, maps_by_name); + } + RC_CHK_ACCESS(maps)->nr_maps_allocated =3D nr_allocate; + } + memmove(&maps_by_address[first_after_index+to_add], + &maps_by_address[first_after_index], + (nr_maps - first_after_index) * sizeof(new1)); + maps_by_address[first_after_index] =3D map__get(new1); + if (maps_by_name) + maps_by_name[nr_maps] =3D map__get(new1); + if (new2) { + maps_by_address[first_after_index + 1] =3D map__get(new2); + if (maps_by_name) + maps_by_name[nr_maps + 1] =3D map__get(new2); + } + RC_CHK_ACCESS(maps)->nr_maps =3D nr_maps + to_add; + maps__set_maps_by_name_sorted(maps, false); + check_invariants(maps); + return 0; +} + /* * Adds new to maps, if new overlaps existing entries then the existing ma= ps are * adjusted or removed so that new fits without overlapping any entries. @@ -743,6 +797,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) { int err =3D 0; FILE *fp =3D debug_file(); + unsigned int i; =20 if (!maps__maps_by_address_sorted(maps)) __maps__sort_by_address(maps); @@ -751,7 +806,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) * Iterate through entries where the end of the existing entry is * greater-than the new map's start. */ - for (unsigned int i =3D first_ending_after(maps, new); i < maps__nr_maps(= maps); ) { + for (i =3D first_ending_after(maps, new); i < maps__nr_maps(maps); ) { struct map **maps_by_address =3D maps__maps_by_address(maps); struct map *pos =3D maps_by_address[i]; struct map *before =3D NULL, *after =3D NULL; @@ -824,9 +879,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) * 'pos' mapping and therefore there are no * later mappings. */ - err =3D __maps__insert(maps, new); - if (!err) - err =3D __maps__insert(maps, after); + err =3D __maps__insert_sorted(maps, i, new, after); map__put(after); check_invariants(maps); return err; @@ -839,7 +892,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) */ map__put(maps_by_address[i]); maps_by_address[i] =3D map__get(new); - err =3D __maps__insert(maps, after); + err =3D __maps__insert_sorted(maps, i + 1, after, NULL); map__put(after); check_invariants(maps); return err; @@ -869,7 +922,7 @@ static int __maps__fixup_overlap_and_insert(struct maps= *maps, struct map *new) } } /* Add the map. */ - err =3D __maps__insert(maps, new); + err =3D __maps__insert_sorted(maps, i, new, NULL); out_err: return err; } --=20 2.45.0.rc1.225.g2a3ae87e7f-goog