Skip to contentSkip to conversation

maps memory improvements and fixes

PATCH Applied Ian Rogers 2 participants 12 messages Feb 10, 2024 – Feb 13, 2024

Subsystems (2)
lore
Share & tools
lore

Ian Rogers

author reviewer
#0 lore raw

v3 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
author reviewer
#1 lore raw

PATCH 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
index bb3fbfe5a73e..b15417a0d617 100644
@@ -156,6 +156,9 @@ static int test__maps__merge_in(struct test_suite *t __maybe_unused, int subtest
 	TEST_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
index 7a785a47467e..14a5ea70d81e 100644
@@ -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
maintainer
#2 lore raw

Re: [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_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.

---

[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;
 }
author reviewer
#3 lore raw

Re: [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_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.

---

[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,
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;
 }
maintainer
#4 lore raw

Re: [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_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.

---

[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_address by 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;
 }
author reviewer
#5 lore raw

Re: [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_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.

---

[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_address by 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,
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;
 }
author reviewer
#6 lore raw

PATCH v3 2/6 perf maps: Get map before returning in maps__find

In reply to Ian Rogers

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.

---
 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
index 5bfec3345d59..c05c0a85dad4 100644
@@ -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
index 822f893e67d5..e808e6fc8f76 100644
@@ -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
index 3573e0b7ef3e..83709146a48a 100644
@@ -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
index 68f45e9e63b6..198903157f9e 100644
@@ -511,7 +511,7 @@ size_t perf_event__fprintf_text_poke(union perf_event *event, struct machine *ma
 		struct 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
index b397a769006f..e8eb9f0b073f 100644
@@ -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
index 13dec408b931..2547c9074b3a 100644
@@ -506,15 +506,18 @@ void maps__remove_maps(struct maps *maps, bool (*cb)(struct map *map, void *data
 struct 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
index be212ba157dc..1710b89e207c 100644
@@ -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
author reviewer
#7 lore raw

PATCH v3 3/6 perf maps: Get map before returning in maps__find_by_name

In reply to Ian Rogers

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.

---
 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
index e808e6fc8f76..fecbf851bb2e 100644
@@ -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
index e8eb9f0b073f..7031f6fddcae 100644
@@ -1537,8 +1537,10 @@ static int maps__set_module_path(struct maps *maps, const char *path, struct kmo
 		return 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
index 2547c9074b3a..ea8fa684e8c6 100644
@@ -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
index a1a796043691..be71abe8b9b0 100644
@@ -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
index 95773c32796d..0b91f813c4fa 100644
@@ -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
index 1710b89e207c..0785a54e832e 100644
@@ -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
author reviewer
#8 lore raw

PATCH v3 4/6 perf maps: Get map before returning in maps__find_next_entry

In reply to Ian Rogers

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.

---
 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
index 7031f6fddcae..4911734411b5 100644
@@ -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
index ea8fa684e8c6..df0c8041899e 100644
@@ -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
author reviewer
#9 lore raw

PATCH v3 5/6 perf maps: Hide maps internals

In reply to Ian Rogers

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.

---
 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
index 7fa6f7c568e2..e9ecd30a5c05 100644
@@ -46,9 +46,9 @@ static int test__thread_maps_share(struct test_suite *test __maybe_unused, int s
 	TEST_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
index 8262f69118db..7517d16c02ec 100644
@@ -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
index 0785a54e832e..35975189999b 100644
@@ -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
index 89c47a5098e2..c59ab4d79163 100644
@@ -383,7 +383,7 @@ static int thread__clone_maps(struct thread *thread, struct thread *parent, bool
 	if (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
index 6013335a8dae..b38d322734b4 100644
@@ -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
index dac536e28360..6a5ac0faa6f4 100644
@@ -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
index 76cd63de80a8..2728eb4f13ea 100644
@@ -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 *initialized
 		return 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
author reviewer
#10 lore raw

PATCH v3 6/6 perf maps: Locking tidy up of nr_maps

In reply to Ian Rogers

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.

---
 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
index 4911734411b5..3da92f18814a 100644
@@ -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
index 439cefab112a..53aea6d2ef93 100644
@@ -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
index 4bcba136ffe5..d9aa62ed968a 100644
@@ -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
maintainer Applied
#11 lore raw
In reply to Ian Rogers
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 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

Quoted 1 line

[...]

Applied to perf-tools-next, thanks!

Best regards,

Signature · 1 line
Namhyung Kim <[email protected]>