Addressing module specification

Document formatted by vherva at Fri Apr 24 11:23:18 1998 on the host schemestation. This document is produced by the SchemeStation project during the Tik-76.115 course.

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 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) Description: 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) Description: addr_entrybyspec(IN ActorSpecifier* spec) Description: 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) Description: 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) Description: 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