Citadel Memory Manager Idea!

[elderK]

typedef struct               
   {               //
      MemoryBlock* NextBlock;      //
      MemoryBlock* PreviousBlock;   // Data type for a Memory Block.
      unsigned int BlockSize;      // I imagine it to be about... 24bytes.
      unsigned int BlockOwner;   //
   } MemoryBlock;

unsigned int FreeAddress;
   // '--- Holds the Next virgin location in RAM.
MemoryBlock* memoryAllocated;
   // '--- Points to the first allocated block.
MemoryBlock* memoryFree;
   // '--- Points to the first freed block.
MemoryBlock* memoryTraveller;
   // '--- Used in Alloc, Free for traversing the List.
MemoryBlock* memoryNext;
   // '--- Used in Alloc and Free, for relinking.
MemoryBlock* memoryPrevious;
   // '--- Ditto.


what will happen?
Alrighty.

When we call Allocate(sizeWeWant), Allocate first traverses the MemoryFree list, searching for any
block on that List that is greater, or equal to the size we want. If no suitable block can be found,
and the FreeAddress is not greater than the RAM we actaully hold, then a new Block will be created
in Virgin space. (thats right, I said Virgin!).

When we go... Free(AllocatedVariable), we will simply unlink the Block we are freeing from the Allocated
List. We link the Blocks Next, to the previous blocks next, we link the next blocks previous, to the previous
blocks Next. Now, the block we are removing is not 'seen' by the Allocated blocks adjacent. Once this is done,
We traverse through the memoryFree list, and point the last 'free' blocks Next, to the block we are freeing.
We link the Blocks previous, to the last block of the memoryFree list.

The problem with this, is Memory fragmentation.
However, I dont have much of an idea on how to 'fix' the fragmentation problem.
As I see it, In order to 'reshuffle' RAM, we would to reorganize whatever is actually in RAM.
For example, Two blocks are seperated by a free block, Delete the free block from existence, and copy the second
block to begin at the end of the First block. The reshuffle from that would make the memory contiguous, however -
the pointer that points the allocated memory for those blocks, would have to be updated so that it pointed to the
correct location. that, I have no idea to do at this point in time, without having a variable in the Block itself
that keeps track of the location of the Pointer that actually points to it.

so far, this is my concept for Citadel Memory management. Please note, that this will be done in Paging Mode.
I dont particularly want to give each variable an entire Page (4kb) of Memory. It seems wasteful.

Any suggestions on how to 'fix' the fragmentation, feel free.
Please tell me what you think of my idea so far.
Thanks!

PS:
Citadels Paging system will allocate the needed Page for the 'RAM' being allocated. For example, if a program running in... say... 0x00200000, and it wants to allocate something,
Citadel will make a page in the correct virtual location and point it to the correct free physical location.

[zeii[at-uni]]

Alrighty, ive come across and Idea to kill the fragmentation.
(System wide).

Exammple:

BLOCK1 BLOOOOOOOOOOOCK2 BLK3

Alrighty, we deallocate Block2.
To the application itself, We are using the linked list system, its own special 'virtual memory map' WILL get fragmented.

However, System memory wont.
What I do PHYSICALLY... is copy BLK3, to where Block2 began, and then Map the Virtual address of BLK3 start point, to Block2s start point, then simply, I update the FreeAddress location.

So, to the application, in its own virtual memory map:

BLOCK1 BLOOOOOOOOOCK2 BLK3
BLOCK1 FREEEEEEEEEEEEEE BLK3

However, I could possibly reposition BLK3 in the Applications virtual map aswell.

Once... block2 was 'unlinked' from the Map, I could set it so Block2, was the same size as Block3, same position as Block2.
And then, simply... set the next on block2, to nothing.
previous on block2, to Block1, Get rid of Block3 entirely...
and Map Block2s 'pointing memory to' Block3.

so, then we have...
BLOCK1 BLOCK3 FREE....

Well, thats my idea?
However, how can I remap... a virtual address to a new physical address WHILE in Paging mode? Would the Physical address we specify, be treated as a Virtual address by the Processor?

[elderK]

Hmm... any try to map something in unmapped space...

like...
I want to see if...
The Page Table, has to be in Virtual=Physical space.
And can things can be remapped while in Paging Mode.

And it keeps page faulting...
... Do I need a seperate Directory? One for Directory-manipulating operations? Switch to the V=P directory, when im changing Page data on the 'showtime' direcotry, then when thats done - re-enabling the Paging system that I modified?

Hmm...

[YeXo]

I don't get your problem with memory fragmentation. If you let every program have their own virtual address space, you can make physically non-continuous memory look continious to the program.

The page table don't has to be in physical=virtual space, but if you want to update it you need the virtual address. You don't need a seperate directory for manipulating operations, you only have to make sure the kernel code you're executing remains at the same virtual address.

[elderK]

The thing im trying to avoid, is fragmentation in physical memory.
I want to waste as little space as possible.

And, in my crackpot zany brain, ive come up with a method that should let me do that. Waste as *little* space as possible. .

The Virtual address of the Kernel never, ever changes... but I was still having major difficulty remapping things. So, now... When im doing some crazy stuff and need 'temporary' access to full Physical RAM, without any virtualization, I just suspend all processes for like a flash second and do what I need to with Paging off, then I Re-enable it... awaken all processes.

Physical Memory and Virtual memory is as contiguous as possible, so I waste as little space as possible. Least, so far.

[YeXo]

The thing im trying to avoid, is fragmentation in physical memory.
I want to waste as little space as possible.

This is exactly the thing I don't understand. You don't waste space when you physical memory is fragmented because you have paging which makes sure the application thinks the memory is continious although the physical memory isn't.

[elderK]

Finnished the concept Physical Memory manager for Citadel
(Ive made some design choices, that I havent implemented yet, so the layout of the code, might seem a little contradictory).

Anywho, The Memory manager (the new one, written by me) can be found in ./memory/citadel_kernel_s1mm.c (and .h)

It *seems* to work ok, but... Im the guy who wrote it, so subconsciously ill work around its failings.

Ive commented it, the best... I could through the coding frenzy.
So, I hope you will understand it.

Tell me what you think, Please.
[Mental note: Add a function that will list the Free list, aswell as the Allocated list, so I can check it...]
[Second mental note: Add a 'Sorting' function, that reshuffles the Freelist, so the smallest free blocks are at the bottom.]

Thanks!
It *seems* to work probably, although I had a few problems, Theyve been 'hack' fixed. I tried to clean it up the best I could.

According to Tests, the BIGGEST 'lost' fragment, will be 16bytes.
Everything greater than that, will be tracked.
(That 16bytes, is because thats how much space I need for Block descriptor, tracking the Memory block the program allocated.)

Citadel Kernel, Most recent source:
http://homepages.ihug.co.nz/~scroodle/citadel-src-300506.tar.gz

Same thing as before, You may need to play with the MAkefile, and set GCC to your GCC, and supply the -fno-builtin. Im using the crosscompiler I setup, so it automatically applies thsoe settings.

Also, I use NASM to assemble the stubs, so you will need that aswell.

Alrighty, im tired, Nighty night all

[elderK]

Alrighty, a new day.
New bugs.

Found some in the Block deletion in the Linked List, and im in the process of fixing them now.

Ive written some Debugging functions, which will print out the Blocks on the Lists, so... I can make sure the Lists are being relinked properly, and total deallocation is working, etc.

Ill post the source once Ive fixed these bugs.

[proxy]

your idea seems like it could work in principle...but you make me wonder, why bother?

I mean, physical memory fragmentation is simply a non-issue if your allocation unit is pages. Aside from the kernel heap itself, my kernel is only capable of growing a process by an exact multple of page size. And it is up to the application itself to manage this usefully. When the process terminates, or explicitly gives pages back, then they go back into the free list.

Since paging regardless of physical locality will have the same over head (a page fault on a page next to the last good page is just as expensive as a page fault on a page 4000 pages down in memory). I fail to see what you gain besides complexity.

proxy

[Zeii[At-Uni]]

I suppose I dont gain all that much
I just set out to write a Physical Memory manager that was decent. .

I wanted to save as many bytes as possible!
(Which, seems to have not worked after all. Ill have to optimize it somewhat).

The Structure to track a block, is 16bytes. Which... means a 1byte allocation, needs 17 bytes of free space.

I could lesson the size of course - but... simply getting rid of the Owner field of the Block descsriptor, then itd be 12bytes, and if I got rid of the Size field, 8 bytes.

Id have to work out the size from the 'previous' and 'next' block addresses, finding the difference between them, but even then, the blocks linked, could be vastly apart.

Who knows.
Anyways, I *think* Ive solved the bugs.
New functions included.

phys_listFree and phys_listAllocated will print a list on screen of the List, starting from Root Block.

I put the above functions in simply for Debugging, as I can track if the List is being relinked correctly or not, and I can also check the sizes of the 'new' blocks being created to map 'fragmented' space.

It seems to work well so far, but any testing you could do would be appreciated.

Please keep in note, that atm, any allocation and deallocation will spew lines and lines of Debug info. Once im satisfied with the PMM, Ill disable the debug output.

Citadel Source (31st May, 2006)
http://homepages.ihug.co.nz/~scroodle/citadel-src-310506.tar.gz


Yours coffee-fully,

[mystran]

Are you trying to do page level management here, or malloc level management? Does your system have all processes in the same address space? Are you trying to avoid the use of paging?

Normally one has a physical memory manager that only deals with fixed size. Internal fragmentation isn't important here, and external fragmentation is solved by paging. Any reasonable amount of per-page overhead is more or less fine, since the allocation unit itself is quite large (4k for Intel).

Then one has a separate malloc that deals with small blocks. My next malloc implementation (i need a replacement to the current hack) will have total of 8 bytes of overhead (on 32-bit): size before and after a block to allow travelsal and coalescing fast (yeah, got the idea from dlmalloc), 8 bytes alignment, leaving lowbits available for indicating whether free and such.

Mininum allocation size is therefore 16 bytes (of which 8 bytes are used by the allocator). For free blocks I also get 8 more bytes (since that's the minimum space in any block) which I can use for double linked free lists (doubly, so I can coalesce in constant time). Sure there's overhead, but I don't see a point with going with much less.

Now, if I really had a lot of objects of only a few bytes, I'd write a separate allocator for those; such objects are usually best special cased. In fact, I'd go so far as to claim that if majority of your objects are 8 bytes or less, then you need a garbage collector.

[Warrior]

Correct, I'd write a low level physical manager which you use for allocating things for paging. Now once you do this and have your paging enviroment up, then write a heap manager which serves up smaller sizes suitable for malloc()/free().

For my low level physical manager I use a bitmap since I really use the pmm rarely outside of paging. Then for the heap manager I use a block management system similiar to yours.

[Ryu]

I hope to think that that is always not going to be correct. It should be depending on how you want your OS, what is it specifically designed for and if paging is right for it.

I am wanting to design an OS that its native user modules run in a non paging enviroment. Personally I don't believe in using paging to get something like 10GB of virtual RAM from physically 1GB RAM. But using paging to get around the fragmentation issue yes. But if you came out with an algorithm that suffices in the fragment issue, then I don't see why one would require paging unless you want that fake slow 10GB of ram. Again this is just my perspective, I know in typical design people will use the paging as thier user module enviroment but its not always the case for someone else.. (Yes if everyone walked down the street, no one would of invented the wheel, teehee!)

Zeii: You got me interested, I may look at the source to find out how you depreciated fragmentation.

[mystran]

The key issue is protection: how you gonna separate different processes so that one process, whether buggy or malicious, can't damage other processes.

Looking at it historically, there's basicly 4 known ways to do this:

1. Run on program at a time. You can still do time-sharing, but it involves fully suspending one process, and loading another process. Clearly very inefficient if we want to get one process to run while another is waiting for something like I/O, but sufficient to allow to people to use the same machine with text terminals at the same time.

2. Divide memory into segments, either statically or dynamically. Then give each process one or more segments. This is much better, but has a problem with external fragmentation. If the processors can do segment base relative addressing, you can do compaction without the processes noticing, but this involves moving data in memory, which is slow in a large system.

3. Dive memory into fixed size pages. You can still manage your system as segments, but if you got paging hardware, you can now cheaply move things around as long as you're happy with page-size alignment. But if you got paging, then you could just as well give each process it's own address space, so you don't need to move anything at all.

Now, with any of the above, you can use virtual memory if you want. In case of whole-process-swapping, you only need memory for the largest process, and anything else is virtual anyway, right? For segmentation and paging, it's the same, but you can now only use swap when you run out of memory, instead of doing it always anyway. Paging is more flexible here, since you can bring only parts of the process in memory, and exploit principle of locality. Ofcourse, if you don't care about virtual memory, then it's a non-issue.

4. Only allow a safe language. With a typesafe language, whether statically or dynamically typed, as long as you don't allow "free" pointers, you can even use a single heap if you want, and if the whole thing has a compacting GC, then you also avoid any fragmentation issues. Systems based on this method do exist (Singularity would be an example).

The important thing here, is that the only solutions that doesn't rely on special hardware, are 1 and 4, and even 1 really needs a way to separate the trusted operating system code from the normal application code. So basicly, the only known way to have mutually protected processes running on a computer, without any hardware enforced protection mechanism, is to use a safe language.

Naturally a provably safe assembler program can be considered to be written in "safe language" for this purpose. This has been done too; the trouble I see with this, is that once you have to write an assembler program such that you can prove it never violates system rules, and provide the proof for the system to verify (against the program).

I can't see that many good reasons for such a proving system; you could just as well have a safe bytecode language, sufficiently close to normal machine language that it can be easily translated into safe machine code. If you take the trouble to implement some reasonable subset of type-inference with algebraic datatypes into the IL-to-Native compiler, then that compiler should be able to shake most of the runtime checks out of the native code.

There's two advantages of proof+native instead of safe IL: 1) you don't need the IL-to-Native compiler in your trusted code base and 2) as long as the proof verification is correct, a bug in the compiler (which can do all kinds of complex optimizations and analysis) won't compromise system security.

Anyway, there's lots of research in this area, so I'm not going to go any futher with this already unreasonably long post, but please let me know if you're interested; I can try to summarize what I'm aware of in a separate thread.

Hope all this makes some sense, and doesn't contain too much misinformation.

[Candy]

4. Only allow a safe language. With a typesafe language, whether statically or dynamically typed, as long as you don't allow "free" pointers, you can even use a single heap if you want, and if the whole thing has a compacting GC, then you also avoid any fragmentation issues. Systems based on this method do exist (Singularity would be an example).

The important thing here, is that the only solutions that doesn't rely on special hardware, are 1 and 4, and even 1 really needs a way to separate the trusted operating system code from the normal application code. So basicly, the only known way to have mutually protected processes running on a computer, without any hardware enforced protection mechanism, is to use a safe language.

Naturally a provably safe assembler program can be considered to be written in "safe language" for this purpose. This has been done too; the trouble I see with this, is that once you have to write an assembler program such that you can prove it never violates system rules, and provide the proof for the system to verify (against the program).

I can't see that many good reasons for such a proving system; you could just as well have a safe bytecode language, sufficiently close to normal machine language that it can be easily translated into safe machine code. If you take the trouble to implement some reasonable subset of type-inference with algebraic datatypes into the IL-to-Native compiler, then that compiler should be able to shake most of the runtime checks out of the native code.

This sounds quite like 1984 from George Orwell to me... You can't insult the government since the words to do so have been taken from the language...