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.

Libarea Use Case

Areas are defined like this:

An Area

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.

Collision of Areas

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.

Area Sets
Libarea contains another important class that contains (and manages) areas: The Areaset. The purposes of an AreaSet are to:

For achieving this functionalities, area sets could be specialized to different techniques of management including:

An Area Set
AreaTypeSpecify the type of container (Linked list, B+ Tree) used internally by the area set.
SpecificToContainerThis data is specific to the container (Linked list, B+ Tree, etc)
AreaStatsHold statistics on area set usage: number of coalescences, etc
t_area_fit_methodSpecifies the behavior of the algorithm when looking for available space
t_area_fnsFunctions specific to the container (Linked list, B+Tree, etc).
t_area_setThe 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.

An Example of "Add" Operation

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.


Another Example of "Add" Operation

Here the area set is not empty but the new area does not glue to the previous one so there is no specific handling.


Another Example of "Add" Operation

Here the new area is glued to another one but they have distinct properties so there is no specific handling.


An Example of "Add" and "Coalesce" Operation

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.

Note in this use case, the "Add" operation is interesting since it doesn't consume an element in the list.

An Example of "Remove" Operation

The caller decides here to suppress an area from the area set. This operation splits an existing area into 2 areas.

Note in this use case, the "Remove" operation consumes one area.

An Example of "Modify" and "Coalesce" Operation

The caller decides here to modify the properties of an area in the set. This operation coalesce two existing areas in only one.

Note in this use case, the "Modify" operation is interesting since it frees an area in the list.

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.

The Rec Structure

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:

NameDescriptionMultiplicity in the whole systemspecificity
phys_setUsed for storing physical addresses1could be coalesced with other areas with same properties (e.g. aspace holder) except when space is defined as "aggregate"
kern_setUsed for storing kernel addresses1Never coalesced
user_setUsed for virtual addresses1 per address space (aspace)Always coalesced when vmaps have same properties and underlying physical addresses are contiguous
Note each set could be managed by differents techniques independently (LinkedList, BPT, etc) according to system policy for kern and phys sets and user policy for user sets.

Let's how a rec itself is allocated with libarea:

How a "rec" is "rec"orded

Memory related system call sequences
This sections shows how some memory related system calls are implemented using recs and libarea:

prsv() sequence