I have raised an issue on GitHub for the identified issue (https://github.com/seL4/musllibc/issues/17#issue-1188160949). Please let me know if there is anything else I need to do to formally report the fault to can do to assist with the resolution.
Stephen
On 24 Mar 2022, at 14:17, WILLIAMS Stephen via Devel mailto:devel@sel4.systems> wrote:
***This mail has been sent from an external source***
Following on from my previous email I have tested the following patch to memalign which I believe resolves the identified weakness:
diff --git a/src/malloc/memalign.c b/src/malloc/memalign.c
index 006bd21c..c98963f0 100644
--- a/src/malloc/memalign.c
+++ b/src/malloc/memalign.c
@@ -21,6 +21,9 @@ void *__memalign(size_t align, size_t len)
errno = ENOMEM;
return NULL;
}
+ else if (len < 4*sizeof(size_t))
+ /* Ensure the length of returned chunk meets the minimum limit. */
+ len = 4*sizeof(size_t);
if (align <= 4*sizeof(size_t)) {
if (!(mem = malloc(len)))
@@ -50,7 +53,29 @@ void *__memalign(size_t align, size_t len)
((size_t *)new)[-1] = header&7 | end-new;
((size_t *)end)[-2] = footer&7 | end-new;
- free(mem);
+ if (new-mem >= 4*sizeof(size_t))
+ free(mem);
+ else {
+ /* The size of the region before 'new' is too small to be handled as a chunk
+ * so we cannot call 'free' on it. Instead we either discard the memory or
+ * transfer ownership of it to the previous chunk */
+ if (!(((size_t *)mem)[-2] & -8)) {
+ /* mem->psize has no length, i.e. 'mem' is the first chunk in this mapped
+ * region. In this case we simply discard the memory prior to 'new' by
+ * making 'new' the first chunk of the mapped region. To do this we set
+ * the length of new->psize to 0 with the 'in use' flag set, which equates
+ * to simply setting its value to 1. */
+ ((size_t *)new)[-2] = 1;
+ }
+ else {
+ /* There is a previous chunk, assign ownership of the region before 'new'
+ * to this previous chunk by increasing it's length. */
+ unsigned char *pre = mem - (((size_t *)mem)[-2] & -8);
+ ((size_t *)pre)[-1] += new-mem;
+ ((size_t *)new)[-2] = ((size_t *)pre)[-1];
+ }
+ }
+
return new;
}
On 24 Mar 2022, at 13:59, WILLIAMS Stephen via Devel mailto:devel@sel4.systemsmailto:devel@sel4.systems> wrote:
***This mail has been sent from an external source***
Following a lot of further investigation I believe I have determined the root cause of this issue. Surprisingly this appears to be a bug in the memalign implementation within seL4's fork of the musl library.
I note that the memory allocation system within the mainline musl was completely reworked / replaced a number of years ago so there does not appear to be any scope to raise a bug report on the musl project.
Fault summary:
The correctness of the memory allocation bookkeeping system relies upon the constraint that the minimum size of a memory 'chunk' is 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. 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, however the code of the __memalign routine within memalign.c can break this minimum size constraint and therefore lead to corruption of the bookkeeping.
The __memalign 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 is 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. __memalign then calls 'free' on the first chunk which wasn't required. So far so good, however __memalign fails to enforce the minimum chunk size constraint on either of the two split chunks.
In our case the first chunk (the one to be freed) was only 16 bytes whilst 4xsizeof(size_t) is 32 bytes, thereby breaking the minimum chunk size constraint and so led to the detected corruption.
Stephen
On 23 Mar 2022, at 00:30, Kent Mcleod mailto:kent.mcleod72@gmail.commailto:kent.mcleod72@gmail.com> wrote:
***This mail has been sent from an external source***
On Tue, Mar 22, 2022 at 6:17 PM Roderick Chapman mailto:rod@proteancode.commailto:rod@proteancode.com> wrote:
On 22/03/2022 04:50, Kent Mcleod wrote:
The memalign definition provided by musl is a weak symbol and would be
overridden by any stronger definition encountered in sources such as
from U-Boot.
Good grief!
Is there a linker warning that complains about that sort of overriding?
I'm not aware of one. If you add `-Wl,-M` to the CMake
`target_link_libraries` command then the linker will print out a
mapping file which contains which object file each symbol comes from.
This may be enough to confirm whether symbols are getting replaced
unexpectedly.
- Rod
_______________________________________________
Devel mailing list -- devel@sel4.systemsmailto:devel@sel4.systemsmailto:devel@sel4.systems
To unsubscribe send an email to devel-leave@sel4.systemsmailto:devel-leave@sel4.systemsmailto:devel-leave@sel4.systems
_______________________________________________
Devel mailing list -- devel@sel4.systemsmailto:devel@sel4.systemsmailto:devel@sel4.systems
To unsubscribe send an email to devel-leave@sel4.systemsmailto:devel-leave@sel4.systemsmailto:devel-leave@sel4.systems
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.
_______________________________________________
Devel mailing list -- devel@sel4.systemsmailto:devel@sel4.systemsmailto:devel@sel4.systems
To unsubscribe send an email to devel-leave@sel4.systemsmailto:devel-leave@sel4.systemsmailto:devel-leave@sel4.systems
_______________________________________________
Devel mailing list -- devel@sel4.systemsmailto:devel@sel4.systems
To unsubscribe send an email to devel-leave@sel4.systemsmailto:devel-leave@sel4.systems
