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]

7 files changed, 119 insertions, 120 deletions

diff --git a/bin/rt_launch.c b/bin/rt_launch.c
index 93f10d5..5e29893 100644
--- a/bin/rt_launch.c
+++ b/bin/rt_launch.c
@@ -42,7 +42,7 @@ void usage(char *error) {
 }
 
 
-#define OPTSTR "p:z:c:vwq:"
+#define OPTSTR "p:c:vwq:"
 
 int main(int argc, char** argv) 
 {
@@ -51,7 +51,6 @@ int main(int argc, char** argv)
         lt_t period;
         int migrate = 0;
         int cluster = 0;
-        int cluster_size = 1;
         int opt;
         int verbose = 0;
         int wait = 0;
@@ -71,9 +70,6 @@ int main(int argc, char** argv)
                         cluster = atoi(optarg);
                         migrate = 1;
                         break;
-                case 'z':
-                        cluster_size = atoi(optarg);
-                        break;
                 case 'q':
                         priority = atoi(optarg);
                         if (!litmus_is_valid_fixed_prio(priority))
@@ -114,11 +110,11 @@ int main(int argc, char** argv)
         info.argv      = argv + optind + 2;
         info.wait      = wait;
         if (migrate) {
-                ret = be_migrate_to_cluster(cluster, cluster_size);
+                ret = be_migrate_to_domain(cluster);
                 if (ret < 0)
                         bail_out("could not migrate to target partition or cluster");
         }
-        ret = __create_rt_task(launch, &info, cluster, cluster_size, wcet, period,
+        ret = __create_rt_task(launch, &info, cluster, wcet, period,
                                 priority, class);
 
 
diff --git a/bin/rtspin.c b/bin/rtspin.c
index 167741d..b4156cc 100644
--- a/bin/rtspin.c
+++ b/bin/rtspin.c
@@ -184,7 +184,7 @@ static int job(double exec_time, double program_end, int lock_od, double cs_leng
         }
 }
 
-#define OPTSTR "p:z:c:wlveo:f:s:q:X:L:Q:"
+#define OPTSTR "p:c:wlveo:f:s:q:X:L:Q:"
 int main(int argc, char** argv)
 {
         int ret;
@@ -194,7 +194,6 @@ int main(int argc, char** argv)
         unsigned int priority = LITMUS_LOWEST_PRIORITY;
         int migrate = 0;
         int cluster = 0;
-        int cluster_size = 1;
         int opt;
         int wait = 0;
         int test_loop = 0;
@@ -226,9 +225,6 @@ int main(int argc, char** argv)
                         cluster = atoi(optarg);
                         migrate = 1;
                         break;
-                case 'z':
-                        cluster_size = atoi(optarg);
-                        break;
                 case 'q':
                         priority = atoi(optarg);
                         if (!litmus_is_valid_fixed_prio(priority))
@@ -326,7 +322,7 @@ int main(int argc, char** argv)
                 duration += period_ms * 0.001 * (num_jobs - 1);
 
         if (migrate) {
-                ret = be_migrate_to_cluster(cluster, cluster_size);
+                ret = be_migrate_to_domain(cluster);
                 if (ret < 0)
                         bail_out("could not migrate to target partition or cluster.");
         }
@@ -339,7 +335,7 @@ int main(int argc, char** argv)
         param.budget_policy = (want_enforcement) ?
                         PRECISE_ENFORCEMENT : NO_ENFORCEMENT;
         if (migrate)
-                param.cpu = cluster_to_first_cpu(cluster, cluster_size);
+                param.cpu = domain_to_first_cpu(cluster);
         ret = set_rt_task_param(gettid(), &param);
         if (ret < 0)
                 bail_out("could not setup rt task params");
diff --git a/include/litmus.h b/include/litmus.h
index 5a79b7d..5a5461f 100644
--- a/include/litmus.h
+++ b/include/litmus.h
@@ -51,6 +51,7 @@ extern "C" {
  * @param param Pointer to the struct to initialise
  */
 void init_rt_task_param(struct rt_task* param);
+
 /**
  * Set real-time task parameters for given process
  * @param pid PID of process
@@ -58,6 +59,7 @@ void init_rt_task_param(struct rt_task* param);
  * @return 0 on success
  */
 int set_rt_task_param(pid_t pid, struct rt_task* param);
+
 /**
  * Get real-time task parameters for given process
  * @param pid PID of process
@@ -74,20 +76,26 @@ int get_rt_task_param(pid_t pid, struct rt_task* param);
  *  Release-master-aware functions for getting the first
  * CPU in a particular cluster or partition. Use these
  * to set rt_task::cpu for cluster/partitioned scheduling.
+ *
+ * \deprecated{Use domain_to_first_cpu() in new code.}
  */
 int partition_to_cpu(int partition);
+
 /**
  * For given cluster, return the identifier for the first associated CPU
  * @param cluster Identifier of the cluster
  * @param cluster_size Size for this cluster
  * @return Identifier for the first associated CPU
+ *
+ * \deprecated{Use domain_to_first_cpu() in new code.}
  */
 int cluster_to_first_cpu(int cluster, int cluster_size);
 
-/* Convenience functions for setting up real-time tasks.
- * Default behaviors set by init_rt_task_params() used.
- * Also sets affinity masks for clustered/partitions
- * functions. Time units in nanoseconds. */
+
+/* The following three functions are convenience functions for setting up
+ * real-time tasks.  Default behaviors set by init_rt_task_params() are used.
+ * Also sets affinity masks for clustered/partitions functions. Time units in
+ * nanoseconds. */
 /**
  * Set up a sporadic task with global scheduling
  * @param e_ns Execution time in nanoseconds
@@ -95,6 +103,7 @@ int cluster_to_first_cpu(int cluster, int cluster_size);
  * @return 0 on success
  */
 int sporadic_global(lt_t e_ns, lt_t p_ns);
+
 /**
  * Set up a sporadic task with partitioned scheduling
  * @param e_ns Execution time in nanoseconds
@@ -103,15 +112,15 @@ int sporadic_global(lt_t e_ns, lt_t p_ns);
  * @return 0 on success
  */
 int sporadic_partitioned(lt_t e_ns, lt_t p_ns, int partition);
+
 /**
  * Set up a sporadic task with clustered scheduling
  * @param e_ns Execution time in nanoseconds
  * @param p_ns Period in nanoseconds
  * @param cluster Cluster to add this task to
- * @param cluster_size Size of the cluster
  * @return 0 on success
  */
-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);
 
 /* simple time unit conversion macros */
 /** Convert seconds to nanoseconds
@@ -250,29 +259,25 @@ typedef int (*rt_fn_t)(void*);
  * @param arg Pointer to arguments to pass to the pointer in rt_prog
  * @param cluster Cluster to schedule this task on. For partitioned scheduling,
  * set to the desired partition. For global scheduling, set to 0
- * @param cluster_size Size of the cluster. For partitioned scheduling, set to
- * 1, for global scheduling set to 0.
  * @param wcet Worst-Case execution time for this task
  * @param period Period at which this task should be launched
  * @param prio Priority for this task
  */
-int create_rt_task(rt_fn_t rt_prog, void *arg, int cluster, int cluster_size,
-                        lt_t wcet, lt_t period, unsigned int prio);
+int create_rt_task(rt_fn_t rt_prog, void *arg, int cluster,
+                   lt_t wcet, lt_t period, unsigned int prio);
 /**
  * Create a real-time task
  * @param rt_prog Function pointer to real-time task body
  * @param arg Pointer to arguments to pass to the pointer in rt_prog
  * @param cluster Cluster to schedule this task on. For partitioned scheduling,
  * set to the desired partition. For global scheduling, set to 0
- * @param cluster_size Size of the cluster. For partitioned scheduling, set to
- * 1, for global scheduling set to 0.
  * @param wcet Worst-Case execution time for this task
  * @param period Period at which this task should be launched
  * @param prio Priority for this task
- * @param cls Task class (???)
+ * @param cls Task class (unused)
  */
-int __create_rt_task(rt_fn_t rt_prog, void *arg, int cluster, int cluster_size,
-                        lt_t wcet, lt_t period, unsigned int prio, task_class_t cls);
+int __create_rt_task(rt_fn_t rt_prog, void *arg, int cluster,
+                     lt_t wcet, lt_t period, unsigned int prio, task_class_t cls);
 
 /*      per-task modes */
 enum rt_task_mode_t {
diff --git a/include/migration.h b/include/migration.h
index 32d933b..f60dfe9 100644
--- a/include/migration.h
+++ b/include/migration.h
@@ -19,62 +19,55 @@ pid_t gettid();
  * @return 0 if successful
  */
 int be_migrate_thread_to_cpu(pid_t tid, int target_cpu);
-/**
- * Migrate and assign a task to a given partition
- * @param tid Process ID for migrated task, 0 for current task
- * @param partition Partition ID to migrate the task to
- * @pre tid is not yet in real-time mode (it's a best effort task)
- * @return 0 if successful
- */
-int be_migrate_thread_to_partition(pid_t tid, int partition);
+
 /**
  * Migrate current task to a given cluster
  * @param tid Process ID for migrated task, 0 for current task
- * @param cluster Cluster ID to migrate the task to
- * @param cluster_sz Size of the cluster to migrate to
+ * @param domain Cluster ID to migrate the task to
  * @pre tid is not yet in real-time mode (it's a best effort task)
  * @return 0 if successful
- *
- * If using release master, set cluster_sz to size of largest cluster. tid
- * will not be scheduled on release master
- */
-int be_migrate_thread_to_cluster(pid_t tid, int cluster, int cluster_sz);
-
-/**
- * @private
- * set ignore_rm == 1 to include release master in tid's cpu affinity
  */
-int __be_migrate_thread_to_cluster(pid_t tid, int cluster, int cluster_sz, int ignore_rm);
+int be_migrate_thread_to_cluster(pid_t tid, int domain);
 
 /**
  * Migrate current task to a given CPU
  * @param target_cpu ID for CPU to migrate to
- * @pre tid is not yet in real-time mode (it's a best effort task)
+ * @pre The current task is not yet in real-time mode (it's a best-effort task)
  * @return 0 if successful
  */
 int be_migrate_to_cpu(int target_cpu);
-/**
- * Migrate current task to a given partition
- * @param partition Partition ID to migrate the task to
- * @pre tid is not yet in real-time mode (it's a best effort task)
- * @return 0 if successful
- */
-int be_migrate_to_partition(int partition);
+
 /**
  * Migrate current task to a given cluster
  * @param cluster Cluster ID to migrate the task to
- * @param cluster_sz Size of the cluster to migrate to
- * @pre tid is not yet in real-time mode (it's a best effort task)
+ * @param cluster_sz Size of the cluster to migrate to (unused)
+ * @pre The current task is not yet in real-time mode (it's a best-effort task)
  * @return 0 if successful
+ *
+ * \deprecated{Use be_migrate_to_domain() instead in new code.}
  */
 int be_migrate_to_cluster(int cluster, int cluster_sz);
 
 /**
+ * Migrate current task to a given scheduling domain (i.e., cluster or
+ * partition).
+ * @param domain The cluster/partition to migrate to.
+ * @pre The current task is not yet in real-time mode (it's a best-effort task).
+ * @return 0 if successful
+ */
+int be_migrate_to_domain(int domain);
+
+/**
  * Return the number of CPUs currently online
  * @return The number of online CPUs
  */
 int num_online_cpus();
+
 /**
  * @todo Document!
  */
 int release_master();
+int domain_to_cpus(int domain, unsigned long long int* mask);
+int cpu_to_domains(int cpu, unsigned long long int* mask);
+
+int domain_to_first_cpu(int domain);
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);
 }