Bitmap or stack based memory manager

[Pype.Clicker]

the bitmap may be made faster if you keep the index of the last allocated page. Assuming that most of the free pages will have another free page after them (i.e. that allocation didn't turn in a big mess), you know that you'll rarely have to look a lot further.
Bitmap scanning can also be improved if you perform a "quickscan" test (i.e. check the whole dword is 0 before checking bits separately).

[Tim]

The reason i am concerned with runs of memory is my kernel uses the physical allocator directly.

Then you're stuck, and a stack allocator is not the way to go. You can really only use a stack allocator for allocating a single page at once.

IMO you shouldn't be using physical pages directly, but allocating contiguous runs of virtual address space, and allocating physical pages either when you allocate the address space or on a page fault.

[Peter_Vigren]

The bitmap will take less memory though as it will be one bit per address rather than 32 for a stack (although in theory less bits can be used, maybe 20, but that will make things more difficult)

But a bitmap will be slower to scan I think.

Well, since the bitmap (as I have understood it) will be placed in memory it will be quite fast depending on the routine... And a bitmap is static. That can both be a advantage and a disadvantage. But I like static.

[pskyboy]

My biggest concern with the whole virtual memory thing is in loacality of memory. If i have a continous run of virtual memory but the page frames are all over the physical memory it will be slower to access then if they are in a long run as modern memory is much faster at doign burst accesses from memory.

The other thing is how am i ment to use virtual memory in my kernel when my virtual memory manager needs physical memory to store its data? chicken egg situation!!

Peter

[jrfritz]

Wait - a - second!

Your programming for the super 64-bit processors...right?

So wouldn't stuff be different?

[pskyboy]

No not really, the x86-64 architecture for memory managment is almost identical except it allows you to have much more memory.

Peter

[Tim]

My biggest concern with the whole virtual memory thing is in loacality of memory.

That's an important consideration. Memory managers in "real" operating systems take a page's location in the cache (or 'colour') into account. They try to allocate memory so that adjacent virtual pages are of different colours, to lessen the chance of adjacent virtual pages pushing each other out of the cache. To solve this, I would have one stack of physical pages for each colour, with the distribution of colours between physical addresses determined by how the target CPU's cache works.

The other thing is how am i ment to use virtual memory in my kernel when my virtual memory manager needs physical memory to store its data? chicken egg situation!!

Give the virtual memory manager its own allocator for its data structures. Or, put a separate allocator in the kernel for low-level things. You could make it a slab allocator; I base it around the normal malloc/free with a custom morecore function. It uses a special area in kernel address space (0xF0000000 to 0xF8000000) as the kernel heap, and interfaces directly to the physical memory manager to allocate pages and map virtual addresses to physical.

Code: Select all

addr_t kernel_sbrk;
void *__morecore(size_t diff)
{
    addr_t new_sbrk, start, phys;

    diff = PAGE_ALIGN_UP(diff);
    assert(diff < 1048576);
    if (kernel_sbrk + diff >= 0xf0000000)
        return NULL;

    start = kernel_sbrk;
    new_sbrk = kernel_sbrk + diff;

    for (; kernel_sbrk < new_sbrk; kernel_sbrk += PAGE_SIZE)
    {
        phys = MemAlloc();
        if (phys == NULL)
            return (char*) -1;

        if (!MemMap(kernel_sbrk, phys, kernel_sbrk + PAGE_SIZE, 
            PRIV_WR | PRIV_KERN | PRIV_PRES))
            return NULL;
    }

    return (void*) start;
}

[pskyboy]

Cheers that helps,

Another question is why do i need the morecore and related functions in the virtual memory manager. What im thinking is why can i not just give each process 4Gb or virtual memory and then let the program use it as it pleases.

Peter

[Tim]

I was answering your question on where the virtual memory manager stores its own data. You'd have a different user-mode morecore which called the virtual memory manager for its memory.

[pskyboy]

So why do i need functions for my apps to call. Can i not just give them 4Gb when the app is loaded and then let it run.

At the moment the way i see it working for my apps is i just create page tables for each app mapping 4Gb of VM and then set CR3 to point to that page table. I then load the executable into the memory and jump to the start of the program.

Peter

[Whatever5k]

I have created my own physical memory allocator (which uses two bitmaps for superpage and pages). The virtual memory allocator will be similar to Tim's code he show...by the way, what is kernel_sbrk, Tim?
The only problem I'm thinking about is what happens if a user requests more than one page and the page tables are non-contiguous. Which virtual start address do I return the user? The lowest, right? But the virtual address space is not contiguous if I have page tables that are non-contiguous. What do I have to do?

[Tim]

pskyboy: Are you considering letting an application access any address and allocate physical pages on every page fault? That seems to me to be unreliable (you'd never catch bugs where you read past the end of a string, for example) and inflexible. You will almost certainly want a way for user apps to request sections of the address space; not necessarily malloc, but a way to allocate and free several pages at a time.

abless: kernel_sbrk points to the end of the kernel's heap. It starts at 0xF0000000 and increases with every call to morecore. Note that you wouldn't use morecore as your allocator, but malloc and free; malloc calls morecore internally when it runs out of heap.

I don't see the problem with non-contiguous page tables. The address space is as contiguous or non-contiguous as you want it. The kernel decides how each and every virtual page maps to a physical page, and the CPU enforces that mapping.

Look at the implementation of morecore I posted. The virtual region from 0xF0000000 to kernel_sbrk is all valid, contiguous memory. The kernel can access any byte in that range successfully because that region is set up by the call to MemMap. The addresses returned by MemAlloc aren't necessarily contiguous: they could be completely random, but we don't mind. This is one of the big advantages of using paging: you can present a single flat address space to an application regardless of how the physical memory underneath works.

[pskyboy]

I don't see the problem with giving an application a whole 4Gb address space and just allocating memory on each page fault. The actually allocation of memory can be handled by malloc. That way it would also make life very easy as to hand out more memory all malloc need do is hand out the current pointer and then incrment it by the size requested so its ready for the next request.

As for the overflow of a string that shoudl be caught by the proggrammers when debugging surely and with newer proggramming languages is less of a problem.

Peter

[Tim]

I don't see the problem with giving an application a whole 4Gb address space and just allocating memory on each page fault. The actually allocation of memory can be handled by malloc. That way it would also make life very easy as to hand out more memory all malloc need do is hand out the current pointer and then incrment it by the size requested so its ready for the next request.

A compromise solution might be to maintain an upper limit on the application's memory and only allocate new pages if the page fault happened in the page immediately above the upper limit. Other page faults (such as those caused by random pointer accesses) would be trapped. You could write malloc to probe addresses every 4096 bytes when allocating new memory, to avoid an invalid page fault. This is similar to how Windows grows threads' stacks.

As for the overflow of a string that shoudl be caught by the proggrammers when debugging surely and with newer proggramming languages is less of a problem.

Famous last words... Anyway, how do you catch the error when the kernel doesn't throw an exception? All you'd notice was that all your memory was eventually used up. If you had a formal memory allocator, you'd get a fault as soon as you accessed the wrong part of memory.

And another thing... there's more things you can do with memory than just map virtual addresses to physical ones. Examples are memory-mapped files (read data from a file on a page fault) and shared memory (two processes looking at the same physical memory). How could you implement those if you don't have a proper virtual memory allocator in the kernel?

Also, you can't give applications the full 4GB since the kernel will need its own area, protected from application space.

[pskyboy]

Yeah true, when i went away and thought about it some more i decided that a proper memory allocator would be better. I just thought it might be cool to give a program 4gb -kernel of space and then just let it play so to speak.

Peter