From 0464b7765aa4d1fc2178e443a3b37d19cfe541a0 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 2 Mar 2025 21:45:51 +0200 Subject: add ideal allocation tracker + Kind of like CHERI, but uses out-of-line pointer information. The idea is that a core that is compatible with ALLOC_IF queries the allocation tracker if an address is legal and gets a response. This ideal tracker effectively has infinite memory and doesn't talk to any other components, but a real implementation might want to limit the allocations per process or chat with some reserved memory region somewhere else in the system to maintain a binary tree or something. --- src/mem/ideal_alloc.c | 209 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 209 insertions(+) create mode 100644 src/mem/ideal_alloc.c (limited to 'src/mem/ideal_alloc.c') diff --git a/src/mem/ideal_alloc.c b/src/mem/ideal_alloc.c new file mode 100644 index 0000000..0396123 --- /dev/null +++ b/src/mem/ideal_alloc.c @@ -0,0 +1,209 @@ +#include +#include + +/** @todo almost everyone has the same def for reg, should maybe make common */ +struct reg { + struct packet pkt; + bool busy; +}; + +struct region { + uint64_t start, end; +}; + +static inline int region_cmp(struct region a, struct region b) +{ + if (a.start == b.start && a.end == b.end) + return 0; + + if (a.start > b.start) + return 1; + + if (a.end < b.end) + return -1; + + return 0; +} + +#define SPTREE_NAME regions +#define SPTREE_TYPE struct region +#define SPTREE_CMP(a, b) region_cmp((a), (b)) +#include + +struct space { + struct regions regions; +}; + +static struct space create_space() +{ + return (struct space){.regions = regions_create()}; +} + +static void destroy_space(struct space *space) +{ + regions_destroy(&space->regions); +} + +#define VEC_NAME spaces +#define VEC_TYPE struct space +#include + +struct alloc { + struct component component; + struct spaces spaces; + uint64_t max_spaces; + + struct reg in; + struct reg out; + + struct component *send; +}; + +static void alloc_destroy(struct alloc *a) +{ + foreach(spaces, s, &a->spaces) { + destroy_space(s); + } + + spaces_destroy(&a->spaces); + free(a); +} + +static stat alloc_receive(struct alloc *a, struct component *from, struct packet pkt) +{ + (void)from; /* unused */ + if (a->in.busy) + return EBUSY; + + a->in.pkt = pkt; + a->in.busy = true; + return OK; +} + +static stat alloc_resp(struct alloc *a, enum alloc_if_ret resp, uint64_t start, uint64_t end) +{ + a->in.busy = false; + + struct packet pkt = response(a->in.pkt); + struct alloc_if_r *r = (struct alloc_if_r *)&pkt.data; + r->r = resp; + r->start = start; + r->end = end; + + stat ret = SEND(a, a->send, pkt); + if (ret == EBUSY) { + a->out.pkt = pkt; + a->out.busy = true; + return OK; + } + + return ret; +} + +static stat alloc_new(struct alloc *a) +{ + struct alloc_if_new *n = (struct alloc_if_new *)&a->in.pkt.data; + if (n->space >= a->max_spaces) + return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0); + + struct space *space = spaces_at(&a->spaces, n->space); + assert(space); + + struct region new = {.start = n->start, .end = n->end}; + struct region *region = regions_insert(&space->regions, new); + if (!region) { + alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0); + return EMEM; + } + + return alloc_resp(a, ALLOC_IF_OK, n->start, n->end); +} + +static stat alloc_rm(struct alloc *a) +{ + struct alloc_if_rm *rm = (struct alloc_if_rm *)&a->in.pkt.data; + if (rm->space >= a->max_spaces) + return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0); + + struct space *space = spaces_at(&a->spaces, rm->space); + assert(space); + + struct region find = {.start = rm->start, .end = rm->end}; + struct region *region = regions_find(&space->regions, find); + if (!region) + return alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0); + + regions_remove_found(&space->regions, region); + regions_free_found(&space->regions, region); + return alloc_resp(a, ALLOC_IF_OK, 0, 0); +} + +static stat alloc_q(struct alloc *a) +{ + struct alloc_if_q *q = (struct alloc_if_q *)&a->in.pkt.data; + if (q->space >= a->max_spaces) + return alloc_resp(a, ALLOC_IF_ERR_SPACE, 0, 0); + + struct space *space = spaces_at(&a->spaces, q->space); + assert(space); + + struct region find = {.start = q->addr, .end = q->addr}; + struct region *region = regions_find(&space->regions, find); + if (!region) + return alloc_resp(a, ALLOC_IF_ERR_RANGE, 0, 0); + + return alloc_resp(a, ALLOC_IF_OK, region->start, region->end); +} + +static stat alloc_clock(struct alloc *a) +{ + if (!a->in.busy) + return OK; + + if (a->out.busy) { + stat ret = SEND(a, a->send, a->out.pkt); + if (ret == EBUSY) + return OK; + + assert(ret == OK); + a->out.busy = false; + } + + uint32_t off = (uint32_t)a->in.pkt.to; + switch (off) { + case ALLOC_IF_NEW: return alloc_new(a); + case ALLOC_IF_RM: return alloc_rm(a); + case ALLOC_IF_Q: return alloc_q(a); + default: break; + } + + return OK; +} + +void ideal_alloc_connect(struct component *alloc, struct component *send) +{ + struct alloc *a = (struct alloc *)alloc; + assert(a->send == NULL); + a->send = send; +} + +struct component *create_ideal_alloc(uint64_t max_spaces) +{ + struct alloc *a = calloc(1, sizeof(struct alloc)); + a->spaces = spaces_create(max_spaces); + if (spaces_uninit(&a->spaces)) { + free(a); + return NULL; + } + + for (size_t i = 0; i < max_spaces; ++i) { + struct space space = create_space(); + spaces_append(&a->spaces, space); + } + + a->max_spaces = max_spaces; + a->component.clock = (clock_callback)alloc_clock; + a->component.receive = (receive_callback)alloc_receive; + a->component.destroy = (destroy_callback)alloc_destroy; + return (struct component *)a; +} -- cgit v1.3