Lines Matching full:memory

74 Design of a General Purpose Memory Allocator for the 4.3BSD UNIX\(dg Kernel
78 .EH 'Design of a General Purpose Memory ...''McKusick, Karels'
79 .OH 'McKusick, Karels''Design of a General Purpose Memory ...'
94 The 4.3BSD UNIX kernel uses many memory allocation mechanisms,
96 This paper describes a general purpose dynamic memory allocator
98 The design of this allocator takes advantage of known memory usage
101 This allocator replaces the multiple memory allocation interfaces
103 results in more efficient use of global memory by eliminating
104 partitioned and specialized memory pools,
108 the new memory allocator,
112 .H 1 "Kernel Memory Allocation in 4.3BSD
114 The 4.3BSD kernel has at least ten different memory allocators.
118 Often the allocations are for small pieces of memory that are only
121 memory would be allocated on the run-time stack.
123 it is not feasible to allocate even moderate blocks of memory on it.
124 Consequently, such memory must be allocated through a more dynamic mechanism.
128 Other blocks of memory must be more persistent than a single system call
129 and really have to be allocated from dynamic memory.
133 Demands for dynamic memory allocation in the kernel have increased
135 Each time a new type of memory allocation has been required,
136 a specialized memory allocation scheme has been written to handle it.
137 Often the new memory allocation scheme has been built on top
140 memory allocation through the allocation of empty buffers [Thompson78].
143 and moving physical memory into or out of the buffer to create
145 To reduce the overhead, a ``new'' memory allocator was built in 4.3BSD
150 This memory allocation method has several drawbacks.
152 Second, it depletes the buffer pool, as it steals memory intended
157 A generalized memory allocator is needed to reduce the complexity
159 Rather than providing many semi-specialized ways of allocating memory,
163 out the most appropriate way to allocate memory.
169 the memory allocator should have an interface similar to the interface
170 of the well-known memory allocator provided for
177 size of memory that is needed.
178 The range of sizes for memory requests should not be constrained.
181 of the piece of memory being freed.
182 .H 1 "Criteria for a Kernel Memory Allocator
184 The design specification for a kernel memory allocator is similar to,
186 the design criteria for a user level memory allocator.
187 The first criterion for a memory allocator is that it make good use
188 of the physical memory.
189 Good use of memory is measured by the amount of memory needed to hold
203 Here, ``requested'' is the sum of the memory that has been requested
205 ``Required'' is the amount of memory that has been
207 An allocator requires more memory than requested because of fragmentation
208 and a need to have a ready supply of free memory for future requests.
209 A perfect memory allocator would have a utilization of 100%.
213 Good memory utilization in the kernel is more important than
215 Because user processes run in virtual memory,
219 being ``requested'' need not tie up physical memory.
224 it is desirable to release unused memory in the ``required'' pool
227 releasing unused memory is fast;
228 a user process must do a system call to release memory.
230 The most important criterion for a memory allocator is that it be fast.
231 Because memory allocation is done frequently,
232 a slow memory allocator will degrade the system performance.
242 Another problem with a slow memory allocator is that programmers
244 cannot afford to use it as their primary memory allocator.
245 Instead they will build their own memory allocator on top of the
246 original by maintaining their own pool of memory blocks.
247 Multiple allocators reduce the efficiency with which memory is used.
248 The kernel ends up with many different free lists of memory
251 consider the case of two subsystems that need memory.
253 the amount of memory tied up in the two lists will be the
254 sum of the greatest amount of memory that each of
257 the amount of memory tied up in the free list may be as low as the
258 greatest amount of memory that either subsystem used.
264 implementations of user-level memory allocators.
266 Nearly all of the memory allocators tested made good use of memory,
268 The fastest memory allocator in the survey by nearly a factor of two
269 was the memory allocator provided on 4.2BSD originally
272 the 4.2BSD memory allocator also wasted twice as much memory
275 The 4.2BSD user-level memory allocator works by maintaining a set of lists
277 Each list contains a set of memory blocks of its corresponding size.
278 To fulfill a memory request,
280 A piece of memory is then removed from the list corresponding
282 Thus, a request for a block of memory of size 53 returns
284 A typical memory allocation requires a roundup calculation
286 Only if the list is empty is a real memory allocation done.
288 the block of memory is put back onto the list from which it came.
290 immediately preceding the memory block.
294 memory allocator for the kernel that do not apply to a user process
295 memory allocator.
296 First, the maximum memory allocation can be determined at
298 This number is never more than the amount of physical memory on the machine,
300 memory dedicated to the operating system is uninteresting to use.
302 to manage its dynamically allocated memory.
304 expanded to accommodate memory requests;
306 For a user process, the maximum amount of memory that may be allocated
307 is a function of the maximum size of its virtual memory.
309 its entire virtual memory,
316 Another special condition of the kernel memory allocator is that it
320 pieces from that arena which it then populates with physical memory.
327 .FI "One day memory usage on a Berkeley time-sharing machine"
332 all of the different uses of dynamic memory are known in advance.
333 Each one of these uses of dynamic memory can be assigned a type.
334 For each type of dynamic memory that is allocated,
338 its available memory and thus a single runaway
340 By putting limits on each type of memory,
341 the single general purpose memory allocator can provide the same
342 protection against memory starvation.\(dg
349 \*(Lb shows the memory usage of the kernel over a one day period
361 Thus, a memory allocator only needs to be
362 fast for small pieces of memory.
363 .H 1 "Implementation of the Kernel Memory Allocator
365 In reviewing the available memory allocators,
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.
382 Similarly, freeing a block of memory can be done with a macro.
385 The free routine is called only if the block of memory is
395 the utilization of memory within the kernel,
397 A frequent caller of the memory allocator
401 pieces of memory in multiples of pages.
421 Thus a request for a five kilobyte piece of memory will use exactly
422 five pages of memory rather than eight kilobytes as with
424 When a large piece of memory is freed,
425 the memory pages are returned to the free memory pool,
429 Another technique to improve both the efficiency of memory utilization
434 This strategy speeds future allocations as several pieces of memory
440 Because the size is not specified when a block of memory is freed,
444 However, this strategy doubles the memory requirement for allocations that
447 instead of storing the size of each piece of memory with the piece itself,
448 the size information is associated with the memory page.
450 the size of a piece of memory that is being freed,
456 memory whose size is exactly a power of two.
458 Now they can be accommodated with no wasted memory.
461 which is willing to wait for memory to become available,
463 that cannot wait for memory to become available.
469 If memory is unavailable and the client cannot wait,
476 The new memory allocator was written about a year ago.
477 Conversion from the old memory allocators to the new allocator
485 Many of the special purpose memory allocators built on
502 and freeing memory in the kernel.
510 routine was used both to allocate one kilobyte memory blocks
513 To get a measure of the cost of memory allocation before
516 exclusive task was memory allocation.
519 clearly be identified as memory allocation usage.
521 the time spent in the kernel could be accounted to memory allocation.
524 because the usual case of the memory allocator is implemented as a macro.
528 we changed the macro always to call the memory allocation routine.
529 Running in this mode, the memory allocator accounted for six percent
545 per megabyte of memory under management (with a one kilobyte page size).
553 First, it will reduce the amount of memory
558 Other researchers have already shown the memory savings
562 memory is never moved from one size list to another.
563 With the 4.2BSD memory allocator this causes problems,
565 a quarter megabyte piece of memory once,
568 memory can be shuffled between large requests so that large blocks
569 of memory are never stranded as they are with the 4.2BSD allocator.
573 that size would acquire a large amount of memory
597 memory allocators remain in the current system.
604 the routine that manages the filesystem buffer pool memory
610 We plan to merge the filesystem buffer cache into the virtual memory system's
613 according to memory load,
614 but will require a policy for balancing memory needs