#pragma once #include #include #include #include #include #include #include namespace types { namespace __allocator { class brk_memory_allocator { public: using byte = uint8_t; using size_type = size_t; struct mem_blk_flags { uint8_t is_free; uint8_t has_next; uint8_t _unused2; uint8_t _unused3; }; struct mem_blk { size_t size; struct mem_blk_flags flags; // the first byte of the memory space // the minimal allocated space is 8 bytes byte data[]; }; private: byte* p_start; byte* p_break; byte* p_limit; brk_memory_allocator() = delete; brk_memory_allocator(const brk_memory_allocator&) = delete; brk_memory_allocator(brk_memory_allocator&&) = delete; constexpr byte* brk(byte* addr) { if (unlikely(addr >= p_limit)) return nullptr; return p_break = addr; } constexpr byte* sbrk(size_type increment) { return brk(p_break + increment); } constexpr mem_blk* _next(mem_blk* blk, size_type blk_size) { auto* p = std::bit_cast(blk); p += sizeof(mem_blk); p += blk_size; return std::bit_cast(p); } // blk MUST be free constexpr void unite_afterwards(mem_blk* blk) { while (blk->flags.has_next) { auto* blk_next = _next(blk, blk->size); if (!blk_next->flags.is_free) break; blk->size += sizeof(mem_blk) + blk_next->size; blk->flags.has_next = blk_next->flags.has_next; } } // @param start_pos position where to start finding // @param size the size of the block we're looking for // @return found block if suitable block exists, if not, the last block constexpr mem_blk* find_blk(mem_blk* start_pos, size_type size) { while (true) { if (start_pos->flags.is_free) { unite_afterwards(start_pos); if (start_pos->size >= size) break; } if (!start_pos->flags.has_next) break; start_pos = _next(start_pos, start_pos->size); } return start_pos; } constexpr mem_blk* allocate_new_block(mem_blk* blk_before, size_type size) { auto ret = sbrk(sizeof(mem_blk) + size); if (!ret) return nullptr; mem_blk* blk = _next(blk_before, blk_before->size); blk_before->flags.has_next = 1; blk->flags.has_next = 0; blk->flags.is_free = 1; blk->size = size; return blk; } constexpr void split_block(mem_blk* blk, size_type this_size) { // block is too small to get split // that is, the block to be split should have enough room // for "this_size" bytes and also could contain a new block if (blk->size < this_size + sizeof(mem_blk) + 8) return; mem_blk* blk_next = _next(blk, this_size); blk_next->size = blk->size - this_size - sizeof(mem_blk); blk_next->flags.has_next = blk->flags.has_next; blk_next->flags.is_free = 1; blk->flags.has_next = 1; blk->size = this_size; } public: constexpr brk_memory_allocator(byte* start, size_type limit) : p_start(start) , p_limit(start + limit) { brk(p_start); auto* p_blk = std::bit_cast(sbrk(0)); p_blk->size = 8; p_blk->flags.has_next = 0; p_blk->flags.is_free = 1; } constexpr void* alloc(size_type size) { // align to 8 bytes boundary size = (size + 7) & ~7; auto* block_allocated = find_blk(std::bit_cast(p_start), size); if (!block_allocated->flags.has_next && (!block_allocated->flags.is_free || block_allocated->size < size)) { // 'block_allocated' in the argument list is the pointer // pointing to the last block block_allocated = allocate_new_block(block_allocated, size); if (!block_allocated) return nullptr; } else { split_block(block_allocated, size); } block_allocated->flags.is_free = 0; auto* blkpos = std::bit_cast(block_allocated); if (blkpos > p_start) p_start = blkpos; return block_allocated->data; } constexpr void free(void* ptr) { auto* blk = std::bit_cast( std::bit_cast(ptr) - sizeof(mem_blk)); blk->flags.is_free = 1; if (std::bit_cast(blk) < p_start) p_start = std::bit_cast(blk); // unite free blocks nearby unite_afterwards(blk); } }; }; // namespace __allocator template concept Allocator = requires(size_t size, typename T::value_type* ptr) { typename T::value_type; { T::allocate_memory(size) }; { T::deallocate_memory(ptr) }; std::is_same_v; std::is_same_v; }; template class allocator_traits; namespace __allocator { inline char __ident_heap[0x100000]; inline __allocator::brk_memory_allocator m_alloc { (uint8_t*)__ident_heap, sizeof(__ident_heap) }; } // namespace __allocator template class kernel_ident_allocator { public: using value_type = T; static constexpr value_type* allocate_memory(size_t count) { return static_cast(__allocator::m_alloc.alloc(count)); } static constexpr void deallocate_memory(value_type* ptr) { __allocator::m_alloc.free(ptr); } }; template