Are your bored ? Then take this little quiz and test your bug-spotting abilities !!
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 ;-)
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; ...
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.
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.
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.
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.
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 for posting an actual programming-related article. It's refreshing.
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; }
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.
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...
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 :-)
My paranoia sanity check ended up biting me in the ass. :-)
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.
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.
struct Mydata { typedef std::pair<Foo, Bar> entry; std::vector<entry> content;
void add (Foo foo, Bar bar) { content.push_back (entry (foo, bar)); } };
struct Mydata { typedef std::pair<Foo, Bar> entry; std::vector<entry> content;void add (Foo foo, Bar bar) { content.push_back (entry (foo, bar)); } };
... 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 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!