From 8abe20b980db3a90d3dea0a29741074872325d35 Mon Sep 17 00:00:00 2001 From: peter Date: Tue, 1 Sep 2026 19:10:55 +0000 Subject: First step at garbage collection We now visit all objects and change the tag of those which are unreachable, to CHUNK_TAG_FREE. Next step will be to implement compaction to combine all free chunks at the end of the memory space. FossilOrigin-Name: f8641c857b5d430f45d7c1f36fb00866659a5ea78f36ee0535c9166060ea0e19 --- src/lib/memory.c | 130 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 126 insertions(+), 4 deletions(-) (limited to 'src/lib/memory.c') diff --git a/src/lib/memory.c b/src/lib/memory.c index 694a31b..d540739 100644 --- a/src/lib/memory.c +++ b/src/lib/memory.c @@ -14,8 +14,10 @@ enum chunk_tag { struct chunk { struct chunk *next; + struct chunk *stack; size_t size; enum chunk_tag tag; + unsigned int reachable:1; uint8_t *data; }; @@ -27,6 +29,7 @@ memory_init(struct aplwc *aplwc) aplwc->size = 0; aplwc->memptrs = NULL; aplwc->rootptrs = NULL; + aplwc->reachable_bit = 0; } void @@ -61,6 +64,8 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) sub = old-new; } + FIX(aplwc->modules); + for(c = (struct chunk *)new; c; c = c->next){ FIX(c->next); FIX(c->data); @@ -130,8 +135,7 @@ grow(struct aplwc *aplwc, size_t extra) fixrefs(aplwc, aligned_data, aplwc->data); if(aplwc->fns.dealloc) aplwc->fns.dealloc(aplwc->unaligned_data); - for(free = &head; (*free); free = &(*free)->next) - assert((*free)->tag != CHUNK_TAG_FREE); + for(free = &head; (*free); free = &(*free)->next); }else free = &head; @@ -141,6 +145,7 @@ grow(struct aplwc *aplwc, size_t extra) (*free)->data = NULL; (*free)->size = aligned_newsize - aplwc->size; (*free)->next = NULL; + (*free)->stack = NULL; aplwc->unaligned_data = unaligned_data; aplwc->data = aligned_data; @@ -170,19 +175,132 @@ find_free(struct aplwc *aplwc, size_t min) return c; } +static void +push(struct aplwc *aplwc, struct chunk **stack, void *p) +{ + struct chunk *c; + + if(p == NULL) + return; + c = (struct chunk *)(((uint8_t*)p)-HEADER_SIZE); + assert(c->tag != CHUNK_TAG_FREE); + + if(c->reachable == aplwc->reachable_bit) + return; + + assert(c->stack == NULL); + c->reachable = aplwc->reachable_bit; + c->stack = *stack; + *stack = c; +} + +static struct chunk * +pop(struct chunk **stack) +{ + struct chunk *c; + + assert(stack); + assert(*stack); + + c = *stack; + *stack = c->stack; + c->stack = NULL; + + return c; +} + +static void +collect(struct aplwc *aplwc) +{ + struct chunk *c; + struct chunk *stack; + struct memory_ptr_frame *frame; + struct root_ptr *root; + size_t i; + + aplwc->reachable_bit = ~aplwc->reachable_bit; + + /* Mark reachable chunks */ + + stack = NULL; + push(aplwc, &stack, aplwc->modules); + + for(frame = aplwc->memptrs; frame; frame = frame->link) + for(i = 0; i < frame->count; i++) + if(frame->ptrs[i]) + push(aplwc, &stack, *frame->ptrs[i]); + + for(root = aplwc->rootptrs; root; root = root->link) + if(root->ptr) + push(aplwc, &stack, root->ptr); + + while(stack){ + c = pop(&stack); +#define PUSH(type, ptr) push(aplwc, &stack, ((type *)c->data)->ptr) + switch(c->tag){ + case CHUNK_TAG_APLWC_LINE: + PUSH(struct aplwc_line, text); + PUSH(struct aplwc_line, tokens); + break; + case CHUNK_TAG_STRING: + break; + case CHUNK_TAG_TOKEN_LIST: + PUSH(struct token_list, text); + break; + case CHUNK_TAG_APLWC_VALUE: + break; + case CHUNK_TAG_APLWC_MODULE: + PUSH(struct aplwc_module, name); + PUSH(struct aplwc_module, tokens); + PUSH(struct aplwc_module, link); + break; + case CHUNK_TAG_FREE: + break; + } +#undef PUSH + } + + /* Free chunks not marked */ + for(c = (struct chunk *)aplwc->data; c; c = c->next){ + if((c->reachable != aplwc->reachable_bit)){ + c->tag = CHUNK_TAG_FREE; + c->data = NULL; + } + } +} + +static void +compact(struct aplwc *aplwc) +{ + UNUSED_PARAMETER(aplwc); +} + static void * alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag) { struct chunk *free; struct chunk *new; + int attempt; + + attempt = 0; retry: free = find_free(aplwc, size); if(!free){ - if(grow(aplwc, size)) + switch(attempt++){ + case 0: + collect(aplwc); goto retry; - else + case 1: + compact(aplwc); + goto retry; + case 2: + if(grow(aplwc, size)) + goto retry; + /* fall-through */ + default: return NULL; + } } assert(free->data == NULL); @@ -194,11 +312,15 @@ retry: free->tag = CHUNK_TAG_FREE; free->size = new->size - (HEADER_SIZE + size); free->data = NULL; + free->stack = NULL; + free->next = new->next; + new->next = free; } new->tag = tag; new->size = sizeof(struct chunk) + size; new->data = ((uint8_t*)new) + sizeof(struct chunk); + new->reachable = aplwc->reachable_bit; new->data += ((uintptr_t)new->data) % ALIGNMENT; -- cgit v1.2.3 From 26c3da82eb6f33cce64d218e97e2d44324fb9721 Mon Sep 17 00:00:00 2001 From: peter Date: Tue, 1 Sep 2026 20:45:23 +0000 Subject: Implement "compaction", which moves all non-free chunks towards the beginning of the allocated space, and combines all the free space at the end. FossilOrigin-Name: c757f65164e1aebf38bc3e9ea8abe4b9f98b183cec7cfbeed0175f65c72f7ca5 --- src/lib/memory.c | 137 +++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 119 insertions(+), 18 deletions(-) (limited to 'src/lib/memory.c') diff --git a/src/lib/memory.c b/src/lib/memory.c index d540739..e95afc5 100644 --- a/src/lib/memory.c +++ b/src/lib/memory.c @@ -18,7 +18,6 @@ struct chunk { size_t size; enum chunk_tag tag; unsigned int reachable:1; - uint8_t *data; }; void @@ -39,6 +38,15 @@ memory_destroy(struct aplwc *aplwc) aplwc->fns.dealloc(aplwc->unaligned_data); } +void * +data(struct chunk *c) +{ + uint8_t *p; + + p = (uint8_t*)c; + return p + HEADER_SIZE; +} + static void fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) { @@ -49,7 +57,7 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) } \ }while(0) -#define FIX_DATA(type, ptr) FIX(((type *)c->data)->ptr) +#define FIX_DATA(type, ptr) FIX(((type *)data(c))->ptr) struct chunk *c; struct memory_ptr_frame *frame; @@ -68,7 +76,6 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) for(c = (struct chunk *)new; c; c = c->next){ FIX(c->next); - FIX(c->data); switch(c->tag){ case CHUNK_TAG_APLWC_LINE: @@ -110,7 +117,7 @@ grow(struct aplwc *aplwc, size_t extra) { uint8_t *unaligned_data, *aligned_data; size_t unaligned_newsize, aligned_newsize, adjust; - struct chunk **free, *head; + struct chunk **free, *head, *last; if(aplwc->fns.alloc == NULL) goto error; @@ -129,24 +136,33 @@ grow(struct aplwc *aplwc, size_t extra) assert(aligned_newsize >= (aplwc->size + extra)); head = (struct chunk *)aligned_data; + last = NULL; if(aplwc->data){ memmove(aligned_data, aplwc->data, aplwc->size); fixrefs(aplwc, aligned_data, aplwc->data); if(aplwc->fns.dealloc) aplwc->fns.dealloc(aplwc->unaligned_data); - for(free = &head; (*free); free = &(*free)->next); + for(free = &head; (*free); free = &(*free)->next) + if((*free)->next) + assert((*free)->tag != CHUNK_TAG_FREE); + else + last = (*free); }else free = &head; - (*free) = (struct chunk *)(aligned_data + aplwc->size); (*free)->tag = CHUNK_TAG_FREE; - (*free)->data = NULL; (*free)->size = aligned_newsize - aplwc->size; (*free)->next = NULL; (*free)->stack = NULL; + if(last && (last->tag == CHUNK_TAG_FREE)){ + assert(last->next == (*free)); + last->size += (*free)->size; + last->next = NULL; + } + aplwc->unaligned_data = unaligned_data; aplwc->data = aligned_data; aplwc->size = aligned_newsize; @@ -236,7 +252,7 @@ collect(struct aplwc *aplwc) while(stack){ c = pop(&stack); -#define PUSH(type, ptr) push(aplwc, &stack, ((type *)c->data)->ptr) +#define PUSH(type, ptr) push(aplwc, &stack, ((type *)data(c))->ptr) switch(c->tag){ case CHUNK_TAG_APLWC_LINE: PUSH(struct aplwc_line, text); @@ -262,17 +278,100 @@ collect(struct aplwc *aplwc) /* Free chunks not marked */ for(c = (struct chunk *)aplwc->data; c; c = c->next){ - if((c->reachable != aplwc->reachable_bit)){ + if((c->reachable != aplwc->reachable_bit)) c->tag = CHUNK_TAG_FREE; - c->data = NULL; + } +} + +static void +swapptr(struct aplwc *aplwc, void *old, void *new) +{ +#define SWAP(ptr) do{ \ + if((ptr) == old) \ + (ptr) = new; \ +}while(0) + +#define SWAP_DATA(type, ptr) SWAP(((type *)data(c))->ptr) + + struct chunk *c; + struct memory_ptr_frame *frame; + struct root_ptr *root; + size_t i; + + SWAP(aplwc->modules); + + for(c = (struct chunk *)new; c; c = c->next){ + SWAP(c->next); + + switch(c->tag){ + case CHUNK_TAG_APLWC_LINE: + SWAP_DATA(struct aplwc_line, text); + SWAP_DATA(struct aplwc_line, tokens); + break; + case CHUNK_TAG_STRING: + break; + case CHUNK_TAG_TOKEN_LIST: + SWAP_DATA(struct token_list, text); + break; + case CHUNK_TAG_APLWC_VALUE: + break; + case CHUNK_TAG_APLWC_MODULE: + SWAP_DATA(struct aplwc_module, name); + SWAP_DATA(struct aplwc_module, tokens); + SWAP_DATA(struct aplwc_module, link); + break; + case CHUNK_TAG_FREE: + break; } } + + for(frame = aplwc->memptrs; frame; frame = frame->link) + for(i = 0; i < frame->count; i++) + if(frame->ptrs[i]) + SWAP(*frame->ptrs[i]); + + for(root = aplwc->rootptrs; root; root = root->link) + if(root->ptr) + SWAP(root->ptr); + +#undef SWAP +#undef SWAP_DATA } static void compact(struct aplwc *aplwc) { - UNUSED_PARAMETER(aplwc); + struct chunk *c, *prev, *next; + void *oldptr, *newptr; + size_t size; + + for(c = (struct chunk *)aplwc->data, prev = NULL; c; prev = c, c = c->next){ + if((prev == NULL) || (prev->tag != CHUNK_TAG_FREE)) + continue; + + if(c->tag == CHUNK_TAG_FREE){ + prev->size += c->size; + prev->next = c->next; + }else{ + /* swap prev and c */ + oldptr = data(c); + newptr = data(prev); + + next = c->next; + size = prev->size; + + memmove(prev, c, c->size); + + c = (struct chunk *)(((uint8_t *)prev) + prev->size); + prev->next = c; + c->next = next; + c->stack = NULL; + c->tag = CHUNK_TAG_FREE; + c->size = size; + + swapptr(aplwc, oldptr, newptr); + } + } } static void * @@ -280,9 +379,15 @@ alloc(struct aplwc *aplwc, size_t size, enum chunk_tag tag) { struct chunk *free; struct chunk *new; + size_t pad; int attempt; + pad = size % ALIGNMENT; + if(pad) + size += ALIGNMENT - pad; + + attempt = 0; retry: free = find_free(aplwc, size); @@ -303,7 +408,7 @@ retry: } } - assert(free->data == NULL); + assert(free->tag == CHUNK_TAG_FREE); new = free; @@ -311,20 +416,16 @@ retry: free = (struct chunk *)(((uint8_t*)free) + HEADER_SIZE + size); free->tag = CHUNK_TAG_FREE; free->size = new->size - (HEADER_SIZE + size); - free->data = NULL; free->stack = NULL; free->next = new->next; new->next = free; } new->tag = tag; - new->size = sizeof(struct chunk) + size; - new->data = ((uint8_t*)new) + sizeof(struct chunk); + new->size = size + HEADER_SIZE; new->reachable = aplwc->reachable_bit; - new->data += ((uintptr_t)new->data) % ALIGNMENT; - - return new->data; + return data(new); } struct aplwc_ref -- cgit v1.2.3 From 047b642464442b290ea04f5d07bb3ce57a59fdb8 Mon Sep 17 00:00:00 2001 From: peter Date: Tue, 1 Sep 2026 21:14:43 +0000 Subject: Put all the code which visits pointers in memory.c behind a macro, so it can easily be reused. FossilOrigin-Name: 1e911fa0ea41797f445fff6f25df36b6c0f07063b5c6e9936cb243294a2d8a0c --- src/lib/memory.c | 177 ++++++++++++++++++------------------------------------- 1 file changed, 56 insertions(+), 121 deletions(-) (limited to 'src/lib/memory.c') diff --git a/src/lib/memory.c b/src/lib/memory.c index e95afc5..a53a37e 100644 --- a/src/lib/memory.c +++ b/src/lib/memory.c @@ -47,17 +47,49 @@ data(struct chunk *c) return p + HEADER_SIZE; } -static void -fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) -{ -#define FIX(ptr) do{ \ - if(ptr){ \ - (ptr) = (void*)(((uint8_t*)(ptr))+add); \ - (ptr) = (void*)(((uint8_t*)(ptr))-sub); \ +#define VISIT_FIELD(X, tag, ptr) X(((struct tag *)data(c))->ptr) +#define VISIT_CHUNK_PTRS(X, c) switch(c->tag){ \ + case CHUNK_TAG_APLWC_LINE: \ + VISIT_FIELD(X, aplwc_line, text); \ + VISIT_FIELD(X, aplwc_line, tokens); \ + break; \ + case CHUNK_TAG_STRING: \ + break; \ + case CHUNK_TAG_TOKEN_LIST: \ + VISIT_FIELD(X, token_list, text); \ + break; \ + case CHUNK_TAG_APLWC_VALUE: \ + break; \ + case CHUNK_TAG_APLWC_MODULE: \ + VISIT_FIELD(X, aplwc_module, name); \ + VISIT_FIELD(X, aplwc_module, tokens); \ + VISIT_FIELD(X, aplwc_module, link); \ + break; \ + case CHUNK_TAG_FREE: \ + break; \ + } +#define VISIT_ROOT_PTRS(X) do{ \ + X(aplwc->modules); \ + for(frame = aplwc->memptrs; frame; frame = frame->link) \ + for(i = 0; i < frame->count; i++) \ + if(frame->ptrs[i]) \ + X(*frame->ptrs[i]); \ + for(root = aplwc->rootptrs; root; root = root->link) \ + if(root->ptr) \ + X(root->ptr); \ +}while(0) + +#define VISIT_ALL_PTRS(X, data) do{ \ + VISIT_ROOT_PTRS(X); \ + for(c = (struct chunk *)(data); c; c = c->next){ \ + X(c->next); \ + VISIT_CHUNK_PTRS(X, c); \ } \ }while(0) -#define FIX_DATA(type, ptr) FIX(((type *)data(c))->ptr) +static void +fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) +{ struct chunk *c; struct memory_ptr_frame *frame; @@ -72,44 +104,14 @@ fixrefs(struct aplwc *aplwc, uint8_t *new, uint8_t *old) sub = old-new; } - FIX(aplwc->modules); - - for(c = (struct chunk *)new; c; c = c->next){ - FIX(c->next); - - switch(c->tag){ - case CHUNK_TAG_APLWC_LINE: - FIX_DATA(struct aplwc_line, text); - FIX_DATA(struct aplwc_line, tokens); - break; - case CHUNK_TAG_STRING: - break; - case CHUNK_TAG_TOKEN_LIST: - FIX_DATA(struct token_list, text); - break; - case CHUNK_TAG_APLWC_VALUE: - break; - case CHUNK_TAG_APLWC_MODULE: - FIX_DATA(struct aplwc_module, name); - FIX_DATA(struct aplwc_module, tokens); - FIX_DATA(struct aplwc_module, link); - break; - case CHUNK_TAG_FREE: - break; - } - } - - for(frame = aplwc->memptrs; frame; frame = frame->link) - for(i = 0; i < frame->count; i++) - if(frame->ptrs[i]) - FIX(*frame->ptrs[i]); - - for(root = aplwc->rootptrs; root; root = root->link) - if(root->ptr) - FIX(root->ptr); - +#define FIX(ptr) do{ \ + if(ptr){ \ + (ptr) = (void*)(((uint8_t*)(ptr))+add); \ + (ptr) = (void*)(((uint8_t*)(ptr))-sub); \ + } \ +}while(0) + VISIT_ALL_PTRS(FIX, new); #undef FIX -#undef FIX_DATA } static enum aplwc_rc @@ -239,40 +241,12 @@ collect(struct aplwc *aplwc) /* Mark reachable chunks */ stack = NULL; - push(aplwc, &stack, aplwc->modules); - - for(frame = aplwc->memptrs; frame; frame = frame->link) - for(i = 0; i < frame->count; i++) - if(frame->ptrs[i]) - push(aplwc, &stack, *frame->ptrs[i]); - - for(root = aplwc->rootptrs; root; root = root->link) - if(root->ptr) - push(aplwc, &stack, root->ptr); +#define PUSH(ptr) push(aplwc, &stack, ptr) + VISIT_ROOT_PTRS(PUSH); while(stack){ c = pop(&stack); -#define PUSH(type, ptr) push(aplwc, &stack, ((type *)data(c))->ptr) - switch(c->tag){ - case CHUNK_TAG_APLWC_LINE: - PUSH(struct aplwc_line, text); - PUSH(struct aplwc_line, tokens); - break; - case CHUNK_TAG_STRING: - break; - case CHUNK_TAG_TOKEN_LIST: - PUSH(struct token_list, text); - break; - case CHUNK_TAG_APLWC_VALUE: - break; - case CHUNK_TAG_APLWC_MODULE: - PUSH(struct aplwc_module, name); - PUSH(struct aplwc_module, tokens); - PUSH(struct aplwc_module, link); - break; - case CHUNK_TAG_FREE: - break; - } + VISIT_CHUNK_PTRS(PUSH, c); #undef PUSH } @@ -286,56 +260,17 @@ collect(struct aplwc *aplwc) static void swapptr(struct aplwc *aplwc, void *old, void *new) { -#define SWAP(ptr) do{ \ - if((ptr) == old) \ - (ptr) = new; \ -}while(0) - -#define SWAP_DATA(type, ptr) SWAP(((type *)data(c))->ptr) - struct chunk *c; struct memory_ptr_frame *frame; struct root_ptr *root; size_t i; - SWAP(aplwc->modules); - - for(c = (struct chunk *)new; c; c = c->next){ - SWAP(c->next); - - switch(c->tag){ - case CHUNK_TAG_APLWC_LINE: - SWAP_DATA(struct aplwc_line, text); - SWAP_DATA(struct aplwc_line, tokens); - break; - case CHUNK_TAG_STRING: - break; - case CHUNK_TAG_TOKEN_LIST: - SWAP_DATA(struct token_list, text); - break; - case CHUNK_TAG_APLWC_VALUE: - break; - case CHUNK_TAG_APLWC_MODULE: - SWAP_DATA(struct aplwc_module, name); - SWAP_DATA(struct aplwc_module, tokens); - SWAP_DATA(struct aplwc_module, link); - break; - case CHUNK_TAG_FREE: - break; - } - } - - for(frame = aplwc->memptrs; frame; frame = frame->link) - for(i = 0; i < frame->count; i++) - if(frame->ptrs[i]) - SWAP(*frame->ptrs[i]); - - for(root = aplwc->rootptrs; root; root = root->link) - if(root->ptr) - SWAP(root->ptr); - -#undef SWAP -#undef SWAP_DATA +#define SWAP(ptr) do{ \ + if((ptr) == old) \ + (ptr) = new; \ +}while(0) + VISIT_ALL_PTRS(SWAP, new); +#undef SWAP } static void -- cgit v1.2.3