Changeset ef1eab7 in mainline for kernel/generic/src/proc/thread.c

Timestamp:

2018-11-03T21:36:39Z (6 years ago)

Author:

Jiri Svoboda <jiri@…>

Branches:

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

Children:

aab5e46

Parents:

ad2cf04

Message:

Replace AVL trees in kernel with ordered dictionary.

File:

• kernel/generic/src/proc/thread.c (modified) (19 diffs)

kernel/generic/src/proc/thread.c

@@ -1 +1 @@
 /*
  * Copyright (c) 2010 Jakub Jermar
+ * Copyright (c) 2018 Jiri Svoboda
  * All rights reserved.
  *
@@ -52 +53 @@
 #include <str.h>
 #include <context.h>
-#include <adt/avl.h>
 #include <adt/list.h>
+#include <adt/odict.h>
 #include <time/clock.h>
 #include <time/timeout.h>
@@ -80 +81 @@
 };
 
-typedef struct {
-        thread_id_t thread_id;
-        thread_t *thread;
-} thread_iterator_t;
-
-/** Lock protecting the threads_tree AVL tree.
+/** Lock protecting the @c threads ordered dictionary .
  *
  * For locking rules, see declaration thereof.
- *
  */
 IRQ_SPINLOCK_INITIALIZE(threads_lock);
 
-/** AVL 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.
- *
- */
-avltree_t threads_tree;
+/** Ordered dictionary of all threads by their address (i.e. pointer to
+ * the thread_t structure).
+ *
+ * When a thread is found in the @c threads ordered dictionary, it is
+ * guaranteed to exist as long as the @c threads_lock is held.
+ *
+ * Members are of type thread_t.
+ */
+odict_t threads;
 
 IRQ_SPINLOCK_STATIC_INITIALIZE(tidlock);
@@ -108 +105 @@
 slab_cache_t *fpu_context_cache;
 #endif
+
+static void *threads_getkey(odlink_t *);
+static int threads_cmp(void *, void *);
 
 /** Thread wrapper.
@@ -252 +252 @@
 #endif
 
-        avltree_create(&threads_tree);
+        odict_initialize(&threads, threads_getkey, threads_cmp);
 }
 
@@ -404 +404 @@
         thread->fpu_context_engaged = false;
 
-        avltree_node_initialize(&thread->threads_tree_node);
-        thread->threads_tree_node.key = (uintptr_t) thread;
+        odlink_initialize(&thread->lthreads);
 
 #ifdef CONFIG_UDEBUG
@@ -447 +446 @@
         irq_spinlock_pass(&thread->lock, &threads_lock);
 
-        avltree_delete(&threads_tree, &thread->threads_tree_node);
+        odict_remove(&thread->lthreads);
 
         irq_spinlock_pass(&threads_lock, &thread->task->lock);
@@ -492 +491 @@
 
         /*
-         * Register this thread in the system-wide list.
-         */
-        avltree_insert(&threads_tree, &thread->threads_tree_node);
+         * Register this thread in the system-wide dictionary.
+         */
+        odict_insert(&thread->lthreads, &threads, NULL);
         irq_spinlock_unlock(&threads_lock, true);
 }
@@ -710 +709 @@
 }
 
-static bool thread_walker(avltree_node_t *node, void *arg)
-{
-        bool *additional = (bool *) arg;
-        thread_t *thread = avltree_get_instance(node, thread_t, threads_tree_node);
-
+static void thread_print(thread_t *thread, bool additional)
+{
         uint64_t ucycles, kcycles;
         char usuffix, ksuffix;
@@ -727 +723 @@
 
 #ifdef __32_BITS__
-        if (*additional)
+        if (additional)
                 printf("%-8" PRIu64 " %10p %10p %9" PRIu64 "%c %9" PRIu64 "%c ",
                     thread->tid, thread->thread_code, thread->kstack,
@@ -738 +734 @@
 
 #ifdef __64_BITS__
-        if (*additional)
+        if (additional)
                 printf("%-8" PRIu64 " %18p %18p\n"
                     "         %9" PRIu64 "%c %9" PRIu64 "%c ",
@@ -749 +745 @@
 #endif
 
-        if (*additional) {
+        if (additional) {
                 if (thread->cpu)
                         printf("%-5u", thread->cpu->id);
@@ -767 +763 @@
                 printf("\n");
         }
-
-        return true;
 }
 
@@ -778 +772 @@
 void thread_print_list(bool additional)
 {
+        odlink_t *odlink;
+        thread_t *thread;
+
         /* Messing with thread structures, avoid deadlock */
         irq_spinlock_lock(&threads_lock, true);
@@ -799 +796 @@
 #endif
 
-        avltree_walk(&threads_tree, thread_walker, &additional);
+        odlink = odict_first(&threads);
+        while (odlink != NULL) {
+                thread = odict_get_instance(odlink, thread_t, lthreads);
+                thread_print(thread, additional);
+                odlink = odict_next(odlink, &threads);
+        }
 
         irq_spinlock_unlock(&threads_lock, true);
@@ -819 +821 @@
         assert(irq_spinlock_locked(&threads_lock));
 
-        avltree_node_t *node =
-            avltree_search(&threads_tree, (avltree_key_t) ((uintptr_t) thread));
-
-        return node != NULL;
+        odlink_t *odlink = odict_find_eq(&threads, thread, NULL);
+        return odlink != NULL;
 }
 
@@ -848 +848 @@
 }
 
-static bool thread_search_walker(avltree_node_t *node, void *arg)
-{
-        thread_t *thread =
-            (thread_t *) avltree_get_instance(node, thread_t, threads_tree_node);
-        thread_iterator_t *iterator = (thread_iterator_t *) arg;
-
-        if (thread->tid == iterator->thread_id) {
-                iterator->thread = thread;
-                return false;
-        }
-
-        return true;
-}
-
 /** Find thread structure corresponding to thread ID.
  *
@@ -874 +860 @@
 thread_t *thread_find_by_id(thread_id_t thread_id)
 {
+        odlink_t *odlink;
+        thread_t *thread;
+
         assert(interrupts_disabled());
         assert(irq_spinlock_locked(&threads_lock));
 
-        thread_iterator_t iterator;
-
-        iterator.thread_id = thread_id;
-        iterator.thread = NULL;
-
-        avltree_walk(&threads_tree, thread_search_walker, (void *) &iterator);
-
-        return iterator.thread;
+        odlink = odict_first(&threads);
+        while (odlink != NULL) {
+                thread = odict_get_instance(odlink, thread_t, lthreads);
+                if (thread->tid == thread_id)
+                        return thread;
+
+                odlink = odict_next(odlink, &threads);
+        }
+
+        return NULL;
 }
 
@@ -933 +924 @@
 
 #endif /* CONFIG_UDEBUG */
+
+/** Get key function for the @c threads ordered dictionary.
+ *
+ * @param odlink Link
+ * @return Pointer to thread structure cast as 'void *'
+ */
+static void *threads_getkey(odlink_t *odlink)
+{
+        thread_t *thread = odict_get_instance(odlink, thread_t, lthreads);
+        return (void *) thread;
+}
+
+/** Key comparison function for the @c threads ordered dictionary.
+ *
+ * @param a Pointer to thread A
+ * @param b Pointer to thread B
+ * @return -1, 0, 1 iff pointer to A is less than, equal to, greater than B
+ */
+static int threads_cmp(void *a, void *b)
+{
+        if (a > b)
+                return -1;
+        else if (a == b)
+                return 0;
+        else
+                return +1;
+}
 
 /** Process syscall to create new thread.