full/empty terminology in _malloc.h

[James Cook]

On Wed, May 19, 2021 at 01:26:24PM +0000, James Cook wrote:
> On Tue, May 18, 2021 at 04:50:36PM -0900, Matthew Dillon wrote:
> > Now onto malloc_mgt_poll_empty_locked().  This code should strictly keep
> > only empty magazines on the empty list and full magazines on the full
> > list.  Any partial magazines will be moved to the partial list.  The order
> > on the empty and full lists shouldn't matter at all.
> > 
> > The partial list is more problematic.  For that we dive into _kmalloc_obj()
> > itself.  It will allocate out of mgt->active first, then mgt->alternate.
> > If both are empty (have no objects available to allocate), then it pulls a
> > slab off of the (per-zone) global ggm->partial list, then ggm->full list,
> > then checks a few ggm->empty elements to see if any happen to have any
> > objects in them (the poller might not have moved them to the appropriate
> > list).
> > 
> > This is the part where we still have a fragmentation issue.  The
> > ggm->partial list is not sorted in any way and it would probably be best if
> > we took the 'most empty' of the slabs from the partial list to make the new
> > active instead of just taking the first one.  Scanning the whole partial
> > list would be expensive, but scanning a couple of slabs off of the partial
> > list might be beneficial.
> > -Matt
> 
> 
> An idea and a bunch of questions.
> 
> 
> Idea:
> 
> In order to quickly find the approximately-most-empty partial bucket,
> how about replacing the "partial" field with an array of "partial"
> buckets, sorted from most empty to must full? E.g.

Another question:

Do you think it's worth doing some offline analysis to figure out the
best policy? I am tempted to dump a bunch of KTR_MEMORY log entries to
a file and then run some simulations.

E.g. maybe it would show scanning the first N elements of the partial
list, as you suggest, is enough.

-- 
James