[BUG] get_unmapped_area() change -> non booting machine

[BUG] get_unmapped_area() change -> non booting machine

[Benjamin Herrenschmidt]

Hi !

I've finally found what is causing my box not to boot any more
with recent 2.6.3-rc* bk's.

Andi change to get_unmapped_area() is triggering that interesting
scenario:

 - bash tries to load
 - ld.so tries to map libc somewhere below the executable at a
location provided by the prelink informations. However, probably due to
outdated prelink informations (I didn't re-run prelink since I updated
glibc), it won't fit.
 - Andi change cause do_mmap() to actually do a search of a free
space from the address... when ends up beeing right after the brk point
of the just loaded bash
 - something (glibc) is now mapped right after brk point of bash,
preventing it from malloc'ing, so it dies.

Just reverting the patch fixes it. Though, the patch do make sense in
some cases, paulus suggested to modify the code so that for a non
MAP_FIXED map, it still search from the passed-in address, but avoids
the spare between the current mm->brk and TASK_UNMAPPED_BASE, thus the
algorithm would still work for things outside of these areas.

Commment ?

(Sorry, no patch at this point, still recovering the box and deep
into another bug...)

Ben.

Re: [BUG] get_unmapped_area() change -> non booting machine

[Linus Torvalds]

On Tue, 10 Feb 2004, Benjamin Herrenschmidt wrote:
> 
> Just reverting the patch fixes it. Though, the patch do make sense in
> some cases, paulus suggested to modify the code so that for a non
> MAP_FIXED map, it still search from the passed-in address, but avoids
> the spare between the current mm->brk and TASK_UNMAPPED_BASE, thus the
> algorithm would still work for things outside of these areas.
> 
> Commment ?

I'd rather revert it. If it has broken something, I'm nervous that random 
hacking will just break more. I see the patch that fixes it, but what else 
will now break? Having a magic special case for "brk" is just too damn 
ugly for words.

What I find strange is that bash passed in something else than NULL as the 
argument in the first place. Doing a quick trace of my bash executable 
shows non-NULL hints only for MAP_FIXED mmap's. So what triggered this? 

Random special cases in code are just evil, and end up biting us in the 
end. Which is why I'd rather see the revert, along with more of a look at 
_why_ bash does what it does for you.

			Linus

Re: [BUG] get_unmapped_area() change -> non booting machine

[Jamie Lokier]

Linus Torvalds wrote:
> What I find strange is that bash passed in something else than NULL as the 
> argument in the first place. Doing a quick trace of my bash executable 
> shows non-NULL hints only for MAP_FIXED mmap's. So what triggered this? 

Run the "prelink" program on your system.

It's not bash which is using non-NULL hints, it's ld.so.  Prelinked
libraries have relocations already resolved on the assumption that
they are mapped at a known address.  (Prelink chooses a different
address for each library).  ld.so calls mmap() with that address.

If the library cannot be mapped at the requested address, then ld.so
has to do dynamic linking as usual, dirtying some pages and looking up
symbols.

The real question is - why does malloc() break?  I'd expect malloc()
to use MAP_ANON these days, when brk() fails.  But it seems not.

-- Jamie

Re: [BUG] get_unmapped_area() change -> non booting machine

[Benjamin Herrenschmidt]

> The real question is - why does malloc() break?  I'd expect malloc()
> to use MAP_ANON these days, when brk() fails.  But it seems not.

I don't know, trying to find my way in glibc mess^H^H^H^Hsource...

Well, it's non-obvious, it should have fallen back to mmap, unless
something wrong in the glibc build undefined HAVE_MMAP ...

Ben.

Re: [BUG] get_unmapped_area() change -> non booting machine

[Andi Kleen]

On Tue, 10 Feb 2004 17:37:38 +0000
Jamie Lokier <jamie@shareable.org> wrote:

 
> The real question is - why does malloc() break?  I'd expect malloc()
> to use MAP_ANON these days, when brk() fails.  But it seems not.

Yep, that's the real bug.

-Andi

Re: [BUG] get_unmapped_area() change -> non booting machine

[Ingo Molnar]

* Andi Kleen <ak@suse.de> wrote:

> > The real question is - why does malloc() break?  I'd expect malloc()
> > to use MAP_ANON these days, when brk() fails.  But it seems not.
> 
> Yep, that's the real bug.

i've pasted the relevant glibc malloc code below - it does use mmap() as
a fallback.

why in this particular case it failed i dont know - i believe some
_minimal_ brk space is supposed to be available though, so if you break
mmap() to fill in the brk space then that might break glibc assumptions.

	Ingo


  if (size > 0)
    brk = (char*)(MORECORE(size));

  if (brk != (char*)(MORECORE_FAILURE)) {
    /* Call the `morecore' hook if necessary.  */
    if (__after_morecore_hook)
      (*__after_morecore_hook) ();
  } else {
  /*
    If have mmap, try using it as a backup when MORECORE fails or
    cannot be used. This is worth doing on systems that have "holes" in
    address space, so sbrk cannot extend to give contiguous space, but
    space is available elsewhere.  Note that we ignore mmap max count
    and threshold limits, since the space will not be used as a
    segregated mmap region.
  */

#if HAVE_MMAP
    /* Cannot merge with old top, so add its size back in */
    if (contiguous(av))
      size = (size + old_size + pagemask) & ~pagemask;

    /* If we are relying on mmap as backup, then use larger units */
    if ((unsigned long)(size) < (unsigned long)(MMAP_AS_MORECORE_SIZE))
      size = MMAP_AS_MORECORE_SIZE;

    /* Don't try if size wraps around 0 */
    if ((unsigned long)(size) > (unsigned long)(nb)) {

      char *mbrk = (char*)(MMAP(0, size, PROT_READ|PROT_WRITE, MAP_PRIVATE));

      if (mbrk != MAP_FAILED) {

        /* We do not need, and cannot use, another sbrk call to find end */
        brk = mbrk;
        snd_brk = brk + size;

        /*
           Record that we no longer have a contiguous sbrk region.
           After the first time mmap is used as backup, we do not
           ever rely on contiguous space since this could incorrectly
           bridge regions.
        */
        set_noncontiguous(av);
      }
    }
#endif
  }

Re: [BUG] get_unmapped_area() change -> non booting machine

[Linus Torvalds]

On Thu, 12 Feb 2004, Ingo Molnar wrote:
> 
> i've pasted the relevant glibc malloc code below - it does use mmap() as
> a fallback.
> 
> why in this particular case it failed i dont know - i believe some
> _minimal_ brk space is supposed to be available though, so if you break
> mmap() to fill in the brk space then that might break glibc assumptions.

I really think that we should aim for "brk()" just working. It's often
faster than mmap, and it's one of those very basic things (ie we should
_not_ assume we have glibc and malloc(), and others may well want to use
brk() too).

For now, the fix is to just revert the change that triggered this. But in 
the long run I'd like to make it less fragile without having magic special 
cases.

One option is to mark the brk() VMA's as being grow-up (which they are), 
and make get_unmapped_area() realize that it should avoid trying to 
allocate just above grow-up segments or just below grow-down segments. 
That's still something of a special case, but at least it's not "magic" 
any more, now it's more of a "makes sense".

Hmm?

		Linus

Re: [BUG] get_unmapped_area() change -> non booting machine

[Dave McCracken]

--On Thursday, February 12, 2004 08:36:48 -0800 Linus Torvalds
<torvalds@osdl.org> wrote:

> One option is to mark the brk() VMA's as being grow-up (which they are), 
> and make get_unmapped_area() realize that it should avoid trying to 
> allocate just above grow-up segments or just below grow-down segments. 
> That's still something of a special case, but at least it's not "magic" 
> any more, now it's more of a "makes sense".

So what's a reasonable value for 'not just above' and 'not just below'?  We
could skip the entire hole, which would give us reasonable behavior for the
brk area, but it wouldn't work so well for the area below the stack.  I'm
sure if we define a 'reasonable' value to skip someone somewhere will
collide with it.

Dave McCracken

Re: [BUG] get_unmapped_area() change -> non booting machine

[Linus Torvalds]

On Thu, 12 Feb 2004, Dave McCracken wrote:
> 
> So what's a reasonable value for 'not just above' and 'not just below'?  We
> could skip the entire hole, which would give us reasonable behavior for the
> brk area, but it wouldn't work so well for the area below the stack.  I'm
> sure if we define a 'reasonable' value to skip someone somewhere will
> collide with it.

Well, we have had _exactly_ this issue before, which is why I mentioned 
it.

See the HP-PA support code (for "CONFIG_STACK_GROWSUP") for setting up the 
stack in such a way that it leaves some empty space above it in fs/exec.c, 
for example. There it does

	...
        /* Limit stack size to 1GB */
        stack_base = current->rlim[RLIMIT_STACK].rlim_max;
        if (stack_base > (1 << 30))
                stack_base = 1 << 30;
        stack_base = PAGE_ALIGN(STACK_TOP - stack_base);
	...

it it uses RLIMIT_STACK plus a maximum limit (although it's a _big_
maximum limit, much bigger than we'd use for BSS). So we could do
something similar for the BSS, with obviously a smaller hard limit (on a 
64-bit architecture a gigabyte is fine, but ..)

			Linus

Re: [BUG] get_unmapped_area() change -> non booting machine

[Dave McCracken]

--On Thursday, February 12, 2004 09:17:44 -0800 Linus Torvalds
<torvalds@osdl.org> wrote:

> it it uses RLIMIT_STACK plus a maximum limit (although it's a _big_
> maximum limit, much bigger than we'd use for BSS). So we could do
> something similar for the BSS, with obviously a smaller hard limit (on a 
> 64-bit architecture a gigabyte is fine, but ..)

Hmm... would it work to just do something like 'if the previous vma is
grow-up then allocate from the top of the hole'?  It'd eliminate the need
for a hard limit and should pretty much stay out of the way of BSS.

Dave McCracken

Re: [BUG] get_unmapped_area() change -> non booting machine

[Linus Torvalds]

On Thu, 12 Feb 2004, Dave McCracken wrote:
> 
> Hmm... would it work to just do something like 'if the previous vma is
> grow-up then allocate from the top of the hole'?  It'd eliminate the need
> for a hard limit and should pretty much stay out of the way of BSS.

Well, the _common_ case at least for the loader is that the "top of the 
hole" is actually the stack. So the above would _really_ suck, and crash 
pretty much immediately ;)

It would also cause the strange behaviour that we'd start allocating the 
virtual memory areas in "reverse order", ie we'd start at the top and grow 
down.

So I don't think that's a very good approach.

This is why special cases get complex: they end up feeding yet more 
special cases.

		Linus

Re: [BUG] get_unmapped_area() change -> non booting machine

[Dave McCracken]

--On Thursday, February 12, 2004 10:19:21 -0800 Linus Torvalds
<torvalds@osdl.org> wrote:

> Well, the _common_ case at least for the loader is that the "top of the 
> hole" is actually the stack. So the above would _really_ suck, and crash 
> pretty much immediately ;)

Hmm, good point.  My mental image of the address space tagged the section
at TASK_UNMAPPED_BASE as already allocated.

Dave McCracken

Re: [BUG] get_unmapped_area() change -> non booting machine

[Benjamin Herrenschmidt]

> One option is to mark the brk() VMA's as being grow-up (which they are), 
> and make get_unmapped_area() realize that it should avoid trying to 
> allocate just above grow-up segments or just below grow-down segments. 
> That's still something of a special case, but at least it's not "magic" 
> any more, now it's more of a "makes sense".

Though we need a way to represent TASK_UNMAPPED_BASE, no ? (as the
limit above which it's ok). 

Ben.

Re: [BUG] get_unmapped_area() change -> non booting machine

[Jamie Lokier]

Linus Torvalds wrote:
> One option is to mark the brk() VMA's as being grow-up (which they are), 
> and make get_unmapped_area() realize that it should avoid trying to 
> allocate just above grow-up segments or just below grow-down segments. 
> That's still something of a special case, but at least it's not "magic" 
> any more, now it's more of a "makes sense".

That reminds me.  What happens when grow-down stack VMAs finally bump
into another VMA.  Is there an unmapped guard page retained to segfault
the program, or does the program silently start overwriting the VMA it
bumped into?

-- Jamie

Re: [BUG] get_unmapped_area() change -> non booting machine

[Andi Kleen]

On Fri, 13 Feb 2004 03:26:04 +0000
Jamie Lokier <jamie@shareable.org> wrote:

> Linus Torvalds wrote:
> > One option is to mark the brk() VMA's as being grow-up (which they are), 
> > and make get_unmapped_area() realize that it should avoid trying to 
> > allocate just above grow-up segments or just below grow-down segments. 
> > That's still something of a special case, but at least it's not "magic" 
> > any more, now it's more of a "makes sense".
> 
> That reminds me.  What happens when grow-down stack VMAs finally bump
> into another VMA.  Is there an unmapped guard page retained to segfault
> the program, or does the program silently start overwriting the VMA it
> bumped into?

In the standard kernel it silently overwrites, but in 2.4-aa there was a patch forever
that adds a guard page.

-Andi

Re: [BUG] get_unmapped_area() change -> non booting machine

[Martin J. Bligh]

--On Sunday, February 15, 2004 06:25:44 +0100 Andi Kleen <ak@suse.de> wrote:

> On Fri, 13 Feb 2004 03:26:04 +0000
> Jamie Lokier <jamie@shareable.org> wrote:
> 
>> Linus Torvalds wrote:
>> > One option is to mark the brk() VMA's as being grow-up (which they are), 
>> > and make get_unmapped_area() realize that it should avoid trying to 
>> > allocate just above grow-up segments or just below grow-down segments. 
>> > That's still something of a special case, but at least it's not "magic" 
>> > any more, now it's more of a "makes sense".
>> 
>> That reminds me.  What happens when grow-down stack VMAs finally bump
>> into another VMA.  Is there an unmapped guard page retained to segfault
>> the program, or does the program silently start overwriting the VMA it
>> bumped into?
> 
> In the standard kernel it silently overwrites, but in 2.4-aa there was a patch forever
> that adds a guard page.

Do you happen to remember the name of the patch? Hunting in Andrea's tree
isn't always easy ;-)

M.

Re: [BUG] get_unmapped_area() change -> non booting machine

[Andi Kleen]

On Fri, 13 Feb 2004 10:33:55 -0800
"Martin J. Bligh" <mbligh@aracnet.com> wrote:

> > In the standard kernel it silently overwrites, but in 2.4-aa there was a patch forever
> > that adds a guard page.
> 
> Do you happen to remember the name of the patch? Hunting in Andrea's tree
> isn't always easy ;-)

00_silent-stack-overflow-18

-Andi

Re: [BUG] get_unmapped_area() change -> non booting machine

[H. Peter Anvin]

Followup to:  <Pine.LNX.4.58.0402120833000.5816@home.osdl.org>
By author:    Linus Torvalds <torvalds@osdl.org>
In newsgroup: linux.dev.kernel
> 
> I really think that we should aim for "brk()" just working. It's often
> faster than mmap, and it's one of those very basic things (ie we should
> _not_ assume we have glibc and malloc(), and others may well want to use
> brk() too).
> 

Okay... I'll ask... what is the point with brk(), i.e. what makes it
faster?  If we didn't have brk(), we could get rid of UNMAPPED_BASE
and therefore get rid of the artificial splitting of userspace memory
(modulo prelink, but that's optional.)

brk() at least on the surface really looks like a strange legacy
interface.  Obviously it's important on nommu architectures, but on
mmu architectures it seems rather redundant.

	-hpa
-- 
PGP public key available - finger hpa@zytor.com
Key fingerprint: 2047/2A960705 BA 03 D3 2C 14 A8 A8 BD  1E DF FE 69 EE 35 BD 74
"The earth is but one country, and mankind its citizens."  --  Bahá'u'lláh
Just Say No to Morden * The Shadows were defeated -- Babylon 5 is renewed!!

Re: [BUG] get_unmapped_area() change -> non booting machine

[Benjamin Herrenschmidt]

> What I find strange is that bash passed in something else than NULL as the 
> argument in the first place. Doing a quick trace of my bash executable 
> shows non-NULL hints only for MAP_FIXED mmap's. So what triggered this? 

It's ld.so which passed the prelink'ed address as a hit on a part glibc
itself. Since glibc is prelinked below the executable on PPC and since
my prelink'ed informations are outdated (prelink somewhat broke on PPC
in latest debian SID), the library wouldn't fit, thus mmap tried to
move it upward... to the brk hole. At least that is my explanation, I
didn't trace the code in ld.so

> Random special cases in code are just evil, and end up biting us in the 
> end. Which is why I'd rather see the revert, along with more of a look at 
> _why_ bash does what it does for you.

It's not bash, it's ld.so... Note that Andi's patch also fix a potential
similar issue with the free_area_cache, if somebody does a MAP_FIXED to
low addresses, then a un-hinted mmap, then that mmap will have chances
to be put straight after brk, causing the same kind of interesting issues.

So if you don't take Andi's latest patch, maybe you should still take
the part that avoid playing with free_area_cache on MAP_FIXED mappings ?

Ben.

Re: [BUG] get_unmapped_area() change -> non booting machine

[Andi Kleen]

On Wed, 11 Feb 2004 09:17:02 +1100
Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote:


> 
> It's not bash, it's ld.so... Note that Andi's patch also fix a potential
> similar issue with the free_area_cache, if somebody does a MAP_FIXED to
> low addresses, then a un-hinted mmap, then that mmap will have chances
> to be put straight after brk, causing the same kind of interesting issues.

Actually, MAP_FIXED is already handled in the caller. It can only happen
for hints without MAP_FIXED.
 
> So if you don't take Andi's latest patch, maybe you should still take
> the part that avoid playing with free_area_cache on MAP_FIXED mappings ?

Reverting everything should have the same effect (it was really a bug I added) 
Doing that would be fine for me, that change was not critical, just nice to 
have.

-Andi

Re: [BUG] get_unmapped_area() change -> non booting machine

[Andi Kleen]

On Tue, 10 Feb 2004 14:47:09 +1100
Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote:
> Just reverting the patch fixes it. Though, the patch do make sense in
> some cases, paulus suggested to modify the code so that for a non
> MAP_FIXED map, it still search from the passed-in address, but avoids
> the spare between the current mm->brk and TASK_UNMAPPED_BASE, thus the
> algorithm would still work for things outside of these areas.
> 
> Commment ?

Can you test this patch please?  It essentially implements Paulus' suggestion.

It also fixes another issue (don't use free_area_cache when the user gave an
address hint).

--- linux-2.6.3rc1-amd64/mm/mmap.c-o	2004-01-28 17:12:37.000000000 +0100
+++ linux-2.6.3rc1-amd64/mm/mmap.c	2004-02-12 00:16:35.000000000 +0100
@@ -727,18 +727,20 @@
  */
 #ifndef HAVE_ARCH_UNMAPPED_AREA
 static inline unsigned long
-arch_get_unmapped_area(struct file *filp, unsigned long addr,
+arch_get_unmapped_area(struct file *filp, unsigned long uaddr,
 		unsigned long len, unsigned long pgoff, unsigned long flags)
 {
 	struct mm_struct *mm = current->mm;
 	struct vm_area_struct *vma;
 	unsigned long start_addr;
+	unsigned long unmapped_base;
+	unsigned long addr;
 
 	if (len > TASK_SIZE)
 		return -ENOMEM;
 
-	if (addr) {
-		addr = PAGE_ALIGN(addr);
+	if (uaddr) {
+		addr = PAGE_ALIGN(uaddr);
 		vma = find_vma(mm, addr);
 		if (TASK_SIZE - len >= addr &&
 		    (!vma || addr + len <= vma->vm_start))
@@ -747,28 +749,40 @@
 		addr = mm->free_area_cache;
 	start_addr = addr;
 
+	unmapped_base = TASK_UNMAPPED_BASE;
 full_search:
-	for (vma = find_vma(mm, addr); ; vma = vma->vm_next) {
+	for (vma = find_vma(mm, addr); ; ) {
 		/* At this point:  (!vma || addr < vma->vm_end). */
 		if (TASK_SIZE - len < addr) {
 			/*
 			 * Start a new search - just in case we missed
 			 * some holes.
 			 */
-			if (start_addr != TASK_UNMAPPED_BASE) {
-				start_addr = addr = TASK_UNMAPPED_BASE;
+			if (start_addr > unmapped_base) {
+				start_addr = addr = unmapped_base;
 				goto full_search;
 			}
 			return -ENOMEM;
 		}
+		/* On the first pass always skip the brk gap to not
+		   confuse glibc malloc.  This can happen with user
+		   address hints < TASK_UNMAPPED_BASE. */
+		if (addr >= mm->brk && addr < unmapped_base) { 
+			vma = find_vma(mm, unmapped_base); 
+			addr = unmapped_base;
+			continue;
+		}
 		if (!vma || addr + len <= vma->vm_start) {
 			/*
-			 * Remember the place where we stopped the search:
+			 * Remember the place where we stopped the search,
+			 * but only if the user didn't give hints.
 			 */
-			mm->free_area_cache = addr + len;
+			if (uaddr == 0) 
+				mm->free_area_cache = addr + len;
 			return addr;
 		}
 		addr = vma->vm_end;
+		vma = vma->vm_next;
 	}
 }
 #else

Re: [BUG] get_unmapped_area() change -> non booting machine

[Benjamin Herrenschmidt]

On Thu, 2004-02-12 at 10:23, Andi Kleen wrote:
> On Tue, 10 Feb 2004 14:47:09 +1100
> Benjamin Herrenschmidt <benh@kernel.crashing.org> wrote:
> > Just reverting the patch fixes it. Though, the patch do make sense in
> > some cases, paulus suggested to modify the code so that for a non
> > MAP_FIXED map, it still search from the passed-in address, but avoids
> > the spare between the current mm->brk and TASK_UNMAPPED_BASE, thus the
> > algorithm would still work for things outside of these areas.
> > 
> > Commment ?
> 
> Can you test this patch please?  It essentially implements Paulus' suggestion.
> 
> It also fixes another issue (don't use free_area_cache when the user gave an
> address hint).

Seem to boot fine here, my libc with wrong prelink hints gets properly
pushed above TASK_UNMAPPED_BASE.

Andrew/Linus, if it works for you, can you push to 2.6.3 before release?
The current stuff will break boot on a number of previously working
configurations.

Ben.