From dc09dd60a03e083c8e9ed2a971e1fda6f1a36309 Mon Sep 17 00:00:00 2001 From: Syed Rameez Mustafa Date: Tue, 7 Jun 2016 15:18:37 -0700 Subject: sched: Optimize the next top task search logic upon task migration find_next_top_index() is responsible for finding the second top task on a CPU when the top task migrates away from that CPU. This operation is expensive as we need to iterate the entire array of top tasks to find the second top task. Optimize this by introducing bitmaps for tracking top task indices. There are two bitmaps; one for the previous window and one for the current window. Each bit in a bitmap tracks whether the corresponding bucket in the top task hashmap has a non zero refcount. The bit is set when the refcount becomes non zero and is cleared when it becomes zero. Finding the second top task upon migration is then simply a matter of finding the highest set bit in the bitmap. Change-Id: Ibafaf66eed756b0328704dfaa89c17ab0d84e359 Signed-off-by: Syed Rameez Mustafa --- include/linux/types.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'include/linux') diff --git a/include/linux/types.h b/include/linux/types.h index 70dd3dfde631..9f2d2f46b459 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -9,6 +9,9 @@ #define DECLARE_BITMAP(name,bits) \ unsigned long name[BITS_TO_LONGS(bits)] +#define DECLARE_BITMAP_ARRAY(name,nr,bits) \ + unsigned long name[nr][BITS_TO_LONGS(bits)] + typedef __u32 __kernel_dev_t; typedef __kernel_fd_set fd_set; -- cgit v1.2.3