Linking: why order matters

By sholsapp | Published: January 18, 2012

Having become somewhat accustom to tools like gcc(1) and ld(1) has been an interesting process — especially when the process ends in confusion. Namely, why order matters when linking static libraries to C/C++ applications, and why said static libraries should always follow the listing of objects. Like all systems, there is a reason why this matters.

While compiling a simple C++ application that used my system’s pthread library, I compiled with the following Makefile:

Exhibit A:

$ g++ -lpthread -o benchmark benchmark.o

Exhibit B:

$ g++ -o benchmark benchmark.o -lpthread

Note the only difference is the order we link the libraries in this application. However, only the applicaiton compiled with the command from Exhibit B works!

After scouring the web for an answer, I stumbled accross a post about linking with pthread at www.stackoverflow.com. An answer by a employed-russian suggested that order actually does matter. Rubbish. I wanted an explanation, and he so he pointed me at one.

The resource wasn’t all too credible looking, but provided a sensible library analogy that brought me back to the classroom days of systems programming — read it yourself here. The example doesn’t provide the implementation details to why this happens, nor does it cite documentation, but provides a cohesive analogy that makes sense.

Last but certainly not least, the analogy pointed at an interesting resource to a book-in-the-works: Linker Book.

Crazy linkers…

Posted in Programming | Tagged , , | Comments closed

Linking shared object files that aren’t explicity used.

By sholsapp | Published: January 11, 2012

Today I learned something from a nice stranger I met on the internet in the #stackoverflow channel on irc.freenode.net named at cky944.

For a personal project I’m modifying the Hoard memory allocator — a shared object library that application programs can link with to replace memory allocation code (e.g., malloc, free, etc.). Other users of Hoard can attest to the fact that one never explicit uses it, but rather implicit uses it through calls to system provided memory management functions.

Having compiled the application on several flavors of Linux, I proceeded to compile a test application that used my modified version of libhoard.so. I used the following incomplete command to compile the hoard_test application:

$ g++ -lrt -L. -lhoard -o hoard_test hoard_test.cpp

The output test application did not behave as expected, so I used ldd to inspect what shared libraries were linked with the application binary.

$ ldd hoard_test
  linux-gate.so.1 =>  (0x00aa3000)
  libstdc++.so.6 => /usr/lib/i386-linux-gnu/libstdc++.so.6 (0x008b5000)
  libm.so.6 => /lib/i386-linux-gnu/libm.so.6 (0x0048b000)
  libgcc_s.so.1 => /lib/i386-linux-gnu/libgcc_s.so.1 (0x0056d000)
  libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0x00110000)
  /lib/ld-linux.so.2 (0x003aa000)

My new friend cky944 had the insight to try explicitly using code that is contained in libhoard.so. He therefore inspected the library with nm -D libhoard.so to see what symbols the shared library exported. Using this information, he identified two functions (hoardstrdup and hoardfree) which he explicitly used in a test case.

#include <stdio.h>
 
char* hoardstrdup(char* s);
void hoardfree(void* p);
 
int main(int argc, char** argv) {
    char* thing = hoardstrdup(argc < 2 ? "world" : argv[1]);
    printf("Hello, %s!\n", thing);
    hoardfree(thing);
    return 0;
}

Viola! This code worked as expected. But why? Apparently, the latest version of Ubuntu’s linker includes a nifty feature that optimizes unused (not explicitly used in the application’s code) shared libraries out of application binaries (the Ubuntu linker includes the --as-needed option by default). Being that I was using libhoard.so implicitly — I had a problem. This default parameter has the undesirable effect of removing the libhoard.so library from the application binary at link time!

To get around this nifty feature one can notify the linker to include all shared libraries by using the gcc flag -Wl,--no-as-needed. Additionally, including a run-time path for the linker to search for libhoard.so was also necessary. This is documented at GCC’s website and can be achieved by exporting the path to libhoard.so in LD_LIBRARY_PATH or by using -Wl,-R flags.

The final compilation command used to build the test application was as follows. Note, /path/to/dir is the path to the directory where libhoard.so exists (and could have been replaced by exporting the same path into LD_LIBRARY_PATH).

$ g++ -O2 -Wall -o hoard_test hoard_test.cpp \
 -Wl,--no-as-needed                         \
 -Wl,-R,/path/to/dir                        \
 -L. -lhoard

Sure enough, this yields a test binary that includes all the references to all of the shared libraries the programmer decided to include regardless of their explicit usage within the application.

$ ldd hoard_test
  linux-gate.so.1 =>  (0x00c63000)
  libhoard.so => /export/libhoard.so (0x00709000)
  libstdc++.so.6 => /usr/lib/i386-linux-gnu/libstdc++.so.6 (0x00918000)
  libm.so.6 => /lib/i386-linux-gnu/libm.so.6 (0x00a4b000)
  libgcc_s.so.1 => /lib/i386-linux-gnu/libgcc_s.so.1 (0x00e16000)
  libc.so.6 => /lib/i386-linux-gnu/libc.so.6 (0x00110000)
  libdl.so.2 => /lib/i386-linux-gnu/libdl.so.2 (0x0066a000)
  libpthread.so.0 => /lib/i386-linux-gnu/libpthread.so.0 (0x00c3d000)
  /lib/ld-linux.so.2 (0x00f58000)

Again, a very big thank you to cky944 for working tirelessly with me to resolve this mysterious issue (upvote his efforts at www.stackoverflow.com)! =)

Posted in Programming, Ubuntu Linux | Tagged , | Comments closed

Calculating a square root.

By sholsapp | Published: December 22, 2010

I was just recently asked to calculate the square root of 17 without a math library. I couldn’t do it when I was asked to, so the question has been bugging me of awhile. I was bored today, so I decided to figure it out.

The following is a Python function that calculates the square root of a number with an optional precision argument (whose semantics I’m not yet sure about, I use it for Python’s round() built-in function to stop a potentially infinite loop; something about Python’s float representation was giving me trouble when comparing values that are very similar).

def mySqrt(of, err = 10):
    minv, maxv, squared = float(0), float(of), float(0)
    while True:
        mid = minv + ((maxv - minv) / 2)
        squared = mid ** 2
        if round(squared, err) == of:
            return mid
        elif squared > of:
            minv, maxv = minv, mid
        else:
            minv, maxv = mid, maxv

The following is a PLT Racket function that calculates the square root of a number. I hard coded a error value that is permissible otherwise PLT Racket will crunch this thing until it explodes.

;; public function assumes some amount of error is
;;  okay.
(define (mySqrt of)
  (let ([error (/ 1 1000000)])
    (mySqrtWrk 0 of of error)))
 
;; worker function to calculate a square root recursively
;;  using binary search
(define (mySqrtWrk minv maxv of err)
  (let* ([mid (+ minv (/ (- maxv minv) 2))]
         [squared (* mid mid)])
    (cond
      [(= of (rationalize squared err)) mid]
      [(< of squared) (mySqrtWrk minv mid of err)]
      [else (mySqrtWrk mid maxv of err)])))

The remainder of this article are some notes on complexity. We can think of the number line as an array of integers (even though they’re not) of size n. We know that a square root of a number is bound between 0 and n, where n is the argument we’re calculating the square root of. We can always choose a value between the minimum and maximum bounds that will divide the search space in half. For instance, if we’re calculating the square root of 17, we can test to see if 17 / 2 squared is smaller or larger than 17 and immediately rule out all numbers less than or greater than 8.5 depending on the results of the comparison. For each iteration of this algorithm we divide the search space in half.

This is binary search, which is known to have logarithmic complexity.

Posted in Programming | Tagged , , , | Comments closed