diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/info/mds.texinfo | 779 |
1 files changed, 779 insertions, 0 deletions
diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo index 949df95..01fb223 100644 --- a/doc/info/mds.texinfo +++ b/doc/info/mds.texinfo @@ -132,6 +132,8 @@ of crashing. * Interprocess Communication:: How servers and clients communicate. @end menu + + @node Layers @section Layers @@ -299,6 +301,8 @@ and wait for a reply from all of them. * Interception:: Implementing protocols and writing unanticipated clients @end menu + + @node Environment Variables @section Environment Variables @@ -774,8 +778,11 @@ into headers and payloads. @menu * Macros:: Writing macroscopic systems. * Auxiliary Functions:: Auxiliary functions for servers. +* Data Structures:: Data structures available in libmdsserver. @end menu + + @node Macros @section Macros @@ -1138,9 +1145,781 @@ value are exactly those of @code{waitpid}. +@node Data Structures +@section Data Structures + +libmdsserver provides a small set of datastructures +that are used by the @command{mds} servers. All of +these are written with marshal-functionallity. + +@table @asis +@item @code{client_list_t} @{also known as @code{struct client_list}@} +In the header file @file{<libmdsserver/client-list.h>}, +libmdsserver defines a dynamic list for storing +client ID:s. + +@item @code{linked_list_t} @{also known as @code{struct linked_list}@} +In the header file @file{<libmdsserver/linked-list.h>}, +libmdsserver defines a double linked linear +sentinel-array-linked list. + +@item @code{hash_table_t} @{also known as @code{struct hash_table}@} +In the header file @file{<libmdsserver/hash-table.h>}, +libmdsserver defines a hash table. + +@item @code{fd_table_t} @{also known as @code{struct fd_table}@} +In the header file @file{<libmdsserver/fd-table.h>}, +libmdsserver defines a lookup table for small +positive integer keys, intended as an alternative +to hash tables for file descriptors as keys. + +@item @code{mds_message_t} @{also known as @code{struct mds_message}@} +In the header file @file{<libmdsserver/mds-message.h>}, +libmdsserver defines a data structure for message +between the server or client and the master server, +with the capability of reading for a socket. +@end table + +These data structures share a common set of associated +function. However, they do not use the same functions; +they are identical except they are are named with the +associated data structure. We will use @code{X_t} +as an example. + +@table @asis +@item @code{X_destroy} [(@code{X_t* restrict this}) @arrow{} @code{void}] +Releases all resouces in @code{*this}, +@code{this} itself is however not @code{free}:d. + +However, @code{hash_table_destory} and +@code{fd_table_destory} have another signature. + +@item @code{X_clone} [(@code{const X_t* restrict this, X_t* restrict out}) @arrow{} @code{int}] +Create a deep duplicate of @code{*this} and store +it in @code{*out}. + +@item @code{X_marshal_size} [(@code{const X_t* restrict this}) @arrow{} @code{size_t}] +Calculates the exact allocate size needed for +the parameter @code{data} in the function +@code{X_marshal} if called with the same +@code{this} parameter. + +@item @code{X_marshal} [(@code{const X_t* restrict this, char* restrict data}) @arrow{} @code{void}] +Marshal the state of @code{*this} into +@code{data}. The number of bytes that +will be stored (contiguously) in @code{data} +can be calculated with @code{X_marshal_size}. + +@item @code{X_unmarshal} [(@code{X_t* restrict this, char* restrict data)}) @arrow{} @code{int}] +Unmarshal a @code{X_t} from +@code{data} into @code{*this}. Returns +zero on success and @code{-1} on error. +The number of bytes read from @code{data} +should, if required, have been precalculated +with @code{X_marshal_size} and stored in an +earlier location of @code{data}. + +However, @code{hash_table_unmarshal} and +@code{fd_table_unmarshal} have another signature. +@end table + +@menu +* Client List:: The @code{client_list_t} data structure.. +@end menu + + + +@node Client List +@subsection Client List + +To create a client list, allocate a +@code{client_list_t*} or otherwise obtain +a @code{client_list_t*}, and call +@code{client_list_create} with that +pointer as the first argument, and +the @code{0} as the second argument, +unless you want to tune the initialisation. +@code{client_list_create} will return +zero on and only on successful initialisation. +@code{client_list_create}'s second parameter +--- @code{size_t capacity} --- can be used +to specify how many element the list should +initially fit. It will grow when needed, but +it is a good idea to tell it how many elements +you are planning to populate it with. + +@code{client_list_t} has two associated +functions for manipulating its content: + +@table @asis +@item @code{client_list_add} [(@code{client_list_t* restrict this, uint64_t client}) @arrow{} @code{int}] +This function will add the element @code{client} +to the list @code{*this}, and return zero on +and only on success. + +@item @code{client_list_remove} [(@code{client_list_t* restrict this, uint64_t client}) @arrow{} @code{void}] +This function will remove exactly one occurrence, +provided that there is at least on occurrence, +of the element @code{client} for the list @code{*this}. +@end table + +The retrieve the number elements stored in +a list, reads its variable @code{size_t size}. +The variable @code{uint64_t* clients} is +used to retrieve stored elements. + +@example +void print_elements(client_list_t* this) +@{ + size_t i; + for (i = 0; i < this->size; i++) + printf("Element #%zu: %" PRIu64 "\n", i, this->elements[i]); +@} +@end example + + + + + @node GNU Free Documentation License @appendix GNU Free Documentation License @include fdl.texinfo @bye + + /** + * The size of the arrays + */ + size_t capacity; + + /** + * The index after the last used index in + * `values` and `next` + */ + size_t end; + + /** + * Head of the stack of reusable positions + */ + size_t reuse_head; + + /** + * Stack of indices than are no longer in use + */ + ssize_t* reusable; + + /** + * The value stored in each node + */ + size_t* values; + + /** + * The next node for each node, `edge` if the current + * node is the last node, and `LINKED_LIST_UNUSED` + * if there is no node on this position + */ + ssize_t* next; + + /** + * The previous node for each node, `edge` if + * the current node is the first node, and + * `LINKED_LIST_UNUSED` if there is no node + * on this position + */ + ssize_t* previous; + + /** + * The sentinel node in the list + */ + ssize_t edge; + +/** + * Create a linked list + * + * @param this Memory slot in which to store the new linked list + * @param capacity The minimum initial capacity of the linked list, 0 for default + * @return Non-zero on error, `errno` will have been set accordingly + */ +int linked_list_create(linked_list_t* restrict this, size_t capacity); + +/** + * Pack the list so that there are no reusable + * positions, and reduce the capacity to the + * smallest capacity that can be used. Not that + * values (nodes) returned by the list's methods + * will become invalid. Additionally (to reduce + * the complexity) the list will be defragment + * so that the nodes' indices are continuous. + * This method has linear time complexity and + * linear memory complexity. + * + * @param this The list + * @return Non-zero on error, `errno` will have been set accordingly + */ +int linked_list_pack(linked_list_t* restrict this); + +/** + * Insert a value in the beginning of the list + * + * @param this:linked_list_t* The list + * @param value:size_t The value to insert + * @return :ssize_t The node that has been created and inserted, + * `LINKED_LIST_UNUSED` on error, `errno` will be set accordingly + */ +#define linked_list_insert_beginning(this, value) \ + (linked_list_insert_after(this, value, this->edge)) + +/** + * Remove the node at the beginning of the list + * + * @param this:linked_list_t* The list + * @return :ssize_t The node that has been removed + */ +#define linked_list_remove_beginning(this) \ + (linked_list_remove_after(this, this->edge)) + +/** + * Insert a value after a specified, reference, node + * + * @param this The list + * @param value The value to insert + * @param predecessor The reference node + * @return The node that has been created and inserted, + * `LINKED_LIST_UNUSED` on error, `errno` will be set accordingly + */ +ssize_t linked_list_insert_after(linked_list_t* restrict this, size_t value, ssize_t predecessor); + +/** + * Remove the node after a specified, reference, node + * + * @param this The list + * @param predecessor The reference node + * @return The node that has been removed + */ +ssize_t linked_list_remove_after(linked_list_t* restrict this, ssize_t predecessor); + +/** + * Insert a value before a specified, reference, node + * + * @param this The list + * @param value The value to insert + * @param successor The reference node + * @return The node that has been created and inserted, + * `LINKED_LIST_UNUSED` on error, `errno` will be set accordingly + */ +ssize_t linked_list_insert_before(linked_list_t* restrict this, size_t value, ssize_t successor); + +/** + * Remove the node before a specified, reference, node + * + * @param this The list + * @param successor The reference node + * @return The node that has been removed + */ +ssize_t linked_list_remove_before(linked_list_t* restrict this, ssize_t successor); + +/** + * Remove the node from the list + * + * @param this The list + * @param node The node to remove + */ +void linked_list_remove(linked_list_t* restrict this, ssize_t node); + +/** + * Insert a value in the end of the list + * + * @param this:linked_list_t* The list + * @param value:size_t The value to insert + * @return :ssize_t The node that has been created and inserted, + * `LINKED_LIST_UNUSED` on error, `errno` will be set accordingly + */ +#define linked_list_insert_end(this, value) \ + (linked_list_insert_before((this), (value), (this)->edge)) + +/** + * Remove the node at the end of the list + * + * @param this:linked_list_t* The list + * @return :ssize_t The node that has been removed + */ +#define linked_list_remove_end(this) \ + (linked_list_remove_before((this), (this)->edge)) + +/** + * Wrapper for `for` keyword that iterates over each element in a linked list + * + * @param list:linked_list_t The linked list + * @param node:ssize_t The variable to store the node in at each iteration + */ +#define foreach_linked_list_node(list, node) \ + for (node = (list).edge; node = (list).next[node], node != (list).edge;) + +/** + * Print the content of the list + * + * @param this The list + * @param output Output file + */ +void linked_list_dump(linked_list_t* restrict this, FILE* restrict output); + + + + + +/** + * Hash table entry + */ +typedef struct hash_entry +{ + /** + * A key + */ + size_t key; + + /** + * The value associated with the key + */ + size_t value; + + /** + * The truncated hash value of the key + */ + size_t hash; + + /** + * The next entry in the bucket + */ + struct hash_entry* next; + +} hash_entry_t; + + +/** + * Value lookup table based on hash value, that do not support + */ +typedef struct hash_table +{ + /** + * The table's capacity, i.e. the number of buckets + */ + size_t capacity; + + /** + * Entry buckets + */ + hash_entry_t** buckets; + + /** + * When, in the ratio of entries comparied to the capacity, to grow the table + */ + float load_factor; + + /** + * When, in the number of entries, to grow the table + */ + size_t threshold; + + /** + * The number of entries stored in the table + */ + size_t size; + + /** + * Check whether two values are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + */ + compare_func* value_comparator; + + /** + * Check whether two keys are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + */ + compare_func* key_comparator; + + /** + * Calculate the hash of a key + * + * If this function pointer is `NULL`, the identity hash is used + * + * Be aware, this variable cannot be marshalled + * + * @param key The key + * @return The hash of the key + */ + hash_func* hasher; + +} hash_table_t; + +/** + * Create a hash table + * + * @param this Memory slot in which to store the new hash table + * @param initial_capacity The initial capacity of the table + * @param load_factor The load factor of the table, i.e. when to grow the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor); + +/** + * Create a hash table + * + * @param this:hash_table_t* Memory slot in which to store the new hash table + * @param initial_capacity:size_t The initial capacity of the table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define hash_table_create_tuned(this, initial_capacity) \ + hash_table_create_fine_tuned(this, initial_capacity, 0.75f) + +/** + * Create a hash table + * + * @param this:hash_table_t* Memory slot in which to store the new hash table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define hash_table_create(this) \ + hash_table_create_tuned(this, 16) + +/** + * Release all resources in a hash table, should + * be done even if construction fails + * + * @param this The hash table + * @param keys_freer Function that frees a key, `NULL` if keys should not be freed + * @param values_freer Function that frees a value, `NULL` if value should not be freed + */ +void hash_table_destroy(hash_table_t* restrict this, free_func* key_freer, free_func* value_freer); + +/** + * Check whether a value is stored in the table + * + * @param this The hash table + * @param value The value + * @return Whether the value is stored in the table + */ +int hash_table_contains_value(const hash_table_t* restrict this, size_t value) __attribute__((pure)); + +/** + * Check whether a key is used in the table + * + * @param this The hash table + * @param key The key + * @return Whether the key is used + */ +int hash_table_contains_key(const hash_table_t* restrict this, size_t key) __attribute__((pure)); + +/** + * Look up a value in the table + * + * @param this The hash table + * @param key The key associated with the value + * @return The value associated with the key, 0 if the key was not used + */ +size_t hash_table_get(const hash_table_t* restrict this, size_t key); + +/** + * Look up an entry in the table + * + * @param this The hash table + * @param key The key associated with the value + * @return The entry associated with the key, `NULL` if the key was not used + */ +hash_entry_t* hash_table_get_entry(const hash_table_t* restrict this, size_t key); + +/** + * Add an entry to the table + * + * @param this The hash table + * @param key The key of the entry to add + * @param value The value of the entry to add + * @return The previous value associated with the key, 0 if the key was not used. + * 0 will also be returned on error, check the `errno` variable. + */ +size_t hash_table_put(hash_table_t* restrict this, size_t key, size_t value); + +/** + * Remove an entry in the table + * + * @param this The hash table + * @param key The key of the entry to remove + * @return The previous value associated with the key, 0 if the key was not used + */ +size_t hash_table_remove(hash_table_t* restrict this, size_t key); + +/** + * Remove all entries in the table + * + * @param this The hash table + */ +void hash_table_clear(hash_table_t* restrict this); + +/** + * Wrapper for `for` keyword that iterates over entry element in a hash table + * + * @param table:hash_table_t The hans table + * @param i:size_t The variable to store the buckey index in at each iteration + * @param entry:hash_entry_t* The variable to store the entry in at each iteration + */ +#define foreach_hash_table_entry(table, i, entry) \ + for (i = 0; i < (table).capacity; i++) \ + for (entry = (table).buckets[i]; entry != NULL; entry = entry->next) + +/** + * Unmarshals a hash table + * + * @param this Memory slot in which to store the new hash table + * @param data In buffer with the marshalled data + * @param remapper Function that translates values, `NULL` if not translation takes place + * @return Non-zero on error, errno will be set accordingly. + * Destroy the table on error. + */ +int hash_table_unmarshal(hash_table_t* restrict this, char* restrict data, remap_func* remapper); + + + + + + /** + * The number of entries stored in the table + */ + size_t size; + + /** + * Map from keys to values + */ + size_t* values; + + /** + * Map from keys to whether that are in used, bit-packed + */ + uint64_t* used; + + /** + * Check whether two values are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + */ + compare_func* value_comparator; + +/** + * Create a fd table + * + * @param this Memory slot in which to store the new fd table + * @param initial_capacity The initial capacity of the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int fd_table_create_tuned(fd_table_t* restrict this, size_t initial_capacity); + +/** + * Create a fd table + * + * @param this:fd_table_t* Memory slot in which to store the new fd table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define fd_table_create(this) \ + fd_table_create_tuned(this, 16) + +/** + * Release all resources in a fd table, should + * be done even if construction fails + * + * @param this The fd table + * @param keys_freer Function that frees a key, `NULL` if keys should not be freed + * @param values_freer Function that frees a value, `NULL` if value should not be freed + */ +void fd_table_destroy(fd_table_t* restrict this, free_func* key_freer, free_func* value_freer); + +/** + * Check whether a value is stored in the table + * + * @param this The fd table + * @param value The value + * @return Whether the value is stored in the table + */ +int fd_table_contains_value(const fd_table_t* restrict this, size_t value) __attribute__((pure)); + +/** + * Check whether a key is used in the table + * + * @param this The fd table + * @param key The key + * @return Whether the key is used + */ +int fd_table_contains_key(const fd_table_t* restrict this, int key) __attribute__((pure)); + +/** + * Look up a value in the table + * + * @param this The fd table + * @param key The key associated with the value + * @return The value associated with the key, 0 if the key was not used + */ +size_t fd_table_get(const fd_table_t* restrict this, int key) __attribute__((pure)); + +/** + * Add an entry to the table + * + * @param this The fd table + * @param key The key of the entry to add + * @param value The value of the entry to add + * @return The previous value associated with the key, 0 if the key was not used. + * 0 will also be returned on error, check the `errno` variable. + */ +size_t fd_table_put(fd_table_t* restrict this, int key, size_t value); + +/** + * Remove an entry in the table + * + * @param this The fd table + * @param key The key of the entry to remove + * @return The previous value associated with the key, 0 if the key was not used + */ +size_t fd_table_remove(fd_table_t* restrict this, int key); + +/** + * Remove all entries in the table + * + * @param this The fd table + */ +void fd_table_clear(fd_table_t* restrict this); + +/** + * Unmarshals a fd table + * + * @param this Memory slot in which to store the new fd table + * @param data In buffer with the marshalled data + * @param remapper Function that translates values, `NULL` if not translation takes place + * @return Non-zero on error, errno will be set accordingly. + * Destroy the table on error. + */ +int fd_table_unmarshal(fd_table_t* restrict this, char* restrict data, remap_func* remapper); + + + + + +/** + * Message passed between a server and a client or between two of either + */ +typedef struct mds_message +{ + /** + * The headers in the message, each element in this list + * as an unparsed header, it consists of both the header + * name and its associated value, joined by ": ". A header + * cannot be `NULL` (unless its memory allocation failed,) + * but `headers` itself is NULL if there are no headers. + * The "Length" should be included in this list. + */ + char** headers; + + /** + * The number of headers in the message + */ + size_t header_count; + + /** + * The payload of the message, `NULL` if none (of zero-length) + */ + char* payload; + + /** + * The size of the payload + */ + size_t payload_size; + + /** + * How much of the payload that has been stored (internal data) + */ + size_t payload_ptr; + + /** + * Internal buffer for the reading function (internal data) + */ + char* buffer; + + /** + * The size allocated to `buffer` (internal data) + */ + size_t buffer_size; + + /** + * The number of bytes used in `buffer` (internal data) + */ + size_t buffer_ptr; + + /** + * 0 while reading headers, 1 while reading payload, and 2 when done (internal data) + */ + int stage; + +} mds_message_t; + + +/** + * Initialise a message slot so that it can + * be used by `mds_message_read` + * + * @param this Memory slot in which to store the new message + * @return Non-zero on error, errno will be set accordingly. + * Destroy the message on error. + */ +int mds_message_initialise(mds_message_t* restrict this); + +/** + * Zero initialise a message slot + * + * @param this Memory slot in which to store the new message + */ +void mds_message_zero_initialise(mds_message_t* restrict this); + +/** + * Extend the header list's allocation + * + * @param this The message + * @param extent The number of additional entries + * @return Zero on success, -1 on error + */ +int mds_message_extend_headers(mds_message_t* restrict this, size_t extent); + +/** + * Read the next message from a file descriptor + * + * @param this Memory slot in which to store the new message + * @param fd The file descriptor + * @return Non-zero on error or interruption, errno will be + * set accordingly. Destroy the message on error, + * be aware that the reading could have been + * interrupted by a signal rather than canonical error. + * If -2 is returned errno will not have been set, + * -2 indicates that the message is malformated, + * which is a state that cannot be recovered from. + */ +int mds_message_read(mds_message_t* restrict this, int fd); + +/** + * Get the required allocation size for `data` of the + * function `mds_message_compose` + * + * @param this The message + * @return The size of the message when marshalled + */ +size_t mds_message_compose_size(const mds_message_t* restrict this) __attribute__((pure)); + +/** + * Marshal a message for communication + * + * @param this The message + * @param data Output buffer for the marshalled data + */ +void mds_message_compose(const mds_message_t* restrict this, char* restrict data); + |