linux.git/tools/perf/util/maps.c, branch v6.9

perf map: Fix map reference count issues

2024-03-01T02:06:00+00:00

The find will get the map, ensure puts are done on all paths.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: Masami Hiramatsu 
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240229062048.558799-1-irogers@google.com

perf maps: Locking tidy up of nr_maps

2024-02-12T20:35:41+00:00

After this change maps__nr_maps is only used by tests, existing users
are migrated to maps__empty. Compute maps__empty under the read lock.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-7-irogers@google.com

perf maps: Hide maps internals

2024-02-12T20:35:41+00:00

Move the struct into the C file. Add maps__equal to work around
exposing the struct for reference count checking. Add accessors for
the unwind_libunwind_ops. Move maps_list_node to its only use in
symbol.c.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-6-irogers@google.com

perf maps: Get map before returning in maps__find_next_entry

2024-02-12T20:35:41+00:00

Finding a map is done under a lock, returning the map without a
reference count means it can be removed without notice and causing
uses after free. Grab a reference count to the map within the lock
region and return this. Fix up locations that need a map__put
following this.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-5-irogers@google.com

perf maps: Get map before returning in maps__find_by_name

2024-02-12T20:35:33+00:00

Finding a map is done under a lock, returning the map without a
reference count means it can be removed without notice and causing
uses after free. Grab a reference count to the map within the lock
region and return this. Fix up locations that need a map__put
following this. Also fix some reference counted pointer comparisons.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-4-irogers@google.com

perf maps: Get map before returning in maps__find

2024-02-12T20:35:26+00:00

Finding a map is done under a lock, returning the map without a
reference count means it can be removed without notice and causing
uses after free. Grab a reference count to the map within the lock
region and return this. Fix up locations that need a map__put
following this.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-3-irogers@google.com

perf maps: Switch from rbtree to lazily sorted array for addresses

2024-02-12T20:35:14+00:00

Maps is a collection of maps primarily sorted by the starting address
of the map. Prior to this change the maps were held in an rbtree
requiring 4 pointers per node. Prior to reference count checking, the
rbnode was embedded in the map so 3 pointers per node were
necessary. This change switches the rbtree to an array lazily sorted
by address, much as the array sorting nodes by name. 1 pointer is
needed per node, but to avoid excessive resizing the backing array may
be twice the number of used elements. Meaning the memory overhead is
roughly half that of the rbtree. For a perf record with
"--no-bpf-event -g -a" of true, the memory overhead of perf inject is
reduce fom 3.3MB to 3MB, so 10% or 300KB is saved.

Map inserts always happen at the end of the array. The code tracks
whether the insertion violates the sorting property. O(log n) rb-tree
complexity is switched to O(1).

Remove slides the array, so O(log n) rb-tree complexity is degraded to
O(n).

A find may need to sort the array using qsort which is O(n*log n), but
in general the maps should be sorted and so average performance should
be O(log n) as with the rbtree.

An rbtree node consumes a cache line, but with the array 4 nodes fit
on a cache line. Iteration is simplified to scanning an array rather
than pointer chasing.

Overall it is expected the performance after the change should be
comparable to before, but with half of the memory consumed.

To avoid a list and repeated logic around splitting maps,
maps__merge_in is rewritten in terms of
maps__fixup_overlap_and_insert. maps_merge_in splits the given mapping
inserting remaining gaps. maps__fixup_overlap_and_insert splits the
existing mappings, then adds the incoming mapping. By adding the new
mapping first, then re-inserting the existing mappings the splitting
behavior matches.

Signed-off-by: Ian Rogers 
Acked-by: Namhyung Kim 
Cc: K Prateek Nayak 
Cc: James Clark 
Cc: Vincent Whitchurch 
Cc: Alexey Dobriyan 
Cc: Colin Ian King 
Cc: Changbin Du 
Cc: Masami Hiramatsu 
Cc: Song Liu 
Cc: Leo Yan 
Cc: Athira Rajeev 
Cc: Liam Howlett 
Cc: Artem Savkov 
Cc: bpf@vger.kernel.org
Signed-off-by: Namhyung Kim 
Link: https://lore.kernel.org/r/20240210031746.4057262-2-irogers@google.com

perf maps: Fix up overlaps during fixup_end

2023-12-20T18:02:36+00:00

Maps are sometimes made overlapping, in particular kernel maps. If the
end of a map overlaps the start of the next, shorten the overlapping
map. This should remove potential non-determinism in maps__find, ie
finding maps by address.

Signed-off-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Andi Kleen 
Cc: Athira Rajeev 
Cc: Changbin Du 
Cc: Colin Ian King 
Cc: Dmitrii Dolgov <9erthalion6@gmail.com>
Cc: German Gomez 
Cc: Guilherme Amadio 
Cc: Huacai Chen 
Cc: Ingo Molnar 
Cc: James Clark 
Cc: Jiri Olsa 
Cc: K Prateek Nayak 
Cc: Kajol Jain 
Cc: Kan Liang 
Cc: Leo Yan 
Cc: Li Dong 
Cc: Liam Howlett 
Cc: Mark Rutland 
Cc: Masami Hiramatsu 
Cc: Miguel Ojeda 
Cc: Ming Wang 
Cc: Namhyung Kim 
Cc: Nick Terrell 
Cc: Paolo Bonzini 
Cc: Peter Zijlstra 
Cc: Ravi Bangoria 
Cc: Sandipan Das 
Cc: Sean Christopherson 
Cc: Steinar H. Gunderson 
Cc: Vincent Whitchurch 
Cc: Wenyu Liu 
Cc: Yang Jihong 
Link: https://lore.kernel.org/r/20231207011722.1220634-23-irogers@google.com
Signed-off-by: Arnaldo Carvalho de Melo

perf maps: Reduce scope of map_rb_node and maps internals

2023-12-20T18:02:17+00:00

Avoid exposing the implementation of maps so that the internals can be
refactored.

Signed-off-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Andi Kleen 
Cc: Athira Rajeev 
Cc: Changbin Du 
Cc: Colin Ian King 
Cc: Dmitrii Dolgov <9erthalion6@gmail.com>
Cc: German Gomez 
Cc: Guilherme Amadio 
Cc: Huacai Chen 
Cc: Ingo Molnar 
Cc: James Clark 
Cc: Jiri Olsa 
Cc: K Prateek Nayak 
Cc: Kajol Jain 
Cc: Kan Liang 
Cc: Leo Yan 
Cc: Li Dong 
Cc: Liam Howlett 
Cc: Mark Rutland 
Cc: Masami Hiramatsu 
Cc: Miguel Ojeda 
Cc: Ming Wang 
Cc: Namhyung Kim 
Cc: Nick Terrell 
Cc: Paolo Bonzini 
Cc: Peter Zijlstra 
Cc: Ravi Bangoria 
Cc: Sandipan Das 
Cc: Sean Christopherson 
Cc: Steinar H. Gunderson 
Cc: Vincent Whitchurch 
Cc: Wenyu Liu 
Cc: Yang Jihong 
Link: https://lore.kernel.org/r/20231207011722.1220634-22-irogers@google.com
Signed-off-by: Arnaldo Carvalho de Melo

perf maps: Add find next entry to give entry after the given map

2023-12-20T18:02:02+00:00

Use to remove map_rb_node use from machine.c.

Signed-off-by: Ian Rogers 
Cc: Adrian Hunter 
Cc: Alexander Shishkin 
Cc: Andi Kleen 
Cc: Athira Rajeev 
Cc: Changbin Du 
Cc: Colin Ian King 
Cc: Dmitrii Dolgov <9erthalion6@gmail.com>
Cc: German Gomez 
Cc: Guilherme Amadio 
Cc: Huacai Chen 
Cc: Ingo Molnar 
Cc: James Clark 
Cc: Jiri Olsa 
Cc: K Prateek Nayak 
Cc: Kajol Jain 
Cc: Kan Liang 
Cc: Leo Yan 
Cc: Li Dong 
Cc: Liam Howlett 
Cc: Mark Rutland 
Cc: Masami Hiramatsu 
Cc: Miguel Ojeda 
Cc: Ming Wang 
Cc: Namhyung Kim 
Cc: Nick Terrell 
Cc: Paolo Bonzini 
Cc: Peter Zijlstra 
Cc: Ravi Bangoria 
Cc: Sandipan Das 
Cc: Sean Christopherson 
Cc: Steinar H. Gunderson 
Cc: Vincent Whitchurch 
Cc: Wenyu Liu 
Cc: Yang Jihong 
Link: https://lore.kernel.org/r/20231207011722.1220634-21-irogers@google.com
Signed-off-by: Arnaldo Carvalho de Melo