Parallel DWARF parsing and improved parallel code parsing (#651) master
authorXiaozhu Meng <xmeng@cs.wisc.edu>
Mon, 13 Jan 2020 21:36:40 +0000 (15:36 -0600)
committerTim Haines <thaines.astro@gmail.com>
Mon, 13 Jan 2020 21:36:40 +0000 (15:36 -0600)
commitd233ae7596cd74201d634c2f0f7d7a0e3d628e79
tree39c363822fc6cedc02269a217b66390849919f83
parent0dffe9f69384b49858006c21667387053d3abcf2
Parallel DWARF parsing and improved parallel code parsing (#651)

* changes for parallelizing symtabapi

* Tweaks to use OpenMP (still one last reducer left)

* Mark a false race in Type.C.
    std::call_once has a barrier at the end, so anything that happens inside is visible to anything that happens after.

* Replace the Cilk reducer with an OpenMP reduction

* Remove some dead code, and move the reducer into the source file.

* Mark the last race so far, move VG macros to a separate file.

* Annotate the two core locks, negating a lot of the race reports
    Implementation is not great though, I moved mcs_init to be a real function call.
    There might be a better way to do this, will investigate at some point.

* Very awkwardly annotate a parallel hashmap by key. Consider implementing better magic.

* Wrap the callback in `omp critical`, to make it parallel-safe no matter what happens.

* Swap out the vector for a TBB concurrent_queue.

* Remove some unnessesary annotations, using a proper OpenMP handles them.

* Revert the core lock annotations, they don't actually really work.

* Macro-replace the locks with boost equivalents. Revert this commit later once the testing is complete, or refactor it fully out.

* Replace the 1-entry cache with a vector that expands with the number of threads.

* Reuse the DwarfWalker between loop iterations, to save some work

* Use the standard allocator, so that Valgrind can track it properly

* Silence some warnings

* Replace the write with a CAS, letting Valgrind mostly ignore it.

* Strengthen the condition, its good enough for now.

* Re-annotate the hash map similar to an RW lock (which it technically is)

* Nearly fully fix the function-static annotations, using a very small constructor.

* Add libc++ annotations to vgannotations, and shift includes around to make them work

* Actually do the annotations right. I learned things today.

* Tell Helgrind to ignore a few more things

* Disable checking on everything

* A few tweaks to annotation

* Add h-b arcs to the pfq rwlock

* Apparently vectors didn't work like I thought they did. Whoops.

* Elfutils is now more thread-safe, and fix the annotations to keep DRD quiet.

* Make vgannotations.h local to Dyninst, and do something C++ for the lazy inits.

* Make the custom locks first-class C++ types, and compatible with C++17's syntax.

* Replace the lock implementations with more reasonable alternatives.

* Move the annotation to handle the case where std::pair does the write

* Unify all the TBB types under a Dyninst-tagged namespace, to permit refactor

Also fix a few whitespace errors near affected lines.

* Move concurrent_hash_map annotations into the unified class.

* Shift the thread-local stuff into a template class

* Wiggle the parallel loops and fine-grain the locking for a performance boost.

* Use Boost's call_once to try and be a bit more portable

* Put some parallelism into DwarfFrameParser. Fixes blue42u/dyninst#18 and blue42u/dyninst#19

* Use atomics for the reference counting. Fixes blue42u/dyninst#4.

* Add an extra lock to the StringTable, and use it to mediate access to the internals. Fixes blue42u/dyninst#20.

* Add a lock for inlines management, fixes blue42u/dyninst#22.

* Add a lock to the function frame vectors, fixes blue42u/dyninst#21.

* Replace a map+lock with a proper parallel hashmap for performance.

* Replace a mutex'd multi_index_container with a series of concurrent_hash_maps.

* Remove the comments that were left over from Cilkscreen race detection.

...I meant to do this a long time ago...

* Fix a number of minor issues, and one possibly important typo.

* Use RAII-style classes when handling the locks.

* Add a few defines for when Valgrind annotations are turned off.

* Parallelize some stuff in Object, makes the loading of files a little faster.

* Swap out some hash_maps for their concurrent forms, more easy parallelism.

* Actually do the parsing properly, and add a lock where it was needed.

* Adding more parallelism.

* Get rid of unnecessary serial code in finalization and add parallelism for hints initialization

* Removed a lock, and attempts to fix the resulting issues that arose afterwards.

* Tweaks to remove the phase-based approach

* 1. Fix missing parsed edges caused by early resuming frames
2. Always choosing the alphabetically smallest name for a function if there are multiple

* Delete swap_busy

* 1. Handle ud2 instruction, which will raise an undefined opcode exception. Therefore, control flow should not fall through
2. When deleting a bogus function, the reference counts of the blocks in the function should be decremented

* 1. Rewrite createAndRecordFrame to allow concurrent frame creations.
2. Simplify the use of frame status: BAD_LOOKUP means frame does not exists
   and a caller should only create a new frame when the result is BAD_LOOKUP

* 1. Resume functions as soon as a function finds a ret instruction
2. Rewrite parts of the tail call correction in finalization

* Estimate parsing task size by function symbol size
and launch large tasks first

* Delete omp critical in parisng of a fram

* Get rid of unnecessary assert

* Small changes to fix some maybe-races

* Munge the annotations for c_hash_map a little, and hotfix a possible race.

* Silence a number of warnings. Identations a mess but its quieter.

* Rewrite the c_hash_map to expose the accessors as a rwlock.

* Replace lock for delayed frames with concurrent hash map

* Parallelize SymtabCodeSource::init_hints

* Parallelize CodeObject::process_hints

* Fix an infinite loop in the parsing finalization stages.

* 1. Fix parallelization for CodeObject::process_hint(): a local variable declared is moved from outside loop to inside loop
2. Fix debug print crash in Parser.C
3. Some code cleanup

* ParseAPI now initialize hints in parallel. So, if the user of ParseAPI overloads the function for creating
ParseAPI::Function, that code should be thread-safe.

Change the DynCFGFactor in dyninstAPI to use mutex to be thread-safe.

* Lasily preparing range data for functions and blocks.

* Add block ranges and clean some dead code

* Add a CMake flag to enable Valgrind annotations

* Use dyn_c_vector, and disable the parallelism for ELF stuff for now.

* Rough additions of locks in various places to make things work.

* Properly initialize the Module in all constructors.

* Fix compilation

* Get rid unnecessary boost::lock_guard and use entry lookup in loop tree construction

* Use static AArch64 decoder tables. Fixes dyninst/dyninst#630.

Other improvements include faster compile time (for affected files),
~1s less load time, ~7.8MiB smaller binary, and ~200KiB more memory usage.

Performance effects not yet tested.

* Should not delete unused ParseAPI::Function during parsing because CFGFactory will do delete all created functions in its destructor.

* Use exchange instead of store to keep Valgrind happy.

* Several fixes for analyzing .a files

1. Rewrite the OverlappingParseData to correct handle overlapping code regions.
2. In .o files, code starts at address 0, so address 0 can be a valid address.
   So, change indirect call target from address 0 to max address to represent indiret calls
3. Use CodeSource to check address validity, which would allow cross CodeRegions valid address;
   but use CodeRegion for raw code bytes, because using CodeSource may return code bytes
   from other regions that are overlapping.

* Fixes for gap parsing, which uses a different interface to call Parser

* Fix range data related to gap parsing

* Fix loop tree callee construction on Power

* Fix function removing in parsing finalization

* Fix crahses of symtabAPI tests on power

* Fix deadlock in constructing analysis graph for jump table analysis.

* Type refcount refactor, part 1: s/Type*/boost::shared_ptr<Type>/g

* Purge Type::refCount and all related code bits. The shared_ptr's handle it now.

Also add proper SFINAE on that one template, since now typeScalar and Type
have the same size (thank GCC's automatic bitfield construction).

* Add the backwards compatbility layer

* Fixup for a minor issue that should have popped up sooner

* CFGFactory class does not need to inherit boost_guard

* Fix compilation on ARM, and fix part of the backwards-compat layer.

* Adjust cmake file to new elfutils

* libdyninstAPI_RT.so should not link against libgomp, which would
cause crash at program startup time due to calling into uninitialized
rewritten libc.

* Cleanup OpenMP handling in build system

* Fix compilation when USE_OpenMP is set to OFF

* Fix a debug print crash

* Fix infinite recursion caused by missing stack unwind debug info

* Disable installing trampolines in instrumentation

* Stack walk should always have an increasing SP on x86

* Several fixes for parallel code parsing

1. Add a jump table finalization step. The assumption here is that different jump tables
   do not share entries. So, if one jump table runs into another one, we know that the
   entries that are overlapping with the next table are out-of-bound.
2. Remove edges and blocks for created by out-of-bound jump table entries
3. Handle problems of failing to resolve jump tables caused by out-of-bound entries from
   other jump table entries.

Co-authored-by: Jonathon Anderson <17242663+blue42u@users.noreply.github.com>
Co-authored-by: Tim Haines <thaines.astro@gmail.com>
102 files changed:
CMakeLists.txt
cmake/ElfUtils.cmake
cmake/Modules/FindValgrind.cmake [new file with mode: 0644]
common/CMakeLists.txt
common/h/IBSTree-fast.h
common/h/IBSTree.h
common/h/concurrent.h [new file with mode: 0644]
common/h/mcs-lock.h [deleted file]
common/h/pfq-rwlock.h [deleted file]
common/h/race-detector-annotations.h [deleted file]
common/src/arch-x86.C
common/src/concurrent.C [new file with mode: 0644]
common/src/linuxKludges.C
common/src/mcs-lock.C [deleted file]
common/src/pfq-rwlock.C
common/src/race-detector-annotations.C [deleted file]
common/src/singleton_object_pool.h
common/src/vgannotations.h [new file with mode: 0644]
dataflowAPI/h/slicing.h
dataflowAPI/src/debug_dataflow.C
dwarf/CMakeLists.txt
dwarf/h/dwarfFrameParser.h
dwarf/src/dwarfFrameParser.C
dyninstAPI/h/BPatch_type.h
dyninstAPI/src/BPatch.C
dyninstAPI/src/BPatch_addressSpace.C
dyninstAPI/src/BPatch_function.C
dyninstAPI/src/BPatch_module.C
dyninstAPI/src/BPatch_snippet.C
dyninstAPI/src/BPatch_type.C
dyninstAPI/src/Parsing.C
dyninstAPI/src/Parsing.h
dyninstAPI/src/Relocation/Springboard.C
dyninstAPI/src/function.C
dyninstAPI/src/parse-cfg.h
dyninstAPI/src/unix.C
dyninstAPI_RT/CMakeLists.txt
examples/CMakeLists.txt
instructionAPI/src/InstructionDecoderImpl.C
instructionAPI/src/Operation.C
parseAPI/CMakeLists.txt
parseAPI/h/CFG.h
parseAPI/h/CFGFactory.h
parseAPI/h/CodeSource.h
parseAPI/h/LockFreeQueue.h
parseAPI/src/Block.C
parseAPI/src/BoundFactCalculator.C
parseAPI/src/CFGFactory.C
parseAPI/src/CFGModifier.C
parseAPI/src/CodeObject.C
parseAPI/src/Function.C
parseAPI/src/IA_IAPI.C
parseAPI/src/IA_IAPI.h
parseAPI/src/IA_aarch64.h
parseAPI/src/IA_power.h
parseAPI/src/IndirectASTVisitor.C
parseAPI/src/IndirectASTVisitor.h
parseAPI/src/IndirectAnalyzer.C
parseAPI/src/IndirectAnalyzer.h
parseAPI/src/JumpTableFormatPred.C
parseAPI/src/JumpTableFormatPred.h
parseAPI/src/LoopAnalyzer.C
parseAPI/src/ParseData.C
parseAPI/src/ParseData.h
parseAPI/src/Parser-speculative.C
parseAPI/src/Parser.C
parseAPI/src/Parser.h
parseAPI/src/ParserDetails.C
parseAPI/src/ProbabilisticParser.C
parseAPI/src/ProbabilisticParser.h
parseAPI/src/SymtabCodeSource.C
parseAPI/src/ThunkData.C
parseAPI/src/debug_parse.C
parseThat/CMakeLists.txt
stackwalk/src/x86-swk.C
symtabAPI/CMakeLists.txt
symtabAPI/h/Aggregate.h
symtabAPI/h/Collections.h
symtabAPI/h/Function.h
symtabAPI/h/Module.h
symtabAPI/h/StringTable.h
symtabAPI/h/Symbol.h
symtabAPI/h/Symtab.h
symtabAPI/h/Type.h
symtabAPI/h/Variable.h
symtabAPI/src/Aggregate.C
symtabAPI/src/Collections.C
symtabAPI/src/Function.C
symtabAPI/src/Module.C
symtabAPI/src/Object-elf.C
symtabAPI/src/Object-elf.h
symtabAPI/src/Object.C
symtabAPI/src/Object.h
symtabAPI/src/Symtab-edit.C
symtabAPI/src/Symtab-lookup.C
symtabAPI/src/Symtab.C
symtabAPI/src/Type-mem.h
symtabAPI/src/Type.C
symtabAPI/src/Variable.C
symtabAPI/src/dwarfWalker.C
symtabAPI/src/dwarfWalker.h
symtabAPI/src/parseStab.C