Changeset 5dcee525 in mainline

Timestamp:

2007-07-29T13:50:20Z (17 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

83a5cba

Parents:

d1e9321

Message:

Replace the threads_btree B+tree with an AVL tree. The new variable is called
threads_tree. For printing list of threads, use the new AVL tree walker
mechanism.

This solves half of ticket #48.

Location:

kernel/generic

Files:

• include/proc/thread.h (modified) (4 diffs)
• src/proc/thread.c (modified) (11 diffs)

kernel/generic/include/proc/thread.h

@@ -42 +42 @@
 #include <synch/rwlock.h>
 #include <synch/spinlock.h>
-#include <adt/btree.h>
+#include <adt/avl.h>
 #include <mm/slab.h>
 #include <arch/cpu.h>
@@ -91 +91 @@
         link_t wq_link;         /**< Wait queue link. */
         link_t th_link;         /**< Links to threads within containing task. */
+
+        /** Threads linkage to the threads_tree. */
+        avltree_node_t threads_tree_node;
         
         /** Lock protecting thread structure.
@@ -205 +208 @@
 /** Thread list lock.
  *
- * This lock protects all link_t structures chained in threads_head.
+ * This lock protects the threads_tree.
  * Must be acquired before T.lock for each T of type thread_t.
  *
@@ -211 +214 @@
 SPINLOCK_EXTERN(threads_lock);
 
-/** B+tree containing all threads. */
-extern btree_t threads_btree;
+/** AVL tree containing all threads. */
+extern avltree_t threads_tree;
 
 extern void thread_init(void);

kernel/generic/src/proc/thread.c

@@ -52 +52 @@
 #include <func.h>
 #include <context.h>
-#include <adt/btree.h>
+#include <adt/avl.h>
 #include <adt/list.h>
 #include <time/clock.h>
@@ -82 +82 @@
 }; 
 
-/** Lock protecting the threads_btree B+tree.
+/** Lock protecting the threads_tree AVL tree.
  *
  * For locking rules, see declaration thereof.
@@ -88 +88 @@
 SPINLOCK_INITIALIZE(threads_lock);
 
-/** B+tree of all threads.
- *
- * When a thread is found in the threads_btree B+tree, it is guaranteed to
+/** ALV tree of all threads.
+ *
+ * When a thread is found in the threads_tree AVL tree, it is guaranteed to
  * exist as long as the threads_lock is held.
  */
-btree_t threads_btree;          
+avltree_t threads_tree;         
 
 SPINLOCK_INITIALIZE(tidlock);
@@ -213 +213 @@
 #endif
 
-        btree_create(&threads_btree);
+        avltree_create(&threads_tree);
 }
 
@@ -340 +340 @@
         t->fpu_context_engaged = 0;
 
+        avltree_node_initialize(&t->threads_tree_node);
+        t->threads_tree_node.key = (uintptr_t) t;
+
         /* might depend on previous initialization */
         thread_create_arch(t);  
@@ -369 +372 @@
 
         spinlock_lock(&threads_lock);
-        btree_remove(&threads_btree, (btree_key_t) ((uintptr_t ) t), NULL);
+        avltree_delete(&threads_tree, &t->threads_tree_node);
         spinlock_unlock(&threads_lock);
 
@@ -392 +395 @@
  *
  * Attach the thread structure to the current task and make it visible in the
- * threads_btree.
+ * threads_tree.
  *
  * @param t     Thread to be attached to the task.
@@ -415 +418 @@
          */
         spinlock_lock(&threads_lock);
-        btree_insert(&threads_btree, (btree_key_t) ((uintptr_t) t), (void *) t,
-            NULL);
+        avltree_insert(&threads_tree, &t->threads_tree_node);
         spinlock_unlock(&threads_lock);
         
@@ -576 +578 @@
 }
 
+static void thread_walker(avltree_node_t *node)
+{
+        thread_t *t;
+                
+        t = avltree_get_instance(node, thread_t, threads_tree_node);
+
+        uint64_t cycles;
+        char suffix;
+        order(t->cycles, &cycles, &suffix);
+                        
+        printf("%-6llu %-10s %#10zx %-8s %#10zx %-3ld %#10zx %#10zx %9llu%c ",
+            t->tid, t->name, t, thread_states[t->state], t->task,
+            t->task->context, t->thread_code, t->kstack, cycles, suffix);
+                        
+        if (t->cpu)
+                printf("%-4zd", t->cpu->id);
+        else
+                printf("none");
+                        
+        if (t->state == Sleeping)
+                printf(" %#10zx", t->sleep_queue);
+                        
+        printf("\n");
+}
+
 /** Print list of threads debug info */
 void thread_print_list(void)
 {
-        link_t *cur;
         ipl_t ipl;
         
@@ -591 +617 @@
             "-- ---------- ---------- ---- ---------\n");
 
-        for (cur = threads_btree.leaf_head.next;
-            cur != &threads_btree.leaf_head; cur = cur->next) {
-                btree_node_t *node;
-                unsigned 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];
-                        
-                        uint64_t cycles;
-                        char suffix;
-                        order(t->cycles, &cycles, &suffix);
-                        
-                        printf("%-6llu %-10s %#10zx %-8s %#10zx %-3ld %#10zx "
-                            "%#10zx %9llu%c ", t->tid, t->name, t,
-                            thread_states[t->state], t->task, t->task->context,
-                            t->thread_code, t->kstack, cycles, suffix);
-                        
-                        if (t->cpu)
-                                printf("%-4zd", t->cpu->id);
-                        else
-                                printf("none");
-                        
-                        if (t->state == Sleeping)
-                                printf(" %#10zx", t->sleep_queue);
-                        
-                        printf("\n");
-                }
-        }
+        avltree_walk(&threads_tree, thread_walker);
 
         spinlock_unlock(&threads_lock);
@@ -638 +634 @@
 bool thread_exists(thread_t *t)
 {
-        btree_node_t *leaf;
-        
-        return btree_search(&threads_btree, (btree_key_t) ((uintptr_t) t),
-            &leaf) != NULL;
+        avltree_node_t *node;
+
+        node = avltree_search(&threads_tree, (avltree_key_t) ((uintptr_t) t));
+        
+        return node != NULL;
 }