Loadable modules in a monolithic kernel

[ManOfSteel]

Hello,
I would like to know how can someone make a monolithic kernel with loadable modules instead of a pure monolithic kernel (the "one big mess").
My guess is that every device driver could be located in a fixed memory location and the IDT entries for example would be pointing to fixed memory locations handlers, right? Is it possible to do it in that way? Is yes, what would be the pros and cons of this method? Is there any other way to do it?
Thank you in advance.

[Pype.Clicker]

Well, the main problem with using the IDT as a 'functions pointers' for modules is that calling an interrupt is quite expensive (at least, much more expensive on IA-32 that it used to be on 8086 or older processors found in 8-bits systems)

Plus, as you might guess, enforcing each module to have its own load address can quickly become a nightmare if new modules are to be added or if they grow ...

The response is to have modules that can be linked to the kernel at runtime. Most of the time, this is achieved by relocating the module when it is loaded and patching a symbol list, e.g.

- the module will contain a list of symbols it imports from the kernel's symbol list
- the kernel will resolve that list and write symbols' address (e.g. where function are) in an array.
- when module need to access one of the kernel's functions, it simply looks at the corresponding index in the import array

If, in addition, modules have the option of _exporting_ symbols aswell, you can use functions provided by both kernel and other module almost transparently.

A more complete solution will consist of using directly the symbol table from the module "executable" to build the import/export lists and to patch addresses that make references to the imports directly instead of requiring an intermediate array (that's what's done in clicker)

[JoeKayzA]

In fact it's quite the same as dynamic link libraries in user space, right?

cheers joe

[Kemp]

My OS is going to have a system where drivers have two calls that they must implement.

1) An initialisation routine that sets up the hardware etc as needed by the driver, allocates resources, all that stuff

2) An 'operate' routine that takes as one its parameters a function number (very like when you call the BIOS) and carries out the appropriate thing (reading, writing, whatever) based on that and the other parameters.

The kernel will have a call that takes the name of the device that needs to be used, the function number and a pointer to a block of data that the driver will need (saying things like where the data to read is, or where the data needs to be written to) whose structure is entirely defined by the driver (hence allowing sub-functions if need be). It finds the location of the operate routine for the driver for that device from a list it keeps and passes the data on to it.

That's the overview, subject to tweaking and me screwing it up ;D

[AR]

@Kemp: How exactly is the driver supposed to allocate memory and heap space? (or resolve device conflict, or dependant devices [eg. USB, PS/2 Keyboard/Mouse]?)

[Kemp]

It allocates memory/heap space the same way anything else does Device conflicts are something I'm thinking about at the moment. I'm taking the loading method of the OS looking for devices and loading drivers for the ones it finds (rather than a driver just being loaded for no apparent reason), so there shouldn't be too much in the way of conflicts.

[Solar]

Ah, another time of AmigaOS reminiscence... they did it this way:

• you have a library with the functions foo(), bar() and baz(). The size of those functions (and thus their start addresses) change with every build, but don't worry.
• after the library is compiled, an offset table is generated: one pointer for every function in the library, pointing to the start address of that function.
• the offset table is linked in front of the library binary, together with a size count for the offset table at the lowermost address.

Device drivers, in AmigaOS, were just a special kind of library.

That could give you this memory layout for our example:

• [-16] size of offset table
• [-12] offset of foo() entry (from library base)
• [-8] offset of bar() entry (from library base)
• [-4] offset of baz() entry (from library base)
• [0+] library code (black box)

Now, when you called the kernel function OpenLibrary(), the kernel checked whether the lib was already resident, loaded it into memory somewhere if that's not the case, and returned the library base pointer to the caller (start of library code plus size of offset table).

All the caller now had to know was the table locations of the various functions - easily done through the library headers. A call to foo(), then, would be a call to (LibraryBase - 12)().

If you add new functions, you add new slots in the offset table for them, keeping the slots of already existing functions the same. You could even do really tricky stuff for backwards compatibility if you require a call to OpenLibrary() stating version number of the library, and providing multiple offset tables (and thus, potentially multiple versions of the same function)...

But what if a library wants to call the kernel? Easy - the kernel itself is a library too, and puts its base pointer into some well-known location (AmigaOS used 0x0000 0004, which was a sure way to kill your system if you inc'ed a NULL pointer...).

Perhaps this is some inspiration for you. Perhaps it's just another reason for other vets here making fun of the forum Amigian.

Edit / PS: I just realized that this is, indeed, about the only way to allow for stripped lib binaries...

[smiddy]

I am currently working on installable and uninstallable device drivers. As you pointed out you have to have a routine that updates teh IDT based on the new code (new only because this is the happy path scenario, other scenarios exist). I have successfully implemented this type of routine. I am working out the details for the Device Manager, as it has to be the traffic cop for the install and uninstall. It also has to be able to know what devices are already within the hardware framework of the system it is running (you can't just assume a particular device is there without checking for it first). I am working out details for that now and should have that done in a month or two.

As has been pointed out, I too am using a set of required functions, much like DOS' and OS/2's device driver interface. There are links on the web that describe these interfaces pretty well and there is ASM source out there for their implementation. I added the required function of uninstall/deinitialize.

Uninstall/deinitialize has to revert back to the last installed driver for that particular device, if one was available. The OS should have a set of basic internal drivers that would be the last driver that could not be uninstalled, like the basic console driver, otherwise you'd loose the ability to interface user to machine.

This is very top level writing here. There are a slew of specifics that need to be accomplished in order for threads/processes using the driver would have to recognize or time out when no action occured when a device driver is snatched away too. That is the job of the Device Manager, the traffic cop.

So, in my mind it is very doable, and seems to work so far along on my development. I just stuck reading specifications on SMBIOS, PnP, ACPI, PCI, et al in order to develop the traffic cop, the Device Manager.

[ManOfSteel]

Hello,

Well, the main problem with using the IDT as a 'functions pointers' for modules is that calling an interrupt is quite expensive (at least, much more expensive on IA-32 that it used to be on 8086 or older processors found in 8-bits systems)

Why would it be any different from using it in the standard way? What is the difference between writing in every IDT entry (bytes 1, 2, 7 and the address offset of the handler routine within the kernel and writing the memory address of the loaded module outside the kernel?
For example:

Code: Select all

TestEntry:
dw TestEntryHandler
dw 0x8
db 0
db 10001110b
dw TestEntryHandler

and

Code: Select all

TestEntry:
dw 0x102000
dw 0x8
db 0
db 10001110b
dw 0x102000

Plus, as you might guess, enforcing each module to have its own load address can quickly become a nightmare if new modules are to be added or if they grow ...

If new modules are to be added, couldn't we just load a new one in the same place that the old one, simply overiding the old one?
Also, for the growing drivers, we can just make the allocated memory a little bigger so that the drivers have more room. With todays memories (at least 128 MB), we would be wasting a relatively little space. And after all the difference in size between a video driver v1.0 and v2.0 is probably not going to be a few dozen MB, is it? We would be able to predict more or less what will be the optimal size for this driver or that one and we would fix memory portions according to that optimal size.

Most of the time, this is achieved by relocating the module when it is loaded and patching a symbol list

What exactly do you mean by "symbol list"?

[AR]

A "symbol list" is the term given to the list of exported/imported symbols from a library/binary.

For example if you call exit(0); in your C program then your program's symbol list will contain something along the lines of "IMPORT exit @function". The C library would contain "EXPORT exit @function". The process of dynamic linking is to link the imports to the exports in the libraries. In this particular case it would be linking the imports to functions in the kernel. [For an example try objdump --syms <Filename>]

Plus, as you might guess, enforcing each module to have its own load address can quickly become a nightmare if new modules are to be added or if they grow ...

If new modules are to be added, couldn't we just load a new one in the same place that the old one, simply overiding the old one?
Also, for the growing drivers, we can just make the allocated memory a little bigger so that the drivers have more room. With todays memories (at least 128 MB), we would be wasting a relatively little space. And after all the difference in size between a video driver v1.0 and v2.0 is probably not going to be a few dozen MB, is it? We would be able to predict more or less what will be the optimal size for this driver or that one and we would fix memory portions according to that optimal size.

I believe Pype was refering to the link address, if you've had experience with LD you know that code is compiled to "know" (or more accurately, to expect) that it will always be at a certain address in memory. If you have multiple modules linked for the same address then that will quickly become a problem in that modules with the same link address will be mutually exclusive. eg. A braindead example would be that if both the mouse and keyboard driver expect to be at 0xC0400000, since you obviously can't put both modules there you can only have the keyboard or the mouse but not both at the same time.

[Solar]

If new modules are to be added, couldn't we just load a new one in the same place that the old one, simply overiding the old one?

Things tend to grow far beyond initial expectations. If every module gets a fixed address, how long do you think can you manage before you run out of address space for every conceivable combination of modules? It's not as if you could put the USB HID driver and the PS/2 HID driver into the same location as there will be someone using a USB mouse with a PS/2 keyboard. And it goes on...

We would be able to predict more or less what will be the optimal size for this driver or that one and we would fix memory portions according to that optimal size.

Like the prediction that 640 kB should be enough for everyone? "You're welcome to write a GFX driver for our OS, but you have to accept it mustn't grow larger than x MB or it won't fit"...

[ManOfSteel]

Hello,

AR,

For example if you call exit(0); in your C program then your program's symbol list will contain something along the lines of "IMPORT exit @function". The C library would contain "EXPORT exit @function". The process of dynamic linking is to link the imports to the exports in the libraries. In this particular case it would be linking the imports to functions in the kernel. [For an example try objdump --syms <Filename>]

Humm, I program in ASM and do not know much C, so what does all this mean in binary code? What does "import/export a function" really means in practice? Import/export what? From what location? To what location?

A braindead example would be that if both the mouse and keyboard driver expect to be at 0xC0400000, since you obviously can't put both modules there you can only have the keyboard or the mouse but not both at the same time.

They cannot expect to be at the same address: it would be impossible because every driver type will have its predefined fixed location, so a KBD driver cannot switch place with a mouse driver, a serial driver cannot be at the same place than a parallel, etc... The module loader would recognize the driver type from its header. It is impossible that they become "mutually exclusive". And if there is more than one version of the same driver, the loader will choose and load the latest unless the user decides otherwise (through settings).

Solar,

Things tend to grow far beyond initial expectations. If every module gets a fixed address, how long do you think can you manage before you run out of address space for every conceivable combination of modules? It's not as if you could put the USB HID driver and the PS/2 HID driver into the same location as there will be someone using a USB mouse with a PS/2 keyboard. And it goes on...

Well, I have quite a big number of devices attached to my computer, Windows currently has 51 installed device drivers of any kind, a lot of them are useless because I do not use all of these hardware. They all make less than 2 MB and in my OS they would not be loaded, providing more memory free space.

Like the prediction that 640 kB should be enough for everyone? "You're welcome to write a GFX driver for our OS, but you have to accept it mustn't grow larger than x MB or it won't fit"...

Yes, at that time, 640KB was enough for everyone. Hardware changes and so does software and operating systems. And if you need a 3D graphics driver that means you have a computer designed for games with probably 256MB RAM or more (especially today). For more flexibility, memory portions sizes for every device driver could be increased automatically by the kernel or maybe manually by the user through customizing utilities depending on the memory size available, or the computer use (bureau, gaming, networking) for example.

[Pype.Clicker]

<my stuff about interrupts/>

Why would it be any different from using it in the standard way? What is the difference between writing in every IDT entry (bytes 1, 2, 7 and 8 ) the address offset of the handler routine within the kernel and writing the memory address of the loaded module outside the kernel?

Well, the problem is not in writing to the IDT entries (the fact you only have 256 of them can however become a nuisance if you're growing things) ... the problem is with performance penalty of calling an interrupt on a Pentium X compared to a commodore ...

When issueing "int xx", the CPU will check that you have the right to do so, etc. and will then have to check if it needs to switch stacks or not, then if the selector in the IDT entry is code segment or not, and if you're entitled to use it, etc. etc.

Comparatively, issueing "call seg:offset" is less heavy (that would mean giving a segment number to each module, and using far call when doing cross-modules call). However, it still requires quite a bunch of extra checks and you might not will to suffer those checks if your module provide, for instance, a firewall rule to be applied on every packet ...

The approach Solar has spoken of (which is basically what occurs in ELF shared libraries), will conduct to

Code: Select all

  mov ebx, __MODULE_BASE ; <- patch this at load time
  mov eax,[ebx+__FUNCTION_ENTRY]
  call eax

or

Code: Select all

  mov ebx, _MY_MODULE_LIBRARIES_LIST
  mov eax,[ebx+__LIBRARY_IDENTIFIER]
  mov eax,[eax+__FUNCTION_ENTRY_IN_LIBRARY]
  call eax

while it's much more efficient, it still get a memory lookup penalty for every function call. You might like it or you might not.

The suggestion i made was more something like having

Code: Select all

topatch:
  call _LIBRARY_FUNCTION
 ...

topatchtoo:
  call _LIBRARY_FUNCTION

...
relocation_entry:
  db 'libraryFunctionName',0
  dd topatch+1, topatchtoo+1

And the nice thing is that most object formats (both ELF and COFF) already contain that relocation entries ... So when loading, you'll lookup a table for "libraryFunctionName" and once you get its actual address, you modify "call _LIBRARY_FUNCTION" with "call <the address you retrieved>" thanks to the list of reference (topatch, topatchtoo) associated with "libraryFunctionName" in the module.

[Solar]

Well, I have quite a big number of devices attached to my computer, Windows currently has 51 installed device drivers of any kind, a lot of them are useless because I do not use all of these hardware. They all make less than 2 MB and in my OS they would not be loaded, providing more memory free space.

The point is that you would have, for every "type" of driver, to reserve a memory region big enough for the maximum conceivable driver of that type. Like, pointer device drivers are loaded to 0x0010 0000 and must not be larger than 1 MByte. Keyboard drivers start at 0x0020 0000.

You just limited all vendors to a maximum of 1 MByte driver space, even for bluetooth data gloves that also read RFID chips. (Or the keyboard stops working.) You also limited all systems to a maximum of one pointing device. (Laptop users will hate you for it.)

Yes, at that time, 640KB was enough for everyone. Hardware changes and so does software and operating systems.

Yet you believe you can come up with a memory map that will withstand all changes of time - or dump most of of your established driver base when revising the map?

And if you need a 3D graphics driver that means you have a computer designed for games with probably 256MB RAM or more (especially today).

But even when a system doesn't need a graphics driver, it cannot load any other driver modules to that RAM space because driver modules can only be loaded to the RAM location reserved for their type...

For more flexibility, memory portions sizes for every device driver could be increased automatically by the kernel or maybe manually by the user through customizing utilities depending on the memory size available, or the computer use (bureau, gaming, networking) for example.

Including the required relocation code for the library binary... so why make libraries non-relocatable in the first place?

Or have I missed something in your approach?

[Legend]

Don't forget that you might need different hardware of the same type in the same computer. 2 different sound cards, several different hard disk controller (on board eide + scsi raid for example) etc.