Added ColorMcGenerator.

4 files changed, 316 insertions, 30 deletions

diff --git a/gen/__init__.py b/gen/__init__.py
index 8c60b46..803bb37 100644
--- a/gen/__init__.py
+++ b/gen/__init__.py
@@ -1,6 +1,9 @@
 import generator as gen
 import edf_generators as edf
+import mc_generators as mc
 
 gen.register_generator("G-EDF", edf.GedfGenerator)
 gen.register_generator("P-EDF", edf.PedfGenerator)
 gen.register_generator("C-EDF", edf.CedfGenerator)
+gen.register_generator("MC", mc.McGenerator)
+gen.register_generator("Color-MC", mc.ColorMcGenerator)
diff --git a/gen/color.py b/gen/color.py
new file mode 100644
index 0000000..8184b8b
--- /dev/null
+++ b/gen/color.py
@@ -0,0 +1,102 @@
+import os
+import re
+
+from collections import namedtuple,defaultdict
+from math import ceil
+from random import randint
+
+class ColorScheme(object):
+    def __init__(self, colors, ways):
+        self.colors = colors
+        self.ways = ways
+
+    def color(self, tasks, wss):
+        '''Assign a color->replicas dict to each task in tasks.'''
+        raise NotImplementedError
+
+class BlockColorScheme(ColorScheme):
+    def __init__(self, colors, ways, way_first):
+        super(BlockColorScheme, self).__init__(colors, ways)
+        self.way_first = way_first
+
+    def color(self, tasks, pages_needed):
+        '''Pages are assigned in blocks, either maximizing the number of ways
+        or maximizing the number of colors used.'''
+        cpus = defaultdict(list)
+        for t in tasks:
+            cpus[t.cpu].append(t)
+
+        if self.way_first:
+            # Way first means maximize ways
+            pages_per_color = min(self.ways, pages_needed)
+            colors_per_task = int(ceil(pages_needed/pages_per_color))
+        else:
+            # Color first means maximize colors
+            colors_per_task = min(self.colors, pages_needed)
+            pages_per_color = int(ceil(pages_needed/colors_per_task))
+
+        curr_color = 0
+        for cpu, tasks in cpus.iteritems():
+            # All tasks on a CPU have the same coloring scheme
+            cpu_colors = defaultdict(int)
+            for _ in xrange(colors_per_task):
+                curr_color = (curr_color + 1) % self.colors
+                cpu_colors[curr_color] = pages_per_color
+
+            for t in tasks:
+                t.colors = cpu_colors
+
+class RandomColorScheme(ColorScheme):
+    def color(self, tasks, pages_needed):
+        '''Pages are placed randomly in the cache'''
+        if pages_needed >= self.ways * self.colors:
+            raise Exception("Too many pages: %d > %d * %d" %
+                            (pages_needed, self.ways, self.colors))
+
+        for t in tasks:
+            t.colors = defaultdict(int)
+
+            for _ in xrange(pages_needed):
+                # Find the next color with available ways
+                while True:
+                    next_color = randint(0, self.colors - 1)
+                    if t.colors[next_color] != self.ways:
+                        break
+
+                t.colors[next_color] += 1;
+
+class EvilColorScheme(ColorScheme):
+    def color(self, tasks, pages_needed):
+        '''All tasks' working sets are placed at the front of the cache'''
+        colors = defaultdict(int)
+        color  = 0
+
+        while pages_needed > 0:
+            colors[color] = min(self.ways, pages_needed)
+            pages_needed -= colors[color]
+
+            color += 1
+
+        for t in tasks:
+            t.colors = colors
+
+
+INFO_FIELDS = ['cache', 'line', 'page', 'ways', 'sets', 'colors']
+INFO_PROC   = '/proc/sys/litmus/color/cache_info'
+
+# Build parsing regex
+FIELD_REGEX = r"(?:.*?{0}.*?(?P<{0}>\d+).*?)"
+INFO_REGEX  = "|".join([FIELD_REGEX.format(field) for field in INFO_FIELDS])
+INFO_REGEX  = r"(?:{})*".format(INFO_REGEX)
+
+# To fill up this
+CacheInfo = namedtuple('CacheInfo', INFO_FIELDS)
+
+def get_cache_info():
+    if os.path.exists(INFO_PROC):
+        with open(INFO_PROC, 'r') as f:
+            data   = f.read()
+            values = re.search(INFO_REGEX, data, re.M|re.I|re.S).groupdict()
+            return CacheInfo(**values)
+    else:
+        return None
diff --git a/gen/generator.py b/gen/generator.py
index f35a22b..1205490 100644
--- a/gen/generator.py
+++ b/gen/generator.py
@@ -51,38 +51,44 @@ class Generator(object):
     This class also performs checks of parameter values and prints out help.
     All subclasses must implement _create_exp.
     '''
-    def __init__(self, scheduler, templates, options, params):
+    def __init__(self, name, templates, options, params):
+        self.__make_defaults(params)
+
         self.options = self.__make_options(params) + options
 
         self.__setup_params(params)
 
         self.params    = params
         self.template  = "\n".join([TP_RM] + templates)
-        self.scheduler = scheduler
-
-    def __make_options(self, params):
-        '''Return generic Litmus options.'''
+        self.scheduler = name
 
-        # Guess defaults using the properties of this computer
+    def __make_defaults(self, params):
+        '''Guess defaults using the properties of this computer'''
         if 'cpus' in params:
-            cpus = min(map(int, params['cpus']))
+            self.cpus = min(map(int, params['cpus']))
         else:
-            cpus = num_cpus()
+            self.cpus = num_cpus()
         try:
             config = get_config_option("RELEASE_MASTER") and True
         except:
             config = False
-        release_master = list(set([False, config]))
+        self.release_master = list(set([False, config]))
 
 
-        return [GenOption('tasks', int, range(cpus, 5*cpus, cpus),
-                              'Number of tasks per experiment.'),
-                GenOption('cpus', int, [cpus],
+    def __make_options(self, params):
+        '''Return generic Litmus options.'''
+        return [GenOption('num_tasks', int,
+                          range(self.cpus, 5*self.cpus, self.cpus),
+                          'Number of tasks per experiment.'),
+                GenOption('cpus', int, [self.cpus],
                           'Number of processors on target system.'),
-                GenOption('release_master', [True,False], release_master,
+                GenOption('release_master', [True,False], self.release_master,
                           'Redirect release interrupts to a single CPU.'),
                 GenOption('duration', float, [30], 'Experiment duration.')]
 
+    def _num_cpus(self):
+        return self.cpus
+
     @staticmethod
     def _dist_option(name, default, distribution, help):
         return GenOption(name, [str, float, type([])] + distribution.keys(),
@@ -119,6 +125,9 @@ class Generator(object):
                                         max_util)
         return ts
 
+    def _out_dir(self):
+        return self.out_dir
+
     def _write_schedule(self, params):
         '''Write schedule file using current template for @params.'''
         sched_file = self.out_dir + "/" + DEFAULTS['sched_file']
diff --git a/gen/mc_generators.py b/gen/mc_generators.py
index d6d8d90..bbb1ab9 100644
--- a/gen/mc_generators.py
+++ b/gen/mc_generators.py
@@ -1,5 +1,6 @@
 import gen.rv as rv
 
+from color import get_cache_info,CacheInfo,BlockColorScheme,RandomColorScheme,EvilColorScheme
 from common import try_get_config_option
 from gen.generator import GenOption,Generator,NAMED_UTILIZATIONS,NAMED_PERIODS
 
@@ -16,11 +17,11 @@ TP_BASE = """#for $t in $lvl{0}
 TP_LVLA = """#if $lvla
 /proc/litmus/plugins/MC-CE/ce_file{
 #for $t in $lvla
-$t.cpu, $t.id, $t.budget
+$t.cpu, $t.lvla_id, $t.budget
 #end for
 }
 #end if
-""" + TP_BASE.format("a", "-i $t.id -p $t.cpu ")
+""" + TP_BASE.format("a", "-i $t.lvla_id -p $t.cpu ")
 TP_LVLB = TP_BASE.format("b", "-p $t.cpu ")
 TP_LVLC = TP_BASE.format("c", "")
 TP_LVLD = """#if $be
@@ -46,10 +47,12 @@ MC_OPT = 'PLUGIN_MC'
 LEVELS = 3
 
 class McGenerator(Generator):
-    def __init__(self, params = {}):
-        super(McGenerator, self).__init__("MC",
-                                          [TP_LVLA, TP_LVLB, TP_LVLC, TP_LVLD],
-                                          self.__make_options(),
+    def __init__(self, name="MC",
+                 templates=[TP_LVLA, TP_LVLB, TP_LVLC, TP_LVLD],
+                 options=[], params={}):
+        super(McGenerator, self).__init__(name,
+                                          templates,
+                                          self.__make_options() + options,
                                           params)
 
     def __make_options(self):
@@ -92,34 +95,46 @@ class McGenerator(Generator):
                                        'Level-C task utilizations (at level C).'),
 
                 Generator._dist_option('shares', ['fair'], NAMED_SHARES,
-                                       'Distribution of actual utilizations.')]
+                                       'Distribution of runtime utilizations.')]
 
     def __partition_worst_fit(self, params, ts):
+        cpus = int(params['cpus'])
+        if params['release_master']:
+            # No level B on the release master
+            cpus -= 1
+
         # Partition using worst-fit for most even distribution
-        utils = [0]*int(params['cpus'])
-        tasks = [0]*int(params['cpus'])
+        utils = [0]*cpus
+        tasks = [0]*cpus
         for t in ts:
             t.cpu = utils.index(min(utils))
-            t.id = tasks[t.cpu]
+            t.lvla_id = tasks[t.cpu]
 
             utils[t.cpu] += t.utilization()
             tasks[t.cpu] += 1
 
+            # Increment by one so release master has no tasks
+            t.cpu += 1
+
     def __adjust(self, params, level):
         # Adjust for levels which aren't used
-        ldiff  = LEVELS - params['levels']
-        shares = self.shares[ldiff:]
-        level -= ldiff
+        num = params['levels']
+        shares = list(self.shares)
+        if num < 4:
+            shares.pop()
+        if num < 3:
+            shares.pop(0)
+            level -= 1
 
         return shares, level
 
     def __get_max_util(self, params, level):
         shares, level = self.__adjust(params, level)
-        return float(shares[level]) / sum(shares[:level]) * params['cpus']
+        return float(shares[level]) / sum(shares[:level+1]) * params['cpus']
 
     def __get_scale(self, params, level):
         shares, level = self.__adjust(params, level)
-        return float(shares[level]) / sum(shares)
+        return float(sum(shares[:level+1])) / sum(shares)
 
     def __create_lvla_sched(self, params):
         if params['levels'] < 3:
@@ -148,11 +163,13 @@ class McGenerator(Generator):
         utils = self._create_dist('utilization', params['b_utils'],
                                   NAMED_UTILIZATIONS)
 
-        # Level-A is present, b must be harmonic with lvla hyperperiod
+
         if params['levels'] > 2:
+            # Level-A is present, b must be harmonic with lvla hyperperiod
             plist = [params['a_hyperperiod']*2**x for x in xrange(0, 4)]
             periods = rv.uniform_choice(plist)
         else:
+            # Level b can have whatever periods it wants
             periods = self._create_dist('period', params['b_periods'],
                                         NAMED_PERIODS)
         max_util = self.__get_max_util(params, 1)
@@ -171,6 +188,9 @@ class McGenerator(Generator):
 
         return self._create_taskset(params, periods, utils, max_util)
 
+    def _customize(self, task_system, params):
+        pass
+
     def _create_exp(self, params):
         # Ugly way of doing it
         self.shares = self._create_dist('shares', params['shares'],
@@ -193,13 +213,165 @@ class McGenerator(Generator):
 
         scales = []
         for index, level in enumerate('abc'):
-            scales += [('scale%s' % level, self.__get_scale(params, index))]
+            if tasks['lvl%s'%level]:
+                scales += [('scale%s' % level, self.__get_scale(params, index))]
 
         schedule_variables = params.items() + tasks.items() + scales
         param_variables = params.items() + [('config-options',conf_options)]
 
+        self._customize(tasks, params)
+
         self._write_schedule(dict(schedule_variables))
         self._write_params(dict(param_variables))
 
         # Ugly
         del(self.shares)
+
+
+# Types are base, locking, preemptive
+# This sets up the scheduler to create each
+TP_TYPE = """#if $type != 'unmanaged'
+/proc/sys/litmus/color/lock_cache{1}
+#else
+/proc/sys/litmus/color/lock_cache{0}
+#end if
+#if $type == 'scheduling'
+/proc/sys/litmus/color/preempt_cache{1}
+#else
+/proc/sys/litmus/color/preempt_cache{0}
+#end if"""
+
+# Use special spin for color tasks
+TP_COLOR_BASE = """colorspin -y $t.id -x $t.colorcsv """
+
+TP_COLOR_B = TP_BASE.format("b", TP_COLOR_BASE + "-p $t.cpu ")
+TP_COLOR_C = TP_BASE.format("c", TP_COLOR_BASE)
+
+# Not even sure job splitting is still possible
+TP_CHUNK = """#if $chunk_size > 0
+/proc/sys/litmus/color/chunk_size{$chunk_size}
+#end if"""
+
+COLOR_TYPES = ['scheduling', 'locking', 'unmanaged']
+
+class ColorMcGenerator(McGenerator):
+    def __init__(self, params = {}):
+        super(ColorMcGenerator, self).__init__("COLOR-MC",
+            templates=[TP_TYPE, TP_CHUNK, TP_COLOR_B, TP_COLOR_C],
+            options=self.__make_options(),
+            params=self.__extend_params(params))
+
+    def __extend_params(self, params):
+        '''Add in fixed mixed-criticality parameters.'''
+        params['levels'] = 2
+        params['be'] = False
+        params['redirect'] = True
+        params['release_master'] = True
+        params['timer_merging'] = False
+        params['slack_stealing'] = False
+
+        # Set these just so they aren't displayed to the user
+        params['d_nice'] = False
+        params['d_fifo'] = False
+        params['a_hyperperiod'] = 0
+        params['a_utils'] = 'bimo-light'
+
+        return params
+
+    def __make_system_info(self):
+        info = get_cache_info()
+
+        if not info:
+            # Pick something semi-reasonable. these will work (wastefully) on
+            # many machines. The plugin will pidgeon hole pages into these
+            # specific areas, so even if the cache which runs this code has
+            # more ways and/or colors than these, it will run as though these
+            # are its parameters. This is sufficient for most testing
+            ways   = 8
+            colors = 8
+            page   = 4096
+            line   = 64
+
+            cache = ways * colors * page
+            sets  = cache / (line * ways)
+
+            info = CacheInfo(cache, line=line, page=page,
+                             ways=ways, sets=sets, colors=colors)
+
+        self.system = info
+
+    def __make_options(self):
+        self.__make_system_info()
+
+        return [GenOption('type', COLOR_TYPES, COLOR_TYPES,
+                          'Cache management type.'),
+                GenOption('chunk_size', float, [0], 'Chunk size.'),
+                GenOption('ways', int, [self.system.ways], 'Ways (associativity).'),
+                GenOption('colors', int, [self.system.colors],
+                          'System colors (cache size / ways).'),
+                GenOption('page_size', int, [self.system.page],
+                          'System page size.'),
+                GenOption('wss', [float, int], [.5],
+                          'Task working set sizes. Can be expressed as a fraction ' +
+                          'of the cache.'),
+                GenOption('align_unmanaged', [True, False], [True],
+                          'Place all working sets of unmanaged task systems in '+
+                          'the same location, for maximum interference.')]
+
+
+    def __get_wss_pages(self, params):
+        '''Return the number of pages in a single task's working set.'''
+        cache_pages = params['ways'] * params['colors']
+
+        wss = params['wss']
+        if type(wss) == float and wss <= 1.0:
+            # Can express wss as fraction of total cache
+            pages = int(wss*cache_pages)
+        else:
+            if wss < params['page_size']:
+                raise Exception(('Cannot have working set (%d) smaller than '
+                                 'a page (%d).') % (wss, params['page_size']))
+
+            pages = wss / params['page_size']
+
+            if pages > cache_pages:
+                raise Exception('WSS (%d) larger than the cache!' % (wss))
+
+        return pages
+
+
+    def __make_csv(self, task):
+        '''Write task.colors into a csv file, stored as task.colorcsv.'''
+        fname = 'colors%d.csv' % task.id
+        task.colorcsv = fname
+
+        with open(self._out_dir() + "/" + fname, 'w') as f:
+            for color, replicas in task.colors.iteritems():
+                f.write("%d, %d\n" % (color, replicas))
+
+    def _customize(self, task_system, params):
+        '''Add coloring properties to the mixed-criticality task system.'''
+        # Every task needs a unique id for coloring and wss walk order
+        all_tasks = []
+        for level, tasks in task_system.iteritems():
+            all_tasks += tasks
+        for i, task in enumerate(all_tasks):
+            task.id = i
+
+        c = params['colors']
+        w = params['ways']
+
+        if params['type'] == 'unmanaged':
+            hrt_colorer = EvilColorScheme(c, w)
+            srt_colorer = hrt_colorer
+        else:
+            srt_colorer = RandomColorScheme(c, w)
+            hrt_colorer = BlockColorScheme(c, w, way_first=True)
+
+        pages_needed = self.__get_wss_pages(params)
+
+        hrt_colorer.color(task_system['lvlb'], pages_needed)
+        srt_colorer.color(task_system['lvlc'], pages_needed)
+
+        for t in all_tasks:
+            self.__make_csv(t)