linux-kernel - [RFC PATCH] mm: memblock: optimize memblock_find_in_range

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Date:	Fri, 4 Jan 2013 17:24:53 +0800
From:	Lin Feng <linfeng@...fujitsu.com>
To:	akpm@...ux-foundation.org, tj@...nel.org
Cc:	mingo@...nel.org, yinghai@...nel.org, liwanp@...ux.vnet.ibm.com,
	benh@...nel.crashing.org, tangchen@...fujitsu.com,
	linux-mm@...ck.org, linux-kernel@...r.kernel.org,
	Lin Feng <linfeng@...fujitsu.com>
Subject: [RFC PATCH] mm: memblock: optimize memblock_find_in_range_node() to minimize the search work

The memblock array is in ascending order and we traverse the memblock array in
reverse order so we can add some simple check to reduce the search work.

Tejun fix a underflow bug in 5d53cb27d8, but I think we could break there for
the same reason.

Cc: Tejun Heo <tj@...nel.org>
Signed-off-by: Lin Feng <linfeng@...fujitsu.com>
---
 mm/memblock.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/mm/memblock.c b/mm/memblock.c
index 6259055..a710557 100644
--- a/mm/memblock.c
+++ b/mm/memblock.c
@@ -111,11 +111,18 @@ phys_addr_t __init_memblock memblock_find_in_range_node(phys_addr_t start,
 	end = max(start, end);
 
 	for_each_free_mem_range_reverse(i, nid, &this_start, &this_end, NULL) {
+		/*
+		 * exclude the regions out of the candidate range, since it's
+		 * likely to find a suitable range, we ignore the worst case.
+		 */
+		if (this_start >= end)
+			continue;
+
 		this_start = clamp(this_start, start, end);
 		this_end = clamp(this_end, start, end);
 
 		if (this_end < size)
-			continue;
+			break;
 
 		cand = round_down(this_end - size, align);
 		if (cand >= this_start)
-- 
1.7.11.7

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/