linux-kernel - [PATCH v3] mm/vmalloc: terminate searching since one node found

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>] [day] [month] [year] [list]

Date:   Tue, 18 Jul 2017 16:27:04 +0800
From:   Zhaoyang Huang <huangzhaoyang@...il.com>
To:     zhaoyang.huang@...eadtrum.com,
        Andrew Morton <akpm@...ux-foundation.org>,
        Michal Hocko <mhocko@...e.com>, Ingo Molnar <mingo@...nel.org>,
        zijun_hu <zijun_hu@....com>, Vlastimil Babka <vbabka@...e.cz>,
        Thomas Garnier <thgarnie@...gle.com>,
        "Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
        Andrey Ryabinin <aryabinin@...tuozzo.com>, linux-mm@...ck.org,
        linux-kernel@...r.kernel.org
Subject: [PATCH v3] mm/vmalloc: terminate searching since one node found

It is no need to find the very beginning of the area within
alloc_vmap_area, which can be done by judging each node during the process

For current approach, the worst case is that the starting node which be found
for searching the 'vmap_area_list' is close to the 'vstart', while the final
available one is round to the tail(especially for the left branch).
This commit have the list searching start at the first available node, which
will save the time of walking the rb tree'(1)' and walking the list'(2)'.

      vmap_area_root
          /      \
     tmp_next     U
        /
      tmp
       /
     ...  (1)
      /
    first(current approach)

vmap_area_list->...->first->...->tmp->tmp_next
                            (2)

Signed-off-by: Zhaoyang Huang <zhaoyang.huang@...eadtrum.com>
---
 mm/vmalloc.c | 9 +++++++++
 1 file changed, 9 insertions(+)

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index 34a1c3e..9a5c177 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -459,9 +459,18 @@ static struct vmap_area *alloc_vmap_area(unsigned long size,
 
 		while (n) {
 			struct vmap_area *tmp;
+			struct vmap_area *tmp_next;
 			tmp = rb_entry(n, struct vmap_area, rb_node);
+			tmp_next = list_next_entry(tmp, list);
 			if (tmp->va_end >= addr) {
 				first = tmp;
+				if (ALIGN(tmp->va_end, align) + size
+						< tmp_next->va_start) {
+					addr = ALIGN(tmp->va_end, align);
+			                if (cached_hole_size >= size)
+						cached_hole_size = 0;
+					goto found;
+				}
 				if (tmp->va_start <= addr)
 					break;
 				n = n->rb_left;
-- 
1.9.1