Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Tue, 24 Jan 2023 03:37:48 -0500
From: Rich Felker <dalias@...c.org>
To: Dominique MARTINET <dominique.martinet@...ark-techno.com>
Cc: musl@...ts.openwall.com
Subject: Re: infinite loop in mallocng's try_avail

On Mon, Jan 23, 2023 at 10:33:39AM +0900, Dominique MARTINET wrote:
> Hi,
> 
> A coworker of mine has been observing hangs during shutdown on our ARM
> alpine/openrc board, where the openrc shutdown process is stuck in
> userspace after having stopped almost everything once in a blue moon
> (running reboot in a loop, this is reproducible roughly one time every
> three days)
> 
> It turns out it's stuck in malloc() as follow:
> (gdb) bt
> #0  try_avail (pm=0xb6f692e8 <__malloc_context+48>) at src/malloc/mallocng/malloc.c:156
> #1  alloc_slot (sc=sc@...ry=0, req=req@...ry=8) at src/malloc/mallocng/malloc.c:288
> #2  0xb6efdc94 in __libc_malloc_impl (n=8) at src/malloc/mallocng/malloc.c:369
> #3  0xb6e9d532 in xmalloc (size=size@...ry=8) at ../src/shared/helpers.h:64
> #4  0xb6e9d598 in rc_stringlist_new () at ../src/librc/librc-stringlist.c:24
> #5  0xb6e9b91e in get_provided (depinfo=depinfo@...ry=0xb6f585d0, runlevel=runlevel@...ry=0xbe940f99 "shutdown", options=options@...ry=3)
>     at ../src/librc/librc-depend.c:269
> #6  0xb6e9bce8 in visit_service (options=3, runlevel=0xbe940f99 "shutdown", depinfo=0xb6f5ee30, visited=0xb6f57b00, sorted=0xb6f57af0, types=0xb6f575a0, 
>     deptree=0xb6ed8ec0) at ../src/librc/librc-depend.c:419
> #7  visit_service (deptree=0xb6ed8ec0, types=0xb6f575a0, sorted=0xb6f57af0, visited=0xb6f57b00, depinfo=0xb6f5ee30, runlevel=0xbe940f99 "shutdown", options=3)
>     at ../src/librc/librc-depend.c:357
> #8  0xb6e9bcb2 in visit_service (options=3, runlevel=0xbe940f99 "shutdown", depinfo=0xb6f62f50, visited=0xb6f57b00, sorted=0xb6f57af0, types=0xb6f575a0, 
>     deptree=0xb6ed8ec0) at ../src/librc/librc-depend.c:405
> #9  visit_service (deptree=0xb6ed8ec0, types=0xb6f575a0, sorted=0xb6f57af0, visited=0xb6f57b00, depinfo=0xb6f62f50, runlevel=0xbe940f99 "shutdown", options=3)
>     at ../src/librc/librc-depend.c:357
> #10 0xb6e9bcb2 in visit_service (options=3, runlevel=0xbe940f99 "shutdown", depinfo=0xb6ed85a0, visited=0xb6f57b00, sorted=0xb6f57af0, types=0xb6f575a0, 
>     deptree=0xb6ed8ec0) at ../src/librc/librc-depend.c:405
> #11 visit_service (deptree=0xb6ed8ec0, types=0xb6f575a0, sorted=0xb6f57af0, visited=0xb6f57b00, depinfo=0xb6ed85a0, runlevel=0xbe940f99 "shutdown", options=3)
>     at ../src/librc/librc-depend.c:357
> #12 0xb6e9bffa in rc_deptree_depends (deptree=deptree@...ry=0xb6ed8ec0, types=types@...ry=0xb6f575a0, services=services@...ry=0xb6f57ab0, 
>     runlevel=0xbe940f99 "shutdown", options=options@...ry=3) at ../src/librc/librc-depend.c:482
> #13 0x004226ea in do_stop_services (going_down=true, parallel=true, newlevel=0xbe940f99 "shutdown", deptree=0xb6ed8ec0, stop_services=<optimized out>, 
>     start_services=0xb6f57d70, types_nw=0xb6f575a0) at ../src/openrc/rc.c:592
> #14 main (argc=<optimized out>, argv=<optimized out>) at ../src/openrc/rc.c:1022
> 
> (this is musl 1.2.4 with a couple of patchs, none around malloc:
> https://gitlab.alpinelinux.org/alpine/aports/-/tree/3.17-stable/main/musl
> )
> 
> For convenience, I've copied the incriminated loop here:
>         int cnt = m->mem->active_idx + 2;
>         int size = size_classes[m->sizeclass]*UNIT;
>         int span = UNIT + size*cnt;
>         // activate up to next 4k boundary
>         while ((span^(span+size-1)) < 4096) {
>                 cnt++;
>                 span += size;
>         }

This code should not be reachable for size class 0 or any size class
allocated inside a larger-size-class slot. That case has active_idx =
cnt-1 (set at line 272).

If this code is being reached, either the allocator state has been
corrupted by some UB in the application, or there's a logic bug in
mallocng. The sequence of events that seem to have to happen to get
there are:

1. Previously active group has no more available slots (line 120).

2. Freed mask of newly activating group (line 131 or 138) is either
   zero (line 145) or the active_idx (read from in-band memory
   susceptible to application buffer overflows etc) is wrong and
   produces zero when its bits are anded with the freed mask (line
   145).

> Here, we have UNIT=16 (constant), we're considering a malloc(8) so
> sizeclass is 0 -> size_classes[0] = 1 -> size = 16, so we're looping
> on this condition:
>   while (span ^ (span + 15) < 4096)
> with span being a multiple of 16.
> 
> I'm not good at maths, but I'm fairly confindent this never gets false:
> 0x0ff0 ^ 0x0fff = f
> 0x1000 ^ 0x100f = f
> It could become true without the -1 (span+16), is that was intended ?
> (It works for other sizes because of the UNIT offset in size, so
> e.g. for size=32 we have 0x0ff0 ^ 0x100f which is 8191 alright, but
> that'd also work without the -1 as far as I can tell)
> 
> 
> Anyway, I'm not ruling out a problem in openrc yet -- rc_parallel is
> known to be buggy -- but looking at the mallocng ctx I can't see any
> obvious problem so I'm asking here first:
> Is that supposed to work? Now I've gotten it down so far it might be
> possible to build a reproducer; unfortunately I do not know how ctx was
> when it entered try_avail (the function entered the if (!mask) so the
> first entry was dequeued), but here's it's current state (please ask if
> you need anything else)
> ------
> (gdb) p __malloc_context            
> $94 = {
>   secret = 15756413639004407235,
>   init_done = 1,
>   mmap_counter = 135,
>   free_meta_head = 0x0,
>   avail_meta = 0x18a3f70,
>   avail_meta_count = 6,
>   avail_meta_area_count = 0,
>   meta_alloc_shift = 0,
>   meta_area_head = 0x18a3000,
>   meta_area_tail = 0x18a3000,
>   avail_meta_areas = 0x18a4000 <error: Cannot access memory at address 0x18a4000>,
>   active = {0x18a3e98, 0x18a3eb0, 0x18a3208, 0x18a3280, 0x0, 0x0, 0x0, 0x18a31c0, 0x0, 0x0, 0x0, 0x18a3148, 0x0, 0x0, 0x0, 0x18a3dd8, 0x0, 0x0, 0x0, 0x18a3d90, 0x0, 
>     0x18a31f0, 0x0, 0x18a3b68, 0x0, 0x18a3f28, 0x0, 0x0, 0x0, 0x18a3238, 0x0 <repeats 18 times>},
>   usage_by_class = {2580, 600, 10, 7, 0 <repeats 11 times>, 96, 0, 0, 0, 20, 0, 3, 0, 8, 0, 3, 0, 0, 0, 3, 0 <repeats 18 times>},
>   unmap_seq = '\000' <repeats 31 times>,
>   bounces = '\000' <repeats 18 times>, "w", '\000' <repeats 12 times>,
>   seq = 1 '\001',
>   brk = 25837568
> }
> (gdb) p *__malloc_context->active[0]
> $95 = {
>   prev = 0x18a3f40,
>   next = 0x18a3e80,
>   mem = 0xb6f57b30,
>   avail_mask = 1073741822,
>   freed_mask = 0,
>   last_idx = 29,
>   freeable = 1,
>   sizeclass = 0,
>   maplen = 0
> }
> (gdb) p *__malloc_context->active[0]->mem
> $97 = {
>   meta = 0x18a3e98,
>   active_idx = 29 '\035',
>   pad = "\000\000\000\000\000\000\000\000\377\000",
>   storage = 0xb6f57b40 ""
> }

This is really weird, because at the point of the infinite loop, the
new group should not yet be activated (line 163), so
__malloc_context->active[0] should still point to the old active
group. But its avail_mask has all bits set and active_idx is not
corrupted, so try_avail should just have obtained an available slot
from it without ever entering the block at line 120. So I'm confused
how it got to the loop.

One odd thing I noticed is that the backtrace pm=0xb6f692e8 does not
match the __malloc_context->active[0] address. Were thse from
different runs?

> ------
> 
> 
> I'm leaving that process stuck in limbo so I can get more infos for a
> few days.
> 
> Meanwhile we'll also be trying to see if the following patch helps --
> given we do not have a good reproducer there won't be any feedback on
> this side for a while.
> ----
> >From f46bbe3117674becb3c5e4ffb7c8f4e4776084db Mon Sep 17 00:00:00 2001
> From: Dominique Martinet <dominique.martinet@...ark-techno.com>
> Date: Mon, 23 Jan 2023 10:12:55 +0900
> Subject: [PATCH] mallocng: try_avail: fix infinite loop
> 
> sizeclass=0 has span being a multiple of size = 16, which will
> never stop having "(span^(span+size-1)) < 4096".
> Removing the -1 makes that ending condition reachable for all
> class sizes.
> ---
>  src/malloc/mallocng/malloc.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/src/malloc/mallocng/malloc.c b/src/malloc/mallocng/malloc.c
> index d695ab8ec982..9ef0b176c31e 100644
> --- a/src/malloc/mallocng/malloc.c
> +++ b/src/malloc/mallocng/malloc.c
> @@ -151,7 +151,7 @@ static uint32_t try_avail(struct meta **pm)
>  				int size = size_classes[m->sizeclass]*UNIT;
>  				int span = UNIT + size*cnt;
>  				// activate up to next 4k boundary
> -				while ((span^(span+size-1)) < 4096) {
> +				while ((span^(span+size)) < 4096) {
>  					cnt++;
>  					span += size;
>  				}
> ----
> 
> Thank you,
> -- 
> Dominique Martinet

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.