lists.openwall.net   lists  /  announce  owl-users  owl-dev  john-users  john-dev  passwdqc-users  yescrypt  popa3d-users  /  oss-security  kernel-hardening  musl  sabotage  tlsify  passwords  /  crypt-dev  xvendor  /  Bugtraq  Full-Disclosure  linux-kernel  linux-netdev  linux-ext4  linux-hardening  linux-cve-announce  PHC 
Open Source and information security mailing list archives
 
Hash Suite: Windows password security audit tool. GUI, reports in PDF.
[<prev] [next>] [thread-next>] [day] [month] [year] [list]
Message-Id: <20240703172117.810918-1-irogers@google.com>
Date: Wed,  3 Jul 2024 10:21:15 -0700
From: Ian Rogers <irogers@...gle.com>
To: Peter Zijlstra <peterz@...radead.org>, Ingo Molnar <mingo@...hat.com>, 
	Arnaldo Carvalho de Melo <acme@...nel.org>, Namhyung Kim <namhyung@...nel.org>, 
	Mark Rutland <mark.rutland@....com>, 
	Alexander Shishkin <alexander.shishkin@...ux.intel.com>, Jiri Olsa <jolsa@...nel.org>, 
	Ian Rogers <irogers@...gle.com>, Adrian Hunter <adrian.hunter@...el.com>, 
	Kan Liang <kan.liang@...ux.intel.com>, Athira Rajeev <atrajeev@...ux.vnet.ibm.com>, 
	linux-perf-users@...r.kernel.org, linux-kernel@...r.kernel.org, 
	Steinar Gunderson <sesse@...gle.com>, Matt Fleming <matt@...dmodwrite.com>
Subject: [PATCH v1 0/2] Try to avoid some qsorts

Reference count checking doesn't work well with rbtree due to the need
for counts on each child and parent edge. As such the reference count
checking changes removed rbtree and replaced them with sorted
arrays. There have been instances where sorting has been shown to be a
regression:
https://lore.kernel.org/lkml/20240521165109.708593-1-irogers@google.com/

These patches address a further 2 cases in comm and dsos, avoiding a
sort when the array is already sorted at the cost of an O(n) memmove.

Ian Rogers (2):
  perf comm str: Avoid sort during insert
  perf dsos: When adding a dso into sorted dsos maintain the sort order

 tools/perf/util/comm.c | 29 ++++++++++++++++++-----------
 tools/perf/util/dsos.c | 26 +++++++++++++++++++++-----
 2 files changed, 39 insertions(+), 16 deletions(-)

-- 
2.45.2.803.g4e1b14247a-goog


Powered by blists - more mailing lists

Powered by Openwall GNU/*/Linux Powered by OpenVZ