Add holistic MSRP analysis (with PCP/SRP for local resources)

This patch adds holistic analysis of the MSRP, which combines the PCP/SRP
for local resources and task-fair mutex spin locks for global resources.

This is added as its own analysis (rather than patching the task-fair mutex
code directly) because
- the MSRP only applies to partitioned scheduling, and
- to not break existing code that does not expect special treatment of local resources.

Simple tests included. Adds some convenience code to Interference and BlockingBounds.

7 files changed, 152 insertions, 0 deletions

diff --git a/native/Makefile b/native/Makefile
index 54c75d8..965f049 100644
--- a/native/Makefile
+++ b/native/Makefile
@@ -111,6 +111,7 @@ SYNC_OBJ  = sharedres.o dpcp.o mpcp.o
 SYNC_OBJ += fmlp_plus.o  global-fmlp.o
 SYNC_OBJ += global-omlp.o part-omlp.o clust-omlp.o
 SYNC_OBJ += rw-phase-fair.o rw-task-fair.o
+SYNC_OBJ += msrp-holistic.o
 
 # #### Targets ####
 
diff --git a/native/include/blocking.h b/native/include/blocking.h
index a4e48f5..cbb4d15 100644
--- a/native/include/blocking.h
+++ b/native/include/blocking.h
@@ -102,6 +102,9 @@ ResourceSharingInfo extract_local_resources(
 ResourceSharingInfo extract_global_resources(
         const ResourceSharingInfo& info,
         const ResourceSet& locals);
+
+BlockingBounds pcp_blocking(const ResourceSharingInfo& info);
+
 extern const unsigned int UNLIMITED;
 
 #endif
diff --git a/native/include/sharedres.h b/native/include/sharedres.h
index 7765fd8..437176b 100644
--- a/native/include/sharedres.h
+++ b/native/include/sharedres.h
@@ -18,6 +18,10 @@ BlockingBounds* phase_fair_rw_bounds(const ResourceSharingInfo& info,
                                      unsigned int procs_per_cluster,
                                      int dedicated_irq = NO_CPU);
 
+BlockingBounds* msrp_bounds_holistic(
+        const ResourceSharingInfo& info,
+        int dedicated_irq = NO_CPU);
+
 // s-oblivious protocols
 
 BlockingBounds* global_omlp_bounds(const ResourceSharingInfo& info,
diff --git a/native/include/sharedres_types.h b/native/include/sharedres_types.h
index fbe8f72..800659a 100644
--- a/native/include/sharedres_types.h
+++ b/native/include/sharedres_types.h
@@ -240,6 +240,7 @@ struct Interference
         unsigned long total_length;
 
         Interference() : count(0), total_length(0) {}
+        Interference(unsigned int length) : count(1), total_length(length) {}
 
         Interference& operator+=(const Interference& other)
         {
@@ -311,6 +312,12 @@ public:
                 return request_span[idx];
         }
 
+        void raise_blocking_length(unsigned idx, const Interference& val)
+        {
+                assert( idx < size() );
+                blocking[idx] = std::max(blocking[idx], val);
+        }
+
         size_t size() const
         {
                 return blocking.size();
diff --git a/native/interface/locking.i b/native/interface/locking.i
index 208fb74..5f4e75d 100644
--- a/native/interface/locking.i
+++ b/native/interface/locking.i
@@ -7,6 +7,7 @@
 %newobject task_fair_mutex_bounds;
 %newobject task_fair_rw_bounds;
 %newobject phase_fair_rw_bounds;
+%newobject msrp_bounds_holistic;
 
 %newobject global_omlp_bounds;
 %newobject global_fmlp_bounds;
diff --git a/native/src/blocking/msrp-holistic.cpp b/native/src/blocking/msrp-holistic.cpp
new file mode 100644
index 0000000..f9b4185
--- /dev/null
+++ b/native/src/blocking/msrp-holistic.cpp
@@ -0,0 +1,90 @@
+#include "stl-hashmap.h"
+
+#include "sharedres.h"
+#include "blocking.h"
+
+
+// Analysis of the MSRP: PCP/SRP for local resources, task-fair mutex
+// spin locks for global resources
+// Applies only to partitioned scheduling.
+BlockingBounds* msrp_bounds_holistic(
+        const ResourceSharingInfo& info,
+        int dedicated_irq)
+{
+        ResourceSet locals = get_local_resources(info);
+        ResourceSharingInfo linfo = extract_local_resources(info, locals);
+        ResourceSharingInfo ginfo = extract_global_resources(info, locals);
+
+        BlockingBounds pcp = pcp_blocking(linfo);
+
+        BlockingBounds* results = task_fair_mutex_bounds(ginfo, 1, dedicated_irq);
+
+        // merge the two analysis results
+        for (unsigned int i = 0; i < results->size(); i++)
+        {
+                unsigned int b_pcp  = pcp.get_blocking_term(i);
+                unsigned int b_spin = results->get_arrival_blocking(i);
+
+                if (b_pcp > b_spin) {
+                        // need to account for larger local blocking
+                        Interference new_arrival(b_pcp);
+                        Interference total = (*results)[i];
+                        // increase total by difference to spin-only blocking
+                        total.total_length += (b_pcp - b_spin);
+
+                        // update
+                        results->set_arrival_blocking(i, new_arrival);
+                        (*results)[i] = total;
+                }
+        }
+
+        return results;
+}
+
+
+BlockingBounds pcp_blocking(const ResourceSharingInfo& info)
+{
+        PriorityCeilings prio_ceilings = get_priority_ceilings(info);
+
+        // split everything by partition
+        Clusters clusters;
+        split_by_cluster(info, clusters);
+
+        // blocking results
+        BlockingBounds results(info);
+
+        foreach(clusters, ct)
+        {
+                Cluster& cluster = *ct;
+                foreach(cluster, it)
+                {
+                        const TaskInfo* tsk = *it;
+                        unsigned int id     = tsk->get_id();
+                        unsigned int prio   = tsk->get_priority();
+
+                        // check each other task
+                        foreach(cluster, jt)
+                        {
+                                const TaskInfo* other = *jt;
+                                if (id != other->get_id() &&
+                                    prio <= other->get_priority())
+                                {
+                                        // blocking possible
+
+                                        foreach(other->get_requests(), req)
+                                        {
+                                                unsigned int res = req->get_resource_id();
+                                                if (prio_ceilings[res] <= prio) {
+                                                        // this CS could cause ceiling blocking / PI blocking
+                                                        // make sure blocking term is at least this large
+                                                        Interference inf(req->get_request_length());
+                                                        results.raise_blocking_length(id, inf);
+                                                }
+                                        }
+                                }
+                        }
+                }
+        }
+
+        return results;
+}
diff --git a/tests/locking.py b/tests/locking.py
index 2a9766f..1a13a4c 100644
--- a/tests/locking.py
+++ b/tests/locking.py
@@ -204,6 +204,52 @@ class Test_bounds(unittest.TestCase):
         self.assertEqual(7 + 7 + 77, res.get_arrival_blocking(4))
         self.assertEqual(0, res.get_arrival_blocking(5))
 
+
+    def test_arrival_blocking_msrp(self):
+        res = cpp.msrp_bounds_holistic(self.rsi1)
+        self.assertEqual(6 + 7 + 7, res.get_arrival_blocking(0))
+        self.assertEqual(5 + 7 + 7, res.get_arrival_blocking(1))
+        self.assertEqual(0, res.get_arrival_blocking(2))
+        self.assertEqual(0, res.get_arrival_blocking(3))
+        self.assertEqual(7 + 7 + 77, res.get_arrival_blocking(4))
+        self.assertEqual(0, res.get_arrival_blocking(5))
+
+    def test_local_resources_msrp(self):
+        self.rsi1.add_request(99, 100, 123456)
+        res = cpp.msrp_bounds_holistic(self.rsi1)
+        self.assertEqual(7 + 7 + 77, res.get_arrival_blocking(4))
+
+    def test_local_resources_msrp2(self):
+        self.rsi1 = cpp.ResourceSharingInfo(7)
+
+        self.rsi1.add_task(100, 100, 0, 0)
+        self.rsi1.add_request(0, 1, 77)
+
+        self.rsi1.add_task(50, 50, 0, 1)
+        self.rsi1.add_request(0, 1, 6)
+
+        self.rsi1.add_task(10, 10, 0, 2)
+        self.rsi1.add_request(0, 1, 5)
+
+        self.rsi1.add_task(10, 10, 1, 3)
+        self.rsi1.add_request(0, 1, 7)
+
+        self.rsi1.add_task(20, 20, 2, 4)
+        self.rsi1.add_request(0, 4, 1)
+
+        self.rsi1.add_task(30, 30, 2, 5)
+        self.rsi1.add_request(0, 1, 7)
+        self.rsi1.add_request(99, 1, 1)
+
+        self.rsi1.add_task(100, 100, 2, 6)
+        self.rsi1.add_request(99, 100, 123456)
+        res = cpp.msrp_bounds_holistic(self.rsi1)
+        self.assertEqual(7 + 7 + 77, res.get_arrival_blocking(4))
+        self.assertEqual(123456, res.get_arrival_blocking(5))
+        self.assertEqual(123456 + 7 + 77, res.get_blocking_term(5))
+        self.assertEqual(0, res.get_blocking_term(6))
+        self.assertEqual(0, res.get_arrival_blocking(6))
+
     def test_arrival_blocking_pf(self):
         c = 1