Implementing libc: stdlib, pt. 2

Earlier this year I was focusing on bringing up an embedded framework. I've been distracted with client work, but am finally resuming framework development. The first stage in that journey is finishing off the Embedded Artistry libc so I can begin work on my memory allocation library and the C++ libraries.

Early warning: If you're unfamiliar with the the standard library functions, I recommend reading this "Guide to C stdlib functions". I will not be describing what each function does.

This article continues from the first stdlib bringup article and cites the primary source and any modifications made for these stdlib functions:

  • atof
  • strtof
  • heapsort
  • qsort
  • qsort_r (reentrant)
  • imaxabs
  • imaxdiv
  • rand
  • rand_r (reentrant)
  • srand

I also implemented the following "support" functions:

  • fls
  • flsl
  • flsll

I have decided to leave strtold (string-to-long-double) unimplemented at this time. The odds that we will need to use it on embedded systems seems exceedingly low, and I will tackle it whenever the time comes. The following functions will be covered in a future article:

  • abort
  • atexit
  • at_quick_exit
  • exit
  • _Exit
  • quick_exit

Header Changes

A new strings.h header has been added due to the fls function family, and stdlib.h has been updated to reflect the new functions.

stdlib.h Updates

The stdlib.h header has been updated to reflect the new features.

The header now include stdint.h due to the imax* function prototypes:

#include <stdint.h>

The imaxdiv_t type was defined to support the imax* functions:

typedef struct
{
    intmax_t quot;
    intmax_t rem;
} imaxdiv_t;

The following function prototypes were added:

float strtof(const char* __restrict, char** __restrict);
intmax_t imaxabs(intmax_t j);
imaxdiv_t imaxdiv(intmax_t numer, intmax_t denom);
int rand_r(unsigned int* ctx);
int rand(void);
void srand(unsigned seed);
int heapsort(void* vbase, size_t nmemb, size_t size, int (*compar)(const void*, const void*));
void qsort_r(void* a, size_t n, size_t es, void* thunk,
             int (*cmp)(void*, const void*, const void*));
void qsort(void* a, size_t n, size_t es, int (*compar)(const void*, const void*));

strings.h

The POSIX header strings.h has been added in a very basic way. The fls family of functions is defined here.

My strings.h implementation:

#ifndef __STRINGS_H_
#define __STRINGS_H_

#include <stddef.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif //__cplusplus

int fls(int mask);
int flsl(long mask);
int flsll(long long mask);

#ifdef __cplusplus
}
#endif //__cplusplus

#endif // __STRINGS_H_

atof

I imported the Apple Open Source atof, which simply serves as a strtod wrapper:

#include <stdlib.h>

double atof(const char* ascii)
{
    return (strtod(ascii, NULL));
}

strtof

I imported the old Sun Microsystems implementation of strtof rather than the more complicated gtoa library.

Since the function is long, I will refer you to the source code. I have converted to the standard type names (TRUE becomes true, CONST becomes const) and removed dead code. The logic is still the same.

imaxabs

I've imported the FreeBSD implementation of imaxabs:

#include <stdlib.h>

intmax_t imaxabs(intmax_t j)
{
    return (j < 0 ? -j : j);
}

imaxdiv

I've imported the FreeBSD implementation of imaxdiv:

#include <stdlib.h>

/* See comments in div.c for implementation details. */
imaxdiv_t imaxdiv(intmax_t numer, intmax_t denom)
{
    imaxdiv_t retval;

    retval.quot = numer / denom;
    retval.rem = numer % denom;
    if(numer >= 0 && retval.rem < 0)
    {
        retval.quot++;
        retval.rem -= denom;
    }
    return (retval);
}

rand and company

I used the Apple Open Source rand.c file as a reference for my basic rand implementation.

Since we're targeting an embedded system, I've cleaned up the code to remove the tests and the random device references. I also converted the rand, srand, and rand_r implementations to be weakly linked, so that we can override these functions on our target architectures.

The resulting rand.c implementation:

#include <stdlib.h>

static unsigned long next = 1;
static int do_rand(unsigned long* ctx)
{
#ifdef USE_WEAK_SEEDING
    /*
     * Historic implementation compatibility.
     * The random sequences do not vary much with the seed,
     * even with overflowing.
     */
    return ((*ctx = *ctx * 1103515245 + 12345) % ((unsigned long)RAND_MAX + 1));
#else /* !USE_WEAK_SEEDING */
    /*
     * Compute x = (7^5 * x) mod (2^31 - 1)
     * without overflowing 31 bits:
     *      (2^31 - 1) = 127773 * (7^5) + 2836
     * From "Random number generators: good ones are hard to find",
     * Park and Miller, Communications of the ACM, vol. 31, no. 10,
     * October 1988, p. 1195.
     */
    long hi, lo, x;

    /* Can't be initialized with 0, so use another value. */
    if(*ctx == 0)
        *ctx = 123459876;
    hi = *ctx / 127773;
    lo = *ctx % 127773;
    x = 16807 * lo - 2836 * hi;
    if(x < 0)
        x += 0x7fffffff;
    return ((*ctx = x) % ((unsigned long)RAND_MAX + 1));
#endif /* !USE_WEAK_SEEDING */
}

__attribute__((weak)) int rand_r(unsigned int* ctx)
{
    unsigned long val = (unsigned long)*ctx;
    int r = do_rand(&val);

    *ctx = (unsigned int)val;
    return (r);
}

__attribute__((weak)) int rand()
{
    return (do_rand(&next));
}

__attribute__((weak)) void srand(unsigned seed)
{
    next = seed;
}

fls Family

The fls function family was imported from Apple's Open Source libplatform. I separated the functions into three files rather than Apple's single source file.

Each implementation will prefer the builtin function version if it exists.

fls

#include <strings.h>

/*
 * Find Last Set bit
 */
int fls(int mask)
{
#if __has_builtin(__builtin_fls)
    return __builtin_fls(mask);
#elif __has_builtin(__builtin_clz)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clz(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned)mask >> 1;
    return (bit);
#endif
}

flsl

#include <strings.h>

/*
 * Find Last Set bit
 */
int flsl(long mask)
{
#if __has_builtin(__builtin_flsl)
    return __builtin_flsl(mask);
#elif __has_builtin(__builtin_clzl)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clzl(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned long)mask >> 1;
    return (bit);
#endif
}

flsll

#include <strings.h>

/*
 * Find Last Set bit
 */
int flsll(long long mask)
{
#if __has_builtin(__builtin_flsll)
    return __builtin_flsll(mask);
#elif __has_builtin(__builtin_clzll)
    if(mask == 0)
        return (0);

    return (sizeof(mask) << 3) - __builtin_clzll(mask);
#else
    int bit;

    if(mask == 0)
        return (0);
    for(bit = 1; mask != 1; bit++)
        mask = (unsigned long long)mask >> 1;
    return (bit);
#endif
}

Sorting Functions

heapsort

I imported the Apple Open Source heapsort implementation. Since the file is quite large, I will refer you directly to the source code.

qsort

I imported the Apple Open Source qsort implementation. I have kept most of the logic in place, but have removed all I_AM_QSORT_B definitions from the file. I left I_AM_QSORT_R defined so that I could implement the qsort_r function in a simple way.

Since the file is quite large, I will refer you directly to the source code.

qsort_r

I have kept the qsort_r.c strategy used in the Apple Open Source implementation:

/*
 * This file is in the public domain.  Originally written by Garrett
 * A. Wollman.
 *
 * $FreeBSD: src/lib/libc/stdlib/qsort_r.c,v 1.1 2002/09/10 02:04:49 wollman Exp $
 */
#define I_AM_QSORT_R
#include "qsort.c"

Putting it All Together

I want to showcase where I find open source function implementations and how I modify them to fit my purposes. I don't believe in re-inventing the wheel, so I am trying to reuse as much code as possible. In many cases in my career, I've seen these functions re-implemented rather than referencing quality implementations that are available and widely used.

The Embedded Artistry libc implementation is nearing completion. The current suite of functions is more than capable of meeting the needs of embedded systems developers. In future articles we will be covering the exit/abort functionality and unit testing support.

Further Reading

CMocka: Enabling XML Output

I've been adding unit tests to my C-based projects with the CMocka testing framework. Now that I have tests defined, I want my build server to run the tests and track the results for each build. Jenkins requires test results to be reported in the JUnit XML format. Luckily, CMocka has built in XML support that's quite easy to enable.

Enabling XML Output

The first step in enabling XML output is to set the CMocka output format. The easiest approach is to set the output format in your test program. This API must be called before any tests are run:

cmocka_set_message_output(CM_OUTPUT_XML);

You can also change CMocka's output behavior using the CMOCKA_MESSAGE_OUTPUT environment variable. Note that CMOCKA_MESSAGE_OUTPUT has higher precedence than the cmocka_set_message_output API, so you can override a test program's default formatting behavior.

Possible values for CMOCKA_MESSAGE_OUTPUT are stdout, subunit, tab, or xml. Options are case-insensitive.

Configuring XML Output Destination

By default, XML output will be printed to stderr. In order to write the results to a file, you must define the environment variable CMOCKA_XML_FILE. If the file already exists or cannot be created, CMocka will output the results to stderr instead.

CMOCKA_XML_FILE=testresults/libc.xml buildresults/test/libc.bin

XML Output With Multiple Test Groups

I like to organize my tests into multiple groups. This causes CMocka to generate invalid XML, as too many top level tags exist in the file. Jenkins will fail to parse the file, and you will also find that tools like xmllint will report errors.

To work around this, you can enable CMocka to generate a separate XML file for each test group. Simply include "%g" in the filename definition. The "%g" characters will be replaced by the group name.

CMOCKA_XML_FILE=testresults/%g.xml

A Note on CMocka API Usage With XML Results

You must use the cmocka_run_group_tests or cmocka_run_group_tests_name APIs to successfully generate XML test results. All other testing APIs will result in summary output instead of XML output.

Putting it All Together

Here's a sample from the Embedded Artistry libc repository. I place my test results inside of my buildresults directory, which is untracked and gets cleaned by the build server.

.PHONY: test
test:
ifeq ("$(wildcard buildresults/testresults/)","")
    @mkdir -p buildresults/testresults
else
    @rm -f buildresults/testresults/*
endif
    @CMOCKA_XML_FILE=buildresults/testresults/%g.xml buildresults/x86_64_debug/test/libc.bin

Further Reading

Embedded Artistry Jenkins Pipeline Library

I'm excited to announce a new Embedded Artistry GitHub repository: jenkins-pipeline-lib

I've been overhauling our Jenkins build server setup to use pipeline multi-branch builds. I like the pipeline format: I'm thrilled that build stages are defined in a file that is stored under SCM with the source code. Developers can look at the commands being run and debug them locally, rather than trying to figure out how the build server works.

Since I support a large number of repositories, I created a pipeline library to contain common functionality and reduce bring-up time for new projects. Functionality includes:

  • Sending email notifications
  • Sending slack notifications
  • Retreiving the build log
  • Retreiving the git change log
  • Retreiving the git commit hash
  • Convenience functions for git tagging
  • Setting GitHub commit status
  • Filling GitHub issues

Using the Pipeline Library

I recommend forking the library so that updates don't surprise you by breaking your builds.

In order to use this pipeline library in your own projects, please see the Extending with Shared Libraries Jenkins documentation.

Examples

For example pipeline files which use this library, refer to the following repositories:

Further Reading: