malloc design assumptions
Jonathan S. Shapiro
Thu, 30 Apr 1998 16:59:10 -0400
I should articulate some assumptions behind the proposed malloc()
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.
+ 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
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