Segment allocation and compaction

[Marven Lee]

My microkernel allocates memory as contiguous spans of physical
memory in a similar way to segments but using spans of physically
contiguous pages. I'm doing it this way as the message passing revolves
around unmapping these segments from one process and then mapping
them into another. A small header of upto 128 bytes can also be
copied with the main body of the message.

But I was thinking of modifying how I allocate and compact these
segments. I was also thinking that I could have a background
task that wakes up every few minutes or so and compacts the
segments downwards.

To manage these physical segments I currently use a quick-fit
allocator with 64 lookaside lists for allocations from 4k to 256k.
Allocations larger than 256k are on a separate list. The best fitting
segment is chosen and split if necessary.

Segments larger than 4MB are aligned on 4MB addresses so that
some or all of a segment can be mapped using 4MB pages.
Freeing a segment merely marks it as free and places it on the
appropriate list depending on it's size.

The above applies to physical memory but also applies to allocating
the virtual address space of each process An array is also used to
manage the areas of a virtual address space, growing on allocations
and shrinking on coalescing. The array makes it quick to search
for a given segment given it's address and the quickfit lookaside
lists make it easier to find a free area.

So I'm going to leave the virtual allocator alone as it works and is
quite quick, but I've been thinking of changing the physical
allocator.

My new thought is to throw away the quick-fit lists and always
allocate memory from the top of the heap. If there isn't enough
space at the top of the heap then the segments below are
compacted to make room at the top.

Perhaps this causes more compaction to occur than the previous
algorithm but can't imagine the compaction needing to occur
that often. Segments are thus sorted by age with the oldest
segments at the bottom of heap and shouldn't need moving that
often during compaction.

A problem is that large segments that are 4MB aligned will often
leave unusable gaps below them that can't be filled, the old algorithm
could at least fill them with smaller allocations. One possible thought
is that if memory is running low then large segments could be
compacted to 4k alignment, removing the gaps underneath them. If
free memory later increases then the large segments can be aligned
on 4MB boundaries again.

I'm also unsure what to do about holes in physical memory and
whether I should manage spans of free memory between the holes
as individual heaps that are compacted separately or if I should
move segments down below holes when compacting.

Similarly I allow areas of memory to be locked in place for DMA
purposes and similar to handling the holes above I could either
move segments the locked segment below it or just compact
above it. Alternatively I could wait during compaction for
the segment to be unlocked and then compact. If the wait
is too long I guess I could do a kernel panic.


--
Marv

[Rod Pemberton]

"Marven Lee" <marv...@gmail.com> wrote in message
news:auu6uq...@mid.individual.net...

> My microkernel allocates memory as contiguous spans of
> physical memory in a similar way to segments but using spans of
> physically contiguous pages. I'm doing it this way as the
> message passing revolves around unmapping these segments from
> one process and then mapping them into another. A small header
> of upto 128 bytes can also be copied with the main body of the
> message.
>

...

> But I was thinking of modifying how I allocate and compact
> these segments. I was also thinking that I could have a
> background task that wakes up every few minutes or so and
> compacts the segments downwards.
>

What is the need for the compaction?

E.g., reduce fragmentation, coalesce the memory pool, limited
memory or out-of-memory issues, imperfect re-use of
de-allocations, lack of virtual memory, ...

I.e., I'd assume that if re-use of de-allocations was working
well, then you wouldn't need to compact memory. There would
be a good fit between former allocations and currently needed
allocations.

> To manage these physical segments I currently use a quick-fit
> allocator with 64 lookaside lists for allocations from 4k to
> 256k. Allocations larger than 256k are on a separate list.
> The best fitting segment is chosen and split if necessary.
>

Do these fit well? Do these re-use well?

Can over-allocation reduce re-use issues?
(e.g., round-up, limited set of allocation sizes, etc.)

By "split if necessary", you're referring to splitting the
_segment_ for allocations less than (undersized) the "best fitting
segment" in size, yes? Or, do you mean splitting the _allocation_
for allocations larger than (oversized) the "best fitting segment"
in size? Splitting the segment is fine, but may make it harder to
find larger blocks to re-use. Could this be a factor in your
desire to compact reclaimed memory? I.e., are you repeatedly
breaking memory allocations into smaller and smaller parts? FYI,
you definately want to avoid splitting the allocation. It will
cause serious problems with HLL's like C. They expect memory
allocations to be contiguous since they reference allocations by a
single address.

...


Rod Pemberton
P.S. If you're replying from comp.arch, please leave a.o.d. on.