4.  Considerations Unique to a Kernel Allocator

      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  |

.in 0 .ce .

      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.