RSS

A libev tutorial and wrapper

I’ve been asked to help people out with libev example code and usage for a while but I never got around to it since I hadnt used libev in ages.  However I have a need for a simple server framework (more on this in another post).   So I figured I’d publish a simple libev tutorial.  More importantly I will create a C library that is a wrapper on top of libev to handle and maintain multiple connections in a clean and extendible way.

A quick introduction to libev is in order.  Back in the day, handling multiple network client connections was either done using multiple threads (one thread per connuction) or via asynchronous apis that multiplexed between several io events across the various connections.  Several APIs existed to enable the later (select/poll, epoll, kqueue etc).  Each of the methods had their own performance guarantees and worse still had platform dependant compatibility issues.  To get around this libevent was developed to provide a uniform interface hiding platform specific details.  Libev developed later was designed to simplify and cleanup several aspects of libevent (eg stripped down, threadsafe, low watcher overhead etc).

The core concept in libev is that of an event loop – a loop that runs continuously listening registered events and calling the associated callback functions.   Events could be io events like file descriptors ready for reads/writes, socket connections accepted etc.

With that it is time to dive in.

Let us first start with a socket server structure that is the context for all things related to a multi client TCP server:

struct LEWSocketServer {
    // A pointer to the event loop that is handling event on 
    // this server socket.
    struct ev_loop *eventLoop;

    // Host the server socket is bound to (not used for now)
    char *host;

    // Port the server is running on
    int port;

    // The socket associated with the server.
    int serverSocket;
    struct ev_io acceptWatcher;

    // A listener structure for events on this socket.
    LEWSocketServerListener *listener;
};

A simple server socket API would begin with being able to start a server:

SSSocketServer *ss_start_server(const char *host, 
                                int port,
                                SSSocketServerListener *listener);

SSSocketServerListener is a structure that helps clients manage the callbacks associated with the individual connections instead of having to deal directly with the libev api.

typedef struct LEWSocketServerListener {
    /**
     * Called when a connection was accepted.  This is an opportunity
     * for the handler of this method to create any connection specific data
     * to be created and returned so that any further activities on the connection
     * will be invoked on this object.
     *
     * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
     */
    void *(*createConnectionContext)();

    /**
     * Called when data has been received for this connection from a client.
     */
    void (*processData)(LEWConnection *connection, const char *data, size_t length);

    /**
     * Called to indicate connection was closed.
     */
    void (*connectionClosed)(LEWConnection *connection);

    /**
     * Called to ask the connection handler for data that can be written.
     * The buffer is an output parameters to be updated by the listener.
     * Return the number of bytes available in the buffer.
     */
    size_t (*writeDataRequested)(LEWConnection *connection, const char **buffer);

    /**
     * Called to indicate that nWritten bytes of data has been written and that the connection
     * object should update its write buffers to discard this data.
     */
    void (*dataWritten)(LEWConnection *connection, size_t nWritten);
} LEWSocketServerListener;

The general structure of a connection follows:

  1. Server socket is in listen state
  2. When a new connection is accepted, a client socket is created and added libev’s eventloop for read events.
  3. write events for the client socket are not enabled. The level-triggered nature of libev (by default) will cause unnecessary write event callbacks even when there is no data to be sent. So a design choice made was to make the api caller responsible to initiate writes when it had data to be sent.
  4. When data is available to be read, it is sent via the listener’s processData callback (along with the connection object associated with the client).
  5. When the caller has data to write it invokes the connection’s writeable attribute.
  6. When the writeable attribute on a connection is set, the write events on the client socket are enabled which invokes the writeDataRequested method on the caller until it return 0 (bytes).
  7. Additionally the library calls the dataWritten callback on the listener so that the client can update its own write data buffers (to pop off the written/sent data).

With this the echo server now looks like:


#include 
#include 
#include 
#include "server.h"

typedef struct EchoConnection {
    char readBuffer[4096];
    int length;
} EchoConnection;

/**
 * Called when a connection was accepted.  This is an opportunity
 * for the handler of this method to create any connection specific data
 * to be created and returned so that any further activities on the connection
 * will be invoked on this object.
 *
 * This method must NOT return NULL.  If it returns NULL, then the connection is refused.
 */
void *createConnectionContextCallback()
{
    EchoConnection *out = calloc(1, sizeof(EchoConnection));
    return out;
}

/** 
 * Called when data has been received for this connection from a client.
 */ 
void processDataCallback(LEWConnection *connection, const char *data, size_t length)
{   
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    memcpy(echoconn->readBuffer, data, length);
    echoconn->length = length;
    lew_connection_set_writeable(connection);
}   

/**
 * Called to indicate connection was closed.
 */
void connectionClosedCallback(LEWConnection *connection)
{
    printf("Connection closed...\n");
} 

/**
 * Called to ask the connection handler for data that can be written.
 * The buffer is an output parameters to be updated by the listener.
 * Return the number of bytes available in the buffer.
 */
size_t writeDataRequestedCallback(LEWConnection *connection, const char **buffer)
{
    printf("Write data requested...\n");
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    *buffer = echoconn->readBuffer;
    return echoconn->length;
}

/**
 * Called to indicate that nWritten bytes of data has been written and that the connection
 * object should update its write buffers to discard this data.
 */
void dataWrittenCallback(LEWConnection *connection, size_t nWritten)
{
    EchoConnection *echoconn = (EchoConnection *)lew_connection_get_context(connection);
    echoconn->length -= nWritten;
}

int main(void)
{
    LEWSocketServerListener listener;
    listener.createConnectionContext = createConnectionContextCallback;
    listener.processData = processDataCallback;
    listener.connectionClosed = connectionClosedCallback;
    listener.writeDataRequested = writeDataRequestedCallback;
    listener.dataWritten = dataWrittenCallback;

    lew_start_server(NULL, 9999, &listener);
}

While there is still some work to be done to handle edge cases this would be relegated to the library rather than leaking out to the client code and most the client code is actually to do with connection logic rather than messing about with event loops.

Full source code is available at: https://github.com/panyam/LibEvWrapper

 
Leave a comment

Posted by on December 12, 2015 in Uncategorized

 

2014 in review

The WordPress.com stats helper monkeys prepared a 2014 annual report for this blog.

Here’s an excerpt:

A San Francisco cable car holds 60 people. This blog was viewed about 2,800 times in 2014. If it were a cable car, it would take about 47 trips to carry that many people.

Click here to see the complete report.

 
Leave a comment

Posted by on December 29, 2014 in Uncategorized

 

Elements of Programming Interviews

This is an index to the problems from THE book being solved in haskell (and counting). Some of the trivial ones will only be attempted on demand!

Chapter 5 – Primitive Types

EPI 5.1: Find the number of bits set in a number (and Parity)


EPI 5.4: Closest integers with the same weight


EPI 5.5 – Generating Power Sets


EPI 5.6 String to Integer inter conversion functions


EPI 5.7 – Generalised conversion between bases


EPI 5.8 – Spreadsheet Column Encoding


EPI 5.9 – Elias encoding and decoding


EPI 5.10 – Greatest Common Divisor

Chapter 6 – Strings and Arrays


EPI 6.1 Dutch Flag Partition


EPI 6.3 – Max Difference


EPI 6.4 – Generalized Max Difference


EPI 6.5 – Subset summing to 0 mod n


EPI 6.6 – Longest contiguous increasing subarray


EPI 6.13 – Rotating an array


EPI 6.15 – Printing a 2D array in spiral order


EPI 6.18 – Run-Length Encoding


EPI 6.19 – Reversing words in a string

 

EPI 6.18 – Run-length Encoding

Problem:

Implement functions to run length encode a string and decode the RLE value of an encoded string.

For example “aaaabcccaa” should be encoded to “4a1b3c2a”, while “3e4f2e” would be decoded to “eeeffffee”.

Solution:

Encoding is straight forward:

run_length_encode :: [Char] -> [Char]
run_length_encode xs = run_length_encode' 0 '|' xs
    where
        run_length_encode' 0 _ [] = []
        run_length_encode' 0 _ (x:xs) = run_length_encode' 1 x xs
        run_length_encode' count curr_ch [] = (show count) ++ [curr_ch]
        run_length_encode' count curr_ch (x:xs)
            | curr_ch == x = run_length_encode' (count + 1) curr_ch xs
            | otherwise = (show count) ++ [curr_ch] ++ run_length_encode' 1 x xs

Decoding is also fairly straightforward, except we just need to accumulate the “count” before that many characters can be output:

run_length_decode :: [Char] -> [Char]
run_length_decode xs = run_length_decode' 0 xs
    where
        run_length_decode' _ [] = []
        run_length_decode' count (x:xs)
            | isDigit x = run_length_decode' ((count * 10) + (digitToInt x)) xs
            | otherwise = (replicate count x) ++ run_length_decode' 0 xs
 

Tags: , , , ,

EPI 6.15 – Printing a 2D array in spiral order

Problem:

Given an nxm 2D array of integers, print it in spiral order.

Eg for a 3×3 matrix (with the following implicit values):

1 2 3
4 5 6
7 8 9

Would be printed as “1 2 3 6 9 8 7 4 5”

Solution:

The straight forward solution is to have 4 iterations, and in each iteration to print one of the two directions (horizontal and vertical) alternatively.

However a more intuitive solution is to use vectors to create a tour starting from the index (0,0) and incrementing the next point based on the current direction and position.

First we create the concept of directions along with a couple of helper functions:

data Direction = North | East | South | West
-- Return the clockwise direction of a given direction
clockwise_of North = East
clockwise_of East = South
clockwise_of South = West
clockwise_of West = North

-- Returns the vector representing the direction
vector_of North = (0, -1)
vector_of South = (0, 1)
vector_of East = (1, 0)
vector_of West = (-1, 0)

-- The primary coordinate that will be updated when traversing in a particular direction
primary_coord North = 1
primary_coord South = 1
primary_coord East = 0
primary_coord West = 0

-- Given a direction and point, returns the next and previous points in the direction.
next_pt dir (x,y) = ((x + fst (vector_of dir)),(y + snd (vector_of dir)))
prev_pt dir (x,y) = ((x - fst (vector_of dir)),(y - snd (vector_of dir)))

Now we simply use the above helpers to start and iterate through a tour:

print_spirally width height = print_spirally' East (0,0) 0 [width, height]
    where
        print_spirally' dir (x,y) t [w,h]
            | w == 0 || h == 0 = []
            | t < [w,h] !! curr_coord = (y * width + x + 1) : print_spirally' dir (next_pt dir (x,y)) (t+1) [w,h]
            | otherwise = print_spirally' next_dir (next_pt next_dir (prev_pt dir (x,y))) 0 [next_w,next_h]
            where 
                curr_coord = primary_coord dir
                dir_vector = vector_of dir
                next_dir = clockwise_of dir
                next_dir_vector = vector_of next_dir
                next_w = w - (abs (fst next_dir_vector))
                next_h = h - (abs (snd next_dir_vector))

Couple of things to note:

* w,h represent the “remaining” width and height in the spiral as each time there is a change in direction, the available coordinate size reduces by one (height if beginning vertically, width if beginning horizontally).
* t is the number of values printed in a given direction (when this value reaches “w” or “h” depending on the direction, direction is rotated and t is reset to 0).
* When the direction needs to change (in the otherwise) the “current” point is one beyond the last point in the direction. For this reason the next point is evaluted from the previous direction in the previous point.

 

Tags: , ,

EPI 6.13 – Rotate an array

Problem:

Given an Array of n elements, design an algorithm for rotating an Array right by i positions. Only O(1) additional storage is allowed.

Solution:

The natural solution is to start from position the value at index k to k + i, repeatedly n times. This will work well if GCD(n,i) is != 1. However a general solution is to perform m jumps of size i, l times, but each time starting from the next index.

The first helper function is to perform m jumps of “size” each starting from a given index, wrapping around if necessary. For example if A = [1,2,3,4,5,6,7,8,9,10],

m_rotations A 0 3 3

would cause the following jumps: 1 -> 4 -> 7, with A resulting in:

[1, 2, 3, 1, 5, 6, 4, 8, 9, 10]
m_rotations xs index size m = elems (m_rotations' (arrayFromList xs 0) index (xs!!index) size m)
    where
        len = length xs
        m_rotations' arr curr_index curr_value size numleft 
            | curr_index < 0 || size <= 0 || numleft <= 0 = arr
            | otherwise = m_rotations' (arr // [(next_index, curr_value)]) next_index next_value size (numleft - 1)
            where
                next_index = mod (curr_index + size) len
                next_value = arr!next_index

Now we create the actual rotator method that calls m_rotations k times, where k = gcd(|A|, j).

This is:

rotate_array xs j = rotate_array' xs 0
    where 
        lxs = length xs
        j' = mod j lxs
        gcd_lxs_j = greatest_common_divisor lxs j'
        numtimes = div lxs gcd_lxs_j
        rotate_array' xs start_index
            | start_index >= gcd_lxs_j = xs
            | otherwise = m_rotations ys (j' - (start_index + 1)) j' numtimes
            where
                ys = rotate_array' xs (start_index + 1)

A simpler algorithm to perform this is very similar to reversing words in a sentence:

rotate_array_simple xs j = reverse (take j rxs) ++ reverse (drop j rxs) 
        where rxs = reverse xs
 

Tags: , ,

EPI 5.10 – Greatest Common Divisor

Problem:

Design an algorithm for computing the GCD of two numbers without using multiplication, division or the modulus operator.

Solution:
The GCD of two numbers can be computed by recursively subtracting the smaller number from the larger until one of the numbers is 0, at which point the non-zero value is the GCD.

However this can be improved by “quickly” eliminating factors of two (by inspecting the least significant bits) and doubling and halving values (via left and right shifting by 1 respectively).

greatest_common_divisor x 0 = x
greatest_common_divisor 0 y = y
greatest_common_divisor x y
    | x_is_even && y_is_even = 2 * greatest_common_divisor (x `shiftR` 1) (y `shiftR` 1)
    | x_is_odd && y_is_even = greatest_common_divisor x (y `shiftR` 1)
    | x_is_even && y_is_odd = greatest_common_divisor (x `shiftR` 1) y
    | x  y = greatest_common_divisor (x - y) x
    | otherwise = x
    where
        x_is_even = (x .&. 1) == 0
        y_is_even = (y .&. 1) == 0
        x_is_odd = not x_is_even
        y_is_odd = not y_is_even
 

Tags: , ,

 
Follow

Get every new post delivered to your Inbox.