Roy's Blog

A Hacker's musings on Code | Tech | Life

Whilst developing Privilege Separation in dhcpcd, I had to come up with an IPC design for it. Of course, that involves creating structures.

So far, my structures in dhcpcd are long lived - or rather the scope is design to live outside of where it was created. As such they are created on the heap and are at the mercy of malloc. Generally I use calloc so that the whole area is inited to zero as uninitialised memory is bad.

So I decided to start out and see if I can just create the structures I need on the stack. Turns out I could! Yay! Now, how to you initialise a structure on the stack to all zeros? First let us consider this structure:

struct ps_addr {
    sa_family_t psa_family;
    union {
        struct in_addr psau_in_addr;
        struct in6_addr psau_in6_addr;
    } psa_u;
#define psa_in_addr     psa_u.psau_in_addr
#define psa_in6_addr    psa_u.psau_in6_addr

The first way is memset:

struct ps_addr psa;

memset(&psa, 0, sizeof(psa));
psa.psa_family = AF_INET;

But what if you could avoid memset? Luckily the C standard allows setting any member and will zero all other members. So we can do this:

struct ps_addr psa = { .psa_family = AF_INET };

Wow!!! So simple. This reduces binary size a fair bit. But then I turned on the Memory Sanitiser and boom, it crashed hard. Why?

The answer is simple - padding. Eric S Raymond gives a very good writeup about the problem. Basically, the standard will initialise any unintialised members to zero - but padding added for alignent isn't a member! So we need to ensure that our structure requires zero padding.

Here is the new struct:

struct ps_addr {
    sa_family_t psa_family;
    uint8_t psa_pad[4 - sizeof(sa_family_t)];
    union {
        struct in_addr psau_in_addr;
        struct in6_addr psau_in6_addr;
    } psa_u;
#define psa_in_addr     psa_u.psau_in_addr
#define psa_in6_addr    psa_u.psau_in6_addr

And it allows the former structure initialisation to work and memory sanitisers are happy - so happy days :) Now, if anyone can tell me what I can use instead of the magic number 4 in the above I'd be even happier!

Continue reading...

open_memstream is one of the more important functions added to POSIX libc of late. It's so important because it makes the generation of strings really easy - you no longer need to care about allocating the right amount of memory as the library will do it for you. Now, there's many functions that already help with this, such as asprintf but that's not standard and if you want to create many strings in one area you still need to care about the size of the area. You want to create an area if you have many strings, because it's more efficient for malloc and if you keep the area around and re-use it then it avoids memory fragmentation.

Now, to be clear, you have been able to do this since forever using fopen, writing to the file and then allocating your area based on the final file size. Still, it requires some memory management still but more importantly it writes to a file. Writing to a file is slow and reduces the life span of the disk you're writing to. It's only been fairly recently that tmpfs was a thing, but even today not all OS's have /tmp mounted as tmpfs. Requiring this isn't exactly ideal for a generic program to do - the setup and install should be easy. Because of all these reasons, most programs worked the string length needed and either allocated an area or string and then finally write the string. However, while saving the disk, it's also a lot more error prone because you need to work out the length of everything and that's not always trivial, especially for things like a DHCP client which is always building strings based on the information given by the DHCP server.

Here's an example of open_memstream in action:

 * Example program which manages an area of environment strings
 * to send to child programs.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

static const char *foo = "foo";
static const char *bar = "bar";

int main(void)
        char *argv[] = { "/usr/bin/env", NULL };
        char *buf, *ep, *p, **env, **envp;
        size_t buflen, nenv, i;
        FILE *fp = open_memstream(&buf, &buflen);

        fprintf(fp, "FOO=%s", foo);
        fputc('\0', fp);
        fprintf(fp, "BAR=%s", bar);
        fputc('\0', fp);

        /* We could keep fp around as our area and just rewind it. */

        /* execve relies on a trailing NULL */
        nenv = 1;
        for (p = buf, ep = p + buflen; p < ep; p++) {
                if (*p == '\0')

        /* reallocarray(3) should be standard really */
        envp = env = malloc(nenv * sizeof(char *));
        *envp++ = buf;
        for (p = buf, ep--; p < ep; p++) {
                if (*p == '\0')
                        *envp++ = p + 1;
        *envp = NULL;

        execve(argv[0], argv, env);

As you can see, we only manage the environment array handed to to execve - open_memstream is managing our string area and fprintf is working out the length each string needs to be for us. This vastly reduces the complexity and increases the security and reliabilty of creating large environment strings, which most DHCP clients do. We could also write a helper function to write the string AND the trailing NULL terminator for the string to be more efficient. You'll get to see this in dhcpcd-8 which should be released later this year.

Continue reading...

Minor update with the following changes:

  • More strict POSIX shell support
  • Interfaces have an implicit metric of 0 unless specified
  • Inline comments are stripped from nameserver and domain entries

The last upate was in 2016, so this is proving to be very stable :)

Continue reading...

Pretty much every piece of software I've seen uses a list of objects. When you need to easily grow and shrink this list easily you then need something like a Linked List. dhcpcd has used very popular and widely available BSD based queue(3), specifically a tailq. The main advantages of this type of list are:

  • Very low extra memory needed for it's implementation
  • Fast at insertion and removal operation - both are O(1)

However, it's just a list. And like any list, to find something we need to pick a starting point and then search in a single direction and match each item until we find it. This is described as O(N) and it's performance roughly corrolates to the Number of objects in the list. If you need to insert at an arbitary point (for example to order the list) you need to search it, so this is O(N) also.

But is this slow?

Typically for dhcpcd, the answer is no because on a desktop, tablet, phone or SOHO router you only have a handful of objects in all the lists. However, someone ran dhcpcd on a switch with millions of routes and dhcpcd was taking minutes of CPU time for routing table modifications. So in this corner case ... yes! dhcpcd is slow! A suggestion to improve matters was given in that report - use a Red-Black Tree instead of a Linked List. A RB tree guarantees O(log N) performance for searching. A patch was even submitted based on OpenBSD's tree implementation! This reduced the dhcpcd runtime from minutes to seconds in his situation.

Now you can't just swap in a RB Tree for a Linked List. Each object within an RB Tree has to have a unique key. Also, you need to have comparison function to define an order to the objects within the tree. Only then can you start to implement it. To find an object within the tree, you just need to know it's key and off you go. I settled on using NetBSD's rbtree(3) implementation instead of the initial suggestion to use the generic BSD tree(3). This mainly to reduce the binary size of dhcpcd because it's in libc on NetBSD and on other systems it will creates a smaller binary due to the complexity of the tree(3) macros. Testing also showed it was slightly faster and also easier to actually develop with.

So should you replace all LinkedLists with RB Trees? No! That would be silly :) After all, sometimes you don't actually need to search or order a list - a lot of the time, lists are used for push/pop operations and thus gain nothing from RB Tree.

You'll get to see this in dhcpcd-8 which should be released later this year.

Continue reading...

Welcome to 2018 :)
dhcpcd-7.0.0 has been released!

Here's the list of changes from rc4:

  • dhcp: when unicasting on L3, unicast on L2 as well
  • dhcp: when rebooting, don't set cidaddr
  • dhcp6: don't listen on IPv6 addresses when not using DHCPv6
  • dhcp: only set probe state when probing (fixes REBOOT reason)
  • linux: use IFA_F_NOPREFIXROUTE for IPv4 addresses
  • ipv6: disable kernel RA if interface is active
  • hooks: set protocol to link for link layer events

Continue reading...