Anonymous user
Memory Allocation: Difference between revisions
m
Added link to another malloc replacement
| [unchecked revision] | [unchecked revision] |
(mentioned fixed size memory allocation →A very very simple Memory Manager) |
m (Added link to another malloc replacement) |
||
| (6 intermediate revisions by 6 users not shown) | |||
Line 6:
The free space will subsequently be used for kernel data structures, application binaries, their heap and [[stack]] etc. - the kernel needs a function that marks a memory area as reserved, and makes that memory available to the process requiring it. In the C Standard Library, this is handled by malloc() and free(); in C++ by new() and delete().
==The Big Picture==
An operating system has many [[Memory_Management|memory management]] layers. Each layer is built on top of the previous layer. To put you in perspective:
* RAM is allocated in the Physical Memory Manager, which is typically a [[Page_Frame_Allocation|page frame allocator]] (another popular choices are [https://en.wikipedia.org/wiki/Slab_allocation SLAB] and buddy allocator).
* Pages are allocated into address space (typically via sbrk() or mmap() system calls) by the Virtual Memory Manager.
* Then the available address space is managed by a user-space allocator, typically called malloc(), this is the topic at hand.
Kernel heap management is very similar, has the same abstractions, but uses different functions:
* at the bottom level, uses the same PMM.
* memory is usually mapped into kernel address space by a special function, and there's no need for system call to raise privilege level.
* allocating kernel [[Heap|heap]] is done via kmalloc(), which is very similar to malloc(), but not defined in libc rather in a kernel library.
As you can see, the VMM differs in only one thing: which [[Paging|paging]] tables are used to map the pages allocated by the PMM (user-space vs. kernel-space). Some protection bits, like supervisor page also differ, otherwise these steps are identical.
Top level memory management is also very similar, the only difference is, which callback is used in the VMM when the manager runs out of free virtual memory. This implies that you can use any existing memory allocator as kmalloc() too, if you replace that callback in them.
So memory allocation goes through these steps:
1. do we have enough free virtual memory?
2. if so, use some structure to record memory allocation status (depends on the allocator)
3. if not, then ask the VMM to enlarge available address space (sbrk/mmap/mapkernelheap etc.)
4. VMM in turn calls the PMM to allocate RAM
5. the newly allocated RAM is recorded in the appropriate paging tables by the VMM
6. go to step 2.
Steps 3 - 5 are slow (mainly because of the required privilege level change), so memory allocators tend to minimize these calls, and reuse the memory in their already mapped address space as much as possible.
==A very very simple Memory Manager==
Line 59 ⟶ 85:
It's not always desirable or practical to write your own memory allocator. Writing an efficient memory allocator can be an entire project in itself and fortunately it's extremely easy to port an existing memory allocator to your OS (to run in either kernel or user space). The advantages of using an existing memory allocator are; porting one is much faster than writing your own especially when you want to focus on other areas of your OS, it is likely to be well-tested so you do not have to debug the memory allocator, it takes a minimal amount of work to port it, and finally, someone else has down the hard work to make it fast, scalable, stable, etc.
Porting a memory allocator is fairly simple to do. Most of them are no more than one source and/or header file. The functionality you must hook is for allocating and freeing pages to your program, so the memory allocator has memory to work with.
There are
*void *alloc_page(
*void free_page(void *start,
In addition, some memory allocators will require you to hook locking functionality to ensure critical sections of the memory allocator aren't executed simultaneously by multiple threads. Typically the functions will appear like;
Line 90 ⟶ 113:
There are a lot of allocators to choose from, so this is far from being a comprehensive list;
*[https://github.com/blanham/liballoc/ liballoc] - Excellent allocator that was originally a part of the Spoon Operating System and designed to be plugged into hobby OS's.
*[http://
*[http://goog-perftools.sourceforge.net/doc/tcmalloc.html TCMalloc] Thread-Caching Malloc. An experimental scalable allocator.
*[http://www.nedprod.com/programs/portable/nedmalloc/ nedmalloc] A very fast and very scalable allocator. These two properties have made it somewhat popular in multi-threaded video games as an alternative to the default provided allocator.
*[http://www.malloc.de/en/ ptmalloc] A widely used memory allocator included with glibc that scales reasonably while being space efficient.
*[https://github.com/jemalloc/jemalloc jemalloc] A general purpose malloc(3) implementation that emphasizes fragmentation avoidance and scalable concurrency support, first used in FreeBSD
*[https://github.com/emeryberger/Hoard Hoard] is a drop-in replacement for malloc that can dramatically improve application performance, especially for multithreaded programs running on multiprocessors and multicore CPUs.
*[https://github.com/fysnet/FYSOS/tree/master/bucket Bucket] is a simple drop-in replacement for malloc for beginners. Most importantly, it has detailed documentation of what happens under the hood. Not just source code comments.
==See Also==
Line 101 ⟶ 127:
===External Links===
*[http://www.osdever.net/tutorials/
*[http://www.osdever.net/tutorials/
▲*[http://www.osdever.net/tutorials/memory2.php?the_id=45 Memory Management 2] - Part two of a two part series on memory management by Tim Robinson
*[http://www.cs.ucsb.edu/~grze/papers/Keyword/MEMORY-MANAGEMENT.html Publications about 'Memory Management'] - A list of some nice articles
*[http://rtportal.upv.es/rtmalloc/ TLSF: Memory Allocator for Real-Time] General purpose dynamic memory allocator specifically designed to meet real-time requirements
| |||