[Bug malloc/15089] New: malloc_trim always trims for large padding

[Bug malloc/15089] New: malloc_trim always trims for large padding

[izetip at yahoo dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15089

             Bug #: 15089
           Summary: malloc_trim always trims for large padding
           Product: glibc
           Version: 2.18
            Status: NEW
          Severity: normal
          Priority: P2
         Component: malloc
        AssignedTo: unassigned@sourceware.org
        ReportedBy: izetip@yahoo.com
    Classification: Unclassified


If you call malloc_trim() with a large enough padding, then an error with how
signed/unsigned arithmetic is handled will cause that large padding to actually
have the same effect as specifying no padding.  This is a problem since
malloc_trim() then becomes overly aggressive and hurts performance.

The bug is in systrim().  Here's the current code:
1236 #define MINSIZE  \
1237   (unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) &
~MALLOC_ALIGN_MASK))
....
2707 static int systrim(size_t pad, mstate av)
2708 {
2709   long  top_size;        /* Amount of top-most memory */
2710   long  extra;           /* Amount to release */
...
2714   size_t pagesz;
2715 
2716   pagesz = GLRO(dl_pagesize);
2717   top_size = chunksize(av->top);
2718 
2719   /* Release in pagesize units, keeping at least one page */
2720   extra = (top_size - pad - MINSIZE - 1) & ~(pagesz - 1);
2721 
2722   if (extra > 0) {
...       MORECORE(-extra); ends up being called

Notice that pad and pagesz are of type size_t and MINSIZE is unsigned long, all
of these are unsigned while the other variables are signed.  When computing
extra, the first operation is:
   top_size - pad
this is  (long) - (size_t) and the result is automatically promoted to size_t
-- which is unsigned.  So if pad > top_size, then while the expected result is
that subtracting the two would be negative, the actual result is that it
becomes an extremely large positive value.  Every single following operation
will continue to be promoted to the unsigned size_t.  This means extra will
always be greater than or equal to 0.

Here's an example that shows how the wrong result is produced. If top_size=128
and pad=512, we would expect extra to be negative and no memory to be trimmed
(also, with 128 bytes, we have less than a page left, so that's another reason
we are not supposed to trim regardless of what pad is set to).  Instead we get:
(gdb) p (((long) 128) - (unsigned long)(512) - ((unsigned long)8) - 1) &
~(((unsigned long)4096)-1)
$1 = 4294963200

extra is positive and so we enter the if statement and will likely erroneously
call MORECORE(-4294963200).

What we wanted is something more like:
(gdb) p (((long) 128) - (long)(512) - ((long)8) - 1) & ~(((long)4096)-1)
$2 = -4096

To be truly robust, the fix should handle the situation where pad > 1LL<<62 in
case someone decides they want to disable trimming by setting pad to something
like (size_t)-1.  Something like the following would probably work:
  long x = top_size - ((long)MINSIZE) - 1;
  extra = x <= pad? -1 : (x - ((long)pad)) & ~(pagesz - 1);

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug malloc/15089] malloc_trim always trims for large padding

[izetip at yahoo dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15089

--- Comment #1 from Thiago Ize <izetip at yahoo dot com> 2013-01-31 18:12:43 UTC ---
Noticed small mistake in my explanation for the fix, it's not
  pad > 1LL<<62
but of course
  pad >= 1ULL<<63
or put another way, whenever making pad signed causes it to become negative.

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug malloc/15089] malloc_trim always trims for large padding

[izetip at yahoo dot com]

http://sourceware.org/bugzilla/show_bug.cgi?id=15089

--- Comment #2 from Thiago Ize <izetip at yahoo dot com> 2013-02-01 23:55:45 UTC ---
I didn't realize that when the result is converted to a long that it would give
the correct signed result (most of the time).  Shame on me.  However, I still
detect it doing the wrong thing for very large pad sizes, such as (size_t)-1,
combined with when there are more than 1 pages that can be released.  I wrote a
little test program to make sure this time:

      const size_t pagesz = 4096;
      const size_t MINSIZE = 8;

      long top_size = 12800;
      size_t pad = -1;

      long extra_bad = (top_size - pad - MINSIZE - 1) & ~(pagesz - 1);

      long x = top_size - ((long)MINSIZE) - 1;
      long good_extra = x <= pad? -1 : (x - ((long)pad)) & ~(pagesz - 1);

      printf("top_size: %ld pad:%zu gives %ld %ld\n", top_size, pad,
good_extra, extra_bad);

It returns:
    top_size: 12800 pad:18446744073709551615 gives -1 12288
So clearly in this case it's doing the wrong thing.

Finally, just to prove this happens in the actual glibc code, here's a gdb
output from CentOS 6 (glibc 2.12) that shows extra is positive even though pad
> top_size:

Breakpoint 2, sYSTRIm (s=18446744073709551615) at malloc.c:3475
3475      if (extra > 0) {
3: pad = 18446744073709551615
2: extra = 12288
1: top_size = 13536

-- 
Configure bugmail: http://sourceware.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are on the CC list for the bug.

[Bug malloc/15089] malloc_trim always trims for large padding

[fernandojvdasilva at gmail dot com]

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

Fernando J V da Silva <fernandojvdasilva at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |fernandojvdasilva at gmail dot com

--- Comment #3 from Fernando J V da Silva <fernandojvdasilva at gmail dot com> ---
I've also noticed this bug. I wrote another test program that can also
demonstrate it. In this test program one can see the memory is reduced to 4096
(1 page) when pad = MAX_SIZET, which shouldn't happen according to
malloc_trim's docs, as previously stated by Thiago Ize. The problem seems to
happen when pad is any value that would be negative when implicitly cast to
long inside systrim "extra" variable calculation. So if someone changes this
program to assign a smaller value to pad -- say pad = MAX_SIZET / 2 -- then the
problem doesn't happen since the heap is kept the same after calling
malloc_trim, as expected.

#include <stdio.h>
#include <malloc.h>

#define MAX_SIZET (~(size_t)0)

int main(int argc, char **argv) 
{
  char *p1;
  size_t pad;

  printf("Allocating 100k\n");
  p1 = malloc(100000);
  malloc_stats();

  printf("\nNow freeing 100k\n");
  free(p1);
  malloc_stats();

  pad = MAX_SIZET;

  printf("\nNow calling malloc_trim, pad=%p\n", pad);
  malloc_trim(pad);
  malloc_stats();
}

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

[Bug malloc/15089] malloc_trim always trims for large padding

[cvs-commit at gcc dot gnu.org]

http://sourceware.org/bugzilla/show_bug.cgi?id=15089

--- Comment #4 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  4b5b548c9fedd5e6d920639e42ea8e5f473c4de3 (commit)
      from  0a3ac0aabf30f6fefb4d262bf2db2c2a99ab09a8 (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=4b5b548c9fedd5e6d920639e42ea8e5f473c4de3

commit 4b5b548c9fedd5e6d920639e42ea8e5f473c4de3
Author: Fernando J. V. da Silva <fernandojvdasilva@gmail.com>
Date:   Fri Dec 6 18:04:10 2013 +0100

    Fix BZ #15089: malloc_trim always trim for large padding.

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

Summary of changes:
 ChangeLog       |    5 +++
 NEWS            |   20 +++++++-------
 malloc/malloc.c |   76 ++++++++++++++++++++++++++++--------------------------
 3 files changed, 54 insertions(+), 47 deletions(-)

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

[Bug malloc/15089] malloc_trim always trims for large padding

[neleai at seznam dot cz]

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

Ondrej Bilka <neleai at seznam dot cz> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
                 CC|                            |neleai at seznam dot cz
         Resolution|---                         |FIXED

--- Comment #5 from Ondrej Bilka <neleai at seznam dot cz> ---
Fixed.

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

[Bug malloc/15089] malloc_trim always trims for large padding

[fweimer at redhat dot com]

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

Florian Weimer <fweimer at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
              Flags|                            |security-

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

[Bug malloc/15089] malloc_trim always trims for large padding

[cvs-commit at gcc dot gnu.org]

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

--- Comment #7 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  51a7380b8968251a49a4c5b0bc7ed1af5b0512c6 (commit)
      from  91b84fe588238289e734ee05cfff26482c8f56ac (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=51a7380b8968251a49a4c5b0bc7ed1af5b0512c6

commit 51a7380b8968251a49a4c5b0bc7ed1af5b0512c6
Author: Will Newton <will.newton@linaro.org>
Date:   Fri Jun 13 16:37:12 2014 +0100

    malloc/malloc.c: Avoid calling sbrk unnecessarily with zero

    Due to my bad review suggestion for the fix for BZ #15089 a check
    was removed from systrim to prevent sbrk being called with a zero
    argument. Add the check back to avoid this useless work.

    ChangeLog:

    2014-06-19  Will Newton  <will.newton@linaro.org>

        * malloc/malloc.c (systrim): If extra is zero then return
        early.

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

Summary of changes:
 ChangeLog       |    5 +++++
 malloc/malloc.c |    3 +++
 2 files changed, 8 insertions(+), 0 deletions(-)

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