45343 - plarena problems

Status: NEW

(NSPR :: NSPR, defect)

Description

[Brendan Eich [:brendan]]

The plarena code derives from NSPR1 code that I wrote in 1995, and I wrote it
badly enough that bug 41381 contains fixes for a number of bugs in jsarena.[ch],
which also derives from the old prarena code:

1.  PL_ARENA_RELEASE will fail to free arenas if called with mark ==
pool->first.avail (== pool->first.limit).

2.  PL_ArenaAllocate will pull arenas of capacity pool->arenasize off the
freelist even if they can't satisfy the current request (nb is the net size of
that request).

I think that's it.  During wtc's great code review, I think he mentioned that
plarena.c also fails to free its monitor, and could use just a lock rather than
a monitor.  It could avoid calling malloc while holding the lock.  I'll shut up
now, my track record here is poor!

/be

Comment 1

[Wan-Teh Chang]

Reassigned bug to larryh.

Comment 2

[Wan-Teh Chang]

We will deal with this bug after 4.1.

We need to ask Brendan to explain the patches
to us as we are not familiar with the arena code.

Comment 3

[Brendan Eich [:brendan]]

I have more to add, as PL_ARENA_GROW makes for O(n**2) space growth if one is
constantly growing an allocation that consumes all the usable space in its
arena.  See bug 33390.

/be

Comment 4

[Brendan Eich [:brendan]]

See also the double-roundup-for-JS_ARENA_GROW bug fixed by the last patch,
http://bugzilla.mozilla.org/showattachment.cgi?attach_id=26250, in bug 44009
(which morphed; most of the comments are about an earlier problem with a similar
symptom).

/be

Comment 5

[Brendan Eich [:brendan]]

Another fix to jsarena.c that ought to show up in plarena.c is in bug 72034.

/be

Comment 6

[larryh (gone)]

Attachment: partial fix.

Comment 7

[larryh (gone)]

The function PL_ArenaRelease() calls FreeArenaList() with PR_TRUE for the 
reallyfree argument. This causes a call to free() for the arena's malloc()'d 
blocks, which seems contrary to the idea of reusing arena blocks. Should 
PL_ArenaRelease() call FreeArenaList() with PR_FALSE?

There's more. nelsonb proposed a fix for PL_AreanAllocate()s exhausting the 
freelist as described in (2)of Brendan's report. See the attachment.

Adding nelsonb to the cc list.

Comment 8

[Nelson Bolyard (seldom reads bugmail)]

Yes, and there's still more.

When PL_ARENAMETER is not defined, the functions PL_FreeArenaPool
and PL_FinishArenaPool do the same thing, except that the latter 
actually frees the arenas while the former sends them to the free list.
Either function can be used as a way of freeing all the arenas in
preparation for freeing the PLArenaPool, when PL_ARENAMETER is not defined. 

But when PL_ARENAMETER is defined, the former leaks the stats name 
and the linked list of PLArenaStats structures, while the latter does 
not.  I think neither function should leak the stats.  

Put another way, applications that use PLArenaPools need a function 
that effectively finishes the ArenaPool, but which recycles the 
arenas to the free list rather than freeing them, whether or not 
PL_ARENAMETER is defined.  Applications that use PL_FreeArenaPool
for that purpose leak memory when PL_ARENAMETER is defined.

Here's another suggestion:  in PL_InitArenaPool, when PL_ARENAMETER
is defined, allocate the space for the name string from the pool,
rather than using strdup.

(I consider these PL_ARENAMETER issues to be low priority since, AFAIK,
we never define PL_ARENAMETER.)

Comment 9

[larryh (gone)]

Attachment: new and improved partial fix

Comment 10

[larryh (gone)]

Changed the arenaLock from a PRMonitor to a PRLock.
See the "new and improved partial fix".

Comment 11

[Brendan Eich [:brendan]]

larryh: perhaps PL_ArenaRelease should pass PR_FALSE to FreeArenaList -- I
honestly can't recall why it doesn't.  Calling code that marks and releases with
any frequency would prefer that, and can always PL_FinishArenaPool when done to
return all arenas to the malloc heap.

The change (nelsonb's?) to PL_ArenaAllocate:

-            if (b->limit - b->base == pool->arenasize) {
+            if (b->limit - b->base >= nb) {

tends to waste most of the space in large arenas that happen to be on the
freelist, when there is great variation in pool->arenasize among active pools. 
I have a more complicated fix that does not do best fit, but that tries to avoid
wasting too much space.

Note that my point 2 in the original comment in this bug doesn't begin to
describe the problem with the == code above (the - line): b->limit ===
(PRUword)b + sz, where sz === PR_MAX(nb, pool->arenasize) + sizeof *b +
pool->mask.  IOW, limit bounds the gross arena size, while pool->arenasize is
the net size specified by the caller to PL_InitArenaPool.

I'll attach my fix to just this "bug 2, take 2" problem next.

nelsonb: although the names are far from clear in their connotations, the idea
is that one *may* call PL_FreeArenaPool to return arenas in the pool to the
freelist, as many times as one likes; whereas one *must* call PL_FinishArenaPool
before ceasing all use of a pool (and potentially freeing the pool itself, if it
is malloc'ed or otherwise recycled).

In that light, I would argue that one must never hoard malloc space in the arena
package's global freelist, where the space came from arenas allocated to a pool
that is no longer alive.  That's a recipe for fragmentation and bloat, in our
experience with JS (whose arena package is a sibling fork to plarena, as both
are based on the NSPR 1.0 era prarena.c).

It's true that you could imagine cases where it wins to hoard arenas even as
their pools die; I'm proposing you don't do that, but the API function names are
not clear, and who am I to dictate?  So to fix the bug you cite (really, the
leak of stats.name), I propose that we relax the undocumented rule that callers
must Finish, however often they Free, an ArenaPool, so that either Free or
Finish works.

I don't think we should avoid leaking stats.name by allocating it from the pool,
because PL_InitArenaPool is void and infallible, and doesn't allocate an initial
arena for the pool.  Of course, strdup can fail, too.  As you note, this is low
priority.  I would just make sure PL_FreeArenaPool frees stats.name #ifdef
PL_ARENAMETER, as part of the Free/FinishArenaPool parity hoped for by your comment.

/be

/be

Comment 12

[Brendan Eich [:brendan]]

But nelsonb's and my proposal breaks PL_ARENAMETER, because it frees (but does
not null out) stats.name in PL_FreeArenaPool.  Yuck.

I think the design was coherent, even if the names weren't great: you may Free
to recycle arenas via the freelist; you must Finish, not only to really free
arenas to the malloc heap, but to free stats.name *and* to unlink the stats
struct from the global arena_stats_list.  So I stand by my original hokey code!

Anyway, all this PL_ARENAMETER is small potatoes.

API compatibility precludes it unless we want to make a synonym and promote it
heavily, but PL_RecyclePooledArenas seems like a better name in hindsight than
PL_FreeArenaPool.  Especially because it avoids the <verb>ArenaPool name scheme
that suggests, misleadingly, that PL_FreeArenaPool is some kind of "free"
antonym to PL_InitArenaPool's "init".

/be

Comment 13

[Brendan Eich [:brendan]]

Attachment: even more partial fix (for "take 2" item 2 from my original comment); avoid recycling too big an arena, based on pool->arenasize and nb

Comment 14

[larryh (gone)]

PL_ArenaAllocate() gives me a headache. The nested while() in the for() ... So, 
I'm slow.

Should this function be re-written to express the intent:

Allocate the requested bytes from pool.
Failing that, find an arena where pool->arenasize == freelist-arena.arenasize.
Failing that, find an arena where pool->arenasize < freelist-arena.arenasize.
Really: current arenas in pool, then exact fit in freelist, then first fit in 
freelist.

Comment 15

[Brendan Eich [:brendan]]

larryh: have at.  I mucked with js/src/jsarena.c a bit a while ago to get rid of
the early continue case, which seemed evil (much as I like continue to cast out
hard cases) because it cast out the more likely case.  So I swapped cases and
made the "claim:" case continue.  But I don't like this code, even though  I
took pains to emulate the code from the LCC paper cited at the top.

/be

Comment 16

[larryh (gone)]

Yet another thought.
If the adding of arenas to the global freelist is done in arenasize order, then 
a single traversal of the global freelist looking for first fit solves potential 
performance problems of multiple traversals of the freelist. ... Means an 
adjustment to other functions adding to the freelist.

Note: separate loops thru different lists of arenas shortens the lock-held time 
on the global freelist.

Comment 17

[Nelson Bolyard (seldom reads bugmail)]

Brendan:  in your "even more partial fix", sz is uninitialized.

Perhaps you intended for the code to be:

-            if (b->limit - b->base == pool->arenasize) {
+            sz = b->limit - b->base;
+            if ((nb > pool->arenasize)
+                ? sz - nb <= pool->arenasize
+                : sz == pool->arenasize) {

I guess this could be called a "first close fit" algorithm,
when arenasize is small.

Larry observes that if the free list is kept sorted in ascending
order by size, then first fit is also best fit.  I think that's
the right answer.

Comment 18

[Nelson Bolyard (seldom reads bugmail)]

Brendan: re: your comment of 2001-03-26 17:37 about PL_FreeArenaPool
I take it you're suggesting that the proper use for an application that
wants to recycle all the blocks in a pool when about to finish it 
should call PL_FreeArenaPool and then PL_FinishArenaPool, in sequence.
Yes?

In NSS, ArenaPools are used to house ALL the components of certain
types of objects that tend to come and go with some frequency.  
The destructor of those objects merely destroys (finishes) the 
arena that contains ALL the components.  Because of the frequency
with which these objects come and go (e.g., every ssl connection for
some/most of them), I believe it is appropriate to always free the 
arenas in the pool before finishing the pool. 

Perhaps it is also appropriate to limit the number of arenas in 
the free list, to prevent "hoarding". 

Comment 19

[Brendan Eich [:brendan]]

Oops, my patch was missing a line -- I just don't love plarena.c as much as
jsarena.c, which has always had that missing line.

nelsonb, I think you'll need some bound on memory held by the arena freelist.  I
like larryh's sorted freelist, so long as the list is short-ish.  Anyone have
numbers for likely average and max length of the freelist?

/be

Comment 20

[Brendan Eich [:brendan]]

Attachment: corrected version of last patch, for posterity

Comment 21

[larryh (gone)]

Attachment: patch rewriting PL_ArenaAllocate(), et.al.

Comment 22

[larryh (gone)]

See attachment 4 [details] [diff] [review]/3/2001.
The patch fixes some of the noted problems.
This patch also sets causes PL_ArenaRelease()and PL_FreeArenaPool() to place 
arenas in the pool being operated upon to actually go on the freelist(1).

Experiments show some relief from pressure on malloc() when using arenas. 
WebServer 6.0 wants this a lot.

Comment 23

[larryh (gone)]

Checking in lib/ds/plarena.c;
/cvsroot/mozilla/nsprpub/lib/ds/plarena.c,v  <--  plarena.c
new revision: 3.7; previous revision: 3.6
done
Checking in lib/tests/Makefile;
/cvsroot/mozilla/nsprpub/lib/tests/Makefile,v  <--  Makefile
new revision: 3.18; previous revision: 3.17
done
Checking in lib/tests/arena.c;
/cvsroot/mozilla/nsprpub/lib/tests/arena.c,v  <--  arena.c
new revision: 3.6; previous revision: 3.5
done

Comment 24

[larryh (gone)]

Revisit #1 in the first part.

Comment 25

[jim_nance]

I just got an assertion on what I think should be legal code.  Here is where the
problem is:

PR_IMPLEMENT(void *) PL_ArenaAllocate(PLArenaPool *pool, PRUint32 nb)
{
    PLArena *a;
    char *rp;     /* returned pointer */

    PR_ASSERT((nb & pool->mask) == 0);

    nb = (PRUword)PL_ARENA_ALIGN(pool, nb); /* force alignment */

Note that we force the allignment after we have done the PR_ASSERT to ensure
that the alignment is OK.  I think these last two lines should be swapped.
Or do we want all the callers to have to align things themselves?  I dont see
how that could be good, but perhaps there is a reason.

Comment 26

[Wan-Teh Chang]

You should use the PL_ARENA_ALLOCATE macro.  Don't
call the PL_ArenaAllocate function directly.

Comment 27

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee didn't login in Bugzilla in the last 7 months and this bug has priority 'P1'.
:KaiE, could you have a look please?
For more information, please visit auto_nag documentation.