Quantcast

RE: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

njn (Bugzilla)-2
On Thu, 19 May 2005, Mark Stemm wrote:

> That version behaves properly, but this modification (walking each
> buffer after it's been allocated) does not:
>
> #include <stdlib.h>
> #include <string.h>
>
> int main(int argc, char **argv)
> {
>    int len = 0;
>    char *data = NULL;
>    int do_copy = 1;
>    for(int i=0; i<2000; i++) {
>        len += 4096;
>        char *data = (char *) malloc(len*sizeof(char));
>        for (int j=0; j<len; j++) {
>            data[j] = j;
>        }
>        free(data);
>    }
>    return 0;
> }
>
> Some nonscientific analysis (i.e. watching "top" while valgrind is
> running) indicates that the memory usage is initially stable, then
> quickly climbs as the buffer gets larger.

I just looked at this.  Turns out that under Valgrind, on my machine (and
presumably yours) a lot of those allocations are failing -- you should be
checking the result of malloc.

I think the problem is this:  the program allocates a 4KB block, then
frees it.  Valgrind puts this block on its free list.  The program then
allocates an 8KB block.  There's no block on the free list which is 8KB or
greater, so Valgrind allocates new memory.  And so on.  So Valgrind's free
list ends up holding blocks of size 4KB, 8KB, 12KB, 16KB, etc.  Huge
amounts of memory quickly get heldon the free list, but none of the blocks
are ever big enough to satisfy the requests.

Basically it's a pathological case for Valgrind's allocator.  Mark, did
you come up with your original program (the realloc one) based on
behaviour you saw with a real application, or were you just experimenting?

N


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
http://ads.osdn.com/?ad_id=7412&alloc_id=16344&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

Mark Stemm
Thanks a lot for taking a look at the problem! I should indeed be
checking the result of malloc, I'll make sure to do so in my actual
program. In my case, my machine started swapping heavily before malloc()
started failing.

The actual program was reading 4kb blocks from a unix file descriptor
and appending the blocks to an in-memory buffer. After noticing problems
with that program under valgrind, I played around a bit to distill it
into the test program I sent.

I really should be re-allocating the buffer exponentially rather than
linearly, but haven't made that change yet. Once I do that, I shouldn't
have any problems as the total number of allocations will ~12 rather
than 2000.

Thanks again for the help.

  --Mark


-----Original Message-----
From: Nicholas Nethercote [mailto:[hidden email]]
Sent: Saturday, May 21, 2005 12:07 PM
To: Mark Stemm
Cc: [hidden email]
Subject: RE: [Valgrind-users] Problem with realloc() + valgrind 2.4.0
(incl. sample program)


On Thu, 19 May 2005, Mark Stemm wrote:

> That version behaves properly, but this modification (walking each
> buffer after it's been allocated) does not:
>
> #include <stdlib.h>
> #include <string.h>
>
> int main(int argc, char **argv)
> {
>    int len = 0;
>    char *data = NULL;
>    int do_copy = 1;
>    for(int i=0; i<2000; i++) {
>        len += 4096;
>        char *data = (char *) malloc(len*sizeof(char));
>        for (int j=0; j<len; j++) {
>            data[j] = j;
>        }
>        free(data);
>    }
>    return 0;
> }
>
> Some nonscientific analysis (i.e. watching "top" while valgrind is
> running) indicates that the memory usage is initially stable, then
> quickly climbs as the buffer gets larger.

I just looked at this.  Turns out that under Valgrind, on my machine
(and
presumably yours) a lot of those allocations are failing -- you should
be
checking the result of malloc.

I think the problem is this:  the program allocates a 4KB block, then
frees it.  Valgrind puts this block on its free list.  The program then
allocates an 8KB block.  There's no block on the free list which is 8KB
or
greater, so Valgrind allocates new memory.  And so on.  So Valgrind's
free
list ends up holding blocks of size 4KB, 8KB, 12KB, 16KB, etc.  Huge
amounts of memory quickly get heldon the free list, but none of the
blocks
are ever big enough to satisfy the requests.

Basically it's a pathological case for Valgrind's allocator.  Mark, did
you come up with your original program (the realloc one) based on
behaviour you saw with a real application, or were you just
experimenting?

N


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
<a href="http://ads.osdn.com/?ad_idt12&alloc_id344&op=click">http://ads.osdn.com/?ad_idt12&alloc_id344&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

Julian Seward-2

Nick wrote:

> I think the problem is this:  the program allocates a 4KB block, then
> frees it.  Valgrind puts this block on its free list.  The program then
> allocates an 8KB block.  There's no block on the free list which is 8KB
> or
> greater, so Valgrind allocates new memory.  And so on.  So Valgrind's
> free
> list ends up holding blocks of size 4KB, 8KB, 12KB, 16KB, etc.  Huge
> amounts of memory quickly get heldon the free list, [...]

When you say "free list", do you mean the place where mem/addrcheck
park freed stuff for a while so as to delay its re-entry into
circulation?

If yes, I'm not sure this analysis is right (or else V is buggy :-)
There is a limit to the amount of stuff allowed on the free list at
once; by default it is 1MB I think.  Certainly it shouldn't spiral
up into the hundreds of MB.  When a free would cause the volume to
go above the limit, the oldest stuff is pushed off the end of the
free list and potentially back into circulation.

J


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
http://ads.osdn.com/?ad_id=7412&alloc_id=16344&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

njn (Bugzilla)-2
On Mon, 23 May 2005, Julian Seward wrote:

>> I think the problem is this:  the program allocates a 4KB block, then
>> frees it.  Valgrind puts this block on its free list.  The program then
>> allocates an 8KB block.  There's no block on the free list which is 8KB
>> or greater, so Valgrind allocates new memory.  And so on.  So
>> Valgrind's free list ends up holding blocks of size 4KB, 8KB, 12KB,
>> 16KB, etc.  Huge amounts of memory quickly get heldon the free list,
>> [...]
>
> When you say "free list", do you mean the place where mem/addrcheck
> park freed stuff for a while so as to delay its re-entry into
> circulation?

No.  I mean the allocator's free list.

N


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
http://ads.osdn.com/?ad_id=7412&alloc_id=16344&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

Julian Seward-2

> On Monday 23 May 2005 20:54, Nicholas Nethercote wrote:
>
> > When you say "free list", do you mean the place where mem/addrcheck
> > park freed stuff for a while so as to delay its re-entry into
> > circulation?
>
> No.  I mean the allocator's free list.

Oh.  My mistake.  Sorry.  Then I agree with your analysis.

J


-------------------------------------------------------
This SF.Net email is sponsored by Oracle Space Sweepstakes
Want to be the first software developer in space?
Enter now for the Oracle Space Sweepstakes!
http://ads.osdn.com/?ad_id=7412&alloc_id=16344&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

njn (Bugzilla)-2
In reply to this post by njn (Bugzilla)-2
On Sat, 21 May 2005, Nicholas Nethercote wrote:

>> Some nonscientific analysis (i.e. watching "top" while valgrind is
>> running) indicates that the memory usage is initially stable, then
>> quickly climbs as the buffer gets larger.
>
> I just looked at this.  Turns out that under Valgrind, on my machine (and
> presumably yours) a lot of those allocations are failing -- you should be
> checking the result of malloc.
>
> I think the problem is this:  the program allocates a 4KB block, then frees
> it.  Valgrind puts this block on its free list.  The program then allocates
> an 8KB block.  There's no block on the free list which is 8KB or greater, so
> Valgrind allocates new memory.  And so on.  So Valgrind's free list ends up
> holding blocks of size 4KB, 8KB, 12KB, 16KB, etc.  Huge amounts of memory
> quickly get heldon the free list, but none of the blocks are ever big enough
> to satisfy the requests.
>
> Basically it's a pathological case for Valgrind's allocator.  Mark, did you
> come up with your original program (the realloc one) based on behaviour you
> saw with a real application, or were you just experimenting?

I should think more before opening my mouth -- the problem is more subtle
than I thought.  I was forgetting that Valgrind's allocator merges blocks
on the free list if they are adjacent.  So it's certainly possible to
allocate, for example, a 12KB block from the free list even if you've only
previously allocated (and freed) a 4KB block and an 8KB block, because
they may have been merged.

Here's the real problem.  Valgrind hands out heap blocks from
"superblocks".  Superblocks are 1MB in size, or, if you ask for a heap
block larger than that, the superblock provided is that size (plus space
for the administrative bytes).

Unfortunately, Valgrind's allocator can only merge blocks on the free list
if they are adjacent.  This means they must be in the same superblock.
But once your program starts asking for heap blocks bigger than 1MB, each
heap block fills a whole superblock, and so there is no merging going on
with free blocks larger than 1MB.  That's where all the address space
goes, and eventually the allocator starts failing.

The fix would be for Valgrind's allocator to monitor in some way the
superblocks it has allocated, and don't let too many stay hanging around
if they're not being used.  Eg. have a free list threshold, and if the
amount of memory on the free list exceeds that, then try to deallocate
superblocks when new ones get allocated.  Or something like that.  If
indeed it's worth bothering with at all -- this is a pretty pathological
case.

N


-------------------------------------------------------
SF.Net email is sponsored by: GoToMeeting - the easiest way to collaborate
online with coworkers and clients while avoiding the high cost of travel and
communications. There is no equipment to buy and you can meet as often as
you want. Try it free.http://ads.osdn.com/?ad_id=7402&alloc_id=16135&op=click
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

RE: Problem with realloc() + valgrind 2.4.0 (incl. sample program)

Patrick Ohly-2
On Wed, 2005-05-25 at 10:07 -0500, Nicholas Nethercote wrote:
> The fix would be for Valgrind's allocator to monitor in some way the
> superblocks it has allocated, and don't let too many stay hanging around
> if they're not being used.  Eg. have a free list threshold, and if the
> amount of memory on the free list exceeds that, then try to deallocate
> superblocks when new ones get allocated.  Or something like that.  If
> indeed it's worth bothering with at all -- this is a pretty pathological
> case.

For what it's worth, I also ran into such an out-of-memory situation
with a test program which uses realloc() to increase the size of an
array dynamically several times. Your analysis sounds right, in this
test program the chunk size quickly grows beyond 1MB.

I'm not sure whether this is pathological. I would certainly appreciate
a fix for it.

--
Best Regards, Patrick Ohly

The content of this message is my personal opinion only and although
I am an employee of Intel, the statements I make here in no way
represent Intel's position on the issue, nor am I authorized to speak
on behalf of Intel on this matter.






-------------------------------------------------------
This SF.Net email is sponsored by Yahoo.
Introducing Yahoo! Search Developer Network - Create apps using Yahoo!
Search APIs Find out how you can build Yahoo! directly into your own
Applications - visit http://developer.yahoo.net/?fr=offad-ysdn-ostg-q22005
_______________________________________________
Valgrind-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/valgrind-users
Loading...