I have a few unordered_maps that I use with custom allocators. In this case I use a rudimentary bump allocator that just simply linearly allocates new memory from an existing continiuos block.
But when I try and call reserve on these maps after a while, they throw an access violaton exception at the line within the std list file I'll show below in :
_List_unchecked_const_iterator& operator () noexcept {
_Ptr = _Ptr->_Next;
return *this;
}
My allocator has enough memory left so I don't think it's because I am running out of memory.
Here's some self contained code that demonstrates it. Copy/paste and run it to see the issue.
#include <stdlib.h>
#include <unordered_map>
#include <vector>
#include <list>
#include <memory>
#define SEQ(type, val) sizeof(type) * val
struct ImpAllocator {
virtual void* Allocate(size_t pSize) = 0;
virtual void Free(void* pPtr) = 0;
};
struct SysAllocator : public ImpAllocator {
void* Allocate(size_t pSize) override {
return malloc(pSize);
}
void Free(void* pPtr) override {
free(pPtr);
}
};
template <class T>
class StdAllocatorWrapper {
public:
std::shared_ptr<ImpAllocator> mInternalAllocator;
using value_type = T;
StdAllocatorWrapper() = default;
StdAllocatorWrapper(std::shared_ptr<ImpAllocator> pInternalAllocator) :
mInternalAllocator(pInternalAllocator)
{}
~StdAllocatorWrapper() = default;
StdAllocatorWrapper(const StdAllocatorWrapper<T>& pOther) = default;
template<class U>
StdAllocatorWrapper(const StdAllocatorWrapper<U>& pOther) {
this->mInternalAllocator = pOther.mInternalAllocator;
}
value_type* allocate(size_t pNumberOfObjects) {
return reinterpret_cast<T*>(mInternalAllocator->Allocate(SEQ(T, pNumberOfObjects)));
}
void deallocate(value_type* pPointer, size_t pNumberOfObjects) {
mInternalAllocator->Free(pPointer);
}
};
template <class T, class U>
bool operator==(StdAllocatorWrapper<T> const& pL, StdAllocatorWrapper<U> const& pR) noexcept {
return pL.mInternalAllocator == pR.mInternalAllocator;
}
template <class T, class U>
bool operator!=(StdAllocatorWrapper<T> const& pL, StdAllocatorWrapper<U> const& pR) noexcept {
return !(pL == pR);
}
template<typename T> using AllocWrapper = StdAllocatorWrapper<T>;
template<typename T, typename K> using Pair = std::pair<const T, K>;
template<typename T, typename K> using PairAllocWrapper = StdAllocatorWrapper<Pair<T, K>>;
template<typename T> using AllocatedVector = std::vector<T, AllocWrapper<T>>;
template<typename T> using AllocatedList = std::list<T, AllocWrapper<T>>;
template<typename T, typename K> using AllocatedUnorderedMap = std::unordered_map<T, K, std::hash<T>, std::equal_to<T>, PairAllocWrapper<T, K>>;
typedef unsigned char* MemBlock;
class BumpAllocator : public ImpAllocator {
private:
std::shared_ptr<ImpAllocator> mInternalAllocator;
size_t mSize;
MemBlock mBlock;
MemBlock mStart;;
size_t mCurrent;
public:
BumpAllocator(size_t pSize, std::shared_ptr<ImpAllocator> pInternalAllocator) :
mInternalAllocator(pInternalAllocator),
mSize(pSize),
mCurrent(0) {
mBlock = reinterpret_cast<MemBlock>(mInternalAllocator->Allocate(pSize));
mStart = mBlock;
}
~BumpAllocator() {
mInternalAllocator->Free(mBlock);
}
void* Allocate(size_t pSize) override {
printf("\n bump allocator wrapper requested: %d", pSize);
if (mCurrent pSize > mSize) {
return nullptr;
}
MemBlock _return = mBlock mCurrent;
mCurrent = pSize;
return _return;
}
void Free(void* pFre) override {
}
void Reset() {
mCurrent = 0;
}
};
struct Animation {
};
struct Texture {
};
struct TextureArrayIndex {
//TexturePointer mTexture;
unsigned int mIndex;
std::shared_ptr<Texture> mTexture;
};
struct RenderOrder {
float mDeltaTime;
std::string mAnimationName;
std::shared_ptr<Animation> mAnim;
};
using Textures = AllocatedUnorderedMap<int, TextureArrayIndex>;
using TexturesAllocWrapper = PairAllocWrapper<int, TextureArrayIndex>;
using RenderOrdersVector = AllocatedVector<RenderOrder>;
using RenderOrdersAllocWrapper = AllocWrapper<RenderOrder>;
using RenderBucket = AllocatedUnorderedMap<unsigned int, RenderOrdersVector>;
using RenderBuckets = AllocatedUnorderedMap<std::shared_ptr<Animation>, RenderBucket>;
using RenderBucketAllocWrapper = PairAllocWrapper<unsigned int, RenderOrdersVector>;
using RenderBucketsAllocWrapper = PairAllocWrapper<std::shared_ptr<Animation>, RenderBucket>;
struct Renderer {
std::shared_ptr<BumpAllocator> mInternalAllocator;
Textures mTextureArrayIndexMap;
RenderBuckets mAnimationRenderBuckets;
Renderer(std::shared_ptr<ImpAllocator> pAllocator) :
mInternalAllocator(std::make_shared<BumpAllocator>(60000, pAllocator)),
mTextureArrayIndexMap(Textures(TexturesAllocWrapper(mInternalAllocator))),
mAnimationRenderBuckets(RenderBuckets(RenderBucketsAllocWrapper(mInternalAllocator)))
{}
void Begin() {
mTextureArrayIndexMap = Textures(TexturesAllocWrapper(mInternalAllocator));
mTextureArrayIndexMap.reserve(2);
mAnimationRenderBuckets = RenderBuckets(RenderBucketsAllocWrapper(mInternalAllocator));
mAnimationRenderBuckets.reserve(1000);
}
void Render() {
}
void Flush() {
mInternalAllocator->Reset();
}
};
int main(int argc, char* argv[]) {
Renderer _renderer(std::make_shared<SysAllocator>());
for (int i = 0; i < 1000; i ) {
_renderer.Begin();
_renderer.Flush();
}
}
CodePudding user response：
I could not reproduce the error with the code given... But the code does not use std::unordered_map, so the error must come from there.
First issue. In your allocators:
void* SysAllocator::Allocate(size_t pSize) override {
return malloc(pSize); // allocator returns NULL on error.
}
void* BumpAllocator::Allocate(size_t pSize) override {
printf("\n bump allocator wrapper requested: %d", pSize);
if (mCurrent pSize > mSize) {
return nullptr; // allocator returns NULL on error.
}
MemBlock _return = mBlock mCurrent;
mCurrent = pSize;
return _return;
}
Your custom allocators return NULL on error, but STL containers expect their allocators to throw a std::bad_alloc exception on error. That's mandatory.
You should change your allocators:
void* SysAllocator::Allocate(size_t pSize) override {
void* p = malloc(pSize);
if (!p)
throw std::bad_alloc();
return p;
}
void* BumpAllocator::Allocate(size_t pSize) override {
printf("\n bump allocator wrapper requested: %d", pSize);
if (mCurrent pSize > mSize)
throw std::bad_alloc();
MemBlock _return = mBlock mCurrent;
mCurrent = pSize;
return _return;
}
This will not solve your problem, but the point of error will have moved to the time of allocation.
I think your problem comes from a lack of memory. std::unordered_map uses hash buckets, and these could very likely use more memory than you anticipated. To investigate, set breakpoints on the throw lines in your Allocate() functions to catch the error right when it happens.
CodePudding user response：
Apart from the issue mentioned by Michael Roy, there is another bug here
void Reset() {
mCurrent = 0;
}
This method, which is called indirectly from your main, means that further allocations will reuse already allocated memory. This is the immediate cause of the crash in the code you posted.
If you comment out the line mCurrent = 0; then you do actually run out of memory and you get the null pointer bug explained by Michael Roy in the other answer.
Tested with MSVC (since that seems to be significant).