Skip to contentSkip to conversation

get_unmapped_area() change -> non booting machine

BUG Benjamin Herrenschmidt 8 participants 22 messages Feb 10, 2004 – Feb 13, 2004

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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.

#1 lore raw
Quoted 7 lines · On Tue, 10 Feb 2004 14:47:09 +1100 Benjamin Herrenschmidt…

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).

mm/mmap.c renamed from mm/mmap.c-o +22 -8
@@ -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
#2 lore raw
Quoted 8 lines · Andi Kleen
Quoted 6 lines · On Tue, 10 Feb 2004 14:47:09 +1100 Benjamin Herrenschmidt…

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.

Quoted 6 lines
Quoted 1 line

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.

#3 lore raw
In reply to Benjamin Herrenschmidt
Quoted 8 lines · Benjamin Herrenschmidt

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

#4 lore raw
Quoted 3 lines · Linus Torvalds

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

#5 lore raw
Quoted 2 lines · On Tue, 10 Feb 2004 17:37:38 +0000 Jamie Lokier <[email protected]> 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

#20 lore raw
In reply to Linus Torvalds
Quoted 4 lines

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

Quoted 3 lines

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.

#19 lore raw
In reply to Jamie Lokier
Quoted 3 lines

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.

#21 lore raw
In reply to Benjamin Herrenschmidt
Quoted 5 lines · On Wed, 11 Feb 2004 09:17:02 +1100 Benjamin Herrenschmidt…

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.

Quoted 2 lines

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

#6 lore raw
In reply to Andi Kleen
Quoted 4 lines · Andi Kleen
Quoted 2 lines

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
}

#7 lore raw
Quoted 7 lines · Ingo Molnar

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

#8 lore raw

--On Thursday, February 12, 2004 08:36:48 -0800 Linus Torvalds

Quoted 5 lines · <[email protected]> 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

#9 lore raw
Quoted 6 lines · Dave McCracken

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

#10 lore raw

--On Thursday, February 12, 2004 09:17:44 -0800 Linus Torvalds

Quoted 4 lines · <[email protected]> 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

#11 lore raw
Quoted 4 lines · Dave McCracken

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

#12 lore raw

--On Thursday, February 12, 2004 10:19:21 -0800 Linus Torvalds

Quoted 3 lines · <[email protected]> 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

#13 lore raw
In reply to Linus Torvalds
Quoted 6 lines

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.

#14 lore raw
In reply to Linus Torvalds
Quoted 5 lines · Linus Torvalds

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

#18 lore raw
In reply to Linus Torvalds
Followup to:  <[email protected]>
By author:    Linus Torvalds <[email protected]>
In newsgroup: linux.dev.kernel
Quoted 6 lines

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

Signature · 4 lines
PGP public key available - finger [email protected]
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!!
#15 lore raw
In reply to Jamie Lokier
Quoted 11 lines · On Fri, 13 Feb 2004 03:26:04 +0000 Jamie Lokier <[email protected]> wrote:
Quoted 5 lines · Linus Torvalds

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

#16 lore raw
Quoted 10 lines · --On Sunday, February 15, 2004 06:25:44 +0100 Andi Kleen <[email protected]> wrote:
Quoted 7 lines · On Fri, 13 Feb 2004 03:26:04 +0000 Jamie Lokier <[email protected]> wrote:
Quoted 5 lines · Linus Torvalds

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".

Quoted 7 lines
Quoted 4 lines

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.

#17 lore raw
Quoted 5 lines · On Fri, 13 Feb 2004 10:33:55 -0800 "Martin J. Bligh" <[email protected]> wrote:
Quoted 2 lines

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