Skip to content

Instantly share code, notes, and snippets.

@kulp

kulp/buddy.c

Last active December 21, 2016 02:05
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kulp/3992122 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kulp/3992122 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. kulp revised this gist Jun 25, 2013. 3 changed files with 11 additions and 25 deletions.
    23 changes: 4 additions & 19 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -18,39 +18,24 @@
    #define BPERBITS 1
    #define BPER (1ul << BPERBITS)

    #ifdef TEST
    # define SI extern inline
    // clang will complain about `extern inline` functions using static variables
    // unless we use a macro like `BSTATE`
    # define BSTATE
    #else
    # define SI static inline
    # define BSTATE static
    #endif
    #define SI static inline

    // TODO need to guarantee alignment of the pool
    static char pool[RANK_0_SIZE << (RANKS - 1)];
    BSTATE unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    static const size_t pool_size = sizeof pool;
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    // bit1 : full
    BSTATE uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];
    static uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    typedef uint32_t np;
    typedef size_t sz;
    #define TN 0 /* top node */

    #ifdef TEST
    const size_t buddy_ranks = RANKS;
    const unsigned *buddy_counts = counts;
    float buddy_overhead = ((float)(sizeof nodes) + sizeof counts) / sizeof pool;
    const size_t buddy_pool_size = sizeof pool;
    #endif

    // -----------------------------------------------------------------------------
    BSTATE inline unsigned ilog2(unsigned long x)
    static inline unsigned ilog2(unsigned long x)
    {
    unsigned result = 0;
    while (x >>= 1)
    4 changes: 2 additions & 2 deletions makefile
    View file
    Original file line number Diff line number Diff line change
    @@ -20,8 +20,8 @@ buddy.o: CFLAGS += -Wall -Wextra $(PEDANTIC) -Wno-unused-value
    buddy.o: CPPFLAGS += -std=c99

    test_buddy: CPPFLAGS += -std=gnu99
    test_buddy: CPPFLAGS += -DTEST
    test_buddy: buddy.o
    test_buddy: test_buddy.o buddy.c
    $(LINK.c) -o $@ $< $(LDLIBS)

    clean:
    $(RM) test_buddy *.o
    9 changes: 5 additions & 4 deletions test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -4,10 +4,11 @@
    #include <sys/time.h>
    #include <assert.h>

    void *buddy_malloc(size_t size);
    void *buddy_calloc(size_t nelem, size_t width);
    void *buddy_realloc(void *ptr, size_t size);
    void buddy_free(void *ptr);
    #include "buddy.c"
    const size_t buddy_ranks = RANKS;
    const unsigned *buddy_counts = counts;
    float buddy_overhead = ((float)(sizeof nodes) + sizeof counts) / sizeof pool;
    const size_t buddy_pool_size = sizeof pool;

    void randomise(char *ptr, long size)
    {
  2. kulp revised this gist Jun 25, 2013. 1 changed file with 3 additions and 2 deletions.
    5 changes: 3 additions & 2 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -31,6 +31,7 @@
    // TODO need to guarantee alignment of the pool
    static char pool[RANK_0_SIZE << (RANKS - 1)];
    BSTATE unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    static const size_t pool_size = sizeof pool;
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    @@ -238,7 +239,7 @@ void *buddy_realloc(void *orig, size_t size)
    size_t rank = NODE2RANK(n);
    size_t max = RANK2BYTES(rank);
    if (size > max) {
    if (n == TN || size >= sizeof pool) {
    if (n == TN || size >= pool_size) {
    errno = ENOMEM;
    return NULL;
    }
    @@ -254,7 +255,7 @@ void *buddy_realloc(void *orig, size_t size)
    p = PARENT(p);
    }

    if (get >= sizeof pool) {
    if (get >= pool_size) {
    errno = ENOMEM;
    return NULL;
    }
  3. kulp revised this gist May 29, 2013. 1 changed file with 9 additions and 9 deletions.
    18 changes: 9 additions & 9 deletions makefile
    View file
    Original file line number Diff line number Diff line change
    @@ -1,25 +1,25 @@
    #CPPFLAGS += -std=c11
    CPPFLAGS += -std=gnu99
    PEDANTIC = -pedantic-errors -Werror

    ifneq ($(DEBUG),)
    CFLAGS += -g -O0
    LDFLAGS += -g
    CFLAGS += -g -O0
    LDFLAGS += -g
    CPPFLAGS += -DDEBUG
    else
    ARCH = native
    CFLAGS += -Os -fomit-frame-pointer -march=$(ARCH)
    ARCH = native
    CFLAGS += -Os -fomit-frame-pointer -march=$(ARCH)
    CPPFLAGS += -DNDEBUG
    endif

    #CPPFLAGS += -DNO_REALLOC
    #CPPFLAGS += -DNO_PROMOTE
    #CPPFLAGS += -DNO_DEMOTE

    PEDANTIC = -pedantic-errors -Werror
    buddy.o: CFLAGS += -Wall -Wextra $(PEDANTIC) -Wno-unused-value

    all: test_buddy

    buddy.o: CFLAGS += -Wall -Wextra $(PEDANTIC) -Wno-unused-value
    buddy.o: CPPFLAGS += -std=c99

    test_buddy: CPPFLAGS += -std=gnu99
    test_buddy: CPPFLAGS += -DTEST
    test_buddy: buddy.o

  4. kulp revised this gist May 28, 2013. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -22,14 +22,14 @@ static struct rec {
    size_t size;
    } records[COUNT];

    unsigned check_range(const void *bad, const void *good, size_t len, size_t bounds[2])
    unsigned check_range(const char *bad, const char *good, size_t len, size_t bounds[2])
    {
    if (len < 2) {
    if (len)
    return *(const char*)bad != *(const char*)good;
    return 0;
    } else if (memcmp(bad, good, len)) {
    size_t subbounds[2][2] = { 0 };
    size_t subbounds[2][2] = { { 0 } };
    int leftbad = check_range(&bad[0 ], &good[0 ], len / 2, subbounds[0]);
    int rightbad = check_range(&bad[len / 2], &good[len / 2], len - len / 2, subbounds[1]);

  5. kulp revised this gist May 28, 2013. 1 changed file with 4 additions and 2 deletions.
    6 changes: 4 additions & 2 deletions makefile
    View file
    Original file line number Diff line number Diff line change
    @@ -6,15 +6,17 @@ CFLAGS += -g -O0
    LDFLAGS += -g
    CPPFLAGS += -DDEBUG
    else
    CFLAGS += -Os -fomit-frame-pointer -march=native
    ARCH = native
    CFLAGS += -Os -fomit-frame-pointer -march=$(ARCH)
    CPPFLAGS += -DNDEBUG
    endif

    #CPPFLAGS += -DNO_REALLOC
    #CPPFLAGS += -DNO_PROMOTE
    #CPPFLAGS += -DNO_DEMOTE

    buddy.o: CFLAGS += -Wall -Wextra -pedantic-errors -Werror -Wno-unused-value
    PEDANTIC = -pedantic-errors -Werror
    buddy.o: CFLAGS += -Wall -Wextra $(PEDANTIC) -Wno-unused-value

    all: test_buddy

  6. kulp revised this gist May 28, 2013. 1 changed file with 15 additions and 11 deletions.
    26 changes: 15 additions & 11 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -18,14 +18,24 @@
    #define BPERBITS 1
    #define BPER (1ul << BPERBITS)

    #ifdef TEST
    # define SI extern inline
    // clang will complain about `extern inline` functions using static variables
    // unless we use a macro like `BSTATE`
    # define BSTATE
    #else
    # define SI static inline
    # define BSTATE static
    #endif

    // TODO need to guarantee alignment of the pool
    static char pool[RANK_0_SIZE << (RANKS - 1)];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    BSTATE unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    // bit1 : full
    static uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];
    BSTATE uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    typedef uint32_t np;
    typedef size_t sz;
    @@ -39,20 +49,14 @@ const size_t buddy_pool_size = sizeof pool;
    #endif

    // -----------------------------------------------------------------------------
    static inline unsigned ilog2(unsigned long x)
    BSTATE inline unsigned ilog2(unsigned long x)
    {
    unsigned result = 0;
    while (x >>= 1)
    result++;
    return result;
    }

    #ifdef TEST
    #define SI extern inline
    #else
    #define SI static inline
    #endif

    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI np LLINK (np n) { return (n << 1) + 1; }
    SI np RLINK (np n) { return (n << 1) + 2; }
    @@ -224,8 +228,8 @@ void *buddy_realloc(void *orig, size_t size)
    {
    if (!size) {
    buddy_free(orig);
    return NULL;
    }
    return NULL;
    }
    if (!orig)
    return buddy_malloc(size);

  7. kulp revised this gist Dec 6, 2012. 1 changed file with 7 additions and 1 deletion.
    8 changes: 7 additions & 1 deletion buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -222,9 +222,15 @@ void buddy_free(void *orig)

    void *buddy_realloc(void *orig, size_t size)
    {
    if (!size) {
    buddy_free(orig);
    return NULL;
    }
    if (!orig)
    return buddy_malloc(size);

    void *what = orig;
    np n = ADDR2NODE(what);

    size_t rank = NODE2RANK(n);
    size_t max = RANK2BYTES(rank);
    if (size > max) {
  8. kulp revised this gist Nov 22, 2012. 1 changed file with 26 additions and 16 deletions.
    42 changes: 26 additions & 16 deletions test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -16,9 +16,11 @@ void randomise(char *ptr, long size)
    }

    #define COUNT 500
    static void *list[COUNT];
    static void *checks[COUNT];
    static size_t sizes[COUNT];
    static struct rec {
    void *addr;
    void *check;
    size_t size;
    } records[COUNT];

    unsigned check_range(const void *bad, const void *good, size_t len, size_t bounds[2])
    {
    @@ -45,7 +47,7 @@ void check(int i)
    {
    size_t bounds[2];
    unsigned count;
    if ((count = check_range(list[i], checks[i], sizes[i], bounds))) {
    if ((count = check_range(records[i].addr, records[i].check, records[i].size, bounds))) {
    printf("index %i had %u bad bytes between %zd and %zd\n", i, count, bounds[0], bounds[1]);
    abort();
    }
    @@ -81,9 +83,11 @@ int main(int argc, char *argv[])
    void *c = malloc(size);
    randomise(ptr, size);
    memcpy(c, ptr, size);
    list[i] = ptr;
    checks[i] = c;
    sizes[i] = size;
    records[i] = (struct rec){
    .addr = ptr,
    .check = c,
    .size = size
    };
    checkall();

    #if !NO_REALLOC
    @@ -100,9 +104,12 @@ int main(int argc, char *argv[])
    randomise(&ptr[size], nsize - size);
    memcpy(&c[size], &ptr[size], nsize - size);
    }
    list[i] = ptr;
    checks[i] = c;
    sizes[i] = nsize;

    records[i] = (struct rec){
    .addr = ptr,
    .check = c,
    .size = nsize
    };
    checkall();

    size_t qsize = size * (0.2 + random() % 4);
    @@ -117,9 +124,12 @@ int main(int argc, char *argv[])
    randomise(&ptr[nsize], qsize - nsize);
    memcpy(&c[nsize], &ptr[nsize], qsize - nsize);
    }
    list[i] = ptr;
    checks[i] = c;
    sizes[i] = qsize;

    records[i] = (struct rec){
    .addr = ptr,
    .check = c,
    .size = qsize
    };
    checkall();
    #endif
    }
    @@ -128,10 +138,10 @@ int main(int argc, char *argv[])

    unsigned long sum = 0;
    for (int i = 0; i < COUNT; i++) {
    sum += sizes[i];
    sum += records[i].size;
    check(i);
    buddy_free(list[i]);
    free(checks[i]);
    buddy_free(records[i].addr);
    free(records[i].check);
    }

    extern const size_t buddy_pool_size;
  9. kulp revised this gist Nov 16, 2012. 1 changed file with 8 additions and 8 deletions.
    16 changes: 8 additions & 8 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -87,7 +87,7 @@ static char *NODE2ADDR(np n)
    {
    size_t base = 0;
    int i = NODE2RANK(n) + RANK_0_LOG;
    while (n > 0) {
    while (n != TN) {
    base |= ISRIGHT(n) << i;
    n = PARENT(n);
    i++;
    @@ -124,7 +124,6 @@ static np ADDR2NODE(char *key)
    }

    // -----------------------------------------------------------------------------
    // splits a node in two, returning 1 for success
    static void buddy_splitnode(np n, sz rank)
    {
    assert(("node is legally splittable", GET_LEAF(n)));
    @@ -136,9 +135,8 @@ static void buddy_splitnode(np n, sz rank)

    SET_LEAF(n,0);

    // Both child nodes are already empty leaf nodes (either because they have
    // never been written to, or because buddy_free() or buddy_realloc() left
    // them that way).
    // Both children are already empty leaf nodes, either because they have
    // never been written, or because buddy_{free,realloc} left them that way.
    }

    static void *buddy_alloc(size_t rank)
    @@ -236,6 +234,9 @@ void *buddy_realloc(void *orig, size_t size)
    }

    #if !NO_PROMOTE
    // Without the ability to promote and demote existing allocation sizes,
    // we drop from 70% utilisation to 50%. Demotion seems more important
    // than promotion, but that may be an effect of the allocation pattern.
    size_t get = max;
    np p = PARENT(n), b = SIBLING(n);
    while (GET_LEAF(b) && !GET_FULL(b) && (get <<= 1) < size && p != TN) {
    @@ -276,14 +277,13 @@ void *buddy_realloc(void *orig, size_t size)
    }
    }
    #if !NO_DEMOTE
    else while (rank > 0 && size <= (max >> 1)) {
    buddy_splitnode(n, rank--);
    else while (rank > 0 && size <= (max >>= 1)) {
    // demote node
    buddy_splitnode(n, rank--);
    // claim the left child of the newly split node
    n = LLINK(n);
    SET_FULL(n,1);

    max >>= 1;
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    }
    #endif
  10. kulp revised this gist Nov 16, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -87,7 +87,7 @@ int main(int argc, char *argv[])
    checkall();

    #if !NO_REALLOC
    size_t nsize = size * (1.2 + random() % 4);
    size_t nsize = size * (1.2 + (random() % 4) - 1);
    printf("Trying to reallocate size %zd bytes ...\n", nsize);
    ptr = buddy_realloc(ptr, nsize);
    if (!ptr) {
  11. kulp revised this gist Nov 16, 2012. 1 changed file with 47 additions and 47 deletions.
    94 changes: 47 additions & 47 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -28,6 +28,7 @@ static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    static uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    typedef uint32_t np;
    typedef size_t sz;
    #define TN 0 /* top node */

    #ifdef TEST
    @@ -46,7 +47,6 @@ static inline unsigned ilog2(unsigned long x)
    return result;
    }

    typedef size_t sz;
    #ifdef TEST
    #define SI extern inline
    #else
    @@ -124,8 +124,53 @@ static np ADDR2NODE(char *key)
    }

    // -----------------------------------------------------------------------------
    static void *buddy_alloc(size_t rank);
    // splits a node in two, returning 1 for success
    static void buddy_splitnode(np n, sz rank)
    {
    assert(("node is legally splittable", GET_LEAF(n)));

    // remove one node of our rank and create two of a smaller rank
    if (!GET_FULL(n))
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    SET_COUNT(rank - 1, GET_COUNT(rank - 1) + 2);

    SET_LEAF(n,0);

    // Both child nodes are already empty leaf nodes (either because they have
    // never been written to, or because buddy_free() or buddy_realloc() left
    // them that way).
    }

    static void *buddy_alloc(size_t rank)
    {
    for (size_t r = rank; r < RANKS; r++) {
    if (!GET_COUNT(r))
    continue;

    size_t rp = IRANK(r);
    size_t first = (1ul << rp) - 1;
    for (np n = first; n < first + (1ul << rp); n++) {
    if (!GET_VALID(n) || !GET_LEAF(n) || GET_FULL(n))
    continue;

    while (r > rank) {
    buddy_splitnode(n, r--);
    n = LLINK(n);
    }

    SET_FULL(n,1);
    SET_COUNT(r, GET_COUNT(r) - 1);
    return NODE2ADDR(n);
    }
    }

    // if we make it here, there were no nodes of appropriate size or larger
    errno = ENOMEM;
    return NULL;
    }

    // -----------------------------------------------------------------------------
    // External API
    void *buddy_malloc(size_t size)
    {
    return buddy_alloc(SIZE2RANK(size));
    @@ -177,23 +222,6 @@ void buddy_free(void *orig)
    }
    }

    // splits a node in two, returning 1 for success
    static void buddy_splitnode(np n, sz rank)
    {
    assert(("node is legally splittable", GET_LEAF(n)));

    // remove one node of our rank and create two of a smaller rank
    if (!GET_FULL(n))
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    SET_COUNT(rank - 1, GET_COUNT(rank - 1) + 2);

    SET_LEAF(n,0);

    // Both child nodes are already empty leaf nodes (either because they have
    // never been written to, or because buddy_free() or buddy_realloc() left
    // them that way).
    }

    void *buddy_realloc(void *orig, size_t size)
    {
    void *what = orig;
    @@ -263,31 +291,3 @@ void *buddy_realloc(void *orig, size_t size)
    return what;
    }

    static void *buddy_alloc(size_t rank)
    {
    for (size_t r = rank; r < RANKS; r++) {
    if (!GET_COUNT(r))
    continue;

    size_t rp = IRANK(r);
    size_t first = (1ul << rp) - 1;
    for (np n = first; n < first + (1ul << rp); n++) {
    if (!GET_VALID(n) || !GET_LEAF(n) || GET_FULL(n))
    continue;

    while (r > rank) {
    buddy_splitnode(n, r--);
    n = LLINK(n);
    }

    SET_FULL(n,1);
    SET_COUNT(r, GET_COUNT(r) - 1);
    return NODE2ADDR(n);
    }
    }

    // if we make it here, there were no nodes of appropriate size or larger
    errno = ENOMEM;
    return NULL;
    }

  12. kulp revised this gist Nov 16, 2012. 1 changed file with 5 additions and 8 deletions.
    13 changes: 5 additions & 8 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -53,14 +53,13 @@ typedef size_t sz;
    #define SI static inline
    #endif

    SI np NODE (sz i) { return i; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI np LLINK (np n) { return NODE((n << 1) + 1); }
    SI np RLINK (np n) { return NODE((n << 1) + 2); }
    SI np LLINK (np n) { return (n << 1) + 1; }
    SI np RLINK (np n) { return (n << 1) + 2; }
    SI sz ISLEFT (np n) { return n & 1; }
    SI sz ISRIGHT (np n) { return !ISLEFT(n); }
    SI np PARENT (np n) { return NODE((n - 1) >> 1); }
    SI np SIBLING (np n) { return NODE(n + ISLEFT(n) - ISRIGHT(n)); }
    SI np PARENT (np n) { return (n - 1) >> 1; }
    SI np SIBLING (np n) { return n + ISLEFT(n) - ISRIGHT(n); }
    SI sz NODE2RANK (np n) { return (n ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    @@ -272,9 +271,7 @@ static void *buddy_alloc(size_t rank)

    size_t rp = IRANK(r);
    size_t first = (1ul << rp) - 1;
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    for (np n = first; n < first + (1ul << rp); n++) {
    if (!GET_VALID(n) || !GET_LEAF(n) || GET_FULL(n))
    continue;

  13. kulp revised this gist Nov 16, 2012. 1 changed file with 13 additions and 15 deletions.
    28 changes: 13 additions & 15 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -55,15 +55,13 @@ typedef size_t sz;

    SI np NODE (sz i) { return i; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI sz DIFF(np a, np b) { return a - b; }
    SI sz INDEX (np n) { return DIFF(n, TN); }
    SI np LLINK (np n) { return NODE((INDEX(n) << 1) + 1); }
    SI np RLINK (np n) { return NODE((INDEX(n) << 1) + 2); }
    SI sz ISLEFT (np n) { return INDEX(n) & 1; }
    SI np LLINK (np n) { return NODE((n << 1) + 1); }
    SI np RLINK (np n) { return NODE((n << 1) + 2); }
    SI sz ISLEFT (np n) { return n & 1; }
    SI sz ISRIGHT (np n) { return !ISLEFT(n); }
    SI np PARENT (np n) { return NODE((INDEX(n) - 1) >> 1); }
    SI np SIBLING (np n) { return NODE(INDEX(n) + ISLEFT(n) - ISRIGHT(n)); }
    SI sz NODE2RANK (np n) { return (INDEX(n) ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI np PARENT (np n) { return NODE((n - 1) >> 1); }
    SI np SIBLING (np n) { return NODE(n + ISLEFT(n) - ISRIGHT(n)); }
    SI sz NODE2RANK (np n) { return (n ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1ul << (r + RANK_0_LOG); }
    @@ -82,15 +80,15 @@ SI void SET_BIT (np n, sz b) { *NODE2PTR(n) |= (1ul << SHAMT(n,b)); }

    SI sz GET_LEAF (np n ) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n ) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n ) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI sz GET_VALID(np n ) { return n == TN || !GET_LEAF(PARENT(n)); }
    SI void SET_LEAF (np n, sz v) { !v ? SET_BIT(n, 0) : CLR_BIT(n, 0); }
    SI void SET_FULL (np n, sz v) { v ? SET_BIT(n, 1) : CLR_BIT(n, 1); }

    static char *NODE2ADDR(np n)
    {
    size_t base = 0;
    int i = NODE2RANK(n) + RANK_0_LOG;
    while (INDEX(n) > 0) {
    while (n > 0) {
    base |= ISRIGHT(n) << i;
    n = PARENT(n);
    i++;
    @@ -151,7 +149,7 @@ void buddy_free(void *orig)
    assert(("rank is valid", rank < RANKS && rank >= 0));
    SET_COUNT(rank, GET_COUNT(rank) + 1); // mark self free
    assert(("count is legal", GET_COUNT(rank) < (1ul << (IRANK(rank) + 1))));
    if (INDEX(n) == 0)
    if (n == TN)
    return;

    np p = PARENT(n);
    @@ -170,7 +168,7 @@ void buddy_free(void *orig)

    n = p;

    if (INDEX(n) == 0)
    if (n == TN)
    break;

    p = PARENT(n);
    @@ -205,15 +203,15 @@ void *buddy_realloc(void *orig, size_t size)
    size_t rank = NODE2RANK(n);
    size_t max = RANK2BYTES(rank);
    if (size > max) {
    if (INDEX(n) == 0 || size >= sizeof pool) {
    if (n == TN || size >= sizeof pool) {
    errno = ENOMEM;
    return NULL;
    }

    #if !NO_PROMOTE
    size_t get = max;
    np p = PARENT(n), b = SIBLING(n);
    while (GET_LEAF(b) && !GET_FULL(b) && (get <<= 1) < size && INDEX(p)) {
    while (GET_LEAF(b) && !GET_FULL(b) && (get <<= 1) < size && p != TN) {
    b = SIBLING(p);
    p = PARENT(p);
    }
    @@ -236,7 +234,7 @@ void *buddy_realloc(void *orig, size_t size)
    // coalescing a full and an empty
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    rank++;
    } while (DIFF(n,p));
    } while (n != p);
    what = NODE2ADDR(n);
    memmove(what, orig, max);
    } else
  14. kulp revised this gist Nov 16, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -83,8 +83,8 @@ SI void SET_BIT (np n, sz b) { *NODE2PTR(n) |= (1ul << SHAMT(n,b)); }
    SI sz GET_LEAF (np n ) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n ) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n ) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI void SET_LEAF (np n, sz v) { CLR_BIT(n, 0); if (!v) SET_BIT(n, 0); }
    SI void SET_FULL (np n, sz v) { CLR_BIT(n, 1); if ( v) SET_BIT(n, 1); }
    SI void SET_LEAF (np n, sz v) { !v ? SET_BIT(n, 0) : CLR_BIT(n, 0); }
    SI void SET_FULL (np n, sz v) { v ? SET_BIT(n, 1) : CLR_BIT(n, 1); }

    static char *NODE2ADDR(np n)
    {
  15. kulp revised this gist Nov 16, 2012. 1 changed file with 23 additions and 34 deletions.
    57 changes: 23 additions & 34 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -181,11 +181,8 @@ void buddy_free(void *orig)
    }

    // splits a node in two, returning 1 for success
    static int buddy_splitnode(np n, sz rank)
    static void buddy_splitnode(np n, sz rank)
    {
    if (rank == 0)
    return 0;

    assert(("node is legally splittable", GET_LEAF(n)));

    // remove one node of our rank and create two of a smaller rank
    @@ -198,8 +195,6 @@ static int buddy_splitnode(np n, sz rank)
    // Both child nodes are already empty leaf nodes (either because they have
    // never been written to, or because buddy_free() or buddy_realloc() left
    // them that way).

    return 1;
    }

    void *buddy_realloc(void *orig, size_t size)
    @@ -256,39 +251,43 @@ void *buddy_realloc(void *orig, size_t size)
    }
    }
    #if !NO_DEMOTE
    else while (rank > 0 && size <= (max >> 1) && buddy_splitnode(n, rank)) {
    else while (rank > 0 && size <= (max >> 1)) {
    buddy_splitnode(n, rank--);
    // demote node
    // claim the left child of the newly split node
    n = LLINK(n);
    SET_FULL(n,1);

    max >>= 1;
    rank--;
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    }
    #endif

    return what;
    }

    static void *buddy_autosplit(size_t need_rank)
    static void *buddy_alloc(size_t rank)
    {
    for (size_t rank = need_rank; rank < RANKS; rank++) {
    if (GET_COUNT(rank)) {
    size_t rp = IRANK(rank);
    size_t first = (1ul << rp) - 1;
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    while (rank > need_rank && buddy_splitnode(n, rank--))
    n = LLINK(n);

    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    return NODE2ADDR(n);
    }
    for (size_t r = rank; r < RANKS; r++) {
    if (!GET_COUNT(r))
    continue;

    size_t rp = IRANK(r);
    size_t first = (1ul << rp) - 1;
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (!GET_VALID(n) || !GET_LEAF(n) || GET_FULL(n))
    continue;

    while (r > rank) {
    buddy_splitnode(n, r--);
    n = LLINK(n);
    }

    SET_FULL(n,1);
    SET_COUNT(r, GET_COUNT(r) - 1);
    return NODE2ADDR(n);
    }
    }

    @@ -297,13 +296,3 @@ static void *buddy_autosplit(size_t need_rank)
    return NULL;
    }

    static void *buddy_alloc(size_t rank)
    {
    if (rank >= RANKS) {
    errno = ENOMEM;
    return NULL;
    }

    return buddy_autosplit(rank);
    }

  16. kulp revised this gist Nov 16, 2012. 1 changed file with 23 additions and 48 deletions.
    71 changes: 23 additions & 48 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -19,19 +19,16 @@
    #define BPER (1ul << BPERBITS)

    // TODO need to guarantee alignment of the pool
    static char pool[RANK_0_SIZE * (1ul << (RANKS - 1))];
    static char pool[RANK_0_SIZE << (RANKS - 1)];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    // bit1 : full
    static uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    // buddy_node_ptr is a structure to do sub-word addressing into the nodes
    // array. This is important for word-addressed architectures where a single
    // element of `nodes` could take 8x of the necessary minimum size.
    typedef uint32_t np;
    static const np TN; // top node
    #define TN 0 /* top node */

    #ifdef TEST
    const size_t buddy_ranks = RANKS;
    @@ -77,18 +74,17 @@ SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    SI sz SHAMT(np n, sz b) { return NODE2SH(n) * BPER + b; }

    SI uint32_t* NODE2PTR(np n) { return &nodes[NODE2BASE(n)]; }

    SI sz GET_BIT(np n, sz b) { return (*NODE2PTR(n) >> SHAMT(n, b)) & 1; }
    SI void CLR_BIT(np n, sz b) { *NODE2PTR(n) &= ~(1 << SHAMT(n,b)); }
    SI void SET_BIT(np n, sz b) { *NODE2PTR(n) |= (1 << SHAMT(n,b)); }
    SI sz GET_BIT (np n, sz b) { return (*NODE2PTR(n) >> SHAMT(n, b)) & 1; }
    SI void CLR_BIT (np n, sz b) { *NODE2PTR(n) &= ~(1ul << SHAMT(n,b)); }
    SI void SET_BIT (np n, sz b) { *NODE2PTR(n) |= (1ul << SHAMT(n,b)); }

    SI sz GET_LEAF (np n) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI void SET_LEAF(np n, sz v) { CLR_BIT(n, 0); if (!v) SET_BIT(n, 0); }
    SI void SET_FULL(np n, sz v) { CLR_BIT(n, 1); if ( v) SET_BIT(n, 1); }
    SI sz GET_LEAF (np n ) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n ) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n ) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI void SET_LEAF (np n, sz v) { CLR_BIT(n, 0); if (!v) SET_BIT(n, 0); }
    SI void SET_FULL (np n, sz v) { CLR_BIT(n, 1); if ( v) SET_BIT(n, 1); }

    static char *NODE2ADDR(np n)
    {
    @@ -131,11 +127,11 @@ static np ADDR2NODE(char *key)
    }

    // -----------------------------------------------------------------------------
    static void *buddy_alloc(size_t size, size_t rank);
    static void *buddy_alloc(size_t rank);

    void *buddy_malloc(size_t size)
    {
    return buddy_alloc(size, SIZE2RANK(size));
    return buddy_alloc(SIZE2RANK(size));
    }

    void *buddy_calloc(size_t nelem, size_t width)
    @@ -222,7 +218,7 @@ void *buddy_realloc(void *orig, size_t size)
    #if !NO_PROMOTE
    size_t get = max;
    np p = PARENT(n), b = SIBLING(n);
    while (GET_LEAF(b) && !GET_FULL(b) && (get *= 2) < size && INDEX(p)) {
    while (GET_LEAF(b) && !GET_FULL(b) && (get <<= 1) < size && INDEX(p)) {
    b = SIBLING(p);
    p = PARENT(p);
    }
    @@ -251,7 +247,7 @@ void *buddy_realloc(void *orig, size_t size)
    } else
    #endif
    {
    what = buddy_alloc(size, SIZE2RANK(size));
    what = buddy_alloc(SIZE2RANK(size));
    if (!what)
    return NULL; // ENOMEM is already set

    @@ -275,21 +271,22 @@ void *buddy_realloc(void *orig, size_t size)
    return what;
    }

    static void *buddy_autosplit(size_t size, size_t need_rank)
    static void *buddy_autosplit(size_t need_rank)
    {
    for (size_t rank = need_rank + 1; rank < RANKS; rank++) {
    for (size_t rank = need_rank; rank < RANKS; rank++) {
    if (GET_COUNT(rank)) {
    size_t rp = IRANK(rank);
    size_t first = (1ul << rp) - 1;
    for (size_t i = 0; i < (1ul << rp); i++) {
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(first + i);
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    while (rank > need_rank && buddy_splitnode(n, rank--))
    n = LLINK(n);

    // tail-recurse after one level of splitting
    return buddy_alloc(size, rank);
    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    return NODE2ADDR(n);
    }
    }
    }
    @@ -300,35 +297,13 @@ static void *buddy_autosplit(size_t size, size_t need_rank)
    return NULL;
    }

    static void *buddy_nosplit(size_t rank)
    {
    // rp is inverted rank (counted from largest down)
    size_t rp = IRANK(rank);
    size_t first = (1ul << rp) - 1;
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    return NODE2ADDR(n);
    }
    }
    // it must not be possible to get here
    abort();
    }

    static void *buddy_alloc(size_t size, size_t rank)
    static void *buddy_alloc(size_t rank)
    {
    if (rank >= RANKS) {
    errno = ENOMEM;
    return NULL;
    }

    if (GET_COUNT(rank)) {
    return buddy_nosplit(rank);
    } else {
    return buddy_autosplit(size, rank);
    }
    return buddy_autosplit(rank);
    }

  17. kulp revised this gist Nov 16, 2012. 1 changed file with 5 additions and 2 deletions.
    7 changes: 5 additions & 2 deletions test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -138,8 +138,11 @@ int main(int argc, char *argv[])
    extern const size_t buddy_ranks;
    extern const unsigned *buddy_counts;

    printf("at peak, allocated %lu of %lu possible bytes (%5.2f%%)\n", sum,
    buddy_pool_size, sum * 100. / buddy_pool_size);
    printf( "at peak, allocated %lu of %lu possible bytes (%5.2f%%)\n"
    "effective overhead : %5.2f%%\n",
    sum, buddy_pool_size, sum * 100. / buddy_pool_size,
    buddy_overhead / ((double)sum / buddy_pool_size) * 100.
    );

    assert(buddy_counts[buddy_ranks - 1] == 1);

  18. kulp revised this gist Nov 16, 2012. 1 changed file with 13 additions and 20 deletions.
    33 changes: 13 additions & 20 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -18,13 +18,14 @@
    #define BPERBITS 1
    #define BPER (1ul << BPERBITS)

    // TODO need to guarantee alignment of the pool
    static char pool[RANK_0_SIZE * (1ul << (RANKS - 1))];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    // bit1 : full
    static unsigned nodes[(1ul << RANKS) / NPER - (1 / NPER)];
    static uint32_t nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    // buddy_node_ptr is a structure to do sub-word addressing into the nodes
    // array. This is important for word-addressed architectures where a single
    @@ -75,27 +76,19 @@ SI sz NODE2SH (np n) { return n & (NPER - 1); }
    SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    // property accessors
    SI sz GET_BIT(np n, sz b)
    {
    return (nodes[NODE2BASE(n)] >> (NODE2SH(n) * BPER + b)) & 1;
    }
    SI sz GET_LEAF (np n) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI sz SHAMT(np n, sz b) { return NODE2SH(n) * BPER + b; }

    SI void SET_LEAF(np n, sz v)
    {
    nodes[NODE2BASE(n)] &= ~( 1 << (NODE2SH(n) * BPER + 0));
    nodes[NODE2BASE(n)] |= ((!(v & 1)) << (NODE2SH(n) * BPER + 0));
    }
    SI uint32_t* NODE2PTR(np n) { return &nodes[NODE2BASE(n)]; }

    // "full" only meaningful for leaf nodes
    SI void SET_FULL(np n, sz v)
    {
    nodes[NODE2BASE(n)] &= ~( 1 << (NODE2SH(n) * BPER + 1));
    nodes[NODE2BASE(n)] |= ((v & 1) << (NODE2SH(n) * BPER + 1));
    }
    SI sz GET_BIT(np n, sz b) { return (*NODE2PTR(n) >> SHAMT(n, b)) & 1; }
    SI void CLR_BIT(np n, sz b) { *NODE2PTR(n) &= ~(1 << SHAMT(n,b)); }
    SI void SET_BIT(np n, sz b) { *NODE2PTR(n) |= (1 << SHAMT(n,b)); }

    SI sz GET_LEAF (np n) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }
    SI void SET_LEAF(np n, sz v) { CLR_BIT(n, 0); if (!v) SET_BIT(n, 0); }
    SI void SET_FULL(np n, sz v) { CLR_BIT(n, 1); if ( v) SET_BIT(n, 1); }

    static char *NODE2ADDR(np n)
    {
  19. kulp revised this gist Nov 15, 2012. 1 changed file with 1 addition and 1 deletion.
    2 changes: 1 addition & 1 deletion test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -141,7 +141,7 @@ int main(int argc, char *argv[])
    printf("at peak, allocated %lu of %lu possible bytes (%5.2f%%)\n", sum,
    buddy_pool_size, sum * 100. / buddy_pool_size);

    assert(buddy_counts[0] == 1);
    assert(buddy_counts[buddy_ranks - 1] == 1);

    return 0;
    }
  20. kulp revised this gist Nov 15, 2012. 1 changed file with 20 additions and 12 deletions.
    32 changes: 20 additions & 12 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -4,6 +4,7 @@
    #include <stdlib.h>
    #include <string.h>
    #include <limits.h>
    #include <stdint.h>

    #define RANK_0_LOG 5
    #define RANK_0_SIZE (1ul << RANK_0_LOG)
    @@ -28,10 +29,7 @@ static unsigned nodes[(1ul << RANKS) / NPER - (1 / NPER)];
    // buddy_node_ptr is a structure to do sub-word addressing into the nodes
    // array. This is important for word-addressed architectures where a single
    // element of `nodes` could take 8x of the necessary minimum size.
    typedef struct buddy_node_ptr {
    unsigned sh:NPERBITS; // number of elements (not bits !) to shift
    unsigned base:(32 - NPERBITS); // base index
    } np;
    typedef uint32_t np;
    static const np TN; // top node

    #ifdef TEST
    @@ -51,11 +49,15 @@ static inline unsigned ilog2(unsigned long x)
    }

    typedef size_t sz;
    #ifdef TEST
    #define SI extern inline
    #else
    #define SI static inline
    #endif

    SI np NODE (sz i) { return (np){ .base = i / NPER, .sh = i % NPER }; }
    SI np NODE (sz i) { return i; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI sz DIFF(np a, np b) { return *(sz*)&a - *(sz*)&b; }
    SI sz DIFF(np a, np b) { return a - b; }
    SI sz INDEX (np n) { return DIFF(n, TN); }
    SI np LLINK (np n) { return NODE((INDEX(n) << 1) + 1); }
    SI np RLINK (np n) { return NODE((INDEX(n) << 1) + 2); }
    @@ -67,26 +69,32 @@ SI sz NODE2RANK (np n) { return (INDEX(n) ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1ul << (r + RANK_0_LOG); }
    SI sz NODE2BASE (np n) { return n >> NPERBITS; }
    SI sz NODE2SH (np n) { return n & (NPER - 1); }

    SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    // property accessors
    SI sz GET_LEAF (np n) { return !((nodes[n.base] >> (n.sh * BPER + 0)) & 1); }
    SI sz GET_FULL (np n) { return ((nodes[n.base] >> (n.sh * BPER + 1)) & 1); }
    SI sz GET_BIT(np n, sz b)
    {
    return (nodes[NODE2BASE(n)] >> (NODE2SH(n) * BPER + b)) & 1;
    }
    SI sz GET_LEAF (np n) { return !GET_BIT(n, 0); }
    SI sz GET_FULL (np n) { return GET_BIT(n, 1); }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }

    SI void SET_LEAF(np n, sz v)
    {
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 0));
    nodes[n.base] |= ((!(v & 1)) << (n.sh * BPER + 0));
    nodes[NODE2BASE(n)] &= ~( 1 << (NODE2SH(n) * BPER + 0));
    nodes[NODE2BASE(n)] |= ((!(v & 1)) << (NODE2SH(n) * BPER + 0));
    }

    // "full" only meaningful for leaf nodes
    SI void SET_FULL(np n, sz v)
    {
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 1));
    nodes[n.base] |= ((v & 1) << (n.sh * BPER + 1));
    nodes[NODE2BASE(n)] &= ~( 1 << (NODE2SH(n) * BPER + 1));
    nodes[NODE2BASE(n)] |= ((v & 1) << (NODE2SH(n) * BPER + 1));
    }

    static char *NODE2ADDR(np n)
  21. kulp revised this gist Nov 15, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -51,11 +51,11 @@ static inline unsigned ilog2(unsigned long x)
    }

    typedef size_t sz;
    #define SI extern inline
    #define SI static inline

    SI np NODE (sz i) { return (np){ .base = i / NPER, .sh = i % NPER }; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI sz DIFF(np a, np b) { return (a.base - b.base) * NPER + (a.sh - b.sh); }
    SI sz DIFF(np a, np b) { return *(sz*)&a - *(sz*)&b; }
    SI sz INDEX (np n) { return DIFF(n, TN); }
    SI np LLINK (np n) { return NODE((INDEX(n) << 1) + 1); }
    SI np RLINK (np n) { return NODE((INDEX(n) << 1) + 2); }
  22. kulp revised this gist Nov 15, 2012. 1 changed file with 2 additions and 2 deletions.
    4 changes: 2 additions & 2 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -78,8 +78,8 @@ SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }

    SI void SET_LEAF(np n, sz v)
    {
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 0));
    nodes[n.base] |= ((v & 1 ^ 1) << (n.sh * BPER + 0));
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 0));
    nodes[n.base] |= ((!(v & 1)) << (n.sh * BPER + 0));
    }

    // "full" only meaningful for leaf nodes
  23. kulp revised this gist Nov 15, 2012. 2 changed files with 15 additions and 15 deletions.
    28 changes: 14 additions & 14 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -6,24 +6,24 @@
    #include <limits.h>

    #define RANK_0_LOG 5
    #define RANK_0_SIZE (1 << RANK_0_LOG)
    #define RANK_0_SIZE (1ul << RANK_0_LOG)
    #define RANKS 20

    // NPER is an architecture-dependent number.
    // NPER is nodes per element of `nodes`
    #define NPERBITS 4
    #define NPER (1 << NPERBITS)
    #define NPER (1ul << NPERBITS)
    // BPER is bits per element of `nodes`
    #define BPERBITS 1
    #define BPER (1 << BPERBITS)
    #define BPER (1ul << BPERBITS)

    static char pool[RANK_0_SIZE * (1 << (RANKS - 1))];
    static char pool[RANK_0_SIZE * (1ul << (RANKS - 1))];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    // bit1 : full
    static unsigned nodes[(1 << RANKS) / NPER - (1 / NPER)];
    static unsigned nodes[(1ul << RANKS) / NPER - (1 / NPER)];

    // buddy_node_ptr is a structure to do sub-word addressing into the nodes
    // array. This is important for word-addressed architectures where a single
    @@ -51,7 +51,7 @@ static inline unsigned ilog2(unsigned long x)
    }

    typedef size_t sz;
    #define SI static inline
    #define SI extern inline

    SI np NODE (sz i) { return (np){ .base = i / NPER, .sh = i % NPER }; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    @@ -66,14 +66,14 @@ SI np SIBLING (np n) { return NODE(INDEX(n) + ISLEFT(n) - ISRIGHT(n)); }
    SI sz NODE2RANK (np n) { return (INDEX(n) ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1 << (r + RANK_0_LOG); }
    SI sz RANK2BYTES(sz r) { return 1ul << (r + RANK_0_LOG); }

    SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    // property accessors
    SI sz GET_LEAF (np n) { return (nodes[n.base] >> (n.sh * BPER + 0)) & 1 ^ 1; }
    SI sz GET_FULL (np n) { return (nodes[n.base] >> (n.sh * BPER + 1)) & 1; }
    SI sz GET_LEAF (np n) { return !((nodes[n.base] >> (n.sh * BPER + 0)) & 1); }
    SI sz GET_FULL (np n) { return ((nodes[n.base] >> (n.sh * BPER + 1)) & 1); }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }

    SI void SET_LEAF(np n, sz v)
    @@ -153,7 +153,7 @@ void buddy_free(void *orig)
    size_t rank = NODE2RANK(n);
    assert(("rank is valid", rank < RANKS && rank >= 0));
    SET_COUNT(rank, GET_COUNT(rank) + 1); // mark self free
    assert(("count is legal", GET_COUNT(rank) < (1 << (IRANK(rank) + 1))));
    assert(("count is legal", GET_COUNT(rank) < (1ul << (IRANK(rank) + 1))));
    if (INDEX(n) == 0)
    return;

    @@ -279,8 +279,8 @@ static void *buddy_autosplit(size_t size, size_t need_rank)
    for (size_t rank = need_rank + 1; rank < RANKS; rank++) {
    if (GET_COUNT(rank)) {
    size_t rp = IRANK(rank);
    size_t first = (1 << rp) - 1;
    for (size_t i = 0; i < (1 << rp); i++) {
    size_t first = (1ul << rp) - 1;
    for (size_t i = 0; i < (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(first + i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    @@ -303,8 +303,8 @@ static void *buddy_nosplit(size_t rank)
    {
    // rp is inverted rank (counted from largest down)
    size_t rp = IRANK(rank);
    size_t first = (1 << rp) - 1;
    for (size_t i = first; i < first + (1 << rp); i++) {
    size_t first = (1ul << rp) - 1;
    for (size_t i = first; i < first + (1ul << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    2 changes: 1 addition & 1 deletion makefile
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,7 @@ buddy.o: CFLAGS += -Wall -Wextra -pedantic-errors -Werror -Wno-unused-value

    all: test_buddy

    CPPFLAGS += -DTEST
    test_buddy: CPPFLAGS += -DTEST
    test_buddy: buddy.o

    clean:
  24. kulp revised this gist Nov 15, 2012. 1 changed file with 5 additions and 10 deletions.
    15 changes: 5 additions & 10 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,7 @@
    #define BPER (1 << BPERBITS)

    static char pool[RANK_0_SIZE * (1 << (RANKS - 1))];
    static unsigned counts[RANKS] = { 1 };
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    @@ -29,17 +29,12 @@ static unsigned nodes[(1 << RANKS) / NPER - (1 / NPER)];
    // array. This is important for word-addressed architectures where a single
    // element of `nodes` could take 8x of the necessary minimum size.
    typedef struct buddy_node_ptr {
    unsigned base:(32 - NPERBITS); // base index
    unsigned sh:NPERBITS; // number of elements (not bits !) to shift
    unsigned base:(32 - NPERBITS); // base index
    } np;
    static const np TN; // top node

    #ifdef TEST
    typedef struct {
    unsigned internal :1,
    full :1;
    } node;

    const size_t buddy_ranks = RANKS;
    const unsigned *buddy_counts = counts;
    float buddy_overhead = ((float)(sizeof nodes) + sizeof counts) / sizeof pool;
    @@ -58,7 +53,7 @@ static inline unsigned ilog2(unsigned long x)
    typedef size_t sz;
    #define SI static inline

    SI np NODE (sz i) { return (np){ i / NPER, i % NPER }; }
    SI np NODE (sz i) { return (np){ .base = i / NPER, .sh = i % NPER }; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI sz DIFF(np a, np b) { return (a.base - b.base) * NPER + (a.sh - b.sh); }
    SI sz INDEX (np n) { return DIFF(n, TN); }
    @@ -73,8 +68,8 @@ SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1 << (r + RANK_0_LOG); }

    SI sz GET_COUNT(sz r) { return counts[IRANK(r)]; }
    SI void SET_COUNT(sz r, sz v) { counts[IRANK(r)] = v; }
    SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    // property accessors
    SI sz GET_LEAF (np n) { return (nodes[n.base] >> (n.sh * BPER + 0)) & 1 ^ 1; }
  25. kulp revised this gist Nov 13, 2012. 1 changed file with 24 additions and 24 deletions.
    48 changes: 24 additions & 24 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -135,18 +135,16 @@ static np ADDR2NODE(char *key)
    }

    // -----------------------------------------------------------------------------
    static void *buddy_alloc(size_t size);
    static void *buddy_alloc(size_t size, size_t rank);

    void *buddy_malloc(size_t size)
    {
    return buddy_alloc(size);
    return buddy_alloc(size, SIZE2RANK(size));
    }

    void *buddy_calloc(size_t nelem, size_t width)
    {
    void *where = buddy_alloc(nelem * width);
    memset(where, 0, nelem * width);
    return where;
    return memset(buddy_malloc(nelem * width), 0, nelem * width);
    }

    void buddy_free(void *orig)
    @@ -257,7 +255,7 @@ void *buddy_realloc(void *orig, size_t size)
    } else
    #endif
    {
    what = buddy_alloc(size);
    what = buddy_alloc(size, SIZE2RANK(size));
    if (!what)
    return NULL; // ENOMEM is already set

    @@ -295,7 +293,7 @@ static void *buddy_autosplit(size_t size, size_t need_rank)
    n = LLINK(n);

    // tail-recurse after one level of splitting
    return buddy_alloc(size);
    return buddy_alloc(size, rank);
    }
    }
    }
    @@ -306,31 +304,33 @@ static void *buddy_autosplit(size_t size, size_t need_rank)
    return NULL;
    }

    static void *buddy_alloc(size_t size)
    static void *buddy_nosplit(size_t rank)
    {
    // round up to next power of two
    unsigned rank = SIZE2RANK(size);
    // rp is inverted rank (counted from largest down)
    size_t rp = IRANK(rank);
    size_t first = (1 << rp) - 1;
    for (size_t i = first; i < first + (1 << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    return NODE2ADDR(n);
    }
    }
    // it must not be possible to get here
    abort();
    }

    static void *buddy_alloc(size_t size, size_t rank)
    {
    if (rank >= RANKS) {
    errno = ENOMEM;
    return NULL;
    }

    if (GET_COUNT(rank)) {
    // rp is inverted rank (counted from largest down)
    size_t rp = IRANK(rank);
    size_t first = (1 << rp) - 1;
    for (size_t i = first; i < first + (1 << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    return NODE2ADDR(n);
    }
    }
    // it must not be possible to get here
    abort();
    return buddy_nosplit(rank);
    } else {
    return buddy_autosplit(size, rank);
    }
  26. kulp revised this gist Nov 13, 2012. 2 changed files with 4 additions and 4 deletions.
    6 changes: 3 additions & 3 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -18,7 +18,7 @@
    #define BPER (1 << BPERBITS)

    static char pool[RANK_0_SIZE * (1 << (RANKS - 1))];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    static unsigned counts[RANKS] = { 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    // bit0 : 0=leaf, 1=internal
    @@ -73,8 +73,8 @@ SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1 << (r + RANK_0_LOG); }

    SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }
    SI sz GET_COUNT(sz r) { return counts[IRANK(r)]; }
    SI void SET_COUNT(sz r, sz v) { counts[IRANK(r)] = v; }

    // property accessors
    SI sz GET_LEAF (np n) { return (nodes[n.base] >> (n.sh * BPER + 0)) & 1 ^ 1; }
    2 changes: 1 addition & 1 deletion test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -141,7 +141,7 @@ int main(int argc, char *argv[])
    printf("at peak, allocated %lu of %lu possible bytes (%5.2f%%)\n", sum,
    buddy_pool_size, sum * 100. / buddy_pool_size);

    assert(buddy_counts[buddy_ranks - 1] == 1);
    assert(buddy_counts[0] == 1);

    return 0;
    }
  27. kulp revised this gist Nov 12, 2012. 1 changed file with 4 additions and 1 deletion.
    5 changes: 4 additions & 1 deletion buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -109,7 +109,10 @@ static char *NODE2ADDR(np n)

    static np ADDR2NODE(char *key)
    {
    size_t rank = RANKS - 1;
    // We start at the second-highest rank because we are always checking the
    // key against the midpoint of the current-rank node, which midpoint is
    // calculated using the size of the next-smallest-rank node.
    size_t rank = RANKS - 2;
    np n = TN;
    char *base = pool;

  28. kulp revised this gist Nov 11, 2012. 1 changed file with 26 additions and 1 deletion.
    27 changes: 26 additions & 1 deletion test_buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -20,10 +20,35 @@ static void *list[COUNT];
    static void *checks[COUNT];
    static size_t sizes[COUNT];

    unsigned check_range(const void *bad, const void *good, size_t len, size_t bounds[2])
    {
    if (len < 2) {
    if (len)
    return *(const char*)bad != *(const char*)good;
    return 0;
    } else if (memcmp(bad, good, len)) {
    size_t subbounds[2][2] = { 0 };
    int leftbad = check_range(&bad[0 ], &good[0 ], len / 2, subbounds[0]);
    int rightbad = check_range(&bad[len / 2], &good[len / 2], len - len / 2, subbounds[1]);

    // return leftmost and rightmost bad bounds
    bounds[0] = subbounds[ leftbad ? 0 : 1][0] + ( leftbad ? 0 : len - len / 2);
    bounds[1] = subbounds[rightbad ? 1 : 0][1] + (rightbad ? len - len / 2 : 0);

    return leftbad + rightbad;
    } else {
    return 0;
    }
    }

    void check(int i)
    {
    if (memcmp(list[i], checks[i], sizes[i]))
    size_t bounds[2];
    unsigned count;
    if ((count = check_range(list[i], checks[i], sizes[i], bounds))) {
    printf("index %i had %u bad bytes between %zd and %zd\n", i, count, bounds[0], bounds[1]);
    abort();
    }
    }

    void checkall(void)
  29. kulp revised this gist Nov 11, 2012. 1 changed file with 9 additions and 3 deletions.
    12 changes: 9 additions & 3 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -69,7 +69,8 @@ SI sz ISRIGHT (np n) { return !ISLEFT(n); }
    SI np PARENT (np n) { return NODE((INDEX(n) - 1) >> 1); }
    SI np SIBLING (np n) { return NODE(INDEX(n) + ISLEFT(n) - ISRIGHT(n)); }
    SI sz NODE2RANK (np n) { return (INDEX(n) ? NODE2RANK(PARENT(n)) : RANKS) - 1; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2((s - 1) >> RANK_0_LOG) + 1 : 0; }
    SI sz SIZE2BLKS (sz x) { return (x + RANK_0_SIZE - 1) >> RANK_0_LOG; }
    SI sz SIZE2RANK (sz s) { return s ? ilog2(SIZE2BLKS(s) - 1) + 1 : 0; }
    SI sz RANK2BYTES(sz r) { return 1 << (r + RANK_0_LOG); }

    SI sz GET_COUNT(sz r) { return counts[r]; }
    @@ -96,7 +97,7 @@ SI void SET_FULL(np n, sz v)
    static char *NODE2ADDR(np n)
    {
    size_t base = 0;
    int i = NODE2RANK(n) + RANK_0_LOG + 1;
    int i = NODE2RANK(n) + RANK_0_LOG;
    while (INDEX(n) > 0) {
    base |= ISRIGHT(n) << i;
    n = PARENT(n);
    @@ -216,7 +217,7 @@ void *buddy_realloc(void *orig, size_t size)
    size_t rank = NODE2RANK(n);
    size_t max = RANK2BYTES(rank);
    if (size > max) {
    if (INDEX(n) == 0) {
    if (INDEX(n) == 0 || size >= sizeof pool) {
    errno = ENOMEM;
    return NULL;
    }
    @@ -229,6 +230,11 @@ void *buddy_realloc(void *orig, size_t size)
    p = PARENT(p);
    }

    if (get >= sizeof pool) {
    errno = ENOMEM;
    return NULL;
    }

    if (get >= size) {
    // can promote existing allocation
    do {
  30. kulp revised this gist Nov 10, 2012. 1 changed file with 19 additions and 17 deletions.
    36 changes: 19 additions & 17 deletions buddy.c
    View file
    Original file line number Diff line number Diff line change
    @@ -11,11 +11,13 @@

    // NPER is an architecture-dependent number.
    // NPER is nodes per element of `nodes`
    #define NPER 16
    #define NPERBITS 4
    #define NPER (1 << NPERBITS)
    // BPER is bits per element of `nodes`
    #define BPER 2
    #define BPERBITS 1
    #define BPER (1 << BPERBITS)

    static char pool[RANK_0_SIZE * (1 << RANKS)];
    static char pool[RANK_0_SIZE * (1 << (RANKS - 1))];
    static unsigned counts[RANKS] = { [RANKS - 1] = 1 };
    // implicit binary tree of nodes
    // node at n has children at (2n + 1) and (2n + 2)
    @@ -27,10 +29,10 @@ static unsigned nodes[(1 << RANKS) / NPER - (1 / NPER)];
    // array. This is important for word-addressed architectures where a single
    // element of `nodes` could take 8x of the necessary minimum size.
    typedef struct buddy_node_ptr {
    unsigned *base; // base pointer
    size_t sh; // number of elements (not bits !) to shift
    unsigned base:(32 - NPERBITS); // base index
    unsigned sh:NPERBITS; // number of elements (not bits !) to shift
    } np;
    static const np TN = { nodes, 0 }; // top node
    static const np TN; // top node

    #ifdef TEST
    typedef struct {
    @@ -56,7 +58,7 @@ static inline unsigned ilog2(unsigned long x)
    typedef size_t sz;
    #define SI static inline

    SI np NODE (sz i) { return (np){ &nodes[i / NPER], i % NPER }; }
    SI np NODE (sz i) { return (np){ i / NPER, i % NPER }; }
    SI sz IRANK (sz r) { return RANKS - 1 - r; }
    SI sz DIFF(np a, np b) { return (a.base - b.base) * NPER + (a.sh - b.sh); }
    SI sz INDEX (np n) { return DIFF(n, TN); }
    @@ -74,21 +76,21 @@ SI sz GET_COUNT(sz r) { return counts[r]; }
    SI void SET_COUNT(sz r, sz v) { counts[r] = v; }

    // property accessors
    SI sz GET_LEAF (np n) { return (*n.base >> (n.sh * BPER + 0)) & 1 ^ 1; }
    SI sz GET_FULL (np n) { return (*n.base >> (n.sh * BPER + 1)) & 1; }
    SI sz GET_LEAF (np n) { return (nodes[n.base] >> (n.sh * BPER + 0)) & 1 ^ 1; }
    SI sz GET_FULL (np n) { return (nodes[n.base] >> (n.sh * BPER + 1)) & 1; }
    SI sz GET_VALID(np n) { return INDEX(n) == 0 || !GET_LEAF(PARENT(n)); }

    SI void SET_LEAF(np n, sz v)
    {
    *n.base &= ~( 1 << (n.sh * BPER + 0));
    *n.base |= ((v & 1 ^ 1) << (n.sh * BPER + 0));
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 0));
    nodes[n.base] |= ((v & 1 ^ 1) << (n.sh * BPER + 0));
    }

    // "full" only meaningful for leaf nodes
    SI void SET_FULL(np n, sz v)
    {
    *n.base &= ~( 1 << (n.sh * BPER + 1));
    *n.base |= ((v & 1) << (n.sh * BPER + 1));
    nodes[n.base] &= ~( 1 << (n.sh * BPER + 1));
    nodes[n.base] |= ((v & 1) << (n.sh * BPER + 1));
    }

    static char *NODE2ADDR(np n)
    @@ -270,7 +272,7 @@ void *buddy_realloc(void *orig, size_t size)
    return what;
    }

    static void *buddy_autosplit(size_t need_rank, size_t size)
    static void *buddy_autosplit(size_t size, size_t need_rank)
    {
    for (size_t rank = need_rank + 1; rank < RANKS; rank++) {
    if (GET_COUNT(rank)) {
    @@ -309,9 +311,9 @@ static void *buddy_alloc(size_t size)
    // rp is inverted rank (counted from largest down)
    size_t rp = IRANK(rank);
    size_t first = (1 << rp) - 1;
    for (size_t i = 0; i < (1 << rp); i++) {
    for (size_t i = first; i < first + (1 << rp); i++) {
    // i is index of nodes of appropriate rank
    np n = NODE(first + i);
    np n = NODE(i);
    if (GET_VALID(n) && GET_LEAF(n) && !GET_FULL(n)) {
    SET_FULL(n,1);
    SET_COUNT(rank, GET_COUNT(rank) - 1);
    @@ -321,7 +323,7 @@ static void *buddy_alloc(size_t size)
    // it must not be possible to get here
    abort();
    } else {
    return buddy_autosplit(rank, size);
    return buddy_autosplit(size, rank);
    }
    }