path: root/gen/mc_generators.py

import gen.rv as rv

from color import get_cache_info,CacheInfo,BlockColorScheme,RandomColorScheme,EvilColorScheme
from common import try_get_config_option, log_once
from gen.generator import GenOption,Generator,NAMED_UTILIZATIONS,NAMED_PERIODS
from parse.col_map import ColMap
from parse.tuple_table import TupleTable


NAMED_SHARES = {
    'weighted' : [1, 1, 8, 1],
    'harmonic' : [1, 2, 4, 1],
    'fair'     : [1, 1, 1, 1],
}

TP_BASE = """#for $t in $lvl{0}
{1}-g {0} -s $scale{0} $t.cost $t.period
#end for"""
TP_LVLA = """#if $lvla
/proc/litmus/plugins/MC-CE/ce_file{
#for $t in $lvla
$t.cpu, $t.lvla_id, $t.budget
#end for
}
#end if
""" + 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
#for $i in range($cpus)
#if $d_fifo
#set $fopt='-f'
#else
#set $fopt=''
#end if
#if d_nice
#set $nopt='-n'
#else
#set $nopt=''
#end if
bespin -s $i -f $i.misses $be_opts -p $i $fopt $nopt
#end for
#end if"""

TM_OPT = 'MERGE_TIMERS'
SS_OPT = 'PLUGIN_MC_LINUX_SLACK_STEALING'
RD_OPT = 'PLUGIN_MC_REDIRECT'
MC_OPT = 'PLUGIN_MC'
LEVELS = 3

class McGenerator(Generator):
    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):
        timer_merging = try_get_config_option(TM_OPT, False)
        slack_stealing = try_get_config_option(SS_OPT, False)
        redirect = try_get_config_option(RD_OPT, True)

        return [GenOption('levels', range(1, LEVELS+1), [3],
                          'Number of criticality levels: C, BC, ABC'),
                GenOption('be', [True,False], [False],
                          'Execute background work using bespin.'),

                GenOption('timer_merging', [True,False], [timer_merging],
                          'Require timer-merging support.'),
                GenOption('redirect', [True,False], [redirect],
                           'Redirect work to the interrupt master.'),
                GenOption('slack_stealing', [True,False], [slack_stealing],
                           'Schedule linux tasks in the background.'),

                GenOption('d_nice', [True,False], [False],
                           'Schedule level-D tasks using nice().'),
                GenOption('d_fifo', [True, False], [False],
                          'Schedule level-D tasks under SCHED_FIFO.'),

                GenOption('a_hyperperiod', float, 25.0,
                           'Level-A hyperperiod (ms).'),
                Generator._dist_option('b_periods', ['harmonic'], NAMED_PERIODS,
                'Level-B task periods. Harmonic is always used if level A is present.'),
                Generator._dist_option('c_periods', ['harmonic'],
                                       NAMED_PERIODS, 'Level-C task periods.'),

                Generator._dist_option('a_utils', ['bimo-light'],
                                       NAMED_UTILIZATIONS,
                                       'Level-A task utilizations (at level A).'),
                Generator._dist_option('b_utils', ['bimo-light'],
                                       NAMED_UTILIZATIONS,
                                       'Level-B task utilizations (at level B).'),
                Generator._dist_option('c_utils', ['bimo-light'],
                                       NAMED_UTILIZATIONS,
                                       'Level-C task utilizations (at level C).'),

                Generator._dist_option('shares', ['fair'], NAMED_SHARES,
                                       '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]*cpus
        tasks = [0]*cpus
        for t in ts:
            t.cpu = utils.index(min(utils))
            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
        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+1]) * params['cpus']

    def __get_scale(self, params, level):
        shares, level = self.__adjust(params, level)
        return float(sum(shares[:level+1])) / sum(shares)

    def __create_lvla_sched(self, params):
        if params['levels'] < 3:
            return []

        utils = self._create_dist('utilization', params['a_utils'],
                                  NAMED_UTILIZATIONS)
        periods = self._create_dist('period', params['a_hyperperiod'], None)

        ts = self._create_taskset(params, periods, utils)

        # Make the budget used by the cyclic executive larger than the
        # actual WCET because of overheads
        for t in ts:
            t.budget = int(1.05 * 1000000 * t.cost)
            t.wcet = int(t.cost)

        self.__partition_worst_fit(params, ts)

        return ts

    def __create_lvlb_sched(self, params):
        if params['levels'] < 2:
            return []

        utils = self._create_dist('utilization', params['b_utils'],
                                  NAMED_UTILIZATIONS)


        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)

        ts = self._create_taskset(params, periods, utils, max_util)
        self.__partition_worst_fit(params, ts)

        return ts

    def __create_lvlc_sched(self, params):
        utils = self._create_dist('utilization', params['c_utils'],
                                  NAMED_UTILIZATIONS)
        periods = self._create_dist('period', params['c_periods'],
                                    NAMED_PERIODS)
        max_util = self.__get_max_util(params, 2)

        return self._create_taskset(params, periods, utils, max_util)

    def _get_tasks(self, params):
        return {'lvla': self.__create_lvla_sched(params),
                'lvlb': self.__create_lvlb_sched(params),
                'lvlc': self.__create_lvlc_sched(params)}

    def _create_exp(self, params):
        # Ugly way of doing it
        self.shares = self._create_dist('shares', params['shares'],
                                        NAMED_SHARES)

        tasks = self._get_tasks(params)

        conf_options = {MC_OPT : 'y'}
        if params['timer_merging']:
            conf_options[TM_OPT] = 'y'
        if params['redirect']:
            if not params['release_master']:
                log_once("Forcing release master option to enable redirection.")
                params['release_master'] = 'y'
            conf_options[RD_OPT] = 'y'
        if params['slack_stealing']:
            conf_options[SS_OPT] = 'y'

        scales = []
        for index, level in enumerate('abc'):
            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"""

# Now done by experiment.py
# # Always add some pages
# TP_ADD = """/proc/sys/litmus/color/add_pages{1}"""

# Use special spin for color tasks
TP_COLOR_BASE = """colorspin -y $t.id -x $t.colorcsv -q $t.wss -l $t.loops """

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_ns > 0
/proc/sys/litmus/color/chunk_size{$chunk_size_ns}
#end if"""

COLOR_TYPES = ['scheduling', 'locking', 'unmanaged']

class ColorMcGenerator(McGenerator):
    __SINGLE_PAGE_LOOP_MS = {'ringo': .023}

    def __init__(self, params = {}):
        super(ColorMcGenerator, self).__init__("MC",
            templates=[TP_TYPE, TP_CHUNK, TP_COLOR_B, TP_COLOR_C],
            options=self.__make_options(),
            params=self.__extend_params(params))

        self.tasksets = None

    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 __get_system_name(self):
        import socket
        return socket.gethostname().split(".")[0]

    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.cache = info

        hostname = self.__get_system_name()
        if hostname not in self.__SINGLE_PAGE_LOOP_MS:
            first_host = self.__SINGLE_PAGE_LOOP_MS.keys()[0]
            log_once("hostname", "No timing info for host %s" % hostname +
                     ", needed to calculate work done per task. Please get the "
                     "timing info and add to __SINGLE_PAGE_LOOP_MS in " +
                     "mc_generators.py. Assuming host %s." % first_host)
            hostname = first_host
        self.host = hostname

    def __make_options(self):
        self.__make_system_info()

        return [GenOption('type', COLOR_TYPES, COLOR_TYPES,
                          'Cache management type.'),
                GenOption('host', self.__SINGLE_PAGE_LOOP_MS.keys(), self.host,
                          'System experiment will run on (for calculating work).'),
                GenOption('chunk_size_ns', float, 0, 'Chunk size. 0 = no chunking.'),
                GenOption('ways', int, self.cache.ways, 'Ways (associativity).'),
                GenOption('colors', int, self.cache.colors,
                          'System colors (cache size / ways).'),
                GenOption('page_size', int, self.cache.page,
                          'System page size.'),
                GenOption('wss', [float, int], .25,
                          'Task working set sizes. Can be expressed as a fraction ' +
                          'of the cache.')]


    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))

        # Divide in half for HRT, SRT divide
        return pages / 2


    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 __get_loops(self, task, pages, system):
        all_pages_loop = self.__SINGLE_PAGE_LOOP_MS[system] * pages
        return int(task.cost / all_pages_loop) + 1

    def _get_tasks(self, params):
        # Share tasksets amongst experiments with different types but
        # identical other parameters for proper comparisons
        if self.tasksets == None:
            fields = params.keys()
            fields.remove("type")
            self.tasksets = TupleTable( ColMap(fields), lambda:None )

        if params not in self.tasksets:
            ts = super(ColorMcGenerator, self)._get_tasks(params)
            self.tasksets[params] = ts

        return self.tasksets[params]

    def _customize(self, task_system, params):
        '''Add coloring properties to the mixed-criticality task system.'''
        pages_needed = self.__get_wss_pages(params)
        real_wss = params['page_size'] * pages_needed

        # 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
            task.wss = real_wss
            task.loops = self.__get_loops(task, pages_needed, params['host'])

        c = params['colors']
        w = params['ways']

        if params['type'] == 'unmanaged':
            hrt_colorer = EvilColorScheme(c, w)
            srt_colorer = hrt_colorer
        else:
            # Divide cache between hrt and srt
            c /= 2
            srt_colorer = RandomColorScheme(c, w)
            hrt_colorer = BlockColorScheme(c, w, way_first=True)

        hrt_colorer.color(task_system['lvlb'], pages_needed)
        srt_colorer.color(task_system['lvlc'], pages_needed)

        # This check has saved me a lot of trouble already, leave it in
        for t in task_system['lvlb'] + task_system['lvlc']:
            if sum(t.colors.values()) * params['page_size'] < real_wss:
                raise Exception("Didn't color enough pages for %s" % params)

        if params['type'] != 'unmanaged':
            # Bump srt into the second half of the cache
            for t in task_system['lvlc']:
                t.colors = {colors+c:w for colors, w in t.colors.iteritems()}

        for t in all_tasks:
            self.__make_csv(t)