Cake #1.01 - Kernel Dynamics System Overview

related cakes: -nothing written yet-
related teacups: -nothing written yet-

cake last reviewed on 13.09.01 by Pype
enjoy your meal

The Main Purpose

The main idea behind the Kernel Dynamics System is to allow easy run-time linking of some modules and server into the kernel. Most of those linkings are made at boot-time, but some of them might change during the session (by example, if you change the Operating mode or if you use hot-plug peripherals)

A module is a pack of objects that will "upgrade" the kernell, i.e. that will either add some new services or improve some existing ones. In fact, the whole Clicker kernel can be seen as a group of components that interacts with each others (memory managers, storage sets classes ...). Some of those components are part of the microkernel, other are imported from modules.

Following this point of view, a module is just but a binary file that hold the code of some component plus informations about how to link them into the system, and KDS is the way we have to express those informations. (Well, enough about module boring stuffes, you all know about Linux module, well, that's the same concept, the same reason, etc. but the way we link them differ. Let's focus on that).

The K.D.S. is intended to give three types of services:

  • naming: through the naming system, it allows to register some name/value bindings and to assign serial numbers to names (substitutes strings a unique id). Moreover, it's possible to define sub-namespaces and creating hierarchic names.
  • services: each service (i.e. filesystem, video access, memory management, etc.) can be seen as a network where servers (modules that provides that service) and clients (modules that requires that service) are interconnected. Each network is given a unique service-name, which allows potential clients to find it through the naming system (services.*).
  • dlods: the support allows dynamic linking and exchange of objects or datas. This feature is still in early design stage and it's difficult to say if it will be used in final system or not ... See the idea page for more informations

  • How can we link clients to servers ?

    software interrupts
    This is the oldest technique we have. Widely used in ms-dos and other small operating system from that era. The server simply hooks an interrupt handler and install its service. Client is supposed to know which interrupt will be used and use registers to pass arguments and select function for the server.
    This methods has clear drawbacks when you move from a small operating system like dos to a network-aware multiuser multitasking multimedia system. Then, it becomes impossible to attribute interrupt number to all possible servers and still respect the hardware architecture requirements (for instance, under Intel Architecture, interrupts number must be inline constants in the source code, so you need a recompilation if the server move to another interrupt handler!).

    Clicker will use software only to provide a generic system call service to applications (well, there we really need it to swap priviledge level), but not for internal (kernel-to-kernel) communication.
    symbolic name linking
    Linux kernel - like Windows DLL, if i remember well - uses symbolic names to link modules to each other. The key idea is that a module that want to provide access to some functions will register in a "centralised" database the binding between the function name and the function address (let's call that database the symbols table, like in a compiler ;-).
    When another module need a function X, it will simply looks up the database and recover the address. It can then call the function by using indirect calls (pointer to function) or - better - modify its code to make the call appear as a local function (by relocation techniques).

    Clicker uses and extends this technique by the mean of the "ksyms.*" subset of the Naming System for functions that are very frequent and that should never be overloaded by modules. Indeed, once a module has imported a symbol, you have usually no way to remember where it stored its pointer and so changing the binding in the symbols table will have no effect for already registered modules.
    services binding
    This is a major new feature of Clicker, inspired by what exist in high-level object-oriented languages like Java or Scheme, but here at kernel level!
    1. You first give an abstract description of a service through a list of interfaces that might be implemented and a symbolic service name.
    2. When a server-module comes in the system, it will provide and register implementations of one or more interfaces. Binding between interfaces and implementations are recorded for further use. Note that many implementations may exist for the same interface.
    3. When a client finally arrive, it will ask the service to give him an implementation for its personal use. The trick is that the client will always use function pointers through a system call (invocation ), but won't call the functions directly. This guaranteed level of indirection allows us to provide high-level functionnalities like switching from an implementation to another without needing to notify the client...
    Services binding is the major linking scheme for Clicker kernel. You'll find it in paging, logging, enhanced display, binary files interpretation, etc.

    The Naming System


    The naming system allows to store some name-value combinations. A name can be any "regular" character-string (restricted to letters, digits and a few special symbols as _, -, @, &, ...). The value can be an integer, string or a pointer. A binding between a name and a value will be called a key and the name and value will be called key-name and key-content or key-value respectively.
    The kernell has a main naming system, that is, a wide set of keys that is globally accessible to the whole system. This keyset is structured hierarchically by the mean of subsets . The notation convention is to separate each new subset by a dot, as if it was fields in a C structure. So "user.application.emacs.foreground" means "the foreground key in the emacs subset, which stands in the application subset of user.
    To allow subsets, each key gets a few bits of flags to determine whether it is a single key or a set of keys, etc.
  • make unique id's. This is the main purpose, you can assign each new name in the namespace a integer that won't be used by any other names.
  • holding constants. It might be useful to use that naming system to store some "runtime constants", this is some values linked to the machine itself (or its environnement) that can't be easily known at compile-time. So in the namespace "sound" you could link "sound.dsp=0x220", "sound.irq=5" and "sound.dma=1", so any part may know the
  • using short symbolic names. It's quite useful to be able to use a symbolic name, but they're often too long to store or compare. with the naming system, it's possible to use a regular integer as a symbolic name. In fact, you'll just have to "register" the symbolic name with the UID feature enabled, and then use the returned UID. You can also get back the full name if you need it for printing (from the UID), even if this operation can't be guaranteed to be as fast as the search by name.
  • Flags

    KDS_SET creates an empty subset of keys rather than a single key
    KDS_CONSTANT the binding cannot be changed
    KDS_SERIAL do not use the given value (if any) but rather assign a new unique-id as value

    Note: the flags KDS_SET and KDS_SERIAL can't be set together, while the value of a KDS_SET is the namer


    Most of them are self-explanatory, so i won't give more details to them. Note that all of them need a "namer" object as first parameter. This can be the global-namer (if you invoke the system-call) or just any custom-namer. If you want more precise informations, refer to the sources (src/head/sys/naming.h, src/kernel/kds/naming.c) or to doxygen-generated documentation

  • int kdsRegister(namer *me,char *path, int flags, int value)
    Note: if the flag KDS_SERIAL is set, the content of value is not used.
  • bool kdsUnregister(namer *me,char *name)
    Note: by unregistering a keyset, you will automatically unregister (i.e. destroy) all the keys or subsets it holds.
  • int kdsLookup(namer *me,char *name)
    Note: the key-value of a keyset is the namer object of this set, so you can either search the full path each time ex: "services.filesystem.interfaces.readonly"),or search first the subset you need ("services.filesystem.interfaces") and then look in it for your key ("readonly").
    Note Also: that we provided _kds(<path>) and _kds_(<base path>,<relative path>) to make common lookups easiers.
  • int kdsRLookup(namer *me, char* path, int id)
    Note: The result of a id-search will only look in the UNIQUE-ID's reference, so a match with a key where KDS_SERIAL is off won't be returned. A nul-value as return means that no match has been found.

  • A supplementary service - the kds Interner - is intended to trade registering time against memory efficiency of the namer by detecting duplicated keys and reutilising the already-registered key's name (even if the name appears in another subset). For instance, if you have registered "", "", "", the string "name" will be put only once in kds memory, rather than three times as we have had following a naive implementation.

    Services and Network Objects System


    The Services System is designed to provide a way to group module that often communicate together. Each "network" provide a single service to its clients. This service may be implemented by one or more servers.
    extensions Each service has a unique name that identifies it. Those names are hold by the naming system in the keyset "services.*". They may take advantage of the hierachical api, so you can create a subset of services "services.fs.*" that will hold every service related to the file system (for instance).
    operations The main operations on a network is to add/remove entities (i.e. servers and clients). On another hand, you also have primitives to send messages from clients to servers and some other ones to reply messages from servers to clients or broadcast messages.

    For those who knows it, it will probably sounds like the V2OS servers system, except i don't think there's anything about interfaces in V2OS. We are also incredibly more flexible that what V2OS can do with interrupts for addressing schemes.


    Each services (and thus each network) may provide one or more set of function (called interfaces ) to its clients. An interface is defined as an interface name and a set of methods. It also holds a list of servers that implement this interface. These informations are stored in a namespace as the kernel main namespace, but local to the service. One of the key ideas is that a server will never implement an interface partially: either it provides all the functions of the interface, or it does not implement it. Attempts to register a server that implements the interface only partially is treated as a module-loading failure.

    I suggest you give a look to the example: it shows the "files" service with its three possible interfaces ( for open/close and delete methods, array for traditional access and set for db-like access).

    example of interfaces for a filesystem
    In addition to the interfaces definitions (i.e. ordered list of methods names), each server that wants to provide the service to an interface is expected to fills an interface table with pointers to the functions that will implement the corresponding methods.

    The order of function in that table must be the same that the one declared in the interface definition.

    The following table will give you an overview of the internal functions that are used to manage interfaces on a service. Note that this is just a model, developers should refer to doxygen-generated documentations for the true methods names. Here we just try to get how it works. It might be weird to document it as object-oriented code, but in fact, kds is object-oriented design implemented in C ...

    Interface.Interface (nb_methods, Interface *base)
    creates a new (empty) interface that will be an extension of the given base interface (set base to NULL to create an interface from scratch rather by inheritance).
    int Interface.addMethod (name)
    adds a method for an interface. If the given name is already defined, the offset of the previously existing one is returned.
    int Interface.getMethod (name)
    looks up in an interface for a given method (which symbolic name is given)
    status Service.addInterface (name, Interface i)
    Installs an interface on a service. Now we can't modify interface definition anymore, but we can start implement it.
    Interface Service.getInterface (name, sharing_mode)
    Retreives an interface object on a server from its symbolic name. We also give a sharing mode

    an uml overview of services

    Using interfaces (the Clients side)

    There are two ways using interfaces. The first one is to use them to send messages. That is, you'll call a generic function kdsSend(service, message_code, message_params...) , where the message_code has the format "interface:method" . The send function will then find back the corresponding function (after it has choosen the target-server according to the deliver-policy of the network) and call it with the given message_params.

    Another way using interface is to register as a usual client of the interface, and asking for a given set of methods. Once this is done, the client can use kdsInvoque to call a method from its local table (stored in the kdsClient structure. Note that methods are now retreived from constant numbers and are ordered in the local table as the client asked through registration rather than keeping their definition order (as stored in the interface definition). This gives the little advantage of not requiring to store a integer for each method to be called.
    If you plan to use an interface frequently, registering to this interface will significantly improves your code's performance. Remember than a "send" function will have to:

    1. split the message code into an interface and a method name
    2. retreive the appropriate Interface structure from its name in the service's local store
    3. retreive the method number by looking up the interface local store
    4. and then only you can call the method.
    Service.send ("interface:method", message) sends out some message to a server of the given service . The message code has the form "interface:method". The corresponding function is found and called with the message as arguments.
    Client Service.addClient( "interface",
    {"method1", ... , "methodN"},

    registers a regular client (and allocates its client descriptor) on the service for the interface which name is given and requiring the localTable to be filled with the given subset of methods ordered as required.
    Client.Invoque(localId, message)
    invoques a method of the interface through its local identifier (this is, its position in the method enumeration of addClient). Note that localId start with 1, not with 0


    A server is a bunch of function that will provide the service. That is, if you're designing the "", you could write one server for each hardware (and put them into modules). Each of them may provide one or more interfaces for the different group of functions it will provide, so it'll looks like

    server interfaces
    S3 Trio 64 mode select, bitmaps
    S3 ViRGE mode select, bitmaps, 3D
    Riva TNT mode select, bitmaps, 3D, MPEG

    Note that the implementation of the interface "bitmaps" will probably be different for each server, while the design of that interface will be the same for each one (clear(), bitblt(), copyArea(), clearArea(), drawLine(), etc.)

    Server Components

    String name
    The server-name is a string that is supposed to identify it in reports, etc. The server-name has to be unique on the network, any attempt to violate this rule will result in the fail of the second server's creation. If the server has been installed by loading a module, then the name of the server will be the name of the module.
    pid owner Tells which program owns the server. A zero value means that the server was installed by a kernel module, not by a "regular" program.
    listof  Interface This list holds one component for each interface implementation. The main part of an implementation is a table of pointer to functions that mathces with the interface definition. See the details for more infos about the structure of those implementation.
    listof  Client This list holds information about the server's clients that have queryed some function. This list is sweeped at server's disconnection to warn those clients. It's also a common way to store dependencies between modules while a module may be server on a network and client on another one.
    void *extra In some special cases, this field may contain a structure of deliver-specific informations (like a mountpoint for a server of the filesystem).

    Servers-related functions

    Server.Server( name, Module, extra,  open(), close(), <activity-callbacks>)
    This creates a new server for the given service, and tells its name and optionnally the extra parameter (NULL if not necessary). The new server got the pid of the caller as owner field, and has both interfaces and clients lists empty
    This registers the given server as a provider for a given interface. The implementation call depends on a definition structure (kdefMethod []) that is to be extracted out of the module definition. 

    Last modified: Mon Aug 28 22:18:32 /etc/localtime 2000