Make C++ and Python LP-based blocking bounds available in bounds.py

Use the faster C++ version if available, unless the caller specifically requested
the Python implementation.

4 files changed, 147 insertions, 4 deletions

diff --git a/.gitignore b/.gitignore
index 44c2f4b..d37770f 100644
--- a/.gitignore
+++ b/.gitignore
@@ -23,3 +23,5 @@ schedcat/sim/_sim.so
 schedcat/sim/native.py
 tmp/
 TAGS
+schedcat/locking/linprog/_lp_analysis.so
+schedcat/locking/linprog/native.py
diff --git a/Makefile b/Makefile
index dcaf25d..5a942b0 100644
--- a/Makefile
+++ b/Makefile
@@ -14,11 +14,13 @@ cpp:
 links: clean-links cpp
         cd schedcat/sched; ln -s ../../native/_sched.so; ln -s ../../native/sched.py native.py
         cd schedcat/locking; ln -s ../../native/_locking.so; ln -s ../../native/locking.py native.py
+        cd schedcat/locking/linprog; ln -s ../../../native/_lp_analysis.so; ln -s ../../../native/lp_analysis.py native.py
         cd schedcat/sim; ln -s ../../native/_sim.so; ln -s ../../native/sim.py native.py
 
 clean-links:
         cd schedcat/sched; rm -f _sched.so native.py
         cd schedcat/locking;  rm -f _locking.so native.py
+        cd schedcat/locking/linprog;  rm -f  _lp_analysis.so native.py
         cd schedcat/sim;  rm -f _sim.so native.py;
 
 clean: clean-links
diff --git a/schedcat/locking/bounds.py b/schedcat/locking/bounds.py
index 8e8f708..0b47fb4 100644
--- a/schedcat/locking/bounds.py
+++ b/schedcat/locking/bounds.py
@@ -66,20 +66,26 @@ def apply_mpcp_bounds(all_tasks, use_virtual_spin=False):
 def get_round_robin_resource_mapping(num_resources, num_cpus,
                                      dedicated_irq=cpp.NO_CPU):
     "Default resource assignment: just assign resources to CPUs in index order."
-    loc   = cpp.ResourceLocality()
+    loc   = {}
     for res_id in xrange(num_resources):
         cpu = res_id % num_cpus
         if cpu == dedicated_irq:
             cpu = (cpu + 1) % num_cpus
-        loc.assign_resource(res_id, cpu)
+        loc[res_id] = cpu
     return loc
 
-# default resource assignment: round robin
+def get_cpp_topology(res_mapping):
+    map = cpp.ResourceLocality()
+    for res_id in res_mapping:
+        map.assign_resource(res_id, res_mapping[res_id])
+    return map
+
 def apply_dpcp_bounds(all_tasks, resource_mapping):
     # The DPCP bounds are expressed in terms of task periods,
     # not response time.
     model = get_cpp_model(all_tasks)
-    res = cpp.dpcp_bounds(model, resource_mapping)
+    topo  = get_cpp_topology(resource_mapping)
+    res = cpp.dpcp_bounds(model, topo)
 
     for i,t in enumerate(all_tasks):
         # remote blocking <=> suspension time
@@ -167,3 +173,52 @@ def apply_phase_fair_rw_bounds(all_tasks, procs_per_cluster,
     apply_suspension_oblivious(all_tasks, res)
 
 
+
+### S-aware LP-based analysis of distributed locking protocols
+
+try:
+    import schedcat.locking.linprog.native as lp_cpp
+
+    lp_cpp_available = True
+except ImportError:
+    lp_cpp_available = False
+
+import schedcat.locking.linprog.dflp as dflp
+import schedcat.locking.linprog.dpcp as dpcp
+
+def apply_py_lp_bounds(bounds, all_tasks, resource_mapping, *args):
+    for t in all_tasks:
+        lp = bounds.get_lp_for_task(resource_mapping,
+                                    all_tasks, t, *args)
+
+        lp.kill_non_positive_vars()
+        solution = lp.solve()
+
+        # total blocking
+        t.blocked   = int(solution(lp.objective_function))
+        t.suspended = int(solution(lp.remote_objective))
+
+def apply_lp_dflp_bounds(all_tasks, resource_mapping,
+                         use_py=False):
+    if use_py or not lp_cpp_available:
+        apply_py_lp_bounds(dflp, all_tasks, resource_mapping)
+    else:
+        model = get_cpp_model(all_tasks)
+        topo  = get_cpp_topology(resource_mapping)
+        res = lp_cpp.lp_dflp_bounds(model, topo)
+        for i, t in enumerate(all_tasks):
+            t.suspended = res.get_remote_blocking(i)
+            t.blocked   = res.get_blocking_term(i)
+
+def apply_lp_dpcp_bounds(all_tasks, resource_mapping,
+                         use_rta = True, use_py=False):
+    if use_py or not lp_cpp_available:
+        apply_py_lp_bounds(dpcp, all_tasks, resource_mapping, use_rta)
+    else:
+        model = get_cpp_model(all_tasks)
+        topo  = get_cpp_topology(resource_mapping)
+        res = lp_cpp.lp_dpcp_bounds(model, topo, use_rta)
+        for i, t in enumerate(all_tasks):
+            t.suspended = res.get_remote_blocking(i)
+            t.blocked   = res.get_blocking_term(i)
+
diff --git a/tests/locking.py b/tests/locking.py
index b16c453..94dda3b 100644
--- a/tests/locking.py
+++ b/tests/locking.py
@@ -9,6 +9,8 @@ import schedcat.locking.partition as lp
 import schedcat.model.tasks as tasks
 import schedcat.model.resources as r
 
+import schedcat.util.linprog
+
 class Locking(unittest.TestCase):
     def setUp(self):
         self.ts = tasks.TaskSystem([
@@ -637,3 +639,85 @@ class Test_partition(unittest.TestCase):
         self.assertIn(self.ts[1], subsets[0])
         self.assertIn(self.ts[2], subsets[1])
         self.assertIn(self.ts[3], subsets[1])
+
+
+class Test_linprog(unittest.TestCase):
+    def setUp(self):
+        self.t1 = tasks.SporadicTask(10, 100)
+        self.t2 = tasks.SporadicTask(25, 200)
+        self.t3 = tasks.SporadicTask(33, 33)
+        self.ts = tasks.TaskSystem([self.t1, self.t2, self.t3])
+
+        self.ts.assign_ids()
+        lb.assign_fp_locking_prios(self.ts)
+
+        for t in self.ts:
+            t.response_time = t.period
+            t.partition =  t.id % 2
+
+        self.ts_no_req = self.ts.copy()
+
+        r.initialize_resource_model(self.ts)
+        r.initialize_resource_model(self.ts_no_req)
+
+        self.t1.resmodel[0].add_request(1)
+        self.t2.resmodel[0].add_request(2)
+        self.t3.resmodel[0].add_request(3)
+
+        # only one resource, assigned to the first processor
+        self.resource_locality = { 0: 0 }
+
+    def test_dpcp_cpp(self):
+        lb.apply_lp_dpcp_bounds(self.ts, self.resource_locality, use_py=False)
+
+    @unittest.skipIf(not schedcat.util.linprog.cplex_available, "no LP solver available")
+    def test_dpcp_py(self):
+        lb.apply_lp_dpcp_bounds(self.ts, self.resource_locality, use_py=True)
+
+    def test_dflp_cpp(self):
+        lb.apply_lp_dflp_bounds(self.ts, self.resource_locality, use_py=False)
+
+    @unittest.skipIf(not schedcat.util.linprog.cplex_available, "no LP solver available")
+    def test_dflp_py(self):
+        lb.apply_lp_dflp_bounds(self.ts, self.resource_locality, use_py=True)
+
+
+
+    def test_dpcp_cpp_no_req(self):
+        lb.apply_lp_dpcp_bounds(self.ts_no_req, {}, use_py=False)
+        self.assertEqual(self.ts_no_req[0].blocked, 0)
+        self.assertEqual(self.ts_no_req[0].suspended, 0)
+        self.assertEqual(self.ts_no_req[1].blocked, 0)
+        self.assertEqual(self.ts_no_req[1].suspended, 0)
+        self.assertEqual(self.ts_no_req[2].blocked, 0)
+        self.assertEqual(self.ts_no_req[2].suspended, 0)
+
+    @unittest.skipIf(not schedcat.util.linprog.cplex_available, "no LP solver available")
+    def test_dpcp_py_no_req(self):
+        lb.apply_lp_dpcp_bounds(self.ts_no_req, {}, use_py=True)
+        self.assertEqual(self.ts_no_req[0].blocked, 0)
+        self.assertEqual(self.ts_no_req[0].suspended, 0)
+        self.assertEqual(self.ts_no_req[1].blocked, 0)
+        self.assertEqual(self.ts_no_req[1].suspended, 0)
+        self.assertEqual(self.ts_no_req[2].blocked, 0)
+        self.assertEqual(self.ts_no_req[2].suspended, 0)
+
+    def test_dflp_cpp_no_req(self):
+        lb.apply_lp_dflp_bounds(self.ts_no_req, {}, use_py=False)
+        self.assertEqual(self.ts_no_req[0].blocked, 0)
+        self.assertEqual(self.ts_no_req[0].suspended, 0)
+        self.assertEqual(self.ts_no_req[1].blocked, 0)
+        self.assertEqual(self.ts_no_req[1].suspended, 0)
+        self.assertEqual(self.ts_no_req[2].blocked, 0)
+        self.assertEqual(self.ts_no_req[2].suspended, 0)
+
+    @unittest.skipIf(not schedcat.util.linprog.cplex_available, "no LP solver available")
+    def test_dflp_py_no_req(self):
+        lb.apply_lp_dflp_bounds(self.ts_no_req, {}, use_py=True)
+        self.assertEqual(self.ts_no_req[0].blocked, 0)
+        self.assertEqual(self.ts_no_req[0].suspended, 0)
+        self.assertEqual(self.ts_no_req[1].blocked, 0)
+        self.assertEqual(self.ts_no_req[1].suspended, 0)
+        self.assertEqual(self.ts_no_req[2].blocked, 0)
+        self.assertEqual(self.ts_no_req[2].suspended, 0)
+