Lines Matching full:that
5 .\" modification, are permitted provided that the following conditions
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
105 and is quick enough that no performance loss is observed
118 Often the allocations are for small pieces of memory that are only
130 Examples include protocol control blocks that remain throughout
146 for name translation that allocates a pool of empty buffers.
177 size of memory that is needed.
187 The first criterion for a memory allocator is that it make good use
203 Here, ``requested'' is the sum of the memory that has been requested
205 ``Required'' is the amount of memory that has been
218 that are part of the ``required'' pool that are not
230 The most important criterion for a memory allocator is that it be fast.
235 because the kernel must allocate many data structure that user
240 that is running.
242 Another problem with a slow memory allocator is that programmers
243 of frequently-used kernel interfaces will feel that they
251 consider the case of two subsystems that need memory.
254 sum of the greatest amount of memory that each of
258 greatest amount of memory that either subsystem used.
276 that are ordered by increasing powers of two.
293 There are several special conditions that arise when writing a
294 memory allocator for the kernel that do not apply to a user process
297 the time that the machine is booted.
306 For a user process, the maximum amount of memory that may be allocated
312 However, that adds extra complications such as new
316 Another special condition of the kernel memory allocator is that it
318 Unlike user processes that can only grow and shrink their heap at one end,
320 pieces from that arena which it then populates with physical memory.
321 The effect is much the same as a user process that has parts of
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.
331 A final special condition that applies to the kernel is that
334 For each type of dynamic memory that is allocated,
336 One reason given for having separate allocators is that
355 The figure demonstrates that most
367 The kernel memory allocator that we ended up with is a hybrid
378 To ensure that the allocator is always called for large requests,
396 that showed that 95 to 98% of allocations are of size one kilobyte or less.
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
444 However, this strategy doubles the memory requirement for allocations that
450 the size of a piece of memory that is being freed,
452 and looking up the size associated with that page.
455 The reason is that many allocations in the kernel are for blocks of
463 that cannot wait for memory to become available.
466 For clients that are willing to wait,
467 the allocator guarrentees that their request will succeed.
487 For example, the allocator that was built on top of the buffer pool allocator
493 we have found that none of the special purpose pools are needed.
496 Consequently applications that used to allocate network
504 and then compare the running time of the routines that
505 implemented the old abstraction versus those that implement the new one.
518 of the running time of the multi-purpose routines that could
520 This number showed that approximately three percent of
526 numerous routines in the kernel that use it.
532 subroutine call overhead for the cases that could
534 we estimate that the allocator would account for
536 These measurements show that the new allocator does not introduce
554 that must be statically allocated at boot time.
568 memory can be shuffled between large requests so that large blocks
573 that size would acquire a large amount of memory
574 that would then not be available for other future requests.
576 In practice, we do not find that the free lists become too large.
580 that can run as part of the idle loop that would sort the elements
585 the page itself could be released back to the free pool so that
587 Although there is no guarantee that all the pieces of a page would ever
599 That part of the system is expected to undergo major revision within
602 The other major allocator that remains is
604 the routine that manages the filesystem buffer pool memory