#390 Integrate Deadlock Detections in Repo

[Rainer Müller]

the result of the thesis of Jan Knoblauch should become integrated into the build system (compiler and runtime and build script)

The extended files are in the attached zip file

[Anonymous]

status:

• the modified and new files are in the zip-file of the ticket
• all changed locations are marked with hfujk
• new files are in folders named hfujk

integration plan:

1. integrate changes in the compiler
   • rename the folder compiler/hfujk to compiler/DeadLockDetection
   • update the current compiler sources with the marked modifications
   • check if imported libraries must be added to the installation script
2. integrate StaticAnalyzer
   • sources should be no problem
   • update prl-script for options
   • add support in the compiler to check whether the static analysis may be applied (no REF on TASK, PROC, SEMA or BOLT is used)
3. integrate changes in the runtime system
4. integrate tests

[Rainer Müller]

status update concerning my working directory:

• there are two additional libraries in use
  • minimal-json-0.9.5.jar from Eclipse
  • commons-lang3-3.12.0.jar from apache commons
  • they must be specified in the classpath for the compiler the static analysis
• the static analysis is integrated in the file system and a Makefile is provided
• first tests with the build script showed that
  • the extension in the prl script works like java -cp "/usr/local"/bin/openpearl_compiler.jar:"/usr/local/lib/antlr-4.8-complete.jar":$APACHECOMMONS:$MJSON org/openpearl/compiler/Compiler \ $standard $PRLFLAGS $prlccinput.prl --createCfg --debugCfg --verbose --debug\ --imc-output $fn.xml \ --output $outputPrlCC
    `
  • the generated dot-files remain in the /tmp-folder
  • a simple example works from the command line, with java -cp ../../compiler/src/org/openpearl/static_analyzer-out/static_analyzer.jar:../../compiler/minimal-json-0.9.5.jar static_analyzer/StaticAnalyzer unorderedLocking

next steps:

• the update for the runtime for dynamic deadlock detection
• add a compiler option for deadlock detection
• the external libraries should be replaced by system libraries

[Rainer Müller]

replacement of external libraries done

• commons-lang3-3.12.0.jar was only used in a never called debug function
  --> function removed by comments
• minimal-json-0.9.5.jar was used in compiler and static_analyzer
  • in compiler the javax.json routines provided by ANTLR could be used
  • in static_analyzer the ANTLR rozutines could not be used, since the classes for parsing were missing
    --> a simple replacement named MyJsonObject was implemented from scratch with support of
    • int
    • boolean
    • string
    • array of strings

changes in the runtime system integrated

• some includes moved from header to implementation
• using namespace stdremoved and std:: added at the usage

testsuite/deadlockTest/unorderedLocking.prl detects deadlock in the runtime system

next steps

• update prl-script to
  • pass parameters for deadlock detection
  • move generated dot-file to source folder
  • invoke staticAnalyzer
• rename runtime/common/hfujk to runtime/common/DeadlockDetection
• find answers to the following questions
  • what is the output location for dynamic deadlock detections?
  • what should happen if a deadlock occurred?
    • Message to stderr ok?
    • Message to Log and generate an interrupt?
    • emit a signal?
  • what is required for multi module support?

[Rainer Müller]

status update

integration continued

• static deadlock detection
  • enabled by default
  • disabled with warning if REF TASK/PROC/SEMA/BOLT is used
• dynamic deadlock detection included in the runtime system

missing points

• PRLFLAGS environment variable currently not used, but is required for verifyAnnotationsPEARL90
• runtime/common/hfujk shoud become renamed to dynamicDeadlockDetection
• static deadlock detection should be provided by a simplified control flow graph to minimize heap usage (706_convert.prl causes heap overflow at my development machine and takes 2 minutes time)
• dynamic deadlock detection does not work with esp32
• maybe
  • dynamic deadlock detection enable/disable by option, if memory or computing power must be saved

[Rainer Müller]

status update

integration continued

• static deadlock detection
  • enabled by default
  • disabled with warning if REF TASK/PROC/SEMA/BOLT is used
• dynamic deadlock detection included in the runtime system

missing points

• add copyright notice to all new files
• PRLFLAGS environment variable currently not used, but is required for verifyAnnotationsPEARL90
• runtime/common/hfujk shoud become renamed to dynamicDeadlockDetection
• static deadlock detection should be provided by a simplified control flow graph to minimize heap usage (706_convert.prl causes heap overflow at my development machine and takes 2 minutes time)
• dynamic deadlock detection does not work with esp32
• maybe
  • dynamic deadlock detection enable/disable by option, if memory or computing power must be saved

[Rainer Müller]

Status update

• copyright notice added added to static and dynamic deadlock detection files
• rename in runtime from hfujk to DynamicDeadlockDetection

found items to optimize

• dynamic deadlock detection stores the names of resources and tasks as string in DeadlockOperation.h. This should be replaced by pointers to TaskCommon and Sema/Bolt
• resource allocation log
  • uses stringstream
  • ResourceAllocationGraph::isDeadlocked() to cout should print to platform dependend channel or Log

[Rainer Müller]

Status update

• copyright notice added added to static and dynamic deadlock detection files
• rename in runtime from hfujk to DynamicDeadlockDetection
• logging of deadlock operations disabled by default

found items to optimize

• dynamic deadlock detection stores the names of resources and tasks as string in DeadlockOperation.h. This should be replaced by pointers to TaskCommon and Sema/Bolt
• resource allocation log
  • uses stringstream
  • ResourceAllocationGraph::isDeadlocked() to cout should print to platform dependend channel or Log
  • enable/disable of logging lock operations should be possible by option (e.g. Log::DEADLOCK)
• dynamic deadlock detection seams to be incomplete with deadlock operation via REF SEMA/BOLT, since the deadlock operations are hard coded with task and resource name --> testsuite/build/851_ref_deref.prl fails

[Rainer Müller]

Status update

• copyright notice added added to static and dynamic deadlock detection files
• rename in runtime from hfujk to DynamicDeadlockDetection
• logging of deadlock operations disabled by default
• deadlock detection (static and dynamic) is disabled if REF TASK/PROC/SEMA or BOLT is detected

found items to optimize

• dynamic deadlock detection stores the names of resources and tasks as string in DeadlockOperation.h. This should be replaced by pointers to TaskCommon and Sema/Bolt
• resource allocation log
  • uses stringstream
  • ResourceAllocationGraph::isDeadlocked() to cout should print to platform dependend channel or Log
  • enable/disable of logging lock operations should be possible by option (e.g. Log::DEADLOCK)
• dynamic deadlock detection seams to be incomplete with deadlock operation via REF SEMA/BOLT, since the deadlock operations are hard coded with task and resource name --> testsuite/build/851_ref_deref.prl fails

[Rainer Müller]

Next steps

1. move control flow graph creation and analysis into SemanticAnalysis
2. move deadlock detection graph creation into SemanticAnalysis
   • export only relevant operations
   • regard signals
   • check for sama/bolt array to disable deadlock detection

[Rainer Müller]

Next steps

1. move control flow graph creation and analysis into SemanticAnalysis
2. move deadlock detection graph creation into SemanticAnalysis
   • export only relevant operations
   • regard function calls in expressions
   • regard signals
   • check for sema/bolt array to disable deadlock detection

[Rainer Müller]

status update

1. Export4StaticDeadlockDetection removes all nodes in PROC and TASK, which are not relevant for the deadlock detection
2. multiple module support needs unique node names in the complete PEARL application
   • the compiler got a new option '--source' which must be set to the input file of the preprocessor, if static deadlock detection is requested
   • the export uses this file name as prefix for the node names followed by the source line number
   • special characters are encoded with '@' as escape character
   • in order to create the correct node name for TASK/PROC 'END'. the grammar was modified by a rule endOfBlockLoopProcOrTask: 'END';

next steps

1. modify the static_analyzer to treat more than 1 DOT files as input
2. add information in procedures with no deadlock relevant operations in the DOT files
3. remove irrelevant local procedures from the exported DOT file
4. remove irrelevant global procedure calls from the global control flow graph
5. regard namespace in --std=OpenPEARL
6. regard signals

[Rainer Müller]

status update for item 1 of next steps above

multi module support works with

• prl script
• export by the compiler with quoted node names for unique node names in the dot file

[Rainer Müller]

commit of the current state

• static deadlock detection switched off by default in the prl-script
• the export of the control deadlock control flow graph has some problems with some test cases (loops and other stuff)
• the static analyzer already works with multiple modules
• export of identifiers with separate namespaces not tested yet

[Rainer Müller]

the ticket was divided into #429 static deadlock detection and #430 dynamic deadlock detection
--> close this ticket