I wrote a simple B-Tree, with Node is defined as:
class Node {
Node* parent = nullptr;
std::uint32_t index = 0;
std::uint32_t height = 1;
std::vector<T> key;
std::vector<unique_alloc_ptr<Node>> child;
// ... details ...
};
where unique_alloc_ptr is the unique_ptr using my custom allocator.
template <typename T>
using unique_alloc_ptr = std::unique_ptr<T, std::function<void(T*)>>;
template <typename T>
unique_alloc_ptr<T> make_unique_fixed(FixedAllocator<T>& alloc) {
T* ptr = alloc.allocate(1);
alloc.construct(ptr);
std::function<void(T*)> deleter;
auto deleter_ = [](T* p, FixedAllocator<T>& alloc) {
alloc.destroy(p);
alloc.deallocate(p, 1);
};
deleter = [&deleter_, &alloc](auto&& PH1) { return deleter_(std::forward<decltype(PH1)>(PH1), alloc); };
return std::unique_ptr<T, decltype(deleter)>(ptr, deleter);
}
The custom allocator uses the memory pool as:
template <typename T>
class FixedAllocator {
struct Chunk {
// details ...
unsigned char data_[blockSize_ * numBlocks_];
};
// details ...
std::vector<Chunk> chunks_;
and my B-Tree uses the memory pool as member variable:
class BTree {
class Node {
// ...
};
// details ...
FixedAllocator<Node> alloc;
unique_alloc_ptr<Node> root;
};
But this gives segfault. As I guess, double free is the problem.
When lifetime of BTree ends, FixedAllocator<Node> is destroyed,
and its internal buffer std::vector<Chunk> is also destroyed.
The problem is, unique_alloc_ptr<Node> is also destroyed as well,
calling destructor of std::vector<unique_alloc_ptr<Node>> child,
which uses FixedAllocator<Node> as internal memory pool,
so double free problem occurs.
How can I solve this problem?
EDIT: Detailed implementation of FixedAllocator
template <typename T>
class FixedAllocator {
struct Chunk {
static constexpr std::size_t blockSize_ = sizeof(T);
static constexpr unsigned char numBlocks_ = FixedAllocator::numBlocks_;
Chunk() {
unsigned char i = 0;
for (unsigned char * p = &data_[0]; i != numBlocks_; p += blockSize_) {
*p = ++i;
}
}
void* allocate() {
unsigned char* result = &data_[firstAvailableBlock_ * blockSize_];
firstAvailableBlock_ = *result;
--blocksAvailable_;
return result;
}
void deallocate(void* p) {
assert(p >= &data_[0]);
auto* toRelease = static_cast<unsigned char*>(p);
assert((toRelease - &data_[0]) % blockSize_ == 0);
*toRelease = firstAvailableBlock_;
firstAvailableBlock_ = static_cast<unsigned char>((toRelease - &data_[0]) / blockSize_);
assert(firstAvailableBlock_ == (toRelease - &data_[0]) / blockSize_);
++blocksAvailable_;
}
bool hasBlock(void* p, std::size_t chunkLength) const {
auto* pc = static_cast<unsigned char*>(p);
return (&data_[0] <= pc) && (pc < &data_[chunkLength]);
}
[[nodiscard]] bool hasAvailable() const {
return (blocksAvailable_ == numBlocks_);
}
[[nodiscard]] bool isFilled() const {
return !blocksAvailable_;
}
unsigned char data_[blockSize_ * numBlocks_];
unsigned char firstAvailableBlock_ = 0;
unsigned char blocksAvailable_ = numBlocks_;
};
private:
static constexpr std::size_t blockSize_ = sizeof(T);
static constexpr unsigned char numBlocks_ = std::numeric_limits<unsigned char>::max();
std::vector<Chunk> chunks_;
Chunk* allocChunk_ = nullptr;
Chunk* deallocChunk_ = nullptr;
Chunk* emptyChunk_ = nullptr;
public:
using value_type = T;
void* doAllocate() {
if (!allocChunk_ || !allocChunk_->blocksAvailable_) {
auto it = chunks_.begin();
for (; ; ++it) {
if (it == chunks_.end()) {
chunks_.emplace_back();
allocChunk_ = &chunks_.back();
deallocChunk_ = &chunks_.front();
break;
}
if (it->blocksAvailable_) {
allocChunk_ = &*it;
break;
}
}
}
assert(allocChunk_);
assert(allocChunk_->blocksAvailable_);
return allocChunk_->allocate();
}
value_type* allocate(std::size_t n) {
assert(n == 1);
auto* p = static_cast<value_type*>(doAllocate());
return p;
}
Chunk* findVicinity(void* p) const {
assert(!chunks_.empty() && deallocChunk_);
const std::size_t chunkLength = numBlocks_ * blockSize_;
// bidirectional search
Chunk* lo = deallocChunk_;
Chunk* hi = deallocChunk_ + 1;
const Chunk* lbound = &chunks_.front();
const Chunk* hbound = &chunks_.back() + 1;
if (hi == hbound) {
hi = nullptr;
}
for (;;) {
if (lo) {
if (lo->hasBlock(p, chunkLength)) {
return lo;
}
if (lo == lbound) {
lo = nullptr;
if (!hi) {
break;
}
} else {
--lo;
}
}
if (hi) {
if (hi->hasBlock(p, chunkLength)) {
return hi;
}
if (++hi == hbound) {
hi = nullptr;
if (!lo) {
break;
}
}
}
}
return nullptr;
}
void deallocate(void* p, std::size_t n) noexcept {
assert(n == 1);
assert(!chunks_.empty());
assert(&chunks_.front() <= deallocChunk_);
assert(&chunks_.back() >= deallocChunk_);
assert(&chunks_.front() <= allocChunk_);
assert(&chunks_.back() >= allocChunk_);
Chunk* foundChunk = nullptr;
const std::size_t chunkLength = numBlocks_ * blockSize_;
if (deallocChunk_->hasBlock(p, chunkLength)) {
foundChunk = deallocChunk_;
} else {
foundChunk = findVicinity(p);
}
assert(foundChunk && foundChunk->hasBlock(p, chunkLength));
deallocChunk_ = foundChunk;
// double free check
assert(emptyChunk_ != deallocChunk_);
assert(!deallocChunk_->hasAvailable());
assert(!emptyChunk_ || emptyChunk_->hasAvailable());
deallocChunk_->deallocate(p);
if (deallocChunk_->hasAvailable()) {
// only release chunk if there are 2 empty chunks.
if (emptyChunk_) {
// if last chunk is empty, just let deallocChunk_ points
// to empty chunk, and release the last.
// otherwise, swap two and release an empty chunk
Chunk* lastChunk = &chunks_.back();
if (lastChunk == deallocChunk_) {
deallocChunk_ = emptyChunk_;
} else if (lastChunk != emptyChunk_) {
std::swap(*emptyChunk_, *lastChunk);
}
assert(lastChunk->hasAvailable());
chunks_.pop_back();
if ((allocChunk_ == lastChunk) || (allocChunk_->isFilled())) {
allocChunk_ = deallocChunk_;
}
}
emptyChunk_ = deallocChunk_;
}
}
template <typename... Args>
void construct (value_type* p, Args&&... args) {
std::construct_at(p, std::forward<Args>(args)...);
}
void destroy(value_type* p) {
std::destroy_at(p);
}
};