[OS] Runtime Deadlock Detector

방학 중 Study의 일환으로 지도 교수님의 과제를 하면서 정리하게 된 글 입니다

Homework4 of Operating System, 2020 Spring
from https://github.com/hongshin/OperatingSystem

Overview

• Make a Runtime monitoring tool using Runtime interpositioning
  • This tool targets to detect cyclic dead locks of mutexes in multithreaded C programs using Pthread
  • The shared library that overrides Pthread APIs should be implemented
• Test programs that the runtime monitoring tool effectively detects occurence of deadlocks should be demonstrated

Pre-study

Linker

1. Symbol resolution
   • Program define and reference symbols (global variables and function)
   • Symbol definitions are stored in object file in symbol table
   • During symbol resoulution step, the linker associates each symbol reference with exactly one symbol definition
2. Relocation
   • Merge seperate code and data sections into single sections
   • Relocates symbols from their relative locations in the .o files to their final absolute memory locations in the executable
   • Updates all references to these symbols to reflect their new positions

Cyclic deadlock

• There exists a circular chain of threads such that each thread holds one or more resources that are being requested by the next thread in the chain

Shared object file(.so file)

Special type of relocatable object file that can be loaded into memory and linked dynamically, at either load time or run-time

Global variable vs Local variable

• Global variable is handled by linker
• Local variable is handled by compliler
• Compiler determines the location of the local variable from some point from stack pointer

Local symbols

• Local non-static C variables : stored on the stack
• Local static C variable : stored in either .bss or .data

Static Linking and Dynamic Linking

• Static Linking

  Programs are translated and linked using a complier driver

  source files (main.c) --(translators)--> Seperately compiled relocatable object files (main.o) --(linker)--> Fully linked executable object file (contains code and data for all functions defined in main.c and sum.c)

• Static Library Has disadvantages

  • Duplication in the stored executables (every function needs libc)
  • Duplicatoin in the running executables
  • Minor bug fixes of system libraries require each application to explicitly relink

• Dynamic Library ( Shared Library )

  • Dynamic linking can occur when executable is first loaded and run (load-time linking)
    • Common case for linux, handled automatically by the dynamic linker
    • Standard C library (libc.so) ususally dynamically linked
  • Dynamic linking can also occur after program has begun (run-time linking)
    • In linux, this is done by calls to the dlopen() interface.
      • Distributing software
      • High performance web servers
      • Runtime library interpositioning
  • Shared library routines can be shared by multiple process

Runtime interpositioning

• Adding some function between target program and library in order to monitor or intercept some behavior or calls to arbitrary function
• Runtime interpositioning can occur at
  • Compile time : When the source code is compiled
  • Link time : When the relocatable object files are statically linked to form an executable object file
  • Load/run time : When an executable object file is loaded into memory, dynamically linked and then executed
• Monitoring and profiling
  • Count number of calls to functions
  • Characterize call sites and arguments to functions
  • Malloc tracing
    • Detecting memory leaks
    • Generating address traces

LD_PRELOAD

The LD_PRELOAD environment variable tells the dynamic linker to resolve unresolve refs by looking its argument(e.g., mymalloc.so) first

Tasks

1 implement a cyclic deadlock monitor ddmon

• ddomn should implement the following cyclic deadlock detection algorithm for Pthread mutex
  • Cyclic deadlock monitoring algorithm
• Struct
  • Probe part: ddmon.c
  • Checker part: ddchk.c

2 implement a target which is multithreaded C program

• Cyclic deadlock program