Litmus core: add generic clustering support

Inspired by the existing C-EDF code, this generic version will build
clusters of CPUs based on a given cache level.

3 files changed, 134 insertions, 0 deletions

diff --git a/include/litmus/clustered.h b/include/litmus/clustered.h
index cad12467b4ee..0c18dcb15e6c 100644
--- a/include/litmus/clustered.h
+++ b/include/litmus/clustered.h
@@ -19,4 +19,26 @@ const char* cache_level_name(enum cache_level level);
 struct proc_dir_entry* create_cluster_file(struct proc_dir_entry* parent,
                                            enum cache_level* level);
 
+
+
+struct scheduling_cluster {
+        unsigned int id;
+        /* list of CPUs that are part of this cluster */
+        struct list_head cpus;
+};
+
+struct cluster_cpu {
+        unsigned int id; /* which CPU is this? */
+        struct list_head cluster_list; /* List of the CPUs in this cluster. */
+        struct scheduling_cluster* cluster; /* The cluster that this CPU belongs to. */
+};
+
+int get_cluster_size(enum cache_level level);
+
+int assign_cpus_to_clusters(enum cache_level level,
+                            struct scheduling_cluster* clusters[],
+                            unsigned int num_clusters,
+                            struct cluster_cpu* cpus[],
+                            unsigned int num_cpus);
+
 #endif
diff --git a/litmus/Makefile b/litmus/Makefile
index 62a20e266eeb..ad9936e07b83 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -6,6 +6,7 @@ obj-y     = sched_plugin.o litmus.o \
             preempt.o \
             litmus_proc.o \
             budget.o \
+            clustered.o \
             jobs.o \
             sync.o \
             rt_domain.o \
diff --git a/litmus/clustered.c b/litmus/clustered.c
new file mode 100644
index 000000000000..04450a8ad4fe
--- /dev/null
+++ b/litmus/clustered.c
@@ -0,0 +1,111 @@
+#include <linux/gfp.h>
+#include <linux/cpumask.h>
+#include <linux/list.h>
+
+#include <litmus/clustered.h>
+
+#ifndef CONFIG_X86
+/* fake get_shared_cpu_map() on non-x86 architectures */
+
+int get_shared_cpu_map(cpumask_var_t mask, unsigned int cpu, int index)
+{
+        if (index != 1)
+                return 1;
+        else {
+                /* Fake L1: CPU is all by itself. */
+                cpumask_clear(mask);
+                cpumask_set_cpu(cpu, mask);
+                return 0;
+        }
+}
+
+#endif
+
+int get_cluster_size(enum cache_level level)
+{
+        cpumask_var_t mask;
+        int ok;
+        int num_cpus;
+
+        if (level == GLOBAL_CLUSTER)
+                return num_online_cpus();
+        else {
+                if (!zalloc_cpumask_var(&mask, GFP_ATOMIC))
+                        return -ENOMEM;
+                /* assumes CPU 0 is representative of all CPUs */
+                ok = get_shared_cpu_map(mask, 0, level);
+                /* ok == 0 means we got the map; otherwise it's an invalid cache level */
+                if (ok == 0)
+                        num_cpus = cpumask_weight(mask);
+                free_cpumask_var(mask);
+
+                if (ok == 0)
+                        return num_cpus;
+                else
+                        return -EINVAL;
+        }
+}
+
+int assign_cpus_to_clusters(enum cache_level level,
+                            struct scheduling_cluster* clusters[],
+                            unsigned int num_clusters,
+                            struct cluster_cpu* cpus[],
+                            unsigned int num_cpus)
+{
+        cpumask_var_t mask;
+        unsigned int i, free_cluster = 0, low_cpu;
+        int err = 0;
+
+        if (!zalloc_cpumask_var(&mask, GFP_ATOMIC))
+                return -ENOMEM;
+
+        /* clear cluster pointers */
+        for (i = 0; i < num_cpus; i++) {
+                cpus[i]->id      = i;
+                cpus[i]->cluster = NULL;
+        }
+
+        /* initialize clusters */
+        for (i = 0; i < num_clusters; i++) {
+                clusters[i]->id = i;
+                INIT_LIST_HEAD(&clusters[i]->cpus);
+        }
+
+        /* Assign each CPU. Two assumtions are made:
+         * 1) The index of a cpu in cpus corresponds to its processor id (i.e., the index in a cpu mask).
+         * 2) All cpus that belong to some cluster are online.
+         */
+        for_each_online_cpu(i) {
+                /* get lowest-id CPU in cluster */
+                if (level != GLOBAL_CLUSTER) {
+                        err = get_shared_cpu_map(mask, cpus[i]->id, level);
+                        if (err != 0) {
+                                /* ugh... wrong cache level? Either caller screwed up
+                                 * or the CPU topology is weird. */
+                                printk(KERN_ERR "Could not set up clusters for L%d sharing (max: L%d).\n",
+                                       level, err);
+                                err = -EINVAL;
+                                goto out;
+                        }
+                        low_cpu = cpumask_first(mask);
+                } else
+                        low_cpu = 0;
+                if (low_cpu == i) {
+                        /* caller must provide an appropriate number of clusters */
+                        BUG_ON(free_cluster >= num_clusters);
+
+                        /* create new cluster */
+                        cpus[i]->cluster = clusters[free_cluster++];
+                } else {
+                        /* low_cpu points to the right cluster
+                         * Assumption: low_cpu is actually online and was processed earlier. */
+                        cpus[i]->cluster = cpus[low_cpu]->cluster;
+                }
+                /* enqueue in cpus list */
+                list_add(&cpus[i]->cluster_list, &cpus[i]->cluster->cpus);
+                printk(KERN_INFO "Assigning CPU%u to cluster %u\n.", i, cpus[i]->cluster->id);
+        }
+out:
+        free_cpumask_var(mask);
+        return err;
+}