@@ -585,16 +585,16 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
phys_addr_t base, phys_addr_t size,
int nid, enum memblock_flags flags)
{
- bool insert = false;
phys_addr_t obase = base;
phys_addr_t end = base + memblock_cap_size(base, &size);
- int idx, nr_new, start_rgn = -1, end_rgn;
+ phys_addr_t rbase, rend;
+ int idx, nr_new, start_rgn, end_rgn;
struct memblock_region *rgn;
if (!size)
return 0;
- /* special case for empty array */
+ /* Special case for empty array */
if (type->regions[0].size == 0) {
WARN_ON(type->cnt != 0 || type->total_size);
type->regions[0].base = base;
@@ -606,80 +606,114 @@ static int __init_memblock memblock_add_range(struct memblock_type *type,
return 0;
}
+ /* Delayed assignment, which is not necessary when the array is empty. */
+ start_rgn = -1;
/*
- * The worst case is when new range overlaps all existing regions,
- * then we'll need type->cnt + 1 empty regions in @type. So if
- * type->cnt * 2 + 1 is less than or equal to type->max, we know
- * that there is enough empty regions in @type, and we can insert
- * regions directly.
+ * Originally, `end_rgn` didn't need to be assigned a value,
+ * but due to the use of nested conditional expressions,
+ * the compiler reports a warning that `end_rgn` is uninitialized.
+ * Therefore, it has been given an initial value here
+ * to eliminate the warning.
*/
- if (type->cnt * 2 + 1 <= type->max)
- insert = true;
+ end_rgn = -1;
repeat:
/*
- * The following is executed twice. Once with %false @insert and
- * then with %true. The first counts the number of regions needed
- * to accommodate the new area. The second actually inserts them.
+ * It is assumed that insertion is always possible under normal circumstances.
+ * If memory is insufficient during insertion, the operation will record the need,
+ * allocate memory, and then re-execute the insertion for the remaining portion.
*/
base = obase;
nr_new = 0;
for_each_memblock_type(idx, type, rgn) {
- phys_addr_t rbase = rgn->base;
- phys_addr_t rend = rbase + rgn->size;
+ rbase = rgn->base;
+ rend = rbase + rgn->size;
if (rbase >= end)
break;
if (rend <= base)
continue;
+
/*
- * @rgn overlaps. If it separates the lower part of new
- * area, insert that portion.
+ * @rgn overlaps. If it separates the lower part of new area, insert that portion.
*/
if (rbase > base) {
#ifdef CONFIG_NUMA
WARN_ON(nid != memblock_get_region_node(rgn));
#endif
WARN_ON(flags != rgn->flags);
- nr_new++;
- if (insert) {
+ /*
+ * If memory is insufficient, the space required will be recorded.
+ * If memory is sufficient, the insertion will proceed.
+ */
+ if (type->cnt >= type->max) {
+ /*
+ * Record obase as the address where the
+ * overlapping part has not been resolved,
+ * so that when repeat restarts,
+ * redundant operations of resolving the
+ * overlapping addresses are avoided.
+ */
+ if (nr_new == 0)
+ obase = base;
+ nr_new++;
+ } else {
if (start_rgn == -1)
start_rgn = idx;
end_rgn = idx + 1;
- memblock_insert_region(type, idx++, base,
- rbase - base, nid,
- flags);
+ memblock_insert_region(type, idx++, base, rbase - base, nid, flags);
}
}
- /* area below @rend is dealt with, forget about it */
+ /* Area below @rend is dealt with, forget about it */
base = min(rend, end);
}
- /* insert the remaining portion */
+ /* Insert the remaining portion */
if (base < end) {
- nr_new++;
- if (insert) {
+ /*
+ * Similarly, after handling the overlapping part,
+ * it is still possible that memory is
+ * insufficient. In that case, the space will be recorded once again.
+ */
+ if (type->cnt >= type->max) {
+ /*
+ * The address of obase needs to be recorded here as well. The purpose is to
+ * handle the situation where,
+ * after resolving the overlap, there is still a remaining space to
+ * insert but memory is insufficient (i.e.,
+ * no memory shortage occurred while resolving the overlap).
+ * This means that space for
+ * N (overlapping parts) + 1 (non-overlapping part) is required.
+ * If obase is not recorded, after memory expansion,
+ * base might revert to the original address to be
+ * inserted (which could be overlapping).
+ * This could lead to for_each_memblock_type attempting
+ * to resolve the overlap again, causing multiple unnecessary iterations,
+ * even if it's just a simple check.
+ */
+ if (nr_new == 0)
+ obase = base;
+ nr_new++;
+ } else {
if (start_rgn == -1)
start_rgn = idx;
end_rgn = idx + 1;
- memblock_insert_region(type, idx, base, end - base,
- nid, flags);
+ memblock_insert_region(type, idx, base, end - base, nid, flags);
}
}
- if (!nr_new)
- return 0;
-
/*
- * If this was the first round, resize array and repeat for actual
- * insertions; otherwise, merge and return.
+ * Finally, check if memory insufficiency occurred during insertion.
+ * If so, the memory will be expanded to an appropriate size,
+ * and the remaining portion will be inserted again.
+ * If not, it means memory is sufficient, and the regions will be merged directly.
*/
- if (!insert) {
- while (type->cnt + nr_new > type->max)
+ if (nr_new > 0) {
+ while (type->cnt + nr_new > type->max) {
if (memblock_double_array(type, obase, size) < 0)
return -ENOMEM;
- insert = true;
+ }
goto repeat;
} else {
memblock_merge_regions(type, start_rgn, end_rgn);
Hi Mike Rapoport、Andrew Morton I have recently been researching the mm subsystem of the Linux kernel, and I came across the memblock_add_range function, which piqued my interest. I found the implementation approach quite interesting, so I analyzed it and identified some areas for optimization. Starting with this part of the code: if (type->cnt * 2 + 1 <= type->max) insert = true; The idea here is good, but it has a certain flaw. The condition is rather restrictive, and it cannot be executed initially. Moreover, it is only valid when the remaining space is (2/1) + 1. If there is enough memory, but it does not satisfy (2/1) + 1, the insertion operation still needs to be performed twice. So, I came up with a solution: delayed allocation. Since memory expansion is exponential, it means that performing around four expansions should be sufficient to handle the memory operations needed early in the kernel, before the buddy system takes over. Therefore, assuming that memory is adequate at the beginning, insertion can happen at any time. If memory is insufficient during the insertion, we record the operation (changing the insertion into a record operation). This involves logging the starting address of the remaining unused space and the number of insertions needed (this usually happens when resolving overlaps). After logging, memory allocation is performed, and then the insertion is attempted again. The benefit of this approach is that it significantly reduces the time cost and also records the starting address of the remaining unused space. This way, the next time the operation begins, it doesn’t have to start from scratch, somewhat like a checkpointed transmission. I optimized memblock_add_range according to my approach. Afterward, I tested it in the qemu-arm environment, and it worked properly. Additionally, I tested it in the linux/tools/testing/memblock directory, and it successfully passed all the test cases. I used perf for performance profiling, and here are my diagnostic records (by the way, my CPU is a 13th Gen Intel(R) Core(TM) i7-13700): The performance of memblock_add_range before the modification is as follows: Samples: 3K of event 'cycles', Event count (approx.): 3853609007 Children Self Comm Shar Symbol 1.32% 1.32% main main [.] memblock_add_range.isra.0 After the modification: Samples: 3K of event 'cycles', Event count (approx.): 3839056584 Children Self Comm Shar Symbol 0.67% 0.67% main main [.] memblock_add_range.isra.0 The optimal performance can reach 0.38%. Samples: 3K of event 'cycles', Event count (approx.): 3839056584 Children Self Comm Shar Symbol 0.38% 0.38% main main [.] memblock_add_range.isra.0 To test the optimal and average utilization rates, I wrote a shell script to execute two versions of the code (one before modification and one after modification). It runs each version 100 times and analyzes the results of perf to calculate the average, minimum, and maximum utilization rates for memblock_add_range. Below are the results from the script: After applying the patch, I measured the performance improvements using `perf` on my Intel i7-13700. The results show a significant reduction in the time spent in `memblock_add_range`: - Before the patch: - Average: 1.22% - Max: 1.63%, Min: 0.93% - After the patch: - Average: 0.69% - Max: 0.94%, Min: 0.50% The optimization provides a 53% reduction in the average CPU time spent in this function, with the worst-case performance now close to the best-case performance before the optimization. Here is my test script (it should be run only in the linux/tools/testing/memblock directory): #!/bin/bash PERF_DATA="perf.data" TOTAL_RUNS=100 CHILDREN_PERCENTAGE=0 SELF_PERCENTAGE=0 CHILDREN_AVERAGE=0 SELF_AVERAGE=0 CHILDRENS=() SELFS=() MIN_CHILDREN=0 MAX_CHILDREN=0 MIN_SELF=0 MAX_SELF=0 function log() { echo -e $* echo -e $* >perf_test.log } if [ -f "./perf_test.log" ]; then rm "./perf_test.log" fi touch perf_test.log for i in $(seq 1 $TOTAL_RUNS) do sudo perf record -e cycles -g ./main > /dev/null 2>&1 read CHILDREN SELF <<< $(sudo perf report | grep "memblock_add_range.isra.0" | awk 'NR==2 {print $1, $2}' | sed 's/%//g') if [ -z $CHILDREN ]; then read CHILDREN SELF <<< $(sudo perf report | grep "memblock_add_range.isra.0" | awk 'NR==1 {print $1, $2}' | sed 's/%//g') fi if [ $MIN_CHILDREN == 0 ]; then MIN_CHILDREN=$CHILDREN fi if [ $MIN_SELF == 0 ]; then MIN_SELF=$SELF fi if (( $(echo "$CHILDREN > $MAX_CHILDREN" | bc -l) )); then MAX_CHILDREN=$CHILDREN elif (( $(echo "$CHILDREN < $MIN_CHILDREN" | bc -l) )); then MIN_CHILDREN=$CHILDREN fi if (( $(echo "$SELF > $MAX_SELF" | bc -l) )); then MAX_SELF=$SELF elif (( $(echo "$SELF < $MIN_SELF" | bc -l) )); then MIN_SELF=$SELF fi log "($i) memblock_add_range.isra.0: Children <$CHILDREN>, Self <$SELF>" CHILDRENS+=($CHILDREN) SELFS+=($SELF) sudo rm -f $PERF_DATA done for PERCENT in "${CHILDRENS[@]}" do CHILDREN_PERCENTAGE=$(echo "$CHILDREN_PERCENTAGE + $PERCENT" | bc) done for PERCENT in "${SELFS[@]}" do SELF_PERCENTAGE=$(echo "$SELF_PERCENTAGE + $PERCENT" | bc) done CHILDREN_AVERAGE=$(echo "scale=2; $CHILDREN_PERCENTAGE / $TOTAL_RUNS" | bc) CHILDREN_AVERAGE=$(printf "%.2f" $CHILDREN_AVERAGE) SELF_AVERAGE=$(echo "scale=2; $SELF_PERCENTAGE / $TOTAL_RUNS" | bc) SELF_AVERAGE=$(printf "%.2f" $SELF_AVERAGE) log "" log "Result report:" log "memblock_add_range.isra.0 Average: Children (Ave<$CHILDREN_AVERAGE%>, Min<$MIN_CHILDREN>, Max<$MAX_CHILDREN)> Self (Ave<$SELF_AVERAGE%>, Min<$MIN_SELF>, Max<$MAX_SELF>)" Here is my patch: From 1d4da808b1c6ef2a8706782c3fe724c62169f311 Mon Sep 17 00:00:00 2001 From: "stephen.eta.zhou" <stephen.eta.zhou@outlook.com> Date: Wed, 5 Feb 2025 12:04:40 +0800 Subject: [PATCH] mm: optimize memblock_add_range() for improved performance - Streamlined memory insertion logic to minimize redundant iterations. - Improved handling of memory insufficiency to avoid excessive reallocations. Signed-off-by: stephen.eta.zhou <stephen.eta.zhou@outlook.com> --- mm/memblock.c | 106 +++++++++++++++++++++++++++++++++----------------- 1 file changed, 70 insertions(+), 36 deletions(-) -- 2.25.1