Most operating systems officially supports some kind of "heap"; not the data structure, but rather a pool of memory which can be borrowed and relinquished as a program continues to execute. Tripos is no exception; in fact, Tripos probably depends on dynamic memory management a bit more than most contemporary operating systems.
Note: The description that follows is true as of when this document is written. Things may change later on; be sure to check assumptions against when a PRD is written!
RAM in the Kestrel-2/EX environment is laid out at negative addresses; that is, the highest address bit is set to address memory. Any top-most address bits not routed to an address decoder are required to preserve sign-extension.
Kestrel-2/EX RISC-V Memory Layout (Hardware)
8 EiB
:
0 2 GiB
+-----+-----+-----------+
| ROM | I/O | RAM |
+-----+-----+-----------+
1 GiB 4 GiB (32-bit)
: :
4 EiB 16 EiB (64-bit)
ROM contains Mantle kernel/hypervisor.
I/O contains all memory-mapped I/O resources.
RAM contains (images of) installed RAM.
Kestrel-2/EX RISC-V Memory Layout (Emulator)
0 2 GiB
+-----------+-----------+
| unmapped | RAM |
+-----------+-----------+
4 GiB (32-bit)
Mantle services typically offered by emulator.
I/O services typically offered by emulator.
RAM contains installed RAM (1 MiB typ.); images MAY be unmapped.
Why? This requirement is part of the RISC-V Privileged Instruction Set specifications, which affects how paged memory management is implemented. The aim is to ensure greater compatibility for both user-mode and supervisor-mode software between 32, 39, 48, and 52-bit page table structures. Although Tripos currently does not use any memory management hardware, there may come a time when it runs inside a protected address space. It seems prudent to benefit from the wisdom of the greater RISC-V community before we reach that stage.
Why? There is also a benefit to this layout which affects implementation of real hardware. The top-most two address bits can be used to drive a partial address decoder (for example, a 74138 configured as a 1-of-4 decoder). We don't need to know which two address bits these are; all we need to know is that they are the top two. The lower address bits can be routed to expansion slots for use by memory expansion cards. Moreover, addresses are referenced relative to zero, so there is no concern about how many absolute address bits exist. The top of memory is always referenced at address -1 (which on 32-bit systems is \(FFFFFFFF, and on 64-bit systems, \)FFFFFFFFFFFFFFFF). This reduces the need for 32-bit vs 64-bit aware applications. If all your memory references occur within 2GiB of address 0, then even on machines with a 64-bit address bus, you can get away with running software that uses 32-bit pointers. (Just remember to load the pointers as signed values.)
The heap is, logically, defined as a reserve of memory that is currently not committed for any other use. It may consist of one or more pools. Each pool represents a region where memory can be allocated.
Why?
We need pools to handle expansion RAM at a future date.
You figure, if a machine comes with 1MB built onto the motherboard,
it will reside from -1048576..-1
(e.g., \(FFFFFFFF_FFF00000..\)FFFFFFFF_FFFFFFFF).
If I then plug in another 1MB of expansion RAM,
it might be configured to respond near the 3GiB mark
(e.g., \(FFFFFFFF_DFF00000..\)FFFFFFFF_DFFFFFFF).
Each pool, then, maintains a linked list of chunks of memory.
+-------------+ | p_base | +-------------+ | p_size | +-------------+ | p_pri | +-------------+ | p_chunklist | +-------------+ | p_name | +-------------+ | p_reserved1 | +-------------+ | p_reserved2 | +-------------+ | p_reserved3 | +-------------+
The p_size and the p_base fields of the pool structure
describe how big the section of RAM is,
in bytes, and where it is located in the physical memory address space.
Note that this span includes both free and used regions of memory,
including all chunk headers.
All pools include at least one free chunk at the time of registration.
Note: A pool can be removed from the system at any time. However, this cannot happen while the pool remains in use. A pool is defined as in use iff there exists at least one chunk with a non-zero owner.
The p_pri field sets the priority of the pool.
When allocating memory, higher priority pools are checked for free blocks first.
The p_reserved fields are currently unused,
and must be kept 0 for future compatibility.
The p_name field points to a combined BCPL/C formatted string
containing a short moniker for this pool of memory.
This provides a nice way of identifying a pool without having to worry about its precise address range.
Each chunk, in turn, describes a single allocation of memory. An allocation starts with a chunk header, which has the following layout:
+------------+ | c_next | +------------+ | c_size | +------------+ | c_owner | +------------+ | c_reserved | +------------+
The c_next field links the chunk into a singly-linked list of chunks.
It points to the next chunk in the free list,
or is 0 if no further chunks are available.
c_size indicates how big the subsequent memory region is, in bytes.
Note:
An observant reader will note that the address of the chunk header
plus the value in c_size
plus the size of a chunk header (32 bytes in this case)
should equal the starting address of the next chunk in the list,
should one exist.
c_owner indicates which task ID currently owns the block of memory.
0 indicates that the chunk is currently free.
Although this can be used for automatic task cleanup,
it's really intended for diagnostic/debugging output.
The c_reserved field is not currently used, but must be kept 0 for future compatibility.
Its existence is to pad the header to a block of memory that is an even power of two.
For the version of Tripos described in this document, this comes to 32 bytes,
since each field is 64-bits wide.
This also sets the granularity for the minimum amount of RAM a program can allocate. Even if only 1 byte is requested by the program, 32 bytes will actually be reserved, since all memory will be allocated in units of the chunk header length.
Why? Making everything uniform like this makes pointer arithmetic that much easier to validate and debug. The value of this will become apparent when looking at how we implement incremental defragmentation.
The following functions are to be implemented:
getmem.
For testing and diagnostics only:
TO add a pool (p) -> id DO
IF p_chunklist is null THEN
Assume pool header lies at very start of memory pool.
Create initial free chunk header.
Link it into the pool.
ELSE
IF first chunk's owner is not zero THEN
RETURN results for malformed memory list.
END
IF first chunk's link isn't NULL THEN
RETURN results for malformed memory list.
END
IF final address in chunk doesn't fit in pool THEN
RETURN results for malformed memory list.
END
END
Find insertion index in system pool vector where this pool should go.
Attempt to insert pool into system pool vector.
IF out of memory THEN
RETURN results for out of memory.
END
RETURN system pool index.
END
TO remove a pool (id) DO
IF id is not valid THEN
RETURN results for failure.
END
IF pool has at least one active chunk THEN
RETURN results for resource in use.
END
Remove the indexed pool from the system pool vector.
RETURN results for success.
END
TO find a pool by name (n) DO
DO FOR EACH pool in the system pool vector
IF pool name matches the provided name n THEN
RETURN index for pool
END
END
RETURN results for nothing found.
END
TO coalesce chunks (c1, c2) DO
Make sure c1 and c2 have the same owner.
IF not THEN
RETURN results for ownership error.
END
Confirm c2 is physically subsequent to c1.
IF not THEN
RETURN results for failure.
END
Increment c1's size by c2's size plus the size of a chunk header.
Relink c1 to c2's successor.
RETURN success.
END
This function is internal, but can be useful for debugging and unit testing.
TO find a free chunk (size) DO
DO FOR EACH pool in the system pool vector
DO FOR EACH chunk in the pool
DO WHILE chunk is free AND subsequent chunk is free
Coalesce chunks.
END
IF chunk size can fit desired allocation THEN
RETURN pointer to chunk.
END
END
END
RETURN results for no chunk found.
END
Splitting of a chunk happens by shrinking the size of the chunk from the top down. So, if we happen to have a free chunk that is 128 bytes in length,
+----+----+----+----+----+
| CH | .. | .. | .. | .. |
+----+----+----+----+----+
| ^
| |
`-------------------'
+c_size
c_owner=0
and we want to allocate 32 bytes from it, we need to account for the new chunk header:
+----+----+----+----+----+
| CH | .. | .. | CA | // |
+----+----+----+----+----+
| ^ | ^
| | | |
`---------' `----'
+c_size +c_size
c_owner=0 c_owner=id
Here, CH's size is reduced by 64 (the size of the header plus the desired allotment size), while CA's size is set to the allotment size.
TO split chunk (c) reserving (sz) bytes for owner (id) DO
IF chunk is not free THEN
RETURN results for malformed chunk header.
END
Round sz up to next multiple of 32.
Compute total allotment size as sz + size of chunk header.
IF the free chunk is large enough for the total allotment size THEN
Reduce free chunk size by total allotment size.
Compute base address of new chunk header.
Fill in new chunk header owned by task id.
RETURN address of new allotment address.
END
IF the free chunk is large enough for (sz) bytes THEN
Mark chunk as owned by task id.
RETURN address of chunk's current allotment.
END
RETURN results for chunk too small.
END
This just leaves the top-level entrypoint to allocate memory. Note that
TO allocate a chunk of size (sz) DO
Round sz up to a 32-byte boundary.
Find a free chunk of size sz.
IF not successful THEN
RETURN results.
END
Split found chunk reserving sz bytes for owner id.
RETURN results.
END
We should probably handle semaphores to prevent multiple threads across CPUs from doing bad things, but you get the idea.
This deallocates a block of memory.
Like getmem, it will share responsibility for incremental defragmentation.
TO deallocate a block (p) DO
Confirm p is aligned on 32-byte boundary.
IF not THEN
RETURN results for bad pointer.
END
Determine chunk address for p.
Mark chunk as free by setting owner to 0.
DO WHILE chunk is free AND subsequent chunk is free
Coalesce chunks.
END
RETURN results for success.
END