is a memory allocation system that...
- is easy to understand and implement
- works with or without paging
- has allocation restrictions for hardware I/O
- supports many attributes
- is multi-task aware
- requires little memory and CPU power
The FYSOS memory allocation system is a free, simple, portable, memory system created to provide an alternative, easy to implement memory allocation system for OS development hobbyists. It is primarily intended to easily allocate and free chunks of memory within the kernel system, and to expand the functionality of the FYSOS operating system.
This system is designed to be able to allocate physical or virtual memory, with type defines instructing on how and where to allocate this memory. For example, if you find a hardware device using mem-mapped I/O that must be below the 32-bit threashold, you can instruct this allocator to do just that.
News
2025 Feb 22 - Version 1.0.0-rc2 of the reference implementation is available.
Overview
The memory allocation scheme is designed to give the owner a simple, easy, and fast way to allocate memory, whether that memory be physically contiguous or not. The owner, using an allocation request type, can allocate memory to fullfill a specific type of allocation.
This system allocates a virtually contiguous block of memory and then when asked, assigns parts of this heap to specific requests. This heap must be virtually contiguous but does not have to be physically contiguous, though a system that does not support paging can use a physical contiguous heap with little to no changes.
This scheme has no idea whether the memory itself is physically contiguous or not, it only guarentees it is virtually contiguous. It is the underlining mmap() call and the OS to have the responsibility of a memory paging and/or memory swapping mechanism.
This scheme uses buckets and pebbles to catagorize the memory used. A bucket will be a specific type of memory, either virtually contiguous, physically contiguous, below the 16Meg mark, above the 4gig mark, or a combination of types. Each pebble within this bucket will keep these characteristics but be given out to the requestor as requested.
There is no limit on the number of buckets or pebbles used. Each bucket can hold an arbitrary number of pebbles and the Heap can hold an arbitrary number of buckets.
This system is designed to be simple to implement. It does not use any complex algorithms such as b-trees or other hash-table style listings. It simply is a linked list of objects, listed one right after another. With this simplicity, and without the complex algorithms, it does take a little more CPU time to transverse through the buckets and pebbles to get to the desired allocation, but the simplicity really out-weighs this small amount of extra time, especially for smaller allocation requests. The extra time is not even noticeable on an allocate heap of 1024 Megs in size, a size well large enough for hobby operating systems like yours and mine.
Technical résumé
| Allocation unit | Buckets and pebbles |
|---|---|
| Types of allocation | Physical or virtual, hardware I/O or general |
| Number of buckets/pebbles | arbitrary, limited to available memory |
| Endianness | little endian |
Where to go from here
To go into the depth of structure formats and algorithms of the allocation system, you may read the FYSOS Bucket/Pebble system specification.
A reference implementation, written in C, is available in the Downloads section.