Changeset 016acbe in mainline

Timestamp:

2006-04-09T14:58:42Z (19 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

7f6e755

Parents:

203f4c3

Message:

Replace list of all threads with B+tree of all threads.
Add function thread_exists() for querying existence of thread.

Location:

generic

Files:

• include/proc/thread.h (modified) (4 diffs)
• src/proc/thread.c (modified) (13 diffs)
• src/synch/waitq.c (modified) (2 diffs)

generic/include/proc/thread.h

@@ -39 +39 @@
 #include <synch/rwlock.h>
 #include <config.h>
+#include <adt/btree.h>
 #include <adt/list.h>
 #include <mm/slab.h>
@@ -66 +67 @@
         link_t wq_link;                         /**< Wait queue link. */
         link_t th_link;                         /**< Links to threads within containing task. */
-        link_t threads_link;                    /**< Link to the list of all threads. */
         
         /** Lock protecting thread structure.
@@ -131 +131 @@
 extern spinlock_t threads_lock;
 
-extern link_t threads_head;                     /**< List of all threads in the system. */
+extern btree_t threads_btree;                   /**< B+tree containing all threads. */
 
 extern void thread_init(void);
@@ -144 +144 @@
 extern void thread_print_list(void);
 extern void thread_destroy(thread_t *t);
+extern bool thread_exists(thread_t *t);
 
 /* Fpu context slab cache */

generic/src/proc/thread.c

@@ -42 +42 @@
 #include <func.h>
 #include <context.h>
+#include <adt/btree.h>
 #include <adt/list.h>
 #include <typedefs.h>
@@ -59 +60 @@
 char *thread_states[] = {"Invalid", "Running", "Sleeping", "Ready", "Entering", "Exiting"}; /**< Thread states */
 
-SPINLOCK_INITIALIZE(threads_lock);      /**< Lock protecting threads_head list. For locking rules, see declaration thereof. */
-LIST_INITIALIZE(threads_head);          /**< List of all threads. */
+/** Lock protecting threads_head list. For locking rules, see declaration thereof. */
+SPINLOCK_INITIALIZE(threads_lock);
+btree_t threads_btree;                  /**< B+tree of all threads. */
 
 SPINLOCK_INITIALIZE(tidlock);
@@ -70 +72 @@
 #endif
 
-
 /** Thread wrapper
  *
@@ -105 +106 @@
         link_initialize(&t->wq_link);
         link_initialize(&t->th_link);
-        link_initialize(&t->threads_link);
         
 #ifdef ARCH_HAS_FPU
@@ -161 +161 @@
                                              NULL, NULL, 0);
 #endif
-}
-
+
+        btree_create(&threads_btree);
+}
 
 /** Make thread ready
@@ -209 +210 @@
 }
 
-
 /** Destroy thread memory structure
  *
@@ -237 +237 @@
         
         spinlock_lock(&threads_lock);
-        list_remove(&t->threads_link);
+        btree_remove(&threads_btree, (__native) t, NULL);
         spinlock_unlock(&threads_lock);
         
         slab_free(thread_slab, t);
 }
-
 
 /** Create new thread
@@ -312 +311 @@
         ipl = interrupts_disable();
         spinlock_lock(&threads_lock);
-        list_append(&t->threads_link, &threads_head);
+        btree_insert(&threads_btree, (__native) t, (void *) t, NULL);
         spinlock_unlock(&threads_lock);
         
@@ -326 +325 @@
         return t;
 }
-
 
 /** Make thread exiting
@@ -364 +362 @@
 }
 
-
 /** Thread usleep
  *
@@ -380 +377 @@
         (void) waitq_sleep_timeout(&wq, usec, SYNCH_NON_BLOCKING);
 }
-
 
 /** Register thread out-of-context invocation
@@ -407 +403 @@
 {
         link_t *cur;
-        thread_t *t;
         ipl_t ipl;
         
@@ -414 +409 @@
         spinlock_lock(&threads_lock);
 
-        for (cur=threads_head.next; cur!=&threads_head; cur=cur->next) {
-                t = list_get_instance(cur, thread_t, threads_link);
-                printf("%s: address=%P, tid=%d, state=%s, task=%P, code=%P, stack=%P, cpu=",
-                        t->name, t, t->tid, thread_states[t->state], t->task, t->thread_code, t->kstack);
-                if (t->cpu)
-                        printf("cpu%d ", t->cpu->id);
-                else
-                        printf("none");
-                printf("\n");
+        for (cur = threads_btree.leaf_head.next; cur != &threads_btree.leaf_head; cur = cur->next) {
+                btree_node_t *node;
+                int i;
+
+                node = list_get_instance(cur, btree_node_t, leaf_link);
+                for (i = 0; i < node->keys; i++) {
+                        thread_t *t;
+                
+                        t = (thread_t *) node->value[i];
+                        printf("%s: address=%P, tid=%d, state=%s, task=%P, code=%P, stack=%P, cpu=",
+                                t->name, t, t->tid, thread_states[t->state], t->task, t->thread_code, t->kstack);
+                        if (t->cpu)
+                                printf("cpu%d ", t->cpu->id);
+                        else
+                                printf("none");
+                        printf("\n");
+                }
         }
 
         spinlock_unlock(&threads_lock);
         interrupts_restore(ipl);
+}
+
+/** Check whether thread exists.
+ *
+ * Note that threads_lock must be already held and
+ * interrupts must be already disabled.
+ *
+ * @param t Pointer to thread.
+ *
+ * @return True if thread t is known to the system, false otherwise.
+ */
+bool thread_exists(thread_t *t)
+{
+        btree_node_t *leaf;
+        
+        return btree_search(&threads_btree, (__native) t, &leaf) != NULL;
 }
 

generic/src/synch/waitq.c

@@ -74 +74 @@
 
         spinlock_lock(&threads_lock);
-        if (!list_member(&t->threads_link, &threads_head))
+        if (!thread_exists(t))
                 goto out;
 
@@ -118 +118 @@
         ipl = interrupts_disable();
         spinlock_lock(&threads_lock);
-        if (!list_member(&t->threads_link, &threads_head))
+        if (!thread_exists(t))
                 goto out;