maps memory improvements and fixes
Subsystems (2)
Ian Rogers
reviewerv3 cover maps memory improvements and fixes
First 6 patches from:
https://lore.kernel.org/lkml/[email protected]/
v3. Fix latent concurrent modification bug in maps__for_each_map. v2. Fix NO_LIBUNWIND=1 build issue.
Ian Rogers (6):
perf maps: Switch from rbtree to lazily sorted array for addresses perf maps: Get map before returning in maps__find
perf maps: Get map before returning in maps__find_by_name perf maps: Get map before returning in maps__find_next_entry perf maps: Hide maps internals
perf maps: Locking tidy up of nr_maps
tools/perf/arch/x86/tests/dwarf-unwind.c | 1 + tools/perf/tests/maps.c | 3 + tools/perf/tests/thread-maps-share.c | 8 +- tools/perf/tests/vmlinux-kallsyms.c | 10 +- tools/perf/util/bpf-event.c | 1 + tools/perf/util/callchain.c | 2 +- tools/perf/util/event.c | 4 +- tools/perf/util/machine.c | 34 +- tools/perf/util/map.c | 1 + tools/perf/util/maps.c | 1302 ++++++++++++++-------- tools/perf/util/maps.h | 65 +- tools/perf/util/probe-event.c | 1 + tools/perf/util/symbol-elf.c | 4 +- tools/perf/util/symbol.c | 31 +- tools/perf/util/thread.c | 2 +- tools/perf/util/unwind-libdw.c | 2 +- tools/perf/util/unwind-libunwind-local.c | 2 +- tools/perf/util/unwind-libunwind.c | 7 +- 18 files changed, 906 insertions(+), 574 deletions(-)
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Ian Rogers
reviewerPATCH v3 1/6 perf maps: Switch from rbtree to lazily sorted array for addresses
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.
--- tools/perf/tests/maps.c | 3 + tools/perf/util/map.c | 1 + tools/perf/util/maps.c | 1203 ++++++++++++++++++++++++--------------- tools/perf/util/maps.h | 54 +- 4 files changed, 777 insertions(+), 484 deletions(-)
tools/perf/tests/maps.c +3 -0
@@ -156,6 +156,9 @@ static int test__maps__merge_in(struct test_suite *t __maybe_unused, int subtestTEST_ASSERT_VAL ("merge check failed" , !ret);maps__zput (maps); +map__zput (map_kcore1); +map__zput (map_kcore2); +map__zput (map_kcore3);return TEST_OK ; }
tools/perf/util/map.c +1 -0
@@ -168,6 +168,7 @@ struct map *map__new(struct machine *machine, u64 start, u64 len,if (dso ==NULL ) goto out_delete; +assert (!dso->kernel);map__init (result, start, start + len, pgoff, dso);if (anon || no_dso) {
tools/perf/util/maps.c +729 -474
1,467 lines not on this page · raw message
tools/perf/util/maps.h +44 -10
79 lines not on this page · raw message
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Namhyung Kim
maintainerRe: [PATCH v3 1/6] perf maps: Switch from rbtree to lazily sorted array for addresses
Quoted 42 lines · Ian Rogers
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_inis rewritten in terms ofmaps__fixup_overlap_and_insert.maps_merge_insplits the given mapping inserting remaining gaps.maps__fixup_overlap_and_insertsplits 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 <[email protected]>Acked-by Namhyung Kim <[email protected]>---
[SNIP]
Quoted 15 lines
int
maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data){tools/perf/util/maps.c +5
-6-struct map_rb_node *pos; +bool done = false;int ret =0 ; -down_read (maps__lock (maps)); -maps__for_each_entry (maps, pos) { - ret =cb (pos->map, data); -if (ret) -break ; +/* See locking/sorting note. */ +while (!done) { +down_read (maps__lock (maps)); +if (maps__maps_by_address_sorted (maps)) {
tools/perf/util/maps.c line 474
Quoted 10 lines
tools/perf/util/maps.c +10
-0+/* +* maps__for_each_map callbacks may buggily/unsafely +* insert into maps_by_address. Deliberately reload +* maps__nr_maps and maps_by_address on each iteration +* to avoid using memory freed by maps__insert growing +* the array - this may cause maps to be skipped or +* repeated. +*/ +for (unsigned int i =0 ; i <maps__nr_maps (maps); i++) { +struct map **maps_by_address =maps__maps_by_address (maps);
Any chance they can move out of the loop? I guess not as they are not marked to const/pure functions..
Thanks,
Namhyung
Quoted 15 lines
tools/perf/util/maps.c +11
-1+struct map *map = maps_by_address[i]; + + ret =cb (map, data); +if (ret) +break ; + } + done = true; + } +up_read (maps__lock (maps)); +if (!done) +maps__sort_by_address (maps); } -up_read (maps__lock (maps));return ret; }
Ian Rogers
reviewerRe: [PATCH v3 1/6] perf maps: Switch from rbtree to lazily sorted array for addresses
Quoted 71 lines · Namhyung Kim
Quoted 42 lines · Ian Rogers
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_inis rewritten in terms ofmaps__fixup_overlap_and_insert.maps_merge_insplits the given mapping inserting remaining gaps.maps__fixup_overlap_and_insertsplits 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 <[email protected]>Acked-by Namhyung Kim <[email protected]>---
[SNIP]
Quoted 15 lines
int
maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data){tools/perf/util/maps.c +5
-6-struct map_rb_node *pos; +bool done = false;int ret =0 ; -down_read (maps__lock (maps)); -maps__for_each_entry (maps, pos) { - ret =cb (pos->map, data); -if (ret) -break ; +/* See locking/sorting note. */ +while (!done) { +down_read (maps__lock (maps)); +if (maps__maps_by_address_sorted (maps)) {tools/perf/util/maps.c line 474
Quoted 10 lines
tools/perf/util/maps.c +10
-0+/* +* maps__for_each_map callbacks may buggily/unsafely +* insert into maps_by_address. Deliberately reload +* maps__nr_maps and maps_by_address on each iteration +* to avoid using memory freed by maps__insert growing +* the array - this may cause maps to be skipped or +* repeated. +*/ +for (unsigned int i =0 ; i <maps__nr_maps (maps); i++) { +struct map **maps_by_address =maps__maps_by_address (maps);
Quoted 2 lines
Any chance they can move out of the loop? I guess not as they are not marked to const/pure functions..
It's not because the cb(...) call below will potentially modify maps_by_address by inserting maps and reallocating the array. Having it outside the loop was what caused the original bug.
Thanks,
Ian
Quoted 19 lines
Thanks,
NamhyungQuoted 15 lines
tools/perf/util/maps.c +11
-1+struct map *map = maps_by_address[i]; + + ret =cb (map, data); +if (ret) +break ; + } + done = true; + } +up_read (maps__lock (maps)); +if (!done) +maps__sort_by_address (maps); } -up_read (maps__lock (maps));return ret; }
Namhyung Kim
maintainerRe: [PATCH v3 1/6] perf maps: Switch from rbtree to lazily sorted array for addresses
Quoted 73 lines · Ian Rogers
Quoted 71 lines · Namhyung Kim
Quoted 42 lines · Ian Rogers
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_inis rewritten in terms ofmaps__fixup_overlap_and_insert.maps_merge_insplits the given mapping inserting remaining gaps.maps__fixup_overlap_and_insertsplits 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 <[email protected]>Acked-by Namhyung Kim <[email protected]>---
[SNIP]
Quoted 25 lines
int
maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data){tools/perf/util/maps.c +15
-6-struct map_rb_node *pos; +bool done = false;int ret =0 ; -down_read (maps__lock (maps)); -maps__for_each_entry (maps, pos) { - ret =cb (pos->map, data); -if (ret) -break ; +/* See locking/sorting note. */ +while (!done) { +down_read (maps__lock (maps)); +if (maps__maps_by_address_sorted (maps)) { +/* +* maps__for_each_map callbacks may buggily/unsafely +* insert into maps_by_address. Deliberately reload +* maps__nr_maps and maps_by_address on each iteration +* to avoid using memory freed by maps__insert growing +* the array - this may cause maps to be skipped or +* repeated. +*/ +for (unsigned int i =0 ; i <maps__nr_maps (maps); i++) { +struct map **maps_by_address =maps__maps_by_address (maps);
Quoted 6 lines
Quoted 2 lines
Any chance they can move out of the loop? I guess not as they are not marked to const/pure functions..
It's not because the cb(...) call below will potentially modify
maps_by_addressby inserting maps and reallocating the array. Having it outside the loop was what caused the original bug.
Oh, I meant if compiler can move them automatically.
Thanks,
Namhyung
Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
tools/perf/util/maps.c +11
-1+struct map *map = maps_by_address[i]; + + ret =cb (map, data); +if (ret) +break ; + } + done = true; + } +up_read (maps__lock (maps)); +if (!done) +maps__sort_by_address (maps); } -up_read (maps__lock (maps));return ret; }
Ian Rogers
reviewerRe: [PATCH v3 1/6] perf maps: Switch from rbtree to lazily sorted array for addresses
Quoted 75 lines · Namhyung Kim
Quoted 73 lines · Ian Rogers
Quoted 71 lines · Namhyung Kim
Quoted 42 lines · Ian Rogers
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_inis rewritten in terms ofmaps__fixup_overlap_and_insert.maps_merge_insplits the given mapping inserting remaining gaps.maps__fixup_overlap_and_insertsplits 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 <[email protected]>Acked-by Namhyung Kim <[email protected]>---
[SNIP]
Quoted 25 lines
int
maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data), void *data){tools/perf/util/maps.c +15
-6-struct map_rb_node *pos; +bool done = false;int ret =0 ; -down_read (maps__lock (maps)); -maps__for_each_entry (maps, pos) { - ret =cb (pos->map, data); -if (ret) -break ; +/* See locking/sorting note. */ +while (!done) { +down_read (maps__lock (maps)); +if (maps__maps_by_address_sorted (maps)) { +/* +* maps__for_each_map callbacks may buggily/unsafely +* insert into maps_by_address. Deliberately reload +* maps__nr_maps and maps_by_address on each iteration +* to avoid using memory freed by maps__insert growing +* the array - this may cause maps to be skipped or +* repeated. +*/ +for (unsigned int i =0 ; i <maps__nr_maps (maps); i++) { +struct map **maps_by_address =maps__maps_by_address (maps);
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
Any chance they can move out of the loop? I guess not as they are not marked to const/pure functions..
It's not because the cb(...) call below will potentially modify
maps_by_addressby inserting maps and reallocating the array. Having it outside the loop was what caused the original bug.Oh, I meant if compiler can move them automatically.
The const (on the accessor) isn't sufficient for that, they'd perhaps need to be restrict. maps here is neither const or restrict which means the callback can modify it (even though it isn't an argument) and the function here needs to reload its value.
Thanks,
Ian
Quoted 20 lines
Thanks,
NamhyungQuoted 17 lines
Quoted 17 lines
Quoted 17 lines
tools/perf/util/maps.c +11
-1+struct map *map = maps_by_address[i]; + + ret =cb (map, data); +if (ret) +break ; + } + done = true; + } +up_read (maps__lock (maps)); +if (!done) +maps__sort_by_address (maps); } -up_read (maps__lock (maps));return ret; }
Ian Rogers
reviewerPATCH v3 2/6 perf maps: Get map before returning in maps__find
In reply to Ian RogersFinding 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.
--- tools/perf/arch/x86/tests/dwarf-unwind.c | 1 + tools/perf/tests/vmlinux-kallsyms.c | 5 ++--- tools/perf/util/bpf-event.c | 1 + tools/perf/util/event.c | 4 ++-- tools/perf/util/machine.c | 22 ++++++++-------------- tools/perf/util/maps.c | 17 ++++++++++------- tools/perf/util/symbol.c | 3 ++- 7 files changed, 26 insertions(+), 27 deletions(-)
tools/perf/arch/x86/tests/dwarf-unwind.c +1 -0
@@ -34,6 +34,7 @@ static int sample_ustack(struct perf_sample *sample, } stack_size =map__end (map) - sp; +map__put (map); stack_size = stack_size >STACK_SIZE ?STACK_SIZE : stack_size;memcpy (buf, (void *) sp, stack_size);
tools/perf/tests/vmlinux-kallsyms.c +2 -3
@@ -151,10 +151,8 @@ static int test__vmlinux_matches_kallsyms_cb2(struct map *map, void *data)u64 mem_end =map__unmap_ip (args->vmlinux_map,map__end (map)); pair =maps__find (args->kallsyms.kmaps, mem_start); -if (pair ==NULL ||map__priv (pair)) -return 0 ; -if (map__start (pair) == mem_start) { +if (pair !=NULL && !map__priv (pair) &&map__start (pair) == mem_start) {struct dso *dso =map__dso (map);if (!args->header_printed) {
@@ -170,6 +168,7 @@ static int test__vmlinux_matches_kallsyms_cb2(struct map *map, void *data)pr_info (" %s\n" , dso->name);map__set_priv (pair,1 ); } +map__put (pair);return 0 ; }
tools/perf/util/bpf-event.c +1 -0
@@ -63,6 +63,7 @@ static int machine__process_bpf_event_load(struct machine *machine, dso->bpf_prog.id = id; dso->bpf_prog.sub_id = i; dso->bpf_prog.env = env; +map__put (map); } }return 0 ;
tools/perf/util/event.c +2 -2
@@ -511,7 +511,7 @@ size_t perf_event__fprintf_text_poke(union perf_event *event, struct machine *mastruct addr_location al;addr_location__init (&al); - al.map =map__get (maps__find (machine__kernel_maps (machine), tp->addr)); + al.map =maps__find (machine__kernel_maps (machine), tp->addr);if (al.map &&map__load (al.map) >=0 ) { al.addr =map__map_ip (al.map, tp->addr); al.sym =map__find_symbol (al.map, al.addr);
@@ -641,7 +641,7 @@ struct map *thread__find_map(struct thread *thread, u8 cpumode, u64 addr,return NULL ; } al->maps =maps__get (maps); - al->map =map__get (maps__find (maps, al->addr)); + al->map =maps__find (maps, al->addr);if (al->map !=NULL ) {/* * Kernel maps might be changed when loading symbols so loading
tools/perf/util/machine.c +8 -14
@@ -896,7 +896,6 @@ static int machine__process_ksymbol_register(struct machine *machine,struct symbol *sym;struct dso *dso;struct map *map =maps__find (machine__kernel_maps (machine), event->ksymbol.addr); -bool put_map = false;int err =0 ;if (!map) {
@@ -913,12 +912,6 @@ static int machine__process_ksymbol_register(struct machine *machine, err = -ENOMEM ; goto out; } -/* -* The inserted map has a get on it, we need to put to release -* the reference count here, but do it after all accesses are -* done. -*/ - put_map = true;if (event->ksymbol.ksym_type ==PERF_RECORD_KSYMBOL_TYPE_OOL ) { dso->binary_type =DSO_BINARY_TYPE__OOL ; dso->data.file_size = event->ksymbol.len;
@@ -952,8 +945,7 @@ static int machine__process_ksymbol_register(struct machine *machine, }dso__insert_symbol (dso, sym); out: -if (put_map) -map__put (map); +map__put (map);return err; }
@@ -977,7 +969,7 @@ static int machine__process_ksymbol_unregister(struct machine *machine,if (sym)dso__delete_symbol (dso, sym); } - +map__put (map);return 0 ; }
@@ -1005,11 +997,11 @@ int machine__process_text_poke(struct machine *machine, union perf_event *event,perf_event__fprintf_text_poke (event, machine, stdout);if (!event->text_poke.new_len) -return 0 ; + goto out;if (cpumode !=PERF_RECORD_MISC_KERNEL ) {pr_debug ("%s: unsupported cpumode - ignoring\n" , __func__); -return 0 ; + goto out; }if (dso) {
@@ -1032,7 +1024,8 @@ int machine__process_text_poke(struct machine *machine, union perf_event *event,pr_debug ("Failed to find kernel text poke address map for %#" PRI_lx64"\n" , event->text_poke.addr); } - +out: +map__put (map);return 0 ; }
@@ -1300,9 +1293,10 @@ static int machine__map_x86_64_entry_trampolines_cb(struct map *map, void *data)return 0 ; dest_map =maps__find (args->kmaps,map__pgoff (map)); -if (dest_map != map) +if (RC_CHK_ACCESS (dest_map) !=RC_CHK_ACCESS (map))map__set_pgoff (map,map__map_ip (dest_map,map__pgoff (map))); +map__put (dest_map); args->found = true;return 0 ; }
tools/perf/util/maps.c +10 -7
@@ -506,15 +506,18 @@ void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *datastruct symbol *maps__find_symbol (struct maps *maps,u64 addr,struct map **mapp) {struct map *map =maps__find (maps, addr); +struct symbol *result =NULL ;/* Ensure map is loaded before using map->map_ip */ if (map !=NULL &&map__load (map) >=0 ) { -if (mapp !=NULL ) - *mapp = map;// TODO: map_put on else path when find returns a get. -return map__find_symbol (map,map__map_ip (map, addr)); - } +if (mapp) + *mapp = map; -return NULL ; + result =map__find_symbol (map,map__map_ip (map, addr)); +if (!mapp) +map__put (map); + } +return result; }struct maps__find_symbol_by_name_args {
@@ -558,7 +561,7 @@ int maps__find_ams(struct maps *maps, struct addr_map_symbol *ams)if (ams->addr <map__start (ams->ms.map) || ams->addr >=map__end (ams->ms.map)) {if (maps ==NULL )return -1 ; - ams->ms.map =maps__find (maps, ams->addr);// TODO: map_get + ams->ms.map =maps__find (maps, ams->addr);if (ams->ms.map ==NULL )return -1 ; }
@@ -868,7 +871,7 @@ struct map *maps__find(struct maps *maps, u64 ip) sizeof(*mapp), map__addr_cmp);if (mapp) - result = *mapp;// map__get(*mapp); + result =map__get (*mapp); done = true; }up_read (maps__lock (maps));
tools/perf/util/symbol.c +2 -1
@@ -757,7 +757,6 @@ static int dso__load_all_kallsyms(struct dso *dso, const char *filename)static int maps__split_kallsyms_for_kcore (struct maps *kmaps,struct dso *dso) { -struct map *curr_map;struct symbol *pos;int count =0 ;struct rb_root_cached old_root = dso->symbols;
@@ -770,6 +769,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso) *root =RB_ROOT_CACHED ;while (next) { +struct map *curr_map;struct dso *curr_map_dso;char *module;
@@ -796,6 +796,7 @@ static int maps__split_kallsyms_for_kcore(struct maps *kmaps, struct dso *dso) pos->end -=map__start (curr_map) -map__pgoff (curr_map);symbols__insert (&curr_map_dso->symbols, pos); ++count; +map__put (curr_map); }/* Symbols have been adjusted */
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Ian Rogers
reviewerPATCH v3 3/6 perf maps: Get map before returning in maps__find_by_name
In reply to Ian RogersFinding 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.
--- tools/perf/tests/vmlinux-kallsyms.c | 5 +++-- tools/perf/util/machine.c | 6 ++++-- tools/perf/util/maps.c | 6 +++--- tools/perf/util/probe-event.c | 1 + tools/perf/util/symbol-elf.c | 4 +++- tools/perf/util/symbol.c | 18 +++++++++++------- 6 files changed, 25 insertions(+), 15 deletions(-)
tools/perf/tests/vmlinux-kallsyms.c +3 -2
@@ -131,9 +131,10 @@ static int test__vmlinux_matches_kallsyms_cb1(struct map *map, void *data)struct map *pair =maps__find_by_name (args->kallsyms.kmaps, (dso->kernel ? dso->short_name : dso->name)); -if (pair) +if (pair) {map__set_priv (pair,1 ); -else { +map__put (pair); + }else {if (!args->header_printed) {pr_info ("WARN: Maps only in vmlinux:\n" ); args->header_printed = true;
tools/perf/util/machine.c +4 -2
@@ -1537,8 +1537,10 @@ static int maps__set_module_path(struct maps *maps, const char *path, struct kmoreturn 0 ; long_name =strdup (path); -if (long_name ==NULL ) +if (long_name ==NULL ) { +map__put (map);return -ENOMEM ; + } dso =map__dso (map);dso__set_long_name (dso, long_name, true);
@@ -1552,7 +1554,7 @@ static int maps__set_module_path(struct maps *maps, const char *path, struct kmo dso->symtab_type++; dso->comp = m->comp; } - +map__put (map);return 0 ; }
tools/perf/util/maps.c +3 -3
@@ -905,7 +905,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name)struct dso *dso =map__dso (maps__maps_by_name (maps)[i]);if (dso &&strcmp (dso->short_name, name) ==0 ) { - result =maps__maps_by_name (maps)[i];// TODO: map__get + result =map__get (maps__maps_by_name (maps)[i]); done = true; } }
@@ -917,7 +917,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name) sizeof(*mapp), map__strcmp_name);if (mapp) { - result = *mapp;// TODO: map__get + result =map__get (*mapp); i = mapp -maps__maps_by_name (maps);RC_CHK_ACCESS (maps)->last_search_by_name_idx = i; }
@@ -942,7 +942,7 @@ struct map *maps__find_by_name(struct maps *maps, const char *name)struct dso *dso =map__dso (pos);if (dso &&strcmp (dso->short_name, name) ==0 ) { - result = pos;// TODO: map__get + result =map__get (pos);break ; } }
tools/perf/util/probe-event.c +1 -0
@@ -358,6 +358,7 @@ static int kernel_get_module_dso(const char *module, struct dso **pdso) map =maps__find_by_name (machine__kernel_maps (host_machine), module_name);if (map) { dso =map__dso (map); +map__put (map); goto found; }pr_debug ("Failed to find module %s.\n" , module);
tools/perf/util/symbol-elf.c +3 -1
@@ -1535,8 +1535,10 @@ static int dso__process_kernel_symbol(struct dso *dso, struct map *map,dso__set_loaded (curr_dso); *curr_mapp = curr_map; *curr_dsop = curr_dso; - }else + }else { *curr_dsop =map__dso (curr_map); +map__put (curr_map); + }return 0 ; }
tools/perf/util/symbol.c +11 -7
@@ -814,7 +814,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, struct map *initial_map) {struct machine *machine; -struct map *curr_map = initial_map; +struct map *curr_map =map__get (initial_map);struct symbol *pos;int count =0 , moved =0 ;struct rb_root_cached *root = &dso->symbols;
@@ -858,13 +858,14 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,dso__set_loaded (curr_map_dso); } +map__zput (curr_map); curr_map =maps__find_by_name (kmaps, module);if (curr_map ==NULL ) {pr_debug ("%s/proc/{kallsyms,modules} " "inconsistency while looking " "for \"%s\" module!\n" , machine->root_dir, module); - curr_map = initial_map; + curr_map =map__get (initial_map); goto discard_symbol; } curr_map_dso =map__dso (curr_map);
@@ -888,7 +889,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,* symbols at this point. */ goto discard_symbol; - }else if (curr_map != initial_map) { + }else if (!RC_CHK_EQUAL (curr_map, initial_map)) {char dso_name[PATH_MAX ];struct dso *ndso;
@@ -899,7 +900,8 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, }if (count ==0 ) { - curr_map = initial_map; +map__zput (curr_map); + curr_map =map__get (initial_map); goto add_symbol; }
@@ -913,6 +915,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, kernel_range++); ndso =dso__new (dso_name); +map__zput (curr_map);if (ndso ==NULL )return -1 ;
@@ -926,6 +929,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,map__set_mapping_type (curr_map,MAPPING_TYPE__IDENTITY );if (maps__insert (kmaps, curr_map)) { +map__zput (curr_map);dso__put (ndso);return -1 ; }
@@ -936,7 +940,7 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta, pos->end -= delta; } add_symbol: -if (curr_map != initial_map) { +if (!RC_CHK_EQUAL (curr_map, initial_map)) {struct dso *curr_map_dso =map__dso (curr_map);rb_erase_cached (&pos->rb_node, root);
@@ -951,12 +955,12 @@ static int maps__split_kallsyms(struct maps *kmaps, struct dso *dso, u64 delta,symbol__delete (pos); } -if (curr_map != initial_map && +if (!RC_CHK_EQUAL (curr_map, initial_map) && dso->kernel ==DSO_SPACE__KERNEL_GUEST &&machine__is_default_guest (maps__machine (kmaps))) {dso__set_loaded (map__dso (curr_map)); } - +map__put (curr_map);return count + moved; }
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Ian Rogers
reviewerPATCH v3 4/6 perf maps: Get map before returning in maps__find_next_entry
In reply to Ian RogersFinding 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.
--- tools/perf/util/machine.c | 4 +++- tools/perf/util/maps.c | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-)
tools/perf/util/machine.c +3 -1
@@ -1761,8 +1761,10 @@ int machine__create_kernel_maps(struct machine *machine)struct map *next =maps__find_next_entry (machine__kernel_maps (machine),machine__kernel_map (machine)); -if (next) +if (next) {machine__set_kernel_mmap (machine, start,map__start (next)); +map__put (next); + } } out_put:
tools/perf/util/maps.c +1 -1
@@ -962,7 +962,7 @@ struct map *maps__find_next_entry(struct maps *maps, struct map *map)down_read (maps__lock (maps)); i =maps__by_address_index (maps, map);if (i <maps__nr_maps (maps)) - result =maps__maps_by_address (maps)[i];// TODO: map__get + result =map__get (maps__maps_by_address (maps)[i]);up_read (maps__lock (maps));return result;
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Ian Rogers
reviewerPATCH v3 5/6 perf maps: Hide maps internals
In reply to Ian RogersMove 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.
--- tools/perf/tests/thread-maps-share.c | 8 +- tools/perf/util/callchain.c | 2 +- tools/perf/util/maps.c | 96 +++++++++++++++++++++++ tools/perf/util/maps.h | 97 +++--------------------- tools/perf/util/symbol.c | 10 +++ tools/perf/util/thread.c | 2 +- tools/perf/util/unwind-libdw.c | 2 +- tools/perf/util/unwind-libunwind-local.c | 2 +- tools/perf/util/unwind-libunwind.c | 7 +- 9 files changed, 124 insertions(+), 102 deletions(-)
tools/perf/tests/thread-maps-share.c +4 -4
@@ -46,9 +46,9 @@ static int test__thread_maps_share(struct test_suite *test __maybe_unused, int sTEST_ASSERT_EQUAL ("wrong refcnt" ,refcount_read (maps__refcnt (maps)),4 );/* test the maps pointer is shared */ -TEST_ASSERT_VAL ("maps don't match" ,RC_CHK_EQUAL (maps,thread__maps (t1))); -TEST_ASSERT_VAL ("maps don't match" ,RC_CHK_EQUAL (maps,thread__maps (t2))); -TEST_ASSERT_VAL ("maps don't match" ,RC_CHK_EQUAL (maps,thread__maps (t3))); +TEST_ASSERT_VAL ("maps don't match" ,maps__equal (maps,thread__maps (t1))); +TEST_ASSERT_VAL ("maps don't match" ,maps__equal (maps,thread__maps (t2))); +TEST_ASSERT_VAL ("maps don't match" ,maps__equal (maps,thread__maps (t3)));/* * Verify the other leader was created by previous call.
@@ -73,7 +73,7 @@ static int test__thread_maps_share(struct test_suite *test __maybe_unused, int s other_maps =thread__maps (other);TEST_ASSERT_EQUAL ("wrong refcnt" ,refcount_read (maps__refcnt (other_maps)),2 ); -TEST_ASSERT_VAL ("maps don't match" ,RC_CHK_EQUAL (other_maps,thread__maps (other_leader))); +TEST_ASSERT_VAL ("maps don't match" ,maps__equal (other_maps,thread__maps (other_leader)));/* release thread group */ thread__put (t3);
tools/perf/util/callchain.c +1 -1
@@ -1157,7 +1157,7 @@ int fill_callchain_info(struct addr_location *al, struct callchain_cursor_node *if (al->map ==NULL ) goto out; } -if (RC_CHK_EQUAL (al->maps,machine__kernel_maps (machine))) { +if (maps__equal (al->maps,machine__kernel_maps (machine))) {if (machine__is_host (machine)) { al->cpumode =PERF_RECORD_MISC_KERNEL ; al->level ='k' ;
tools/perf/util/maps.c +96 -0
117 lines not on this page · raw message
tools/perf/util/maps.h +9 -88
125 lines not on this page · raw message
tools/perf/util/symbol.c +10 -0
@@ -63,6 +63,16 @@ struct symbol_conf symbol_conf = { .res_sample = 0, }; +struct map_list_node { +struct list_head node; +struct map *map; +}; + +static struct map_list_node *map_list_node__new (void ) +{ +return malloc (sizeof (struct map_list_node )); +} +static enum dso_binary_type binary_type_symtab[] = {DSO_BINARY_TYPE__KALLSYMS ,DSO_BINARY_TYPE__GUEST_KALLSYMS ,
tools/perf/util/thread.c +1 -1
@@ -383,7 +383,7 @@ static int thread__clone_maps(struct thread *thread, struct thread *parent, boolif (thread__pid (thread) ==thread__pid (parent))return thread__prepare_access (thread); -if (RC_CHK_EQUAL (thread__maps (thread),thread__maps (parent))) { +if (maps__equal (thread__maps (thread),thread__maps (parent))) {pr_debug ("broken map groups on thread %d/%d parent %d/%d\n" ,thread__pid (thread),thread__tid (thread),thread__pid (parent),thread__tid (parent));
tools/perf/util/unwind-libdw.c +1 -1
@@ -263,7 +263,7 @@ int unwind__get_entries(unwind_entry_cb_t cb, void *arg,struct unwind_info *ui, ui_buf = { .sample = data, .thread = thread, - .machine =RC_CHK_ACCESS (thread__maps (thread))->machine, + .machine =maps__machine ((thread__maps (thread))), .cb = cb, .arg = arg, .max_stack = max_stack,
tools/perf/util/unwind-libunwind-local.c +1 -1
@@ -706,7 +706,7 @@ static int _unwind__prepare_access(struct maps *maps) {void *addr_space =unw_create_addr_space (&accessors,0 ); -RC_CHK_ACCESS (maps)->addr_space = addr_space; +maps__set_addr_space (maps, addr_space);if (!addr_space) {pr_err ("unwind: Can't create unwind address space.\n" );return -ENOMEM ;
tools/perf/util/unwind-libunwind.c +1 -6
@@ -12,11 +12,6 @@ struct unwind_libunwind_ops __weak *local_unwind_libunwind_ops;struct unwind_libunwind_ops __weak *x86_32_unwind_libunwind_ops;struct unwind_libunwind_ops __weak *arm64_unwind_libunwind_ops; -static void unwind__register_ops (struct maps *maps,struct unwind_libunwind_ops *ops) -{ -RC_CHK_ACCESS (maps)->unwind_libunwind_ops = ops; -} -int unwind__prepare_access (struct maps *maps,struct map *map,bool *initialized) {const char *arch;
@@ -60,7 +55,7 @@ int unwind__prepare_access(struct maps *maps, struct map *map, bool *initializedreturn 0 ; } out_register: -unwind__register_ops (maps, ops); +maps__set_unwind_libunwind_ops (maps, ops); err =maps__unwind_libunwind_ops (maps)->prepare_access (maps);if (initialized)
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Ian Rogers
reviewerPATCH v3 6/6 perf maps: Locking tidy up of nr_maps
In reply to Ian RogersAfter this change maps__nr_maps is only used by tests, existing users are migrated to maps__empty. Compute maps__empty under the read lock.
--- tools/perf/util/machine.c | 2 +- tools/perf/util/maps.c | 10 ++++++++-- tools/perf/util/maps.h | 4 ++-- 3 files changed, 11 insertions(+), 5 deletions(-)
tools/perf/util/machine.c +1 -1
@@ -440,7 +440,7 @@ static struct thread *findnew_guest_code(struct machine *machine,return NULL ;/* Assume maps are set up if there are any */ -if (maps__nr_maps (thread__maps (thread))) +if (!maps__empty (thread__maps (thread)))return thread; host_thread =machine__find_thread (host_machine,-1 , pid);
tools/perf/util/maps.c +8 -2
@@ -541,7 +541,13 @@ void maps__remove(struct maps *maps, struct map *map)bool maps__empty (struct maps *maps) { -return maps__nr_maps (maps) ==0 ; +bool res; + +down_read (maps__lock (maps)); + res =maps__nr_maps (maps) ==0 ; +up_read (maps__lock (maps)); + +return res; }bool maps__equal (struct maps *a,struct maps *b)
@@ -871,7 +877,7 @@ int maps__copy_from(struct maps *dest, struct maps *parent) parent_maps_by_address =maps__maps_by_address (parent); n =maps__nr_maps (parent); -if (maps__empty (dest)) { +if (maps__nr_maps (dest) ==0 ) {/* No existing mappings so just copy from parent to avoid reallocs in insert. */ unsigned int nr_maps_allocated =RC_CHK_ACCESS (parent)->nr_maps_allocated; struct map **dest_maps_by_address =
tools/perf/util/maps.h +2 -2
@@ -43,8 +43,8 @@ int maps__for_each_map(struct maps *maps, int (*cb)(struct map *map, void *data)void maps__remove_maps (struct maps *maps,bool (*cb)(struct map *map,void *data),void *data);struct machine *maps__machine (const struct maps *maps); -unsigned int maps__nr_maps (const struct maps *maps); -refcount_t *maps__refcnt (struct maps *maps); +unsigned int maps__nr_maps (const struct maps *maps);/* Test only. */ +refcount_t *maps__refcnt (struct maps *maps);/* Test only. */ #ifdef HAVE_LIBUNWIND_SUPPORT void *maps__addr_space (const struct maps *maps);
Signature · 1 line
2.43.0.687.g38aa6559b0-goog
Quoted 14 lines · Ian Rogers
First 6 patches from:
https://lore.kernel.org/lkml/[email protected]/v3. Fix latent concurrent modification bug in
maps__for_each_map. v2. Fix NO_LIBUNWIND=1 build issue.Ian Rogers (6):
perf maps: Switch from rbtree to lazily sorted array for addresses perf maps: Get map before returning inmaps__find
perf maps: Get map before returning inmaps__find_by_nameperf maps: Get map before returning inmaps__find_next_entryperf maps: Hide maps internals
perf maps: Locking tidy up ofnr_maps
Quoted 1 line
[...]
Applied to perf-tools-next, thanks!
Best regards,
Signature · 1 line
Namhyung Kim <[email protected]>