better buddy memory allocator

3 files changed, 204 insertions, 1 deletions

diff --git a/lib/buddymap.c b/lib/buddymap.c
new file mode 100644
index 0000000..6a616c9
--- /dev/null
+++ b/lib/buddymap.c
@@ -0,0 +1,168 @@
+#include "buddymap.h"
+#include "jove.h"
+
+#define BLOCK_AT_LAYER(blocks, l, i) blocks[l][i / BUDDY_BLOCK_BITS]
+#define BLOCK_BITMASK(i) (1ULL << (i % BUDDY_BLOCK_BITS))
+
+bool
+buddy_bit_test(struct BuddyMap *map, size_t l, size_t i)
+{
+    return (BLOCK_AT_LAYER(map->blocks, l, i) & BLOCK_BITMASK(i)) > 0;
+}
+
+void
+buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i)
+{
+    size_t wi = i << l;
+    size_t bits = 1ULL << l;
+    for(size_t wl = 0; wl < map->orders; wl++) {
+        if(bits == 0) {
+            if(buddy_bit_test(map, wl - 1, (wi << 1) + 1)) bits = 1;
+        }
+        for(size_t bit = 0; bit < bits; bit++) {
+            size_t rbit = bit + wi;
+            if(l == 0 && !buddy_bit_test(map, 0, rbit)) map->free--;
+            BLOCK_AT_LAYER(map->blocks, wl, rbit) |= BLOCK_BITMASK(rbit);
+        }
+        bits >>= 1;
+        wi >>= 1;
+    }
+}
+
+void
+buddy_bit_free(struct BuddyMap *map, size_t l, size_t i)
+{
+    size_t wi = i << l;
+    size_t bits = 1ULL << l;
+    for(size_t wl = 0; wl < map->orders; wl++) {
+        if(bits == 0) bits = 1;
+        for(size_t bit = 0; bit < bits; bit++) {
+            size_t rbit = bit + wi;
+            if(l == 0 && buddy_bit_test(map, 0, rbit)) map->free++;
+            BLOCK_AT_LAYER(map->blocks, wl, rbit) &= ~BLOCK_BITMASK(rbit);
+        }
+        bits >>= 1;
+        wi >>= 1;
+    }
+}
+
+static void
+s_buddy_op_range(
+        struct BuddyMap *map,
+        size_t l,
+        size_t start,
+        size_t end,
+        void (*op)(struct BuddyMap*, size_t, size_t))
+{
+    size_t layerw = 1ULL << l;
+    size_t start_off = start % layerw;
+    size_t end_off = end % layerw;
+
+    size_t start_real = start + (start_off > 0 ? (layerw - start_off) : 0);
+    size_t end_real = end - end_off;
+
+    if(start_real != start) s_buddy_op_range(map, l - 1, start, start_real, op);
+    if(end_real != end) s_buddy_op_range(map, l - 1, end_real, end, op);
+
+    size_t start_bit = start_real >> l;
+    size_t end_bit = end_real >> l;
+    if(start_bit == end_bit || end_bit < start_bit) return;
+    for(size_t bit = start_bit; bit < end_bit; bit++)
+        op(map, l, bit);
+}
+
+static size_t
+s_buddy_layer_bestfit(struct BuddyMap *map, size_t length)
+{
+    if(length == 1) return 0;
+    size_t length_log2 = LOG2(length);
+    if(length_log2 > map->orders) length_log2 = map->orders - 1;
+    return length_log2;
+}
+
+void
+buddy_mark_range(struct BuddyMap *map, size_t start, size_t end)
+{
+    size_t l = s_buddy_layer_bestfit(map, end - start);
+    s_buddy_op_range(map, l, start, end, buddy_bit_mark);
+}
+void 
+buddy_free_range(struct BuddyMap *map, size_t start, size_t end)
+{ 
+    size_t l = s_buddy_layer_bestfit(map, end - start);
+    s_buddy_op_range(map, l, start, end, buddy_bit_free);
+}
+
+static intmax_t
+s_buddy_top_firstfree(struct BuddyMap *map)
+{
+    size_t layer = map->orders - 1;
+    size_t layer_bits = map->bits >> layer;
+    size_t layer_blocks = layer_bits / BUDDY_BLOCK_BITS;
+    for(size_t i = 0; i < layer_blocks; i++) {
+        if(map->blocks[layer][i] == (uintptr_t)-1) continue;
+        for(size_t j = 0; j < BUDDY_BLOCK_BITS; j++) {
+            size_t bit = (i * BUDDY_BLOCK_BITS) + j;
+            if(buddy_bit_test(map, layer, bit)) continue;
+            return bit;
+        }
+    }
+    return -1;
+}
+
+static intmax_t
+s_buddy_top_alloc_contig(struct BuddyMap *map, size_t length)
+{
+    size_t layer = map->orders - 1;
+    size_t layer_bits = map->bits >> layer;
+
+    size_t contig_base = 0;
+    size_t contig_bits = 0;
+    for(size_t i = 0; i < layer_bits; i++) {
+        if(buddy_bit_test(map, layer, i)) {
+            contig_base = i + 1;
+            contig_bits = 0;
+            continue;
+        }
+        if(++contig_bits == length) {
+            return contig_base;
+        }
+    }
+    return -1;
+}
+
+intmax_t
+buddy_alloc(struct BuddyMap *map, size_t length)
+{
+    size_t layer = s_buddy_layer_bestfit(map, length);
+    size_t layerw = 1ULL << layer;
+    size_t allocw = length / layerw;
+
+    if(allocw == 0) allocw = 1;
+    if(allocw > 1)
+        return s_buddy_top_alloc_contig(map, length);
+
+    intmax_t alloci = s_buddy_top_firstfree(map);
+    if(alloci < 0) {
+        klogf("Top layer is full!\n");
+        return -1;
+    }
+
+    for(int wlayer = map->orders - 2; wlayer > layer; wlayer--) {
+        alloci <<= 1;
+        if(buddy_bit_test(map, wlayer, alloci)) {
+            alloci++;
+        }
+    }
+    alloci <<= 1;
+    if(buddy_bit_test(map, layer, alloci)) alloci++;
+
+    s_buddy_op_range(map, layer, alloci, alloci + length, buddy_bit_mark);
+    return alloci;
+}
+
+void
+buddy_free(struct BuddyMap *map, size_t i, size_t length)
+{
+    buddy_free_range(map, i, i + length);
+}
diff --git a/lib/buddymap.h b/lib/buddymap.h
new file mode 100644
index 0000000..1af8dfb
--- /dev/null
+++ b/lib/buddymap.h
@@ -0,0 +1,35 @@
+#ifndef JOVE_LIB_BUDDYMAP_H
+#define JOVE_LIB_BUDDYMAP_H 1
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdbool.h>
+
+#define BUDDY_BLOCK_BYTES sizeof(intmax_t)
+#define BUDDY_BLOCK_BITS (BUDDY_BLOCK_BYTES * 8)
+
+#define BUDDY_BITS_FOR(range) (range * 2)
+#define BUDDY_BLOCKS_FOR(range) (BUDDY_BITS_FOR(range) / BUDDY_BLOCK_BITS)
+
+struct BuddyMap
+{
+    size_t orders;
+    size_t bits;
+    size_t free;
+    uintmax_t **blocks;
+};
+
+#define BUDDY_BIT_PARTIAL 0
+#define BUDDY_BIT_FULL 1
+
+bool buddy_bit_test(struct BuddyMap *map, size_t l, size_t i);
+void buddy_bit_mark(struct BuddyMap *map, size_t l, size_t i);
+void buddy_bit_free(struct BuddyMap *map, size_t l, size_t i);
+
+void buddy_mark_range(struct BuddyMap *map, size_t start, size_t end);
+void buddy_free_range(struct BuddyMap *map, size_t start, size_t end);
+
+intmax_t buddy_alloc(struct BuddyMap *map, size_t length);
+void buddy_free(struct BuddyMap *map, size_t i, size_t length);
+
+#endif
diff --git a/lib/jove.h b/lib/jove.h
index 4aa60ed..6015112 100644
--- a/lib/jove.h
+++ b/lib/jove.h
@@ -4,7 +4,7 @@
 #define ALWAYS_INLINE inline __attribute__((always_inline))
 #define PAGEALIGN __attribute__((aligned(0x1000)))
 
-//#define LOG2(n) (__builtin_clz(n) ^ 31)
+#define LOG2(n) (31 - __builtin_clz(n))
 
 extern void *_kernel_start;
 extern void *_kernel_end;