1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#pragma once
#include <stdint.h>
#include <stddef.h>
#define MAGIC_COOKIE_BYTES 32
#define ADDRESS_BITS (8 * sizeof(void*))
struct buddy {
uint8_t magic[MAGIC_COOKIE_BYTES];
struct free_block *(avail[ADDRESS_BITS]);
size_t root_logsize;
void *base;
};
// Note: O(1) below means linear in the number of address bits.
// Initialize a buddy with (constant) global state stored in @state.
// NOTE: after initializing the buddy, you should always pass the exact same
// pointer in for @state in future calls. If you need to move @state, use
// move_buddy(...).
// O(1)
void init_buddy(uint8_t *base, size_t size, uint8_t magic[MAGIC_COOKIE_BYTES],
struct buddy *state);
// Allocate a block of size >= @size
// O(1)
void *allocate(size_t size, struct buddy *state);
// Liberate a block of size @size starting at @base.
// O(1)
void liberate(void *base, size_t size, struct buddy *state);
// Print debug information for the allocator.
// O(N) where N is number of liberated items
void debug_buddy(struct buddy *state);
// Simulates @new = allocate, memcpy(@new, @old), free(@old), with some
// optimizations for cases where the reallocation can be done in place.
// O(1)
void *reallocate(void *old, size_t new_size, size_t old_size,
struct buddy *state);
// Attempts to reserve a range [@start,@start+@size).
//
// Returns 1 if success, 0 otherwise.
//
// Whenever possible, we avoid writing anything into the reserved region.
//
// If the reservation succeeds, and @out_start (@out_size) is negative, it puts
// the start (size) of the actually reserved region into *@out_start
// (*@out_size). These can be passed into liberate(...) later to unreserve.
//
// O(1)
int reserve(void *start, size_t size, void **out_start, size_t *out_size,
struct buddy *state);
// Update @state to assume the memory pool has been copied to
// [@new_base,@new_base+@new_size)
// Can *ONLY* be used when @new_size >= the existing size.
// O(1)
void grow_buddy(uint8_t *new_base, size_t new_size, struct buddy *state);
// Update @state to only use the subset of the pool in range
// [@state->base,@state->base+new_size)
// Can *ONLY* be used when @new_size <= the existing size.
// This *CAN* write to anything in the old pool.
// This *CAN* fail, in which case everything is unmodified and 0 is returned.
// Upon success, 1 is returned.
// O(1)
int shrink_buddy(size_t new_size, struct buddy *state);
// Used to move the global state of the buddy.
// O(1)
void move_buddy(struct buddy *new_state, struct buddy *old_state);
|
