kernel/linux.git/tools/perf/util/map.c, branch linux-6.9.y

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 tools: Remove misleading comments on map functions

2024-02-09T22:08:41+00:00

When it converts sample IP to or from objdump-capable one, there's a comment saying that kernel modules have DSO_SPACE__USER. But commit 02213cec64bb ("perf maps: Mark module DSOs with kernel type") changed it and makes the comment confusing. Let's get rid of it. Signed-off-by: Namhyung Kim Acked-by: Arnaldo Carvalho de Melo Reviewed-by: Ian Rogers Link: https://lore.kernel.org/r/20240208181025.1329645-1-namhyung@kernel.org

perf map: Simplify map_ip/unmap_ip and make 'struct map' smaller

2023-12-06T16:01:42+00:00

When mapping an IP it is either an identity mapping or a DSO relative mapping, so a single bit is required in the struct to identify this. The current code uses function pointers, adding 2 pointers per map and also pushing the size of a map beyond 1 cache line. Switch to using a byte to identify the mapping type (as well as priv and erange_warned), to avoid any masking. Change struct maps's layout to avoid holes. Before: ``` struct map { u64 start; /* 0 8 */ u64 end; /* 8 8 */ _Bool erange_warned:1; /* 16: 0 1 */ _Bool priv:1; /* 16: 1 1 */ /* XXX 6 bits hole, try to pack */ /* XXX 3 bytes hole, try to pack */ u32 prot; /* 20 4 */ u64 pgoff; /* 24 8 */ u64 reloc; /* 32 8 */ u64 (*map_ip)(const struct map *, u64); /* 40 8 */ u64 (*unmap_ip)(const struct map *, u64); /* 48 8 */ struct dso * dso; /* 56 8 */ /* --- cacheline 1 boundary (64 bytes) --- */ refcount_t refcnt; /* 64 4 */ u32 flags; /* 68 4 */ /* size: 72, cachelines: 2, members: 12 */ /* sum members: 68, holes: 1, sum holes: 3 */ /* sum bitfield members: 2 bits, bit holes: 1, sum bit holes: 6 bits */ /* last cacheline: 8 bytes */ }; ``` After: ``` struct map { u64 start; /* 0 8 */ u64 end; /* 8 8 */ u64 pgoff; /* 16 8 */ u64 reloc; /* 24 8 */ struct dso * dso; /* 32 8 */ refcount_t refcnt; /* 40 4 */ u32 prot; /* 44 4 */ u32 flags; /* 48 4 */ enum mapping_type mapping_type:8; /* 52: 0 4 */ /* Bitfield combined with next fields */ _Bool erange_warned; /* 53 1 */ _Bool priv; /* 54 1 */ /* size: 56, cachelines: 1, members: 11 */ /* padding: 1 */ /* last cacheline: 56 bytes */ }; ``` Signed-off-by: Ian Rogers Acked-by: Namhyung Kim Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Andi Kleen Cc: Athira Jajeev 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 (Google) Cc: Miguel Ojeda Cc: Ming Wang 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/20231127220902.1315692-13-irogers@google.com Signed-off-by: Arnaldo Carvalho de Melo

perf symbol: Remove symbol_name_rb_node

2023-06-24T04:47:20+00:00

Most perf commands want to sort symbols by name and this is done via an invasive rbtree that on 64-bit systems costs 24 bytes. Sorting the symbols in a DSO by name is optional and not done by default, however, if sorting is requested the 24 bytes is allocated for every symbol. This change removes the rbtree and uses a sorted array of symbol pointers instead (costing 8 bytes per symbol). As the array is created on demand then there are further memory savings. The complexity of sorting the array and using the rbtree are the same. To support going to the next symbol, the index of the current symbol needs to be passed around as a pair with the current symbol. This requires some API changes. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim Cc: Carsten Haitzler Cc: Mark Rutland Cc: Jason Wang Cc: Changbin Du Cc: Yang Jihong Cc: Peter Zijlstra Cc: Adrian Hunter Cc: Arnaldo Carvalho de Melo Cc: Jiri Olsa Cc: Alexander Shishkin Cc: Kan Liang Cc: Athira Rajeev Cc: Ingo Molnar Cc: Christophe JAILLET Link: https://lore.kernel.org/r/20230623054520.4118442-3-irogers@google.com [ minimize change in symbols__sort_by_name() ] Signed-off-by: Namhyung Kim

perf dso: Sort symbols under lock

2023-06-24T04:44:48+00:00

Determine if symbols are sorted, set the sorted flag and sort under the dso lock. Done in the interest of thread safety. Signed-off-by: Ian Rogers Acked-by: Namhyung Kim Cc: Carsten Haitzler Cc: Mark Rutland Cc: Jason Wang Cc: Changbin Du Cc: Yang Jihong Cc: Peter Zijlstra Cc: Adrian Hunter Cc: Arnaldo Carvalho de Melo Cc: Jiri Olsa Cc: Alexander Shishkin Cc: Kan Liang Cc: Athira Rajeev Cc: Ingo Molnar Cc: Christophe JAILLET Link: https://lore.kernel.org/r/20230623054520.4118442-2-irogers@google.com [ handle the similar code in util/probe-event.c ] Signed-off-by: Namhyung Kim

perf srcline: Optimize comparision against SRCLINE_UNKNOWN

2023-06-12T21:17:00+00:00

This is a string constant that gets returned and then strcmp() around, we can instead just do a pointer comparision. That requires a new global variable to comply with these warnings from some versions of clang and gcc: 41 68.95 fedora:rawhide : FAIL clang version 16.0.4 (Fedora 16.0.4-1.fc39) result of comparison against a string literal is unspecified (use an explicit string comparison function instead) [-Werror,-Wstring-compare] if (start_line != SRCLINE_UNKNOWN && ^ ~~~~~~~~~~~~~~~ 41 Ack comments: Agreed, the strcmps make me nervous as they won't distinguish heap from a global meaning we could end up with things like pointers to freed memory. The comparison with the global is always going to be same imo. Acked-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Ali Saidi Cc: Andi Kleen Cc: Athira Rajeev Cc: Brian Robbins Cc: Changbin Du Cc: Dmitrii Dolgov <9erthalion6@gmail.com> Cc: Fangrui Song Cc: German Gomez Cc: Ingo Molnar Cc: Ivan Babrou Cc: James Clark Cc: Jing Zhang Cc: Jiri Olsa Cc: John Garry Cc: K Prateek Nayak Cc: Kan Liang Cc: Leo Yan Cc: Liam Howlett Cc: Mark Rutland Cc: Miguel Ojeda Cc: Mike Leach Cc: Namhyung Kim Cc: Naveen N. Rao Cc: Peter Zijlstra Cc: Ravi Bangoria Cc: Sean Christopherson Cc: Steinar H. Gunderson Cc: Suzuki Poulouse Cc: Wenyu Liu Cc: Will Deacon Cc: Yang Jihong Cc: Ye Xingchen Cc: Yuan Can Link: https://lore.kernel.org/lkml/ZIcoJytUEz4UgQYR@kernel.org Signed-off-by: Arnaldo Carvalho de Melo

perf srcline: Change free_srcline to zfree_srcline

2023-06-12T18:57:54+00:00

Make use after free more unlikely. Signed-off-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Ali Saidi Cc: Andi Kleen Cc: Athira Rajeev Cc: Brian Robbins Cc: Changbin Du Cc: Dmitrii Dolgov <9erthalion6@gmail.com> Cc: Fangrui Song Cc: German Gomez Cc: Ingo Molnar Cc: Ivan Babrou Cc: James Clark Cc: Jing Zhang Cc: Jiri Olsa Cc: John Garry Cc: K Prateek Nayak Cc: Kan Liang Cc: Leo Yan Cc: Liam Howlett Cc: Mark Rutland Cc: Miguel Ojeda Cc: Mike Leach Cc: Namhyung Kim Cc: Naveen N. Rao Cc: Peter Zijlstra Cc: Ravi Bangoria Cc: Sean Christopherson Cc: Steinar H. Gunderson Cc: Suzuki Poulouse Cc: Wenyu Liu Cc: Will Deacon Cc: Yang Jihong Cc: Ye Xingchen Cc: Yuan Can Cc: coresight@lists.linaro.org Cc: linux-arm-kernel@lists.infradead.org Link: https://lore.kernel.org/r/20230608232823.4027869-26-irogers@google.com Signed-off-by: Arnaldo Carvalho de Melo

perf thread: Add accessor functions for thread

2023-06-12T18:57:53+00:00

Using accessors will make it easier to add reference count checking in later patches. Committer notes: thread->nsinfo wasn't wrapped as it is used together with nsinfo__zput(), where does a trick to set the field with a refcount being dropped to NULL, and that doesn't work well with using thread__nsinfo(thread), that loses the &thread->nsinfo pointer. When refcount checking is added to 'struct thread', later in this series, nsinfo__zput(RC_CHK_ACCESS(thread)->nsinfo) will be used to check the thread pointer. Signed-off-by: Ian Rogers Cc: Adrian Hunter Cc: Alexander Shishkin Cc: Ali Saidi Cc: Andi Kleen Cc: Athira Rajeev Cc: Brian Robbins Cc: Changbin Du Cc: Dmitrii Dolgov <9erthalion6@gmail.com> Cc: Fangrui Song Cc: German Gomez Cc: Ingo Molnar Cc: Ivan Babrou Cc: James Clark Cc: Jing Zhang Cc: Jiri Olsa Cc: John Garry Cc: K Prateek Nayak Cc: Kan Liang Cc: Leo Yan Cc: Liam Howlett Cc: Mark Rutland Cc: Miguel Ojeda Cc: Mike Leach Cc: Namhyung Kim Cc: Naveen N. Rao Cc: Peter Zijlstra Cc: Ravi Bangoria Cc: Sean Christopherson Cc: Steinar H. Gunderson Cc: Suzuki Poulouse Cc: Wenyu Liu Cc: Will Deacon Cc: Yang Jihong Cc: Ye Xingchen Cc: Yuan Can Cc: coresight@lists.linaro.org Cc: linux-arm-kernel@lists.infradead.org Link: https://lore.kernel.org/r/20230608232823.4027869-4-irogers@google.com Signed-off-by: Arnaldo Carvalho de Melo

perf script: Refine printing of dso offset (dsoff)

2023-05-12T18:21:49+00:00

Print dso offset only for object files, and in those cases force using the dso->long_name if the dso->name starts with '[' or the dso is kcore, in order to avoid special names such as [vdso], or mixing up kcore with vmlinux. Signed-off-by: Adrian Hunter Cc: Changbin Du Cc: Ian Rogers Cc: Jiri Olsa Cc: Namhyung Kim Link: https://lore.kernel.org/r/20230424055107.12105-3-adrian.hunter@intel.com Signed-off-by: Arnaldo Carvalho de Melo

perf map: Add helper map__fprintf_dsoname_dsoff

2023-05-12T18:21:48+00:00

This adds a helper function map__fprintf_dsoname_dsoff() to print dsoname with optional dso offset. Suggested-by: Adrian Hunter Signed-off-by: Changbin Du Acked-by: Adrian Hunter Cc: Alexander Shishkin Cc: Hui Wang Cc: Ian Rogers Cc: Ingo Molnar Cc: Jiri Olsa Cc: Mark Rutland Cc: Namhyung Kim Cc: Peter Zijlstra Link: https://lore.kernel.org/r/20230418031825.1262579-3-changbin.du@huawei.com Signed-off-by: Arnaldo Carvalho de Melo