As basic allocator, I can recommend a memblock allocator.
Basic idea is this: You have a list of the available memory regions, and a list of the reserved memory regions.
Code:
struct memblock {
phys_addr_t start;
size_t len;
};
struct memblock memavail[32];
struct memblock memreserved[64];
size_t navail;
size_t nreserved;
The array sizes are arbitrary, but ought to be sufficient for a start. If you run out of memory in these, you may need to look into extending the scheme.
The intervals are kept in order and non-overlapping. So, the two basic operations are adding and removing memory ranges. With the preceding properties, these are not so hard:
Code:
static void add_range_to_memblock(struct memblock *arr, size_t *n, size_t limit, phys_addr_t start, size_t len) {
size_t i;
for (i = 0; i < *n; i++)
if (arr[i].start > start)
break;
/* can we just add this to the preceding block? */
if (i && arr[i-1].start + arr[i-1].len >= start) {
size_t overlap = arr[i-1].start + arr[i-1].len - start;
arr[i-1].len += len - overlap;
/* is it possible to unite this with the next block now? */
if (i < *n && arr[i-1].start + arr[i-1].len == arr[i].start) {
arr[i-1].len += arr[i].len;
if (i + 1 < *n)
memmove(arr + i, arr + i + 1, (*n - i - 1) * sizeof (struct memblock));
--*n;
}
}
/* can we just add this to the following block? */
else if (i < *n && start + len >= arr[i].start) {
size_t overlap = start + len - arr[i].start;
arr[i].start = start;
arr[i].len += len - overlap;
}
/* need to add a new block */
else if (*n < limit) {
if (i < *n)
memmove(arr + i + 1, arr + i, (*n - i - 1) * sizeof (struct memblock));
arr[i].start = start;
arr[i].len = len;
++*n;
}
else
die("Out of memory adding block at %x", start);
}
static void remove_range_from_memblock(struct memblock *arr, size_t *n, size_t limit, phys_addr_t start, size_t len)
{
size_t i;
for (i = 0; i < *n; i++)
if (arr[i].start >= start)
break;
/* Both ends match? Remove entire block */
if (i < *n && arr[i].start== start && arr[i].len == len) {
if (i + 1 < *n)
memmove(arr + i, arr + i + 1, (*n - i - 1) * sizeof (struct memblock));
--*n;
}
/* start matches? Adjust start and len */
else if (i < *n && arr[i].start == start) {
arr[i].start += len;
arr[i].len -= len;
}
/* end matches? Adjust len */
else if (i < *n && arr[i].start + arr[i].len == start + len) {
arr[i].len -= len;
}
/* central match? Adjust list for hole in the middle */
else if (i < *n && start + len < arr[i].start + arr[i].len) {
if (*n == limit) die("Out of memory adding hole at %X", start);
if (i + 1 < *n)
memmove(arr + i + 1, arr + i, (*n - i - 1) * sizeof (struct memblock));
size_t offset = start - arr[i].start;
arr[i+1].start = arr[i].start + offset + len;
arr[i+1].len = arr[i].len - len - offset;
arr[i].len = offset;
}
}
If memory keeps getting exhausted, it is pretty simple to extend the scheme with a linked list. Just remember that you can only allocate a new list node after the kernel has been successfully exempted from allocation, though that should be pretty simple.
In any case, in initialization you now add all the memory given by the memory map as usable RAM to the available memblock, and all the memory given as reserved, as well as the location of the kernel, your modules (if any), and the stack to the "reserved" memblock. Afterwards the allocator is ready.
Allocation then means iterating over the available memory on one hand and the holes between the reserved memory on the other hand, in order to find a hole that fulfills the request. Pretty simple:
Code:
static phys_addr_t *alloc(size_t sz, size_t algn)
{
size_t avidx, residx = 0;
for (avidx = 0; avidx < navail; avidx++)
{
phys_addr_t start;
size_t len;
while (memreserved[residx].start + memreserved[residx].len < memavail[avidx].start && residx < nreserved)
residx++;
while (residx < nreserved && memreserved[residx].start < memavail[avidx].start + memavail[avidx].len)
{
start = memavail[avidx].start;
if (memreserved[residx].start + memreserved[residx].len > start)
start = memreserved[residx].start + memreserved[residx].len;
len = memavail[avidx].start + memavail[avidx].len - start;
if (residx < nreserved && memreserved[residx+1].start - start < len)
len = memreserved[residx+1].start - start;
if (((start + algn - 1) & -algn) + sz <= start + len)
{
start = (start + algn - 1) & -algn;
add_reserved_range(start, sz);
dbg_printf("Allocating address %8x\n", start);
return start;
}
}
}
return 0;
}
There you go, there's your basic physical address allocator. It returns whatever address is still free, and you can do whatever you want with it. It does not scale very well, so you should avoid making many small requests. Indeed, a kmalloc() implementation or anything of the sort ought to be a few layers beyond this one. Linux uses an allocator not unlike this one for bootstrapping, until the main allocator can be used. Maybe that is a strategy you want to look into. But in any case, this allocator can be initialized in a time linear to the number of memory areas, not their size.