From 92ca922f0a19145f2dcc99d84fe656fa55b52c2e Mon Sep 17 00:00:00 2001 From: Hong zhi guo Date: Tue, 31 Jul 2012 16:41:35 -0700 Subject: [PATCH] vmalloc: walk vmap_areas by sorted list instead of rb_next() There's a walk by repeating rb_next to find a suitable hole. Could be simply replaced by walk on the sorted vmap_area_list. More simpler and efficient. Mutation of the list and tree only happens in pair within __insert_vmap_area and __free_vmap_area, under protection of vmap_area_lock. The patch code is also under vmap_area_lock, so the list walk is safe, and consistent with the tree walk. Tested on SMP by repeating batch of vmalloc anf vfree for random sizes and rounds for hours. Signed-off-by: Hong Zhiguo Cc: Nick Piggin Cc: Johannes Weiner Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- mm/vmalloc.c | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/mm/vmalloc.c b/mm/vmalloc.c index e03f4c7307a5..7e25ee3ce6e5 100644 --- a/mm/vmalloc.c +++ b/mm/vmalloc.c @@ -413,11 +413,11 @@ nocache: if (addr + size - 1 < addr) goto overflow; - n = rb_next(&first->rb_node); - if (n) - first = rb_entry(n, struct vmap_area, rb_node); - else + if (list_is_last(&first->list, &vmap_area_list)) goto found; + + first = list_entry(first->list.next, + struct vmap_area, list); } found: -- 2.20.1