c++ - 带有自定义分配器的 unique_ptr

Question

我写了一个简单的B-Tree，Node定义为：

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 ...
};

unique_alloc_ptr使用我的自定义分配器的 unique_ptr在哪里。

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);
}

自定义分配器将内存池用作：

template <typename T>
class FixedAllocator {
    struct Chunk {
        // details ...
        unsigned char data_[blockSize_ * numBlocks_];
    };
    // details ...
    std::vector<Chunk> chunks_;

我的 B-Tree 使用内存池作为成员变量：

class BTree {
     class Node {
        // ...
     };
     // details ...
     FixedAllocator<Node> alloc;
     unique_alloc_ptr<Node> root;
};

但这给出了段错误。正如我猜想的那样，双重免费是问题所在。

当 BTree 的生命周期结束时，FixedAllocator<Node>被销毁，其内部缓冲区std::vector<Chunk>也被销毁。

问题是，unique_alloc_ptr<Node>也被销毁了，调用了std::vector<unique_alloc_ptr<Node>>子的析构函数，它FixedAllocator<Node>用作内部内存池，所以出现了双重释放问题。

我怎么解决这个问题？

编辑：详细实施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);
    }

};

标签： c++memory-management