malloc-standard: Fix truncation problem in malloc

This fixes a bug that can lead to the calculation of a wrong bin `idx`,
which in turn leads to a too small chunk of memory being chosen for the
number of bytes (`nb`) to be allocated. This leads to a fault (or
possibly to memory being written in the wrong location) when using the
offset `nb` on top of the chunk for a write operation.

malloc() takes the number of bytes to allocate as size_t, but the
calculation of the global bin index idx is done via
malloc_largebin_index() which takes as parameter and calculates
internally with unsigned int. This leads, for large allocations, to a
truncation of the value and consequently to the idx being wrongly
calculated.

idx is an index into the bins which are sorted in ascending order of
size range of its including chunks (e.g. 8-16, 16-32, 32-64,...).
The malloc() algorithm depends on the idx being calculated such that
we begin searching only at a bin whose chunks are always large enough
to include the memory size to be allocated (nb).

If the idx is too small (as can happen due to the described integer
overflow), this code will lead to a write to a wrong
address (remainder->bk resp. remainder->fd) (lines from malloc.c):

1086    size = chunksize(victim);
1087
1088    /* We know the first chunk in this bin is big enough to use. */
1089    assert((unsigned long)(size) >= (unsigned long)(nb));

1108    remainder = chunk_at_offset(victim, nb);

1111    remainder->bk = remainder->fd = unsorted_chunks(av);

The chunk victim should normally be from a bin of a range where each
chunk is at least of the size nb. Since it's not, its size may be
smaller than nb. With assertions enabled the assertion in 1089 would
fail. Without assertions we add nb as an offset to the chunk but since
the size of the chunk is a lot smaller than nb, this will point to an
address somewhere else.

Signed-off-by: Marcus Haehnel <marcus.haehnel@kernkonzept.com>

1 files changed, 5 insertions, 5 deletions

diff --git a/libc/stdlib/malloc-standard/malloc.c b/libc/stdlib/malloc-standard/malloc.c
index cecea87ec..e51bc6610 100644
--- a/libc/stdlib/malloc-standard/malloc.c
+++ b/libc/stdlib/malloc-standard/malloc.c
@@ -29,7 +29,7 @@ __UCLIBC_MUTEX_INIT(__malloc_lock, PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP);
 struct malloc_state __malloc_state;  /* never directly referenced */
 
 /* forward declaration */
-static int __malloc_largebin_index(unsigned int sz);
+static int __malloc_largebin_index(unsigned long sz);
 
 #ifdef __UCLIBC_MALLOC_DEBUGGING__
 
@@ -755,10 +755,10 @@ static void* __malloc_alloc(size_t nb, mstate av)
   Compute index for size. We expect this to be inlined when
   compiled with optimization, else not, which works out well.
 */
-static int __malloc_largebin_index(unsigned int sz)
+static int __malloc_largebin_index(unsigned long sz)
 {
-    unsigned int  x = sz >> SMALLBIN_WIDTH;
-    unsigned int m;            /* bit position of highest set bit of m */
+    unsigned long  x = sz >> SMALLBIN_WIDTH;
+    unsigned long m;            /* bit position of highest set bit of m */
 
     if (x >= 0x10000) return NBINS-1;
 
@@ -776,7 +776,7 @@ static int __malloc_largebin_index(unsigned int sz)
 	   S. Warren Jr's book "Hacker's Delight".
 	   */
 
-	unsigned int n = ((x - 0x100) >> 16) & 8;
+	unsigned long n = ((x - 0x100) >> 16) & 8;
 	x <<= n;
 	m = ((x - 0x1000) >> 16) & 4;
 	n += m;