Saturday, July 21, 2012

gcc constructor attribute

It is sometimes helpful to provide a way to 'initialize the system' when you are writing a library. Many times, this manifests itself in the form of a lib_init() call. Similarly, any convenience cleanup would be provided via lib_close(). For a concrete example look at ncurses which provides initscr() and endwin() for this use.

In the case when these routines are required (as they are in ncurses) there is an easier way to provide the proper setup without placing the onus to call these methods on the developer. GCC provides __attribute__((constructor)) and __attribute__((destructor)) which allow for calling methods when a library is loaded and unloaded respectively. These calls happen outside the scope of main. For example,

#include <stdio.h>

__attribute__((constructor)) void init() {
    fprintf (stderr, "constructor\n");
}

int main () {
    return fprintf(stderr, "main\n");
}

This program will output the following:

constructor
main


In the case of a library such as ncurses this is a perfect place to invoke the necessary initialization and cleanup routines. A simplified example library:

__attribute__((constructor))
static void setup() { do_some ("setup"); }

__attribute__((destructor))
static void breakdown() { do_some ("breakdown"); }

void mylib_method (const char * thing) { do_some (thing); }

Now, if a developer links against your library setup() is called when your library is loaded and breakdown() is called when it is unloaded. A nicety of this approach is that it provides the same functionality if the library is pulled in when the executable is loaded or at some later point (via dlopen/dlsym, for example) thus always ensuring a consistent environment for your code.

This is obviously not a fit for all libraries. Only those with setup and cleanup that can be self-contained and are always required would benefit from such an approach. In those cases, however, I prefer this method to the alternative of burdening the developer with requirements of my library.

Friday, March 23, 2012

Fisheye

I've recently been working on a design of an interface and have been doing some prototyping in d3 to support that effort. One of the effects we are considering is a 'fisheye' swell when mousing over a set of options.

I put together a small demo of what this would look like in practice. It is a work in progress for anything that may become useful but I like the idea so far.

You can find the code on github: fisheye

Sunday, February 19, 2012

LLVM pass on Windows: integrating with opt

I've been using LLVM for a few weeks now and my primary interaction with it has been writing custom passes. LLVM has a very nice system for handling user defined passes: you create an independent plug-in and load it dynamically using the opt tool. A full explanation can be found in the LLVM pass documentation.

Unfortunately, plug-ins are dynamically linked in LLVM which excludes this approach on Windows (without relying on Cygwin). For all my searching I was not able to find instructions on integrating a pass directly with the opt tool but I needed to support custom passes on Windows without using Cygwin. Mostly as a note for myself, I am listing here the steps I used to create my own custom pass as part of the opt tool; hopefully they will be useful for others as well.

I've followed as best I could the format used by existing infrastructure within LLVM. This does not mean that I have not missed something critical or what I have provided adheres to LLVM policy and/or standards.

N.B. These examples assume you are:
  •  already familiar with writing a custom pass as described by the LLVM documentation
  •  capable of understanding Makefiles and how to modify them to suit your needs
  •  using llvm-3.0 (that is the version used in these examples)
These examples will build a pass named mypass which will simply print out all function names. This pass will be part of the Custom library (also created here).

The first step is to create a new directory named Custom under llvm/lib/Transforms. This is where all passes for the new library will live. Create a very simple function pass and place it in this new directory - I used the following (MyPass.cpp)
#define DEBUG_TYPE "mypass"
#include "llvm/Function.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Custom.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;

namespace {
  struct MyPass : public FunctionPass {
    static char ID;
    MyPass() : FunctionPass(ID) {
      initializeMyPassPass(*PassRegistry::getPassRegistry());
    }

    /*
     * Just print the function name 
     */
    bool runOnFunction(Function &F) {
      bool Changed = false;
      errs().write_escaped(F.getName()) << "\n";
      return Changed;
    }
  };
}

char MyPass::ID = 0;
INITIALIZE_PASS(MyPass, "mypass", "Print all function names",
                false, false)

FunctionPass *llvm::createMyPassPass() {
  return new MyPass();
}
To load this, and multiple other custom passes, it is necessary to create an initialization routine that iterates over all passes in the library. In this example the only call in that routine is the call to the pass above. Still in the Custom directory, create the following as Custom.cpp:
#include "llvm/InitializePasses.h"
#include "llvm-c/Initialization.h"

using namespace llvm;

/// initializeCustom - Initialize all passes in the Custom library
void llvm::initializeCustom(PassRegistry &Registry) {
  initializeMyPassPass(Registry);
}

/// LLVMInitializeCustom - C binding for initializeCustom.
void LLVMInitializeCustom(LLVMPassRegistryRef R) {
  initializeCustom(*unwrap(R));
}
You will also need to support either build system with a Makefile and CMakeLists.txt.
LEVEL = ../../..
LIBRARYNAME = LLVMCustom
BUILD_ARCHIVE = 1

include $(LEVEL)/Makefile.common

add_llvm_library(LLVMCustom
  MyPass.cpp
  Custom.cpp
  )
That is the entirety of writing a new pass library for LLVM. The remainder of the work is integrating that new code into the larger system.

First, you need to define a way for LLVM to create an instance of your pass. Save the following as Custom.h in llvm/include/llvm/Transforms/
#ifndef LLVM_CUSTOM_H
#define LLVM_CUSTOM_H

namespace llvm {

FunctionPass *createMyPassPass();

}

#endif
Then you need to provide the prototypes for the two initialization routines. Add the following two lines to llvm/include/llvm/InitializePasses.h - make sure you do so inside the llvm namespace.
void initializeCustom(PassRegistry&);
void initializeMyPassPass(PassRegistry&);
Next, you need to set any passes to be linked by adding entries into llvm/include/llvm/LinkAllPasses.h
#include "llvm/Transforms/Custom.h"

// This part must reside in the constructor of struct ForcePassLinking
(void) llvm::createMyPassPass();
Updates are required to all relevant makefiles in the source tree. You will need to adjust the following to account for the additions discussed above:
  • llvm/lib/Transforms/Makefile
  • llvm/lib/Transforms/CMakeLists.txt
  • llvm/tools/opt/Makefile (add link dependency for 'custom')
  • llvm/tools/opt/CMakeLists.txt (add link dependency for 'custom')
  • llvm/tools/bugpoint/Makefile (add link dependency for 'custom')
  • llvm/tools/bugpoint/CMakeLists.txt (add link dependency for 'custom')
Finally, add the code to load the custom library in opt. Add the initialization call in the appropriate place in opt.cpp
initializeCustom(Registry);
The new pass should now be visible (on all platforms) without having to load a library with opt.
    -mergereturn                               - Unify function exit nodes
    -module-debuginfo                          - Decodes module-level debug info
    -mypass                                    - Print all function names
    -no-aa                                     - No Alias Analysis (always returns 'may' alias)
    -no-path-profile                           - No Path Profile Information

Wednesday, January 25, 2012

Return on Investment

About a year ago, a friend and I were discussing the evolution of learning new tools while working under time constraints. He claimed that, regardless of the pressure, it is almost always better to sacrifice the upfront time in learning a new tool than to stay in your comfort zone to construct the illusion of progress. By illusion he simply meant that early stage progress is shadowed by the long-term effect of having to maintain and update a homegrown solution.

He used the following illustration to convey his point:



The effect is that if you choose to develop your own tools you satisfy the immediate gratification of results but the final solution is more likely to end up as a house of cards.

I had forgotten about this conversation until recently. The program I am currently working on had me in line to provide relevant results in a shortened amount of time. I am working with the llvm compiler infrastructure and it's unique assembly language. Part of what I needed to do is understand, at a high level, the contents of an llvm assembly file. My natural reaction to this was to implement some minimal parser in Ruby to get to a working set of results quickly. Things went well until I wanted to make a decent tool for broader use within the team: I was starting to spend more time on developing the Ruby code than making headway on my tasks. Not only did I dig myself a grave in that respect but since I was quick to satisyfy the initial demand for results I set an expectation that the work was less complicated than it truly is (and will continue to be). I was building a house of cards.

I ended up scrapping the Ruby implementation and I'm now happily coming up to speed on how to manage llvm code with, well, llvm tools. This is not without effect from the leads of the program, of course. Live and learn, I suppose.

Monday, January 16, 2012

Just making sure

I was pouring over some code recently and came across one expression that really made me shake my head:
buff[strlen(buff)] = 0;
I pretty sure the intent was
buff[strlen(buff) - 1] = 0;
Either that, or they really wanted to make sure the string was null-terminated.

Friday, December 9, 2011

Underhanded C (the explanation)

In my last post I provided what would have been my entry to the underhanded C contest if it was still active. In this post I will give the details of how the code works and what bonus points I tried to target.

My solution really boils down to an off-by-one error that is hidden in a return value. A sharp observer would certainly see that I bail silently in the middle of parsing the comment section when a full luggage record was already input; that would be a huge breadcrumb to the source of the error in an investigation/review.

Due to how I handle newlines in the grab_line function it is possible to read only a newline character and return a 0-length result (considered an error in the context of grab_luggage_entry). If any entry is exactly BUFF_SIZE characters long the entire entry is silently discarded because the last read suffers from the 0-length return.

Here are the evaluation criteria and my attention to them:

Short code:
The critical section is less than 70 lines of code (with comments) but the logic for filtering made things a bit longer. This was by far the hardest target to hit with respect to the contest

Universal:
This code works on multiple platforms (Windows/Linux) but in different ways since the line endings are different ('\n' vs. '\r\n') and only '\n' is used in the check

Plausible deniability:
Comment size is unbounded in the spec so using fgets is justified/plausible as a input mechanism
getline is not portable and we want to work on multiple platforms (more justification for fgets)

Syntax coloring:
Passes syntax coloring, high compiler warnings and valgrind tests


... with bonus points for...


Mis-routing appears innocent:
The length of the line is the only qualifier to misroute making the error appear arbitrary and random in most contexts

Flexible mis-routing:
An informed operator may arbitrarily choose to trigger the behavior for nasty patrons (qualifies for spite bonus as well)
Additionally, by making the buffer size a macro (gcc -DBUFF_SIZE=128) behavior can be modified without changing the code.


While the contest appears no longer active I still enjoyed spending some time thinking up how I would write this. I've seen past winners' entries and this is certainly not of that caliber but it was nice to see that I was able to address the majority of the scoring points in at least some way.

Saturday, September 24, 2011

Underhanded C (the code)

There was some recent activity around the Underhanded C Contest. The posts are almost 2 years old now and I've attempted to contact the author without reply so I'm assuming that the contest is dead and my posting ideas for a solution won't provide any competitive advantage. If anyone finds evidence to the contrary please let me know.

In general, the premise of this round of the competition is to [mis]configure the routing of luggage in the most innocuous way possible with bonus points for plausible deniability and other features. Here is what I would have submitted if the competition was still live with explanation of the sneaky parts to follow in another post

The input specification provides a very specific format for the fields of the entries save one critical exception. I decided to target the input handling part of the system as opposed to the actual routing algorithm as it provided for several bonus point aspects. I'll explain them later but first, the code.

Here is the devious section of the code:
#define BUFF_SIZE 64

/* Represents a single entry in the luggage schedule input file */
typedef struct {
    long time;
    char lid[9], fid[7], from[4], to[4], *note;
} luggage_entry;

/*
 * Pull from input stream removing any newline. 
 * If there is info left for this record (determined by the lack of a newline), 
 * data_remains is set to 1 otherwise it is set to 0.
 * Returns number of bytes read from the stream
 */
size_t grab_line (char * buff, size_t buff_sz, int * data_remains) {
    char * nl = 0;
    if (NULL == fgets (buff, buff_sz, stdin)) { return 0; }
    nl = strrchr (buff, '\n');
    if (nl) {
        *data_remains = *nl = 0;
    } else {
        *data_remains = 1;
    }
    return strlen (buff);
}
/*
 * Returns non-zero on successful record load, 0 on failure
 */
int grab_luggage_entry (luggage_entry * e) {

    char line_buff[BUFF_SIZE] = {0}, *p = 0;
    int data_remains = 0, nbytes = 0;

    if (! grab_line (line_buff, sizeof (line_buff), &data_remains))
        return 0;

    /* Input format:  DDDDDDDDDD CCCCCCCC CCCCC? CCC CCC ?*  */
    sscanf (line_buff, "%ld %s %s %s %s%n",
            &e->time, e->lid, e->fid, e->from, e->to, &nbytes);

    /* A trailing space indicates a comment, otherwise we are done */
    p = strchr (line_buff + nbytes, ' ');
    if (!p)
        return 1;
    /* There is a comment. Grab it. */
    p += 1; /* ignore the first space */
    e->note = malloc (strlen(p) + 1);
    strcpy (e->note, p);

    /* loop until the remainder of the line is processed */
    while (data_remains) {

        size_t new_size = 0;

        if (! grab_line (line_buff, sizeof (line_buff), &data_remains)) {
            free (e->note);
            return 0;
        }

        /* Append the new data */
        new_size = strlen(e->note) + strlen(line_buff) + 1;
        e->note = realloc (e->note, new_size);
        strcat (e->note, line_buff);
    }
    return 1;
}
and the main driver...
int main (int argc, char ** argv) {

    struct entry_list *list = 0;

    /* ... */

    while (! feof (stdin) && ! ferror (stdin)) {

        struct entry entry;
        memset(&entry, 0, sizeof(entry));

        if (grab_luggage_entry (&entry))
            add_entry (list, &entry);

    }

    /* ... */
Here is a sample run with input/output as expected.
Input:
1262002831 UA129089 TP579 FRA OPO   Passengers missed first connecting flight
1262027494 UA129086 LH1230 FRA LIS
1262027495 UA129089 LH1230 FRA LIS   Next flight canceled, passengers rerouted
1262029822 UA129086 LH1450 FRA LHR  Passenger A says screw it, send me to London
1262030463 UA129086 LH1280 FRA DUB  Direct flight canceled, rerouted
1262030463 UA129086 LH1390 DUB LHR
1262033482 UA129089 LH1750 FRA LIS Layover in FRA. Route to LIS
1262040831 UA129086 TP579 OPO FRA
Output:
1262002831 UA129089 TP579 FRA OPO   Passengers missed first connecting flight
1262027494 UA129086 LH1230 FRA LIS
1262027495 UA129089 LH1230 FRA LIS   Next flight canceled, passengers rerouted
1262029822 UA129086 LH1450 FRA LHR  Passenger A says screw it, send me to London
1262030463 UA129086 LH1280 FRA DUB  Direct flight canceled, rerouted
1262030463 UA129086 LH1390 DUB LHR
1262040831 UA129086 TP579 OPO FRA
I'll follow-up with another post about how the code works and some of the bonus aspects.