Reprinted from: _P_r_o_c_e_e_d_i_n_g_s _o_f _t_h_e _S_a_n _F_r_a_n_c_i_s_c_o _U_S_E_N_I_X _C_o_n_- _f_e_r_e_n_c_e, pp. 295-303, June 1988. DDeessiiggnn ooff aa GGeenneerraall PPuurrppoossee MMeemmoorryy AAllllooccaattoorr ffoorr tthhee 44..33BBSSDD UUNNIIXX||-- KKeerrnneell _M_a_r_s_h_a_l_l _K_i_r_k _M_c_K_u_s_i_c_k _M_i_c_h_a_e_l _J_. _K_a_r_e_l_s Computer Systems Research Group Computer Science Division Department of Electrical Engineering and Computer Science University of California, Berkeley Berkeley, California 94720 _A_B_S_T_R_A_C_T The 4.3BSD UNIX kernel uses many memory allo- cation mechanisms, each designed for the particu- lar needs of the utilizing subsystem. This paper describes a general purpose dynamic memory alloca- tor that can be used by all of the kernel subsys- tems. The design of this allocator takes advan- tage of known memory usage patterns in the UNIX kernel and a hybrid strategy that is time-effi- cient for small allocations and space-efficient for large allocations. This allocator replaces the multiple memory allocation interfaces with a single easy-to-program interface, results in more efficient use of global memory by eliminating par- titioned and specialized memory pools, and is quick enough that no performance loss is observed relative to the current implementations. The paper concludes with a discussion of our experi- ence in using the new memory allocator, and direc- tions for future work. 11.. KKeerrnneell MMeemmoorryy AAllllooccaattiioonn iinn 44..33BBSSDD The 4.3BSD kernel has at least ten different memory allocators. Some of them handle large blocks, some of them handle small chained data structures, and others include information to describe I/O operations. Often the alloca- tions are for small pieces of memory that are only needed for the duration of a single system call. In a user process such short-term memory would be allocated on the run-time stack. Because the kernel has a limited run-time stack, it ----------- |-UNIX is a registered trademark of AT&T in the US and other countries. Summer USENIX '88 295 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels is not feasible to allocate even moderate blocks of memory on it. Consequently, such memory must be allocated through a more dynamic mechanism. For example, when the system must translate a pathname, it must allocate a one kilobye buffer to hold the name. Other blocks of memory must be more per- sistent than a single system call and really have to be allocated from dynamic memory. Examples include protocol control blocks that remain throughout the duration of the network connection. Demands for dynamic memory allocation in the kernel have increased as more services have been added. Each time a new type of memory allocation has been required, a spe- cialized memory allocation scheme has been written to handle it. Often the new memory allocation scheme has been built on top of an older allocator. For example, the block device subsystem provides a crude form of memory allocation through the allocation of empty buffers [Thompson78]. The alloca- tion is slow because of the implied semantics of finding the oldest buffer, pushing its contents to disk if they are dirty, and moving physical memory into or out of the buffer to create the requested size. To reduce the overhead, a ``new'' memory allocator was built in 4.3BSD for name trans- lation that allocates a pool of empty buffers. It keeps them on a free list so they can be quickly allocated and freed [McKusick85]. This memory allocation method has several drawbacks. First, the new allocator can only handle a limited range of sizes. Second, it depletes the buffer pool, as it steals memory intended to buffer disk blocks to other purposes. Finally, it creates yet another interface of which the pro- grammer must be aware. A generalized memory allocator is needed to reduce the complexity of writing code inside the kernel. Rather than providing many semi-specialized ways of allocating memory, the kernel should provide a single general purpose alloca- tor. With only a single interface, programmers do not need to figure out the most appropriate way to allocate memory. If a good general purpose allocator is available, it helps avoid the syndrome of creating yet another special purpose allocator. To ease the task of understanding how to use it, the memory allocator should have an interface similar to the interface of the well-known memory allocator provided for applications programmers through the C library routines _m_a_l_l_o_c() and _f_r_e_e(). Like the C library interface, the allocation routine should take a parameter specifying the size of memory that is needed. The range of sizes for mem- ory requests should not be constrained. The free routine should take a pointer to the storage being freed, and should not require additional information such as the size of the Summer USENIX '88 296 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... piece of memory being freed. 22.. CCrriitteerriiaa ffoorr aa KKeerrnneell MMeemmoorryy AAllllooccaattoorr The design specification for a kernel memory allocator is similar to, but not identical to, the design criteria for a user level memory allocator. The first criterion for a memory allocator is that it make good use of the physical memory. Good use of memory is measured by the amount of memory needed to hold a set of allocations at any point in time. Percentage utilization is expressed as: _u_t_i_l_i_z_a_t_i_o_n=_r___e_r___q_e___u_q___e_u___s_i___t_r___e_e___d_d__ Here, ``requested'' is the sum of the memory that has been requested and not yet freed. ``Required'' is the amount of memory that has been allocated for the pool from which the requests are filled. An allocator requires more memory than requested because of fragmentation and a need to have a ready supply of free memory for future requests. A perfect memory allocator would have a utilization of 100%. In prac- tice, having a 50% utilization is considered good [Korn85]. Good memory utilization in the kernel is more important than in user processes. Because user processes run in vir- tual memory, unused parts of their address space can be paged out. Thus pages in the process address space that are part of the ``required'' pool that are not being ``requested'' need not tie up physical memory. Because the kernel is not paged, all pages in the ``required'' pool are held by the kernel and cannot be used for other purposes. To keep the kernel utilization percentage as high as possi- ble, it is desirable to release unused memory in the ``required'' pool rather than to hold it as is typically done with user processes. Because the kernel can directly manipulate its own page maps, releasing unused memory is fast; a user process must do a system call to release mem- ory. The most important criterion for a memory allocator is that it be fast. Because memory allocation is done fre- quently, a slow memory allocator will degrade the system performance. Speed of allocation is more critical when exe- cuting in the kernel than in user code, because the kernel must allocate many data structure that user processes can allocate cheaply on their run-time stack. In addition, the kernel represents the platform on which all user processes run, and if it is slow, it will degrade the performance of every process that is running. Another problem with a slow memory allocator is that programmers of frequently-used kernel interfaces will feel that they cannot afford to use it as their primary memory allocator. Instead they will build their own memory Summer USENIX '88 297 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels allocator on top of the original by maintaining their own pool of memory blocks. Multiple allocators reduce the effi- ciency with which memory is used. The kernel ends up with many different free lists of memory instead of a single free list from which all allocation can be drawn. For example, consider the case of two subsystems that need memory. If they have their own free lists, the amount of memory tied up in the two lists will be the sum of the greatest amount of memory that each of the two subsystems has ever used. If they share a free list, the amount of memory tied up in the free list may be as low as the greatest amount of memory that either subsystem used. As the number of subsystems grows, the savings from having a single free list grow. 33.. EExxiissttiinngg UUsseerr--lleevveell IImmpplleemmeennttaattiioonnss There are many different algorithms and implementations of user-level memory allocators. A survey of those avail- able on UNIX systems appeared in [Korn85]. Nearly all of the memory allocators tested made good use of memory, though most of them were too slow for use in the kernel. The fastest memory allocator in the survey by nearly a factor of two was the memory allocator provided on 4.2BSD originally written by Chris Kingsley at California Institute of Tech- nology. Unfortunately, the 4.2BSD memory allocator also wasted twice as much memory as its nearest competitor in the survey. The 4.2BSD user-level memory allocator works by main- taining a set of lists that are ordered by increasing powers of two. Each list contains a set of memory blocks of its corresponding size. To fulfill a memory request, the size of the request is rounded up to the next power of two. A piece of memory is then removed from the list corresponding to the specified power of two and returned to the requester. Thus, a request for a block of memory of size 53 returns a block from the 64-sized list. A typical memory allocation requires a roundup calculation followed by a linked list removal. Only if the list is empty is a real memory alloca- tion done. The free operation is also fast; the block of memory is put back onto the list from which it came. The correct list is identified by a size indicator stored imme- diately preceding the memory block. 44.. CCoonnssiiddeerraattiioonnss UUnniiqquuee ttoo aa KKeerrnneell AAllllooccaattoorr 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 mem- ory 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 Summer USENIX '88 298 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... kernel can statically allocate a set of data structures to manage its dynamically allocated memory. These data struc- tures 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 effi- ciently 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 alloca- tor 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. 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 sin- gle 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 mem- ory, 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 instan- taneous 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 ----------- |-One might seriously ask the question what good it is if ``only'' one subsystem within the kernel hangs if it is something like the network on a diskless workstation. Summer USENIX '88 299 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels +---------------------------------------+ | 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 \*(Lb. \*(Lt hold the superblock for a mounted file system. Thus, a mem- ory allocator only needs to be fast for small pieces of mem- ory. 55.. IImmpplleemmeennttaattiioonn ooff tthhee KKeerrnneell MMeemmoorryy AAllllooccaattoorr In reviewing the available memory allocators, none of their strategies could be used without some modification. The kernel memory allocator that we ended up with is a hybrid of the fast memory allocator found in the 4.2BSD C library and a slower but more-memory-efficient first-fit allocator. Summer USENIX '88 300 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... Small allocations are done using the 4.2BSD power-of- two list strategy; the typical allocation requires only a computation of the list to use and the removal of an element if it is available, so it is quite fast. Macros are pro- vided to avoid the cost of a subroutine call. Only if the request cannot be fulfilled from a list is a call made to the allocator itself. To ensure that the allocator is always called for large requests, the lists corresponding to large allocations are always empty. Appendix A shows the data structures and implementation of the macros. Similarly, freeing a block of memory can be done with a macro. The macro computes the list on which to place the request and puts it there. The free routine is called only if the block of memory is considered to be a large alloca- tion. Including the cost of blocking out interrupts, the allocation and freeing macros generate respectively only nine and sixteen (simple) VAX instructions. Because of the inefficiency of power-of-two allocation strategies for large allocations, a different strategy is used for allocations larger than two kilobytes. The selec- tion of two kilobytes is derived from our statistics on the utilization of memory within the kernel, that showed that 95 to 98% of allocations are of size one kilobyte or less. A frequent caller of the memory allocator (the name transla- tion function) always requests a one kilobyte block. Addi- tionally the allocation method for large blocks is based on allocating pieces of memory in multiples of pages. Conse- quently the actual allocation size for requests of size 2x_p_a_g_e_s_i_z_e or less are identical.|- In 4.3BSD on the VAX, the (software) page size is one kilobyte, so two kilobytes is the smallest logical cutoff. Large allocations are first rounded up to be a multiple of the page size. The allocator then uses a first-fit algo- rithm to find space in the kernel address arena set aside for dynamic allocations. Thus a request for a five kilobyte piece of memory will use exactly five pages of memory rather than eight kilobytes as with the power-of-two allocation strategy. When a large piece of memory is freed, the memory pages are returned to the free memory pool, and the address ----------- |-To understand why this number is 2x_p_a_g_e_s_i_z_e one observes that the power-of-two algorithm yields sizes of 1, 2, 4, 8, ... pages while the large block algorithm that allocates in multiples of pages yields sizes of 1, 2, 3, 4, ... pages. Thus for allocations of sizes between one and two pages both algorithms use two pages; it is not until allocations of sizes between two and three pages that a difference emerges where the power-of-two algorithm will use four pages while the large block algorithm will use three pages. Summer USENIX '88 301 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels space is returned to the kernel address arena where it is coalesced with adjacent free pieces. Another technique to improve both the efficiency of memory utilization and the speed of allocation is to cluster same-sized small allocations on a page. When a list for a power-of-two allocation is empty, a new page is allocated and divided into pieces of the needed size. This strategy speeds future allocations as several pieces of memory become available as a result of the call into the allocator. ker|nel|+m+e+mo+ry|pa|ges| |++++++| | ++++ | | | char *kmembase+--+--+---+--+--+--+--+---+--+--+--+--+---+--++++ kmemsizes[] = 1{024,256,512,3072c,oncto,nt,128,128,freec,ont,1281,024f,ree,contc,ont, Legend: free - unused page cont - continuation of previous page Usage: memscihzaer(a*daddrd)r; { return(kmemsizes[(addr - kmembase) - PAGESIZE]); } \.in 0 \.ce \*(Lb. \*(Lt Because the size is not specified when a block of mem- ory is freed, the allocator must keep track of the sizes of the pieces it has handed out. The 4.2BSD user-level alloca- tor stores the size of each block in a header just before the allocation. However, this strategy doubles the memory requirement for allocations that require a power-of-two- sized block. Therefore, instead of storing the size of each piece of memory with the piece itself, the size information is associated with the memory page. Figure 2 shows how the kernel determines the size of a piece of memory that is being freed, by calculating the page in which it resides, and looking up the size associated with that page. Elimi- nating the cost of the overhead per piece improved utiliza- tion far more than expected. The reason is that many allo- cations in the kernel are for blocks of memory whose size is exactly a power of two. These requests would be nearly dou- bled if the user-level strategy were used. Now they can be accommodated with no wasted memory. The allocator can be called both from the top half of the kernel, which is willing to wait for memory to become available, and from the interrupt routines in the bottom half of the kernel that cannot wait for memory to become available. Clients indicate their willingness (and ability) Summer USENIX '88 302 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... to wait with a flag to the allocation routine. For clients that are willing to wait, the allocator guarrentees that their request will succeed. Thus, these clients can need not check the return value from the allocator. If memory is unavailable and the client cannot wait, the allocator returns a null pointer. These clients must be prepared to cope with this (hopefully infrequent) condition (usually by giving up and hoping to do better later). 66.. RReessuullttss ooff tthhee IImmpplleemmeennttaattiioonn The new memory allocator was written about a year ago. Conversion from the old memory allocators to the new alloca- tor has been going on ever since. Many of the special pur- pose allocators have been eliminated. This list includes _c_a_l_l_o_c(), _w_m_e_m_a_l_l(), and _z_m_e_m_a_l_l(). Many of the special purpose memory allocators built on top of other allocators have also been eliminated. For example, the allocator that was built on top of the buffer pool allocator _g_e_t_e_b_l_k() to allocate pathname buffers in _n_a_m_e_i() has been eliminated. Because the typical allocation is so fast, we have found that none of the special purpose pools are needed. Indeed, the allocation is about the same as the previous cost of allocating buffers from the network pool (_m_b_u_fs). Conse- quently applications that used to allocate network buffers for their own uses have been switched over to using the gen- eral purpose allocator without increasing their running time. Quantifying the performance of the allocator is diffi- cult because it is hard to measure the amount of time spent allocating and freeing memory in the kernel. The usual approach is to compile a kernel for profiling and then com- pare the running time of the routines that implemented the old abstraction versus those that implement the new one. The old routines are difficult to quantify because individ- ual routines were used for more than one purpose. For exam- ple, the _g_e_t_e_b_l_k() routine was used both to allocate one kilobyte memory blocks and for its intended purpose of pro- viding buffers to the filesystem. Differentiating these uses is often difficult. To get a measure of the cost of memory allocation before putting in our new allocator, we summed up the running time of all the routines whose exclu- sive task was memory allocation. To this total we added the fraction of the running time of the multi-purpose routines that could clearly be identified as memory allocation usage. This number showed that approximately three percent of the time spent in the kernel could be accounted to memory allo- cation. The new allocator is difficult to measure because the usual case of the memory allocator is implemented as a macro. Thus, its running time is a small fraction of the running time of the numerous routines in the kernel that use Summer USENIX '88 303 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels it. To get a bound on the cost, we changed the macro always to call the memory allocation routine. Running in this mode, the memory allocator accounted for six percent of the time spent in the kernel. Factoring out the cost of the statistics collection and the subroutine call overhead for the cases that could normally be handled by the macro, we estimate that the allocator would account for at most four percent of time in the kernel. These measurements show that the new allocator does not introduce significant new run- time costs. The other major success has been in keeping the size information on a per-page basis. This technique allows the most frequently requested sizes to be allocated without waste. It also reduces the amount of bookkeeping informa- tion associated with the allocator to four kilobytes of information per megabyte of memory under management (with a one kilobyte page size). 77.. FFuuttuurree WWoorrkk Our next project is to convert many of the static ker- nel tables to be dynamically allocated. Static tables include the process table, the file table, and the mount table. Making these tables dynamic will have two benefits. First, it will reduce the amount of memory that must be statically allocated at boot time. Second, it will elimi- nate the arbitrary upper limit imposed by the current static sizing (although a limit will be retained to constrain run- away clients). Other researchers have already shown the memory savings achieved by this conversion [Rodriguez88]. Under the current implementation, memory is never moved from one size list to another. With the 4.2BSD memory allo- cator this causes problems, particularly for large alloca- tions where a process may use a quarter megabyte piece of memory once, which is then never available for any other size request. In our hybrid scheme, memory can be shuffled between large requests so that large blocks of memory are never stranded as they are with the 4.2BSD allocator. How- ever, pages allocated to small requests are allocated once to a particular size and never changed thereafter. If a burst of requests came in for a particular size, that size would acquire a large amount of memory that would then not be available for other future requests. In practice, we do not find that the free lists become too large. However, we have been investigating ways to han- dle such problems if they occur in the future. Our current investigations involve a routine that can run as part of the idle loop that would sort the elements on each of the free lists into order of increasing address. Since any given page has only one size of elements allocated from it, the effect of the sorting would be to sort the list into Summer USENIX '88 304 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... distinct pages. When all the pieces of a page became free, the page itself could be released back to the free pool so that it could be allocated to another purpose. Although there is no guarantee that all the pieces of a page would ever be freed, most allocations are short-lived, lasting only for the duration of an open file descriptor, an open network connection, or a system call. As new allocations would be made from the page sorted to the front of the list, return of elements from pages at the back would eventually allow pages later in the list to be freed. Two of the traditional UNIX memory allocators remain in the current system. The terminal subsystem uses _c_l_i_s_ts (character lists). That part of the system is expected to undergo major revision within the next year or so, and it will probably be changed to use _m_b_u_fs as it is merged into the network system. The other major allocator that remains is _g_e_t_b_l_k(), the routine that manages the filesystem buffer pool memory and associated control information. Only the filesystem uses _g_e_t_b_l_k() in the current system; it manages the constant-sized buffer pool. We plan to merge the filesystem buffer cache into the virtual memory system's page cache in the future. This change will allow the size of the buffer pool to be changed according to memory load, but will require a policy for balancing memory needs with filesystem cache performance. 88.. AAcckknnoowwlleeddggmmeennttss In the spirit of community support, we have made vari- ous versions of our allocator available to our test sites. They have been busily burning it in and giving us feedback on their experiences. We acknowledge their invaluable input. The feedback from the Usenix program committee on the initial draft of our paper suggested numerous important improvements. 99.. RReeffeerreenncceess Korn85 David Korn, Kiem-Phong Vo, ``In Search of a Better Malloc'' _P_r_o_c_e_e_d_i_n_g_s _o_f _t_h_e _P_o_r_t_l_a_n_d _U_s_e_n_i_x _C_o_n_f_e_r_e_n_c_e, pp 489-506, June 1985. McKusick85 M. McKusick, M. Karels, S. Leffler, ``Perfor- mance Improvements and Functional Enhancements in 4.3BSD'' _P_r_o_c_e_e_d_i_n_g_s _o_f _t_h_e _P_o_r_t_l_a_n_d _U_s_e_n_i_x _C_o_n_f_e_r_e_n_c_e, pp 519-531, June 1985. Rodriguez88 Robert Rodriguez, Matt Koehler, Larry Palmer, Ricky Palmer, ``A Dynamic UNIX Operating Sys- tem'' _P_r_o_c_e_e_d_i_n_g_s _o_f _t_h_e _S_a_n _F_r_a_n_c_i_s_c_o _U_s_e_n_i_x _C_o_n_f_e_r_e_n_c_e, June 1988. Summer USENIX '88 305 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels Thompson78 Ken Thompson, ``UNIX Implementation'' _B_e_l_l _S_y_s_- _t_e_m _T_e_c_h_n_i_c_a_l _J_o_u_r_n_a_l, volume 57, number 6, pp 1931-1946, 1978. Summer USENIX '88 306 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... 11110000.... AAAAppppppppeeeennnnddddiiiixxxx AAAA ---- IIIImmmmpppplllleeeemmmmeeeennnnttttaaaattttiiiioooonnnn DDDDeeeettttaaaaiiiillllssss _/_* _* _C_o_n_s_t_a_n_t_s _f_o_r _s_e_t_t_i_n_g _t_h_e _p_a_r_a_m_e_t_e_r_s _o_f _t_h_e _k_e_r_n_e_l _m_e_m_o_r_y _a_l_l_o_c_a_t_o_r_. _* _* _2 _*_* _M_I_N_B_U_C_K_E_T _i_s _t_h_e _s_m_a_l_l_e_s_t _u_n_i_t _o_f _m_e_m_o_r_y _t_h_a_t _w_i_l_l _b_e _* _a_l_l_o_c_a_t_e_d_. _I_t _m_u_s_t _b_e _a_t _l_e_a_s_t _l_a_r_g_e _e_n_o_u_g_h _t_o _h_o_l_d _a _p_o_i_n_t_e_r_. _* _* _U_n_i_t_s _o_f _m_e_m_o_r_y _l_e_s_s _o_r _e_q_u_a_l _t_o _M_A_X_A_L_L_O_C_S_A_V_E _w_i_l_l _p_e_r_m_a_n_e_n_t_l_y _* _a_l_l_o_c_a_t_e _p_h_y_s_i_c_a_l _m_e_m_o_r_y_; _r_e_q_u_e_s_t_s _f_o_r _t_h_e_s_e _s_i_z_e _p_i_e_c_e_s _o_f _m_e_m_o_r_y _* _a_r_e _q_u_i_t_e _f_a_s_t_. _A_l_l_o_c_a_t_i_o_n_s _g_r_e_a_t_e_r _t_h_a_n _M_A_X_A_L_L_O_C_S_A_V_E _m_u_s_t _* _a_l_w_a_y_s _a_l_l_o_c_a_t_e _a_n_d _f_r_e_e _p_h_y_s_i_c_a_l _m_e_m_o_r_y_; _r_e_q_u_e_s_t_s _f_o_r _t_h_e_s_e _s_i_z_e _* _a_l_l_o_c_a_t_i_o_n_s _s_h_o_u_l_d _b_e _d_o_n_e _i_n_f_r_e_q_u_e_n_t_l_y _a_s _t_h_e_y _w_i_l_l _b_e _s_l_o_w_. _* _C_o_n_s_t_r_a_i_n_t_s_: _C_L_B_Y_T_E_S _<_= _M_A_X_A_L_L_O_C_S_A_V_E _<_= _2 _*_* _(_M_I_N_B_U_C_K_E_T _+ _1_4_) _* _a_n_d _M_A_X_A_L_L_O_C_S_I_Z_E _m_u_s_t _b_e _a _p_o_w_e_r _o_f _t_w_o_. _*_/ ####ddddeeeeffffiiiinnnneeee MINBUCKET 4 _/_* _4 _=_> _m_i_n _a_l_l_o_c_a_t_i_o_n _o_f _1_6 _b_y_t_e_s _*_/ ####ddddeeeeffffiiiinnnneeee MAXALLOCSAVE (2 _* CLBYTES) _M_A_X_A_L_L_O_C_S_A_V_E _/_* _* _M_a_x_i_m_u_m _a_m_o_u_n_t _o_f _k_e_r_n_e_l _d_y_n_a_m_i_c _m_e_m_o_r_y_. _* _C_o_n_s_t_r_a_i_n_t_s_: _m_u_s_t _b_e _a _m_u_l_t_i_p_l_e _o_f _t_h_e _p_a_g_e_s_i_z_e_. _*_/ ####ddddeeeeffffiiiinnnneeee MAXKMEM (1024 _* PAGESIZE) _M_A_X_K_M_E_M _/_* _* _A_r_e_n_a _f_o_r _a_l_l _k_e_r_n_e_l _d_y_n_a_m_i_c _m_e_m_o_r_y _a_l_l_o_c_a_t_i_o_n_. _* _T_h_i_s _a_r_e_n_a _i_s _k_n_o_w_n _t_o _s_t_a_r_t _o_n _a _p_a_g_e _b_o_u_n_d_a_r_y_. _*_/ eeeexxxxtttteeeerrrrnnnn cccchhhhaaaarrrr kmembase[MAXKMEM]; _/_* _* _A_r_r_a_y _o_f _d_e_s_c_r_i_p_t_o_r_s _t_h_a_t _d_e_s_c_r_i_b_e _t_h_e _c_o_n_t_e_n_t_s _o_f _e_a_c_h _p_a_g_e _*_/ ssssttttrrrruuuucccctttt kmemsizes {{{{ sssshhhhoooorrrrtttt ks-indx; _/_* _b_u_c_k_e_t _i_n_d_e_x_, _s_i_z_e _o_f _s_m_a_l_l _a_l_l_o_c_a_t_i_o_n_s _*_/ u-short ks-pagecnt; _/_* _f_o_r _l_a_r_g_e _a_l_l_o_c_a_t_i_o_n_s_, _p_a_g_e_s _a_l_l_o_c_a_t_e_d _*_/ }}}} kmemsizes[MAXKMEM _/ PAGESIZE]; _/_* _* _S_e_t _o_f _b_u_c_k_e_t_s _f_o_r _e_a_c_h _s_i_z_e _o_f _m_e_m_o_r_y _b_l_o_c_k _t_h_a_t _i_s _r_e_t_a_i_n_e_d _*_/ ssssttttrrrruuuucccctttt kmembuckets {{{{ caddr-t kb-next; _/_* _l_i_s_t _o_f _f_r_e_e _b_l_o_c_k_s _*_/ }}}} bucket[MINBUCKET + 16]; Summer USENIX '88 307 San Francisco, June 20-24 Design of a General Purpose Memory ... McKusick, Karels _/_* _* _M_a_c_r_o _t_o _c_o_n_v_e_r_t _a _s_i_z_e _t_o _a _b_u_c_k_e_t _i_n_d_e_x_. _I_f _t_h_e _s_i_z_e _i_s _c_o_n_s_t_a_n_t_, _* _t_h_i_s _m_a_c_r_o _r_e_d_u_c_e_s _t_o _a _c_o_m_p_i_l_e _t_i_m_e _c_o_n_s_t_a_n_t_. _*_/ ####ddddeeeeffffiiiinnnneeee MINALLOCSIZE (1 << MINBUCKET) _M_I_N_A_L_L_O_C_S_I_Z_E ####ddddeeeeffffiiiinnnneeee BUCKETINDX(size) \ _B_U_C_K_E_T_I_N_D_X (size) <= (MINALLOCSIZE _* 128) \ ? (size) <= (MINALLOCSIZE _* 8) \ ? (size) <= (MINALLOCSIZE _* 2) \ ? (size) <= (MINALLOCSIZE _* 1) \ ? (MINBUCKET + 0) \ : (MINBUCKET + 1) \ : (size) <= (MINALLOCSIZE _* 4) \ ? (MINBUCKET + 2) \ : (MINBUCKET + 3) \ : (size) <= (MINALLOCSIZE_* 32) \ ? (size) <= (MINALLOCSIZE _* 16) \ ? (MINBUCKET + 4) \ : (MINBUCKET + 5) \ : (size) <= (MINALLOCSIZE _* 64) \ ? (MINBUCKET + 6) \ : (MINBUCKET + 7) \ : (size) <= (MINALLOCSIZE _* 2048) \ _/_* _e_t_c _._._. _*_/ _/_* _* _M_a_c_r_o _v_e_r_s_i_o_n_s _f_o_r _t_h_e _u_s_u_a_l _c_a_s_e_s _o_f _m_a_l_l_o_c_/_f_r_e_e _*_/ ####ddddeeeeffffiiiinnnneeee MALLOC(space, cast, size, flags) {{{{ \ _M_A_L_L_O_C rrrreeeeggggiiiisssstttteeeerrrr ssssttttrrrruuuucccctttt kmembuckets _*kbp = &bucket[BUCKETINDX(size)]; \ lllloooonnnngggg s = splimp(); \ iiiiffff (kbp->kb-next == NULL) {{{{ \ (space) = (cast)malloc(size, flags); \ }}}} eeeellllsssseeee {{{{ \ (space) = (cast)kbp->kb-next; \ kbp->kb-next = _*(caddr-t _*)(space); \ }}}} \ splx(s); \ }}}} ####ddddeeeeffffiiiinnnneeee FREE(addr) {{{{ \ _F_R_E_E rrrreeeeggggiiiisssstttteeeerrrr ssssttttrrrruuuucccctttt kmembuckets _*kbp; \ rrrreeeeggggiiiisssstttteeeerrrr ssssttttrrrruuuucccctttt kmemsizes _*ksp = \ &kmemsizes[((addr) - kmembase) _/ PAGESIZE]; \ lllloooonnnngggg s = splimp(); \ iiiiffff (1 << ksp->ks-indx > MAXALLOCSAVE) {{{{ \ free(addr); \ }}}} eeeellllsssseeee {{{{ \ kbp = &bucket[ksp->ks-indx]; \ _*(caddr-t _*)(addr) = kbp->kb-next; \ kbp->kb-next = (caddr-t)(addr); \ }}}} \ splx(s); \ }}}} Summer USENIX '88 308 San Francisco, June 20-24 McKusick, Karels Design of a General Purpose Memory ... Summer USENIX '88 309 San Francisco, June 20-24