Subject: Re: free page management
To: Jason Thorpe <>
From: Chris G. Demetriou <>
List: tech-kern
Date: 03/10/1997 19:39:52
Jason Thorpe said:
> However, the way free pages are managed by the VM system isn't terribly
> conducive to flexible allocation policies.  It's designed to grab a page,
> quickly, from a free list, which is currently fine for 100% of the cases of
> post-bootstrap dynamic memory allocation in the kernel (there are some
> special hacks for dynamic memory allocation before the VM system is
> bootstrapped, but the pages those allocators allocate are not managed).

So, what you're suggesting is to add overhead to the (very) common
case for what's hoped to be infrequent operations on a
hopefully-decreasing set of architectures?

It sounds like you're optimizing for the wrong thing, here...

I'm also concerned that since the implementation of the extent manager
involves potentially long linear linked list searches, each extent
manager call could be ... painfully slow, adding to the overall added

You've obviously implemented this, have you run any tests to see how
this performs in various conditions (e.g. compile on small-memory
machine, compile on medium-memory machine, and compile in large-memory

> So, the obvious right thing to do here is to use an extent map to track
> free/allocated managed pages.  However, there's a problem with this... the
> vm_page structures on the free/active/inactive lists contain a great deal
> more information than just address of the page, such as the associated
> object, dirty bits, etc.

Obviously, optimization is premature, but i'm concerned about the
possibility of expensive, repetitive lookups (e.g. you pull the thing
off the head of the free list, and have to do a long linear lookup to
find it in the extent map, you pull the next thing off the free list
and have to do the same thing).

It sounds like you really want to be able to associate an vm_page with
an extent region descriptor and vice-versa, and easily be able to
insert/extract entries from the free page list & extent map.
To me, it sounds like using the extent map here is very wrong since
you don't want to have to pay the costs of keeping the data structures

I'd say that what you really want might be a #-of-managed-pages-long
bitmap, which marks pages as in-use or not.  with something like that,
you can easily find available regions, mark pages in-use or
not-in-use, and translate from "available page" to vm_page structure
and vice-versa...