[9fans] aux/acidleak pool pathology

[9fans] aux/acidleak pool pathology

[erik quanstrom]

without getting to deep in the details of the pool
library, the reallocation loop aux/acidleak sends
realloc off the deep end.

here's an example; i've added an abort so i can see
how big acidleak is getting

	rb2; ps -a | grep xyz
	xyz           15104    0:29   0:02    45132K Pread    fs [upas/fs -np]
	rb2; leak 15104
	aux/acidleak: realloc 12280320 fails
	acidleak 25325: suicide: sys: trap: fault read addr=0x0 pc=0x00004a14
	rb2; ps -a | grep leak
	xyz           25325    0:02   0:03  2022876K Broken   aux/acidleak
	xyz           25328    0:00   0:00      156K Pread    grep leak

obviously the Brdline loop in main is reallocating data and block
so they don't fit in their previous buckets and pool sbrk's more
memory.  it would seem that pool is missing the fact that
at some point the old, now-empty blocks are big enough
when merged.  however  libc/port/pool.c:/^poolreallocl
appears to have the proper logic.

- erik

Re: [9fans] aux/acidleak pool pathology

[Russ Cox]

> obviously the Brdline loop in main is reallocating data and block
> so they don't fit in their previous buckets and pool sbrk's more
> memory.  it would seem that pool is missing the fact that

It's probably a combination of data and block growing together
along with the occasional estrdup that is causing the fragmentation.
You should rewrite both of the reallocs to double the array when
they outgrow the current one instead of growing by a fixed amount.
The fixed amount is nice because it avoids the extra variable
tracking the maximum size of the array, but it's a terrible algorithm.

Russ

Re: [9fans] aux/acidleak pool pathology

[erik quanstrom]

On Thu May 21 12:39:00 EDT 2009, rsc@swtch.com wrote:
> > obviously the Brdline loop in main is reallocating data and block
> > so they don't fit in their previous buckets and pool sbrk's more
> > memory.  it would seem that pool is missing the fact that
>
> It's probably a combination of data and block growing together
> along with the occasional estrdup that is causing the fragmentation.
> You should rewrite both of the reallocs to double the array when
> they outgrow the current one instead of growing by a fixed amount.
> The fixed amount is nice because it avoids the extra variable
> tracking the maximum size of the array, but it's a terrible algorithm.

in this simple case, that is an fine solution.  but i also see similar
behavior with upas/fs, especially when opening and closing multiple
mailboxes.  i was actually trying to debug a case where upas/fs has
sbrk'd 800mb but had not had an active set >43mb when i ran across
this behavior.

more importantly, since pool is used in the kernel, i would imagine
that a determined attacker could force the kernel to "run out" of
memory in a similar fashion.  perhaps by dd'ing large chunks and
small chunks from /dev/zero.  maybe there's a simple reason this can't
happen that i'm missing.  but i don't currently see it.

- erik

Re: [9fans] aux/acidleak pool pathology

[erik quanstrom]

> behavior with upas/fs, especially when opening and closing multiple
> mailboxes.

sorry.  that's not clear.  *serially* opening and closing mailboxes.  only
one mail box is open at a time.  apple mail, for example, opens every
mailbox you've got every 5 minutes and checks it.  apple mail doesn't
respect imap.subscribed.

- erik

Re: [9fans] aux/acidleak pool pathology

[Russ Cox]

On Thu, May 21, 2009 at 9:54 AM, erik quanstrom <quanstro@quanstro.net> wrote:
> On Thu May 21 12:39:00 EDT 2009, rsc@swtch.com wrote:
>> > obviously the Brdline loop in main is reallocating data and block
>> > so they don't fit in their previous buckets and pool sbrk's more
>> > memory.  it would seem that pool is missing the fact that
>>
>> It's probably a combination of data and block growing together
>> along with the occasional estrdup that is causing the fragmentation.
>> You should rewrite both of the reallocs to double the array when
>> they outgrow the current one instead of growing by a fixed amount.
>> The fixed amount is nice because it avoids the extra variable
>> tracking the maximum size of the array, but it's a terrible algorithm.
>
> in this simple case, that is an fine solution.  but i also see similar
> behavior with upas/fs, especially when opening and closing multiple
> mailboxes.  i was actually trying to debug a case where upas/fs has
> sbrk'd 800mb but had not had an active set >43mb when i ran across
> this behavior.

all allocators have fragmentation and reuse problems.
some are better than others, but they all do.
linear reallocs are always a bad idea; the worse
part is requiring the array to be contiguous in the
first place, but you can't qsort a linked list.

if upas/fs is allocating arbitrarily large buffers,
then its allocation behavior is broken too.

> more importantly, since pool is used in the kernel, i would imagine
> that a determined attacker could force the kernel to "run out" of
> memory in a similar fashion.  perhaps by dd'ing large chunks and
> small chunks from /dev/zero.  maybe there's a simple reason this can't
> happen that i'm missing.  but i don't currently see it.

if the kernel can be forced to allocate an arbitrarily
large chunk of data, that's the bug to fix, not the
allocator behavior.  it probably can, in its handling
of strings like user names and large paths passed
to open.  /dev/zero doesn't allocate at all.

russ

Re: [9fans] aux/acidleak pool pathology

[erik quanstrom]

> part is requiring the array to be contiguous in the
> first place, but you can't qsort a linked list.

i've sidestepped this problem a few times by building a
linked list and later building an array to sort.  then, if
necessary, relinking the list.  the big allocation is then
done only once.

even after changing to a power-of-two allocation and starting
with 8k items, aux/acidleak still takes 400mb on a 40mb proc
with only 155278 bytes actually allocated (in the target process).

is the a chance that pool is not packing the small
allocations together well?

> if upas/fs is allocating arbitrarily large buffers,
> then its allocation behavior is broken too.

there are a fixed number of large buffers.  up to 15 messages
and mdir uses dirreadall so it can qsort.  the qsort is easy enough
to eliminate, but it's more difficult to bound message buffers.

- erik

Re: [9fans] aux/acidleak pool pathology

[Russ Cox]

> even after changing to a power-of-two allocation and starting
> with 8k items, aux/acidleak still takes 400mb on a 40mb proc
> with only 155278 bytes actually allocated (in the target process).
>
> is the a chance that pool is not packing the small
> allocations together well?

i wouldn't judge pool based on acidleak.
have you checked how much data acidleak
is allocating in that 400mb?  i expect the
data array to be huge: it knows about every
word in memory that looks vaguely like a pointer.
acidleak was never intended to be lightweight.

>> if upas/fs is allocating arbitrarily large buffers,
>> then its allocation behavior is broken too.
>
> there are a fixed number of large buffers.  up to 15 messages
> and mdir uses dirreadall so it can qsort.  the qsort is easy enough
> to eliminate, but it's more difficult to bound message buffers.

i never said fixing it was easy.  ;-)

russ

Re: [9fans] aux/acidleak pool pathology

[erik quanstrom]

!/bin/upas/marshal -s 'Re: [9fans] aux/acidleak pool pathology' -R /mail/fs/mbox/272 9fans@9fans.net
> >> if upas/fs is allocating arbitrarily large buffers,
> >> then its allocation behavior is broken too.
> >
> > there are a fixed number of large buffers.  up to 15 messages
> > and mdir uses dirreadall so it can qsort.  the qsort is easy enough
> > to eliminate, but it's more difficult to bound message buffers.
>
> i never said fixing it was easy.  ;-)

from the embarrassing bugs department....

going to all that trouble might not be worth it at
~10000 message mailboxes.  it turns out that a bug i
introduced earlier in the week in imap4d was causing all
mailboxes to remain open.  so the 400mb process had grown
from a 50mb process due to a few esoteric leaks and having
1.5gb in 203 mailboxes open all at once.  it's suprising that
upas/fs did as well as it did.

combining the tricks from the week shrinks this process to
a slightly more manageable 12mb.

unfortunately, i think this will just encourage users to
aim for 100000 messages in their inbox.

☺

- erik

Re: [9fans] aux/acidleak pool pathology

[Joel C. Salomon]

On Thu, May 21, 2009 at 10:13 PM, erik quanstrom <quanstro@quanstro.net> wrote:
> unfortunately, i think this will just encourage users to
> aim for 100000 messages in their inbox.

Have you ever pointed an IMAP client at “[Gmail]/All Mail” and asked
it to download all headers?

—Joel

Re: [9fans] aux/acidleak pool pathology

[erik quanstrom]

On Fri May 22 12:54:27 EDT 2009, joelcsalomon@gmail.com wrote:
> On Thu, May 21, 2009 at 10:13 PM, erik quanstrom <quanstro@quanstro.net> wrote:
> > unfortunately, i think this will just encourage users to
> > aim for 100000 messages in their inbox.
>
> Have you ever pointed an IMAP client at “[Gmail]/All Mail” and asked
> it to download all headers?
>
> —Joel

yes.

- erik