C error - free(): invalid next size (fast)

I am not sure why I am getting the below error. Strangely enough, this error doesn't occur when I use Mac OS X, but it does when I use my Linux (Debian) partition.

-----------
Empty Queue: 0 0 0 0 0 0 0 0 0 0 

---------------
Populated Queue: 5 3 1 7 6 3 2 1 4 4 

-------------
After Dequeue: 3 1 7 6 3 2 1 4 4 0 
    Datum: 5

*** glibc detected *** ./queue_demo: free(): invalid next size (fast): 0x0000000000c73010 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x75b76)[0x7fde5c98db76]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x6c)[0x7fde5c9928ac]
./queue_demo[0x40098d]
./queue_demo[0x4008d8]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xfd)[0x7fde5c936ead]
./queue_demo[0x4006d9]
======= Memory map: ========
00400000-00401000 r-xp 00000000 08:01 940937                             /home/dylan/Desktop/CST352_Gleason_Lab2/solution_1/queue_demo
00601000-00602000 rw-p 00001000 08:01 940937                             /home/dylan/Desktop/CST352_Gleason_Lab2/solution_1/queue_demo
00c73000-00c94000 rw-p 00000000 00:00 0                                  [heap]
7fde58000000-7fde58021000 rw-p 00000000 00:00 0 
7fde58021000-7fde5c000000 ---p 00000000 00:00 0 
7fde5c702000-7fde5c717000 r-xp 00000000 08:01 1079347                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fde5c717000-7fde5c917000 ---p 00015000 08:01 1079347                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fde5c917000-7fde5c918000 rw-p 00015000 08:01 1079347                    /lib/x86_64-linux-gnu/libgcc_s.so.1
7fde5c918000-7fde5ca95000 r-xp 00000000 08:01 1079316                    /lib/x86_64-linux-gnu/libc-2.13.so
7fde5ca95000-7fde5cc95000 ---p 0017d000 08:01 1079316                    /lib/x86_64-linux-gnu/libc-2.13.so
7fde5cc95000-7fde5cc99000 r--p 0017d000 08:01 1079316                    /lib/x86_64-linux-gnu/libc-2.13.so
7fde5cc99000-7fde5cc9a000 rw-p 00181000 08:01 1079316                    /lib/x86_64-linux-gnu/libc-2.13.so
7fde5cc9a000-7fde5cc9f000 rw-p 00000000 00:00 0 
7fde5cc9f000-7fde5ccbf000 r-xp 00000000 08:01 1079447                    /lib/x86_64-linux-gnu/ld-2.13.so
7fde5cea3000-7fde5cea6000 rw-p 00000000 00:00 0 
7fde5cebb000-7fde5cebe000 rw-p 00000000 00:00 0 
7fde5cebe000-7fde5cebf000 r--p 0001f000 08:01 1079447                    /lib/x86_64-linux-gnu/ld-2.13.so
7fde5cebf000-7fde5cec0000 rw-p 00020000 08:01 1079447                    /lib/x86_64-linux-gnu/ld-2.13.so
7fde5cec0000-7fde5cec1000 rw-p 00000000 00:00 0 
7fff13797000-7fff137b8000 rw-p 00000000 00:00 0                          [stack]
7fff137ff000-7fff13800000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted

This error happens when I call the destruct function in my Queue structure, in a test program written below.

#include <time.h>
#include <stdio.h>
#include "Queue.h"

int main(int argc, char* argv[])
{
   // create a "queue" data structure
   Queue_t* my_queue = construct(10);

   // generate a random seed
   srand( (unsigned)time(NULL) );

   // display the empty queue
   printf("-----------\n");
   printf("Empty Queue: ");
   display(my_queue);
   printf("\n");

   // populate the queue with random numbers
   int i = 0;

   for(; i < my_queue->maximum_count; ++i)
      enqueue(my_queue, rand() % 10);

   printf("---------------\n");
   printf("Populated Queue: ");
   display(my_queue);
   printf("\n");

   // dequeue, print the current queue and the datum
   int datum = dequeue(my_queue);

   printf("-------------\n");
   printf("After Dequeue: ");
   display(my_queue);
   printf("\tDatum: %d\n\n", datum);

   // clean up memory
   destruct(my_queue);

   return 0;
}

Here is my data structure:

#ifndef QUEUE_H
#define QUEUE_H

typedef struct Queue
{
   int  current_count;
   int  maximum_count;
   int  buffer[];       // queue uses an array
} Queue_t;


// routines to implement Queue-like functionality (FIFO)
// TODO: somehow encapsulate all these features in the struct itself.
//
Queue_t* construct(int buff_size);
void     destruct (Queue_t* queue);
void     display  (Queue_t* queue);
int      dequeue  (Queue_t* queue);
void     enqueue  (Queue_t* queue, const int datum);

#endif

Implementation:

#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "Queue.h"

Queue_t* construct(int buff_size)
{
   Queue_t* queue = malloc(
      sizeof(Queue_t) + sizeof(int) * sizeof(Queue_t));

   assert(queue != NULL);
   queue->maximum_count = buff_size;
   queue->current_count = 0;
   memset(queue->buffer, 0, sizeof(int)*buff_size);

   return queue;
}

void destruct(Queue_t* queue)
{
   assert(queue != NULL);
   free(queue);  // error at this statement
   printf("Queue destroyed!\n");
}

void display(Queue_t* queue)
{
   int i = 0;

   for(; i < queue->maximum_count; ++i)
      printf("%d ", queue->buffer[i]);
   printf("\n");
}

void enqueue(Queue_t* queue, const int datum)
{
   assert(queue->current_count < queue->maximum_count);
   queue->buffer[queue->current_count] = datum;
   ++queue->current_count;
}


int dequeue(Queue_t* queue)
{
   int i = 1;
   int datum = queue->buffer[0];

   assert(queue->current_count > 0);

   for(; i < queue->maximum_count; ++i)
   {
      queue->buffer[i-1] = queue->buffer[i];
      queue->buffer[i] = 0;
   }

   --queue->current_count;

   return datum;
}

回答1:

This looks like you have corrupted some data used by libc memory allocation functions. In your construct function shouldn't we change

Queue_t* queue = malloc(
      sizeof(Queue_t) + sizeof(int) * sizeof(Queue_t));

Queue_t* queue = malloc(
          sizeof(Queue_t) + sizeof(int) * buff_size);

The following line in construct seems to cause the corruption now due to incorrect amount of memory being allocated for queue.

 memset(queue->buffer, 0, sizeof(int)*buff_size);

When you apply the sizeof operator to a structure with a flexible array member, only fields other than the flexible array comprise the total structure size i.e. its size is 0. When you are allocating memory for such structures, you need to specify explicitly how many extra bytes you want at the end of the structure.

回答2:

These two lines should match:

Queue_t* queue = malloc(sizeof(Queue_t) + sizeof(int) * buff_size);
memset(queue->buffer, 0, sizeof(int)*buff_size);

The original code would allocate 8+4*8 = 40 bytes, while the memset would clear 8+4*10 = 48 bytes. This doesn't necessarily show as memory corruption, as eg. 64-bit gnu malloc will align the memory blocks to 16-byte boundaries, so it would actually allocate also the missing 8 bytes.

Other malloc implementations can and will allocate even more and just put some bookkeeping data (just before each allocated unit - perhaps linked list or pointer to parent block in some tree-like structure). Overwriting this bookkeeping will then show up as 'corrupted list' when freeing.

回答3:

You haven't defined size of your array in

typedef struct Queue
{
   int  current_count;
   int  maximum_count;
   int  buffer[];       // queue uses an array
} Queue_t;

This is a defined behavior only for C99. For prior compilers if you want the buffer to mark the start of your real buffer, declare it as int buffer[1]; and allocate a larger buffer.

In addition, it seems that your allocation is incorrect:

Queue_t* queue = malloc(
    sizeof(Queue_t) + sizeof(int) * sizeof(Queue_t));

What exactly are you allocating here? It probably should be
Queue_t* queue = malloc(sizeof(Queue_t) + sizeof(int) * buf_size);