Avoid needlessly costly migrations. CONFIG_SCHED_CPU_AFFINITY

Given a choice between several available CPUs (unlinked) on which
to schedule a task, let the scheduler select the CPU closest to
where that task was previously scheduled.  Hopefully, this will
reduce cache migration penalties.

Notes: SCHED_CPU_AFFINITY is dependent upon x86 (only x86 is
supported at this time). Also PFair/PD^2 does not make use of
this feature.

Signed-off-by: Andrea Bastoni <bastoni@cs.unc.edu>

7 files changed, 222 insertions, 3 deletions

diff --git a/include/litmus/affinity.h b/include/litmus/affinity.h
new file mode 100644
index 000000000000..5eee0eaa170d
--- /dev/null
+++ b/include/litmus/affinity.h
@@ -0,0 +1,79 @@
+#ifndef __LITMUS_AFFINITY_H
+#define __LITMUS_AFFINITY_H
+
+#include <linux/cpumask.h>
+
+/*
+  L1 (instr) = depth 0
+  L1 (data)  = depth 1
+  L2 = depth 2
+  L3 = depth 3
+ */
+#define NUM_CACHE_LEVELS 4
+
+struct neighborhood
+{
+        unsigned int size[NUM_CACHE_LEVELS];
+        cpumask_var_t neighbors[NUM_CACHE_LEVELS];
+};
+
+/* topology info is stored redundently in a big array for fast lookups */
+extern struct neighborhood neigh_info[NR_CPUS];
+
+void init_topology(void); /* called by Litmus module's _init_litmus() */
+
+/* Works like:
+void get_nearest_available_cpu(
+        cpu_entry_t* nearest,
+        cpu_entry_t* start,
+        cpu_entry_t* entries,
+        int release_master)
+
+Set release_master = -1 for no RM.
+
+We use a macro here to exploit the fact that C-EDF and G-EDF
+have similar structures for their cpu_entry_t structs, even though
+they do not share a common base-struct.  The macro allows us to
+avoid code duplication.
+
+TODO: Factor out the job-to-processor linking from C/G-EDF into
+a reusable "processor mapping".  (See B.B.'s RTSS'09 paper &
+dissertation.)
+ */
+#define get_nearest_available_cpu(nearest, start, entries, release_master) \
+{ \
+        (nearest) = NULL; \
+        if (!(start)->linked) { \
+                (nearest) = (start); \
+        } else { \
+                int __level; \
+                int __cpu; \
+                struct neighborhood* __neighbors = &neigh_info[(start)->cpu]; \
+                \
+                for (__level = 0; (__level < NUM_CACHE_LEVELS) && !(nearest); ++__level) { \
+                        if (__neighbors->size[__level] > 1) { \
+                                for_each_cpu(__cpu, __neighbors->neighbors[__level]) { \
+                                        if (__cpu != (release_master)) { \
+                                                cpu_entry_t* __entry = &per_cpu((entries), __cpu); \
+                                                if (!__entry->linked) { \
+                                                        (nearest) = __entry; \
+                                                        break; \
+                                                } \
+                                        } \
+                                } \
+                        } else if (__neighbors->size[__level] == 0) { \
+                                break; \
+                        } \
+                } \
+        } \
+        \
+        if ((nearest)) { \
+                TRACE("P%d is closest available CPU to P%d\n", \
+                                (nearest)->cpu, (start)->cpu); \
+        } else { \
+                TRACE("Could not find an available CPU close to P%d\n", \
+                                (start)->cpu); \
+        } \
+}
+
+#endif
diff --git a/litmus/Kconfig b/litmus/Kconfig
index ad8dc8308cf0..d7fde6f97e14 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -62,6 +62,25 @@ config LITMUS_LOCKING
 
 endmenu
 
+menu "Performance Enhancements"
+
+config SCHED_CPU_AFFINITY
+        bool "Local Migration Affinity"
+        depends on X86
+        default y
+        help
+          Rescheduled tasks prefer CPUs near to their previously used CPU.  This
+          may improve performance through possible preservation of cache affinity.
+
+          Warning: May make bugs harder to find since tasks may migrate less often.
+
+          NOTES:
+                * Feature is not utilized by PFair/PD^2.
+
+          Say Yes if unsure.
+
+endmenu
+
 menu "Tracing"
 
 config FEATHER_TRACE
diff --git a/litmus/Makefile b/litmus/Makefile
index ad9936e07b83..7338180f196f 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -21,6 +21,7 @@ obj-y     = sched_plugin.o litmus.o \
 
 obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o
 obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o
+obj-$(CONFIG_SCHED_CPU_AFFINITY) += affinity.o
 
 obj-$(CONFIG_FEATHER_TRACE) += ft_event.o ftdev.o
 obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
diff --git a/litmus/affinity.c b/litmus/affinity.c
new file mode 100644
index 000000000000..9adab7a3bcd7
--- /dev/null
+++ b/litmus/affinity.c
@@ -0,0 +1,44 @@
+#include <linux/cpu.h>
+
+#include <litmus/affinity.h>
+
+struct neighborhood neigh_info[NR_CPUS];
+
+/* called by _init_litmus() */
+void init_topology(void) {
+        int cpu;
+        int i;
+        int chk;
+        int depth = num_cache_leaves;
+
+        if (depth > NUM_CACHE_LEVELS)
+                depth = NUM_CACHE_LEVELS;
+
+        for_each_online_cpu(cpu) {
+                for (i = 0; i < depth; ++i) {
+                        long unsigned int firstbits;
+
+                        chk = get_shared_cpu_map((struct cpumask *)&neigh_info[cpu].neighbors[i], cpu, i);
+                        if (chk) {
+                                /* failed */
+                                neigh_info[cpu].size[i] = 0;
+                        } else {
+                                /* size = num bits in mask */
+                                neigh_info[cpu].size[i] =
+                                        cpumask_weight((struct cpumask *)&neigh_info[cpu].neighbors[i]);
+                        }
+                        firstbits = *neigh_info[cpu].neighbors[i]->bits;
+                        printk("CPU %d has %d neighbors at level %d. (mask = %lx)\n",
+                                                        cpu, neigh_info[cpu].size[i], i, firstbits);
+                }
+
+                /* set data for non-existent levels */
+                for (; i < NUM_CACHE_LEVELS; ++i) {
+                        neigh_info[cpu].size[i] = 0;
+
+                        printk("CPU %d has %d neighbors at level %d. (mask = %lx)\n",
+                                                cpu, neigh_info[cpu].size[i], i, 0lu);
+                }
+        }
+}
+
diff --git a/litmus/litmus.c b/litmus/litmus.c
index bb8c6c7e9dd1..73af6c3010d6 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -17,6 +17,10 @@
 #include <litmus/litmus_proc.h>
 #include <litmus/sched_trace.h>
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+#include <litmus/affinity.h>
+#endif
+
 /* Number of RT tasks that exist in the system */
 atomic_t rt_task_count          = ATOMIC_INIT(0);
 static DEFINE_RAW_SPINLOCK(task_transition_lock);
@@ -540,6 +544,10 @@ static int __init _init_litmus(void)
 
         init_litmus_proc();
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+        init_topology();
+#endif
+
         return 0;
 }
 
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index 73fe1c442a0d..e29a9fe2a8e8 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -43,6 +43,10 @@
 
 #include <litmus/bheap.h>
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+#include <litmus/affinity.h>
+#endif
+
 /* to configure the cluster size */
 #include <litmus/litmus_proc.h>
 #include <linux/uaccess.h>
@@ -257,6 +261,23 @@ static noinline void requeue(struct task_struct* task)
         }
 }
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+static cpu_entry_t* cedf_get_nearest_available_cpu(
+                                cedf_domain_t *cluster, cpu_entry_t* start)
+{
+        cpu_entry_t* affinity;
+
+        get_nearest_available_cpu(affinity, start, cedf_cpu_entries, -1);
+
+        /* make sure CPU is in our cluster */
+        if (affinity && cpu_isset(affinity->cpu, *cluster->cpu_map))
+                return(affinity);
+        else
+                return(NULL);
+}
+#endif
+
+
 /* check for any necessary preemptions */
 static void check_for_preemptions(cedf_domain_t *cluster)
 {
@@ -270,8 +291,20 @@ static void check_for_preemptions(cedf_domain_t *cluster)
                 task = __take_ready(&cluster->domain);
                 TRACE("check_for_preemptions: attempting to link task %d to %d\n",
                       task->pid, last->cpu);
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+                {
+                        cpu_entry_t* affinity =
+                                        cedf_get_nearest_available_cpu(cluster,
+                                                &per_cpu(cedf_cpu_entries, task_cpu(task)));
+                        if(affinity)
+                                last = affinity;
+                        else if(last->linked)
+                                requeue(last->linked);
+                }
+#else
                 if (last->linked)
                         requeue(last->linked);
+#endif
                 link_task_to_cpu(task, last);
                 preempt(last);
         }
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 3092797480f8..17926e9fccdc 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -23,6 +23,10 @@
 
 #include <litmus/bheap.h>
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+#include <litmus/affinity.h>
+#endif
+
 #include <linux/module.h>
 
 /* Overview of GSN-EDF operations.
@@ -253,21 +257,52 @@ static noinline void requeue(struct task_struct* task)
         }
 }
 
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+static cpu_entry_t* gsnedf_get_nearest_available_cpu(cpu_entry_t* start)
+{
+        cpu_entry_t* affinity;
+
+        get_nearest_available_cpu(affinity, start, gsnedf_cpu_entries,
+#ifdef CONFIG_RELEASE_MASTER
+                        gsnedf.release_master
+#else
+                        -1
+#endif
+                        );
+
+        return(affinity);
+}
+#endif
+
 /* check for any necessary preemptions */
 static void check_for_preemptions(void)
 {
         struct task_struct *task;
         cpu_entry_t* last;
 
-        for(last = lowest_prio_cpu();
-            edf_preemption_needed(&gsnedf, last->linked);
-            last = lowest_prio_cpu()) {
+        for (last = lowest_prio_cpu();
+             edf_preemption_needed(&gsnedf, last->linked);
+             last = lowest_prio_cpu()) {
                 /* preemption necessary */
                 task = __take_ready(&gsnedf);
                 TRACE("check_for_preemptions: attempting to link task %d to %d\n",
                       task->pid, last->cpu);
+
+#ifdef CONFIG_SCHED_CPU_AFFINITY
+                {
+                        cpu_entry_t* affinity =
+                                        gsnedf_get_nearest_available_cpu(
+                                                &per_cpu(gsnedf_cpu_entries, task_cpu(task)));
+                        if (affinity)
+                                last = affinity;
+                        else if (last->linked)
+                                requeue(last->linked);
+                }
+#else
                 if (last->linked)
                         requeue(last->linked);
+#endif
+
                 link_task_to_cpu(task, last);
                 preempt(last);
         }