There are several special conditions that arise when writing a memory allocator for the kernel that do not apply to a user process memory allocator. First, the maximum memory allocation can be determined at the time that the machine is booted. This number is never more than the amount of physical memory on the machine, and is typically much less since a machine with all its memory dedicated to the operating system is uninteresting to use. Thus, the kernel can statically allocate a set of data structures to manage its dynamically allocated memory. These data structures never need to be expanded to accommodate memory requests; yet, if properly designed, they need not be large. For a user process, the maximum amount of memory that may be allocated is a function of the maximum size of its virtual memory. Although it could allocate static data structures to manage its entire virtual memory, even if they were efficiently encoded they would potentially be huge. The other alternative is to allocate data structures as they are needed. However, that adds extra complications such as new failure modes if it cannot allocate space for additional structures and additional mechanisms to link them all together.
Another special condition of the kernel memory allocator is that it can control its own address space. Unlike user processes that can only grow and shrink their heap at one end, the kernel can keep an arena of kernel addresses and allocate pieces from that arena which it then populates with physical memory. The effect is much the same as a user process that has parts of its address space paged out when they are not in use, except that the kernel can explicitly control the set of pages allocated to its address space. The result is that the ``working set'' of pages in use by the kernel exactly corresponds to the set of pages that it is really using.
+---------------------------------------+ | Memory statistics by bucket size | +---------------------------------------+ | Size In Use Free Requests | +---------------------------------------+ | 128 329 39 3129219 | | 256 0 0 0 | | 512 4 0 16 | | 1024 17 5 648771 | | 2048 13 0 13 | | 2049-4096 0 0 157 | | 4097-8192 2 0 103 | | 8193-16384 0 0 0 | |16385-32768 1 0 1 | +---------------------------------------+
+--------------------------------------------------+ | Memory statistics by type | +--------------------------------------------------+ | Type In Use Mem Use High Use Requests | +--------------------------------------------------+ | mbuf 6 1K 17K 3099066 | | devbuf 13 53K 53K 13 | | socket 37 5K 6K 1275 | | pcb 55 7K 8K 1512 | |routetbl 229 29K 29K 2424 | |fragtbl 0 0K 1K 404 | | zombie 3 1K 1K 24538 | | namei 0 0K 5K 648754 | |ioctlops 0 0K 1K 12 | |superblk 24 34K 34K 24 | | temp 0 0K 8K 258 | +--------------------------------------------------+
A final special condition that applies to the kernel is that all of the different uses of dynamic memory are known in advance. Each one of these uses of dynamic memory can be assigned a type. For each type of dynamic memory that is allocated, the kernel can provide allocation limits. One reason given for having separate allocators is that no single allocator could starve the rest of the kernel of all its available memory and thus a single runaway client could not paralyze the system. By putting limits on each type of memory, the single general purpose memory allocator can provide the same protection against memory starvation.**
Figure 1 shows the memory usage of the kernel over a one day period on a general timesharing machine at Berkeley. The ``In Use'', ``Free'', and ``Mem Use'' fields are instantaneous values; the ``Requests'' field is the number of allocations since system startup; the ``High Use'' field is the maximum value of the ``Mem Use'' field since system startup. The figure demonstrates that most allocations are for small objects. Large allocations occur infrequently, and are typically for long-lived objects such as buffers to hold the superblock for a mounted file system. Thus, a memory allocator only needs to be fast for small pieces of memory.