[Bug malloc/19048] New: Avoid corruption of free_list

[Bug malloc/19048] New: Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

            Bug ID: 19048
           Summary: Avoid corruption of free_list
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: malloc
          Assignee: unassigned at sourceware dot org
          Reporter: paulo.cesar.pereira.de.andrade at gmail dot com
  Target Milestone: ---

Created attachment 8666
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8666&action=edit
0001-Avoid-corruption-of-free_list.patch

When a thread leaves, arena_thread_freeres is called, the malloc
arena associated with the thread is added to the head of free_list,
and free_list set to the arena of the exiting thread.

  A common problem can be described as:
1. thread "t1" uses arena "a"
2. thread "t2" uses arena "a"
3. "t1" exit, making:
        a->next_free = free_list;
        free_list = a;
4. "t2" exits, but since free_list == a, it ends with
   free_list->next_free = free_list;

  When a program has several short lived threads, and most commonly
when there are more threads than arenas, one arena will end up being
used by most threads, causing significant contention.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #1 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8667
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8667&action=edit
arena_test.c

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #2 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8668
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8668&action=edit
arena_test.pl

arena_test.c creates several threads in a loop:

2 threads for 32 sec
4 threads for 16 sec
8 threads for 8 sec
16 threads for 4 sec
32 threads for 2 sec
64 threads for 1 sec

every thread allocates some memory. When a thread leaves,
it attaches gdb and reads the value of the arena "key",
__libc_tsd_MALLOC for every thread, using arena_test.pl,
and prints a summary for every loop.

It shows that the proposed patch better distributes the
arenas among threads, while current glibc, and older versions,
at least as of the original commit in 2009 creating
arena_thread_freeres will use the same arena for most
threads.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #3 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8669
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8669&action=edit
test.c

This is an alternate test case (older, from before detecting
the actual problem), that also shows how the patch makes a
significant difference.

Sample usage of this alternate test case:

$ gcc -pthread test.c -o test
$ ./test 1000 10000 1000 10

will cause all passes to run very slowly, while:

$ MALLOC_ARENA_MAX=1000 ./test 1000 10000 1000 10

allocating one arena per thread, will only be slow
in the first pass, but, with the proposed patch, it
is "fast" in all passes.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #4 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
  I have an alternate patch, using/updating where
applicable, a global "tail" pointer, but I prefer the
simpler, proposed one, as it is very unlikely to have
unexpected side effects, while the other needs to handle
free_list (re)construction after or during fork, and may
have other side effects that I could not think of.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #8666|0                           |1
        is obsolete|                            |

--- Comment #5 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8672
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8672&action=edit
0001-Avoid-corruption-of-free_list.patch

Patch updated to make sure to not "break" the linked list,
and corrupt free_list in a patch to avoid (other) corruption...

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #8672|0                           |1
        is obsolete|                            |

--- Comment #6 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8674
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8674&action=edit
0001-Avoid-corruption-of-free_list.patch

Also properly handle the case of the arena associated
with the exiting thread already being the head of free_list.

The idea is to put the arena as last to be reused, in
a round robin manner. Other more complex "scheduling"
could be implemented, but could require maintaining a
reference counter of arenas, increased when set as
thread arena, reset when unset as thread arena, or
thread exits.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fweimer at redhat dot com

--- Comment #7 from Florian Weimer <fweimer at redhat dot com> ---
Can you clarify if you mean “corruption” or “contention”?  These two are very
different things.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
>From glibc-bugs-return-30069-listarch-glibc-bugs=sources.redhat.com@sourceware.org Wed Oct 07 18:06:46 2015
Return-Path: <glibc-bugs-return-30069-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Delivered-To: listarch-glibc-bugs@sources.redhat.com
Received: (qmail 87567 invoked by alias); 7 Oct 2015 18:06:46 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Delivered-To: mailing list glibc-bugs@sourceware.org
Received: (qmail 87522 invoked by uid 48); 7 Oct 2015 18:06:43 -0000
From: "carlos at redhat dot com" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sourceware.org
Subject: [Bug manual/19086] New: posix_fallocate64 documented argument order is wrong.
Date: Wed, 07 Oct 2015 18:06:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: new
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: glibc
X-Bugzilla-Component: manual
X-Bugzilla-Version: unspecified
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: carlos at redhat dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at sourceware dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: bug_id short_desc product version bug_status bug_severity priority component assigned_to reporter cc target_milestone
Message-ID: <bug-19086-131@http.sourceware.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-10/txt/msg00106.txt.bz2
Content-length: 901

https://sourceware.org/bugzilla/show_bug.cgi?id\x19086

            Bug ID: 19086
           Summary: posix_fallocate64 documented argument order is wrong.
           Product: glibc
           Version: unspecified
            Status: NEW
          Severity: normal
          Priority: P2
         Component: manual
          Assignee: unassigned at sourceware dot org
          Reporter: carlos at redhat dot com
                CC: mtk.manpages at gmail dot com, roland at gnu dot org
  Target Milestone: ---

The manual/filesys.texi lists posix_fallocate64 as having the following
prototype:

int posix_fallocate64 (int @var{fd}, off64_t @var{length}, off64_t
@var{offset})

Which is wrong. It should be:

int posix_fallocate64 (int @var{fd}, off64_t @var{offset}, off64_t
@var{length})

(offset and length are swapped).

--
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at sourceware dot org   |fweimer at redhat dot com

--- Comment #8 from Florian Weimer <fweimer at redhat dot com> ---
(In reply to Florian Weimer from comment #7)
> Can you clarify if you mean “corruption” or “contention”?  These two are
> very different things.

Disregard that, its corruption which leads to contention.

I looked at the downstream bug report (rhbz#1264189), and it is now clear that
free_list (in malloc/arena.c) is corrupted.  It eventually turns into a
circular list, instead of being a stack.  Once this happens, the code that
should pop an element from the stack in get_free_list keeps returning the same
arena again and again.

arena_thread_freeres makes free_list circular if the same arena is pushed on
the stack again because the next pointer is overwritten.  This can happen if
threads share the same arena.

I think we need to go the arena reference counter route and push the arena on
the stack only if the reference counter hits zero.  list_lock is global, so we
should avoid doing a list traversal while holding it.

I don't think this is a correctness issue.  Observed malloc behavior is still
compliant, it's just much slower than it could be.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
>From glibc-bugs-return-30082-listarch-glibc-bugs=sources.redhat.com@sourceware.org Thu Oct 08 16:45:40 2015
Return-Path: <glibc-bugs-return-30082-listarch-glibc-bugs=sources.redhat.com@sourceware.org>
Delivered-To: listarch-glibc-bugs@sources.redhat.com
Received: (qmail 2230 invoked by alias); 8 Oct 2015 16:45:40 -0000
Mailing-List: contact glibc-bugs-help@sourceware.org; run by ezmlm
Precedence: bulk
List-Id: <glibc-bugs.sourceware.org>
List-Subscribe: <mailto:glibc-bugs-subscribe@sourceware.org>
List-Post: <mailto:glibc-bugs@sourceware.org>
List-Help: <mailto:glibc-bugs-help@sourceware.org>, <http://sourceware.org/lists.html#faqs>
Sender: glibc-bugs-owner@sourceware.org
Delivered-To: mailing list glibc-bugs@sourceware.org
Received: (qmail 2166 invoked by uid 48); 8 Oct 2015 16:45:36 -0000
From: "carlos at redhat dot com" <sourceware-bugzilla@sourceware.org>
To: glibc-bugs@sourceware.org
Subject: [Bug locale/18589] sort-test.sh fails at random
Date: Thu, 08 Oct 2015 16:45:00 -0000
X-Bugzilla-Reason: CC
X-Bugzilla-Type: changed
X-Bugzilla-Watch-Reason: None
X-Bugzilla-Product: glibc
X-Bugzilla-Component: locale
X-Bugzilla-Version: unspecified
X-Bugzilla-Keywords:
X-Bugzilla-Severity: normal
X-Bugzilla-Who: carlos at redhat dot com
X-Bugzilla-Status: NEW
X-Bugzilla-Resolution:
X-Bugzilla-Priority: P2
X-Bugzilla-Assigned-To: unassigned at sourceware dot org
X-Bugzilla-Target-Milestone: ---
X-Bugzilla-Flags:
X-Bugzilla-Changed-Fields: cc
Message-ID: <bug-18589-131-LepwqzNiVs@http.sourceware.org/bugzilla/>
In-Reply-To: <bug-18589-131@http.sourceware.org/bugzilla/>
References: <bug-18589-131@http.sourceware.org/bugzilla/>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 7bit
X-Bugzilla-URL: http://sourceware.org/bugzilla/
Auto-Submitted: auto-generated
MIME-Version: 1.0
X-SW-Source: 2015-10/txt/msg00119.txt.bz2
Content-length: 715

https://sourceware.org/bugzilla/show_bug.cgi?id\x18589

Carlos O'Donell <carlos at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |carlos at redhat dot com

--- Comment #3 from Carlos O'Donell <carlos at redhat dot com> ---
We've had another report of this in Fedora for cs_CZ. Reverting the patch fixes
hte issue. I'm going to revert the patch in master and checkin a regression
test (bug-strcoll2.c) which captures the failure and should give Leonhard
something to work wtih.

--
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[paulo.cesar.pereira.de.andrade at gmail dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #9 from Paulo Andrade <paulo.cesar.pereira.de.andrade at gmail dot com> ---
Created attachment 8700
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8700&action=edit
glibc-arena.patch

Alternate simpler patch (from a test rpm build) that that makes
the exiting thread arena the free_list, like in current glibc,
with the following checks:

o if the thread arena it is already free_list do nothing
o if the thread arena is in free_list remove it

After the above checks, do as current glibc, making the arena
the first one to be reused.

The previous patch did put the exiting thread arena at the tail
of the free_list, the new one puts it in the head, and, in the
common case of it already being in free_list, exits early the
traversal, as it should be at most once in the list.

The speed improvement, with either patch makes some tests run
more than 100 times faster, making glibc malloc speed comparable
to jemallc (that was the user complaint, jemalloc running 100
times faster than glibc).

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] Avoid corruption of free_list

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #10 from Florian Weimer <fweimer at redhat dot com> ---
I posted a completely different patch which avoids the list traversal (and
allows us to return arenas to free_list before thread exit if we want to make
that optimization):

<https://sourceware.org/ml/libc-alpha/2015-10/msg00270.html>

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: Avoid corruption of free_list

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Avoid corruption of         |malloc: Avoid corruption of
                   |free_list                   |free_list

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: Avoid corruption of free_list

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #11 from Florian Weimer <fweimer at redhat dot com> ---
Created attachment 8718
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8718&action=edit
check-free_list.sh

Test script which examines a running process to see if its arena free list has
become cyclic.

Usage:

$ bash 5995 6984
5995 no cycle
6984 CYCLE

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|malloc: Avoid corruption of |malloc: arena free list can
                   |free_list                   |become cyclic, increasing
                   |                            |contention

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #8718|application/x-shellscript   |text/plain
          mime type|                            |

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Attachment #8718|0                           |1
        is obsolete|                            |

--- Comment #12 from Florian Weimer <fweimer at redhat dot com> ---
Created attachment 8719
  --> https://sourceware.org/bugzilla/attachment.cgi?id=8719&action=edit
check-free_list.sh

New script which adds a check for availability of glibc debugging information.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[cvs-commit at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

--- Comment #13 from cvs-commit at gcc dot gnu.org <cvs-commit at gcc dot gnu.org> ---
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  a62719ba90e2fa1728890ae7dc8df9e32a622e7b (commit)
      from  0b9af583a5c2d68085e88cece13952bf05dc4882 (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=a62719ba90e2fa1728890ae7dc8df9e32a622e7b

commit a62719ba90e2fa1728890ae7dc8df9e32a622e7b
Author: Florian Weimer <fweimer@redhat.com>
Date:   Wed Oct 28 19:32:46 2015 +0100

    malloc: Prevent arena free_list from turning cyclic [BZ #19048]

        [BZ# 19048]
        * malloc/malloc.c (struct malloc_state): Update comment.  Add
        attached_threads member.
        (main_arena): Initialize attached_threads.
        * malloc/arena.c (list_lock): Update comment.
        (ptmalloc_lock_all, ptmalloc_unlock_all): Likewise.
        (ptmalloc_unlock_all2): Reinitialize arena reference counts.
        (deattach_arena): New function.
        (_int_new_arena): Initialize arena reference count and deattach
        replaced arena.
        (get_free_list, reused_arena): Update reference count and deattach
        replaced arena.
        (arena_thread_freeres): Update arena reference count and only put
        unreferenced arenas on the free list.

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

Summary of changes:
 ChangeLog       |   17 +++++++++++++
 NEWS            |   15 +++++++++--
 malloc/arena.c  |   70 +++++++++++++++++++++++++++++++++++++++++++++++++++----
 malloc/malloc.c |   11 +++++++-
 4 files changed, 103 insertions(+), 10 deletions(-)

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[fweimer at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #14 from Florian Weimer <fweimer at redhat dot com> ---
Fixed in 2.23.

-- 
You are receiving this mail because:
You are on the CC list for the bug.

[Bug malloc/19048] malloc: arena free list can become cyclic, increasing contention

[jsm28 at gcc dot gnu.org]

https://sourceware.org/bugzilla/show_bug.cgi?id=19048

Joseph Myers <jsm28 at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |2.23

-- 
You are receiving this mail because:
You are on the CC list for the bug.