[PATCH] [BZ 20628] make mallinfo saturating

[PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

The mallinfo() API is fixed as "int" even though on 64-bit systems,
where size_t is bigger than int, these can overflow.  The man pages
document this behavior.  The API cannot be changed.  However, this
patch changes the "returns incorrect values" case from overflowing to
saturation, so that the bogus values are easily spotted as 0x7fffffff
(INT_MAX in that case) instead of being an arbitrary (possibly
"reasonable") overflowed value.

A demonstration case is included in this email (and the bz, with
output), but as testing it requires at least 2 Gb of free memory, I
have not included a test case in the source tree at this time.

Built and tested with no new warnings or failures on both Fedora 20
and rawhide (no surprise, no tests test mallinfo()) on x86_64.

Man page change: After "However, because some internal bookkeeping
values may be of type long, the reported values may wrap around zero
and thus be inaccurate." add "In versions of glibc after X.YY, the
reported values will saturate at INT_MAX instead of overflowing."

Related BZs:
3973 - malloc_stats/struct mallinfo is not 64bits ready (WONTFIX)
5711 - mallinfo structure cannot hold 64 bit data (WONTFIX)

2016-09-27  DJ Delorie  <dj@delorie.com>

	[BZ #20628]
	* malloc/malloc.c (int_mallinfo): Use saturating add instead of
	overflow to collect statistics into a fixed "int" container.

-------------------- mallinfo-overflow-demo.c
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

void
print_stats ()
{
  struct mallinfo m = mallinfo ();
  printf("Malloc stats...\n");
#define F(x) printf("%-8s 0x%08x %d\n", #x, m.x, m.x);
  F(arena);
  F(ordblks);
  F(smblks);
  F(hblks);
  F(hblkhd);
  F(usmblks);
  F(fsmblks);
  F(uordblks);
  F(fordblks);
  F(keepcost);
}

int
main()
{
  int i;
  print_stats ();
  for (i=0; i<0x22345678; i++)
    malloc (0x10);
  print_stats ();
}
--------------------

$ ./mallinfo-overflow-demo 
Malloc stats...
arena    0x00000000 0
...
uordblks 0x00000000 0
Malloc stats...
arena    0x468b0000 1183514624
...
uordblks 0x468acf00 1183502080
...

$ ~/tools/upstream/glibc.mallinfo.build/testrun.sh ./mallinfo-overflow-demo
Malloc stats...
arena    0x00000000 0
...
uordblks 0x00000000 0
...
Malloc stats...
arena    0x7fffffff 2147483647
...
uordblks 0x7fffffff 2147483647
...

--------------------
diff --git a/malloc/malloc.c b/malloc/malloc.c
index ef04360..4f438ef 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -224,6 +224,7 @@
 #include <unistd.h>
 #include <stdio.h>    /* needed for malloc_stats */
 #include <errno.h>
+#include <limits.h>
 
 #include <shlib-compat.h>
 
@@ -4633,18 +4634,29 @@ int_mallinfo (mstate av, struct mallinfo *m)
         }
     }
 
-  m->smblks += nfastblocks;
-  m->ordblks += nblocks;
-  m->fordblks += avail;
-  m->uordblks += av->system_mem - avail;
-  m->arena += av->system_mem;
-  m->fsmblks += fastavail;
+/* Saturated add - add ADD to SUM.  If the result exceeds the range of
+   "int", set SUM to INT_MAX instead.  Assumes ADD and SUM are
+   positive.  The published ABI prevents us from bumping "int" to a
+   larger type.  */
+#define SAT_ADD(SUM, ADD) \
+  ({ INTERNAL_SIZE_T tmp = (INTERNAL_SIZE_T)(SUM) + (INTERNAL_SIZE_T)(ADD); SUM = (tmp > INT_MAX) ? INT_MAX : tmp; })
+
+/* Likewise, but assign ADD to SUM.  */
+#define SAT_SET(SUM, ADD) \
+  ({ SUM = ((INTERNAL_SIZE_T)(ADD) > INT_MAX) ? INT_MAX : (ADD); })
+
+  SAT_ADD (m->smblks, nfastblocks);
+  SAT_ADD (m->ordblks, nblocks);
+  SAT_ADD (m->fordblks, avail);
+  SAT_ADD (m->uordblks, av->system_mem - avail);
+  SAT_ADD (m->arena, av->system_mem);
+  SAT_ADD (m->fsmblks, fastavail);
   if (av == &main_arena)
     {
-      m->hblks = mp_.n_mmaps;
-      m->hblkhd = mp_.mmapped_mem;
-      m->usmblks = 0;
-      m->keepcost = chunksize (av->top);
+      SAT_SET (m->hblks, mp_.n_mmaps);
+      SAT_SET (m->hblkhd, mp_.mmapped_mem);
+      SAT_SET (m->usmblks, 0);
+      SAT_SET (m->keepcost, chunksize (av->top));
     }
 }
 

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Paul Eggert]

It would be more backward-compatible to represent minor overflows as 
negative numbers that are equivalent to the correct answers modulo 
(UINT_MAX + 1). That way, callers can continue to retrieve the correct 
values by casting int to unsigned. The code can use -1 to represent a 
value greater than UINT_MAX. This all should be doable just as 
efficiently as the proposed patch.

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

I considered that, but given that a 64-bit address space wraps "int" 4
billion times, I doubt allowing unsigned conversions adds much value.  I
chose INT_MAX because it's still "biggest" of the valid ABI-compliant
return values.  The ABI is broken anyway on 64-bit size_t systems, I
think the only real value in this type of patch is making sure the user
knows the value is "wrong", rather than trying to return useful data.

But yeah, just as easy to do it either way.  I'll get some popcorn and
let you regulars argue it out :-)

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Carlos O'Donell]

On 09/27/2016 03:07 PM, Paul Eggert wrote:
> It would be more backward-compatible to represent minor overflows as
> negative numbers that are equivalent to the correct answers modulo
> (UINT_MAX + 1). That way, callers can continue to retrieve the
> correct values by casting int to unsigned. The code can use -1 to
> represent a value greater than UINT_MAX. This all should be doable
> just as efficiently as the proposed patch.
 
Agreed, I had not considered that case. It would certainly make the
interface as useful as it could be with a 32-bit address space, but
it would still be mostly useless on a 64-bit system (even with 48-bit VA).

I just double checked that C11 does continue to contain the clause
that allows the conversion to work:
~~~
6.3.1.3
Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or
subtracting one more than the maximum value that can be represented in the new type
until the value is in the range of the new type.60)
60) The rules describe arithmetic on the mathematical value, not the value of a given type of expression.
~~~

This way you could cast the values to 'unsigned int' and know you had
a valid result as long as it was less than '(unsigned int)-1' (reserved
for overflow).

DJ, Care to make a version 2 of the patch?

-- 
Cheers,
Carlos.

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

"Carlos O'Donell" <carlos@redhat.com> writes:
> DJ, Care to make a version 2 of the patch?

Version 2.  Changed some of the counters to larger types and tested those
too, which took about 130Gb of virtual memory and lots of waiting...

	[BZ #20628]
	* malloc/malloc.c (int_mallinfo): Use saturating add instead of
	overflow to collect statistics into a fixed "int" container.

diff --git a/malloc/malloc.c b/malloc/malloc.c
index ef04360..e3f4693 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -224,6 +224,7 @@
 #include <unistd.h>
 #include <stdio.h>    /* needed for malloc_stats */
 #include <errno.h>
+#include <limits.h>
 
 #include <shlib-compat.h>
 
@@ -4594,8 +4595,8 @@ int_mallinfo (mstate av, struct mallinfo *m)
   mchunkptr p;
   INTERNAL_SIZE_T avail;
   INTERNAL_SIZE_T fastavail;
-  int nblocks;
-  int nfastblocks;
+  INTERNAL_SIZE_T nblocks;
+  INTERNAL_SIZE_T nfastblocks;
 
   /* Ensure initialization */
   if (av->top == 0)
@@ -4633,18 +4634,29 @@ int_mallinfo (mstate av, struct mallinfo *m)
         }
     }
 
-  m->smblks += nfastblocks;
-  m->ordblks += nblocks;
-  m->fordblks += avail;
-  m->uordblks += av->system_mem - avail;
-  m->arena += av->system_mem;
-  m->fsmblks += fastavail;
+/* Saturated add - add ADD to SUM.  If the result exceeds the range of
+   "int", set SUM to UINT_MAX instead ((int)-1).  Assumes ADD and SUM
+   are positive.  The published ABI prevents us from bumping "int" to
+   a larger type.  */
+#define SAT_ADD(SUM, ADD) \
+  ({ INTERNAL_SIZE_T tmp = (INTERNAL_SIZE_T)(SUM) + (INTERNAL_SIZE_T)(ADD); SUM = (tmp > UINT_MAX) ? -1 : tmp; })
+
+/* Likewise, but assign ADD to SUM.  */
+#define SAT_SET(SUM, ADD) \
+  ({ SUM = ((INTERNAL_SIZE_T)(ADD) > UINT_MAX) ? -1 : (ADD); })
+
+  SAT_ADD (m->smblks, nfastblocks);
+  SAT_ADD (m->ordblks, nblocks);
+  SAT_ADD (m->fordblks, avail);
+  SAT_ADD (m->uordblks, av->system_mem - avail);
+  SAT_ADD (m->arena, av->system_mem);
+  SAT_ADD (m->fsmblks, fastavail);
   if (av == &main_arena)
     {
-      m->hblks = mp_.n_mmaps;
-      m->hblkhd = mp_.mmapped_mem;
-      m->usmblks = 0;
-      m->keepcost = chunksize (av->top);
+      SAT_SET (m->hblks, mp_.n_mmaps);
+      SAT_SET (m->hblkhd, mp_.mmapped_mem);
+      SAT_SET (m->usmblks, 0);
+      SAT_SET (m->keepcost, chunksize (av->top));
     }
 }
 

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Paul Eggert]

On 10/04/2016 01:04 PM, DJ Delorie wrote:
> +/* Saturated add - add ADD to SUM.  If the result exceeds the range of
> +   "int", set SUM to UINT_MAX instead ((int)-1).  Assumes ADD and SUM
> +   are positive.  The published ABI prevents us from bumping "int" to
> +   a larger type.  */
> +#define SAT_ADD(SUM, ADD) \
> +  ({ INTERNAL_SIZE_T tmp = (INTERNAL_SIZE_T)(SUM) + (INTERNAL_SIZE_T)(ADD); SUM = (tmp > UINT_MAX) ? -1 : tmp; })
> +
> +/* Likewise, but assign ADD to SUM.  */
> +#define SAT_SET(SUM, ADD) \
> +  ({ SUM = ((INTERNAL_SIZE_T)(ADD) > UINT_MAX) ? -1 : (ADD); })
These don't look right, as INTERNAL_SIZE_T might not be wider than int, 
which means the + in SAT_ADD will wrap around before SAT_ADD gets a 
chance to check for overflow. Also, if SUM is INT_MIN then SAT_ADD(SUM, 
1) should set it to INT_MIN + 1, but that doesn't happen when 
INTERNAL_SIZE_T is wider than int.

How about something like the following instead?

   #define MIN(a, b) ((a)<(b)?(a):(b))

   /* Return the sum of the unsigned int A and the nonnegative integer B.
      If the result is not representable as an unsigned int, return 
UINT_MAX.
      B's type may be any integer type.  */
   #define UINT_SATURATED_ADD(a, b) \
      ({ unsigned a1 = a, b1 = MIN (b, UINT_MAX), sum1 = a1 + b1; \
         sum1 < a1 ? UINT_MAX : sum1; })

and then set 'm->smblks = UINT_SATURATED_ADD (m->sm_blks, nfastblocks);' 
and 'm->hblks = UINT_SATURATED_ADD (0, mp_.n_mmaps);', etc.

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

Paul Eggert <eggert@cs.ucla.edu> writes:
> These don't look right, as INTERNAL_SIZE_T might not be wider than int, 

In which case, the values we're adding up won't overflow because memory
is limited to an int-sized address space.

> Also, if SUM is INT_MIN

"Assumes ADD and SUM are positive."

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Paul Eggert]

DJ Delorie wrote:
> Paul Eggert <eggert@cs.ucla.edu> writes:
>> These don't look right, as INTERNAL_SIZE_T might not be wider than int,
>
> In which case, the values we're adding up won't overflow because memory
> is limited to an int-sized address space.

I don't see how that follows. If INTERNAL_SIZE_T and int are both 32 bits, then 
(INTERNAL_SIZE_T)(SUM) + (INTERNAL_SIZE_T)(ADD) is a 32-bit unsigned addition. 
This addition can overflow and wrap around, but the code doesn't check for that 
overflow.

>> Also, if SUM is INT_MIN
>
> "Assumes ADD and SUM are positive."

That assumption is incorrect, since SUM can be INT_MIN after a wraparound overflow.

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

Paul Eggert <eggert@cs.ucla.edu> writes:
> I don't see how that follows. If INTERNAL_SIZE_T and int are both 32
> bits, then (INTERNAL_SIZE_T)(SUM) + (INTERNAL_SIZE_T)(ADD) is a 32-bit
> unsigned addition.  This addition can overflow and wrap around, but
> the code doesn't check for that overflow.

I'm not arguing that the logic handles it, I'm arguing that with a
32-bit memory space none of the values will "happen" to cause an
overflow, because we never have more than 2^32 bytes of memory or 2^32
objects to count.  I.e. overflow would only happen in the case where the
logic handles it properly.  I'll add a comment to this effect, unless
you're arguing that the macro should be more general-purpose, which we
can argue in an independent context if you wish.

>>> Also, if SUM is INT_MIN
>>
>> "Assumes ADD and SUM are positive."
>
> That assumption is incorrect, since SUM can be INT_MIN after a
> wraparound overflow.

Well it *used* to be correct... /me will work on that ;-)

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

Version 3.  Cast SUM to unsigned first, in case it's pre-wrapped.
Expanded comment.  Verified that ADD is always INTERNAL_SIZE_T so no
need to cast that to unsigned.

	[BZ #20628]
	* malloc/malloc.c (int_mallinfo): Use saturating add instead of
	overflow to collect statistics into a fixed "int" container.

diff --git a/malloc/malloc.c b/malloc/malloc.c
index ef04360..9d4018f 100644
--- a/malloc/malloc.c
+++ b/malloc/malloc.c
@@ -224,6 +224,7 @@
 #include <unistd.h>
 #include <stdio.h>    /* needed for malloc_stats */
 #include <errno.h>
+#include <limits.h>
 
 #include <shlib-compat.h>
 
@@ -4594,8 +4595,8 @@ int_mallinfo (mstate av, struct mallinfo *m)
   mchunkptr p;
   INTERNAL_SIZE_T avail;
   INTERNAL_SIZE_T fastavail;
-  int nblocks;
-  int nfastblocks;
+  INTERNAL_SIZE_T nblocks;
+  INTERNAL_SIZE_T nfastblocks;
 
   /* Ensure initialization */
   if (av->top == 0)
@@ -4633,18 +4634,38 @@ int_mallinfo (mstate av, struct mallinfo *m)
         }
     }
 
-  m->smblks += nfastblocks;
-  m->ordblks += nblocks;
-  m->fordblks += avail;
-  m->uordblks += av->system_mem - avail;
-  m->arena += av->system_mem;
-  m->fsmblks += fastavail;
+/* Saturated add - add ADD to SUM.  If the result exceeds the range of
+   "int" (or, wrapped, "unsigned int"), set SUM to UINT_MAX instead
+   ((int)-1).  Assumes ADD and SUM reflect positive values, even when
+   they wrap to negative, and that SUM is type "int".  The published
+   ABI prevents us from bumping "int" to a larger type.  Note: this
+   macro doesn't handle overflow when INTERNAL_SIZE_T is the same size
+   as "int", but in that case, the things we're counting wouldn't
+   cause an overflow anyway.
+
+   The net result is that sums which would wrap around and become
+   misleading positive values again, stop at -1, so any positive value
+   we report is accurate, and any negative number other than -1 we
+   report can be cast to unsigned to become accurate.  */
+#define SAT_ADD(SUM, ADD) \
+  ({ INTERNAL_SIZE_T tmp = (INTERNAL_SIZE_T)(unsigned)(SUM) + (INTERNAL_SIZE_T)(ADD); SUM = (tmp > UINT_MAX) ? -1 : tmp; })
+
+/* Likewise, but assign ADD to SUM.  */
+#define SAT_SET(SUM, ADD) \
+  ({ SUM = ((INTERNAL_SIZE_T)(ADD) > UINT_MAX) ? -1 : (ADD); })
+
+  SAT_ADD (m->smblks, nfastblocks);
+  SAT_ADD (m->ordblks, nblocks);
+  SAT_ADD (m->fordblks, avail);
+  SAT_ADD (m->uordblks, av->system_mem - avail);
+  SAT_ADD (m->arena, av->system_mem);
+  SAT_ADD (m->fsmblks, fastavail);
   if (av == &main_arena)
     {
-      m->hblks = mp_.n_mmaps;
-      m->hblkhd = mp_.mmapped_mem;
-      m->usmblks = 0;
-      m->keepcost = chunksize (av->top);
+      SAT_SET (m->hblks, mp_.n_mmaps);
+      SAT_SET (m->hblkhd, mp_.mmapped_mem);
+      SAT_SET (m->usmblks, 0);
+      SAT_SET (m->keepcost, chunksize (av->top));
     }
 }
 

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Paul Eggert]

On 10/06/2016 09:52 AM, DJ Delorie wrote:
> with a 32-bit memory space none of the values will "happen" to cause an
> overflow, because we never have more than 2^32  bytes of memory or 2^32
> objects to count.

The code should work even when INTERNAL_SIZE_T is 32 bits and size_t is 
64 bits. Although perhaps there are other problems with such 
configurations, we shouldn't make matters worse with this change. For 
example, mallinfo should work if there are multiple 4-GiB arenas in such 
a configuration.

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Joseph Myers]

On Thu, 6 Oct 2016, Paul Eggert wrote:

> On 10/06/2016 09:52 AM, DJ Delorie wrote:
> > with a 32-bit memory space none of the values will "happen" to cause an
> > overflow, because we never have more than 2^32  bytes of memory or 2^32
> > objects to count.
> 
> The code should work even when INTERNAL_SIZE_T is 32 bits and size_t is 64
> bits. Although perhaps there are other problems with such configurations, we

Actually, is there really a use for the INTERNAL_SIZE_T abstraction at 
all?  I think it might make sense just to replace INTERNAL_SIZE_T by 
size_t everywhere.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [PATCH] [BZ 20628] make mallinfo saturating

[Paul Eggert]

On 10/06/2016 01:43 PM, Joseph Myers wrote:
> Actually, is there really a use for the INTERNAL_SIZE_T abstraction at
> all?  I think it might make sense just to replace INTERNAL_SIZE_T by
> size_t everywhere.

Yes, although I think part of the intent was to support a system with 
individual arenas limited to 2**32 bytes even on 64-bit platforms, if 
nobody needs this capability the code would be simpler without it and 
removing it would fix the problem I mentioned. (Another part of the 
intent was to support pre-C89 platforms where size_t was a signed type, 
but that long ago became unimportant.)

Re: [PATCH] [BZ 20628] make mallinfo saturating

[DJ Delorie]

Ping!

https://sourceware.org/ml/libc-alpha/2016-10/msg00142.html