18 June, 2011

Easy way to merge (put together) several pdf files into single one in Linux

I've noticed, that convert utility from ImageMagick is a great tool to union PDF's into single one:
convert 1.pdf 2.pdf 3.pdf single.pdf

08 June, 2011

Using fsync and fsync_range with directories

There is a non-obvious difference between possible fd argument for fsync() and fsync_range(). In Linux and NetBSD you can use fsync() to sync directory. In NetBSD there is also fsync_range() which can't be used for directories, because it expects writable fd. Originally I thought that if fsync_range() can't, then fsync() can't too, but it can.

Example below shows how to obtain file descriptor for directory to use it with fsync:
#include <stdio.h>
#include <stdlib.h>

#include <dirent.h>
#include <unistd.h>
#include <fcntl.h>
#include <errno.h>


int main() {
    int fd;
    DIR *dirp;
    int error;
    char path[] = "test_dir";

    if ((dirp = opendir(path)) == 0) {
        printf("Failed to open dir: %d\n", errno);
        return -1;
    }
    fd = dirfd(dirp);
    if (fd == -1) {
        printf("Failed to open: %d\n", errno);
        return -1;
    }

    if (fsync(fd) == -1) {
        printf("fsync failed: %d\n", errno);
        return -1;
    }
    return 0;
}

02 June, 2011

On the transparent conversion of Indirect (mutual) recursion to "no nested calls"

In a previous post I've shown how to implement functions in recursion-like style without nested call (real recursion). Implementing algorithms this way helps to save some memory (stack).
It made me wonder if we can convert/optimize mutual recursion in a way transparent to users. As basic example I chose following code:
int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}

Like in previous example I decided to use context manipulations plus function wrappers for even() and odd().
Unfortunately there is no way to wrap functions (symbols) referenced in same file as the symbol (check this). It gives some limitations: in our case even() and odd() should be separated into different source files. In common case our approach will not work with normal recursion (a()->a()) without source modification (not just recompiling with wrapper library as I wanted). Note, that if even() and odd() are in the shared library (most likely), then you can use LD_PRELOAD to wrap these functions and it will work just fine.

even.c:
int odd(int);

int even(int n)
{
    if (n == 0)
        return 1;
    else
        return odd(abs(n) - 1);
}

odd.c:
int even(int);

int odd(int n)
{
    if (n == 0)
        return 0;
    else
        return even(abs(n) - 1);
}


wrapped.c:
int __real_even(int n);
int __real_odd(int n);

volatile int even_odd_arg;
int (*volatile fp)(int);
volatile int even_odd_res;


void dispatch(ucontext_t *_return_context) {
    static ucontext_t *return_context = 0;
    if (return_context == NULL) {
        return_context = _return_context;
    }
    even_odd_res = fp(even_odd_arg);

    setcontext(return_context);
}

ucontext_t* get_dispatcher_context(ucontext_t* return_context)
{
    static ucontext_t dispatcher_context;
    static char iterator_stack[SIGSTKSZ];
    static initialized = 0;

    if (initialized)
        return &dispatcher_context;

    dispatcher_context.uc_stack.ss_sp   = iterator_stack;
    dispatcher_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&dispatcher_context);

    makecontext(&dispatcher_context, (void (*)(void)) dispatch,
                1, return_context);

    return &dispatcher_context;
}

int __wrap_even(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_even;
    swapcontext(&this_context, get_dispatcher_context(&this_context));

    return even_odd_res;
}


int __wrap_odd(int n) {
    ucontext_t this_context;
    even_odd_arg = n;
    fp = __real_odd;
    swapcontext(&this_context, get_dispatcher_context(&this_context));
    return even_odd_res;
}


main.c:
int even(int);

int main()
{
    int i;
    for (i = 0; i <= 10; i++) {
        int is_even = even(i);
        if (is_even)
            printf("%d is even\n", i);
        else
            printf("%d is odd\n", i);
    }
    return 0;
}

To compile use "gcc -c -O0 *.c; gcc *.o -Wl,-wrap,even -Wl,-wrap,odd -o test_mut_rec".

Mutual recursion without nested function calls in C

My friend Ryukzak has implemented mutual recursion library to use it without nested calls and thus memory overhead (stack). I decided I can do the same using ucontext. Here is a prototype (not generic) to calculate factorial:

struct Fac_state {
    int n;
    int acc;
};

void fac_times2(ucontext_t *other_context, ucontext_t *this_context,
               struct Fac_state *fstate)
{
    while (1) {
        fstate->acc *= fstate->n;
        fstate->n--;
        swapcontext(this_context, other_context);
    }
}


int factorial(int n)
{
    char iterator_stack[SIGSTKSZ];
    struct Fac_state fstate = {n, 1};

    ucontext_t this_context, other_context;

    other_context.uc_stack.ss_sp   = iterator_stack;
    other_context.uc_stack.ss_size = sizeof(iterator_stack);
    getcontext(&other_context);

    makecontext(&other_context, (void (*)(void)) fac_times2,
                3, &this_context, &other_context, &fstate);

    while (1) {
        if (fstate.n == 0)
            break;
        swapcontext(&this_context, &other_context);
    }
    return fstate.acc;
}

One more example in my next post.