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 <async_rel.h>
+#include <ipc/ipc.h>
+#include <fibril_synch.h>
+#include <adt/list.h>
+#include <adt/hash_table.h>
+#include <malloc.h>
+#include <errno.h>
+#include <assert.h>
+
+#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);
+}
+
+/** @}
+ */
