Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision 362948106914d0c4117845a63ad433052f3c1980) +++ uspace/lib/c/Makefile (revision ddd7118f67777e66551eaa92810ca73e704b82c5) @@ -84,4 +84,5 @@ generic/ipc.c \ generic/async.c \ + generic/async_rel.c \ generic/loader.c \ generic/getopt.c \ Index: uspace/lib/c/generic/async_rel.c =================================================================== --- uspace/lib/c/generic/async_rel.c (revision ddd7118f67777e66551eaa92810ca73e704b82c5) +++ uspace/lib/c/generic/async_rel.c (revision ddd7118f67777e66551eaa92810ca73e704b82c5) @@ -0,0 +1,307 @@ +/* + * Copyright (c) 2010 Jakub Jermar + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +/** + * This file implements simple relation support for the async framework. + * + * By the term "relation", we mean a logical data path between a client and a + * server over which the client can send multiple, potentially blocking, + * requests to the server. + * + * Clients and servers are naturally connected using IPC phones, thus an IPC + * phone represents a connection between a client and a server. In one + * connection, there can be many relations. + * + * Relations are useful in situations in which there is only one IPC connection + * between the client and the server, but the client wants to be able to make + * multiple parallel requests. Using only a single phone and without any other + * provisions, all requests would have to be serialized. On the other hand, the + * client can make as many parallel requests as there are active relations. + * + * There are several possible implementations of relations. This implementation + * uses additional phones to represent relations. Using phones both for the + * primary connection and also for its relations has several advantages: + * + * - to make a series of requests over a relation, the client can continue to + * use the existing async framework APIs + * - the server supports relations by the virtue of spawning a new connection + * fibril, just as it does for every new connection even without relations + * - the implementation is pretty straightforward; a very naive implementation + * would be to make each request using a fresh phone (that is what we have + * done in the past); a slightly better approach would be to cache connected + * phones so that they can be reused by a later relation within the same + * connection (that is what this implementation does) + * + * The main disadvantages of using phones to represent relations are: + * + * - if there are too many relations (even cached ones), the task may hit its + * limit on the maximum number of connected phones, which could prevent the + * task from making new IPC connections to other tasks + * - if there are too many IPC connections already, it may be impossible to + * create a relation by connecting a new phone thanks to the task's limit on + * the maximum number of connected phones + * + * These problems can be helped by increasing the limit on the maximum number of + * connected phones to some reasonable value and by limiting the number of + * phones cached to some fraction of this limit. + * + * The cache itself has a mechanism to close some number of unused phones if a + * new phone cannot be connected, but the outter world currently does not have a + * way to ask the phone cache to shrink. + * + * To minimize the confusion stemming from the fact that we use phones for two + * things (the primary IPC connection and also each relation), this file makes + * the distinction by using the term 'key phone' for the former and 'relation + * phone' for the latter. Under the hood, all phones remain equal, of course. + * + * There is a small inefficiency in that the cache repeatedly allocates and + * deallocated the rel_node_t structures when in fact it could keep the + * allocated structures around and reuse them later. But such a solution would + * be effectively implementing a poor man's slab allocator while it would be + * better to have the slab allocator ported to uspace so that everyone could + * benefit from it. + */ + +#include +#include +#include +#include +#include +#include +#include +#include + +#define KEY_NODE_HASH_BUCKETS 16 + +typedef struct { + link_t link; /**< Key node hash table link. */ + int key_phone; /**< The phone serving as a key. */ + link_t rel_head; /**< List of open relation phones. */ +} key_node_t; + +typedef struct { + link_t rel_link; /**< Link for the list of relation phones. */ + link_t global_link; /**< Link for the global list of phones. */ + int rel_phone; /**< Connected relation phone. */ +} rel_node_t; + +/** + * Mutex protecting the global_rel_head list and the key_node_hash hash table. + */ +static fibril_mutex_t async_rel_mutex; + +/** + * List of all currently unused relation phones. + */ +static LIST_INITIALIZE(global_rel_head); + +/** + * Hash table containing lists of available relation phones for all key + * phones. + */ +static hash_table_t key_node_hash; + +static hash_index_t kn_hash(unsigned long *key) +{ + return *key % KEY_NODE_HASH_BUCKETS; +} + +static int kn_compare(unsigned long *key, hash_count_t keys, link_t *item) +{ + key_node_t *knp = hash_table_get_instance(item, key_node_t, link); + + return *key == (unsigned long) knp->key_phone; +} + +static void kn_remove_callback(link_t *item) +{ +} + +static hash_table_operations_t key_node_hash_ops = { + .hash = kn_hash, + .compare = kn_compare, + .remove_callback = kn_remove_callback +}; + +/** Initialize the async_rel subsystem. + * + * Needs to be called prior to any other interface in this file. + */ +int async_rel_init(void) +{ + fibril_mutex_initialize(&async_rel_mutex); + list_initialize(&global_rel_head); + return hash_table_create(&key_node_hash, KEY_NODE_HASH_BUCKETS, 1, + &key_node_hash_ops); +} + +static void key_node_initialize(key_node_t *knp) +{ + link_initialize(&knp->link); + knp->key_phone = -1; + list_initialize(&knp->rel_head); +} + +static void rel_node_initialize(rel_node_t *rnp) +{ + link_initialize(&rnp->rel_link); + link_initialize(&rnp->global_link); + rnp->rel_phone = -1; +} + +/** Create a new relation for a connection represented by a key phone. + * + * @param key_phone Phone representing the connection. + * @return Phone representing the new relation or a negative error + * code. + */ +int async_relation_create(int key_phone) +{ + unsigned long key = (unsigned long) key_phone; + link_t *lnk; + key_node_t *knp; + rel_node_t *rnp; + int rel_phone; + + fibril_mutex_lock(&async_rel_mutex); + lnk = hash_table_find(&key_node_hash, &key); + if (!lnk) { + /* + * The key node was not found in the hash table. Try to allocate + * and hash in a new one. + */ + knp = (key_node_t *) malloc(sizeof(key_node_t)); + if (!knp) { + /* + * As a possible improvement, we could make a one-time + * attempt to create a phone without trying to add the + * key node into the hash. + */ + fibril_mutex_unlock(&async_rel_mutex); + return ENOMEM; + } + key_node_initialize(knp); + knp->key_phone = key_phone; + hash_table_insert(&key_node_hash, &key, &knp->link); + } else { + /* + * Found the key node. + */ + knp = hash_table_get_instance(lnk, key_node_t, link); + } + + if (!list_empty(&knp->rel_head)) { + /* + * There are available relation phones for the key phone. + */ + rnp = list_get_instance(knp->rel_head.next, rel_node_t, + rel_link); + list_remove(&rnp->rel_link); + list_remove(&rnp->global_link); + + rel_phone = rnp->rel_phone; + free(rnp); + } else { + /* + * There are no available relation phones for the key phone. + * Make a one-time attempt to connect a new relation phone. + */ +retry: + rel_phone = ipc_connect_me_to(key_phone, 0, 0, 0); + if (rel_phone >= 0) { + /* success, do nothing */ + } else if (!list_empty(&global_rel_head)) { + /* + * We did not manage to connect a new phone. But we can + * try to hangup some currently unused phones and try + * again. + */ + rnp = list_get_instance(global_rel_head.next, + rel_node_t, global_link); + list_remove(&rnp->global_link); + list_remove(&rnp->rel_link); + rel_phone = rnp->rel_phone; + free(rnp); + ipc_hangup(rel_phone); + goto retry; + } else { + /* + * This is unfortunate. We failed both to find a cached + * phone or to create a new one even after cleaning up + * the cache. This is most likely due to too many key + * phones being kept connected. + */ + rel_phone = ELIMIT; + } + } + + fibril_mutex_unlock(&async_rel_mutex); + return rel_phone; +} + +/** Destroy a relation. + * + * @param key_phone Phone representing the connection. + * @param rel_phone Phone representing the relation within the connection. + */ +void async_relation_destroy(int key_phone, int rel_phone) +{ + unsigned long key = (unsigned long) key_phone; + key_node_t *knp; + rel_node_t *rnp; + link_t *lnk; + + fibril_mutex_lock(&async_rel_mutex); + lnk = hash_table_find(&key_node_hash, &key); + assert(lnk); + knp = hash_table_get_instance(lnk, key_node_t, link); + rnp = (rel_node_t *) malloc(sizeof(rel_node_t)); + if (!rnp) { + /* + * Being unable to remember the connected relation phone here + * means that we simply hangup. + */ + fibril_mutex_unlock(&async_rel_mutex); + ipc_hangup(rel_phone); + return; + } + rel_node_initialize(rnp); + rnp->rel_phone = rel_phone; + list_append(&rnp->rel_link, &knp->rel_head); + list_append(&rnp->global_link, &global_rel_head); + fibril_mutex_unlock(&async_rel_mutex); +} + +/** @} + */ Index: uspace/lib/c/include/async_rel.h =================================================================== --- uspace/lib/c/include/async_rel.h (revision ddd7118f67777e66551eaa92810ca73e704b82c5) +++ uspace/lib/c/include/async_rel.h (revision ddd7118f67777e66551eaa92810ca73e704b82c5) @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2010 Jakub Jermar + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** @addtogroup libc + * @{ + */ +/** @file + */ + +#ifndef LIBC_ASYNC_REL_H_ +#define LIBC_ASYNC_REL_H_ + +extern int async_rel_init(void); +extern int async_relation_create(int); +extern void async_relation_destroy(int, int); + +#endif + +/** @} + */