SystemStateFlow.py 16.1 KB
Newer Older
1
from collections import defaultdict
2 3 4 5 6 7 8
from .common import *
from .Analysis import *
from .Sporadic import SporadicEvent
from .Function import Function
from .GlobalAbbInfo import GlobalAbbInfo
from .SystemSemantic import *
from .AtomicBasicBlock import E
9 10


11
class SystemStateFlow(Analysis):
12 13 14 15 16 17
    """This pass lets the system state flow through the system. It should
       be faster than the symbolic execution, but lead to a more
       imprecise global cfg, since it merges states at function calls
       and join nodes.

    """
18 19
    pass_alias = "state-flow"

20 21
    def __init__(self):
        Analysis.__init__(self)
22 23 24 25 26
        self.sporadic_events = []
        # A member for the RunningTask analysis
        self.running_task = None
        # States for the fixpoint iteration
        self.before_abb_states = None
27
        self.edge_states = None
28 29
        self.system_call_semantic = None
        self.fixpoint = None
30 31
        # This variable stores how many interrupt sources can trigger for an ABB
        self.isr_activation_for_abb = defaultdict(lambda: 0)
32

33 34
    def requires(self):
        # We require all possible system edges to be contructed
35
        return ["DynamicPriorityAnalysis", "InterruptControlAnalysis"]
36

37 38 39
    def get_edge_filter(self):
        return set([E.task_level, E.state_flow, E.state_flow_irq])

40
    @staticmethod
41
    def update_before_state(edge_states, before_state_dict, block, edge_type):
42
        input_abbs = block.get_incoming_nodes(edge_type)
43 44
        input_states = [edge_states[(source, block)] for source in input_abbs]
        before = SystemState.merge_many(block.system_graph, input_states)
45

46 47
        changed = False
        if not block in before_state_dict:
48 49 50
            assert not before.frozen
            before_state_dict[block] = before.copy()
            before_state_dict[block].freeze()
51 52
            changed = True
        else:
53
            before_state_dict[block].frozen = False
54
            changed = before_state_dict[block].merge_with(before)
55 56 57
            before_state_dict[block].frozen = True
            before = before_state_dict[block]

58
        return changed, before
59

60
    def set_state_on_edge(self, source, target, state):
61 62
        if not target in source.get_outgoing_nodes(E.state_flow):
            source.add_cfg_edge(target, E.state_flow)
63

64 65 66
        # We say that on the edge from one ABB to the other one, the
        # running abb is already the target
        state.current_abb = target
67 68 69
        if target in self.before_abb_states:
            self.before_abb_states[target].frozen = False
            changed = self.before_abb_states[target].merge_with(state)
70
        else:
71 72 73 74 75
            changed = True
            self.before_abb_states[target] = state
        self.before_abb_states[target].frozen = True
        if changed and not target in self.fixpoint:
            self.fixpoint.enqueue_later(item = target)
76

77 78
    def install_sporadic_events(self):
        # Install the alarm handlers
79 80 81
        if self.system_graph.AlarmHandlerSubtask:
            wrapped_alarm = SSF_SporadicEvent(self.system_graph.AlarmHandlerSubtask,
                                              self.system_call_semantic)
82
            self.sporadic_events.append(wrapped_alarm)
83

84
        # Install the ISR handlers
85
        for isr in self.system_graph.isrs:
86
            wrapped_isr = SSF_SporadicEvent(isr, self.system_call_semantic)
87
            self.sporadic_events.append(wrapped_isr)
88

89 90
    def do_computation_with_sporadic_events(self, block, before, syscall):
        after_states = self.system_call_semantic.do_computation(block, before, syscall)
91 92

        # Handle sporadic events
93
        events = 0
94
        for sporadic_event in self.sporadic_events:
95 96
            if not sporadic_event.can_trigger(before):
                continue
97
            after = sporadic_event.trigger(before)
98
            after_states.append(after)
99
            events += 1
Christian Dietrich's avatar
Christian Dietrich committed
100
        block.sporadic_trigger_count = events
101

102
        return after_states
103

104
    def block_functor(self, fixpoint, block):
105
        self.debug("{{{ " + str(block))
106

107
        before = self.before_abb_states[block]
108 109 110

        # If this block belongs to a task, it must the highest
        # available task for the input state. Otherwise we wouldn't
111
        # have been scheduled (or the current task is non-preemptable)
112
        scc = self.system_call_semantic
113

114
        after_states = scc.do_SystemCall(
115
            block, before,
116 117 118 119 120 121 122 123
            {S.StartOS         : scc.do_StartOS,
             S.ActivateTask    : scc.do_ActivateTask,
             S.TerminateTask   : scc.do_TerminateTask,
             S.ChainTask       : scc.do_ChainTask,
             S.computation     : self.do_computation_with_sporadic_events,
             S.kickoff         : scc.do_computation, # NO ISRS!
             S.SetRelAlarm     : scc.do_computation, # ignore
             S.CancelAlarm     : scc.do_computation, # ignore
124 125
             S.GetAlarm        : scc.do_computation, # ignore
             S.AdvanceCounter  : scc.do_AdvanceCounter,
126 127 128 129 130 131 132 133 134 135
             # Done in DynamicPriorityAnalysis
             S.GetResource     : scc.do_computation,
             S.ReleaseResource : scc.do_computation,
             # Done in InterruptControlAnalysis
             S.DisableAllInterrupts : scc.do_computation,
             S.EnableAllInterrupts  : scc.do_computation,
             S.SuspendAllInterrupts : scc.do_computation,
             S.ResumeAllInterrupts  : scc.do_computation,
             S.SuspendOSInterrupts  : scc.do_computation,
             S.ResumeOSInterrupts   : scc.do_computation,
136 137
             S.AcquireCheckedObject : scc.do_computation,
             S.ReleaseCheckedObject : scc.do_computation,
138 139

             S.Idle            : scc.do_Idle})
140

141
        # Schedule depending on the possible output state
142 143 144 145
        for (sycall, after_state) in after_states:
            edges = self.system_call_semantic.schedule_imprecise(block, after_state)
            for (source, target, new_state) in edges:
                self.set_state_on_edge(source, target, new_state)
146

147
        self.debug("}}}")
148

149

150
    def do(self):
151 152 153 154
        # If there are any events, we cannot use the state flow analysis
        for subtask in self.system_graph.subtasks:
            if len(subtask.events) > 0:
                logging.warn("Skipped State-Flow Analysis, since Events are present")
155 156
                return

157 158
        old_copy_count = SystemState.copy_count

159 160
        self.running_task = self.get_analysis(CurrentRunningSubtask.name())
        # (ABB, ABB) -> SystemState
161
        self.edge_states = {}
162
        # ABB -> SystemState
163

164
        self.system_call_semantic = SystemCallSemantic(self.system_graph)
165 166 167

        self.install_sporadic_events()

168
        entry_abb = self.system_graph.get(Function, "StartOS").entry_abb
169 170 171 172 173 174
        entry_state = SystemState(self.system_graph)
        entry_state.current_abb = entry_abb
        entry_state.freeze()

        self.before_abb_states = {entry_abb: entry_state}

175
        self.fixpoint = FixpointIteration([entry_abb])
176
        self.fixpoint.do(self.block_functor)
177

178 179
        # Fixup StartOS Node, otherwise usage of this pointer gets more complicated
        self.before_abb_states[entry_abb].current_abb = entry_abb
180

181 182
        # Merge SporadicEvents
        for isr in self.sporadic_events:
183 184
            isr.fixup_before_states()
            if isinstance(isr.wrapped_event, Alarm):
185
                counter = isr.wrapped_event.counter
186
                # Ignore softcounters
187
                if counter.conf.softcounter:
188
                    continue
189
            for abb in isr.wrapped_event.handler.abbs:
190
                self.before_abb_states[abb] = isr.collected_states[abb]
191

192

193

194 195 196 197
        # Record the number of copied system states
        self.system_graph.stats.add_data(self, "copied-system-states",
                                         SystemState.copy_count - old_copy_count,
                                         scalar = True)
198
        logging.info(" + %d system states copied", SystemState.copy_count - old_copy_count)
199 200 201
        # Record the precision indicators for each abb
        # Count the number of ABBs in the system the analysis works on
        is_relevant = self.system_graph.passes["AddFunctionCalls"].is_relevant_function
202
        abbs = [x for x in self.system_graph.abbs if is_relevant(x.function)]
203 204 205
        precisions = []
        for abb in abbs:
            # Only ABBs from Subtasks
206
            if not abb.function.subtask or not abb.function.subtask.is_real_thread():
207 208 209 210 211 212 213 214 215 216 217
                continue

            if abb in self.before_abb_states:
                precision = self.before_abb_states[abb].precision()
                if not abb.isA(S.StartOS):
                    self.stats.add_data(abb, "ssf-precision", precision, scalar=True)
                precisions.append(precision)
            else:
                # State will not be visited, for sure
                precisions.append(1.0)
        self.stats.add_data(self, "precision", precisions, scalar = True)
218

219 220 221
    ##
    ## Result getters for this analysis
    ##
222 223
    def reachable_subtasks_from_abb(self, abb):
        subtasks = set()
224
        for reached in abb.get_outgoing_nodes(E.state_flow):
225 226 227 228
            st = self.running_task.for_abb(reached)
            subtasks.add(st)
        return subtasks

229
    def activating_subtasks(self, subtask):
230
        subtasks = set()
231
        abbs = set()
232
        for reaching in subtask.entry_abb.get_incoming_nodes(E.state_flow):
233
            st = self.running_task.for_abb(reaching)
234 235
            if st == subtask:
                continue
236
            subtasks.add(st)
237 238
            abbs.add(reaching)
        return subtasks, abbs
239

240
    def for_abb(self, abb):
241 242
        """Return a GlobalAbbInformation object for this object"""
        if abb in self.before_abb_states:
243
            return SSF_GlobalAbbInformation(self, abb)
244

245 246 247 248 249
class SSF_SporadicEvent(SporadicEvent):
    def __init__(self, wrapped_event, system_call_semantic):
        SporadicEvent.__init__(self, wrapped_event.system_graph, \
                               wrapped_event.name, wrapped_event.task,
                               wrapped_event.handler)
250
        self.system_call_semantic = system_call_semantic
251
        self.wrapped_event = wrapped_event
252

253
        self.collected_states = {}
254 255
        # Initialize empty states for merging collected states into
        for abb in self.wrapped_event.handler.abbs:
256
            self.collected_states[abb] = SystemState(self.system_graph)
257

258 259 260 261 262 263 264
        # Variables for the fixpoint iterations
        self.result = None
        self.start_state = None
        self.edge_states = None
        self.before_abb_states = None
        self.fixpoint = None

265 266
        irq_entry_state = SystemState(self.system_graph)
        self.irq_exit_state = SystemState(self.system_graph)
267
        for subtask in self.system_graph.subtasks:
268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283
            irq_entry_state.set_suspended(subtask)
            irq_entry_state.set_continuation(subtask, subtask.entry_abb)

        irq_entry_state.set_ready(self.wrapped_event.handler)
        irq_entry_abb = self.wrapped_event.handler.entry_abb
        irq_entry_state.current_abb = irq_entry_abb

        self.edge_states = dict()
        self.before_abb_states = {irq_entry_abb: irq_entry_state}

        self.fixpoint = FixpointIteration([irq_entry_abb])
        self.fixpoint.do(self.block_functor)

        self.surely_activated = []
        self.maybe_activated = []
        self.in_state = SystemState(self.system_graph)
284
        for subtask in self.system_graph.user_subtasks:
285 286 287 288 289 290 291 292 293
            if self.irq_exit_state.is_surely_ready(subtask):
                self.surely_activated.append(subtask)
            elif self.irq_exit_state.is_maybe_ready(subtask):
                self.maybe_activated.append(subtask)


    def can_trigger(self, state):
        return self.wrapped_event.can_trigger(state)

294
    def do_iret(self, block, before, syscall):
295 296 297 298 299 300 301 302
        # When there is no further local abb node, we have reached the
        # end of the interrupt handler
        self.irq_exit_state.merge_with(before)
        self.irq_exit_state.set_suspended(self.wrapped_event.handler)

        return []


303
    def block_functor(self, fixpoint, block):
304
        if block == self.wrapped_event.handler.entry_abb:
305
            self.changed_current_block = True
306
            before = self.before_abb_states[block]
307 308
        else:
            self.changed_current_block, before = \
309
                SystemStateFlow.update_before_state(self.edge_states,
310
                                                        self.before_abb_states,
311
                                                        block,
312
                                                        edge_type = E.state_flow_irq)
313 314 315

        after_states = self.system_call_semantic.do_SystemCall(
            block, before,
316 317 318 319
            {S.ActivateTask: self.system_call_semantic.do_ActivateTask,
             S.computation: self.system_call_semantic.do_computation,
             S.kickoff: self.system_call_semantic.do_computation,
             S.Idle: self.system_call_semantic.do_Idle,
320
             S.CheckAlarm      : self.system_call_semantic.do_CheckAlarm,
321
             S.iret: self.do_iret})
322
        # Schedule depending on the possible output states
323 324 325 326
        for (syscall, after_state) in after_states:
            edges = self.system_call_semantic.schedule_imprecise(block, after_state)
            for (source, target, new_state) in edges:
                self.set_state_on_edge(source, target, new_state)
327 328 329 330

        # This has to be done after the system call handling, since
        # new irq links could have been introduced
        if self.changed_current_block:
331
            for node in block.get_outgoing_nodes(E.state_flow_irq):
332 333
                self.fixpoint.enqueue_soon(item = node)

334
        # Never leave the handler function here
335
        assert block.function.subtask == self.wrapped_event.handler.subtask
336 337

    def set_state_on_edge(self, source, target, state):
338 339
        if not target in source.get_outgoing_nodes(E.state_flow_irq):
            source.add_cfg_edge(target, E.state_flow_irq)
340 341
            self.changed_current_block = True

342 343 344 345
        # We say that on the edge from one ABB to the other one, the
        # running abb is already the target
        state.current_abb = target

346 347
        self.edge_states[(source, target)] = state

348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374
    def trigger(self, in_state):
        self.in_state.current_abb = in_state.current_abb
        self.in_state.merge_with(in_state, return_changed = False)
        current_subtask = in_state.current_subtask
        current_abb     = in_state.current_abb
        # We have also preempted this one
        self.in_state.add_continuation(current_subtask, current_abb)
        self.in_state.current_abb = None

        ret_state = in_state.copy()
        ret_state.set_continuation(current_subtask, current_abb)

        for subtask in self.surely_activated:
            # Task was surely activated by ISR
            ret_state.set_ready(subtask)
            # If the task is alreay surely running, we cannot add
            # the entry_abb
            if not ret_state.is_surely_ready(subtask):
                ret_state.add_continuation(subtask, subtask.entry_abb)
        for subtask in self.maybe_activated:
            # Task was maybe activated by ISR
            if not ret_state.is_surely_ready(subtask):
                ret_state.set_unsure(subtask)
                # If the task is alreay surely running, we cannot add
                # the entry_abb
                ret_state.add_continuation(subtask, subtask.entry_abb)

375
        return (None, ret_state)
376 377

    def fixup_before_states(self):
378
        for abb in self.wrapped_event.handler.abbs:
379 380
            self.in_state.current_abb = abb
            self.collected_states[abb].merge_with(self.in_state)
381

382
class SSF_GlobalAbbInformation(GlobalAbbInfo):
383 384 385 386
    def __init__(self, analysis, abb):
        GlobalAbbInfo.__init__(self)
        self.analysis = analysis
        self.abb      = abb
387
        assert self.analysis.valid, "SystemStateFlow is not valid"
388 389 390 391 392 393 394 395

    @property
    def state_before(self):
        return self.analysis.before_abb_states[self.abb]

    @property
    def states_after(self):
        """Returns a list of possible next system states"""
396
        edges = set(self.abb.get_outgoing_edges(E.state_flow))
397 398 399

        states = []
        for edge in edges:
400
            states.append(self.analysis.before_abb_states[edge.target])
401
        return states
402

403 404 405
    @property
    def abbs_before(self):
        return self.abb.get_incoming_nodes(E.state_flow)