glibc detected *** free(): invalid pointer

Question

I have the following problem with this segment of code. Can some one please help?

Note: QueueItem is being created on a different thread.

WorkItem * Dequeue(Queue ** Q)    
{    
    if(QueueIsEmpty(*Q)) return NULL;

    QueueItem * tmp = (*Q)->Head;
    (*Q)->Head = ((*Q)->Head)->NextItem;
    WorkItem * retval = tmp->workItem;
    free(tmp); //Generates  glibc detected *** free(): invalid pointer
    return retval;
}

edit This function is protected on access when multiple threads are running.

WorkItem * DequeueSynchronous(Queue ** Q)
{
    WorkItem * retval;
    pthread_mutex_lock((*Q)->QueMutex);
    retval = Dequeue (Q);
    pthread_mutex_unlock((*Q)->QueMutex);
    return retval;
}

(*Q)->Head; is allocated my malloc.

Queue * Queue_Init(pthread_mutex_t * mutex)
{
    Queue * retval = (Queue *)malloc(sizeof(Queue *));
    retval->Head = retval->Tail =NULL;
    retval->QueMutex = mutex;
    return retval;
}

void Enqueue (Queue * Q, WorkItem * WI)
{

   if(!Q)return;
   QueueItem * QI = (QueueItem *) malloc(sizeof(QueueItem *));
   QI->workItem = WI;
   QI->NextItem = NULL;

   if(QueueIsEmpty(Q))
   {
       Q->Head = Q->Tail = QI;
       return;
   }

   Q->Tail->NextItem = QI;
   Q->Tail = QI;
}

void EnqueueSynchronous (Queue * Q, WorkItem * WI)
{

   pthread_mutex_lock(Q->QueMutex);
   Enqueue (Q, WI);
   pthread_mutex_unlock(Q->QueMutex);
}

Also thanks for the input, I will look at valgrind.

EDIT 2

typedef struct {
    char ** FileNames;
    int  ** Results;
    int NumOfItems;
}WorkItem;

typedef struct QI{
    WorkItem * workItem;
    struct QI * NextItem;
}QueueItem;

typedef struct {
    QueueItem * Head, * Tail;
    pthread_mutex_t * QueMutex;
}Queue;

Dequeue is called -Dequeue(&WorkQue) All threads that call Dequeue were given &WorkQue as part of their args;

typedef struct{
    int ThreadID;
    WorkItem * workItem;
    char ** keywordsArray;
    int nKeywords;
    Queue ** WorkQueue, ** WorkCompletedQ;   
}ThreadArgs;

 pthread_t threads[NTHREADS];
ThreadArgs threadArgs[NTHREADS];

for(i=0;i<NTHREADS;i++)
{
    threadArgs[i].ThreadID=i;
    threadArgs[i].workItem = Dequeue(&WorkQue);
    threadArgs[i].WorkQueue = &WorkQue;
    threadArgs[i].WorkCompletedQ = &WorkCompletedQ;
    threadArgs[i].nKeywords=_kwlist->length;
    threadArgs[i].keywordsArray = ListToArray(*_kwlist);
}    

for(i=0;i<NTHREADS;i++)
{
    pthread_create(&threads[i], NULL, WorkerThread,(void *)&(threadArgs[i]));
}

each thread calls dequeue using myWork = DequeueSynchronous(myThreadArgs->WorkQueue);

Answer 1

Looking at your updated code, I think you're having memory corruption due to these lines:

Queue * retval = (Queue *)malloc(sizeof(Queue *));

Note that you're only allocating enough for a pointer to a Queue there - you should instead write:

Queue * retval = (Queue *)malloc(sizeof(Queue)); // version one

Or better:

Queue * retval = (Queue *)malloc(sizeof(*retval)); // version two

The second version is better, because it's robust to changes in the type of retval.

Both of these lines say "allocate enough space for a Queue, and set the queue pointer retval to point to it". Your previous line said "allocate enough space for a Queue pointer, and set the queue pointer retval to point to it". The old version caused an under allocation (since the structure was almost certainly larger than a pointer).

Then, when you assign to parts of the Queue structure that are past the space you've actually allocated, you stamp some other part of memory. I suspect that this causes you to stamp some of malloc()s internal control data, which is what causes the invalid free later on. You will need to change all of your malloc() calls to malloc the size of the structure rather than the size of the pointer.

Note that you should also not cast the result of malloc. In my opinion, your final malloc() statements should look like this:

Queue * retval = malloc(sizeof(*retval));

If that doesn't fix it, can you edit your question to include:

1. The definition of the Queue structure
2. How you're calling DequeueSynchronous (or, where the *Q becomes **Q)

---

Unrelatedly, note that you also have a bug where you don't clear the tail when the list becomes empty after a dequeue. I suspect you may need to write:

(*Q)->Head = ((*Q)->Head)->NextItem;
if ((*Q)->Head == NULL) (*Q)->Tail = NULL;

This will clear the tail if there's now no head in the queue.

Answer 2

There's nothing intrinsically wrong with this, as far as we can see. But the problem must be that tmp (in other words, (*Q)->Head on entry to the function) isn't a pointer to a block allocated by malloc(). If it was allocated in any other way -- or if it's a pointer into the middle of a block rather than the start -- then you can't free it with free().

It's also possible that it's been freed already; perhaps your multiple threads are causing it to be freed more than once.