diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/buddymap.c | 168 | ||||
| -rw-r--r-- | lib/buddymap.h | 35 | ||||
| -rw-r--r-- | lib/jove.h | 2 |
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 @@ -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; |