GitLab

The symbolic system execution is now able to enumerate all possible
system states with two different approaches. Either we can use the "old"
version which uses states with blocks to be executed in the next step,
like it is described in LCTES'15 (Dietrich et. al).

Or we can use the application finite state machines as basis. These
state machines are smaller (lesser nodes) than the application's
CFG. They are based on the task's ICFG.

Change-Id: I05e050ed3f39bd18ecf86b4d7bb423b4ce0825e0

Change-Id: I21d06ffc334fcb349f657023cc52ba63d756d3df

Reading the OIL file and the llvmpy basic blocks is done in
passes. Therefore, we can omit them in the future, if wanted.

Change-Id: Ideef98fc1d9a74af498c522b1509a9d9f2289c92

Rename all parts in a more logical way. The generator is now divided
into three main parts:
  - analysis: Generate GCFG and State Transition graph
  - transform: Generate Assertions, CFG Regions, FSMs
  - coder: bring the information collected in the previous steps down to
           the code.

Change-Id: I5cfd48f6a8d195c30b16b425eda010d9b0405dcd

In order to use a finite state automata as OS implementation, I had to
adjust major parts of the interrupt semantic. Also was the
FiniteStateMachineBuilder flawed, but seems to work now. I could
successfully encode almost all posix test-cases (including
bench-coptermock) as state machines.

Change-Id: Ie5ce6ab4e3f282fa3044026e3ef4f5c8d773b3a3

If we encouter an application with events, we do not use the
System-State Flow Analysis.

Change-Id: I81c30083a95157b64d114a6b8081b11eb43b55d8

- Do not measure the statistics in the pass run time.
- Use the ISR count that can fire at one ABB to calculate
  edge-count:oil-static. This allows system annotations to be considered
  in this number.
- Only count "natural blocks" as abb-count. Natural blocks are existing
  in the application and reachable in the GCFG.
- In the fully connected graph self loops are allowed

Change-Id: Icb28b2d7b1b04e9c075e2c756893505d7e60d5dc

Change-Id: I01ed6f00fb536972710db024531aef9a126c76d5

- SystemGraph: proper accessors for system objects
  .tasks | .subtasks | .alarms | .find() | .get()

- SystemObject: abstract class for all system objects
  A system object has a configuration and an implementation and
  stores everything we know about a certain entity.

Change-Id: Ia42d83f8d826aa22eeddf0d06206c197f48fb966

Offers the implementation of the generator and all necessary changes
to the dependability service and the example application.

Application:
- Remove implementation specific code that is now handled by the
  generator
- Add a description of the CheckedObject to osekossystem.xml
- Move the type declaration to an extra header file (type.h). This
  file is referenced in the xml description to offer a way to define
  many types at once.

Dependability Service:
- Add extern declarations to variables which the generator will
  define.
- Adjust acquire and release interface to work on indices instead of
  pointers.
- Declare external OSEKOS_* functions.
- Fill the dependability queue before entering the infinite loop.
  (This might require a change when features like anti scheduling are
  added)

Generator:
- Make CheckedObject interface known to the generator.
- Replace CheckedObject syscalls to call the appropriate function with
  the appropriate CheckedObject index.
- Extract values from the osek_dom and hand them on to where they are
  required.
- Generate variables into the source file:
    - OS_all_CheckedObjects: An array statically containing all
                             CheckedObjects.
    - OS_all_CheckedObjects_size: The size of this array.
    - OS_*_CheckedObject_Index: The index of CheckedObject named "*"
                                in the array.
- Include the header of the dependability service and of the headers
  the user defined which contain the types.

Change-Id: I4c31c5868d695a2fea61bc7356aad9a6d8162854

We do not spawn a sub-flow analysis for every computation block, for
every sporadic event, but we calculate the influence of the sporadic
event once and "mask" it onto the incomming system state when triggered
the sporadic event.

This is possible, because not all system calls are allowed in ISR2s.

Change-Id: I2d7e04d37039e663e7838207ab6e9d12356ad4d7

Implement two new system calls that increment the counter from the
userspace and allow the access to the remaining ticks on a counter.

Change-Id: I628f500200ab22b703dc8619e09879d11a52aa2c

To get away from the RTSC dependencies, the ABB graph generation
is performed via the python LLVM bindings.

To test the current state, call: main.py -l<list of .ll files>
Example: main.py -l main.ll,foo.ll,bar.ll

Current state:
    - Source modules are linked
    - Basic blocks are splitted at call or invoke instructions
    - BB successors found
    - call to kickoff at each subtask entry
    - Setup all control-flow edges
    - Integrate into rest of the generator framework
    - Add unique ABB suffix to all system calls
    - Output adapted IR to build with suffixed Syscalls
    - Optimize runtime
    - Code cleaned up

    - Starting ABB mergeing, added method for merging ABBS
    - Linear ABB merge looks good
    - Merge if / if-else patterns

TODO:
    - Hope for the best

Change-Id: Ia23d4b84cdc93a349ec0ba6b0497c74a8c22b560

Generate as well the dynamic priority inference graph as the static
priority inference graph.

Change-Id: I4b6005580c583c666479b345342793ddf6f7d7f7

The frozen flag now indicates whether we can reuse a system state, or it
must be preserved as it is. The copy_if_needed() method does copy the
system state only conditionally, if it is frozen.

Change-Id: I3defb67d4d3b51c54a9736817b62bf2ff4c73e30

Thee precision metric for a system states gives an impression how precise
the information is a system state has.

Change-Id: Ifec8f05a1b72a16e208c3c2eeaa04e0a361a8889

In the stats.dict.py now more interesting information about the GCFG,
SSE and SSF is collected.

Change-Id: I09fc82c298cc727aa7eb306df112a95819db23ce

The coptermock application is ported from ciao (without events) to have
an sample application, that we can use as a "big" evalutation system.

Change-Id: I29a34eef2e0f40bf83888b5ff4fdad6cca1cea7c

The interrupt semantic of SSF and SSE differred significantly. Now the
symbolic execution graph is fixed to bend interrupt entry states to the
interrupt exit states. This mimics the same semantic as state flow pass.

Change-Id: I8fc9e45cdc2a7eb5f7a5e012c6d678b8feefceb3

Change-Id: I94e7621b051206b213fa15575079c9429359a400

Change-Id: I295d534485a381689a79582069f16604bb016507

Let the user promise, that all subtasks in a task have to be at least
maybe suspended in order to retrigger it again. This will greatly
improve the handling of interrupts and alarms. We have to assume further
assertions for the fact that (period == deadline).

Change-Id: Ifab1a2559cf40bc6cb398e2e9e393d57695df7ff

The information whether the interrupts are currently enabled or disabled
should (see OSEK specification) never leave the task-level control
flow. Therefore we can statically (like in the Resource optimization)
assign the blocking information for each ABB. The generator then
generates then Machine::{dis,en}able_interrupts() calls only when an
protected area is entered.

Change-Id: I8db9e0828367d0d1410710f8e877ca04223c2ab3

Change-Id: I9cf3166070c3b0d60f74e5892d86ab9d6e5dcf79

For a pass the edge filter promises, that the pass will only use edges
of that type.

Change-Id: Ib8245f3f88edebf70a2c1f14bc8026c2d432f9a4

Both the system state flow and the symbolic system execution can provide
global flow control graphs. The ConstructGlobalCFG pass (formerly
Combine_RunningTask_SSE) selects and combines both methods.

Change-Id: I311f07a31aba1075bf29826d5aa9ce271f1dcb14

The running task analysis is more a system state dataflow analysis. So
we should name it like that.

Change-Id: I39ea9baaa6c2c1781e2ff270ae403b41f06a15ed

The RunningTask and SymbolicSystemExecution are only necessary when
specialization of system calls should be used.

Change-Id: I5b4ee71be3d586f8ff597085a30f6b485cc45db1

Since we now return in all cases to the computation block we were
interrupted by a sporadic event, we could no longer distinguish between
the start and the preemption of a subtask. A new block kickoff in front
of the first computatation block makes this possible. This will unbreak alarm1f

Change-Id: I234bcd9fc1404b5b513ab2b929dc33edfd0b84c8

For the symbolic execution we can carry a calling stack with us, which
allows precise returns from function. The graph construction done in
AddFunction is only useful for the RunningTask analysis.

Change-Id: I98ce0429aa7857ffbea4b9b14612def113b7f0cf

The from the symbolic system execution also a global control flow graph
can be obtained. The global cfg is now improved by that analysis
step. We remove edges that are not found in the symbolic system
execution.

Change-Id: I75f5a48d48d68a88bbbbe648f5d5a815cbe1e032

- break up SystemGraph and PassManager
- Have a generic ISR implementation and not only the RunningTask
  variant.
- Each Alarm has an handler that calls ActivateTask

Change-Id: Ib9a754791fe2522f3b0850af3ccb66431e305db0

The idea with symbolic system execution is to go all possible paths
through the system without merging the states. The result of the SSE is
a graph where system states are connected. Each system state exists only
once in that graph, so there will be cycles.

The goal of the SSE is to get a more precise picture of system
transitions than with the dataflow analysis of the system state, since
states are not merged, when more than one state flows into an
ABB. Downside: It might and probably will (at least with ISRs) explode.

Change-Id: Ie75217df26b048f9cc206391929b5c31ae58cd71

The SpecializedSystemCalls backend exploits the RunningTask analysis to
generate very specific code for exactly one system call. It uses the
GlobalAbbInfo interface to allow a later plug'n replace of the
RunningTask analysis, which is a data flow analysis by the symbolic
execution of the system state.

Until now only ActivateTask, TerminateTask and ChainTask are specialized
and scheduling is only then specialized when only one other task is a
possible next ABB.

Change-Id: Ie46b9a03fb8cdddb00ec6940bc8d5a491bf58455

resource2 is testsuite for resource usage in combination with alarms.

Change-Id: Ia05793117ae4872e4f394384daaeaf8bb18813c1

When a subtask is ready and has more than one continuation point with
different dynamic priorities, we cannot be sure anymore that always the
higher prior block is taken.

The problem can be illustrated like this. Imagine you activate a higher
prior task, once with an resource taken (prio 6) and once without the
resource (prio 2). In both cases you're scheduled. Then your task is
surely running, but it is not sure that you return that you return
immediately to the successor of the higher prior task.

Change-Id: I74272c8b9570619a3863bc65fb18c32c865d38e3

When Resources are used, different Atomic Basic Blocks in a subtask have
different dynamic priorities. Therefore the scheduling and pruning
algorithm in RunningTask had to be adapted. Now scheduling works as
following:

1. Find all possible continuation blocks for all possibly running tasks
2. Sort them by dynamic priority.
3. From the highest dynamic priority we take all priorities until, we
   find a surely running ABB (subtask is surely running)
4. We dispatch to all those blocks.
5. When all continuations of a task have higher priority than the
   dispatched block, we're sure that this block cannot be enabled,
   otherwise it would have been scheduled before.

Change-Id: Iee9567623e6b9d23a5611bcc2b6d514468c2590e

CancelAlarm just sets the armed flag to false.

Change-Id: Ia95017a3e267050884965f625f7001514d1908b7

SetRelAlarm is the first systemcall, that really needs arguments from
userspace, that are not always deducible from the task activation
scheme. We encode the values on the userstack and pass a pointer to the
encoded values to the kernelspace. The kernelspace only reads from those
pointers, therefore we can expect no corrupting writes in outerspace.

Change-Id: I908722b00581aacd20a5cd054939c74cbc534cef

Change-Id: If4216c1b1e3455cb433af4fc0208a0eaef42212a