[PATCH v3 1/3] perf maps: Sort kcore maps

[Leo Yan]

When merging kcore maps into the kernel maps, it has an implicit
requirement for the kcore maps ordering, otherwise, some sections
delivered by the kcore maps will be ignored.

Let's see below example:

  Ordering 1:
  Kcore maps       | Start address      | End address
  -----------------+--------------------+--------------------
  kcore_text       | 0xffff800080000000 | 0xffff8000822f0000
  vmalloc          | 0xffff800080000000 | 0xfffffdffbf800000

  Ordering 2:
  Kcore maps       | Start address      | End address
  -----------------+--------------------+--------------------
  vmalloc          | 0xffff800080000000 | 0xfffffdffbf800000
  kcore_text       | 0xffff800080000000 | 0xffff8000822f0000

The 'kcore_text' map is a subset of the 'vmalloc' map. When merging
these two maps into the kernal maps with the maps__merge_in() function,
the ordering 1 inserts the 'kcore_text' map prior to the 'vmalloc' map,
thus the 'kcore_text' map will be respected. On the other hand, if maps
are inserted with the ordering 2, the 'vmalloc' is inserted ahead, as a
result, its subset map will be ignored afterwards.

To merge the maps in a reliable way, this commit sorts the kcore maps
before merging them. Besides sorting the maps based on the end address,
it also gives the priority to a subset map to insert it before its
superset map in the list.

Signed-off-by: Leo Yan <leo.yan@xxxxxxx>
---
 tools/perf/util/symbol.c | 50 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 49 insertions(+), 1 deletion(-)

diff --git a/tools/perf/util/symbol.c b/tools/perf/util/symbol.c
index 9e5940b5bc59..c1513976ab6e 100644
--- a/tools/perf/util/symbol.c
+++ b/tools/perf/util/symbol.c
@@ -1256,6 +1256,7 @@ static int kcore_mapfn(u64 start, u64 len, u64 pgoff, void *data)
 {
 	struct kcore_mapfn_data *md = data;
 	struct map_list_node *list_node = map_list_node__new();
+	struct map_list_node *node;
 
 	if (!list_node)
 		return -ENOMEM;
@@ -1269,8 +1270,55 @@ static int kcore_mapfn(u64 start, u64 len, u64 pgoff, void *data)
 	map__set_end(list_node->map, map__start(list_node->map) + len);
 	map__set_pgoff(list_node->map, pgoff);
 
-	list_add(&list_node->node, &md->maps);
+	list_for_each_entry(node, &md->maps, node) {
+		/*
+		 * When the new map (list_node)'s end address is less than
+		 * current node, it can be divided into three cases.
+		 *
+		 * Case 1: the new map does not overlap with the current node,
+		 * as the new map's end address is less than the current node's
+		 * start address.
+		 *                      [*******node********]
+		 *    [***list_node***] `start              `end
+		 *    `start          `end
+		 *
+		 * Case 2: the new map overlaps with the current node.
+		 *
+		 *        ,start              ,end
+		 *        [*******node********]
+		 *    [***list_node***]
+		 *    `start          `end
+		 *
+		 * Case 3: the new map is subset of the current node.
+		 *
+		 *        ,start              ,end
+		 *        [*******node********]
+		 *         [***list_node***]
+		 *         `start          `end
+		 *
+		 * For above three cases, insert the new map node before the
+		 * current node.
+		 */
+		if (map__end(node->map) > map__end(list_node->map))
+			break;
+
+		/*
+		 * When the new map is subset of the current node and both nodes
+		 * have the same end address, insert the new map node before the
+		 * current node.
+		 *
+		 *        ,start              ,end
+		 *        [*******node********]
+		 *            [***list_node***]
+		 *            `start          `end
+		 */
+		if ((map__end(node->map) == map__end(list_node->map)) &&
+		    (map__start(node->map) <= map__start(list_node->map)))
+			break;
+	}
 
+	/* Insert the new node (list_node) ahead */
+	list_add_tail(&list_node->node, &node->node);
 	return 0;
 }
 
-- 
2.34.1