mailing list of musl libc
 help / color / mirror / code / Atom feed
* [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption
@ 2022-05-03 10:51 WILLIAMS Stephen
  2022-05-03 12:59 ` Rich Felker
  0 siblings, 1 reply; 5+ messages in thread
From: WILLIAMS Stephen @ 2022-05-03 10:51 UTC (permalink / raw)
  To: musl

[-- Attachment #1: Type: text/plain, Size: 3480 bytes --]

Fault detection / background:

This fault was detected whilst working with the seL4 microkernel which uses an old fork of musl libc (see https://github.com/seL4/musllibc/issues/17). Whilst the implementation of aligned_alloc has changed between the seL4 fork and the mainline musl libc the same underlying fault still appears to be present in oldmalloc branch of mainline musl libc.

Fault summary:

The correctness of the memory allocation bookkeeping system relies upon the constraint that the minimum size of a memory 'chunk' is SIZE_ALIGN, defined in malloc_impl.h as 4xsizeof(size_t). If this constraint is broken then bad things happen and the bookkeeping system becomes corrupted, specifically:

1. Arithmetic wrap-around of x occurs in the routines bin_index and bin_index_up within malloc.c resulting in the maximum chunk index being used when the minimum index should have been used. This can lead to chunks below the minimum size limit to be considered to be large unallocated chunks of memory. Subsequent allocation of these unallocated chunks (considered to be large but in reality tiny) allows previously allocated chunks to be re-used / overwritten.

2.The 'next' and 'prev' pointers held in an unallocated chunk (used to maintained a doubly linked list of unallocated chunks) that is below the minimum size limit may be overlayed with the bookkeeping of the following chunk.

The malloc routine enforces this minimum chunk size limit (through the adjust_size routine), however the code of the aligned_alloc routine within aligned_alloc.c can break this minimum size constraint and therefore lead to corruption of the bookkeeping.

The aligned_alloc routine works by malloc'ing sufficient memory to ensure the requested amount of memory is available, at the requested alignment, somewhere within the malloc'ed region. This means that there may be some unused memory allocated before the start of the aligned memory area. This can be handled by splitting the chunk allocated by malloc into two chunks, a chunk of memory prior to the start of the aligned memory followed by a chunk that starts at the requested alignment (see aligned_alloc.c lines 43:49). aligned_alloc then calls ‘__bin_chunk’ (line 51) on the first chunk which wasn't required. So far so good, however aligned_alloc fails to enforce the minimum chunk size constraint on either of the two split chunks.

Proposed fix:

1. A minimum size limit on the ‘len’ parameter of aligned_alloc must be enforced to ensure that the resulting chunk returned by aligned_alloc meets the minimum chunk length limit, i.e. adjust the input ‘len’ value to be no less than SIZE_ALIGN.

2. aligned_alloc must not call ‘__bin_chunk’ in the case where new-men < SIZE_ALIGN. In such a case rather than effectively ‘free’ing this small chunk (which is below the minimum length limit and therefore leads to corruption of the bookkeeping) the memory should be added to the end of the preceding chunk.

Thanks for your help,
Stephen

This message contains information that may be privileged or confidential and is the property of the Capgemini Group. It is intended only for the person to whom it is addressed. If you are not the intended recipient, you are not authorized to read, print, retain, copy, disseminate, distribute, or use this message or any part thereof. If you receive this message in error, please notify the sender immediately and delete all copies of this message.

[-- Attachment #2: Type: text/html, Size: 4530 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption
  2022-05-03 10:51 [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption WILLIAMS Stephen
@ 2022-05-03 12:59 ` Rich Felker
  2022-05-03 15:14   ` WILLIAMS Stephen
  0 siblings, 1 reply; 5+ messages in thread
From: Rich Felker @ 2022-05-03 12:59 UTC (permalink / raw)
  To: WILLIAMS Stephen; +Cc: musl

On Tue, May 03, 2022 at 10:51:32AM +0000, WILLIAMS Stephen wrote:
> Fault detection / background:
> 
> This fault was detected whilst working with the seL4 microkernel
> which uses an old fork of musl libc (see
> https://github.com/seL4/musllibc/issues/17). Whilst the
> implementation of aligned_alloc has changed between the seL4 fork
> and the mainline musl libc the same underlying fault still appears
> to be present in oldmalloc branch of mainline musl libc.

Do you actually have a test case that demonstrates the corruption? I
tried the one from the linked thread at:

https://lists.sel4.systems/hyperkitty/list/devel@sel4.systems/thread/2K2S7OOZJCWD3Z22XGS36OIXD7HRXKNC

and with current musl built --with-malloc=oldmalloc, I get:

memalign: align = 0x40, size = 0x1000. Returned address = 0x579e6040
memalign: align = 0x40, size = 0x1000. Returned address = 0x579e8000

I suspect your fork of oldmalloc is breaking some invariant memalign
depends on.

It's also plausible that there was a bug in the very old version you
forked from, but commit 3c2cbbe7ba8b4486299ae0d5336ae01ab520d116 seems
like the only relevant change. There was an earlier bug vaguely
related to your report fixed in 2013 with commit
70a92bc968156155dd578f7fb1d4c4e3fceb32f8 but you seem to already have
that fix.

> Fault summary:
> 
> The correctness of the memory allocation bookkeeping system relies
> upon the constraint that the minimum size of a memory 'chunk' is
> SIZE_ALIGN, defined in malloc_impl.h as 4xsizeof(size_t). If this
> constraint is broken then bad things happen and the bookkeeping
> system becomes corrupted, specifically:
> 
> 1. Arithmetic wrap-around of x occurs in the routines bin_index and
> bin_index_up within malloc.c resulting in the maximum chunk index
> being used when the minimum index should have been used. This can
> lead to chunks below the minimum size limit to be considered to be
> large unallocated chunks of memory. Subsequent allocation of these
> unallocated chunks (considered to be large but in reality tiny)
> allows previously allocated chunks to be re-used / overwritten.
> 
> 2.The 'next' and 'prev' pointers held in an unallocated chunk (used
> to maintained a doubly linked list of unallocated chunks) that is
> below the minimum size limit may be overlayed with the bookkeeping
> of the following chunk.
> 
> The malloc routine enforces this minimum chunk size limit (through
> the adjust_size routine), however the code of the aligned_alloc
> routine within aligned_alloc.c can break this minimum size
> constraint and therefore lead to corruption of the bookkeeping.
> 
> The aligned_alloc routine works by malloc'ing sufficient memory to
> ensure the requested amount of memory is available, at the requested
> alignment, somewhere within the malloc'ed region. This means that
> there may be some unused memory allocated before the start of the
> aligned memory area. This can be handled by splitting the chunk
> allocated by malloc into two chunks, a chunk of memory prior to the
> start of the aligned memory followed by a chunk that starts at the
> requested alignment (see aligned_alloc.c lines 43:49). aligned_alloc
> then calls ‘__bin_chunk’ (line 51) on the first chunk which wasn't
> required. So far so good, however aligned_alloc fails to enforce the
> minimum chunk size constraint on either of the two split chunks.
> 
> Proposed fix:
> 
> 1. A minimum size limit on the ‘len’ parameter of aligned_alloc must
> be enforced to ensure that the resulting chunk returned by
> aligned_alloc meets the minimum chunk length limit, i.e. adjust the
> input ‘len’ value to be no less than SIZE_ALIGN.
> 
> 2. aligned_alloc must not call ‘__bin_chunk’ in the case where
> new-men < SIZE_ALIGN. In such a case rather than effectively
> ‘free’ing this small chunk (which is below the minimum length limit
> and therefore leads to corruption of the bookkeeping) the memory
> should be added to the end of the preceding chunk.

The splitting aligned_alloc does results in two chunks. The first one
necessarily has valid size because new-mem is a multiple of SIZE_ALIGN
(basic argument: new is rounded up to a multiple of some power of two
>=SIZE_ALIGN and mem already was already a multiple of SIZE_ALIGN by
virtue of having been returned by malloc).

The second chunk has size equal to whatever malloc(len+align-1)
produced (which is necessarily a multiple of SIZE_ALIGN and no less
than len+align-1), minus some multiple of SIZE_ALIGN (from the size of
the first, above) strictly less than align. This means it's >= len and
a multiple of SIZE_ALIGN. There is some concern to be had about what
happens when len==0, but because we used align-1 instead of
align-SIZE_ALIGN to get the extra space, we over-requested
SIZE_ALIGN-1 bytes already and there is no zero case.

If you think there's a gap in this reasoning, could you point it out
with a test case (doesn't need to run; just argument values and
possibly a made up address and chunk size malloc returns) that we can
work through by hand to see where something goes wrong?

Rich

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption
  2022-05-03 12:59 ` Rich Felker
@ 2022-05-03 15:14   ` WILLIAMS Stephen
  2022-05-03 15:47     ` Rich Felker
  0 siblings, 1 reply; 5+ messages in thread
From: WILLIAMS Stephen @ 2022-05-03 15:14 UTC (permalink / raw)
  To: Rich Felker; +Cc: WILLIAMS Stephen, musl

[-- Attachment #1: Type: text/plain, Size: 6358 bytes --]

On 3 May 2022, at 13:59, Rich Felker <dalias@libc.org<mailto:dalias@libc.org>> wrote:
\x7f\x7f\x7f\x1c\x7f\x7f\x7f\x7f\x1f\x1f\x1f\x1e
***This mail has been sent from an external source***

On Tue, May 03, 2022 at 10:51:32AM +0000, WILLIAMS Stephen wrote:
Fault detection / background:

This fault was detected whilst working with the seL4 microkernel
which uses an old fork of musl libc (see
https://github.com/seL4/musllibc/issues/17). Whilst the
implementation of aligned_alloc has changed between the seL4 fork
and the mainline musl libc the same underlying fault still appears
to be present in oldmalloc branch of mainline musl libc.

Do you actually have a test case that demonstrates the corruption? I
tried the one from the linked thread at:

https://lists.sel4.systems/hyperkitty/list/devel@sel4.systems/thread/2K2S7OOZJCWD3Z22XGS36OIXD7HRXKNC

and with current musl built --with-malloc=oldmalloc, I get:

memalign: align = 0x40, size = 0x1000. Returned address = 0x579e6040
memalign: align = 0x40, size = 0x1000. Returned address = 0x579e8000

I suspect your fork of oldmalloc is breaking some invariant memalign
depends on.

It's also plausible that there was a bug in the very old version you
forked from, but commit 3c2cbbe7ba8b4486299ae0d5336ae01ab520d116 seems
like the only relevant change. There was an earlier bug vaguely
related to your report fixed in 2013 with commit
70a92bc968156155dd578f7fb1d4c4e3fceb32f8 but you seem to already have
that fix.

Fault summary:

The correctness of the memory allocation bookkeeping system relies
upon the constraint that the minimum size of a memory 'chunk' is
SIZE_ALIGN, defined in malloc_impl.h as 4xsizeof(size_t). If this
constraint is broken then bad things happen and the bookkeeping
system becomes corrupted, specifically:

1. Arithmetic wrap-around of x occurs in the routines bin_index and
bin_index_up within malloc.c resulting in the maximum chunk index
being used when the minimum index should have been used. This can
lead to chunks below the minimum size limit to be considered to be
large unallocated chunks of memory. Subsequent allocation of these
unallocated chunks (considered to be large but in reality tiny)
allows previously allocated chunks to be re-used / overwritten.

2.The 'next' and 'prev' pointers held in an unallocated chunk (used
to maintained a doubly linked list of unallocated chunks) that is
below the minimum size limit may be overlayed with the bookkeeping
of the following chunk.

The malloc routine enforces this minimum chunk size limit (through
the adjust_size routine), however the code of the aligned_alloc
routine within aligned_alloc.c can break this minimum size
constraint and therefore lead to corruption of the bookkeeping.

The aligned_alloc routine works by malloc'ing sufficient memory to
ensure the requested amount of memory is available, at the requested
alignment, somewhere within the malloc'ed region. This means that
there may be some unused memory allocated before the start of the
aligned memory area. This can be handled by splitting the chunk
allocated by malloc into two chunks, a chunk of memory prior to the
start of the aligned memory followed by a chunk that starts at the
requested alignment (see aligned_alloc.c lines 43:49). aligned_alloc
then calls ‘__bin_chunk’ (line 51) on the first chunk which wasn't
required. So far so good, however aligned_alloc fails to enforce the
minimum chunk size constraint on either of the two split chunks.

Proposed fix:

1. A minimum size limit on the ‘len’ parameter of aligned_alloc must
be enforced to ensure that the resulting chunk returned by
aligned_alloc meets the minimum chunk length limit, i.e. adjust the
input ‘len’ value to be no less than SIZE_ALIGN.

2. aligned_alloc must not call ‘__bin_chunk’ in the case where
new-men < SIZE_ALIGN. In such a case rather than effectively
‘free’ing this small chunk (which is below the minimum length limit
and therefore leads to corruption of the bookkeeping) the memory
should be added to the end of the preceding chunk.

The splitting aligned_alloc does results in two chunks. The first one
necessarily has valid size because new-mem is a multiple of SIZE_ALIGN
(basic argument: new is rounded up to a multiple of some power of two
=SIZE_ALIGN and mem already was already a multiple of SIZE_ALIGN by
virtue of having been returned by malloc).

The second chunk has size equal to whatever malloc(len+align-1)
produced (which is necessarily a multiple of SIZE_ALIGN and no less
than len+align-1), minus some multiple of SIZE_ALIGN (from the size of
the first, above) strictly less than align. This means it's >= len and
a multiple of SIZE_ALIGN. There is some concern to be had about what
happens when len==0, but because we used align-1 instead of
align-SIZE_ALIGN to get the extra space, we over-requested
SIZE_ALIGN-1 bytes already and there is no zero case.

If you think there's a gap in this reasoning, could you point it out
with a test case (doesn't need to run; just argument values and
possibly a made up address and chunk size malloc returns) that we can
work through by hand to see where something goes wrong?

Rich

Interesting. From the logging I’m seeing (admittedly with an old fork in use with seL4) ‘mem’ is not guaranteed to be a multiple of SIZE_ALIGN as you are suggesting above.

The following was generated with logging inside of the __memalign routine to show the values of ’new’ and ‘mem’:

new = 0x5cd500
mem = 0x5cd4f0
memalign: align = 0x40, size = 0x1000. Returned address = 0x5cd500

new = 0x5cd500
mem = 0x5cd4f0
memalign: align = 0x40, size = 0x1000. Returned address = 0x5cd500

The ‘mem’ address returned by malloc is not a multiple of SIZE_ALIGN (32 on this system) thereby leading to new-mem being less that SIZE_ALIGN.

Stpehen

This message contains information that may be privileged or confidential and is the property of the Capgemini Group. It is intended only for the person to whom it is addressed. If you are not the intended recipient, you are not authorized to read, print, retain, copy, disseminate, distribute, or use this message or any part thereof. If you receive this message in error, please notify the sender immediately and delete all copies of this message.

[-- Attachment #2: Type: text/html, Size: 37059 bytes --]

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption
  2022-05-03 15:14   ` WILLIAMS Stephen
@ 2022-05-03 15:47     ` Rich Felker
  2022-05-03 20:01       ` Kent Mcleod
  0 siblings, 1 reply; 5+ messages in thread
From: Rich Felker @ 2022-05-03 15:47 UTC (permalink / raw)
  To: WILLIAMS Stephen; +Cc: musl

On Tue, May 03, 2022 at 03:14:34PM +0000, WILLIAMS Stephen wrote:
> Interesting. From the logging I’m seeing (admittedly with an old
> fork in use with seL4) ‘mem’ is not guaranteed to be a multiple of
> SIZE_ALIGN as you are suggesting above.
> 
> The following was generated with logging inside of the __memalign routine to show the values of ’new’ and ‘mem’:
> 
> new = 0x5cd500
> mem = 0x5cd4f0
> memalign: align = 0x40, size = 0x1000. Returned address = 0x5cd500
> 
> new = 0x5cd500
> mem = 0x5cd4f0
> memalign: align = 0x40, size = 0x1000. Returned address = 0x5cd500
> 
> The ‘mem’ address returned by malloc is not a multiple of SIZE_ALIGN
> (32 on this system) thereby leading to new-mem being less that
> SIZE_ALIGN.

Interesting. I don't see where any changes were made to your fork of
malloc that would cause this, but it's definitely an intended variant
that all chunks be aligned mod SIZE_ALIGN, and that was the case all
the way back to the original musl oldmalloc.

Is it possible that PAGE_SIZE is evaluating to nonsense (maybe
libc.page_size ununitialized), resulting in the initial brk not
getting aligned? It's an implicit assumption that page size is larger
than SIZE_ALIGN.

Rich

^ permalink raw reply	[flat|nested] 5+ messages in thread

* Re: [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption
  2022-05-03 15:47     ` Rich Felker
@ 2022-05-03 20:01       ` Kent Mcleod
  0 siblings, 0 replies; 5+ messages in thread
From: Kent Mcleod @ 2022-05-03 20:01 UTC (permalink / raw)
  To: musl; +Cc: WILLIAMS Stephen

> Is it possible that PAGE_SIZE is evaluating to nonsense (maybe
> libc.page_size ununitialized), resulting in the initial brk not
> getting aligned? It's an implicit assumption that page size is larger
> than SIZE_ALIGN.
>

Yes, libc.page_size being uninitialized is likely what's happening.
We departed from calling __init_libc at some point in the seL4 fork...

> Rich

^ permalink raw reply	[flat|nested] 5+ messages in thread

end of thread, other threads:[~2022-05-03 20:01 UTC | newest]

Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-05-03 10:51 [musl] BUG REPORT: Fault in src/malloc/oldmalloc/aligned_alloc.c leads to memory corruption WILLIAMS Stephen
2022-05-03 12:59 ` Rich Felker
2022-05-03 15:14   ` WILLIAMS Stephen
2022-05-03 15:47     ` Rich Felker
2022-05-03 20:01       ` Kent Mcleod

Code repositories for project(s) associated with this public inbox

	https://git.vuxu.org/mirror/musl/

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).