Use /proc/litmus/domains to set up affinity masks

This patch replaces the algorithm used to compute CPU affinity masks.
The old algorithm was fragile and would break on systems with multiple
levels of shared caches. (As found on some older Intel chips, and as
one would probably find on a system with hyper-threading enabled.) The
bug stems from fact that Linux enumerates consecutive CPUs in a way
that distributes them across the physical system, thereby reducing
contention resources (e.g., cache).

Cluster size no longer needs to be provided now that cluster/CPU
mappings are explicit in /proc/litmus/domains/.

This keeps the following migration functions, but marks them as
deprecated:
  - be_migrate_to_cluster()
  - cluster_to_first_cpu()
  - partition_to_cpu()

Although the deprecated interfaces are supported, the implementations
for these functions call the new be_migrate_to_domain() and
domain_to_first_cpu() functions.

[bbb: resolved several merge conflicts]

3 files changed, 70 insertions, 61 deletions

diff --git a/src/litmus.c b/src/litmus.c
index dce8e1b..4631eea 100644
--- a/src/litmus.c
+++ b/src/litmus.c
@@ -135,7 +135,7 @@ int sporadic_partitioned(lt_t e_ns, lt_t p_ns, int partition)
         int ret;
         struct rt_task param;
 
-        ret = be_migrate_to_partition(partition);
+        ret = be_migrate_to_domain(partition);
         check("be_migrate_to_partition()");
         if (ret != 0)
                 return ret;
@@ -143,17 +143,17 @@ int sporadic_partitioned(lt_t e_ns, lt_t p_ns, int partition)
         init_rt_task_param(&param);
         param.exec_cost = e_ns;
         param.period = p_ns;
-        param.cpu = partition_to_cpu(partition);
+        param.cpu = domain_to_first_cpu(partition);
 
         return set_rt_task_param(gettid(), &param);
 }
 
-int sporadic_clustered(lt_t e_ns, lt_t p_ns, int cluster, int cluster_size)
+int sporadic_clustered(lt_t e_ns, lt_t p_ns, int cluster)
 {
         int ret;
         struct rt_task param;
 
-        ret = be_migrate_to_cluster(cluster, cluster_size);
+        ret = be_migrate_to_domain(cluster);
         check("be_migrate_to_cluster()");
         if (ret != 0)
                 return ret;
@@ -161,7 +161,7 @@ int sporadic_clustered(lt_t e_ns, lt_t p_ns, int cluster, int cluster_size)
         init_rt_task_param(&param);
         param.exec_cost = e_ns;
         param.period = p_ns;
-        param.cpu = cluster_to_first_cpu(cluster, cluster_size);
+        param.cpu = domain_to_first_cpu(cluster);
 
         return set_rt_task_param(gettid(), &param);
 }
diff --git a/src/migration.c b/src/migration.c
index 5de81d5..3bd6d0a 100644
--- a/src/migration.c
+++ b/src/migration.c
@@ -27,31 +27,48 @@ int num_online_cpus()
         return sysconf(_SC_NPROCESSORS_ONLN);
 }
 
-int partition_to_cpu(int partition)
+static int read_mapping(int idx, const char* which, unsigned long long int* mask)
 {
-        int cpu = partition;
-        int master = release_master();
-        if (master != -1 && master <= cpu) {
-                ++cpu; /* skip over the release master */
+        int     ret = -1;
+        char buf[129] = {0};
+        char fname[80] = {0};
+
+        if (num_online_cpus() > 64) {
+                /* XXX: Support more than 64 CPUs.
+                 * User can still set appropriate values directly. */
+                goto out;
         }
-        return cpu;
-}
 
-int cluster_to_first_cpu(int cluster, int cluster_sz)
-{
-        int first_cpu;
-        int master;
+        snprintf(fname, sizeof(fname), "/proc/litmus/%s/%d", which, idx);
+
+        ret = read_file(fname, &buf, sizeof(buf)-1);
+        if (ret <= 0)
+                goto out;
 
-        if (cluster_sz == 1)
-                return partition_to_cpu(cluster);
+        *mask = strtoull(buf, NULL, 16);
+        ret = 0;
 
-        master = release_master();
-        first_cpu = cluster * cluster_sz;
+out:
+        return ret;
+}
+
+int domain_to_cpus(int domain, unsigned long long int* mask)
+{
+        return read_mapping(domain, "domains", mask);
+}
 
-        if (master == first_cpu)
-                ++first_cpu;
+int cpu_to_domains(int cpu, unsigned long long int* mask)
+{
+        return read_mapping(cpu, "cpus", mask);
+}
 
-        return first_cpu;
+int domain_to_first_cpu(int domain)
+{
+        unsigned long long int mask;
+        int ret = domain_to_cpus(domain, &mask);
+        if(ret == 0)
+                return (ffsll(mask)-1);
+        return ret;
 }
 
 int be_migrate_thread_to_cpu(pid_t tid, int target_cpu)
@@ -89,44 +106,29 @@ int be_migrate_thread_to_cpu(pid_t tid, int target_cpu)
         return ret;
 }
 
-int be_migrate_thread_to_cluster(pid_t tid, int cluster, int cluster_sz)
-{
-        return __be_migrate_thread_to_cluster(tid, cluster, cluster_sz, 0);
-}
-
-int __be_migrate_thread_to_cluster(pid_t tid, int cluster, int cluster_sz,
-                                                 int ignore_rm)
+int be_migrate_thread_to_domain(pid_t tid, int domain)
 {
-        int first_cpu = cluster * cluster_sz; /* first CPU in cluster */
-        int last_cpu = first_cpu + cluster_sz - 1;
-        int master;
-        int num_cpus;
+        int     ret, num_cpus;
         cpu_set_t *cpu_set;
         size_t sz;
-        int i;
-        int ret;
-
-        /* TODO: Error check to make sure that tid is not a real-time task. */
+        unsigned long long int mask;
 
-        if (cluster_sz == 1) {
-                /* we're partitioned */
-                return be_migrate_thread_to_partition(tid, cluster);
-        }
+        ret = domain_to_cpus(domain, &mask);
+        if (ret != 0)
+                return ret;
 
-        master = (ignore_rm) ? -1 : release_master();
         num_cpus = num_online_cpus();
-
-        if (num_cpus == -1 || last_cpu >= num_cpus || first_cpu < 0)
+        if (num_cpus == -1)
                 return -1;
 
         cpu_set = CPU_ALLOC(num_cpus);
         sz = CPU_ALLOC_SIZE(num_cpus);
         CPU_ZERO_S(sz, cpu_set);
 
-        for (i = first_cpu; i <= last_cpu; ++i) {
-                if (i != master) {
-                        CPU_SET_S(i, sz, cpu_set);
-                }
+        while(mask) {
+                int idx = ffsll(mask) - 1;
+                CPU_SET_S(idx, sz, cpu_set);
+                mask &= ~(1ull<<idx);
         }
 
         /* apply to caller */
@@ -140,23 +142,30 @@ int __be_migrate_thread_to_cluster(pid_t tid, int cluster, int cluster_sz,
         return ret;
 }
 
-int be_migrate_thread_to_partition(pid_t tid, int partition)
+int be_migrate_to_cpu(int target_cpu)
+{
+        return be_migrate_thread_to_cpu(0, target_cpu);
+}
+
+int be_migrate_to_domain(int domain)
 {
-        return be_migrate_thread_to_cpu(tid, partition_to_cpu(partition));
+        return be_migrate_thread_to_domain(0, domain);
 }
 
 
-int be_migrate_to_cpu(int target_cpu)
+/* deprecated functions. */
+
+int be_migrate_to_cluster(int cluster, int cluster_size)
 {
-        return be_migrate_thread_to_cpu(0, target_cpu);
+        return be_migrate_to_domain(cluster);
 }
 
-int be_migrate_to_cluster(int cluster, int cluster_sz)
+int cluster_to_first_cpu(int cluster, int cluster_size)
 {
-        return be_migrate_thread_to_cluster(0, cluster, cluster_sz);
+        return domain_to_first_cpu(cluster);
 }
 
-int be_migrate_to_partition(int partition)
+int partition_to_cpu(int partition)
 {
-        return be_migrate_thread_to_partition(0, partition);
+        return domain_to_first_cpu(partition);
 }
diff --git a/src/task.c b/src/task.c
index 5f2fa26..35bad66 100644
--- a/src/task.c
+++ b/src/task.c
@@ -40,11 +40,11 @@ int __launch_rt_task(rt_fn_t rt_prog, void *rt_arg, rt_setup_fn_t setup,
         return rt_task;
 }
 
-int __create_rt_task(rt_fn_t rt_prog, void *arg, int cluster, int cluster_size,
+int __create_rt_task(rt_fn_t rt_prog, void *arg, int cluster,
                 lt_t wcet, lt_t period, unsigned int priority, task_class_t class)
 {
         struct rt_task params;
-        params.cpu       = cluster_to_first_cpu(cluster, cluster_size);
+        params.cpu       = domain_to_first_cpu(cluster);
         params.period    = period;
         params.exec_cost = wcet;
         params.cls       = class;
@@ -57,10 +57,10 @@ int __create_rt_task(rt_fn_t rt_prog, void *arg, int cluster, int cluster_size,
                                 (rt_setup_fn_t) set_rt_task_param, &params);
 }
 
-int create_rt_task(rt_fn_t rt_prog, void *arg, int cluster, int cluster_size,
+int create_rt_task(rt_fn_t rt_prog, void *arg, int cluster,
                 lt_t wcet, lt_t period, unsigned int prio)
 {
-        return __create_rt_task(rt_prog, arg, cluster, cluster_size, wcet, period,
+        return __create_rt_task(rt_prog, arg, cluster, wcet, period,
                                 prio, RT_CLASS_HARD);
 }