unsigned char variable is not incremented

Question

I came across one strange behaviour. In my code one variable is decremented, but not incremented and as a result my algorithm does not work. The variable name is blocksAvailable, it is defined in Chunk class, initiated with Chunk::init method, decremented with Chunk::allocate method and must be incremented with Chunk::deallocate method. So, there are just two places where this variable is mentioned - allocate and deallocate methods. In one place it gets decremented (and it works) and in other place it gets incremented and it does not work. This is the completely minimized and reproducible code:

#include <cstddef>
#include <iostream>
#include <vector>

using uchar = unsigned char;

class Chunk 
{
private:    

    friend class FixedAllocator;

    void init(size_t blockSize, uchar blocks);

    void release();

    void* allocate(size_t blockSize);

    void deallocate(void* p, size_t blockSize);

    inline bool hasBlock(void* p, size_t chunkLen) const
    {
        uchar * pc = static_cast<uchar*>(p);
        return (pData <= pc) && (pc <= (pData + chunkLen));
    }

    inline bool releasable(uchar numBlocks) const
    {
          return blocksAvailable == numBlocks;    
    }

    uchar* pData;

    uchar firstAvailableBlock, blocksAvailable;    
};

void Chunk::init(size_t blockSize, uchar blocks)
{
     // for n of Ts it will allocate n * sizeof(T) memory
    pData = new uchar[blockSize * blocks];
    firstAvailableBlock = 0;
    blocksAvailable = blocks;
    uchar i = 0;
    uchar* p = pData;
    // used by allocate method to move forward firstAvailableBlock 
    for (; i != blocks; p += blockSize) 
    {
          *p = ++i;
    }
}

void Chunk::release()
{
    ::operator delete(pData);
}

void* Chunk::allocate(size_t blockSize)
{
     if (!blocksAvailable) return 0;
     // move firstAvailableBlock one block ahead
    uchar* pResult = pData + firstAvailableBlock * blockSize;
    firstAvailableBlock = *pResult;
    --blocksAvailable;
    std::cout << "blocksAvailable after allocate " << blocksAvailable << std::endl;
    return pResult;
}

void Chunk::deallocate(void* p, size_t blockSize)
{
    uchar* toRelease = static_cast<uchar*>(p);
    // find last but one available block
    firstAvailableBlock = static_cast<uchar>((toRelease - pData) / blockSize);
    ++blocksAvailable;
    std::cout << "blocksAvailable after deallocate " << blocksAvailable << std::endl;
}

class FixedAllocator 
{
private:
    size_t blockSize;
    uchar blocks;
    using Chunks = std::vector<Chunk>;
    Chunks chunks;
    Chunk* allocChunk;
public:
    FixedAllocator();
    ~FixedAllocator();
    void init(size_t blockSize, size_t pageSize);
    const int blockOwner(void* p) const;
    void * allocate();
    void deallocate(void* p);
};

FixedAllocator::FixedAllocator()
    :blockSize(0),
    blocks(0),
    chunks(0),
    allocChunk(nullptr)
{
}

FixedAllocator::~FixedAllocator()
{
    Chunks::iterator it;
    for (it = chunks.begin(); it != chunks.end(); ++it)
    {
        it->release();    
    }
}

void FixedAllocator::init(size_t blockSize_, size_t pageSize)
{
     blockSize = blockSize_;
    size_t numBlocks = pageSize / blockSize;
    blocks = static_cast<uchar>(numBlocks);
}

const int FixedAllocator::blockOwner(void* p) const
{
    size_t chunkLen = blocks * blockSize;
    std::vector<int>::size_type i = 0, sz = chunks.size();
    for (; i < sz; i++)
    {
          if (chunks[i].hasBlock(p, chunkLen))
        {
               return i;        
        }    
    }
    return -1;
}

void* FixedAllocator::allocate()
{
     if (!allocChunk || allocChunk->blocksAvailable == 0)
    {
        Chunks::iterator i = chunks.begin();    
        for (;;++i)
        {
            if (i == chunks.end())
            {
                 // allocate memory for one more chunk
                chunks.reserve(chunks.size() + 1);
                Chunk newChunk;  
                newChunk.init(blockSize, blocks);
                // add new chunk to memory pool
                chunks.push_back(newChunk);                
                // points to new just initiated chunk
                allocChunk = &chunks.back();
                break;
            }
            if (i->blocksAvailable > 0)
            {
                 // points to chunk with available blocks
                allocChunk = &*i;
                break;            
            }                   
        }
    }
    return allocChunk->allocate(blockSize);
}

void FixedAllocator::deallocate(void* p)
{
    // TODO. Optimize. Now very bruteforce and non-efficient
    const int chunkPos = blockOwner(p); 
    if (chunkPos != -1) 
    {
           Chunk chunk = chunks[chunkPos];
           chunk.deallocate(p, blockSize);         
         // if chunk is releasable, release memory 
         if (chunk.releasable(blocks))
         {
             chunk.release();
             chunks.erase(chunks.begin() + chunkPos);
             // allocChunk may point to deleted chunk
             // so, reset it                      
             allocChunk = &chunks.back();
         } else {
             // there are free blocks in chunk
             // so, reset allocChunk for faster future allocation
             allocChunk = &chunk;    
         }         
    }    
}

int main() {
     FixedAllocator* alloc = new FixedAllocator();
     alloc->init(4, 12);
     void* p = alloc->allocate();
     void* q = alloc->allocate();
     void* r = alloc->allocate();
     alloc->deallocate(p);
     alloc->deallocate(q);
     alloc->deallocate(r);   
     return 0;
}

As you can see, I have two debug statements in my code. One which prints blocksAvailable value after increment and one which prints its value after decrement.

But this is what I have on my screen, when I compile and run my code:

As you can see, blocksAvailable is initiated with value 3, then it gets decremented three times (three calls to allocate method), but after each decrement (call to deallocate) its value stays the same - 1. It really drives me crazy and looks like some ghost in my code. You can easily reproduce it, compile and run as simply as:

$ g++ main.cpp
$ ./a.out

I hope, someone can help me to find where this ghost appeared from.

This code doesn't seem minimal code which is reproducing the issue. Please try to reduce the code as much as possible. — Mayank Jain
– Mayank Jain, Commented Jan 4, 2018 at 12:59
And when you used your debugger to step through your code, one line at a time, what observations did you make about the values of the variable, and whether or not it was modified as expected? — Sam Varshavchik
– Sam Varshavchik, Commented Jan 4, 2018 at 13:01
I minimized it as much as possible. If I have one trivial class with two methods, where one method increments and another method decrements, then it works, because it must work. But I do not know why in the context of my code, it does not work. — Jacobian
– Jacobian, Commented Jan 4, 2018 at 13:02
I made some observations. On the screen shot you can see, that blocksAvailable is correctly decremented (there is no problem with this allocate method), but it is corretly decremented only for the first time. Subsequent operations do not effect this variable for some reason. — Jacobian
– Jacobian, Commented Jan 4, 2018 at 13:05
Put breakpoint at first statement printing "after deallocate". After your debugger stops on it, put data (write) breakpoint on blocksAvailable, unpause, and see what happens. — HolyBlackCat
– HolyBlackCat, Commented Jan 4, 2018 at 13:06

melpomene · Accepted Answer · 2018-01-04 13:27:36Z

2

Here is the only place in your code where you call Chunk::deallocate:

       Chunk chunk = chunks[chunkPos];
       chunk.deallocate(p, blockSize);

The first line makes a copy of your Chunk; the second line calls deallocate on it, which increments chunk.blocksAvailable. But chunk is just a copy of the data. Modifying it has no lasting effect.

In particular, chunks[chunkPos] is unaffected and still contains blocksAvailable = 0.

answered Jan 4, 2018 at 13:27

melpomene

86.2k8 gold badges96 silver badges155 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

unsigned char variable is not incremented

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related