Skip to main content
gamedev.net
🔒 Locked

Problem with push_back on vector

Started by Gammastrahler 10 replies 1.6k views
Original Post
Gammastrahler
Gammastrahler
Hi, i have written a custom memory allocator, and i have a vector of memblocks for housekeeping. if i need to create a new block, i call push_back, but this crashes after creating some blocks! here is the relevant code 

if (bytes < freeBlock->size)
{
    MEMBLOCK newBlock;

    newBlock.size = freeBlock->size - bytes;
    newBlock.used = false;
			
    freeBlock->size = bytes;

    _blockList.push_back(newBlock);   // crashes!!!!

    _freeMem -= bytes;
}
is it because the newBlock variable is local? would be nice of anyone could help me with this problem...
Palidine
Palidine
Couple things:

1) post the declaration of MEMBLOCK

2) newBlock.size should = bytes, not freeBlock->size - bytes

the way you have it coded now, every time you allocates "bytes" you are setting newBlock.size equal to the new current total of unused bytes.

#2 is probably your problem.

Say you have 10 bytes.

User asks for 1 byte
you are giving them 9 bytes.

Next user asks for 1 byte
You are giving them 8 bytes.

etc etc

The second time you allocate, you are out of memory.

-me
ToohrVyk
ToohrVyk
Possible reasons for the crash:

1° _blockList is not a valid object (you might have dereferenced a null pointer somewhere when calling this member function).

2° _blockList has been corrupted by an overflow.

3° There is an issue with the copy constructor of MEMBLOCK.
Blog — Facebook
Gammastrahler
Gammastrahler
Here is the complete code

Little explanation: The _blockList vector is separated from the actual memory block, as opposed to common implementations 

struct MEMBLOCK{	size_t	size : 31;	bool	used : 1;};class ALLOCATOR{	size_t			_chunkSize;	char*			_chunk;	std::vector<MEMBLOCK>	_blockList;	size_t			_freeMem;	public:    ALLOCATOR(const size_t chunkSize) : _chunkSize(chunkSize)     {        MEMBLOCK block;        block.size = chunkSize;        block.used = false;        _chunk = new char(chunkSize);        _blockList.push_back(block);        _freeMem = chunkSize;    }    void* allocate(const size_t bytes)    {        if (_chunkSize < bytes || bytes == 0)            return NULL;        MEMBLOCK *freeBlock = NULL;        size_t addr = 0;        for (std::vector<MEMBLOCK>::iterator pBlock = _blockList.begin();            pBlock != _blockList.end(); ++pBlock)        {  	    if (pBlock->size >= bytes && !pBlock->used)	    {	        freeBlock = &(*pBlock);	        break;            }	    else	        addr += pBlock->size;        }        if (!freeBlock)            return NULL;        freeBlock->used = true;	if (bytes < freeBlock->size)	{	    MEMBLOCK newBlock;	    newBlock.size = freeBlock->size - bytes;	    newBlock.used = false;				    freeBlock->size = bytes;	    _blockList.push_back(newBlock);	    _freeMem -= bytes;	}	else	{	    freeBlock->size = bytes;	    _freeMem -= bytes;	}		        return (_chunk + addr);    }}ALLOCATOR mem(1024);char* my_new_string(const char* str){    char* pDest =(char*)mem.allocate(strlen(str) + 1);    strcpy(pDest, str);    return pDest;}void main(){    char* s1, *s2, *s3;    std::cout << (s1 = my_new_string("HelloWorld!")) << std::endl;    std::cout << (s2 = my_new_string("I´m going to bed now")) << std::endl; // When the third string is created, this causes push_back to crash in my allocator function    std::cout << (s3 = my_new_string("Good morning, Mrs. Meyers")) << std::endl;}
Palidine
Palidine
read my post again. This is your problem:

newBlock.size = freeBlock->size - bytes;

should be

newBlock.size = bytes;

-me
Palidine
Palidine
another big problem you have:

you set _chunk equal to some new'd memory which you then push back to the vector. Later when you're allocating your return an offset of _chunk to the user.

That makes no sense. You're almost guaranteed to return invalid memory. because sucessive elements in the vector have absolutely no predictable locational relationship with the address stored in _chunk.

Essentially let's say you allocate _chunk at 0x00000000. Later you'll push stuff to the back of the vector, that stuff get's copied into the vector's array deal. The address of the memory in the vector's contiguous memory block is unrelated to the location of the address stored in _chunk because the data in chunk was itself copied into the vector.

if you want to be returning offsets, you want to return offsets from the front of the vector..... however that's also bad because every time a vector grows beyond it's current bounds, it copies all of itself somewhere else in memory which would then invalidate any memory addresses you've previously given out to anyone.

Basically, your architecture just won't work (unless i've just missed some important details).

The typical architecture of a memory manager uses handles so that the memory you give out can be manipulated at will by the manager without invalidating memory that other people are holding.

-me
Gammastrahler
Gammastrahler
@Palidine

Thanks for your help. But i think my code is a little bit confusing due to the fact, that the variable named "freeBlock" is somewhat misleading.

freeBlock is the "first fit" block that is greater than or equal to the bytes the user aquired, and freeblock is then marked as used, so it is no longer a freeblock but actual the block that is related to the allocated memory.

And then, newBlock is created to store information of the remaining free bytes

Lets say, i have a single free block of 100 byte,
and the user aks me for 80 bytes,
then i set this block´s size to 80 bytes, and create a new (free block) with 20 bytes in size.
Palidine
Palidine
no. you're storing that offset in the array thusly:

10 total bytes

allocate 1 byte
push_back a struct with a .size = 9

allocate 1 byte
push_back a struct with a .size = 8

allocate another byte
iterate the list

addr += 9
addr += 8

return _chunk + 17;

note that the addr offset is horribly wrong
note that _chunk + 17 is no where in your vector of memory because the pointer stored in _chunk has no relationship with the memory space of the vector

-me
Enigma
Enigma
_chunk = new char(chunkSize); allocates a single byte from the freestore and stores the value of chunkSize, converted to type char, in that byte. I suspect you wanted _chunk = operator new(chunkSize);

Σnigma
Gammastrahler
Gammastrahler
Quote:
Original post by Palidine
no. you're storing that offset in the array thusly:

10 total bytes

allocate 1 byte
push_back a struct with a .size = 9

allocate 1 byte
push_back a struct with a .size = 8

allocate another byte
iterate the list

addr += 9
addr += 8

return _chunk + 17;

note that the addr offset is horribly wrong
note that _chunk + 17 is no where in your vector of memory because the pointer stored in _chunk has no relationship with the memory space of the vector

-me


I´m just using the vector for holding information about the size of the block, they have no relationship to the memory addressed by _chunk, neither physically nor logically :)
the vector only keeps track of the number of blocks and the block sizes / as well as the status (used/unused)

The problem is fixed now, it was the error detected by Enigma. Now it works :)

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.