281866 - PL_ArenaAllocate wastes memory, gives large arenas to small requests

Status: RESOLVED DUPLICATE of bug 166701

(NSPR :: NSPR, defect)

Description

[Nelson Bolyard (seldom reads bugmail)]

In short, mixing big arenas and little arenas in a program wastes 
a LOT of memory when the arena free list is in use.  This is a big
problem when CRLs are in use.  I am planning a workaround for NSS.

PR_ArenaAllocate uses a first-fit algorithm to find an arena on the 
free list to satisfy a request for a new arena.  It ensures that 
the arena is big enough, but otherwise does not ensure a good fit.

When arenas are freed, they are added (perhaps as a group) to the 
front of the free list.  So the free list is more-or-less a LIFO
(a stack).  When a very large arena is freed (put on the free list), 
and goes to the head of the free list, it will be picked up by the 
next request for an arena, no matter how small that request may be.  
It may be that the requestor will hold the very large arena for a 
long time, with most of it wasted.

When large arenas get allocated for small requests, then large arenas 
do not remain on the free list to satisfy additional requests for 
large arenas.  So, more large arenas get allocated.  Eventually the 
number of large arenas allocated greatly exceeds the number really 
needed, and a LOT of allocated memory is wasted, causing the process 
to hold much more memory than it needs.  

I can envision several possible solutions to this, including:

a) sort the arena free list in order of ascending arena size.
then the first fit algorithm will also be a best fit algorithm.
Larry tried that once, and we found it slowed things down a lot.

b) break the arena free list up into several lists, each for a
arenas of a different range of sizes, with a ceiling on the largest
size that can be put on any free list.  NSPR's zone allocater uses
this model.  Maybe the PL_Arena code should always use the zone 
allocator, even if/when PR_Malloc does not (for non-arena requests).  

The present PL_Arena API does not allow a user of PLArenaPools 
(such as NSS) to choose a ceiling for arenas that are recycled on 
the free list, nor does it allow the user to individually free some 
arenas in a pool, while recycling others.  It does provide a function 
that always frees (never recycles) the content of an arena pool  The
user can make the free/recycle decision only for the whole arenapool.

I intend to devise a workaround in NSS for this issue.  I will file 
a separate bug (RFE) about that.

Comment 1

[Wan-Teh Chang]

Added the father of PLArena to the cc list.
Perhaps other copies of PLArena could also
use these improvements.  jsarena.c doesn't
seem to address this issue

Comment 2

[Nelson Bolyard (seldom reads bugmail)]

This bug appears to be a dup of 166701.  
The patch attached to that bug was never checked in because 
of some objections (expressed in private email, not attached)
that the solution was less than ideal.  

But this problem is real and real products in the field
are bleeding memory because of it.  It needs to be fixed.

*** This bug has been marked as a duplicate of 166701 ***