The unpaged world ...

[elderK]

Hey folks,

Out of curiousity - How many of you have seriously considered the various possibilities of managing a single unpaged address space?

By unpaged here, I mean all virtualized memory disabled.
Zero translation.

WHAT CRAZY @!#$ IS THIS? You might be asking. What is the point
of NON VIRTUALIZED memory? What a waste offff time ...

Well, perhaps. But, I find it an interesting question to ask, considering
every affordable embedded MCU features no MMU.

That got me thinking about a great deal of things. Mostly along the lines of ... If a process grows too large for whatever chunk I hand it, Must it be moved? Since translation is not an option, it seems it would have to be.

If anyone takes time to answer this, with some thought, itd be greatly appreciated.

~Z

EDIT : In this case, Affordable meaning inexpensive enough for a student living in the slums to acquire.

[Solar]

How many of you have seriously considered the various possibilities of managing a single unpaged address space?

/me raises his hand.

I come from the AmigaOS, which doesn't make use of the MMU (because for over a decade Amigas didn't have one out of the box). Hence, I read many descriptions of the "scatter loader", dynamic relocations and so forth.

AmigaOS binaries were subdivided into "hunks", which were placed into memory individually. A 1 meg binary might end up as one 512 byte hunk and two 256 byte hunks. Pointers were adjusted during the load process by means of a relocation table. This required some discipline by the programmer and some additional work for the loader, but all in all it worked out well. (And it made for one unholy fast IPC system as all you had to do, ever, was passing a pointer.)

Relocating a process once it's running is tricky, of course - you don't know which other processes might hold pointers to it cached somewhere. You could handle this by yet more programming discipline, though.

[JackScott]

Trusting programmers?

Now THERE is a recipe for disaster!

[elderK]

Why do so many people fail to remember?

That we have all used systems, that by _our_ own standards (now),
are incredibly insecure and unprotected.

AmigaOS, MS-DOS, Win3.1, Win9x (Seriously, its a lot crappier than most people think - and they already think its crap ).

In any case, You need some faith.
We are kernel developers, not lovely handholding babysitters.

Anywho, This thread is not about the issue of insecurity. Rather, it is about
the allocation mechanisms for unpaged, single address spaces.

And, as an asside - How to deal with its problems. Ie: Relocating a program when it gets too large for its current slab of memory.

~Z

[Ready4Dis]

Give it an out of memory issue, and let the program decide what to do. Seriously though, if you're loading an application, you know if it has enough room or not (because you obviously allocate space to load it to). When it asks for memory, you either have it or you don't (without virtual memory). If you want to move memory around in the middle, you would have to have 'smart' pointers, where you would register all pointers, this way if you had to move some memory, you would lock everything, update all the pointers, then unlock it. The programmers wouldn't be able to play with pointers much though, so it'd depend on lot on developers being nice. I would just return not enough memory however. I don't know to many things that don't support MMU's, except for the really small microcontrollers, but if you have that much limited space and you're trying to run a high level OS, you are going to have memory problems .

[Laksen]

I'm making an unpaged os.

I relocate all modules at loadtime and in that process I resolve the modules API references into the kernel and other processes. That way I don't even need a dedicated IPC system. Granted I will probably need it later as the design grows more complex

I don't get what you are talking about, with "process chunk grows too big"?

[elderK]

Ready4Dis, I like that idea.

I really do. Infact, I think thats freaking brilliant.
Have a pointer table. Itll be a little slower but - Itd allow me to perform memory protection without MMU hardware.

As for really small Microcontrollers, well, yes.
Those are used mostly in the embedded space. They outsell the more advanced cpus by millions every year. Maybe even billions.

Laksen, Process not having enough memory is simple:

Process runs, you give it 512KiB memory.
It does allocations, yadda yadda yadda.
That 512KiB is exhausted.

You cannot page, so you cannot simply allocate it a page and map it in.
Memory is not contiguous, so you cant simply... expand for the hell of it without slamming into something else.

With Segmentation, you could relocate - but that requires copying larger and larger chunks of memory about.

Without Segmentation, it involves the relocation of code and the update of many pointers...

However, having a Pointer table - which the API manages... Thats a lot nicer.

Then again, Microcontrollers have EEPROMs built in - with capacities far exceeding the controllers data RAM. Could simply block the process - relocate it if you have the memory. If not, burn it to EEPROM and bring something else in. So, more like banking.

A solution with smart pointers and Amiga-style hunks seems kinda interesting.

~Z

[Laksen]

I solve that by having two memory allocation levels. On the bottom I have the kernel MM. This will service the kernel ofcourse and then it'll service the processes.

The processes have a memory manager each at kernel level. Those will service the memory allocation from the process and will request memory from the kernel.

This makes perfect sense in my mind, but I don't know if I've misunderstood you

[Dex]

My OS does not use paging and uses a single address space (it users a relocatable file format for drivers etc), OS's like the xbox also do not use paging etc, and most people would not see them as crap or old.

While the Xbox kernel is based on the NT/Windows 2000 kernel, it's extremely lean. There's no virtual memory paging, and only a single process is allowed (though that process can spawn multiple threads). The entire kernel fits into 150KB--far less than the 1MB original goal.
The development library is polling-based rather than event driven (unlike Windows). This was due directly to feedback from game developers.
The game owns the hardware--it runs in ring 0, and has direct access to all hardware (including CPU and graphics).
Memory allocation is the responsibility of the app--there's no front-end memory allocation.

[lollynoob]

Hello all you non-paging folks, I'm doing one of these as well. For executables, I'm just using relocatable a.out binaries (for simplicity), and for any problem where something might need to be virtualized (e.g. memory), I'm planning on just having whatever manages the resource return a "not there" error code. Seems to make everything a whole lot easier.

As far as security issues, plenty of operating systems have gone without memory protection and done fine; they've already been mentioned earlier, but the fact that they've been heard of shows that they weren't complete failures. As far as my system goes, the priority is on the freedom of the software to do what it wants; regardless of if that's "dangerous" or not.

[Colonel Kernel]

Singularity can run with paging disabled. Nevertheless, the kernel still tracks memory usage in terms of pages. Each process occupies some set of pages for its code, which never grows, and for its garbage collected heap and thread stacks, which can grow arbitrarily.

For the heap, the entire thing doesn't necessarily need to be contiguous. The GC is a trusted part of the system that tracks which pages belong to the process' heap and can free unused ones if needed, so it knows where they all are.

The interesting thing is how stacks are implemented in Singularity -- they are not contiguous either. When a stack grows to a certain size, the next stack frame is allocated in a region somewhere else and linked to the previous region. Eventually, when the stack unwinds back to the beginning of that new region, it is unlinked and freed and the stack is switched back to the previous region. The code that does this linking and unlinking is injected into each process when it is compiled from IL to native code by Bartok. So you could probably use a similar technique as long as there is some way in your OS to instrument the code before you run it.

[elderK]

ColonelKernel, That sounds cool.
And, it sounds vaguely like something I was pondering a short while after my last post.

Amethyst (my kernel) in its current MMU-powered IA32 form, uses a series of Pool allocators - dedicated for the fragmentation-free allocation requirements of Kernel space structures.

Userspace allocation has always been a "I dont think about that". To me, Userspace management of Memory is up to the Process _or_ the libraries powering it. That being said, the Kernel obviously provides mechanisms to Userspace for the allocation and release of Pages.

All of these techniques would continue to function fine in a nonpaged environment. Except now, one problem solved by memory translation rears its ugly head once again ...

Fragmentation.

Sure - The kernel can allocate stuff without _internal_ fragmentation to its Pools and with minimal tracking overhead. Sure, Userspace programs _could_ just request arbitrary pages. No problem there, until memory has been seriously thrashed.

And - There may be say, 3MiB freespace available. The problem? That 3MiB is sparse and formed of seperate 4K Chunks, all scattered through the address space, none of it contiguous. This seems to be the largest threat in nonpaged environment?

A Buddy Allocator could possibly be the solution to that.

That being said, There are also some assumptions that can be drawn ...

With the embedded devices (ie: That could be a Cellphone or perhaps some crazy Automotive thing), the various programs that will execute requiring the Kernel will already be stored onchip. Either as part of the Kernels Image, or loaded afterwards in EEPROM.

Fragmentation is irrelevant in that case, since Applications are only started at the time the Device is?

Then again, I refuse to limit the system to that. So, the new assumption is - that in this case, speed is second to the utilization of storage. The Buddy Allocator would have to be tiny, absolutely positively tiny.

*ponder, ponder, ponder*
~Z

EDIT: Well, no, it doenst need to be small... since whatever logical page size I decide on, is physically mapped. Oy, Ive been spoiled far too long by virtualized memory Twists the way I think. Just store the metadata directly in the blocks - transient style. Will require a little programmer discipline, but its a small price to pay for zero overhead and perfect power-of-two blocks.

[Solar]

Trusting programmers?

Now THERE is a recipe for disaster!

Actually I had the feeling that, on AmigaOS, it created a "darwinist" environment. If an application crashed, it was bad. It had the potential of wiping out everything you worked on at that time. On the one hand, it meant that such applications were shunned, and on the other, it meant that coders really put some effort into making their apps stable.

Early on in Win9x / Linux times, I got the impression that many coders thought "so what when it segfaults once in a while, that's what memory protection is for". Woefully, some coders still think this way.

The reason to decide against memory protection are simple. There are platforms where an MMU is not an integral part of the CPU, and adding one would add cost / power consumption. And memory protection / paging does imply a performance penalty, and however slim that may seem on desktop CPUs (where you wouldn't want to do without MP anyway), it can become quite an issue on low-powered devices (like Amigas then, or embedded systems today).

[jal]

it can become quite an issue on low-powered devices (like Amigas then, or embedded systems today).

Of course, almost all current embedded devices you can actually run an OS on are superior in terms of processor power to an 68000. Most have all applications in ROM anyway, so the whole protection issue is non-existing.


JAL

[Colonel Kernel]

Most have all applications in ROM anyway, so the whole protection issue is non-existing.

Application code may be in ROM, but the data is still in RAM. Without some means of protection apps can crap all over each other's heaps and stacks.