This sections exposes how simple memory is managed under LSE/OS.
Challenges of a memory manager
When we write a memory manager for an operating system, what is hard is that we can't rely on nothing:
The first thing we will have to know is that the memory manager manages the memory of the system but also use memory to store its own structures.
How can we allocate these structures? We don't have any malloc() available. The snake bites its tail.
One of the most important things we wanted to avoid in LSE/OS was to allocate these structures statically. So we used a way to make this fully dynamic as we will explain later.
In LSE/OS, these structures are called "recs". A rec has a fixed size of ~80 bytes (this size was determined by needs of information a rec has to store).
Each rec consume memory so we tend to use algorithms that use the minimum recs.
Recs are derived from areas which are explained in the next section:
LSE/OS core memory management relies on a simple library: libarea. Libarea is not specific to operating system memory management, it simply know how to manipulate areas.
Areas are defined like this:
Mathematically speaking, an area could be defined ine one dimension as a starting point and a length (blk,nb_blks). The collide() operation simply returns 0 if the two areas doesn't intersect each other.
On the previous diagram, only the areas (1,3) and (3,4) collide.
Areas also have a specific "data" attributes that we could call the "property" of the area. Many areas could share the same "property" as we see later.
Libarea contains another important class that contains (and manages) areas: The Areaset. The purposes of an AreaSet are to:
- Add/remove/modify areas.
- Sort areas from first_blk to last_blk.
- To ensure that areas don't collide each other.
- Find available space between areas
- Coalesce areas if possible when adding, modifying areas or finding space between areas.
- Make lookups fast especially for finding the area corresponding to a specified block number
For achieving this functionalities, area sets could be specialized to different techniques of management including:
- STATIC: Areas are stored in a static array (slow lookups, not dynamic)
- LL: Areas are stored in Linked Lists (slow lookups, dynamic)
- BPT: Areas are stored in a B+ Tree (fast lookups, dynamic) - B means Balanced
|AreaType||Specify the type of container (Linked list, B+ Tree) used internally by the area set.|
|SpecificToContainer||This data is specific to the container (Linked list, B+ Tree, etc)|
|AreaStats||Hold statistics on area set usage: number of coalescences, etc|
|t_area_fit_method||Specifies the behavior of the algorithm when looking for available space|
|t_area_fns||Functions specific to the container (Linked list, B+Tree, etc).|
|t_area_set||The main structure that contains methods that could be overrided (coalesce(), print(), copy(), xlate()) for managing different kind of properties.|
As we said just before, areas have non-unique properties. These properties are used for the "add", "remove" and "modify" operations. Let's examine the following use cases (properties are represented by patterns), for each use case, the number of elements before and after operation is displayed in a table.
The area set is empty before the "Add" operation. There is no specific use case except that the area set only check that the area is not outside boundaries.
Here the area set is not empty but the new area does not glue to the previous one so there is no specific handling.
Here the new area is glued to another one but they have distinct properties so there is no specific handling.
Things become more complex here since the new area is glued to another one that has the same property. The two areas are coalesced together.
The caller decides here to suppress an area from the area set. This operation splits an existing area into 2 areas.
The caller decides here to modify the properties of an area in the set. This operation coalesce two existing areas in only one.
There area plenty other uses cases. The area set class manages all the possible use cases for all the possible types of management (Linked lists, Balanced + Trees, etc).
Allocation of a "rec" in coresrv
Coreserv is responsible for allocating memory. As we said before, coresrv use "recs" for storing information about memory chunks. As we said before, a rec is in fact (at least) an area.
Attributes of the recs are in fact the properties basis on which the area will perform coalescing operations.
Three kinds of area_sets are used in coresrv:
|Name||Description||Multiplicity in the whole system||specificity|
|phys_set||Used for storing physical addresses||1||could be coalesced with other areas with same properties (e.g. aspace holder) except when space is defined as "aggregate"|
|kern_set||Used for storing kernel addresses||1||Never coalesced|
|user_set||Used for virtual addresses||1 per address space (aspace)||Always coalesced when vmaps have same properties and underlying physical addresses are contiguous|
Let's how a rec itself is allocated with libarea:
Memory related system call sequences
This sections shows how some memory related system calls are implemented using recs and libarea: