317 lines
10 KiB
C
317 lines
10 KiB
C
|
|
#include <assert.h>
|
|
|
|
#include <debug.h>
|
|
|
|
#include <value/struct.h>
|
|
#include <value/shallow_free.h>
|
|
#include <value/foreach_accessible_subvalue.h>
|
|
|
|
#include <memory/smalloc.h>
|
|
#include <memory/srealloc.h>
|
|
|
|
#include "linked_list/struct.h"
|
|
#include "linked_list/init.h"
|
|
#include "linked_list/append.h"
|
|
#include "linked_list/remove.h"
|
|
#include "linked_list/clear.h"
|
|
#include "linked_list/pop.h"
|
|
|
|
#include "flags.h"
|
|
#include "struct.h"
|
|
#include "dotout.h"
|
|
#include "allocate_node.h"
|
|
|
|
struct value* gc_allocate_node(
|
|
struct gc* this)
|
|
{
|
|
ENTER;
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: start");
|
|
}
|
|
#endif
|
|
|
|
// check if we need to garbage-collect
|
|
if (true
|
|
&& this->flags->minimum < this->bytes_currently_allocated
|
|
&& this->bytes_currently_allocated > this->bytes_of_last_garbage_collection
|
|
&& this->bytes_currently_allocated - this->bytes_of_last_garbage_collection
|
|
> this->flags->run_every)
|
|
{
|
|
dpvlu(this->bytes_currently_allocated);
|
|
dpvlu(this->bytes_of_last_garbage_collection);
|
|
dpvlu(this->flags->run_every);
|
|
dpvlu(this->flags->process_limit);
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: time to garbage collect");
|
|
}
|
|
#endif
|
|
|
|
size_t i = 0, n = this->flags->process_limit;
|
|
|
|
for (; this->grey.head && i < n; i += sizeof(struct value))
|
|
{
|
|
dputs("processing grey...");
|
|
|
|
struct value* grey = linked_list_pop(
|
|
/* linked list: */ &this->grey,
|
|
/* link offset: */ offsetof(struct value, grey));
|
|
|
|
value_foreach_accessible_subvalue(grey, ({
|
|
void callback(struct value* subvalue)
|
|
{
|
|
if (subvalue->white.in_set)
|
|
{
|
|
// remove from white set
|
|
linked_list_remove(
|
|
/* list: */ &this->white,
|
|
/* element: */ subvalue,
|
|
/* offset of link: */ offsetof(struct value, white));
|
|
|
|
// add to grey set
|
|
linked_list_append(
|
|
/* list: */ &this->grey,
|
|
/* element: */ subvalue,
|
|
/* offset of link: */ offsetof(struct value, grey));
|
|
}
|
|
}
|
|
|
|
callback;
|
|
}));
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: processing grey (%lu of %lu)", i, n);
|
|
}
|
|
#endif
|
|
}
|
|
|
|
if (i < n)
|
|
{
|
|
assert(!this->grey.head);
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: all greys are gone, but we can still do more");
|
|
}
|
|
#endif
|
|
|
|
// if we haven't hit the process limit yet then the grey set must be \
|
|
empty. If that's the case, then start processing the white nodes.
|
|
|
|
for (; this->white.head && i < n; i += sizeof(struct value))
|
|
{
|
|
struct value* white = linked_list_pop(
|
|
/* linked list: */ &this->white,
|
|
/* link offset: */ offsetof(struct value, white));
|
|
|
|
// remove white from "internally_referenced"
|
|
linked_list_remove(
|
|
/* linked list: */ &this->internally_referenced,
|
|
/* element: */ white,
|
|
/* link offset: */ offsetof(struct value, internally_referenced));
|
|
|
|
assert(white->external_refcount == 0);
|
|
assert(white->externally_referenced.in_set == false);
|
|
assert(white->internally_referenced.in_set == false);
|
|
assert(white->grey.in_set == false);
|
|
assert(white->white.in_set == false);
|
|
assert(white->reaped.in_set == false);
|
|
|
|
dpvp(white);
|
|
dpvp(white->inheritance);
|
|
|
|
dpvb(VALGRIND_CHECK_VALUE_IS_DEFINED(white));
|
|
|
|
shallow_free_value(white);
|
|
|
|
// reset value:
|
|
#ifdef VALGRIND_BUILD
|
|
VALGRIND_MAKE_MEM_UNDEFINED(white, sizeof(*white));
|
|
|
|
link_init(&white->internally_referenced);
|
|
link_init(&white->reaped);
|
|
link_init(&white->grey);
|
|
link_init(&white->white);
|
|
link_init(&white->externally_referenced);
|
|
|
|
white->external_refcount = 0;
|
|
#endif
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
white->kind = vk_uninitalized;
|
|
#endif
|
|
|
|
linked_list_append(
|
|
/* list: */ &this->reaped,
|
|
/* element: */ white,
|
|
/* offset of link: */ offsetof(struct value, reaped));
|
|
|
|
this->bytes_currently_allocated -= sizeof(struct value);
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: processing whites (%lu of %lu)", i, n);
|
|
}
|
|
#endif
|
|
}
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: done with white");
|
|
}
|
|
#endif
|
|
|
|
// with garbage collection offically done, we still need to set up \\
|
|
for next time:
|
|
{
|
|
// reset the white set to match the allocated set:
|
|
{
|
|
linked_list_deep_clear(
|
|
/* linked list: */ &this->white,
|
|
/* link offset: */ offsetof(struct value, white));
|
|
|
|
for (struct value* v = this->internally_referenced.head;
|
|
v; v = v->internally_referenced.next)
|
|
{
|
|
linked_list_append(
|
|
/* linked list: */ &this->white,
|
|
/* element: */ v,
|
|
/* link offset: */ offsetof(struct value, white));
|
|
}
|
|
}
|
|
|
|
// reset the grey set to match "keep forever" set
|
|
{
|
|
linked_list_deep_clear(
|
|
/* linked list: */ &this->grey,
|
|
/* link offset: */ offsetof(struct value, grey));
|
|
|
|
for (struct value* v = this->externally_referenced.head;
|
|
v; v = v->externally_referenced.next)
|
|
{
|
|
linked_list_append(
|
|
/* linked list: */ &this->grey,
|
|
/* element: */ v,
|
|
/* link offset: */ offsetof(struct value, grey));
|
|
}
|
|
}
|
|
}
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: reset grey and white sets");
|
|
}
|
|
#endif
|
|
}
|
|
|
|
this->bytes_of_last_garbage_collection = this->bytes_currently_allocated;
|
|
}
|
|
|
|
// check if the free-list is empty:
|
|
if (!this->reaped.head)
|
|
{
|
|
// if so, allocate a new block
|
|
|
|
if (this->blocks.n == this->blocks.cap)
|
|
{
|
|
this->blocks.cap = this->blocks.cap << 1 ?: 1;
|
|
|
|
this->blocks.data = srealloc(
|
|
this->blocks.data,
|
|
sizeof(*this->blocks.data) * this->blocks.cap);
|
|
}
|
|
|
|
this->next_block_cap = this->next_block_cap << 1 ?: 1;
|
|
|
|
struct value* new_block = smalloc(
|
|
/* size: */ sizeof(*new_block) * this->next_block_cap);
|
|
|
|
this->blocks.data[this->blocks.n++] = (struct block_info) {
|
|
.start = new_block,
|
|
.cap = this->next_block_cap,
|
|
};
|
|
|
|
// iterate through each block, appending to free list
|
|
for (size_t i = 0; i < this->next_block_cap; i++)
|
|
{
|
|
struct value* value = &new_block[i];
|
|
|
|
#ifdef VALGRIND_BUILD
|
|
VALGRIND_MAKE_MEM_UNDEFINED(value, sizeof(*value));
|
|
#endif
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
value->kind = vk_uninitalized;
|
|
#endif
|
|
|
|
link_init(&value->internally_referenced);
|
|
link_init(&value->reaped);
|
|
link_init(&value->grey);
|
|
link_init(&value->white);
|
|
link_init(&value->externally_referenced);
|
|
|
|
value->external_refcount = 0;
|
|
|
|
linked_list_append(
|
|
/* list: */ &this->reaped,
|
|
/* element: */ value,
|
|
/* offset of link: */ offsetof(struct value, reaped));
|
|
}
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: loaded new block");
|
|
}
|
|
#endif
|
|
}
|
|
|
|
this->bytes_currently_allocated += sizeof(struct value);
|
|
|
|
// pop first element off of free list
|
|
struct value* new = linked_list_pop(
|
|
/* list: */ &this->reaped,
|
|
/* link offset: */ offsetof(struct value, reaped));
|
|
|
|
new->external_refcount = 1;
|
|
|
|
// add to "keep this forever" set
|
|
linked_list_append(
|
|
/* list: */ &this->externally_referenced,
|
|
/* element: */ new,
|
|
/* link offset: */ offsetof(struct value, externally_referenced));
|
|
|
|
#ifdef DOTOUT_BUILD
|
|
if (this->flags->dotout)
|
|
{
|
|
gc_dotout(this, "gc_allocate_node: pop first element off of free list, add to externally_referenced set");
|
|
}
|
|
#endif
|
|
|
|
EXIT;
|
|
return new;
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|