Race condition using ATOMIC_FASTBINS in _int_free causes crash or heap corruption

Created attachment 6833
Reproduction recipe

I reported the following bug in ubuntu's libc about 6 months ago where the ATOMIC_FASTBINS feature can crash or cause heap corruption.

https://bugs.launchpad.net/ubuntu/+source/eglibc/+bug/1020210

I'm pasting the content of that problem here and will attach the reproduction recipe. Unfortunately, the reproduction recipe is only reliable with the exact version of eglibc in ubuntu, given enough time to build an arbitrary version, I should be able to create one that works with any version.

----

We have an application which makes heavy allocation and de-allocation demands from multiple threads. We run this application continuously on many servers, and once every several CPU months or years, we were getting a crash in _int_free that did not look like vanilla heap corruption. I believe I have narrowed it down to a race condition in _int_free due to the ATOMIC_FASTBINS feature. Basically, in the lockless FASTBIN _int_free path, a chunk is pulled into a local variable with the intent to add it to the fastbins list. However, the heap consolidation/trim code can race with this, and can coalesce the entire block and/or give it back to the OS before _int_free has a chance to try and store it into the fastbins list.

The problem is very challenging to reproduce in situ, but using gdb I have a recipe which demonstrates the crash 100% of the time on my 12.04 x64 system running eglibc 2.15. It relies on malloc_trim, although in our in situ data, the consolidation is triggered as a result of a normal free. malloc_trim is just easier to control.

While I am not a glibc developer, I could not see any easy ways to fix the situation shy of disabling ATOMIC_FASTBINS.

I am attaching the reproduction source. Other pertinent information follows:

> jpieper@calculon:~/downloads$ lsb_release -rd
> Description: Ubuntu 12.04 LTS
> Release: 12.04

> jpieper@calculon:~/downloads$ apt-cache policy libc6
> libc6:
> Installed: 2.15-0ubuntu10
> Candidate: 2.15-0ubuntu10
> Version table:
> *** 2.15-0ubuntu10 0
> 500 http://us.archive.ubuntu.com/ubuntu/ precise/main amd64 Packages
> 100 /var/lib/dpkg/status

What I expect: I expect the attached application, when run using the gdb script in the comments, to complete with no failures.
What happened: A SIGSEGV after the final continue.

I can't reproduce this on Fedora 17 x86_64 (glibc-2.15 + patches). Can you reproduce this with vanilla glibc? Also, can you reproduce this with newer versions of eglibc. glibc-2.15 had ATOMIC_FASTBINS removed, i.e. made into an implicit option, so there's no way to disable it.

I was able to reproduce this bug on Fedora 19, x86_64.

Reproduction required a slight modification of the recipe: the breakpoint in malloc.c needs to happen at line 3865. This line will continue to change as new versions of the library are released.

Required packages: glibc-debuginfo boost-devel boost-thread gcc-c++

[testuser@localhost ~]$ yum info glibc
Loaded plugins: auto-update-debuginfo, langpacks, refresh-packagekit
Installed Packages
Name : glibc
Arch : x86_64
Version : 2.17
Release : 18.fc19

[testuser@localhost ~]$ cat /etc/redhat-release
Fedora release 19 (Schrödinger’s Cat)

[testuser@localhost ~]$ cat gdb_script
break main
r
set scheduler-locking on
break 54
break 59
break 60
c
break malloc.c:3865
c
thread 2
c
c
thread 1
c
[testuser@localhost ~]$

I can reproduce this on the Ubuntu Trusty Tahr amd64 daily snapshot: (d6856805ca67b41eac70213736c198eb *trusty-desktop-amd64.iso)

This confirms the bug's existence up through eglibc 2.17-93ubuntu4. I have attached an updated recipe for this target.

testuser@trusty:~$ apt-cache policy libc6
libc6:
  Installed: 2.17-93ubuntu4
  Candidate: 2.17-93ubuntu4

testuser@trusty:~$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description: Ubuntu Trusty Tahr (development branch)
Release: 14.04
Codename: trusty

Created attachment 7250
Trusty Tahr Reproduction Recipe

(In reply to Nate Gallaher from comment #4)
> Created attachment 7250 [details]
> Trusty Tahr Reproduction Recipe

On glibc master the test does not produce a SIGSEGV and can be continued and exits normally.

It would really help if you could describe in detail what you think is the race condition between malloc_trim and the fastbin implementation?

Carlos, this is faster to debug on paper than trying debug optimized program.

For minimal example what is wrong I could trigger assert for unoptimized version of malloc. In optimized version you need go to assembly to see where gcc scheduled loads.

Idea is simple, while we free one chunk then a chunk on top of fastbin could be in other thread allocated, resized and then returned back into top of fastbin to trigger assertion or seqfault when trim unmaps corresponding page.

A program is following,

#include <stdlib.h>
#include <pthread.h>

void * freea (void *p)
{
  free (p); // 1
}

int main ()
{
  pthread_t x;
  char *u, *v;
  u = malloc (16);
  pthread_create (&x, NULL, freea, u);

  v = malloc (16);
  free (v); // 2

  malloc_trim (0);
  v = malloc (512); // 3
  free (v);

  malloc_trim (0);
  v = malloc (16);
  free (v); // 4
}

First step into free 1 until you get to this fragment.

Here run free 2 so v gets into top of fastbin.

    unsigned int idx = fastbin_index(size); // 32 >> 4 = 2
    fb = &fastbin (av, idx);

    mchunkptr fd;
    mchunkptr old = *fb; // v
    unsigned int old_idx = ~0u;
    do
      {
        /* Another simple check: make sure the top of the bin is not the
           record we are going to add (i.e., double free). */
        if (__builtin_expect (old == p, 0))
          {
            errstr = "double free or corruption (fasttop)";
            goto errout;
          }

Now here run step 3 where v is chunk of size 528

        if (old != NULL)
          old_idx = fastbin_index(chunksize(old)); // 528 >> 4 = 33
        p->fd = fd = old;

And continue by step 4 which returns v into top of fastbin. which is same state as at 2.

      }
    while ((old = catomic_compare_and_exchange_val_rel (fb, p, fd)) != fd);

And as 33 != 2 we cause an error.

    if (fd != NULL && __builtin_expect (old_idx != idx, 0))
      {
        errstr = "invalid fastbin entry (free)";
        goto errout;
      }

[For the benefit of Carlos and other developers]

There are two patches for this bug posted to libc-alpha@, one from Ondrej and one from myself.

The attached Trusty Tahr reproduction testcase has line numbers for GDB breakpoints wrong, and one has to correct them to get the failure.

Created attachment 7331
Trusty reproduction testcase

Fixed trusty testcase.

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, master has been updated
       via abc26e998f74750850cc02f9c249ee794cbdd8e8 (commit)
       via 362b47fe09ca9a928d444c7e2f7992f7f61bfc3e (commit)
      from b9bcbbcbe7afa94442d335811d4a1c1e0c0a1daf (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=abc26e998f74750850cc02f9c249ee794cbdd8e8

commit abc26e998f74750850cc02f9c249ee794cbdd8e8
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:55:03 2013 +1300

    Restore accidentally deleted bug-fix entries in NEWS.

     * NEWS: Restore accidentally deleted bug-fix entries.

https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=362b47fe09ca9a928d444c7e2f7992f7f61bfc3e

commit 362b47fe09ca9a928d444c7e2f7992f7f61bfc3e
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog | 11 +++++++++++
 NEWS | 23 ++++++++++++-----------
 malloc/malloc.c | 20 ++++++++++++--------
 3 files changed, 35 insertions(+), 19 deletions(-)

Fixed by the above commit.

Real credit goes to Josh Pieper, whose carefully prepared testcase made it possible to investigate and fix the bug.

Fixed on trunk only. I've pinged release managers to merge the fix to 2.15 onwards.

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, 2.15 has been created
        at 9875bb22212391e39d9d2c29b4b5d5e9e1f83beb (commit)

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=9875bb22212391e39d9d2c29b4b5d5e9e1f83beb

commit 9875bb22212391e39d9d2c29b4b5d5e9e1f83beb
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

    Conflicts:

     ChangeLog
     NEWS

-----------------------------------------------------------------------

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, 2.15 has been deleted
       was 9875bb22212391e39d9d2c29b4b5d5e9e1f83beb

- Log -----------------------------------------------------------------
9875bb22212391e39d9d2c29b4b5d5e9e1f83beb Fix race in free() of fastbin chunk: BZ #15073
-----------------------------------------------------------------------

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, release/2.15/master has been updated
       via 9875bb22212391e39d9d2c29b4b5d5e9e1f83beb (commit)
      from 53fa2b6063a484e19a6c48c4efff00a6491c0f4e (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=9875bb22212391e39d9d2c29b4b5d5e9e1f83beb

commit 9875bb22212391e39d9d2c29b4b5d5e9e1f83beb
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

    Conflicts:

     ChangeLog
     NEWS

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog | 7 +++++++
 NEWS | 2 +-
 malloc/malloc.c | 20 ++++++++++++--------
 3 files changed, 20 insertions(+), 9 deletions(-)

Fixed in 2.15.1

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, release/2.16/master has been updated
       via c972bcc9ebdb5c2601b6b34001c7450e7a0b5ea3 (commit)
      from 02eff8c4f82241c0843d47cb58c4355eb4f5d9e9 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=c972bcc9ebdb5c2601b6b34001c7450e7a0b5ea3

commit c972bcc9ebdb5c2601b6b34001c7450e7a0b5ea3
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

    Conflicts:

     ChangeLog
     NEWS

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog | 7 +++++++
 NEWS | 2 +-
 malloc/malloc.c | 20 ++++++++++++--------
 3 files changed, 20 insertions(+), 9 deletions(-)

Fixed in 2.16.1

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, release/2.17/master has been updated
       via 3db0119ef56decc402827d5b84774fa4487f6cd4 (commit)
      from 15256e58adc62d8d62c03b2b3ba526b468758702 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=3db0119ef56decc402827d5b84774fa4487f6cd4

commit 3db0119ef56decc402827d5b84774fa4487f6cd4
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

    Conflicts:

     ChangeLog
     NEWS

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog | 7 +++++++
 NEWS | 2 +-
 malloc/malloc.c | 20 ++++++++++++--------
 3 files changed, 20 insertions(+), 9 deletions(-)

Fixed in 2.17.1.

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The branch, release/2.18/master has been updated
       via 8b43a2274a593ce91e673db1cfac6e808134bc84 (commit)
      from ca0dd6386ed2b5c5c6ca392547628a1228432ae0 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
https://sourceware.org/git/gitweb.cgi?p=glibc.git;h=8b43a2274a593ce91e673db1cfac6e808134bc84

commit 8b43a2274a593ce91e673db1cfac6e808134bc84
Author: Maxim Kuvyrkov <email address hidden>
Date: Tue Dec 24 09:44:50 2013 +1300

    Fix race in free() of fastbin chunk: BZ #15073

    Perform sanity check only if we have_lock. Due to lockless nature of fastbins
    we need to be careful derefencing pointers to fastbin entries (chunksize(old)
    in this case) in multithreaded environments.

    The fix is to add have_lock to the if-condition checks. The rest of the patch
    only makes code more readable.

     * malloc/malloc.c (_int_free): Perform sanity check only if we
     have_lock.

    Conflicts:

     ChangeLog
     NEWS

-----------------------------------------------------------------------

Summary of changes:
 ChangeLog | 7 +++++++
 NEWS | 2 +-
 malloc/malloc.c | 20 ++++++++++++--------
 3 files changed, 20 insertions(+), 9 deletions(-)

Fixed on 2.18.1.

This is an automated email from the git hooks/post-receive script. It was
generated because a ref change was pushed to the repository containing
the project "GNU C Library master sources".

The annotated tag, glibc-2.19 has been created
        at 62acb0ba856abf4a2a173e4b49c28749af7bd572 (tag)
   tagging 9a869d822025be8e43b78234997b10bf0cf9d859 (commit)
  replaces glibc-2.18
 tagged by Allan McRae
        on Fri Feb 7 19:12:54 2014 +1000

- Log -----------------------------------------------------------------
The GNU C Library
=================

The GNU C Library version 2.19 is now available.

The GNU C Library is used as *the* C library in the GNU systems
and most systems with the Linux kernel.

The GNU C Library is primarily designed to be a portable
and high performance C library. It follows all relevant
standards including ISO C11 and POSIX.1-2008. It is also
internationalized and has one of the most complete
internationalization interfaces known.

The GNU C Library webpage is at http://www.gnu.org/software/libc/

Packages for the 2.19 release may be downloaded from:
        http://ftpmirror.gnu.org/libc/
        http://ftp.gnu.org/gnu/libc/

The mirror list is at http://www.gnu.org/order/ftp.html

NEWS for version 2.19
=====================

* The following bugs are resolved with this release:

  156, 387, 431, 762, 832, 926, 2801, 4772, 6786, 6787, 6807, 6810, 6981,
  7003, 9721, 9954, 10253, 10278, 11087, 11157, 11214, 12100, 12486, 12751,
  12986, 13028, 13982, 13985, 14029, 14032, 14120, 14143, 14155, 14286,
  14547, 14699, 14752, 14782, 14876, 14910, 15004, 15048, 15073, 15089,
  15128, 15218, 15268, 15277, 15308, 15362, 15374, 15400, 15425, 15427,
  15483, 15522, 15531, 15532, 15593, 15601, 15608, 15609, 15610, 15632,
  15640, 15670, 15672, 15680, 15681, 15723, 15734, 15735, 15736, 15748,
  15749, 15754, 15760, 15763, 15764, 15797, 15799, 15825, 15843, 15844,
  15846, 15847, 15849, 15850, 15855, 15856, 15857, 15859, 15867, 15886,
  15887, 15890, 15892, 15893, 15895, 15897, 15901, 15905, 15909, 15915,
  15917, 15919, 15921, 15923, 15939, 15941, 15948, 15963, 15966, 15968,
  15985, 15988, 15997, 16032, 16034, 16036, 16037, 16038, 16041, 16046,
  16055, 16071, 16072, 16074, 16077, 16078, 16103, 16112, 16143, 16144,
  16146, 16150, 16151, 16153, 16167, 16169, 16172, 16195, 16214, 16245,
  16271, 16274, 16283, 16289, 16293, 16314, 16316, 16330, 16337, 16338,
  16356, 16365, 16366, 16369, 16372, 16375, 16379, 16384, 16385, 16386,
  16387, 16390, 16394, 16398, 16400, 16407, 16408, 16414, 16430, 16431,
  16453, 16474, 16506, 16510, 16529

* Slovenian translations for glibc messages have been contributed by the
  Translation Project's Slovenian team of translators.

* The public headers no longer use __unused nor __block. This change is to
  support compiling programs that are derived from BSD sources and use
  __unused internally, and to support compiling with Clang's -fblock
  extension which uses __block.

* CVE-2012-4412 The strcoll implementation caches indices and rules for
  large collation sequences to optimize multiple passes. This cache
  computation may overflow for large collation sequences and may cause a
  stack or b...