A custom memory allocator in c++

Question

Recently I became interested in implementing a FORTH language interpreter. That led me to read about memory models etc. which led me to write this custom memory allocator in c++. It's very dumb as memory allocators go but it seems to be working as intended. I'd like you to confirm that it is and tell me if there is anything wrong or I should be doing differently.

To explain the code:

Storage is the "memory" itself. It consists of an array of MEMSIZE bytes and a bitset of MEMSIZE length where each bit will be on if the corresponding byte of memory is allocated or not. I also implemented operator<< so I could dump out the bitmap for debugging purposes.

Allocator is the allocator itself. It is a template struct which is specialized for each data type that can be constructed. I aimed to fulfill all the requirements for a std::c++ 17 allocator.

Cell and Flag are the only valid data types that can be used in this program. Cell is a 64bit value which can be accessed as a 64bit signed integer or as an array of 8 bytes. It must be aligned to an 8 byte boundary. Flag is 1 byte long. Eventually it will be used to implement booleans but here it can be any value from 0 - 255. Both Cell and Flag have custom new and delete methods that use Allocator.

main() contains some tests to see if everything works ok.

Here is the code. I also have some questions which I have asked at the end.

#include <array>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <memory>
#include <new>

constexpr std::size_t MEMSIZE = 80;

static struct Storage {
    using Memory = std::array<std::uint8_t, MEMSIZE>;
    Memory memory_{};
    std::bitset<MEMSIZE> free_{};

    friend std::ostream& operator<<(std::ostream&, const Storage&);
} storage;

std::ostream& operator<<(std::ostream& out, const Storage& storage) {
    for (std::size_t i = 0; i < MEMSIZE; i++) {
        out << (storage.free_[i] ? '*' : '_');
    }

    return out;
}

template<class T>
struct Allocator {
public:
    using value_type = T;

    Allocator() noexcept {
    }

    template<class U>
    Allocator(const Allocator<U>&) noexcept {
    }

    T* allocate(std::size_t n) {
        for (std::size_t i = 0; i < MEMSIZE; i += alignof(T)) {
            bool fits = true;
            if (storage.free_[i] == 0) {
                for (std::size_t j = i; j < i + n; j++) {
                    if (storage.free_[j] == 1) {
                        fits = false;
                        break;
                    }
                }
                if (fits) {
                    for (std::size_t j = i; j < i + n; j++) {
                        storage.free_.set(j);
                    }
                    return reinterpret_cast<T*>(&storage.memory_[i]);
                }
            }
        }

        throw std::bad_alloc();
    }

    void deallocate(T* p, std::size_t n) {
        auto start = std::distance(&storage.memory_[0],
            reinterpret_cast<Storage::Memory::pointer>(p));
        for (std::size_t i = start; i < start + n; i++) {
            storage.free_.reset(i);
        }
    }
};

template <class T, class U>
constexpr bool operator== (const Allocator<T>& lhs, const Allocator<U>& rhs)
noexcept {
    return true;
}

template <class T, class U>
constexpr bool operator!= (const Allocator<T>& lhs, const Allocator<U>& rhs)
noexcept {
    return !operator==(lhs, rhs);
}

struct Cell;
static Allocator<Cell> cellAlloc;

struct Cell {
    using size_type = std::int64_t;
    constexpr static std::size_t CELLSIZE = sizeof(size_type);

    explicit Cell() : Cell(0) {
    }

    Cell(size_type val) : val_{val} {
    }

    static void* operator new  ( std::size_t n ) {
        return std::allocator_traits<Allocator<Cell>>::allocate(cellAlloc, n);
    }

    static void* operator new[]  ( std::size_t n ) {
        return operator new(n - sizeof(Cell));
    }

    static void operator delete (void *ptr, std::size_t n = 1) {
        std::allocator_traits<Allocator<Cell>>::deallocate(
            cellAlloc, static_cast<Cell*>(ptr), n);
    }

    static void operator delete[] (void *ptr, std::size_t n) {
        operator delete(ptr, n - sizeof(Cell));
    }

    union {
        size_type val_;
        std::uint8_t bytes_[CELLSIZE];
    };
};

struct Flag;
static Allocator<Flag> flagAlloc;

struct Flag {
    Flag(std::uint8_t val) : val_{val} {
    }

    static void* operator new  ( std::size_t n ) {
        return std::allocator_traits<Allocator<Flag>>::allocate(flagAlloc, n);
    }

    static void* operator new[]  ( std::size_t n ) {
        return operator new(n - sizeof(std::uint8_t));
    }

    static void operator delete (void *ptr, std::size_t n = 1) {
        std::allocator_traits<Allocator<Flag>>::deallocate(
            flagAlloc, static_cast<Flag*>(ptr), n);
    }

    static void operator delete[] (void *ptr, std::size_t n) {
        operator delete(ptr, n - sizeof(std::uint8_t));
    }

    std::uint8_t val_;
};

int main() {
    std::cout << "The size of Cell is " << sizeof(Cell) << '\n';
    std::cout << "The size of Flag is " << sizeof(Flag) << '\n';

    std::cout << "Allocating...\n";
    Cell* cells[10];
    for (auto i = 0; i < 10; i++) {
        cells[i] = new Cell(i * 1000);
    }
    std::cout << storage << '\n';
    for (auto i = 0; i < 10; i++) {
        std::cout << cells[i]->val_ << ' ';
    }
    std::cout << '\n';

    std::cout << "Allocate one more...\n";
    try {
        new Cell(10000);
    } catch (std::bad_alloc&) {
        std::cout << "No, out of memory.\n";
    }

    std::cout << "Deallocating...\n";
    for (auto i = 0; i < 10; i++) {
        delete cells[i];
    }
    std::cout << storage << '\n';

    std::cout << "Reallocating...\n";
    auto cellarray = new Cell[10]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    std::cout << storage << '\n';
    for (auto i = 0; i < 10; i++) {
        std::cout << cellarray[i].val_ << ' ';
    }
    std::cout << '\n';

    std::cout << "Deallocating...\n";
    delete[] cellarray;
    std::cout << storage << '\n';

    std::cout << "Allocating Flag...\n";
    auto flag = new Flag{255};
    std::cout << storage << '\n';
    std::cout << (int)flag->val_ << '\n';

    std::cout << "Flag + Allocating Cell...\n";
    auto cell = new Cell(99);
    std::cout << storage << '\n';
    std::cout << cell->val_ << '\n';

    std::cout << "Deallocating Flag...\n";
    delete flag;
    std::cout << storage << '\n';

    std::cout << "Another Cell...\n";
    auto cell2 = new Cell(66);
    std::cout << storage << '\n';
    std::cout << cell2->val_ << ' ' << cell->val_ << '\n';

    std::cout << "Deallocating...\n";
    delete cell;
    delete cell2;
    std::cout << storage << '\n';

    std::cout << "Enough space...\n";
    Flag *flags[MEMSIZE];
    for (std::size_t i = 0; i < MEMSIZE; i++) {
        flags[i] = new Flag(0);
    }
    for (std::size_t i = 64; i < 71; i++) {
        delete flags[i];
    }
    try {
        new Cell(12345678);
    } catch (std::bad_alloc&) {
        std::cout << "No, not enough space.\n";
    }
    std::cout << storage << '\n';

    std::cout << "Aligned...\n";
    for (std::size_t i = 64; i < 71; i++) {
        flags[i] = new Flag(0);
    }
    for (std::size_t i = 65; i < 73; i++) {
        delete flags[i];
    }
    try {
        new Cell(87654321);
    } catch (std::bad_alloc&) {
        std::cout << "No, misaligned.\n";
    }
    std::cout << storage << '\n';

}

1. For Storage I suppose using a bitset like this will not be scalable for large amounts of memory. How big can memory get before it becomes worth my while to implement some other scheme instead?
2. Am I missing any required functionality from Allocator?
3. For Allocator I left the constructor and copy constructor empty because the struct has no data members. If I used =default instead would that work? They are required to be marked noexcept.
4. Similarly for operator== and !=. All instances of Allocator<T> will be equal because they have no data correct?
5. Must the specialized allocators for each type be static and defined outside the type itself? It seems a bit untidy to me.

Your comments/critiques are most welcome.

Answer 1

1. Looking at this, you have a single static with all the memory packed together and all bits to indicate 'free/available'. I don't see a way to improve the memory usage of these bits. If the MEMSIZE would be variable, you could consider other techniques, though in this case, the bitset looks the most efficient.
2. Looking at the allocator requirements, I believe all required elements are available. You could still add type defs like size_type, difference_type, propagate_on_container_move_assignment, is_always_equal ... to improve some usage by std::vector. These are optional and the provided example on the page doesn't have them either.
3. = default is a very good choice. Normally, this default method becomes noexcept out of it's own. You could add it, though, if you than change the class so the default behavior no longer is noexcept, it makes the method deleted.
4. You are correct, all instances of Allocator can be considered equal. (See the is_always_equal typedef I've mentioned before)
5. As your allocators don't have state, you don't need a static variable for them. You could create them when needed. With some CRTP you could reduce the amount of code needed in the classes using it.

Some other random remarks:

• Storage::operator<< could use a ranged based for loop
• Your allocate function could be optimized, as you don't have to check every combination. (aka: If you encounter 5 free elements and you need to allocate 10, you can jump to after that first used element
• You could replace some of the for-loops with std::all_of/std::none_of (or if you implement the previous std::find)
• You don't have protection for out-of bounds checking in the inner loop. (If you are at index 76 and need to allocate 10 elements)
• Why would you decrement n in the new operator for an array.