2004-10-29 Marcus Brinkmann <marcus@gnu.org>

	* Makefile.am (task_SOURCES): Add task-id.c.
	* task.h (task_id_to_task_lock, task_id_to_task): New declarations.
	(task_id_get_task): New static inline function.
	(task_id_enter, task_id_add): New prototypes.
	* task.c (create_bootstrap_caps): Enter the new tasks into the
	hash table with task_id_enter.
	* task-id.c: New file.

6 files changed, 203 insertions, 23 deletions

diff --git a/task/ChangeLog b/task/ChangeLog
index e0c522d..2d2919f 100644
--- a/task/ChangeLog
+++ b/task/ChangeLog
@@ -1,5 +1,13 @@
 2004-10-29  Marcus Brinkmann  <marcus@gnu.org>
 
+	* Makefile.am (task_SOURCES): Add task-id.c.
+	* task.h (task_id_to_task_lock, task_id_to_task): New declarations.
+	(task_id_get_task): New static inline function.
+	(task_id_enter, task_id_add): New prototypes.
+	* task.c (create_bootstrap_caps): Enter the new tasks into the
+	hash table with task_id_enter.
+	* task-id.c: New file.
+
 	* ia32-cmain.c (switch_thread): Correct start of small sub stack
 	address.  Reported by Rian Hunter <hurd@thelaststop.net>.
 
diff --git a/task/Makefile.am b/task/Makefile.am
index 522a391..5d70bcd 100644
--- a/task/Makefile.am
+++ b/task/Makefile.am
@@ -30,7 +30,7 @@ task_CPPFLAGS = -I$(top_builddir)/include			\
 task_SOURCES = $(ARCH_SOURCES)					\
 	output.h output.c					\
 	physmem-user.h physmem-user.c mmap.c malloc-wrap.c	\
-	task.h task.c task-class.c
+	task.h task.c task-class.c task-id.c
 
 # Doug Lea's malloc is included by malloc-wrap.c.
 EXTRA_task_SOURCES = malloc.c
diff --git a/task/task-class.c b/task/task-class.c
index f439468..4fa4420 100644
--- a/task/task-class.c
+++ b/task/task-class.c
@@ -32,27 +32,6 @@
 #include "task.h"
 
 
-struct task
-{
-  /* The capability object must be the first member of this
-     struct.  */
-  struct hurd_cap_obj obj;
-
-  /* The task ID is used in the version field of the global thread ID,
-     so it is limited to L4_THREAD_VERSION_BITS (14/32) bits and must
-     not have its lower 6 bits set to all zero (because that indicates
-     a local thread ID).  */
-  l4_word_t task_id;
-
-  /* FIXME: Just for testing and dummy stuff: A small table of the
-     threads in this task.  */
-#define MAX_THREADS 4
-  l4_thread_id_t threads[MAX_THREADS];
-  unsigned int nr_threads;
-};
-typedef struct task *task_t;
-
-
 static void
 task_reinit (hurd_cap_class_t cap_class, hurd_cap_obj_t obj)
 {
@@ -130,6 +109,7 @@ task_alloc (l4_word_t task_id, unsigned int nr_threads,
   if (err)
     return err;
 
+  task->task_id = task_id;
   assert (nr_threads <= MAX_THREADS);
   task->nr_threads = nr_threads;
   memcpy (task->threads, threads, sizeof (l4_thread_id_t) * nr_threads);
diff --git a/task/task-id.c b/task/task-id.c
new file mode 100644
index 0000000..ec51d05
--- /dev/null
+++ b/task/task-id.c
@@ -0,0 +1,121 @@
+/* task-id.c - Manage task IDs.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+   Written by Marcus Brinkmann.
+
+   This file is part of the GNU Hurd.
+
+   The GNU Hurd is free software; you can redistribute it and/or
+   modify it under the terms of the GNU General Public License as
+   published by the Free Software Foundation; either version 2, or (at
+   your option) any later version.
+
+   The GNU Hurd is distributed in the hope that it will be useful, but
+   WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
+
+#if HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <stddef.h>
+
+#include "task.h"
+
+
+/* The hash table mapping task IDs to tasks.  */
+struct hurd_ihash task_id_to_task
+  = HURD_IHASH_INITIALIZER (offsetof (struct task, locp));
+
+/* The lock protecting the task_it_to_task hash table and associated
+   data.  */
+pthread_mutex_t task_id_to_task_lock = PTHREAD_MUTEX_INITIALIZER;
+
+#define task_id_is_free(task_id) \
+  (hurd_ihash_find (&task_id_to_task, (task_id)) == NULL)
+
+
+/* Enter the task TASK under its ID into the hash table, consuming one
+   reference.  Mainly used by the bootstrap functions.  */
+error_t
+task_id_enter (task_t task)
+{
+  error_t err;
+
+  pthread_mutex_lock (&task_id_to_task_lock);
+  err = hurd_ihash_add (&task_id_to_task, task->task_id, task);  
+  pthread_mutex_unlock (&task_id_to_task_lock);
+
+  return err;
+}
+
+
+/* Increment the task_id_next marker.  */
+static inline hurd_task_id_t
+task_id_inc (hurd_task_id_t task_id)
+{
+  /* We know that either the next task ID or the one after it is
+     valid.  So we manually unroll the loop here.  */
+
+  task_id++;
+  if (! L4_THREAD_VERSION_VALID (task_id))
+    task_id++;
+
+  return task_id;
+}
+
+
+/* Find a free task ID, enter the task TASK into the hash table under
+   this ID, consuming one reference, and return the new task ID.  If
+   no free task ID is available, EAGAIN is returned.  */
+error_t
+task_id_add (task_t task, hurd_task_id_t *task_id_p)
+{
+  /* Zero is an invalid task ID.  But last_task_id will be incremented
+     to the next valid task ID before the first allocation takes
+     place.  This variable is protected by task_id_to_task_lock.  */
+  static hurd_task_id_t last_task_id;
+  error_t err = 0;
+  hurd_task_id_t task_id;
+
+  pthread_mutex_lock (&task_id_to_task_lock);
+
+  /* Find next valid task ID.  */
+  task_id = task_id_inc (last_task_id);
+
+  if (__builtin_expect (! task_id_is_free (task_id), 0))
+    {
+      /* Slow path.  The next task ID is taken.  Skip forward until we
+	 find a free one.  */
+
+      /* The first task ID we tried.  */
+      hurd_task_id_t first_task_id = task_id;
+
+      do
+	task_id = task_id_inc (task_id);
+      while (task_id != first_task_id && !task_id_is_free (task_id));
+
+      /* Check if we wrapped over and ended up where we started.  */
+      if (task_id == first_task_id)
+	err = EAGAIN;
+    }
+
+  if (__builtin_expect (!err, 1))
+    {
+      err = hurd_ihash_add (&task_id_to_task, task_id, task);
+      if (__builtin_expect (!err, 1))
+	{
+	  task->task_id = task_id;
+	  *task_id_p = task_id;
+	  last_task_id = task_id;
+	}
+    }
+
+  pthread_mutex_unlock (&task_id_to_task_lock);
+
+  return err;
+}
diff --git a/task/task.c b/task/task.c
index cefc355..ef1a23a 100644
--- a/task/task.c
+++ b/task/task.c
@@ -99,11 +99,15 @@ create_bootstrap_caps (hurd_cap_bucket_t bucket)
 	  debug ("Creating task cap for 0x%x:", task_id);
 
 	  err = task_alloc (task_id, nr_threads, threads, &obj);
-
 	  if (err)
 	    panic ("task_alloc: %i\n", err);
+
 	  hurd_cap_obj_unlock (obj);
 
+	  err = task_id_enter ((task_t) obj);
+	  if (err)
+	    panic ("task_id_enter: %i\n", err);
+
 	  err = hurd_cap_bucket_inject (bucket, obj, task_id, &cap);
 	  if (err)
 	    panic ("hurd_cap_bucket_inject: %i\n", err);
@@ -204,6 +208,9 @@ task_server (void *arg)
 
   /* No root object is provided by the task server.  */
   /* FIXME: Use a worker timeout.  */
+  /* FIXME: Use a no-sender callback that deletes the resources from a
+     dead task and turns it into a zombie or removes it from the hash
+     table completely.  */
   err = hurd_cap_bucket_manage_mt (bucket, NULL, 0, 0);
   if (err)
     debug ("bucket_manage_mt failed: %i\n", err);
diff --git a/task/task.h b/task/task.h
index 746c192..be3e30a 100644
--- a/task/task.h
+++ b/task/task.h
@@ -18,10 +18,14 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111, USA. */
 
+#ifndef TASK_H
+#define TASK_H	1
+
 #include <errno.h>
 
 #include <l4.h>
 #include <hurd/cap-server.h>
+#include <hurd/ihash.h>
 
 #include "output.h"
 
@@ -44,6 +48,30 @@ void switch_thread (l4_thread_id_t from, l4_thread_id_t to);
 
 /* Task objects.  */
 
+struct task
+{
+  /* The capability object must be the first member of this
+     struct.  */
+  struct hurd_cap_obj obj;
+
+  /* This is for fast removal from the task_id_to_task hash table.  */
+  hurd_ihash_locp_t locp;
+
+  /* The task ID is used in the version field of the global thread ID,
+     so it is limited to L4_THREAD_VERSION_BITS (14/32) bits and must
+     not have its lower 6 bits set to all zero (because that indicates
+     a local thread ID).  */
+  l4_word_t task_id;
+
+  /* FIXME: Just for testing and dummy stuff: A small table of the
+     threads in this task.  */
+#define MAX_THREADS 4
+  l4_thread_id_t threads[MAX_THREADS];
+  unsigned int nr_threads;
+};
+typedef struct task *task_t;
+
+
 /* Initialize the task class subsystem.  */
 error_t task_class_init ();
 
@@ -53,3 +81,39 @@ error_t task_class_init ();
    reference.  */
 error_t task_alloc (l4_word_t task_id, unsigned int nr_threads,
 		    l4_thread_id_t *threads, hurd_cap_obj_t *r_obj);
+
+
+extern pthread_mutex_t task_id_to_task_lock;
+
+/* The hash table mapping task IDs to tasks.  */
+extern struct hurd_ihash task_id_to_task;
+
+/* Acquire a reference for the task with the task ID TASK_ID and
+   return the task object.  If the task ID is not valid, return
+   NULL.  */
+static inline task_t
+task_id_get_task (hurd_task_id_t task_id)
+{
+  task_t task;
+
+  pthread_mutex_lock (&task_id_to_task_lock);
+  task = hurd_ihash_find (&task_id_to_task, task_id);
+  if (task)
+    hurd_cap_obj_ref (&task->obj);
+  pthread_mutex_unlock (&task_id_to_task_lock);
+
+  return task;
+}
+
+
+/* Enter the task TASK under its ID into the hash table, consuming one
+   reference.  Mainly used by the bootstrap functions.  */
+error_t task_id_enter (task_t task);
+
+/* Find a free task ID, enter the task TASK (which must not be locked)
+   into the hash table under this ID, acquiring reference.  The new
+   task ID is returned in TASK_ID.  If no free task ID is available,
+   EAGAIN is returned.  */
+error_t task_id_add (task_t task, hurd_task_id_t *task_id_p);
+
+#endif	/* TASK_H */