1 Introduction
SCHEMESTATION uses random 256 bit
identifiers to address agents. The
256-bit size ensures that it is very hard to guess an address of a
specific agent. ([1] gives some elucidating examples
about how hard it would be).
These identifiers (that will be referred to as agent specifiers) are unique
within a domain.
The specifiers have to be mapped to the actual agent entries in the
domains scheduling system. If the corresponding agent has migrated
away, the agent specifier within a domain might also map to another
agent specifier in another domain. Also, the kernel agent and other
such special agents would need their own type of addresses, as would
the external agents.
2 Requirements
An Agent specifier can map to
- Local address, eg. a pointer or index to scheduler's
run queue
- Remote address, eg. a (domain address, agent
specifier) pair
- Special agent address, eg. an integer that
identifies the special agent
- External agent address, eg. an integer that
identifies the external agent.
The addressing system has to provide the means for adding agent
specifier entries, replacing them (eg. resetting the address for a
specifier), efficiently searching them by the specifier and searching them
by the address. Removing entries has to be possible, also.
It must be possible for the user to generate an (unique) agent
specifier, and compare it to another.
There can be several thousand agent specifier entries in the
addressing system, and yet the searching and addition operations must
be done in reasonable time. This implies that the addressing system
might need to use a kind of hash table to store the entries.
There must be a way to save the addressing system to the disk in order
to initiate a controlled system shutdown for persistence (and of
course means to load the saved state back).
Since the virtual machine may block the execution of an agent, there
has to be a storage queue for the messages. It is natural to
store the messages along with the addressing entry, so we demand that the
addressing system is able to maintain the queue.
3 Functionality
The addressing system is first initialized using
addr_initializeaddrsystem. The user can generate random
specifiers using addr_generatespecifier.
An entry that consists of a specifier and an address, can be added
to the data structure using using
addr_addentry-function. If there is need to reset the
address of an entry, it should be done using the
addr_setentry-function instead of deleting and adding
the entry again. This holds the message queue of the entry intact. Entries
can be deleted using the addr_deleteentry or
addr_deleteentriesbyaddress function, if the address
instead of the specifier is known.
Addresses can be compared using
addr_cmpraddr and specifiers using
addr_cmprspec functions.
An entry can be sought by the specifier using
addr_addrbyspec, which returns a pointer to the
address. The pointer is valid as long as the entry is removed from the
system (since the caller could have no way of knowing whether an entry
is removed, he can only trust the entry being valid as long as he does
not give the control back to the addressing
system). addr_specsbyaddr takes an address as the argument
and returns a caller-freed array of matching specifiers.
The addressing system can be saved to disk in order to initiate a
system shutdown using addr_savetodisk. The system can
then be recovered using addr_readfromdisk
For debugging purposes, there is the addr_dumpaddrsystem
function that gives an ascii representation of the whole addressing
system to stdout.
When the virtual machine sets an agent to blocking state, it calls
addr_setmessageblocking that sets the blocking-bit of the
correspondent entries to indicate, that the agent can not receive
messages. (Recall, that there might be several entries and thereby
several message queues per agent.)
Before the shutting down the system, one should call
addr_shutdownaddrsystem to free the memory used by the
addressing system.
4.2.15 The functions of module Addressing |
| File addressing-internal.h
C-functions:
-
void addr_addresstoasc(INOUT char* str, IN Address *address)
Description: | Prints the address address to str in readable -
that is in hexadecimal - format. |
- Status addr_deliver_messages(IN ActorEntry *entry)
-
AddrStatus addr_dumpentry(IN ActorEntry* entry)
Description: | Prints the contents of the entry to STDIN. Returns ADDR_OK,
if the entry is not invalid. |
- addr_entriesbyaddr(IN Address* addr)
- addr_entrybyspec(IN ActorSpecifier* spec)
-
void addr_freeentry(IN ActorEntry* entry)
Description: | Frees the memory used by the entry. The entry
definetely will be invalid after calling this. |
-
unsigned addr_hashvalue(IN void *item, IN long size, IN long maxvalue)
Description: | Counts a hash value from an arbitrary long item. Uses very simple
and thereby propably non-optimal algorithm. The hash value is
returned as the return value. The size argument specifies
the length of the item. The hash value will be moduloed
between 0 and maxvalue. |
-
void addr_hexdump(INOUT char* dest, IN char* source, IN int len)
Description: | Dumps len characters from source to dest in
hexadecimal format. |
- Status addr_push_message(IN ActorEntry *entry,
struct Message *message)
-
AddrStatus addr_readentry(IN int fd)
Description: | Reads an entry from the disk. Returns ADDR_OK on success,
ADDR_INTERNAL or ADDR_INVALIDARG otherwise (eg. fd bad etc.) |
-
AddrStatus addr_resizehash(AddrResizeAction resizeaction)
Description: | Either doubles or halves the size of the address hash table. If
the enlarge argument is ADDR_ENLARGE, enlargement is done,
halving takes place otherwise. The table will be reallocated and
all entries rehashed. Return ADDR_OK on success. |
-
unsigned addr_spechashvalue(IN ActorSpecifier *addr)
Description: | Counts a hash value from a ActorSpecifier. The value is counted
simply by anding the first bytes of the specifier, since the
ActorSpecifier should adequetely random. The hash value is
returned as the return value. The function uses the
addresssystem.hashmask as the mask for anding the hash value. |
-
void addr_spectoasc(INOUT char* str, IN ActorSpecifier* spec)
Description: | Prints the actor specifier spec to str in readable -
that is in hexadecimal - format. |
-
AddrStatus addr_writeentry(IN int fd, IN ActorEntry* entry)
Description: | Writes an entry to disk. Returns ADDR_OK on success, ADDR_INTERNAL
or ADDR_INVALIDARG otherwise (eg. fd bad etc.) |
File addressing.h
C-functions:
-
AddrStatus addr_addentry(IN Address* address, IN ActorSpecifier* spec)
Description: | Adds an ActorEntry to the addresssystem.addresstable.
The added entry is constructed of the address and
spec arguments. Values are copied.
If the given specifier pointer is NULL, a random one is
generated with addr_generatespecifier(). Return ADDR_OK on
success. Requires, that address is non-NULL. |
- addr_addrbyspec(IN ActorSpecifier* spec)
-
Bool addr_cmpraddr(IN Address *a, IN Address *b)
Description: | Compares tho Addresses, return true on match, false otherwise.
If either a or b is NULL, false is returned. |
-
Bool addr_cmprspec(IN ActorSpecifier *a, IN ActorSpecifier *b)
Description: | Compares tho ActorSpecifiers, return true on match, false
otherwise. If either a or b is NULL, false is
returned. |
-
int addr_deleteentriesbyaddress(IN Address* Address)
Description: | Deletes the ActorEntry that matches the arguments address
from addresssystem.addresstable. Returns the number of succesfully
deleted entries. |
-
AddrStatus addr_deleteentry(IN ActorSpecifier* spec)
Description: | Deletes the ActorEntry that matches the arguments spec
from addresssystem.addresstable. Returns ADDR_OK on success, and
ADDR_ADDRNOTFOUND, if no such entry was found.
Message queue is deleted. |
-
AddrStatus addr_dumpaddrsystem()
Description: | Prints the contents of the addresssystem to STDIN. Returns ADDR_OK,
if the entry is not invalid. |
-
void addr_initaddresssystem(INOUT void)
Description: | Initializes the addresssystem. This essentially includes
allocating memory for the addresstable, and initializing the rando
number generator. |
-
Status addr_readfromdisk(int fd)
Description: | Recovers the address system from disk. The address system has
to be saved using addr_savetodisk().
This would be typically called when one wants to restart a frozen
SchemeStation domain.
Takes the file descriptor to be read as an argument.
|
-
Status addr_savetodisk(int fd)
Description: | Saves the whole address table to disk in order to do a temporary
system shut down. The address system can be completely recovered
from the disk using addr_readfromdisk().
Takes the file descriptor to be written as an argument.
|
-
Status addr_set_blocking(ActorSpecifier *address, Bool arg)
Description: | This is as addr_setmessageblocking, but for addresses and not
local scheduler identifiers. |
-
AddrStatus addr_setentry(IN Address* address, IN ActorSpecifier* spec)
Description: | Sets the address of the specified actor specifier (spec to
address. If the specifier already exists in the addressing
system, this should be used instead of addr_deleteentry() and
addr_addentry(), because the latter convention destroys the actors
message queue.
Returns ADDR_OK on success, ADDR_ADDRNOTFOUND if the specifier
spec was not found. Requires address and spec
to be non-NULL. |
-
int addr_setmessageblocking(SchedulerID id, Bool arg)
Description: | Sets address table entries to blocking or non blocking
state. Returns the number of entries affected |
-
void addr_shutdownaddrsystem(INOUT void)
Description: | Frees the memory used by address system. All (reverse and normal)
entries will be invalid after calling this. |
-
unsigned addr_specsbyaddr(IN Address* addr, OUT ActorSpecifier** specs)
Description: | Returns a caller freed array of ActorSpecifiers (not pointers to
them) that match the argument addr. The argument spec is set
to point to that array. The return value will be the number of
addresses found. This is essentially an interface to
addr_entriesbyaddr(). The pointer is guaranteed to remain valid until another
procedure in the address module is called, but not necessarily
any longer. |
[1] Scheneier, Bruce. Applied Cryptography : Protocols, Algorithms,
and Source Code in C, 2nd ed. 1995, John Wiley & Sons
|