Porting to architechture with no MMU (ipod/gba ARM)

[JJeronimo]

It makes certain things trickier - you need support for PIC (position-independent code); a binary format that has proper relocation tables,

I think that's the classical way to load programs in archs without MMU...

If the architecture doesn't support executing PIC eficiently, then parhaps the best choice is relocation tables...

I would say you need both. PIC allows you to access data relative to the instruction pointer, which is fine for your binary image,

But x86 has no such addressing mode (unless you are in long mode)

but you need relocation tables once you want to access e.g. libraries - which will be at a different offset from your binary at each startup.

You need relocation tables even without shared libraries because, on x86, the assemblers are unable to generate position-independent code unless the programmer explicitly writes the program that way...

In my (purely theoric) opinion, address space sharing makes it much simpler to implement shared libraries than with address space separation...

I wouldn't move a library around once it has been loaded.

So you risk having the address space extremelly fragmented... (unless you conseder the holes in the library's space as heap, which is a solution, too)

You will always have some programmers caching a library's address locally, either due to laziness or claims of efficiency. When the library moves, and programs access the old location because they don't go through the proper system services to get the current library address... booom.

???
I thought that the loader automatically relocated library calls...

Why did I say you need offset tables? Easy: Library versions. If your apps were jumping at library functions directly, you would have to relink all applications using a certain library once you update that library. Functions change length, new functions get inserted between the old ones...

I doubt it's a good idea to relink an application against it's libraries just because you now have a new library version!
*Newly executed* programs will use the new lib, not the old ones...

AmigaOS solved it quite smartly: When you request a library from the system via OpenLibrary(), the system would give you the "base pointer" to that library - either the position where it was already loaded previously, or the address it was just loaded to due to your request.

Didn't understand...
I was talking only about shared (but not dynamic linked libraries)...




PS: Have you ever considered to omit shared (loadtime linking) library support at all and using IPC to call library functions? That's exactly what I'm thinking about to implement in the future!
Some time ago, when I started doing low level programming in DOS, one of the first programs I worked on was a Brainfuck interpreter... And I immediatly thought about a BrainfuckOS, capable of multitasking Brainfuck apps by counting interpreted instructions! One of the things I though was using the brainfuck "terminal" (read with "," and written to with ".") as a command space to allow apps to access kernel services (the IO manager and th IPC subsystem)... When an app wanted to provide some shared function(ality) (being it a previlleged service or an ordinary utilitary function), it would registry that command (which in fact would behave like an IPC (or would I say RPC?) port) sending the correct commands to the kernel command space... To call a shared function from some other program, that program would issue a command calling that function...

None of this stupid ideas have passed beyond pure "JJ's brainfuck" so far!


In fact, that's a lie! I'm still thinking about using IPC to call functions, but now I've thrown away that idea of interpreting BF code... also, I'm convinced that a new mechanism, called "IPC scripts" I've invented will attenuate the overhead of calling the (kernelmode) IPC subsystem too much times during program execution and waiting for the other process to handle the request and return back the result...
I've not yet spent much time thinking about this applied to library calls... but for calling system functions (such as "servers" in a microkernel design) I think it will work...


PS2: Another solution for having dynamic link functions in any OS (not just without MMU), that relies on IPC too (but this time not for making the proper function calls) would be to implement a library server that would enumerate all the library functions available using the IPC namespace (assuming that the kernel has one) and the application that needs the function would ask that server to provide the function through *some* way that the underlying platform allows to use (shared memory, IPC messaging to copy the code through address spaces, a far pointer), already correctly relocated to the address the requesting app asks (this isn't needed if the address space is shared, as happens without MMUs)...


PS3: None of this solutions is suitable if you already implemented a shared library mechanism (they are just design proposals), but I hope it provides some ideas the work arround the problem...

JJ

[Solar]

But x86 has no such addressing mode (unless you are in long mode)

x86 does have a MMU. But you are right, this architecture would run only with a performance penalty on a x86. (There is a way to create PIC on x86, but it uses up one of the registers, of which there aren't many to begin with.)

I wouldn't move a library around once it has been loaded.

So you risk having the address space extremelly fragmented... (unless you conseder the holes in the library's space as heap, which is a solution, too)

Yes, that's one disadvantage of not having a MMU (the other being not having memory protection). That is why it is beneficial to have a binary format that allows "scattering" the binary across available memory chunks.

When the library moves, and programs access the old location because they don't go through the proper system services to get the current library address... booom.

???
I thought that the loader automatically relocated library calls...

Yes, during loading. But if you move the library after a binary has been loaded, you would have to update all references in the binary again, and you can no longer be sure you get them all.

(Note that I was talking about dynamically linked libs.)

Didn't understand...
I was talking only about shared (but not dynamic linked libraries)...

Oh, OK. I tend to use the two terms as equivalent, because I consider shared libs to be of little effective use if they aren't also dynamically linked.

PS: Have you ever considered to omit shared (loadtime linking) library support at all and using IPC to call library functions?

Considered it for Pro-POS, to get over language limitations... never got beyond planning stage.

[Ready4Dis]

What is the difference between a negative base pointer, and a regular pointer? I mean, a jump table at X, then x+4, then x+8, etc can be used in exactly the same manner (this is how my libraries started out). I could easily add another function, by extending the table to Base+FuncCount*4. I don't really know what the difference would be by returning a pointer to the end of my function table and counting backwards, just seems like it would cause more confusion than anything.

[Solar]

What's the significance of the negative base pointer?

You have a library base pointer. At a negative offset from that base pointer is the jump table, at a positive offset is the actual library code.

Significance? Perhaps it was easier to handle that way. Or it had something to do with addressing limitations. (IIRC, 68k could do relative jumps only to a certain maximum plus / minus from a given base.) I don't know, really.

[Ready4Dis]

What's the significance of the negative base pointer?

Significance? Perhaps it was easier to handle that way. Or it had something to do with addressing limitations. (IIRC, 68k could do relative jumps only to a certain maximum plus / minus from a given base.) I don't know, really.

I don't know, doesn't seem likely since the app calling it probably wasn't doing a relative jump within this table, and the library itself only has the table as a reference to it's functions, not to use itself, and even if it did use it itself, it would have to be in such a way that other apps could use it (so it's FULL address would need stored), either way, it wouldn't change the distance from the table to the code of the library anywas, the table would be the exact same size . Was just wondering if there was a known reason for doing it that way vs. the way I was doing it .

[TheQuux]

Hi,

There's some interesting notes in the uClinux FAQ:

Q. Does uClinux support multitasking? What limitations are imposed by not
having a MMU?

A. uClinux absolutely DOES support multi-tasking, although there are a
few things that you must keep in mind when designing programs...

1. uClinux does not implement fork(); instead it implements vfork().
This does not mean no multitasking, it simply means that the
parent blocks until the child does exec() or exit(). You can still
get full multitasking.

The most interesting part is part 1, where it says there is multi-tasking while describing a system that I'd call single-tasking (i.e. only the most recently created task that hasn't terminated will be able to use the CPU).


Cheers,

Brendan

Actually, it is multitasking:

Init vforks, and the child blocks.
The child exec's /bin/sh; the parent is woken from La Petite Morte...

Heh.

I can't think of any other way to do it, because exec would need to either copy the address space (in which case, everything would need to be relocated, which would cause enormous problems with self-modifying code, or absolute data addressess)l or map the memory to two places at once, which would not be possible without a MMU.