The FYSOS memory allocation system specification 1.0.0-rc2

This document describes version 1.0.0-rc2 of the FYSOS memory allocation system: a free, simple, portable, personal, fully featured allocation system for embedded tasks and hobbyists alike. Minor changes made to this document (e.g. wording) that do not affect the registry system format are tracked by the third number in the document version number.

This memory allocation system is in the release development stage: this document supersedes any previous version of the memory allocation system specification with no care for backward compatibility.

Since this is a new memory allocation system, and some aspects are still to be defined, suggestions or corrections are welcome, for either the memory allocation system or this document. Please contact the author at: fys at fysnet.net. The author wishes to thank those who have submitted comments and criticism in order to improve this system.

Table of contents

• Differences from the previous versions
• Definitions
• Machine Size
• Virtual Heap
• Heap Catalog
• The Bucket Structure
• The Pebble Structure
• Splitting Pebbles
• Merging Pebbles
• Aligned Requests
• Physical Requests
• Initialization
• Allocation requests
• Requirements

Differences from the previous versions

• version 1.0.0-rc2
  • Reformat: A few more modifications
  • Spinlock: Change the Spinlock function
• version 1.0.0-rc1
  • Reformat: Reformatted the specification to be consistent with other like FYSOS specifications
  • Structure: Modified the structure layout slightly
• version 1.0.0-rc0
  • Official Release: Official release version 1.0.0-rc0.

Definitions

The following terms and conventions will be used throughout this specification:

• must, must not, should, should not, may: these words are to be interpreted as described in RFC 2119;
• reserved for future use: a data field that has not yet been defined. When creating a new entry that field must be written as zeros. When reading an existing entry, a driver must not make assumption about the content of that field. When writing that field to an existing entry, a driver must preserve the value in that field;
• byte: a group of eight adjacent bits, an octet;
• driver: a system driver, or any other part of the operating system, or any application implementing this specification to access the registry system;
• page: a minimum number of contiguous bytes of an allocation unit of the underlining system, usually 4k;
• pebble: a block of memory, used to store data, belonging to a single task or request;
• bucket: a block of memory, used to store child pebbles;
• heap: a contiguous block of memory, physical or other, containing an arbitrary number of buckets, each bucket containing an arbitrary number of pebbles. A heap has but one owner, though an owner may have multiple heaps;
• The C++ syntax is used for code snippets and structure formats, with stdint.h integral types. The char type is assumed to be 8-bit. Hex numbers are prefixed with 0x;
• Unless otherwise stated, all numbers must be stored in little endian format (least significant byte first).

Machine Size

This specification outlines a 32-bit memory module and a 64-bit memory module. When you compile for a 32-bit platform, pointers and size_t declarations are 32-bit wide. When you compile for a 64-bit platform, pointers and size_t declarations are 64-bit wide.

The struct Bucket structure is always 64 bytes in size, no matter the platform.

The struct Pebble structure is of a different size depending on the inclusion of the name field and the platform size.

• On a 64-bit platform and the name field is omitted, the struct Pebble structure is 64 bytes in size.
• On a 64-bit platform and the name field is included, the struct Pebble structure is 128 bytes in size.
• On a 32-bit platform and the name field is omitted, the struct Pebble structure is 64 bytes in size.
• On a 32-bit platform and the name field is included, the struct Pebble structure is 64 bytes in size.

Virtual Heap

 Figure 1: Layout of a FYSOS memory allocation system.

To make it easier on the kernel, a virtual memory heap is created. The heap is a number of blocks of memory available to the kernel. The heap is used as a simple way to allocate and free virtual memory without calling the underlining physical allocator for each and every memory request, making it much faster to allocate memory.

On Kernel start up, it calls the Virtual Memory Allocator (mmap()) to allocate a single linear block of memory, 64 Meg is suggested but not required, for this heap. The memory in the heap may or may not be physically contiguous. This heap is then further managed by a Heap Allocator. All requests for memory go through this Heap Allocator.

If a memory request can be satisfied from this initial block of memory, the Heap Allocator records the allocation within its catalog and returns a pointer to a region large enough to satisfy the request. No call to the Virtual Memory Allocator or Physical Memory Allocator is needed, drastically speeding up the memory request.

If the memory request cannot be satisfied, due to lack of remaining room in the current catalog, a special alignment request, a physical address request, or other situation, the Heap Allocator may then call upon the Virtual Memory Allocator to satisfy the request. The Virtual Memory Allocator may then call upon the Physical Memory Allocator to satisfy the request.

This Virtual Heap Allocator maintains a catalog of virtual memory addresses from base address of the Bucket to the size of the heap set by the Kernel. The Kernel’s heap may set this limit to any amount. Any Heap created for a user task may set an initial limit, resizing as needed.

Heap Catalog

The Heap Catalog consists of Buckets and Pebbles. Initially there is a single Bucket of any size holding one to an arbitrary number of Pebbles within it. Each Pebble is marked used or free. If a Pebble is marked free, it may be used to satisfy a memory request. This Pebble can be split into two Pebbles so that the remaining part of the Pebble can then be used to satisfy another request.

If at any time there is not a Pebble within a Bucket to satisfy a memory request, a new Bucket may be allocated, placing free Pebbles within, to satisfy the request.

Buckets

A Bucket is allocated by the Virtual Memory Allocator, is of an arbitrary size, and is considered a contiguous number of virtually allocated bytes from start to end. The starting memory location and any contiguous byte to the end may or may not be physically contiguous, but must be virtually contiguous.

A Bucket is allocated and freed from the Virtual Memory Allocator using two functions, the first may be a function called mmap() and the second may be called mmap_free(). No other system memory function is required as far as the Heap Allocator is concerned. All Virtual Memory allocated for a Bucket is cataloged by the Virtual Memory Allocator.

A Bucket maintains only the Pebbles within it and has no awareness of any other Pebbles within another Bucket.

A Bucket may be resized at any time as long as the Pebbles within are maintained. If a Bucket has excess free Pebbles, or a single free Pebble with excess memory allocated for it, a Bucket may shrink to accommodate. If a Bucket doesn’t have enough free space within, it may expand to create an addition number of Pebbles. However, any memory added to the Bucket must be contiguously added at the end of the currently allocated memory. i.e.: A Bucket may only increase in size if the added memory is Virtually consecutively added at the end and the new sized Bucket is still completely continuous.

A Bucket has the following format and must be stored in the first bytes of the allocated space returned from the Virtual Memory Allocator.

The Bucket's localFlags field is defined as the following:

Pebbles

Pebbles are stored within a bucket. A Bucket must have at least one Pebble. A Pebble is used to satisfy a memory allocation request.

A Pebble has the following format.

The Pebble's localFlags field is defined as the following:

Splitting Pebbles

When Splitting a Pebble to allocate a portion of the memory allocated to it, you must add at least one Pebble in either direction, updating the two surrounding Pebbles to point to this newly added Pebble. You may only split a Pebble when there is enough room to satisfy the current allocation request and a new Pebble will have at least the 64-byte minimum available space allotted for it (sizeof(Pebble) + 64). If splitting a Pebble does not leave enough room for a new Pebble and this 64-byte space, the Pebble is not to be spit and the allocated size must remain as is. This 64-byte space is determined with a #define and can be changed. A value that is a power of two is recommended.

When using the Alignment functionality, you may split a Pebble into three contiguous Pebbles. The first will be a free Pebble simply to pad to the next Pebble, which will be the Aligned Pebble. Then this Aligned Pebble may possibly split again to free any excess space after it. This may create three Pebbles when splitting one Pebble for an aligned request. If doing so, the first and the possible third Pebble must remain available for use by another request.

Please note that when splitting in this manner, if the first Pebble will have an available size less than 64, it is recommended to align on the next available alignment, the one after the current calculated alignment, to make the first Pebble have an available space of at or more than 64 bytes. Also note that the Aligned Pebble must start 128 bytes (the size of a Pebble Structure) before the alignment value so that the available memory starts on the requested alignment.

Also, please note that if the current Pebble, before you split it into three, already is aligned on the requested alignment, there is no need to create three. Simply return the current Pebble, possibly first splitting it into two to free the excess space.

Merging Pebbles

When two consecutive Pebbles are free, your Heap Allocator should merge these Pebbles to create a single Pebble. To do this, the first Pebble needs to consume the second Pebble. All linked-list pointers must be updated for any surrounding Pebbles. The Size field in the first Pebble is now increased to the size of both Pebbles including the deleted Pebble’s header block. new_size = pebble0->size + sizeof(pebble) + pebble1->size

Be sure to watch that if you delete a Pebble by merging, the Bucket’s First Pebble pointer is still valid. i.e.: by deleting this Pebble, first make sure the Bucket wasn’t pointing to this Pebble, and adjust if needed.

Aligned Requests

When the caller is requesting a memory address that is aligned on a supplied boundary requirement, it is up to your Heap Allocator to satisfy this request. The manner in which you do is not specified here. However, here are a few examples. See a previous section on splitting a Pebble for more on accommodating Aligned requests.

1. Your Heap Allocator may adjust a Pebble’s location so that the byte just after the Pebble Structure satisfies the alignment request. To do this, you forgo the 64-byte alignment request specified in a previous section and place a Pebble so that it is just before the aligned location. To do this, you must have an original free Pebble large enough to split and place a new Pebble within the allocated space so that this new Pebble’s memory region is now aligned.
2. You may insert a new Bucket into the Heap, so that the newly created first Pebble is now aligned on the requested alignment. However, this makes it so that your code cannot assume the first Pebble is just after the memory used for the Bucket. This means that there may be unused space between the memory used to store the Bucket data and the first Pebble. However, this is an easy way to allocate aligned and/or physically aligned memory. See the next section for more on this use.

Physical Requests

Physical contiguous memory requests must also be satisfied by the Heap Allocator. Physically allocated Buckets are allocated, stored, and freed exactly like Virtually allocated Buckets, only that the localFlags field is adjusted to indicate which is which. When a new Bucket is created, the Heap Allocator passes a flag to the Virtual Memory Allocator to return memory that is Physically and Contiguous allocated. The Heap Allocator requests the Virtual Memory Allocator to make sure and allocate Physical Memory addresses that are contiguous. There is no difference in the Heap allocation scheme between Virtually stored Buckets and Physically stored Buckets, other than the localFlags member of the Bucket indicating the difference.

Heap Initialization

Generally, the owner--usually the kernel but later a user app--will call the underlining paging system to allocate a virtually contiguous block of memory, creating one or more buckets and each bucket having one or more pebbles. When the owner then makes a memory request, the allocator will scroll through the bucket(s) and pebble(s) until it finds a satisfactory type of memory block.

In general, this allocation request will simply be a size in bytes and the allocator will return a virtually contiguous block of memory at least the size of the request.

However, as a kernel, a request for physically contiguous memory may be requested. This is where another Bucket can be created within the same heap or a new heap.

Each heap is created using the underlining mmap() style system call. If the system is using memory paging, the call should return a virtually contiguous block of memory, or if requested, a physically contiguous block of memory.

If the underlining system does not support memory paging, a physical contiguous block of memory will be returned for both types of request.

This allocation scheme does not require the underlining system to support paging. The mmap() call can simply return a physical address of the first byte of memory and a size.

Allocation requests

The owner of the heap will make a request for a specific type of memory. This can be anything from a normal allocation, to a more specific request such as physically contiguous and possible aligned memory request.

A driver should check each bucket within the heap to see if any bucket satisfies this type of request. If none are found, a driver may add a bucket to the linked list, first extending the size of the heap or making room within the heap, or a new heap can be allocated and initialized.

A suggested calling prototype might look like this:

/* Allocate size bytes, w/o Alignment, Request Flags, Caller name/debug info */
void *kmalloc(size_t size, uint32_t Alignment, uint32_t rtFlags, const char *debugName);

A caller might use similar calls as this:

/* Allocate 64k, no alignment, anywhere in the virtual address space, "a long time ago" */
void *fobar = kmalloc(65536, 0, rtVirtual, "What is the");
/* Allocate 1Meg, 4k page alignment, anywhere in the physical address space below 4Gig, "in a galaxy far," */
void *fobar = kmalloc(1 * 1024 * 1024, 4096, rtPhysical | rtAligned | rtLow4Gig, "core temperature");
/* Allocate 4k page, 64-byte alignment, anywhere in the physical address space and clear it, "far, far away...."*/
void *fobar = kmalloc(4096, 64, rtPhysical | rtAligned | rtLowAny | rtClear, "of a tauntaun?");
/* Allocate 32k, 32-byte alignment, anywhere in the virtual address space and clear it, "let the wookie win"*/
void *fobar = kmalloc(32768, 32, rtVirtual | rtAligned | rtClear, "-- Luke warm --");

if (fobar == NULL) {
  /* Do some kind of error */
  return ERROR_NO_MEMORY;
}

Requirements

The following is a list of notes and/or requirements.

• You may have more than one Bucket within a Heap, especially when the Heap owner is the Kernel. For this Kernel, create one or more Buckets for virtual memory, and then anticipate a call with a rtLow* requirement.
• It is up to the Virtual/Physical Memory Allocator (mmap()) to make sure no Heap overlaps another. i.e.: it should account for and assume that a request will have a rtLow* bit set, so it must maintain a strategy to reserve these areas for those requests.
• There must not be any unused space between Pebbles. A Pebble is allocated on a 64-byte boundary so with a 64-byte minumal alignment, there should never be any unused space between Pebbles.