|
From: Paul M. <pa...@sa...> - 2004-08-22 23:21:43
|
In the course of getting Valgrind going on PowerPC, I found a couple
of bugs in find_map_space. Both of them show up when the client does
an mmap with a non-zero address but without MAP_FIXED set. I came
across them on PowerPC because we tend to map shared libraries
immediately below the executable, but they could occur on x86 as well.
The first bug occurs if the address given is less than the address of
any existing map. What happens then is that VG_(SkipNode_First)()
returns NULL. The main for loop in VG_(find_map_space)() then exits
immediately, and VG_(find_map_space)() returns 0, and the client gets
an ENOMEM error. The patch below fixes this by calling
VG_(SkipNode_First)() if VG_(SkipList_Find)() returns NULL.
The second bug is that if the client asks for an address below the
executable but the range of addresses it wants isn't free,
find_map_space will give an address just above the executable instead
of starting at VG_(client_mapbase), which is what the kernel does.
Giving an address just above the executable is bad because it
restricts the amount of memory which can be obtained with brk().
This patch fixes that by jumping up to VG_(client_mapbase) if the
address we would move up to is less than that.
Paul.
diff -urN old-cvs/coregrind/vg_memory.c valgrind-cvs/coregrind/vg_memory.c
--- old-cvs/coregrind/vg_memory.c 2004-08-11 09:37:59.000000000 +1000
+++ valgrind-cvs/coregrind/vg_memory.c 2004-08-23 08:33:01.578978112 +1000
@@ -494,9 +494,10 @@
Segment *s;
Addr ret;
Addr limit = (for_client ? VG_(client_end) : VG_(valgrind_end));
+ Addr base = (for_client ? VG_(client_mapbase) : VG_(valgrind_base));
if (addr == 0)
- addr = for_client ? VG_(client_mapbase) : VG_(valgrind_base);
+ addr = base;
else {
/* leave space for redzone and still try to get the exact
address asked for */
@@ -514,16 +515,22 @@
VG_(printf)("find_map_space: ret starts as %p-%p client=%d\n",
ret, ret+len, for_client);
- for(s = VG_(SkipList_Find)(&sk_segments, &ret);
- s != NULL && s->addr < (ret+len);
+ s = VG_(SkipList_Find)(&sk_segments, &ret);
+ if (s == NULL)
+ s = VG_(SkipNode_First)(&sk_segments);
+
+ for(; s != NULL && s->addr < (ret+len);
s = VG_(SkipNode_Next)(&sk_segments, s))
{
if (debug)
VG_(printf)("s->addr=%p len=%d (%p) ret=%p\n",
s->addr, s->len, s->addr+s->len, ret);
- if (s->addr < (ret + len) && (s->addr + s->len) > ret)
+ if (s->addr < (ret + len) && (s->addr + s->len) > ret) {
ret = s->addr+s->len;
+ if (ret < base - VKI_BYTES_PER_PAGE)
+ ret = base - VKI_BYTES_PER_PAGE;
+ }
}
if (debug) {
|
|
From: Tom H. <th...@cy...> - 2004-08-23 06:16:04
|
In message <166...@ca...>
Paul Mackerras <pa...@sa...> wrote:
> The first bug occurs if the address given is less than the address of
> any existing map. What happens then is that VG_(SkipNode_First)()
> returns NULL. The main for loop in VG_(find_map_space)() then exits
> immediately, and VG_(find_map_space)() returns 0, and the client gets
> an ENOMEM error. The patch below fixes this by calling
> VG_(SkipNode_First)() if VG_(SkipList_Find)() returns NULL.
Didn't Nick fix that recently?
> The second bug is that if the client asks for an address below the
> executable but the range of addresses it wants isn't free,
> find_map_space will give an address just above the executable instead
> of starting at VG_(client_mapbase), which is what the kernel does.
> Giving an address just above the executable is bad because it
> restricts the amount of memory which can be obtained with brk().
> This patch fixes that by jumping up to VG_(client_mapbase) if the
> address we would move up to is less than that.
Interesting. We have had complaints about brk() failing under
valgrind and I wonder if that's the cause.
Tom
--
Tom Hughes (th...@cy...)
Software Engineer, Cyberscience Corporation
http://www.cyberscience.com/
|
|
From: Nicholas N. <nj...@ca...> - 2004-08-23 09:09:39
|
On Mon, 23 Aug 2004, Tom Hughes wrote:
>> The first bug occurs if the address given is less than the address of
>> any existing map. What happens then is that VG_(SkipNode_First)()
>> returns NULL. The main for loop in VG_(find_map_space)() then exits
>> immediately, and VG_(find_map_space)() returns 0, and the client gets
>> an ENOMEM error. The patch below fixes this by calling
>> VG_(SkipNode_First)() if VG_(SkipList_Find)() returns NULL.
>
> Didn't Nick fix that recently?
No... I did fix another similar bug where a SkipList_First() call had to
be added after a failing SkipList_Find() call. The way the skiplist works
is quite strange in that respect, and easy to get wrong. I'm concerned
that some or all of the other calls to SkipList_Find() also exhibit this
bug.
I've committed that fix.
>> The second bug is that if the client asks for an address below the
>> executable but the range of addresses it wants isn't free,
>> find_map_space will give an address just above the executable instead
>> of starting at VG_(client_mapbase), which is what the kernel does.
>> Giving an address just above the executable is bad because it
>> restricts the amount of memory which can be obtained with brk().
>> This patch fixes that by jumping up to VG_(client_mapbase) if the
>> address we would move up to is less than that.
I'm not convinced this part of the patch works. It looks to me like it
might try to return the same address (base - VKI_BYTES_PER_PAGE) more than
once.
Actually, I'm not at all sure about that, because that loop -- both the
current version and the proposed new version -- are far too subtle for my
liking (not to mention uncommented). I look at them and, after a few
minutes of head-scratching, I *think* I see how they work, but there's a
real leap of faith involved. Surely this loop can be rewritten in a
clearer fashion?
> Interesting. We have had complaints about brk() failing under
> valgrind and I wonder if that's the cause.
The following program gives me a seg fault under Valgrind:
#include <stdio.h>
#include <unistd.h>
#define MAX 3000
int main () {
char* ptr;
int i;
for (i=0; i<MAX; i++) {
printf ("%d: ", i);
printf ("calling sbrk(1)\n");
ptr = sbrk(1);
printf ("sbrk returned %p\n\n", ptr);
if (ptr == (void*)-1) {
printf ("sbrk() failed!\n");
return 0;
}
*ptr = 0;
}
return 0;
}
The output being:
2588: calling sbrk(1)
sbrk returned 0x804a000
==4855==
==4855== Process terminating with default action of signal 11 (SIGSEGV):
dumping core
==4855== Access not within mapped region at address 0x804A000
==4855== at 0x80483DF: main (in /auto/homes/njn25/grind/head/brk)
==4855==
==4855== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 11 from 1)
==4855== malloc/free: in use at exit: 0 bytes in 0 blocks.
==4855== malloc/free: 0 allocs, 0 frees, 0 bytes allocated.
==4855== For a detailed leak analysis, rerun with: --leak-check=yes
==4855== For counts of detected errors, rerun with: -v
Segmentation fault
And that still happens with the second part of the patch. I'll file a bug
report about this.
N
|
|
From: Paul M. <pa...@sa...> - 2004-08-23 12:04:18
|
Nicholas Nethercote writes:
> I'm not convinced this part of the patch works. It looks to me like it
> might try to return the same address (base - VKI_BYTES_PER_PAGE) more than
> once.
No... we only do the assignment if the current segment ends before
base - VKI_BYTES_PER_PAGE. If there is a segment that overlaps that
we will find it further down the list. It's safe because that
assignment can only increase ret.
> Actually, I'm not at all sure about that, because that loop -- both the
> current version and the proposed new version -- are far too subtle for my
> liking (not to mention uncommented). I look at them and, after a few
> minutes of head-scratching, I *think* I see how they work, but there's a
> real leap of faith involved. Surely this loop can be rewritten in a
> clearer fashion?
The main if statement in the loop is just "if the proposed new bit
overlaps the existing bit". If that happens we bump the proposed new
bit up to start after the existing bit (or possibly further with my
patch). We go through all the existing bits and stop when we find a
bit that starts after the end of the proposed new bit. The assumption
is that the skiplist gives us the existing bits in increasing order.
> > Interesting. We have had complaints about brk() failing under
> > valgrind and I wonder if that's the cause.
>
> The following program gives me a seg fault under Valgrind:
[snip]
Well, this test in do_brk() is wrong:
if (PGROUNDDN(newbrk) != PGROUNDDN(VG_(brk_limit))) {
That triggers when the break goes from (e.g.) 0x10010fff to
0x10011000, and the code in there concludes (correctly) that no more
memory is needed, and updates VG_(brk_limit) to 0x10011000. Then when
we raise the break to 0x10011001, that test doesn't trigger and so we
don't allocate any more memory, but we return the new break.
Regards,
Paul.
|
|
From: Nicholas N. <nj...@ca...> - 2004-08-23 12:18:36
|
On Mon, 23 Aug 2004, Paul Mackerras wrote:
>> I'm not convinced this part of the patch works. It looks to me like it
>> might try to return the same address (base - VKI_BYTES_PER_PAGE) more than
>> once.
>
> No... we only do the assignment if the current segment ends before
> base - VKI_BYTES_PER_PAGE. If there is a segment that overlaps that
> we will find it further down the list. It's safe because that
> assignment can only increase ret.
>
>> Actually, I'm not at all sure about that, because that loop -- both the
>> current version and the proposed new version -- are far too subtle for my
>> liking (not to mention uncommented). I look at them and, after a few
>> minutes of head-scratching, I *think* I see how they work, but there's a
>> real leap of faith involved. Surely this loop can be rewritten in a
>> clearer fashion?
>
> The main if statement in the loop is just "if the proposed new bit
> overlaps the existing bit". If that happens we bump the proposed new
> bit up to start after the existing bit (or possibly further with my
> patch). We go through all the existing bits and stop when we find a
> bit that starts after the end of the proposed new bit. The assumption
> is that the skiplist gives us the existing bits in increasing order.
Ok, well explained; that's exactly what should be in a comment attached
to that code.
> Well, this test in do_brk() is wrong:
>
> if (PGROUNDDN(newbrk) != PGROUNDDN(VG_(brk_limit))) {
>
> That triggers when the break goes from (e.g.) 0x10010fff to
> 0x10011000, and the code in there concludes (correctly) that no more
> memory is needed, and updates VG_(brk_limit) to 0x10011000. Then when
> we raise the break to 0x10011001, that test doesn't trigger and so we
> don't allocate any more memory, but we return the new break.
What should the test say? Can you make a patch?
N
|
|
From: Paul M. <pa...@sa...> - 2004-08-24 13:06:27
|
Nicholas Nethercote writes:
> On Mon, 23 Aug 2004, Paul Mackerras wrote:
> > Well, this test in do_brk() is wrong:
> >
> > if (PGROUNDDN(newbrk) != PGROUNDDN(VG_(brk_limit))) {
> >
> > That triggers when the break goes from (e.g.) 0x10010fff to
> > 0x10011000, and the code in there concludes (correctly) that no more
> > memory is needed, and updates VG_(brk_limit) to 0x10011000. Then when
> > we raise the break to 0x10011001, that test doesn't trigger and so we
> > don't allocate any more memory, but we return the new break.
>
> What should the test say? Can you make a patch?
Sure, basically the test should be using PGROUNDUP rather than
PGROUNDDN. This patch fixes it. The test program runs to completion
now.
Paul.
diff -urN valgrind-cvs/coregrind/vg_syscalls.c valgrind-x86/coregrind/vg_syscalls.c
--- valgrind-cvs/coregrind/vg_syscalls.c 2004-08-24 18:26:22.483982552 +1000
+++ valgrind-x86/coregrind/vg_syscalls.c 2004-08-24 22:44:52.259061552 +1000
@@ -900,6 +900,7 @@
Addr ret = VG_(brk_limit);
static const Bool debug = False;
Segment *seg;
+ Addr current, newaddr;
if (debug)
VG_(printf)("do_brk: brk_base=%p brk_limit=%p newbrk=%p\n",
@@ -922,9 +923,9 @@
if (seg != NULL && newbrk > seg->addr)
return VG_(brk_limit);
- if (PGROUNDDN(newbrk) != PGROUNDDN(VG_(brk_limit))) {
- Addr current = PGROUNDUP(VG_(brk_limit));
- Addr newaddr = PGROUNDUP(newbrk);
+ current = PGROUNDUP(VG_(brk_limit));
+ newaddr = PGROUNDUP(newbrk);
+ if (newaddr != current) {
/* new brk in a new page - fix the mappings */
if (newbrk > VG_(brk_limit)) {
|
|
From: Nicholas N. <nj...@ca...> - 2004-08-25 17:00:09
|
On Tue, 24 Aug 2004, Paul Mackerras wrote:
>>> Well, this test in do_brk() is wrong:
>>>
>>> if (PGROUNDDN(newbrk) != PGROUNDDN(VG_(brk_limit))) {
>>>
>>> That triggers when the break goes from (e.g.) 0x10010fff to
>>> 0x10011000, and the code in there concludes (correctly) that no more
>>> memory is needed, and updates VG_(brk_limit) to 0x10011000. Then when
>>> we raise the break to 0x10011001, that test doesn't trigger and so we
>>> don't allocate any more memory, but we return the new break.
>>
>> What should the test say? Can you make a patch?
>
> Sure, basically the test should be using PGROUNDUP rather than
> PGROUNDDN. This patch fixes it. The test program runs to completion
> now.
committed, thanks
N
|