summaryrefslogtreecommitdiffstats
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/buddymap.c168
-rw-r--r--lib/buddymap.h35
-rw-r--r--lib/jove.h2
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;