MEMORY MANAGEMENT

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:

Areas
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:

• 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

An Area Set

Class	Description
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.

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.

Before	After
0	1

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.

Before	After
1	2

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.

Before	After
1	2

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.

Before	After
2	2

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.

Before	After
2	3

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.

Before	After
3	2

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:

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

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