|
From: Mark S. <ms...@cl...> - 2005-05-19 21:41:49
|
It looks like it's not a problem with realloc() directly, but a problem
with copying between large allocated chunks. This program:
#include <stdlib.h>
#include <string.h>
void my_memcpy(char *dest, char *src, unsigned int len)
{
for(int i=3D0; i<len; i++) {
dest[i] =3D src[i];
}
}
int main(int argc, char **argv)
{
int len =3D 0;
char *data =3D NULL;
int do_copy =3D 1;
for(int i=3D0; i<2000; i++) {
len +=3D 4096;
char *new_data =3D (char *) malloc(len*sizeof(char));
if (data && do_copy) {
my_memcpy(new_data, data, len-4096);
}
free(data);
data =3D new_data;
}
free(data);
return 0;
}
Exibits the same problem if do_copy is 1, but behaves properly if
do_copy is 0.
--Mark
-----Original Message-----
From: val...@li...
[mailto:val...@li...] On Behalf Of
Nicholas Nethercote
Sent: Thursday, May 19, 2005 2:16 PM
To: Thomas Steffen
Cc: val...@li...
Subject: Re: [Valgrind-users] Problem with realloc() + valgrind 2.4.0
(incl. sample program)
On Thu, 19 May 2005, Thomas Steffen wrote:
> If you look at the realloc function in memcheck, you will find this is
> by design. Realloc always returns a fresh piece of address space, so=20
> that it can check for any old pointer that are not updated. Of course=20
> this uses a lot of address space, which means it uses a lot of memory.
Are you sure? It looks to me like it reuses the same memory if the new=20
size is smaller or equal to the old size. It allocates new memory if
the=20
new size is bigger.
But the allocator does avoid recycling freed blocks for a while, which=20
might explain the 700MB figure.
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=3D7412&alloc_id=3D16344&op=3Dclick
_______________________________________________
Valgrind-users mailing list Val...@li...
https://lists.sourceforge.net/lists/listinfo/valgrind-users
|
|
From: Mark S. <ms...@cl...> - 2005-05-20 00:27:04
|
>So here's a question. How does the following variant behave?
...
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 =3D 0;
char *data =3D NULL;
int do_copy =3D 1;
for(int i=3D0; i<2000; i++) {
len +=3D 4096;
char *data =3D (char *) malloc(len*sizeof(char));
for (int j=3D0; j<len; j++) {
data[j] =3D 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.=20
--Mark
|
|
From: Nicholas N. <nj...@cs...> - 2005-05-21 19:06:52
|
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
|
|
From: Nicholas N. <nj...@cs...> - 2005-05-25 15:07:07
|
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 |
|
From: Patrick O. <Pat...@in...> - 2005-05-30 11:40:48
|
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. |
|
From: Mark S. <ms...@cl...> - 2005-05-23 17:05:06
|
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:nj...@cs...]=20
Sent: Saturday, May 21, 2005 12:07 PM
To: Mark Stemm
Cc: val...@li...
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=20
> buffer after it's been allocated) does not:
>
> #include <stdlib.h>
> #include <string.h>
>
> int main(int argc, char **argv)
> {
> int len =3D 0;
> char *data =3D NULL;
> int do_copy =3D 1;
> for(int i=3D0; i<2000; i++) {
> len +=3D 4096;
> char *data =3D (char *) malloc(len*sizeof(char));
> for (int j=3D0; j<len; j++) {
> data[j] =3D 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=20
> quickly climbs as the buffer gets larger.
I just looked at this. Turns out that under Valgrind, on my machine
(and=20
presumably yours) a lot of those allocations are failing -- you should
be=20
checking the result of malloc.
I think the problem is this: the program allocates a 4KB block, then=20
frees it. Valgrind puts this block on its free list. The program then=20
allocates an 8KB block. There's no block on the free list which is 8KB
or=20
greater, so Valgrind allocates new memory. And so on. So Valgrind's
free=20
list ends up holding blocks of size 4KB, 8KB, 12KB, 16KB, etc. Huge=20
amounts of memory quickly get heldon the free list, but none of the
blocks=20
are ever big enough to satisfy the requests.
Basically it's a pathological case for Valgrind's allocator. Mark, did=20
you come up with your original program (the realloc one) based on=20
behaviour you saw with a real application, or were you just
experimenting?
N
|
|
From: Julian S. <js...@ac...> - 2005-05-23 19:33:07
|
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 |
|
From: Nicholas N. <nj...@cs...> - 2005-05-23 19:54:31
|
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 |
|
From: Julian S. <js...@ac...> - 2005-05-24 12:21:08
|
> 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 |
|
From: Julian S. <js...@ac...> - 2005-05-19 23:12:26
|
> It looks like it's not a problem with realloc() directly, but a problem
> with copying between large allocated chunks. This program:
I think Nick's analysis is right. I'm just surprised V will hold onto
700M of stuff. I thought we had it so that it would only hold on to
a fixed amount, by default 1MB of space (--freelist-vol= ..)
So here's a question. How does the following variant behave?
> #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));
> free(data);
> }
>
> return 0;
> }
J
|