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.

TODO: If a lower-priority task must be preempted and there are several
scheduled tasks with the same low priority, then preempt the closest.

7 files changed, 217 insertions, 1 deletions

diff --git a/include/litmus/affinity.h b/include/litmus/affinity.h
new file mode 100644
index 000000000000..2bcb09c70046
--- /dev/null
+++ b/include/litmus/affinity.h
@@ -0,0 +1,72 @@
+#ifndef __LITMUS_AFFINITY_H
+#define __LITMUS_AFFINITY_H
+
+#include <linux/cpumask.h>
+
+#define MAX_CACHE_DEPTH 3
+
+struct neighborhood
+{
+        unsigned int size[MAX_CACHE_DEPTH];
+        cpumask_var_t neighbors[MAX_CACHE_DEPTH];
+};
+
+/* 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.
+ */
+#define get_nearest_available_cpu(nearest, start, entries, release_master) \
+{ \
+        if(!(start)->linked) \
+        { \
+                (nearest) = (start); \
+        } \
+        else \
+        { \
+                int __level; \
+                int __cpu; \
+                struct neighborhood* __neighbors = &neigh_info[(start)->cpu]; \
+                (nearest) = NULL; \
+                \
+                for(__level = 0; (__level < MAX_CACHE_DEPTH) && !(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..65c881b6ba12 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"
+        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 ahrder to find since tasks may migrate less often.
+
+          NOTES:
+                * Pfair/PD^2 does not support this option.
+                * Only x86 currently supported.
+
+          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..9d5405cf05fd
--- /dev/null
+++ b/litmus/affinity.c
@@ -0,0 +1,49 @@
+#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 > MAX_CACHE_DEPTH) /* L4 and greater?? */
+                depth = MAX_CACHE_DEPTH;
+
+        for_each_online_cpu(cpu)
+        {
+                for(i = 0; i < (int)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 < MAX_CACHE_DEPTH; ++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 26938acacafc..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);
@@ -115,7 +119,7 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param)
                 tp.cls != RT_CLASS_BEST_EFFORT)
         {
                 printk(KERN_INFO "litmus: real-time task %d rejected "
-                                 "because its class is invalid\n");
+                                 "because its class is invalid\n", pid);
                 goto out_unlock;
         }
         if (tp.budget_policy != NO_ENFORCEMENT &&
@@ -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..1538695c1c1d 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(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..c22bba91b319 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,6 +257,23 @@ 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)
 {
@@ -266,8 +287,21 @@ static void check_for_preemptions(void)
                 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);
         }