diff options
Diffstat (limited to 'libguile/whippet/src/copy-space.h')
-rw-r--r-- | libguile/whippet/src/copy-space.h | 979 |
1 files changed, 979 insertions, 0 deletions
diff --git a/libguile/whippet/src/copy-space.h b/libguile/whippet/src/copy-space.h new file mode 100644 index 000000000..7f262c221 --- /dev/null +++ b/libguile/whippet/src/copy-space.h @@ -0,0 +1,979 @@ +#ifndef COPY_SPACE_H +#define COPY_SPACE_H + +#include <pthread.h> +#include <stdlib.h> + +#include "gc-api.h" + +#define GC_IMPL 1 +#include "gc-internal.h" + +#include "assert.h" +#include "background-thread.h" +#include "debug.h" +#include "extents.h" +#include "gc-align.h" +#include "gc-attrs.h" +#include "gc-inline.h" +#include "gc-lock.h" +#include "gc-platform.h" +#include "spin.h" + +// A copy space: a block-structured space that traces via evacuation. + +#define COPY_SPACE_SLAB_SIZE (64 * 1024 * 1024) +#define COPY_SPACE_REGION_SIZE (64 * 1024) +#define COPY_SPACE_BLOCK_SIZE (2 * COPY_SPACE_REGION_SIZE) +#define COPY_SPACE_BLOCKS_PER_SLAB \ + (COPY_SPACE_SLAB_SIZE / COPY_SPACE_BLOCK_SIZE) +#define COPY_SPACE_HEADER_BYTES_PER_BLOCK \ + (COPY_SPACE_BLOCK_SIZE / COPY_SPACE_BLOCKS_PER_SLAB) +#define COPY_SPACE_HEADER_BLOCKS_PER_SLAB 1 +#define COPY_SPACE_NONHEADER_BLOCKS_PER_SLAB \ + (COPY_SPACE_BLOCKS_PER_SLAB - COPY_SPACE_HEADER_BLOCKS_PER_SLAB) +#define COPY_SPACE_HEADER_BYTES_PER_SLAB \ + (COPY_SPACE_HEADER_BYTES_PER_BLOCK * COPY_SPACE_HEADER_BLOCKS_PER_SLAB) + +struct copy_space_slab; + +struct copy_space_slab_header { + union { + struct { + struct copy_space_slab *next; + struct copy_space_slab *prev; + unsigned incore_block_count; + }; + uint8_t padding[COPY_SPACE_HEADER_BYTES_PER_SLAB]; + }; +}; +STATIC_ASSERT_EQ(sizeof(struct copy_space_slab_header), + COPY_SPACE_HEADER_BYTES_PER_SLAB); + +// Really just the block header. +struct copy_space_block { + union { + struct { + struct copy_space_block *next; + uint8_t in_core; + uint8_t all_zeroes[2]; + uint8_t is_survivor[2]; + size_t allocated; // For partly-empty blocks. + }; + uint8_t padding[COPY_SPACE_HEADER_BYTES_PER_BLOCK]; + }; +}; +STATIC_ASSERT_EQ(sizeof(struct copy_space_block), + COPY_SPACE_HEADER_BYTES_PER_BLOCK); + +struct copy_space_region { + char data[COPY_SPACE_REGION_SIZE]; +}; + +struct copy_space_block_payload { + struct copy_space_region regions[2]; +}; + +struct copy_space_slab { + struct copy_space_slab_header header; + struct copy_space_block headers[COPY_SPACE_NONHEADER_BLOCKS_PER_SLAB]; + struct copy_space_block_payload blocks[COPY_SPACE_NONHEADER_BLOCKS_PER_SLAB]; +}; +STATIC_ASSERT_EQ(sizeof(struct copy_space_slab), COPY_SPACE_SLAB_SIZE); + +static inline struct copy_space_block* +copy_space_block_for_addr(uintptr_t addr) { + uintptr_t base = align_down(addr, COPY_SPACE_SLAB_SIZE); + struct copy_space_slab *slab = (struct copy_space_slab*) base; + uintptr_t block_idx = + (addr / COPY_SPACE_BLOCK_SIZE) % COPY_SPACE_BLOCKS_PER_SLAB; + return &slab->headers[block_idx - COPY_SPACE_HEADER_BLOCKS_PER_SLAB]; +} + +static inline struct copy_space_block* +copy_space_block_header(struct copy_space_block_payload *payload) { + return copy_space_block_for_addr((uintptr_t) payload); +} + +static inline struct copy_space_block_payload* +copy_space_block_payload(struct copy_space_block *block) { + uintptr_t addr = (uintptr_t) block; + uintptr_t base = align_down(addr, COPY_SPACE_SLAB_SIZE); + struct copy_space_slab *slab = (struct copy_space_slab*) base; + uintptr_t block_idx = + (addr / COPY_SPACE_HEADER_BYTES_PER_BLOCK) % COPY_SPACE_BLOCKS_PER_SLAB; + return &slab->blocks[block_idx - COPY_SPACE_HEADER_BLOCKS_PER_SLAB]; +} + +static uint8_t +copy_space_object_region(struct gc_ref obj) { + return (gc_ref_value(obj) / COPY_SPACE_REGION_SIZE) & 1; +} + +#define COPY_SPACE_PAGE_OUT_QUEUE_SIZE 4 + +struct copy_space_block_list { + struct copy_space_block *head; +}; + +struct copy_space_block_stack { + struct copy_space_block_list list; +}; + +enum copy_space_flags { + COPY_SPACE_ATOMIC_FORWARDING = 1, + COPY_SPACE_ALIGNED = 2, + COPY_SPACE_HAS_FIELD_LOGGING_BITS = 4, +}; + +struct copy_space { + pthread_mutex_t lock; + struct copy_space_block_stack empty; + struct copy_space_block_stack partly_full; + struct copy_space_block_list full ALIGNED_TO_AVOID_FALSE_SHARING; + size_t allocated_bytes; + size_t fragmentation; + struct copy_space_block_stack paged_out[COPY_SPACE_PAGE_OUT_QUEUE_SIZE] + ALIGNED_TO_AVOID_FALSE_SHARING; + ssize_t bytes_to_page_out ALIGNED_TO_AVOID_FALSE_SHARING; + // The rest of these members are only changed rarely and with the heap + // lock. + uint8_t active_region ALIGNED_TO_AVOID_FALSE_SHARING; + uint8_t atomic_forward; + uint8_t in_gc; + uint32_t flags; + size_t allocated_bytes_at_last_gc; + size_t fragmentation_at_last_gc; + struct extents *extents; + struct copy_space_slab **slabs; + size_t nslabs; +}; + +enum copy_space_forward_result { + // We went to forward an edge, but the target was already forwarded, so we + // just updated the edge. + COPY_SPACE_FORWARD_UPDATED, + // We went to forward an edge and evacuated the referent to a new location. + COPY_SPACE_FORWARD_EVACUATED, + // We went to forward an edge but failed to acquire memory for its new + // location. + COPY_SPACE_FORWARD_FAILED, +}; + +struct copy_space_allocator { + uintptr_t hp; + uintptr_t limit; + struct copy_space_block *block; +}; + +static struct gc_lock +copy_space_lock(struct copy_space *space) { + return gc_lock_acquire(&space->lock); +} + +static void +copy_space_block_list_push(struct copy_space_block_list *list, + struct copy_space_block *block) { + struct copy_space_block *next = + atomic_load_explicit(&list->head, memory_order_acquire); + do { + block->next = next; + } while (!atomic_compare_exchange_weak(&list->head, &next, block)); +} + +static struct copy_space_block* +copy_space_block_list_pop(struct copy_space_block_list *list) { + struct copy_space_block *head = + atomic_load_explicit(&list->head, memory_order_acquire); + struct copy_space_block *next; + do { + if (!head) + return NULL; + } while (!atomic_compare_exchange_weak(&list->head, &head, head->next)); + head->next = NULL; + return head; +} + +static void +copy_space_block_stack_push(struct copy_space_block_stack *stack, + struct copy_space_block *block, + const struct gc_lock *lock) { + struct copy_space_block *next = stack->list.head; + block->next = next; + stack->list.head = block; +} + +static struct copy_space_block* +copy_space_block_stack_pop(struct copy_space_block_stack *stack, + const struct gc_lock *lock) { + struct copy_space_block *head = stack->list.head; + if (head) { + stack->list.head = head->next; + head->next = NULL; + } + return head; +} + +static struct copy_space_block* +copy_space_pop_empty_block(struct copy_space *space, + const struct gc_lock *lock) { + struct copy_space_block *ret = copy_space_block_stack_pop(&space->empty, + lock); + if (ret) { + ret->allocated = 0; + ret->is_survivor[space->active_region] = 0; + } + return ret; +} + +static void +copy_space_push_empty_block(struct copy_space *space, + struct copy_space_block *block, + const struct gc_lock *lock) { + copy_space_block_stack_push(&space->empty, block, lock); +} + +static struct copy_space_block* +copy_space_pop_full_block(struct copy_space *space) { + return copy_space_block_list_pop(&space->full); +} + +static void +copy_space_push_full_block(struct copy_space *space, + struct copy_space_block *block) { + if (space->in_gc) + block->is_survivor[space->active_region] = 1; + copy_space_block_list_push(&space->full, block); +} + +static struct copy_space_block* +copy_space_pop_partly_full_block(struct copy_space *space, + const struct gc_lock *lock) { + return copy_space_block_stack_pop(&space->partly_full, lock); +} + +static void +copy_space_push_partly_full_block(struct copy_space *space, + struct copy_space_block *block, + const struct gc_lock *lock) { + copy_space_block_stack_push(&space->partly_full, block, lock); +} + +static void +copy_space_page_out_block(struct copy_space *space, + struct copy_space_block *block, + const struct gc_lock *lock) { + copy_space_block_stack_push + (block->in_core + ? &space->paged_out[0] + : &space->paged_out[COPY_SPACE_PAGE_OUT_QUEUE_SIZE-1], + block, + lock); +} + +static struct copy_space_block* +copy_space_page_in_block(struct copy_space *space, + const struct gc_lock *lock) { + for (int age = 0; age < COPY_SPACE_PAGE_OUT_QUEUE_SIZE; age++) { + struct copy_space_block *block = + copy_space_block_stack_pop(&space->paged_out[age], lock); + if (block) return block; + } + return NULL; +} + +static ssize_t +copy_space_request_release_memory(struct copy_space *space, size_t bytes) { + return atomic_fetch_add(&space->bytes_to_page_out, bytes) + bytes; +} + +static int +copy_space_page_out_blocks_until_memory_released(struct copy_space *space) { + ssize_t pending = atomic_load(&space->bytes_to_page_out); + struct gc_lock lock = copy_space_lock(space); + while (pending > 0) { + struct copy_space_block *block = copy_space_pop_empty_block(space, &lock); + if (!block) break; + copy_space_page_out_block(space, block, &lock); + pending = (atomic_fetch_sub(&space->bytes_to_page_out, COPY_SPACE_BLOCK_SIZE) + - COPY_SPACE_BLOCK_SIZE); + } + gc_lock_release(&lock); + return pending <= 0; +} + +static ssize_t +copy_space_maybe_reacquire_memory(struct copy_space *space, size_t bytes) { + ssize_t pending = + atomic_fetch_sub(&space->bytes_to_page_out, bytes) - bytes; + struct gc_lock lock = copy_space_lock(space); + while (pending + COPY_SPACE_BLOCK_SIZE <= 0) { + struct copy_space_block *block = copy_space_page_in_block(space, &lock); + if (!block) break; + copy_space_push_empty_block(space, block, &lock); + pending = (atomic_fetch_add(&space->bytes_to_page_out, + COPY_SPACE_BLOCK_SIZE) + + COPY_SPACE_BLOCK_SIZE); + } + gc_lock_release(&lock); + return pending; +} + +static void +copy_space_reacquire_memory(struct copy_space *space, size_t bytes) { + ssize_t pending = copy_space_maybe_reacquire_memory(space, bytes); + GC_ASSERT(pending + COPY_SPACE_BLOCK_SIZE > 0); +} + +static inline int +copy_space_contains_address(struct copy_space *space, uintptr_t addr) { + return extents_contain_addr(space->extents, addr); +} + +static inline int +copy_space_contains(struct copy_space *space, struct gc_ref ref) { + return copy_space_contains_address(space, gc_ref_value(ref)); +} + +static int +copy_space_has_field_logging_bits(struct copy_space *space) { + return space->flags & COPY_SPACE_HAS_FIELD_LOGGING_BITS; +} + +static size_t +copy_space_field_logging_blocks(struct copy_space *space) { + if (!copy_space_has_field_logging_bits(space)) + return 0; + size_t bytes = COPY_SPACE_SLAB_SIZE / sizeof (uintptr_t) / 8; + size_t blocks = + align_up(bytes, COPY_SPACE_BLOCK_SIZE) / COPY_SPACE_BLOCK_SIZE; + return blocks; +} + +static uint8_t* +copy_space_field_logged_byte(struct gc_edge edge) { + uintptr_t addr = gc_edge_address(edge); + uintptr_t base = align_down(addr, COPY_SPACE_SLAB_SIZE); + base += offsetof(struct copy_space_slab, blocks); + uintptr_t field = (addr & (COPY_SPACE_SLAB_SIZE - 1)) / sizeof(uintptr_t); + uintptr_t byte = field / 8; + return (uint8_t*) (base + byte); +} + +static uint8_t +copy_space_field_logged_bit(struct gc_edge edge) { + // Each byte has 8 bytes, covering 8 fields. + size_t field = gc_edge_address(edge) / sizeof(uintptr_t); + return 1 << (field % 8); +} + +static void +copy_space_clear_field_logged_bits_for_region(struct copy_space *space, + void *region_base) { + uintptr_t addr = (uintptr_t)region_base; + GC_ASSERT_EQ(addr, align_down(addr, COPY_SPACE_REGION_SIZE)); + GC_ASSERT(copy_space_contains_address(space, addr)); + if (copy_space_has_field_logging_bits(space)) + memset(copy_space_field_logged_byte(gc_edge(region_base)), + 0, + COPY_SPACE_REGION_SIZE / sizeof(uintptr_t) / 8); +} + +static void +copy_space_clear_field_logged_bits_for_block(struct copy_space *space, + struct copy_space_block *block) { + struct copy_space_block_payload *payload = copy_space_block_payload(block); + copy_space_clear_field_logged_bits_for_region(space, &payload->regions[0]); + copy_space_clear_field_logged_bits_for_region(space, &payload->regions[1]); +} + +static inline void +copy_space_allocator_set_block(struct copy_space_allocator *alloc, + struct copy_space_block *block, + int active_region) { + struct copy_space_block_payload *payload = copy_space_block_payload(block); + struct copy_space_region *region = &payload->regions[active_region]; + alloc->block = block; + alloc->hp = (uintptr_t)®ion[0]; + alloc->limit = (uintptr_t)®ion[1]; +} + +static inline int +copy_space_allocator_acquire_block(struct copy_space_allocator *alloc, + struct copy_space_block *block, + int active_region) { + if (block) { + copy_space_allocator_set_block(alloc, block, active_region); + return 1; + } + return 0; +} + +static int +copy_space_allocator_acquire_empty_block(struct copy_space_allocator *alloc, + struct copy_space *space) { + struct gc_lock lock = copy_space_lock(space); + struct copy_space_block *block = copy_space_pop_empty_block(space, &lock); + gc_lock_release(&lock); + if (copy_space_allocator_acquire_block(alloc, block, space->active_region)) { + block->in_core = 1; + if (block->all_zeroes[space->active_region]) { + block->all_zeroes[space->active_region] = 0; + } else { + memset((char*)alloc->hp, 0, COPY_SPACE_REGION_SIZE); + copy_space_clear_field_logged_bits_for_region(space, (void*)alloc->hp); + } + return 1; + } + return 0; +} + +static int +copy_space_allocator_acquire_partly_full_block(struct copy_space_allocator *alloc, + struct copy_space *space) { + struct gc_lock lock = copy_space_lock(space); + struct copy_space_block *block = copy_space_pop_partly_full_block(space, + &lock); + gc_lock_release(&lock); + if (copy_space_allocator_acquire_block(alloc, block, space->active_region)) { + alloc->hp += block->allocated; + return 1; + } + return 0; +} + +static void +copy_space_allocator_release_full_block(struct copy_space_allocator *alloc, + struct copy_space *space) { + size_t fragmentation = alloc->limit - alloc->hp; + size_t allocated = COPY_SPACE_REGION_SIZE - alloc->block->allocated; + atomic_fetch_add_explicit(&space->allocated_bytes, allocated, + memory_order_relaxed); + if (fragmentation) + atomic_fetch_add_explicit(&space->fragmentation, fragmentation, + memory_order_relaxed); + copy_space_push_full_block(space, alloc->block); + alloc->hp = alloc->limit = 0; + alloc->block = NULL; +} + +static void +copy_space_allocator_release_partly_full_block(struct copy_space_allocator *alloc, + struct copy_space *space) { + size_t allocated = alloc->hp & (COPY_SPACE_REGION_SIZE - 1); + if (allocated) { + atomic_fetch_add_explicit(&space->allocated_bytes, + allocated - alloc->block->allocated, + memory_order_relaxed); + alloc->block->allocated = allocated; + struct gc_lock lock = copy_space_lock(space); + copy_space_push_partly_full_block(space, alloc->block, &lock); + gc_lock_release(&lock); + } else { + // In this case, hp was bumped all the way to the limit, in which + // case allocated wraps to 0; the block is full. + atomic_fetch_add_explicit(&space->allocated_bytes, + COPY_SPACE_REGION_SIZE - alloc->block->allocated, + memory_order_relaxed); + copy_space_push_full_block(space, alloc->block); + } + alloc->hp = alloc->limit = 0; + alloc->block = NULL; +} + +static inline struct gc_ref +copy_space_allocate(struct copy_space_allocator *alloc, + struct copy_space *space, + size_t size) { + GC_ASSERT(size > 0); + GC_ASSERT(size <= gc_allocator_large_threshold()); + size = align_up(size, gc_allocator_small_granule_size()); + + if (alloc->hp + size <= alloc->limit) + goto done; + + if (alloc->block) + copy_space_allocator_release_full_block(alloc, space); + while (copy_space_allocator_acquire_partly_full_block(alloc, space)) { + if (alloc->hp + size <= alloc->limit) + goto done; + copy_space_allocator_release_full_block(alloc, space); + } + if (!copy_space_allocator_acquire_empty_block(alloc, space)) + return gc_ref_null(); + // The newly acquired block is empty and is therefore large enough for + // a small allocation. + +done: + struct gc_ref ret = gc_ref(alloc->hp); + alloc->hp += size; + return ret; +} + +static struct copy_space_block* +copy_space_append_block_lists(struct copy_space_block *head, + struct copy_space_block *tail) { + if (!head) return tail; + if (tail) { + struct copy_space_block *walk = head; + while (walk->next) + walk = walk->next; + walk->next = tail; + } + return head; +} + +static void +copy_space_flip(struct copy_space *space) { + // Mutators stopped, can access nonatomically. + struct copy_space_block* flip = space->full.head; + flip = copy_space_append_block_lists(space->partly_full.list.head, flip); + flip = copy_space_append_block_lists(space->empty.list.head, flip); + space->empty.list.head = flip; + space->partly_full.list.head = NULL; + space->full.head = NULL; + space->allocated_bytes = 0; + space->fragmentation = 0; + space->active_region ^= 1; + space->in_gc = 1; +} + +static inline void +copy_space_allocator_init(struct copy_space_allocator *alloc) { + memset(alloc, 0, sizeof(*alloc)); +} + +static inline void +copy_space_allocator_finish(struct copy_space_allocator *alloc, + struct copy_space *space) { + if (alloc->block) + copy_space_allocator_release_partly_full_block(alloc, space); +} + +static void +copy_space_finish_gc(struct copy_space *space, int is_minor_gc) { + // Mutators stopped, can access nonatomically. + if (is_minor_gc) { + // Avoid mixing survivors and new objects on the same blocks. + struct copy_space_allocator alloc; + copy_space_allocator_init(&alloc); + while (copy_space_allocator_acquire_partly_full_block(&alloc, space)) + copy_space_allocator_release_full_block(&alloc, space); + copy_space_allocator_finish(&alloc, space); + } + + space->allocated_bytes_at_last_gc = space->allocated_bytes; + space->fragmentation_at_last_gc = space->fragmentation; + space->in_gc = 0; +} + +static size_t +copy_space_can_allocate(struct copy_space *space, size_t bytes) { + // With lock! + size_t count = 0; + for (struct copy_space_block *empties = space->empty.list.head; + empties && count < bytes; + empties = empties->next) { + count += COPY_SPACE_REGION_SIZE; + } + return count; +} + +static void +copy_space_add_to_allocation_counter(struct copy_space *space, + uint64_t *counter) { + *counter += space->allocated_bytes - space->allocated_bytes_at_last_gc; +} + +static void +copy_space_gc_during_evacuation(void *data) { + // If space is really tight and reordering of objects during + // evacuation resulted in more end-of-block fragmentation and thus + // block use than before collection started, we can actually run out + // of memory while collecting. We should probably attempt to expand + // the heap here, at least by a single block; it's better than the + // alternatives. + fprintf(stderr, "Out of memory\n"); + GC_CRASH(); +} + +static inline enum copy_space_forward_result +copy_space_forward_atomic(struct copy_space *space, struct gc_edge edge, + struct gc_ref old_ref, + struct copy_space_allocator *alloc) { + struct gc_atomic_forward fwd = gc_atomic_forward_begin(old_ref); + +retry: + if (fwd.state == GC_FORWARDING_STATE_NOT_FORWARDED) + gc_atomic_forward_acquire(&fwd); + + switch (fwd.state) { + case GC_FORWARDING_STATE_NOT_FORWARDED: + default: + // Impossible. + GC_CRASH(); + case GC_FORWARDING_STATE_ACQUIRED: { + // We claimed the object successfully; evacuating is up to us. + size_t bytes = gc_atomic_forward_object_size(&fwd); + struct gc_ref new_ref = copy_space_allocate(alloc, space, bytes); + if (gc_ref_is_null(new_ref)) { + gc_atomic_forward_abort(&fwd); + return COPY_SPACE_FORWARD_FAILED; + } + // Copy object contents before committing, as we don't know what + // part of the object (if any) will be overwritten by the + // commit. + memcpy(gc_ref_heap_object(new_ref), gc_ref_heap_object(old_ref), bytes); + gc_atomic_forward_commit(&fwd, new_ref); + gc_edge_update(edge, new_ref); + return COPY_SPACE_FORWARD_EVACUATED; + } + case GC_FORWARDING_STATE_BUSY: + // Someone else claimed this object first. Spin until new address + // known, or evacuation aborts. + for (size_t spin_count = 0;; spin_count++) { + if (gc_atomic_forward_retry_busy(&fwd)) + goto retry; + yield_for_spin(spin_count); + } + GC_CRASH(); // Unreachable. + case GC_FORWARDING_STATE_FORWARDED: + // The object has been evacuated already. Update the edge; + // whoever forwarded the object will make sure it's eventually + // traced. + gc_edge_update(edge, gc_ref(gc_atomic_forward_address(&fwd))); + return COPY_SPACE_FORWARD_UPDATED; + } +} + +static int +copy_space_forward_if_traced_atomic(struct copy_space *space, + struct gc_edge edge, + struct gc_ref old_ref) { + struct gc_atomic_forward fwd = gc_atomic_forward_begin(old_ref); +retry: + switch (fwd.state) { + case GC_FORWARDING_STATE_NOT_FORWARDED: + return 0; + case GC_FORWARDING_STATE_BUSY: + // Someone else claimed this object first. Spin until new address + // known. + for (size_t spin_count = 0;; spin_count++) { + if (gc_atomic_forward_retry_busy(&fwd)) + goto retry; + yield_for_spin(spin_count); + } + GC_CRASH(); // Unreachable. + case GC_FORWARDING_STATE_FORWARDED: + gc_edge_update(edge, gc_ref(gc_atomic_forward_address(&fwd))); + return 1; + default: + GC_CRASH(); + } +} + +static inline enum copy_space_forward_result +copy_space_forward_nonatomic(struct copy_space *space, struct gc_edge edge, + struct gc_ref old_ref, + struct copy_space_allocator *alloc) { + uintptr_t forwarded = gc_object_forwarded_nonatomic(old_ref); + if (forwarded) { + gc_edge_update(edge, gc_ref(forwarded)); + return COPY_SPACE_FORWARD_UPDATED; + } else { + size_t size; + gc_trace_object(old_ref, NULL, NULL, NULL, &size); + struct gc_ref new_ref = copy_space_allocate(alloc, space, size); + if (gc_ref_is_null(new_ref)) + return COPY_SPACE_FORWARD_FAILED; + memcpy(gc_ref_heap_object(new_ref), gc_ref_heap_object(old_ref), size); + gc_object_forward_nonatomic(old_ref, new_ref); + gc_edge_update(edge, new_ref); + return COPY_SPACE_FORWARD_EVACUATED; + } +} + +static int +copy_space_forward_if_traced_nonatomic(struct copy_space *space, + struct gc_edge edge, + struct gc_ref old_ref) { + uintptr_t forwarded = gc_object_forwarded_nonatomic(old_ref); + if (forwarded) { + gc_edge_update(edge, gc_ref(forwarded)); + return 1; + } + return 0; +} + +static inline enum copy_space_forward_result +copy_space_forward(struct copy_space *src_space, struct copy_space *dst_space, + struct gc_edge edge, + struct gc_ref old_ref, + struct copy_space_allocator *dst_alloc) { + GC_ASSERT(copy_space_contains(src_space, old_ref)); + GC_ASSERT(src_space != dst_space + || copy_space_object_region(old_ref) != src_space->active_region); + if (GC_PARALLEL && src_space->atomic_forward) + return copy_space_forward_atomic(dst_space, edge, old_ref, dst_alloc); + return copy_space_forward_nonatomic(dst_space, edge, old_ref, dst_alloc); +} + +static inline int +copy_space_forward_if_traced(struct copy_space *space, struct gc_edge edge, + struct gc_ref old_ref) { + GC_ASSERT(copy_space_contains(space, old_ref)); + GC_ASSERT(copy_space_object_region(old_ref) != space->active_region); + if (GC_PARALLEL && space->atomic_forward) + return copy_space_forward_if_traced_atomic(space, edge, old_ref); + return copy_space_forward_if_traced_nonatomic(space, edge, old_ref); +} + +static int +copy_space_is_aligned(struct copy_space *space) { + return space->flags & COPY_SPACE_ALIGNED; +} + +static int +copy_space_fixed_size(struct copy_space *space) { + // If the extent is aligned, it is fixed. + return copy_space_is_aligned(space); +} + +static inline uintptr_t +copy_space_low_aligned_address(struct copy_space *space) { + GC_ASSERT(copy_space_is_aligned(space)); + GC_ASSERT_EQ(space->extents->size, 1); + return space->extents->ranges[0].lo_addr; +} + +static inline uintptr_t +copy_space_high_aligned_address(struct copy_space *space) { + GC_ASSERT(copy_space_is_aligned(space)); + GC_ASSERT_EQ(space->extents->size, 1); + return space->extents->ranges[0].hi_addr; +} + +static inline int +copy_space_contains_address_aligned(struct copy_space *space, uintptr_t addr) { + uintptr_t low_addr = copy_space_low_aligned_address(space); + uintptr_t high_addr = copy_space_high_aligned_address(space); + uintptr_t size = high_addr - low_addr; + return (addr - low_addr) < size; +} + +static inline int +copy_space_contains_edge_aligned(struct copy_space *space, + struct gc_edge edge) { + return copy_space_contains_address_aligned(space, gc_edge_address(edge)); +} + +static inline int +copy_space_should_promote(struct copy_space *space, struct gc_ref ref) { + GC_ASSERT(copy_space_contains(space, ref)); + uintptr_t addr = gc_ref_value(ref); + struct copy_space_block *block = copy_space_block_for_addr(gc_ref_value(ref)); + GC_ASSERT_EQ(copy_space_object_region(ref), space->active_region ^ 1); + return block->is_survivor[space->active_region ^ 1]; +} + +static int +copy_space_contains_edge(struct copy_space *space, struct gc_edge edge) { + return copy_space_contains_address(space, gc_edge_address(edge)); +} + +static int +copy_space_remember_edge(struct copy_space *space, struct gc_edge edge) { + GC_ASSERT(copy_space_contains_edge(space, edge)); + uint8_t* loc = copy_space_field_logged_byte(edge); + uint8_t bit = copy_space_field_logged_bit(edge); + uint8_t byte = atomic_load_explicit(loc, memory_order_acquire); + do { + if (byte & bit) return 0; + } while (!atomic_compare_exchange_weak_explicit(loc, &byte, byte|bit, + memory_order_acq_rel, + memory_order_acquire)); + return 1; +} + +static int +copy_space_forget_edge(struct copy_space *space, struct gc_edge edge) { + GC_ASSERT(copy_space_contains_edge(space, edge)); + uint8_t* loc = copy_space_field_logged_byte(edge); + uint8_t bit = copy_space_field_logged_bit(edge); + uint8_t byte = atomic_load_explicit(loc, memory_order_acquire); + do { + if (!(byte & bit)) return 0; + } while (!atomic_compare_exchange_weak_explicit(loc, &byte, byte&~bit, + memory_order_acq_rel, + memory_order_acquire)); + return 1; +} + +static size_t copy_space_is_power_of_two(size_t n) { + GC_ASSERT(n != 0); + return (n & (n - 1)) == 0; +} + +static size_t copy_space_round_up_power_of_two(size_t n) { + if (copy_space_is_power_of_two(n)) + return n; + + return 1ULL << (sizeof(size_t) * 8 - __builtin_clzll(n)); +} + +static struct copy_space_slab* +copy_space_allocate_slabs(size_t nslabs, uint32_t flags) { + size_t size = nslabs * COPY_SPACE_SLAB_SIZE; + size_t alignment = COPY_SPACE_SLAB_SIZE; + if (flags & COPY_SPACE_ALIGNED) { + GC_ASSERT(copy_space_is_power_of_two(size)); + alignment = size; + } + return gc_platform_acquire_memory(size, alignment); +} + +static void +copy_space_add_slabs(struct copy_space *space, struct copy_space_slab *slabs, + size_t nslabs) { + size_t old_size = space->nslabs * sizeof(struct copy_space_slab*); + size_t additional_size = nslabs * sizeof(struct copy_space_slab*); + space->extents = extents_adjoin(space->extents, slabs, + nslabs * sizeof(struct copy_space_slab)); + space->slabs = realloc(space->slabs, old_size + additional_size); + if (!space->slabs) + GC_CRASH(); + while (nslabs--) + space->slabs[space->nslabs++] = slabs++; +} + +static void +copy_space_shrink(struct copy_space *space, size_t bytes) { + ssize_t pending = copy_space_request_release_memory(space, bytes); + copy_space_page_out_blocks_until_memory_released(space); + + // It still may be the case we need to page out more blocks. Only collection + // can help us then! +} + +static size_t +copy_space_first_payload_block(struct copy_space *space) { + return copy_space_field_logging_blocks(space); +} + +static void +copy_space_expand(struct copy_space *space, size_t bytes) { + GC_ASSERT(!copy_space_fixed_size(space)); + ssize_t to_acquire = -copy_space_maybe_reacquire_memory(space, bytes); + if (to_acquire <= 0) return; + size_t reserved = align_up(to_acquire, COPY_SPACE_SLAB_SIZE); + size_t nslabs = reserved / COPY_SPACE_SLAB_SIZE; + struct copy_space_slab *slabs = + copy_space_allocate_slabs(nslabs, space->flags); + copy_space_add_slabs(space, slabs, nslabs); + + struct gc_lock lock = copy_space_lock(space); + for (size_t slab = 0; slab < nslabs; slab++) { + for (size_t idx = copy_space_first_payload_block(space); + idx < COPY_SPACE_NONHEADER_BLOCKS_PER_SLAB; + idx++) { + struct copy_space_block *block = &slabs[slab].headers[idx]; + block->all_zeroes[0] = block->all_zeroes[1] = 1; + block->in_core = 0; + copy_space_page_out_block(space, block, &lock); + reserved -= COPY_SPACE_BLOCK_SIZE; + } + } + gc_lock_release(&lock); + copy_space_reacquire_memory(space, 0); +} + +static void +copy_space_advance_page_out_queue(void *data) { + struct copy_space *space = data; + struct gc_lock lock = copy_space_lock(space); + for (int age = COPY_SPACE_PAGE_OUT_QUEUE_SIZE - 3; age >= 0; age--) { + while (1) { + struct copy_space_block *block = + copy_space_block_stack_pop(&space->paged_out[age], &lock); + if (!block) break; + copy_space_block_stack_push(&space->paged_out[age + 1], block, &lock); + } + } + gc_lock_release(&lock); +} + +static void +copy_space_page_out_blocks(void *data) { + struct copy_space *space = data; + int age = COPY_SPACE_PAGE_OUT_QUEUE_SIZE - 2; + struct gc_lock lock = copy_space_lock(space); + while (1) { + struct copy_space_block *block = + copy_space_block_stack_pop(&space->paged_out[age], &lock); + if (!block) break; + block->in_core = 0; + block->all_zeroes[0] = block->all_zeroes[1] = 1; + gc_platform_discard_memory(copy_space_block_payload(block), + COPY_SPACE_BLOCK_SIZE); + copy_space_clear_field_logged_bits_for_block(space, block); + copy_space_block_stack_push(&space->paged_out[age + 1], block, &lock); + } + gc_lock_release(&lock); +} + +static int +copy_space_init(struct copy_space *space, size_t size, uint32_t flags, + struct gc_background_thread *thread) { + size = align_up(size, COPY_SPACE_BLOCK_SIZE); + size_t reserved = align_up(size, COPY_SPACE_SLAB_SIZE); + if (flags & COPY_SPACE_ALIGNED) + reserved = copy_space_round_up_power_of_two(reserved); + size_t nslabs = reserved / COPY_SPACE_SLAB_SIZE; + struct copy_space_slab *slabs = copy_space_allocate_slabs(nslabs, flags); + if (!slabs) + return 0; + + pthread_mutex_init(&space->lock, NULL); + space->empty.list.head = NULL; + space->partly_full.list.head = NULL; + space->full.head = NULL; + for (int age = 0; age < COPY_SPACE_PAGE_OUT_QUEUE_SIZE; age++) + space->paged_out[age].list.head = NULL; + space->allocated_bytes = 0; + space->fragmentation = 0; + space->bytes_to_page_out = 0; + space->active_region = 0; + space->atomic_forward = flags & COPY_SPACE_ATOMIC_FORWARDING; + space->flags = flags; + space->allocated_bytes_at_last_gc = 0; + space->fragmentation_at_last_gc = 0; + space->extents = extents_allocate((flags & COPY_SPACE_ALIGNED) ? 1 : 10); + copy_space_add_slabs(space, slabs, nslabs); + struct gc_lock lock = copy_space_lock(space); + for (size_t slab = 0; slab < nslabs; slab++) { + for (size_t idx = copy_space_first_payload_block(space); + idx < COPY_SPACE_NONHEADER_BLOCKS_PER_SLAB; + idx++) { + struct copy_space_block *block = &slabs[slab].headers[idx]; + block->all_zeroes[0] = block->all_zeroes[1] = 1; + block->in_core = 0; + block->is_survivor[0] = block->is_survivor[1] = 0; + if (reserved > size) { + copy_space_page_out_block(space, block, &lock); + reserved -= COPY_SPACE_BLOCK_SIZE; + } else { + copy_space_push_empty_block(space, block, &lock); + } + } + } + gc_lock_release(&lock); + gc_background_thread_add_task(thread, GC_BACKGROUND_TASK_START, + copy_space_advance_page_out_queue, + space); + gc_background_thread_add_task(thread, GC_BACKGROUND_TASK_END, + copy_space_page_out_blocks, + space); + return 1; +} + +#endif // COPY_SPACE_H |