Fjalar, a dynamic analysis framework for C/C++ programs
README file
Philip Guo
Robert Rudd

Last updated: 2009-12-28

A local copy of the Fjalar webpage appears here:
  ./docs/fjalar-www/index.html

This file contains information relevant for those who are interested
in customizing or extending Fjalar.

A list of improvements and extensions we'd like to see can be located 
in the TODO file in the same directory of this README.

The notes/ directory contains development notes, including instructions on
how to merge in new versions of valgrind (notes/valgrind_merge.html).


Introduction
-------------
It is recommended for Fjalar developers to become acquainted with
Valgrind and Memcheck. Valgrind is a instrumentation framework for
building dynamic analysis tools. Memcheck is a tool build on Valgrind
which is used for detecting memory errors.

More information can be found at
http://valgrind.org/docs/manual/manual.html. Of particular interest
are the following sections:

"2. Using and understanding the Valgrind Core" - A general overview of
how Valgrind works

"4. Memcheck: a memory error detector" - Covers basic usage and
concepts behind memcheck. Of particular interest is section 4.5 on the
details of Memcheck's implementation, including an overview of
Valid-value (V) bits and Valid-address (A) bits, which are used
sporadically throughout Fjalar. 

Additional information on [A,V] bits can be found in the comments in 
mc_main.c

Understanding Memcheck's error checking machinery is important for
making non-trivial changes to Fjalar as Fjalar essentially piggybacks
on top of Memcheck. Fjalar instrumentation is inserted after
Memcheck's and Fjalar makes use of Memcheck's A/V-bits to provide
information on C/C++ in a safe way. 

Known Issues
------------
* There is a significant amount of differences between comparability sets 
generated by DynComp on an x86 machine vs. an x86-64 machine. This is due 
to some imprecision in how DynComp tracks comparability. This is documented
more comprehensively in notes/dyncomp-architectural-issues

Building Fjalar
---------------
The simplest way to build the system is to run ./auto-everything.sh at the
root of the Fjalar directory (just ./fjalar not ./fjalar/valgrind/fjalar).
This will configure, build and make a local install of a small valgrind
executable and a large shared library - for an AMD64 linux based system,
this will be named fjalar-amd64-linux.  This will contain the rest of
Valgrind as well as Fjalar, Kvasir and DynComp.  The latter two are tools
built on top of the Fjalar framework used in conjunction with the Daikon
tool - see the Daikon user manual for more information:
  http://plse.cs.washington.edu/daikon/download/doc/daikon.html#Kvasir

Making a Release
----------------
Information on making a release can be found in notes/fjalar-release-notes.txt 

What follows is a summary of the contents of interesting source files:

Debugging DynComp Errors
~~~~~~~~~~~~~~~~~~~~~~~~
A tool for aiding in debugging DynComp comparability errors can be found in ./tools

Fjalar source files:
--------------------
disambig.[ch] - Implements pointer-type disambiguation

fjalar_dwarf.h - Contains definitions used for dealing with DWARF
		 information. This is separated out from the primary
		 includes below due to wanting to keep the separation
   		 between the DWARF parsing code and the main Fjalar code
		 this is the only set of definitions shared between the DWARF
		 parsing code (typedata.[ch]) the main Fjalar logic, and
		 Fjalar tools.

fjalar_include.h - This is the API that Fjalar provides to its tool.
                   Contains relevant data structures and functions.
		   This file is the defacto Developer Documentation for
	  	   Fjalar and Fjalar tools.

fjalar_main.[ch] - Most of the code that interacts with the Valgrind
                   core.  Hooks into Valgrind to perform function
                   entrance and exit tracking, start-up and tear-down
                   code, command-line option processing.

fjalar_runtime.[ch] - Contains functions that interact with the
                      Valgrind core after initialization and performs
                      run time functionality that is useful for tools,
                      such as finding out sizes of
                      dynamically-allocated arrays and finding what
                      variable corresponds to a given memory address

fjalar_select.[ch] - Implements selective program point and variable
                     tracking

fjalar_tool.h - Contains prototypes for all functions that Fjalar
                tools must implement in order to compile properly

fjalar_traversal.[ch] - Contains functions that perform traversals
                        through data structures at run time.  Each of
                        these functions takes in a callback function
                        pointer parameter, which can be used to
                        perform a specific action during each step of
                        the traversal.  This forms the core of
                        Fjalar's ability to recurse into data
                        structures during execution.

generate_fjalar_entries.[ch] - Reads the low-level DWARF info. data
                               structures produced by typedata.c and
                               translates them into higher-level
                               data structures representing functions,
                               variables, and types (defined in
                               fjalar_include.h) that will be used by
                               Fjalar and its tools.  Also contains
                               functions to produce XML output of
                               those data structures.

typedata.[ch] - Hooks into the Readelf debugging info. parser to
                construct very low-level but organized data structures
                containing the information present in the DWARF2
                debug. info.  Essentially, Readelf was meant to only
                output text, but I hacked it to make calls into
                typedata.c so that it can populate the data structures
                defined in typedata.h.


Kvasir source files (in kvasir/ sub-directory):
-----------------------------------------------
decls-output.[ch] - Outputs declarations to .decls file; mainly
                    consists of one callback action function to pass
                    into Fjalar

dtrace-output.[ch] - Outputs runtime values to .dtrace file; consists
                     of one callback action function to pass into
                     Fjalar as well as lots of auxiliary functions
                     (and macros) to print out the correct values
                     based on raw memory contents and compile-time
                     type info. provided by Fjalar

kvasir_main.[ch] - Command-line option processing, opening various
                   files, and hooks for what to do at entrances and
                   exits of functions


DynComp source files (in kvasir/ sub-directory):
------------------------------------------------
dyncomp_main.[ch] - Lots of helper functions to manage tags by
                    allocating, copying, and freeing them, etc...

dyncomp_runtime.[ch] - Performs the values-to-variable comparability
                       algorithm at every execution of every program
                       point, translates between tags and
                       comparability numbers for Daikon, and
                       implements the tag garbage collector

dyncomp_translate.[ch] - Emulates mc_translate.[ch] by performing
                         Valgrind IR instrumentation to add in tag
                         manipulations wherever there are register or
                         memory operations; the code is quite dense
                         and lots of it is copied from
                         mc_translate.[ch] and modified

union_find.[ch] - Union-find data structure implementation lifted from
                  somewhere else (cited in the comments) and modified
