malloc design assumptions

[Jonathan S. Shapiro]

I should articulate some assumptions behind the proposed malloc()
design:

1. Use of malloc() is bimodal -- the object is either very long
   lived (e.g. a device descriptor) or relatively short lived 
   (e.g. an I/O request block).  The allocator is assumed to keep
   these separated by leveraging the 'usage type' field.

2. The long-lived allocations are invariably during device
   initialization or similar kinds of activities.  My claim is that
   these weren't really the kinds of dynamic allocations whose
   reliability we were concerned about.

   These activities are no longer required to occur at startup time.

3. Allocations of contiguous physical memory regions for direct
   application use is very limited in practice.  While such
   allocations do create islands in physical memory space, the islands 
   should not matter in practice, as they are a small fraction of the
   total available memory.

4. Allocations of physical ranges in support of malloc are *generally*
   long lived.  The exceptions are burst conditions, in which (e.g.) a 
   large number of depend table entries or mbuf's (network structures) 
   are allocated for a brief period of time.

   Some observations:

   + All allocations under burst conditions are entitled to fail
     (i.e. refuse to allocate).

   + There are a small set of object types associated with bursty
     allocation:

		mbufs (networking)
		mclusters (networking)
		depend table entries
		I/O request structures

     in the future I might want to add threads to that list.

   + All burst-allocated objects are short-lived.

   + By relatively simple means (prioritization of allocation), then,
     the "extra" storage can be deallocated by simply marking intent
     to do so and then waiting until the allocated objects are freed.

     Threads would be an exception to this; one would probably need a
     traversal agent to compact a dynamically allocated thread table.

5. All of the dynamically allocated structures that exist in the
   kernel at the moment are already handled through pointers and
   already have associated memory allocators and free list managers.

6. Low water marks can be used to prevent starvation.  This is
   particularly important for I/O structures.

7. Dynamically allocated structures are small relative to the size of
   a page.  This suggests that the low-level malloc can grab
   fixed-length "chunks" of pages for such objects, avoiding
   fragmentation.


shap