Move MPPC++: Break out the MPCP code into own file

Part of refactoring sharedres.cpp.

2 files changed, 323 insertions, 319 deletions

diff --git a/native/src/blocking/mpcp.cpp b/native/src/blocking/mpcp.cpp
new file mode 100644
index 0000000..8b87556
--- /dev/null
+++ b/native/src/blocking/mpcp.cpp
@@ -0,0 +1,320 @@
+#include "sharedres.h"
+#include "blocking.h"
+
+#include "stl-helper.h"
+#include "math-helper.h"
+
+// ***************************  MPCP ******************************************
+
+
+typedef std::vector<unsigned int> PriorityCeilings;
+
+static void determine_priority_ceilings(const Resources& resources,
+                                        PriorityCeilings& ceilings)
+{
+        ceilings.reserve(resources.size());
+
+        foreach(resources, it)
+        {
+                unsigned int ceiling = UINT_MAX;
+                const ContentionSet& cs = *it;
+
+                foreach(cs, jt)
+                {
+                        const RequestBound* req = *jt;
+                        ceiling = std::min(ceiling, req->get_task()->get_priority());
+                }
+
+                ceilings.push_back(ceiling);
+        }
+}
+
+typedef std::vector<unsigned long> ResponseTimes;
+typedef std::vector<ResponseTimes> TaskResponseTimes;
+typedef std::vector<TaskResponseTimes> ClusterResponseTimes;
+
+static unsigned long get_max_gcs_length(const TaskInfo* tsk,
+                                        const PriorityCeilings& ceilings,
+                                        unsigned int preempted_ceiling)
+{
+        unsigned long gcs_length = 0;
+
+        foreach(tsk->get_requests(), it)
+        {
+                unsigned int prio  = ceilings[it->get_resource_id()];
+                if (prio < preempted_ceiling)
+                        gcs_length = std::max(gcs_length,
+                                              (unsigned long) it->get_request_length());
+        }
+
+        return gcs_length;
+}
+
+static void determine_gcs_response_times(const TaskInfo* tsk,
+                                         const Cluster& cluster,
+                                         const PriorityCeilings& ceilings,
+                                         ResponseTimes& times)
+{
+        times.reserve(tsk->get_requests().size());
+
+        foreach(tsk->get_requests(), it)
+        {
+                unsigned long resp = it->get_request_length();
+                unsigned int prio  = ceilings[it->get_resource_id()];
+
+                // Equation (2) in LNR:09.
+                // One request of each local gcs that can preempt our ceiling,
+                // but at most one per task (since tasks are sequential).
+
+                foreach(cluster, jt)
+                {
+                        const TaskInfo* t = *jt;
+
+                        if (t != tsk)
+                                resp += get_max_gcs_length(t, ceilings, prio);
+                }
+
+                times.push_back(resp);
+        }
+}
+
+static void determine_gcs_response_times(const Cluster& cluster,
+                                         const PriorityCeilings& ceilings,
+                                         TaskResponseTimes& times)
+{
+        times.reserve(cluster.size());
+        foreach(cluster, it)
+        {
+                times.push_back(ResponseTimes());
+                determine_gcs_response_times(*it, cluster, ceilings,
+                                             times.back());
+        }
+}
+
+static void determine_gcs_response_times(const Clusters& clusters,
+                                         const PriorityCeilings& ceilings,
+                                         ClusterResponseTimes& times)
+{
+        times.reserve(clusters.size());
+        foreach(clusters, it)
+        {
+                times.push_back(TaskResponseTimes());
+                determine_gcs_response_times(*it, ceilings, times.back());
+        }
+}
+
+static unsigned long response_time_for(unsigned int res_id,
+                                       unsigned long interval,
+                                       const TaskInfo* tsk,
+                                       const ResponseTimes& resp,
+                                       bool multiple)
+{
+        const Requests& requests = tsk->get_requests();
+        unsigned int i = 0;
+
+        for (i = 0; i < requests.size(); i++)
+                if (requests[i].get_resource_id() == res_id)
+                {
+                        if (multiple)
+                        {
+                                // Equation (3) in LNR:09.
+                                // How many jobs?
+                                unsigned long num_jobs;
+                                num_jobs  = divide_with_ceil(interval, tsk->get_period());
+                                num_jobs += 1;
+
+                                // Note: this may represent multiple gcs, so multiply.
+                                return num_jobs * resp[i] * requests[i].get_num_requests();
+                        }
+                        else
+                                // Just one request.
+                                return resp[i];
+                }
+        // if we get here, then the task does not access res_id
+        return 0;
+}
+
+static unsigned long  mpcp_remote_blocking(unsigned int res_id,
+                                           unsigned long interval,
+                                           const TaskInfo* tsk,
+                                           const Cluster& cluster,
+                                           const TaskResponseTimes times,
+                                           unsigned long& max_lower)
+{
+        unsigned int i;
+        unsigned long blocking = 0;
+
+        // consider each task in cluster
+        for (i = 0; i < cluster.size(); i++)
+        {
+                const TaskInfo* t = cluster[i];
+                if (t != tsk)
+                {
+                        if (t->get_priority() < tsk->get_priority())
+                                // This is a higher-priority task;
+                                // it can block multiple times.
+                                blocking += response_time_for(res_id, interval,
+                                                              t, times[i], true);
+                        else
+                                // This is a lower-priority task;
+                                // it can block only once.
+                                max_lower = std::max(max_lower,
+                                                     response_time_for(res_id, interval,
+                                                                       t, times[i], false));
+                }
+        }
+
+        return blocking;
+}
+
+static unsigned long  mpcp_remote_blocking(unsigned int res_id,
+                                           unsigned long interval,
+                                           const TaskInfo* tsk,
+                                           const Clusters& clusters,
+                                           const ClusterResponseTimes times,
+                                           unsigned long& max_lower)
+{
+        unsigned int i;
+        unsigned long blocking;
+
+        max_lower = 0;
+        blocking  = 0;
+
+        for (i = 0; i < clusters.size(); i++)
+        {
+                blocking += mpcp_remote_blocking(res_id, interval,
+                                                 tsk, clusters[i], times[i],
+                                                 max_lower);
+        }
+        return blocking;
+}
+
+static unsigned long mpcp_remote_blocking(unsigned int res_id,
+                                          const TaskInfo* tsk,
+                                          const Clusters& clusters,
+                                          const ClusterResponseTimes times)
+{
+        unsigned long interval;
+        unsigned long blocking = 1;
+        unsigned long max_lower;
+
+        do
+        {
+                // last bound
+                interval = blocking;
+                // Bail out if it doesn't converge.
+                if (interval > tsk->get_response())
+                        return UNLIMITED;
+
+                blocking = mpcp_remote_blocking(res_id, interval,
+                                                tsk, clusters, times,
+                                                max_lower);
+
+                // Account for the maximum lower-priority gcs
+                // that could get in the way.
+                blocking += max_lower;
+
+                // Loop until it converges.
+        } while ( interval != blocking );
+
+        return blocking;
+}
+
+static unsigned long mpcp_remote_blocking(const TaskInfo* tsk,
+                                          const Clusters& clusters,
+                                          const ClusterResponseTimes times)
+{
+        unsigned long blocking = 0;
+
+
+        const Requests& requests = tsk->get_requests();
+        unsigned int i = 0;
+
+        for (i = 0; i < requests.size(); i++)
+        {
+                unsigned int b;
+                b = mpcp_remote_blocking(requests[i].get_resource_id(),
+                                         tsk, clusters, times);
+                if (b != UNLIMITED)
+                        // may represent multiple, multiply accordingly
+                        blocking += b * requests[i].get_num_requests();
+                else
+                        // bail out if it didn't converge
+                        return b;
+        }
+
+        return blocking;
+}
+
+static unsigned long mpcp_arrival_blocking(const TaskInfo* tsk,
+                                           const Cluster& cluster,
+                                           bool virtual_spinning)
+{
+        unsigned int prio = tsk->get_priority();
+        unsigned int blocking = 0;
+        unsigned int i;
+
+        for (i = 0; i < cluster.size(); i++)
+                if (cluster[i] != tsk && cluster[i]->get_priority() >= prio)
+                        blocking += cluster[i]->get_max_request_length();
+
+        if (virtual_spinning)
+                // Equation (4) in LNR:09.
+                return blocking;
+        else
+                // Equation (1) in LNR:09.
+                return blocking * tsk->get_num_arrivals();
+}
+
+BlockingBounds* mpcp_bounds(const ResourceSharingInfo& info,
+                            bool use_virtual_spinning)
+{
+        Resources resources;
+        Clusters clusters;
+
+        split_by_resource(info, resources);
+        split_by_cluster(info, clusters);
+
+        // 2) Determine priority ceiling for each request.
+        PriorityCeilings gc;
+        determine_priority_ceilings(resources, gc);
+
+
+        // 3) For each request, determine response time. This only depends on the
+        //    priority ceiling for each request.
+        ClusterResponseTimes responses;
+        determine_gcs_response_times(clusters, gc, responses);
+
+        unsigned int i;
+
+        BlockingBounds* _results = new BlockingBounds(info);
+        BlockingBounds& results = *_results;
+
+        for (i = 0; i < info.get_tasks().size(); i++)
+        {
+                const TaskInfo& tsk  = info.get_tasks()[i];
+
+                unsigned long remote, local = 0;
+
+                // 4) Determine remote blocking for each request. This depends on the
+                //    response times for each remote request.
+                remote = mpcp_remote_blocking(&tsk, clusters, responses);
+
+                // 5) Determine arrival blocking for each task.
+                if (remote != UNLIMITED)
+                        local = mpcp_arrival_blocking(&tsk, clusters[tsk.get_cluster()],
+                                                      use_virtual_spinning);
+
+                // 6) Sum up blocking: remote blocking + arrival blocking.
+                results[i].total_length = remote + local;
+
+
+                Interference inf;
+                inf.total_length = remote;
+                results.set_remote_blocking(i, inf);
+        }
+
+        return _results;
+}
+
+
diff --git a/native/src/sharedres.cpp b/native/src/sharedres.cpp
index 935d20f..a3b4ed9 100644
--- a/native/src/sharedres.cpp
+++ b/native/src/sharedres.cpp
@@ -22,7 +22,7 @@
 
 #include "blocking.h"
 
-static const unsigned int UNLIMITED = UINT_MAX;
+const unsigned int UNLIMITED = UINT_MAX;
 
 std::ostream& operator<<(std::ostream &os, const TaskInfo  &ti)
 {
@@ -78,10 +78,8 @@ unsigned int RequestBound::get_max_num_requests(unsigned long interval) const
 
 // ****** non-exported helpers *******
 
-typedef std::vector<const TaskInfo*> Cluster;
-typedef std::vector<Cluster> Clusters;
 
-static void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters)
+void split_by_cluster(const ResourceSharingInfo& info, Clusters& clusters)
 {
         foreach(info.get_tasks(), it)
         {
@@ -111,7 +109,7 @@ void sort_by_priority(Clusters& clusters)
 }
 
 
-static void split_by_resource(const ResourceSharingInfo& info, Resources& resources)
+void split_by_resource(const ResourceSharingInfo& info, Resources& resources)
 {
         foreach(info.get_tasks(), it)
         {
@@ -1720,317 +1718,3 @@ BlockingBounds* part_fmlp_bounds(const ResourceSharingInfo& info, bool preemptiv
         return _results;
 }
 
-// ***************************  MPCP ******************************************
-
-
-typedef std::vector<unsigned int> PriorityCeilings;
-
-static void determine_priority_ceilings(const Resources& resources,
-                                        PriorityCeilings& ceilings)
-{
-        ceilings.reserve(resources.size());
-
-        foreach(resources, it)
-        {
-                unsigned int ceiling = UINT_MAX;
-                const ContentionSet& cs = *it;
-
-                foreach(cs, jt)
-                {
-                        const RequestBound* req = *jt;
-                        ceiling = std::min(ceiling, req->get_task()->get_priority());
-                }
-
-                ceilings.push_back(ceiling);
-        }
-}
-
-typedef std::vector<unsigned long> ResponseTimes;
-typedef std::vector<ResponseTimes> TaskResponseTimes;
-typedef std::vector<TaskResponseTimes> ClusterResponseTimes;
-
-static unsigned long get_max_gcs_length(const TaskInfo* tsk,
-                                        const PriorityCeilings& ceilings,
-                                        unsigned int preempted_ceiling)
-{
-        unsigned long gcs_length = 0;
-
-        foreach(tsk->get_requests(), it)
-        {
-                unsigned int prio  = ceilings[it->get_resource_id()];
-                if (prio < preempted_ceiling)
-                        gcs_length = std::max(gcs_length,
-                                              (unsigned long) it->get_request_length());
-        }
-
-        return gcs_length;
-}
-
-static void determine_gcs_response_times(const TaskInfo* tsk,
-                                         const Cluster& cluster,
-                                         const PriorityCeilings& ceilings,
-                                         ResponseTimes& times)
-{
-        times.reserve(tsk->get_requests().size());
-
-        foreach(tsk->get_requests(), it)
-        {
-                unsigned long resp = it->get_request_length();
-                unsigned int prio  = ceilings[it->get_resource_id()];
-
-                // Equation (2) in LNR:09.
-                // One request of each local gcs that can preempt our ceiling,
-                // but at most one per task (since tasks are sequential).
-
-                foreach(cluster, jt)
-                {
-                        const TaskInfo* t = *jt;
-
-                        if (t != tsk)
-                                resp += get_max_gcs_length(t, ceilings, prio);
-                }
-
-                times.push_back(resp);
-        }
-}
-
-static void determine_gcs_response_times(const Cluster& cluster,
-                                         const PriorityCeilings& ceilings,
-                                         TaskResponseTimes& times)
-{
-        times.reserve(cluster.size());
-        foreach(cluster, it)
-        {
-                times.push_back(ResponseTimes());
-                determine_gcs_response_times(*it, cluster, ceilings,
-                                             times.back());
-        }
-}
-
-static void determine_gcs_response_times(const Clusters& clusters,
-                                         const PriorityCeilings& ceilings,
-                                         ClusterResponseTimes& times)
-{
-        times.reserve(clusters.size());
-        foreach(clusters, it)
-        {
-                times.push_back(TaskResponseTimes());
-                determine_gcs_response_times(*it, ceilings, times.back());
-        }
-}
-
-static unsigned long response_time_for(unsigned int res_id,
-                                       unsigned long interval,
-                                       const TaskInfo* tsk,
-                                       const ResponseTimes& resp,
-                                       bool multiple)
-{
-        const Requests& requests = tsk->get_requests();
-        unsigned int i = 0;
-
-        for (i = 0; i < requests.size(); i++)
-                if (requests[i].get_resource_id() == res_id)
-                {
-                        if (multiple)
-                        {
-                                // Equation (3) in LNR:09.
-                                // How many jobs?
-                                unsigned long num_jobs;
-                                num_jobs  = divide_with_ceil(interval, tsk->get_period());
-                                num_jobs += 1;
-
-                                // Note: this may represent multiple gcs, so multiply.
-                                return num_jobs * resp[i] * requests[i].get_num_requests();
-                        }
-                        else
-                                // Just one request.
-                                return resp[i];
-                }
-        // if we get here, then the task does not access res_id
-        return 0;
-}
-
-static unsigned long  mpcp_remote_blocking(unsigned int res_id,
-                                           unsigned long interval,
-                                           const TaskInfo* tsk,
-                                           const Cluster& cluster,
-                                           const TaskResponseTimes times,
-                                           unsigned long& max_lower)
-{
-        unsigned int i;
-        unsigned long blocking = 0;
-
-        // consider each task in cluster
-        for (i = 0; i < cluster.size(); i++)
-        {
-                const TaskInfo* t = cluster[i];
-                if (t != tsk)
-                {
-                        if (t->get_priority() < tsk->get_priority())
-                                // This is a higher-priority task;
-                                // it can block multiple times.
-                                blocking += response_time_for(res_id, interval,
-                                                              t, times[i], true);
-                        else
-                                // This is a lower-priority task;
-                                // it can block only once.
-                                max_lower = std::max(max_lower,
-                                                     response_time_for(res_id, interval,
-                                                                       t, times[i], false));
-                }
-        }
-
-        return blocking;
-}
-
-static unsigned long  mpcp_remote_blocking(unsigned int res_id,
-                                           unsigned long interval,
-                                           const TaskInfo* tsk,
-                                           const Clusters& clusters,
-                                           const ClusterResponseTimes times,
-                                           unsigned long& max_lower)
-{
-        unsigned int i;
-        unsigned long blocking;
-
-        max_lower = 0;
-        blocking  = 0;
-
-        for (i = 0; i < clusters.size(); i++)
-        {
-                blocking += mpcp_remote_blocking(res_id, interval,
-                                                 tsk, clusters[i], times[i],
-                                                 max_lower);
-        }
-        return blocking;
-}
-
-static unsigned long mpcp_remote_blocking(unsigned int res_id,
-                                          const TaskInfo* tsk,
-                                          const Clusters& clusters,
-                                          const ClusterResponseTimes times)
-{
-        unsigned long interval;
-        unsigned long blocking = 1;
-        unsigned long max_lower;
-
-        do
-        {
-                // last bound
-                interval = blocking;
-                // Bail out if it doesn't converge.
-                if (interval > tsk->get_response())
-                        return UNLIMITED;
-
-                blocking = mpcp_remote_blocking(res_id, interval,
-                                                tsk, clusters, times,
-                                                max_lower);
-
-                // Account for the maximum lower-priority gcs
-                // that could get in the way.
-                blocking += max_lower;
-
-                // Loop until it converges.
-        } while ( interval != blocking );
-
-        return blocking;
-}
-
-static unsigned long mpcp_remote_blocking(const TaskInfo* tsk,
-                                          const Clusters& clusters,
-                                          const ClusterResponseTimes times)
-{
-        unsigned long blocking = 0;
-
-
-        const Requests& requests = tsk->get_requests();
-        unsigned int i = 0;
-
-        for (i = 0; i < requests.size(); i++)
-        {
-                unsigned int b;
-                b = mpcp_remote_blocking(requests[i].get_resource_id(),
-                                         tsk, clusters, times);
-                if (b != UNLIMITED)
-                        // may represent multiple, multiply accordingly
-                        blocking += b * requests[i].get_num_requests();
-                else
-                        // bail out if it didn't converge
-                        return b;
-        }
-
-        return blocking;
-}
-
-static unsigned long mpcp_arrival_blocking(const TaskInfo* tsk,
-                                           const Cluster& cluster,
-                                           bool virtual_spinning)
-{
-        unsigned int prio = tsk->get_priority();
-        unsigned int blocking = 0;
-        unsigned int i;
-
-        for (i = 0; i < cluster.size(); i++)
-                if (cluster[i] != tsk && cluster[i]->get_priority() >= prio)
-                        blocking += cluster[i]->get_max_request_length();
-
-        if (virtual_spinning)
-                // Equation (4) in LNR:09.
-                return blocking;
-        else
-                // Equation (1) in LNR:09.
-                return blocking * tsk->get_num_arrivals();
-}
-
-BlockingBounds* mpcp_bounds(const ResourceSharingInfo& info,
-                            bool use_virtual_spinning)
-{
-        Resources resources;
-        Clusters clusters;
-
-        split_by_resource(info, resources);
-        split_by_cluster(info, clusters);
-
-        // 2) Determine priority ceiling for each request.
-        PriorityCeilings gc;
-        determine_priority_ceilings(resources, gc);
-
-
-        // 3) For each request, determine response time. This only depends on the
-        //    priority ceiling for each request.
-        ClusterResponseTimes responses;
-        determine_gcs_response_times(clusters, gc, responses);
-
-        unsigned int i;
-
-        BlockingBounds* _results = new BlockingBounds(info);
-        BlockingBounds& results = *_results;
-
-        for (i = 0; i < info.get_tasks().size(); i++)
-        {
-                const TaskInfo& tsk  = info.get_tasks()[i];
-
-                unsigned long remote, local = 0;
-
-                // 4) Determine remote blocking for each request. This depends on the
-                //    response times for each remote request.
-                remote = mpcp_remote_blocking(&tsk, clusters, responses);
-
-                // 5) Determine arrival blocking for each task.
-                if (remote != UNLIMITED)
-                        local = mpcp_arrival_blocking(&tsk, clusters[tsk.get_cluster()],
-                                                      use_virtual_spinning);
-
-                // 6) Sum up blocking: remote blocking + arrival blocking.
-                results[i].total_length = remote + local;
-
-
-                Interference inf;
-                inf.total_length = remote;
-                results.set_remote_blocking(i, inf);
-        }
-
-        return _results;
-}
-
-