When a domain invokes a key either explicitly or implicitly, the kernel acts in two phases:
- The dry run where it sets no global state that is meaningful between entries into the kernel except for shared and exclusive locks.
- After all of the locks have been acquired the wet run begins and global state under control of the exclusive locks may be modified and data under the shared locks may be examined.
If some lock cannot be acquired the operation will be deferred or fail and then there are then several cases:
- The domain may be referencing some component of itself or perhaps a component of a domain to which the kernel must return the response as when the last key of the message is a resume key to another domain.
Some such cases are allowed but general and slower code is required.
- A loop in a meter chain is discovered or other cases of a node participating twice in a transaction.
Such cases are disallowed.
- In a MP configuration two CPUs may be running the kernel or one CPU may be attempting to operate on a node that is a component of another domain that is running on another CPU.
Keykos has no such code just now as it does not support MP yet.
The exclusive locks are in place to detect and avoid these collisions.
It might be necessary to signal the CPU running the locked domain to deschedule and unlock that domain, and then to run the domain attempting the blocked action.
This would make rescind operations very prompt.
After the kernel has responded to the invocation the locks are released.
Each node or page has a count of the number of times it has been locked in shared mode.
It is quite rare for a node to participate in one kernel transaction twice but it was easier to allow than to disallow.
See this note contrasting the function of primitive hardware locks and those of Java.
The “general code” referred to above sounds complicated.
Actually it is simpler than the fast code.
The general code marshals the message from the domain into an area of the kernel thus matching the conceptual steps.
This marshaling is oblivious to the meaning of the message and the kernel object being invoked.
The marshaled message includes the keys from the message.
The invoker is then unlocked.
Enough of the recipient is verified to be in core to receive the response message.
The action is then attempted and resulting message placed in a separate kernel area.
The message is then delivered to the recipient.
An issue is the semantics of an operation that changes how the recipient will receive the response.
The recipient may have been “receptive” before the operation but not after.
If this is a security hole then such operations may be disallowed.
They once were and still may be.
Except for performance, there would be no need for the fast case which merely interprets the message as it is found in the component parts of the invoking domain.
more info
Locking Instructions
Some instruction sets have “compare double and swap” and this allows you to insert an element into a doubly linked list.
How do we do this in machines without such instructions?
The doubly linked lists in the Keykos kernel reside in item space.
Each linked key includes a pointer to the head of the linked list where a lock for the list resides.
If we come upon such an element that we need to modify we:
- Load the pointer to the list head—this load is atomic and the pointer is always to an item space element.
- We grab the lock and look again at the pointer in the key to see if it still points to the list head.
If not we release the lock and restart.
If we cannot get the lock we dither.
- We now had exclusive access to the entire list and we can perform sequential list updates.
Our lock also gives us access to the page or node associated with the list head, which is often useful.
When we need only to examine the chain we grab the shared lock which is a counter in the list header.
To “dither” means that we look to see if we are the one that holds the exclusive lock.
If so there are special rules that determine whether the operation is allowed.
If it is not us we consult with scheduling logic to arrange for the actor (some domain) to be scheduled when this lock conflict is less likely.
I think that “compare double and swap” would be of considerable performance benefit in some cases.