Tiny Quiz #1: Spot the bug !

Posted 7 Apr 2006 at 00:35 UTC by freetype Share This

Are your bored ? Then take this little quiz and test your bug-spotting abilities !!

Scanning through the sources of a couple well-known open-source libraries, I found several occurences of the same kind of code that tickled me. Let's say you want to store two parallel arrays in a custom data structure, as in:

   typedef struct {
       int    count;   // number of items in each array
       Foo*   foos;    // array of Foos
       Bar*   bars;    // array of Bars
   } MyData;

Now, here's the function used to add a (foo,bar) pair to the data structure:

  static int
  mydata_add( MyData  *data,  Foo  foo, Bar  bar )
  {
      Foo*  new_foos;
      Bar*  new_bars;
      int   count = data->count;

if ( count == 0 ) new_foos = malloc( sizeof(Foo) ); else new_foos = realloc( data->foos, sizeof(Foo)*(count+1) ); if ( new_foos == NULL ) return -1; if ( count == 0 ) new_bars = malloc( sizeof(Bar) ); else new_bars = realloc( data->bars, sizeof(Bar)*(count+1) ); if ( new_bars == NULL ) return -1; new_foos[count] = foo; new_bars[count] = bar; data->foos = new_foos; data->bars = new_bars; data->count = count+1; return 0; }

Let's ignore the fact that incrementing by 1 is probably the worse way to grow dynamic arrays, or that 'count' could overflow; and consider that the code is in C (not C++ !!) and must run in a long-running process like an X Server. The quiz is the following:

  • list all memory-related bugs in the "mydata_add" function. this means any potential memory leak or dangling pointer creation. (hint: there are 4 of them !!)

  • propose a new implementation that fixes all issues

  • is your solution scalable ? I.e. would it be simple to implement if there were 16 parallel arrays, instead of 2 ? If not, propose a scalable one.

I know, I know, it's not too difficult, but I just want to highlight that careful memory management isn't always that simple ! And it's a good way to fill my current insomnia ;-)


Omg !, posted 7 Apr 2006 at 10:35 UTC by freetype » (Master)

Hummm, I really need more sleep: there are only 2 issues in the code above, not 4. Anyway, the exercise still remains. As a bonus, can you spot the bug in this alternate version:

    ...
    if ( count == 0 )
        new_foos = malloc( sizeof(Foo) );
    else
        new_foos = realloc( data->foos, (count+1)*sizeof(Foo) );
    if (new_foos == NULL)
        return -1;
    data->foos = new_foos;
    if ( count == 0 )
        new_bars = malloc( sizeof(Bar) );
    else
        new_bars = realloc( data->bars, (count+1)*sizeof(Foo) );
    if (new_bars == NULL)
        return -1;
    ...

realloc, posted 7 Apr 2006 at 11:23 UTC by djm » (Master)

Let's ignore the fact that incrementing by 1 is probably the worse way to grow dynamic arrays

A half-decent realloc implementation will handle this correctly, e.g. by sizing to the next power of two up from the requested allocation.

realloc, posted 7 Apr 2006 at 11:36 UTC by freetype » (Master)

A half-decent realloc implementation will handle this correctly, e.g. by sizing to the next power of two up from the requested allocation

This is very dependent on the memory manager implementation, and is only generally true until a certain size is reached. I.e. If your arrays become bigger than, say, 512 bytes, you end up performing the whole, slow, best-fit/first-fit/wathever search on each realloc call, with the potential to fragment your memory a lot.

Attempt #1, posted 7 Apr 2006 at 16:56 UTC by cdfrey » (Journeyer)

Here's one attempt at reimplementing the function.

static int
mydata_add( MyData  *data,  Foo  foo, Bar  bar )
{
        Foo*  new_foos;
        Bar*  new_bars;
        int   count = data->count;

/* this assumes the corresponding mydata_del() will free these arrays when they get to 0, and that mydata_init() will set count to 0 */ if ( count == 0 ) { data->foos = NULL; data->bars = NULL; }

new_foos = realloc(data->foos, sizeof(Foo) * (count+1));

if( new_foos == NULL ) return -1; data->foos = new_foos;

new_bars = realloc(data->bars, sizeof(Bar) * (count+1)); if( new_bars == NULL ) return -1; data->bars = new_bars;

data->foos[count] = foo; data->bars[count] = bar; data->count++; return 0; }

I can't think of a way to make this scalable unless I start losing type information, or unless I change the struct.

Also, you can't really optimize the "count+1" step without changing the struct either, to keep track of the real size of the array.

Answer to attempt #1, posted 7 Apr 2006 at 20:28 UTC by freetype » (Master)

Dear cdfrey,

Congratulations, you're on the right path !! However, your code still exhibits a potential memory leak under very specific conditions.

Can you find it ? How would you fix this, being allowed to code mydata_init as well.

Apart from that, you're right that optimizing the 'count+1' does requires a new field in the structure, but that's not what I want to highlight here.

When the second allocation fails, posted 7 Apr 2006 at 22:07 UTC by slamb » (Journeyer)

If the newfoos (malloc|realloc) succeeds but the newbars one fails, newfoos will be leaked. Worse, for count != 0, data->foos will be left as a dangling pointer; future operations will corrupt memory.

Also, stylistically, the "if (...) malloc(...) else realloc(...)" annoys me. I find unnecessary special cases confusing and error-prone. The malloc(sizeof(foo)) is equivalent to realloc(NULL, (count+1)*sizeof(foo)). cdfrey's code takes advantage of this, so it's much better.

Easiest fix: use C++ and scoped pointers. But in a pure-C project, you'll have to have an array of your current new pointers and loop over the previous ones in the cleanup case.

Seems like a lot of people get realloc's error case wrong. I sometimes see this:

    ptr = realloc(ptr, n);

...which is always wrong. If ptr is NULL afterward, you've just clobbered your pointer to (leaked) the old allocation. Unless you're about to abort(), you need to free that.

Thanks, posted 7 Apr 2006 at 22:09 UTC by slamb » (Journeyer)

Thanks for posting an actual programming-related article. It's refreshing.

remaining memory leak?, posted 7 Apr 2006 at 23:11 UTC by cdfrey » (Journeyer)

I don't see a memory leak in my version. You'll have to enlighten me :-)

According to the manpage, realloc doesn't change the original memory on failure, so if the first realloc succeeds, and the second one fails, the only problem is that the first array has space for one extra Foo item. The count is not updated, so there is no consistency issue. The next time mydata_add() is called, that extra item will be needed anyway, so I figured it was safe.

My mydata_init() would be pretty simple:

void mydata_init( MyData *data )
{
    data->count = 0;
    data->foos = NULL;
    data->bars = NULL;
}

Interesting, posted 7 Apr 2006 at 23:34 UTC by nymia » (Master)

  1. I'd use a different data structure, say singly-linked or doubly-linked having count along with head and tail pointers declared in the parent node.
  2. Arrays are cool for cross-ref'ing, though I'm not sure if they work well with a bignum. Most arrays I used were hardcoded data decls that never got updated.
This is definitely new to me. Interesting to see more comments.

Bug, posted 7 Apr 2006 at 23:37 UTC by nymia » (Master)

Saw one bug.

Fault is when new_foos returns not null and the new_bars return null, count is not synched and will cause undefined behavior.

remaining memory leak, posted 8 Apr 2006 at 00:11 UTC by freetype » (Master)

cdfrey, consider that your mydata_add is called twice, and that on the first call, the second realloc fails. As you stated, a block was allocated in data->foos. Now, on the second call, both arrays are set to NULL because count is still 0, this means that you just leaked the previously allocated block !

By the way, this is equivalent to the bug in the second version of the code I provided.

Of course, the right fix is to have mydata_init performing all inits to 0 and NULL, and using the simpler code:

  new_foos = realloc( data->foos, (count+1)*sizeof(Foo) );
  if ( new_foos == NULL )
      return -1;
  data->foos = new_foos;

new_bars = realloc( data->bars, (count+1)*sizeof(Bar) ); if ( new_bars == NULL ) return -1; data->bars = new_bars;

Now, a few remarks to clarify all this:

  • the original code uses count to determine wether to use alloc or realloc, that's because it didn't care to initialize all array pointers to NULL properly: if data->foos is undefined when count is 0, you can't use the realloc() simplification.

    I could have mentionned that, but I didn't want to give too many hints for something so simple :-)

  • Alas, the real issue is that, because of potential partial failures, the count field cannot be used as an reliable indicator for the size of all arrays. The only thing you can say is that it's the minimum number of items in each one of them.

    Moreover, if you didn't properly initialized your array pointers, you cant' distinguish between an undefined or partially allocated array when count is 0.

  • As a conclusion, always initialize your array pointers to NULL before using them, and use realloc smartly. this will make your code simpler and safer in the case of partial failures.

It's a bit sad to see the 'if (...) malloc() else realloc()' scheme being used so much by developers. Most of them don't realize the potential for abuse. I guess it comes from the fact that this was required with pre-ANSI C compilers, and that the specifications detailing the realloc behaviour precisely were not freely available until recently.

And I agree with slamb that this is nothing compared to the gross mistake that 'ptr = realloc( ptr, new_size )' is. Sadly, all too common as well...

answers, posted 8 Apr 2006 at 00:21 UTC by freetype » (Master)

I forget to answer the original question, i.e. list all issues of the original code:

well, as you now know, it all boils down to what happens when the second allocation fails.

  • if count was 0, we leak a newly allocated block of memory. Bad, but not too dangerous.

  • however, if count was > 0, then we have reallocated the block pointed by data->foos, without updating the corresponding pointer. If the block was moved by the allocater, we just create a dangling pointer, which may create chaos when the array is later used to access items.

the second version of the code fixes the two issues described above. However, it introduces another potential memory leak, which happens when the function is later called (only triggered when count is 0, and the first allocation then succeed).

isn't it funny to see how tricky something so simple can be to implement correctly ?

Thanks for your time, hope you enjoyed it as much as I did. I encourage you to post other "Mini Quiz" and little fun programming challenges articles on Advogato. After all, they're the spice of our craft :-)

Whoops, posted 8 Apr 2006 at 00:50 UTC by cdfrey » (Journeyer)

My paranoia sanity check ended up biting me in the ass. :-)

C++, posted 9 Apr 2006 at 23:32 UTC by Pseudonym » (Journeyer)

Easiest fix: use C++ and scoped pointers.

True enough. Look at do_pipe in fs/pipe.c in your Linux kernel sources, and just think how much easier it would be in C++. (Yes, yes, I know, there are good reasons why the Linux kernel is in C, not C++.)

For completeness, though, I should point out that if you're using C++, you'd better have a good reason not to be using built-in containers.

C++ really ?, posted 11 Apr 2006 at 08:42 UTC by freetype » (Master)

In some situations, using C++ is not a "fix", i.e. it creates more problems than it solves.

Oh, and it's pretty easy to achieve the same kind of bug with smart pointers. Just use the wrong one, and you'll never realize you're leaking memory on every release.

I'm really tired of C++ fanboys.

C++ fanboy answer, posted 13 Apr 2006 at 11:24 UTC by abraham » (Master)

struct Mydata { typedef std::pair<Foo, Bar> entry; std::vector<entry> content;

void add (Foo foo, Bar bar) { content.push_back (entry (foo, bar)); } };

C++ fanboy answer (now formatted!), posted 13 Apr 2006 at 11:27 UTC by abraham » (Master)

struct Mydata
{
  typedef std::pair<Foo, Bar> entry;
  std::vector<entry> content;

void add (Foo foo, Bar bar) { content.push_back (entry (foo, bar)); } };

hierarchical allocation, posted 16 Apr 2006 at 02:03 UTC by nconway » (Master)

... makes memory allocation in C a lot less painful and error-prone, especially for daemons and similarly long-running programs. See talloc, for example.

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!

X
Share this page