[rld] Layout

Imagine a simple system whose executables contain just two segments: one read-only and executable (call it “TEXT”) and another writable and not executable (“DATA”).

The repository sections are a superset of these, but for simplicity let’s consider just text, data, bss, and rodata. Here’s a trivial example:

int f1 (void) {
    static int a = 1;
    static int b = 0;
    ++a;
    ++b;
    return a + b;
}
char const * f2 (void) {
    return "f2";
}

The compilation will contain two fragments:

• f₁ representing f1(). It contains 3 sections: text for the function body, data for the definition of “a”, and bss for variable “b”.
• f₂ representing f2(). This fragment has text as well as rodata for the const char array.

(Note that this isn’t the only possible representation and the compiler may emit more fragments than this. The above shows the most efficient way to describe this program.)

We can define a table which maps the repository section kinds to segments:

Section Kind	Segment
data	DATA
bss	DATA
text	TEXT
rodata	TEXT

Note that the order of the section-kinds will be important for the ordering of data within a segment. Many systems separate non-executable read-only data into a segment of its own.

The data within each of the segments must to be contiguous. This means that the layout must gather and sort the payload of each section kind from the live fragments. We can do this using a three-dimensional array where the of the form structure

Segments	Sections
	text	rodata	data	bss
TEXT	f1, f2	f2
DATA			f1	f1

Finally, this three-dimensional table can be flattened to produce the final layout:

+---TEXT----+  +- DATA -+
v           v  v        v
f1 f2  f2      f1    f1
text   rodata  data  bss

This scheme, although elegant in its simplicity doesn't handle overlapping segments. More to follow…