m4drat/memplusplus

C++ memory allocator with smart GC

memplusplus's Issues

iterator for ChunkTreap

Add travis-CI + CTest.

Travis-CI: https://www.youtube.com/watch?v=3ulKzD2cmSw&list=PLs3KjaCtOwSZ2tbuV1hx8Xz-rFZTan2J1&index=83
AppVeyor: https://www.youtube.com/watch?v=R8OrWVVf5CM&list=PLs3KjaCtOwSZ2tbuV1hx8Xz-rFZTan2J1&index=84
CTest: https://www.youtube.com/watch?v=ZlMbqFcJEzA&list=PLs3KjaCtOwSZ2tbuV1hx8Xz-rFZTan2J1&index=86
General: https://www.youtube.com/watch?v=YbgH7yat-Jo

Get rid of the exceptions

Fill issues and milestones.

UniquePtr class

General refactoring

• Allocate should only allocate memory for an object. Create separate method for object construction and one more method to automatically allocate and construct objects.
• Change inheritance scheme (We should only have MemoryManager/MemoryAllocator + GC as a member)
• Inside GC, increase newly created arena size

Check for many calls to GC::Collect(). Right now it fails with `free(): invalid pointer`. example_project, main.cpp:75.

class MemoryManager

We can use 8 bytes of metadata for chunks in use, and 16 bytes for metadata, if chunk is freed.

Transfer arena.begin and arena.end from void* to byte*

Add more security features, e.g. chunk header xor-ing, better randomization, double-free checks, buffer overflow prevention, ...

• heap canaries
• randomized allocations? (probably it isn't possible)
• headers encryption
• better randomization of mmaped arenas (e.g. mimalloc: mi_unix_mmapx)
• Top chunk checks
• Checks on chunks merging
• Replace std::terminate with std::abort?
• On deallocate fill memory with zeroes
• Check for invalid headers (for example: chunk header gets overwritten, so we need to check for invalid merging)
• Check for invalid smart pointer initialization
• Check for double-free
• Check for invalid free

option(MPP_SECURE "Build with advanced security checks" OFF)

Performance comparisons (mimalloc, malloc, jemalloc) + cpu/memory Profiling

Specifically measure: Using valgrind to measure cache misses

Implement performance comparison with these memory allocators:

• gcpp (only speed gain after compacting)
• mimalloc (only allocation/deallocation speed)
• rpmalloc (only allocation/deallocation speed)
• jemalloc (only allocation/deallocation speed)
• hoard (only allocation/deallocation speed)
• supermalloc (only allocation/deallocation speed)
• ptmalloc3 (only allocation/deallocation speed)
• ptmalloc2 (only allocation/deallocation speed) - use latest libc
• mem++ (speed gain after compacting + allocation/deallocation speed)
• Mesh (only allocation/deallocation speed)
• tcmalloc (only allocation/deallocation speed)

Useful links:

1. rpmalloc-benchmark
2. how-can-i-profile-c-code-running-on-linux
3. easy_profiler
4. prof
5. VISUAL BENCHMARKING in C++ (how to measure performance visually)
6. Google benchmark
7. "Performance Matters" by Emery Berger
8. Coz: Finding Code that Counts with Causal Profiling
9. P2329-move_at_scale
10. CppCon 2015: Chandler Carruth "Tuning C++: Benchmarks, and CPUs, and Compilers! Oh My!"
11. Intel v-tune
12. github-gprof2dot
13. How to benchamrk correctly: llvm

Don't forget to use clang stabilizer!

Add PROFILING definition and option to build

#!/bin/bash

# build the program (no special flags are needed)
g++ -std=c++11 cpuload.cpp -o cpuload

# run the program with callgrind; generates a file callgrind.out.12345 that can be viewed with kcachegrind
valgrind --tool=callgrind ./cpuload

# open profile.callgrind with kcachegrind
kcachegrind profile.callgrind

#!/bin/bash

# build the program; For our demo program, we specify -DWITHGPERFTOOLS to enable the gperftools specific #ifdefs
g++ -std=c++11 -DWITHGPERFTOOLS -lprofiler -g ../cpuload.cpp -o cpuload

# run the program; generates the profiling data file (profile.log in our example)
./cpuload

# convert profile.log to callgrind compatible format
pprof --callgrind ./cpuload profile.log > profile.callgrind

# open profile.callgrind with kcachegrind
kcachegrind profile.callgrind

class Heuristics

SharedGcPtr class

1. Calling of ctor/dtor
2. update internal state of GC, while adding/removing SharedGcPtr.
3. Different SharedGcPtr's that points to the same object.
4. Initialization of smart pointers

1. auto ptr = SharedGcPtr<SharedGcPtr>((UserClass*)(void* ptr));
2. auto ptr = SharedGcPtr<SharedGcPtr>(SharedGcPtrptr);
3. auto ptr = SharedGcPtr<SharedGcPtr*>(SharedGcPtr* ptr);

5. SharedGcPtr, that points bot to the beginning of chunk.
6. Active objects iteration
7. make_SharedGcPtr(Args...)

Info:

• https://stackoverflow.com/questions/45723676/c-custom-smart-pointer
• https://codereview.stackexchange.com/questions/200737/custom-smart-pointer-class-template
• https://isocpp.org/wiki/faq/dtors#memory-pools
• replit playground: https://repl.it/repls/JauntyUnripeActivecell
• https://stackoverflow.com/questions/2494471/c-is-it-possible-to-call-a-constructor-directly-without-new/2494619
• http://www.parashift.com/c++-faq-lite/placement-new.html

Allow to use garbage collector only on the part of the heap.

E.g. some part of memory is manually-controlled, and another using GcPtr and GC. So add new info bit to the chunk structure: IsControlledByGc.

Add debug configuration, in which you have guard pages, and much more security-related checks (uaf, double-free, ...)

Add Reallocate method

Transfer some parts from manual memory managment (new and delete) to automatic (smart pointers).

Add method to allocate memory for arrays + custom deallocator

Correct deletion of all Arena's, ChunkTreap's, ...

Check. Somehow `t_arena->m_CurrentlyAllocatedSpace` become really big, because of deallocating chunks with size similar to top chunk's size.

Automate GC::Collect() + add method to check memory consumption + all available memory

Linked to #67

class GarbageCollector

Add pull request tempalte. Add Issue template.

Add readme for release state + instructions how to use this library + Update cmake

https://app.diagrams.net/#G1Asx29Gv8yJ_QW50T7-T0pRbeMXUvFslT

Refactor statistics system

1. Refactor everything statistics-related (right now the system looks like a lot of dirty hacks)
2. GC metrics: #67
3. Use macros to define statistics-related things

class Graph

Add info about visualizers (and other debug features) into README.md

Replace objects.svg with real example

Better visualization of important data structures.

https://eli.thegreenplace.net/2009/11/23/visualizing-binary-trees-with-graphviz

• Objects graph
• ChunkTreap

Global `new` and `delete` replacement.

Add env variables, for example: MPP_DUMP_OBJECTS_GRAPH, MPP_SHOW_STATISTICS

Add options module to operate with env variables.

Problems with SharedGcPtr and void data type

Allocator general improvements

• Add cache layer
• Change allocation logic (firstly reuse all available space in free list, and only then allocate new arena)
• Inside GC, increase newly created arena size

Migrate from `__attribute__((constructor))` to static class instances.

• Profiler class
• EnvOptions class
• MemoryManager class (partially)

Extend fuzzer to make it possible to create/delete/copy shared ptrs + call GC::Collect()

struct Arena, struct Chunk

sharedgcptr-imp.cpp rename to sharedgcptr-imp.hpp

class MemoryAllocator

We dont need to delete objects from vector, if they are not there: sharedgcptr-imp.hpp:62,96,120

Completely migrate to clang. Use sanitizers + valgrind. Add fuzz testing using LLVMFuzzerTestOneInput + KLEE test cases generation.

1. Fully translate everything to use clang.
2. Use sanitizers - add sanitizers build.
3. Create valgrind scripts.
4. Add fuzz testing using LLVMFuzzerTestOneInput: https://www.youtube.com/watch?v=gO0KBoqkOoU
5. Create KLEE build, that will automatically generate test cases.

Better tests coverage + actually measure tests code coverage.

Codecov + project badges: https://www.youtube.com/watch?v=FOcCFGkkQ9c

Fix, cannot allocate more than 17.000 blocks of size 2056 in a row. Segfault, looks like we somewhere use negative offset.

Problem occurs for newly created arena

Customisable heuristics. (e.g. user can write they own heuristics logic)

Tests for ChunkTreap

1. Тест удаления конкретного чанка из дерева (с разными адресами, но одинаковыми размерами). (2 случая: 1-ый чанк лежит перед 2-ым, 1-ый чанк лежит после 2-го)

Complete documentation.

JAVADOC_AUTOBRIEF is NO now. Rewrite all docs with explicit @brief tag.

Multithreading!

Should be in new branch

Update std::allocator interface

We already have default std::allocator interface that uses Allocate/Deallocate functions directly. But we are going to get rid of these functions in the future (due to some problems described in #30). So we have to refactor this interface in such a way, so it's possible to use it without presence of Allocate/Deallocate methods.

Build for windows + AppVeyor

Add ASAN (AddressSanitizer) support

1 Poisoning Memory with (or without) Address Sanitizer
2. __asan_unpoison_memory_region

General layouting algorithm

Potential solution - 1

1. Can be formulated in terms of discrete knapsack w/o repetitions:
2. Item value: number of outgoing pointers / ingoing pointers. "Weight": size of the memory cell.
3. Knapsack capacity: one memory page

Potential solution - 2

1. Greedy approach.

Things to note

1. Base virtual class for all heuristics
2. Tagging system (What type of data structure)

Resources:

1. Algorithms for knapsack problem
2. Multiple Constraint Knapsack Problem