jemalloc() assumes DSS is aligned

[John Baldwin]

I tracked down a weird bug at work on the older jemalloc in FreeBSD 8/9 that a
co-worker tripped over.  Specifically, if you build the program below and link
it with gold, the program will have an _end symbol that is on an odd address
(std::nothrow results in some single-byte symbol being added to the end of the
BSS).  This causes the first arena allocated by jemalloc to use an odd
address, and the rbt_nil structures for that arena's embedded trees (like
runs_avail) to be allocated on odd addresses.  This interferes with the RB
trees using the low bit to distinguish red vs black.  Specifically, the
program ends up setting the right node of rbt_nil to an incorrect pointer
value (the low bit gets cleared) resulting in an eventual segfault.  Looking
at phkmalloc, it always applied round_page() to the results from sbrk().  I
believe that for jemalloc only the very first allocation from the DSS needs to
check for misalignment, and the patch below does fix the segfault on FreeBSD
8.  I have a stab at porting the change to jemalloc 3.0.0 in HEAD, but I'm not
sure if it is quite correct.  Also, I only made the DSS align on the quantum
boundary rather than a page boundary.  BTW, I filed a bug with the binutils
folks as I initially thought this was a gold bug.  However, POSIX doesn't make
any guarantees about the return value of sbrk(), so I think gold is not
broken.

Test program:

#include <stdio.h>
#include <new>

void foo()
{
        char *c = new(std::nothrow) char[10];
        delete c;
}

int
main()
{
        printf("Hello world\n");
}

Tested patch against FreeBSD 8:

Index: malloc.c
===================================================================
--- malloc.c (revision 225507)
+++ malloc.c (working copy)
@@ -5132,6 +5132,9 @@ MALLOC_OUT:
 #ifdef MALLOC_DSS
  malloc_mutex_init(&dss_mtx);
  dss_base = sbrk(0);
+ i = (uintptr_t)dss_base & QUANTUM_MASK;
+ if (i != 0)
+ dss_base = sbrk(QUANTUM - i);
  dss_prev = dss_base;
  dss_max = dss_base;
  extent_tree_szad_new(&dss_chunks_szad);


Untested forward port to jemalloc 3.0.0:

Index: chunk_dss.c
===================================================================
--- chunk_dss.c (revision 235919)
+++ chunk_dss.c (working copy)
@@ -123,12 +123,16 @@ chunk_in_dss(void *chunk)
 bool
 chunk_dss_boot(void)
 {
+ uintptr_t off;
 
  cassert(config_dss);
 
  if (malloc_mutex_init(&dss_mtx))
  return (true);
  dss_base = sbrk(0);
+ off = (uintptr_t)dss_base & QUANTUM_MASK;
+ if (off != 0)
+ dss_base = sbrk(QUANTUM - off);
  dss_prev = dss_base;
  dss_max = dss_base;
 
binutils ld.gold PR: http://sourceware.org/bugzilla/show_bug.cgi?id=14149
 
--
John Baldwin
_______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "[hidden email]"

[Jason Evans-2]

On Jun 13, 2012, at 8:31 AM, John Baldwin wrote:

> I tracked down a weird bug at work on the older jemalloc in FreeBSD 8/9 that a
> co-worker tripped over.  Specifically, if you build the program below and link
> it with gold, the program will have an _end symbol that is on an odd address
> (std::nothrow results in some single-byte symbol being added to the end of the
> BSS).  This causes the first arena allocated by jemalloc to use an odd
> address, and the rbt_nil structures for that arena's embedded trees (like
> runs_avail) to be allocated on odd addresses.  This interferes with the RB
> trees using the low bit to distinguish red vs black.  Specifically, the
> program ends up setting the right node of rbt_nil to an incorrect pointer
> value (the low bit gets cleared) resulting in an eventual segfault.  Looking
> at phkmalloc, it always applied round_page() to the results from sbrk().  I
> believe that for jemalloc only the very first allocation from the DSS needs to
> check for misalignment, and the patch below does fix the segfault on FreeBSD
> 8.  I have a stab at porting the change to jemalloc 3.0.0 in HEAD, but I'm not
> sure if it is quite correct.  Also, I only made the DSS align on the quantum
> boundary rather than a page boundary.  BTW, I filed a bug with the binutils
> folks as I initially thought this was a gold bug.  However, POSIX doesn't make
> any guarantees about the return value of sbrk(), so I think gold is not
> broken.

Hi John,

Your fix for FreeBSD 7/8/9 looks correct to me.  I don't currently have any development machines running anything but 10-CURRENT, so I'd be grateful if you could commit the fix, assuming it isn't much trouble for you.  (I'll set up additional development installations if needed.)

I don't think this is an issue for HEAD's chunk_alloc_dss(), because there is logic to always insert enough padding to allocate on chunk alignment boundaries, and also base_alloc() no longer makes any attempt to use a partial dss 'chunk'.

Thanks,
Jason

P.S. Sorry about putting off responding to your original email for too long._______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "[hidden email]"

[John Baldwin]

On Wednesday, June 13, 2012 12:29:26 pm Jason Evans wrote:

> On Jun 13, 2012, at 8:31 AM, John Baldwin wrote:
> > I tracked down a weird bug at work on the older jemalloc in FreeBSD 8/9 that a
> > co-worker tripped over.  Specifically, if you build the program below and link
> > it with gold, the program will have an _end symbol that is on an odd address
> > (std::nothrow results in some single-byte symbol being added to the end of the
> > BSS).  This causes the first arena allocated by jemalloc to use an odd
> > address, and the rbt_nil structures for that arena's embedded trees (like
> > runs_avail) to be allocated on odd addresses.  This interferes with the RB
> > trees using the low bit to distinguish red vs black.  Specifically, the
> > program ends up setting the right node of rbt_nil to an incorrect pointer
> > value (the low bit gets cleared) resulting in an eventual segfault.  Looking
> > at phkmalloc, it always applied round_page() to the results from sbrk().  I
> > believe that for jemalloc only the very first allocation from the DSS needs to
> > check for misalignment, and the patch below does fix the segfault on FreeBSD
> > 8.  I have a stab at porting the change to jemalloc 3.0.0 in HEAD, but I'm not
> > sure if it is quite correct.  Also, I only made the DSS align on the quantum
> > boundary rather than a page boundary.  BTW, I filed a bug with the binutils
> > folks as I initially thought this was a gold bug.  However, POSIX doesn't make
> > any guarantees about the return value of sbrk(), so I think gold is not
> > broken.
>
> Hi John,
>
> Your fix for FreeBSD 7/8/9 looks correct to me.  I don't currently have any development machines running anything but 10-CURRENT, so I'd be

grateful if you could commit the fix, assuming it isn't much trouble for you.  (I'll set up additional development installations if needed.)

Sure, I'm fine with doing that.

> I don't think this is an issue for HEAD's chunk_alloc_dss(), because there is logic to always insert enough padding to allocate on chunk alignment
boundaries, and also base_alloc() no longer makes any attempt to use a partial dss 'chunk'.

Ok, this was my main concern was to ensure it was fixed going forward.

> Thanks,
> Jason
>
> P.S. Sorry about putting off responding to your original email for too long.

No problem, I figured the original got lost. :-P

--
John Baldwin
_______________________________________________
[hidden email] mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-current
To unsubscribe, send any mail to "[hidden email]"