Pasted

 
#include <memory>
#include <new>
#include <cstdlib>
#include <cstdio>
#include <utility>
#include <array>
#include <string>
#include <vector>
 
using std::printf;
using std::size_t;
using std::string;
using std::vector;
 
// MALLOCATOR
 
template <typename T>
struct mallocator {
    using value_type = T;
    
    mallocator() = default;
    template <typename U>
    constexpr mallocator(const mallocator<U>&) noexcept {}
 
    [[nodiscard]] T *allocate(size_t count) {
        return static_cast<T *>(std::malloc(count * sizeof(T)));
    }
    void deallocate(T *ptr, size_t) noexcept {
        return free(ptr);
    }
};
 
template <typename T, typename U>
bool operator== (const mallocator<T>&, const mallocator<U>&) { return true; }
template <typename T, typename U>
bool operator!= (const mallocator<T>&, const mallocator<U>&) { return false; }
 
// GARBAGE COLLECTOR
 
bool alloc_debug = false;
 
struct allocation {
    size_t *base;
    size_t *top;
    bool active; // enum class?
    bool marked; // enum class?
};
 
vector<
    allocation,
    mallocator<allocation>
> allocations = {};
 
 
bool heuristic = true;
 
void *GC_allocate(size_t);
void GC_free(void *);
void GC_ondelete(void *);
void GC_collect();
 
void *GC_allocate(size_t len) {
    printf("GC_allocate\n");
    if (heuristic) {
        GC_collect();
    }
 
    auto ptr = std::malloc(len);
    printf("  allocated %p : %lu\n", ptr, len);
 
    size_t *base = static_cast<size_t *>(ptr);
    size_t *top = base + (len / sizeof(size_t));
 
    allocations.push_back({base, top, true, false});
    return ptr;
}
 
void GC_free(void *ptr) {
    printf("GC_free\n");
    std::free(ptr);
}
 
void GC_ondelete(void *) {
    printf("GC_ondelete\n");
    // pass
}
 
size_t *top_of_stack;
 
void scan_mark_recurse(size_t *, size_t *);
 
void mark_from_registers() {
    std::array<size_t *, 9> registers;
 
    asm ("mov %%rax, %0" : "=r"(registers[0]));
    asm ("mov %%rcx, %0" : "=r"(registers[1]));
    asm ("mov %%rbx, %0" : "=r"(registers[2]));
    asm ("mov %%rdx, %0" : "=r"(registers[3]));
    asm ("mov %%rsi, %0" : "=r"(registers[4]));
    asm ("mov %%rdi, %0" : "=r"(registers[5]));
    asm ("mov %%rsp, %0" : "=r"(registers[6]));
    asm ("mov %%rbp, %0" : "=r"(registers[7]));
    // asm ("mov %%rip, %0" : "=r"(registers[8]));
 
    for (auto const& r : registers) {
        // copypaste from below
        for (auto& alloc : allocations) {
            // printf("    looking for allocation: %p\n", (void *)alloc.base);
            if (alloc.marked || !alloc.active) {
                continue;
            }
            if (r >= alloc.base && r < alloc.top) { // CLEANUP TYPE MESS
                alloc.marked = true;
                printf("    found %p\n", (void *)alloc.base);
                scan_mark_recurse(alloc.base, alloc.top);
                continue;
            }
        }
    }
}
 
void scan_mark_recurse(size_t *from, size_t *to) {
    printf("scan_mark_recurse(%p, %p);\n", (void *)from, (void *)to);
    int delta = from > to ? -1 : 1;
 
    for (size_t *v = from; v != to; v += delta) {
        printf("    v: %p -> %016lx\n", (void *)v, *v);
        for (auto& alloc : allocations) {
            // printf("    looking for allocation: %p\n", (void *)alloc.base);
            if (alloc.marked || !alloc.active) {
                continue;
            }
            if ((size_t*)*v >= alloc.base && (size_t*)*v < alloc.top) { // CLEANUP TYPE MESS
                alloc.marked = true;
                printf("    found %p\n", (void *)alloc.base);
                scan_mark_recurse(alloc.base, alloc.top);
                continue;
            }
        }
    }
}
 
size_t *stack_ptr() {
    size_t *ptr;
    asm ("mov %%rsp, %0" : "=r"(ptr));
    return ptr;
}
 
void GC_collect() {
    printf("GC_collect\n");
    mark_from_registers();
    scan_mark_recurse(top_of_stack, stack_ptr());
 
    size_t allocs = 0, freed = 0;
    for (auto& alloc : allocations) {
        if (!alloc.active) continue;
        if (!alloc.marked) {
            // printf("  %p not found - freeing\n", (void *)alloc.base);
            freed += 1;
            GC_free(alloc.base);
            alloc.active = false; // not final solution - delete from array?
        } else {
            // printf("  %p found - keeping\n", (void *)alloc.base);
            allocs += 1;
            alloc.marked = false;
        }
    }
 
    printf("Did a collection: allocs: %lu, freed %lu\n", allocs, freed);
}
 
// OPERATORS
 
void * operator new(size_t size) {
    return GC_allocate(size);
}
void operator delete(void *ptr) noexcept {
    GC_ondelete(ptr);
}
void operator delete(void *ptr, size_t) noexcept {
    GC_ondelete(ptr);
}
 
// MAIN  /  TEST
 
struct destruct {
    string name;
    destruct(string name) : name(name) {
        printf("destruct (%s) constructed\n", name.c_str());
    }
    ~destruct() {
        printf("destruct (%s) destroyed!\n", name.c_str());
    }
};
 
int *inner() {
    vector<int> v1 = {1, 2, 3};
    vector<int> v2 = {3, 4, 5};
    destruct d{"local"};
    auto e = new destruct{"heap"};
    return &v2[1];
}
 
int main(int argc, char **argv) {
    (void)argc;
    top_of_stack = reinterpret_cast<size_t *>(&argv);
    
    int *f = inner();
    GC_collect();
    printf("%i\n", *f);
    f = nullptr;
    GC_collect();
}