Lines Matching +full:in +full:- +full:kernel

4 .\" Redistribution and use in source and binary forms, with or without
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\"    notice, this list of conditions and the following disclaimer in the
19 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68 pp. 295-303, June 1988.
74 Design of a General Purpose Memory Allocator for the 4.3BSD UNIX\(dg Kernel
81 \(dgUNIX is a registered trademark of AT&T in the US and other countries.
94 The 4.3BSD UNIX kernel uses many memory allocation mechanisms,
97 that can be used by all of the kernel subsystems.
99 patterns in the UNIX kernel and a hybrid strategy that is time-efficient
100 for small allocations and space-efficient for large allocations.
102 with a single easy-to-program interface,
103 results in more efficient use of global memory by eliminating
107 The paper concludes with a discussion of our experience in using
112 .H 1 "Kernel Memory Allocation in 4.3BSD
114 The 4.3BSD kernel has at least ten different memory allocators.
120 In a user process such short-term
121 memory would be allocated on the run-time stack.
122 Because the kernel has a limited run-time stack,
133 Demands for dynamic memory allocation in the kernel have increased
145 To reduce the overhead, a ``new'' memory allocator was built in 4.3BSD
158 of writing code inside the kernel.
159 Rather than providing many semi-specialized ways of allocating memory,
160 the kernel should provide a single general purpose allocator.
170 of the well-known memory allocator provided for
182 .H 1 "Criteria for a Kernel Memory Allocator
184 The design specification for a kernel memory allocator is similar to,
190 a set of allocations at any point in time.
213 Good memory utilization in the kernel is more important than
215 Because user processes run in virtual memory,
217 Thus pages in the process address space
220 Because the kernel is not paged,
221 all pages in the ``required'' pool are held by the kernel and
223 To keep the kernel utilization percentage as high as possible,
224 it is desirable to release unused memory in the ``required'' pool
226 Because the kernel can directly manipulate its own page maps,
233 Speed of allocation is more critical when executing in the
234 kernel than in user code,
235 because the kernel must allocate many data structure that user
236 processes can allocate cheaply on their run-time stack.
237 In addition, the kernel represents the platform on which all user
243 of frequently-used kernel interfaces will feel that they
248 The kernel ends up with many different free lists of memory
253 the amount of memory tied up in the two lists will be the
257 the amount of memory tied up in the free list may be as low as the
261 .H 1 "Existing User-level Implementations
264 implementations of user-level memory allocators.
265 A survey of those available on UNIX systems appeared in [Korn85].
267 though most of them were too slow for use in the kernel.
268 The fastest memory allocator in the survey by nearly a factor of two
273 as its nearest competitor in the survey.
275 The 4.2BSD user-level memory allocator works by maintaining a set of lists
283 a block from the 64-sized list.
291 .H 1 "Considerations Unique to a Kernel Allocator
294 memory allocator for the kernel that do not apply to a user process
301 Thus, the kernel can statically allocate a set of data structures
316 Another special condition of the kernel memory allocator is that it
319 the kernel can keep an arena of kernel addresses and allocate
322 its address space paged out when they are not in use,
323 except that the kernel can explicitly control the set of pages
325 The result is that the ``working set'' of pages in use by the
326 kernel exactly corresponds to the set of pages that it is really using.
327 .FI "One day memory usage on a Berkeley time-sharing machine"
331 A final special condition that applies to the kernel is that
332 all of the different uses of dynamic memory are known in advance.
335 the kernel can provide allocation limits.
337 no single allocator could starve the rest of the kernel of all
345 one subsystem within the kernel hangs if it is something like the
349 \*(Lb shows the memory usage of the kernel over a one day period
351 The ``In Use'', ``Free'', and ``Mem Use'' fields are instantaneous values;
358 and are typically for long-lived objects
363 .H 1 "Implementation of the Kernel Memory Allocator
367 The kernel memory allocator that we ended up with is a hybrid
368 of the fast memory allocator found in the 4.2BSD C library
369 and a slower but more-memory-efficient first-fit allocator.
371 Small allocations are done using the 4.2BSD power-of-two list strategy;
391 Because of the inefficiency of power-of-two allocation strategies
395 the utilization of memory within the kernel,
401 pieces of memory in multiples of pages.
406 observes that the power-of-two algorithm yields sizes of 1, 2, 4, 8, \&...
407 pages while the large block algorithm that allocates in multiples
412 that a difference emerges where the power-of-two algorithm will use
419 The allocator then uses a first-fit algorithm to find space in the
420 kernel address arena set aside for dynamic allocations.
423 the power-of-two allocation strategy.
426 and the address space is returned to the kernel address arena
431 is to cluster same-sized small allocations on a page.
432 When a list for a power-of-two allocation is empty,
442 The 4.2BSD user-level allocator stores the size of each block
445 require a power-of-two-sized block.
449 \*(Lb shows how the kernel determines
451 by calculating the page in which it resides,
455 The reason is that many allocations in the kernel are for blocks of 
457 These requests would be nearly doubled if the user-level strategy were used.
460 The allocator can be called both from the top half of the kernel,
462 and from the interrupt routines in the bottom half of the kernel
489 to allocate pathname buffers in 
502 and freeing memory in the kernel.
503 The usual approach is to compile a kernel for profiling
514 putting in our new allocator,
518 of the running time of the multi-purpose routines that could
521 the time spent in the kernel could be accounted to memory allocation.
526 numerous routines in the kernel that use it.
529 Running in this mode, the memory allocator accounted for six percent
530 of the time spent in the kernel.
535 at most four percent of time in the kernel.
537 significant new run-time costs.
539 The other major success has been in keeping the size information
540 on a per-page basis.
549 kernel tables to be dynamically allocated.
572 If a burst of requests came in for a particular size,
578 if they occur in the future.
589 most allocations are short-lived, lasting only for the duration of
594 allow pages later in the list to be freed.
597 memory allocators remain in the current system.
609 it manages the constant-sized buffer pool.
611 page cache in the future.
620 They have been busily burning it in and giving
628 David Korn, Kiem-Phong Vo,
629 ``In Search of a Better Malloc''
631 pp 489-506, June 1985.
634 ``Performance Improvements and Functional Enhancements in 4.3BSD''
636 pp 519-531, June 1985.
646 pp 1931-1946, 1978.