Changeset b76a2217 in mainline for kernel/generic/src/proc/task.c

Timestamp:

2007-07-29T19:17:25Z (17 years ago)

Author:

Jakub Jermar <jakub@…>

Branches:

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

Children:

7fe9c5b

Parents:

83a5cba

Message:

Give the AVL tree walkers the possibility to take an argument.
Each walker is now supposed to return a bool value to support walk termination.

Switch over from the tasks_btree B+tree to tasks_tree AVL tree.
This makes the fix for ticket #48 complete.

File:

• kernel/generic/src/proc/task.c (modified) (10 diffs)

kernel/generic/src/proc/task.c

@@ -47 +47 @@
 #include <arch.h>
 #include <panic.h>
+#include <adt/avl.h>
 #include <adt/btree.h>
 #include <adt/list.h>
@@ -62 +63 @@
 #endif
 
-/** Spinlock protecting the tasks_btree B+tree. */
+/** Spinlock protecting the tasks_tree AVL tree. */
 SPINLOCK_INITIALIZE(tasks_lock);
 
-/** B+tree of active tasks.
- *
- * The task is guaranteed to exist after it was found in the tasks_btree as
+/** AVL tree of active tasks.
+ *
+ * The task is guaranteed to exist after it was found in the tasks_tree as
  * long as:
  * @li the tasks_lock is held,
@@ -75 +76 @@
  *
  */
-btree_t tasks_btree;
+avltree_t tasks_tree;
 
 static task_id_t task_counter = 0;
@@ -87 +88 @@
 {
         TASK = NULL;
-        btree_create(&tasks_btree);
+        avltree_create(&tasks_tree);
+}
+
+/*
+ * The idea behind this walker is to remember a single task different from TASK.
+ */
+static bool task_done_walker(avltree_node_t *node, void *arg)
+{
+        task_t *t = avltree_get_instance(node, task_t, tasks_tree_node);
+        task_t **tp = (task_t **) arg;
+
+        if (t != TASK) { 
+                *tp = t;
+                return false;   /* stop walking */
+        }
+
+        return true;    /* continue the walk */
 }
 
@@ -103 +120 @@
                 
                 t = NULL;
-                link_t *cur;
-                for (cur = tasks_btree.leaf_head.next;
-                    cur != &tasks_btree.leaf_head; cur = cur->next) {
-                        btree_node_t *node;
-                        
-                        node = list_get_instance(cur, btree_node_t, leaf_link);
-                        
-                        unsigned int i;
-                        for (i = 0; i < node->keys; i++) {
-                                if ((task_t *) node->value[i] != TASK) {
-                                        t = (task_t *) node->value[i];
-                                        break;
-                                }
-                        }
-                }
+                avltree_walk(&tasks_tree, task_done_walker, &t);
                 
                 if (t != NULL) {
@@ -188 +191 @@
         spinlock_lock(&tasks_lock);
         ta->taskid = ++task_counter;
-        btree_insert(&tasks_btree, (btree_key_t) ta->taskid, (void *) ta, NULL);
+        avltree_node_initialize(&ta->tasks_tree_node);
+        ta->tasks_tree_node.key = ta->taskid; 
+        avltree_insert(&tasks_tree, &ta->tasks_tree_node);
         spinlock_unlock(&tasks_lock);
         interrupts_restore(ipl);
@@ -205 +210 @@
          */
         spinlock_lock(&tasks_lock);
-        btree_remove(&tasks_btree, t->taskid, NULL);
+        avltree_delete(&tasks_tree, &t->tasks_tree_node);
         spinlock_unlock(&tasks_lock);
 
@@ -311 +316 @@
 task_t *task_find_by_id(task_id_t id)
 {
-        btree_node_t *leaf;
-        
-        return (task_t *) btree_search(&tasks_btree, (btree_key_t) id, &leaf);
+        avltree_node_t *node;
+        
+        node = avltree_search(&tasks_tree, (avltree_key_t) id);
+
+        if (node)
+                return avltree_get_instance(node, task_t, tasks_tree_node); 
+        return NULL;
 }
 
@@ -401 +410 @@
 }
 
+static bool task_print_walker(avltree_node_t *node, void *arg)
+{
+        task_t *t = avltree_get_instance(node, task_t, tasks_tree_node);
+        int j;
+                
+        spinlock_lock(&t->lock);
+                        
+        uint64_t cycles;
+        char suffix;
+        order(task_get_accounting(t), &cycles, &suffix);
+                        
+        printf("%-6llu %-10s %-3ld %#10zx %#10zx %9llu%c %7zd %6zd",
+            t->taskid, t->name, t->context, t, t->as, cycles, suffix,
+            t->refcount, atomic_get(&t->active_calls));
+        for (j = 0; j < IPC_MAX_PHONES; j++) {
+                if (t->phones[j].callee)
+                        printf(" %zd:%#zx", j, t->phones[j].callee);
+        }
+        printf("\n");
+                        
+        spinlock_unlock(&t->lock);
+        return true;
+}
+
 /** Print task list */
 void task_print_list(void)
 {
-        link_t *cur;
         ipl_t ipl;
         
@@ -416 +448 @@
             "------ ------>\n");
 
-        for (cur = tasks_btree.leaf_head.next; cur != &tasks_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++) {
-                        task_t *t;
-                        int j;
-
-                        t = (task_t *) node->value[i];
-                
-                        spinlock_lock(&t->lock);
-                        
-                        uint64_t cycles;
-                        char suffix;
-                        order(task_get_accounting(t), &cycles, &suffix);
-                        
-                        printf("%-6llu %-10s %-3ld %#10zx %#10zx %9llu%c %7zd "
-                            "%6zd", t->taskid, t->name, t->context, t, t->as,
-                            cycles, suffix, t->refcount,
-                            atomic_get(&t->active_calls));
-                        for (j = 0; j < IPC_MAX_PHONES; j++) {
-                                if (t->phones[j].callee)
-                                        printf(" %zd:%#zx", j,
-                                            t->phones[j].callee);
-                        }
-                        printf("\n");
-                        
-                        spinlock_unlock(&t->lock);
-                }
-        }
+        avltree_walk(&tasks_tree, task_print_walker, NULL);
 
         spinlock_unlock(&tasks_lock);