Changeset ef1eab7 in mainline


Ignore:
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.

Location:
kernel
Files:
4 deleted
7 edited

Legend:

Unmodified
Added
Removed

  • kernel/Makefile

    rad2cf04 ref1eab7  
    161161
    162162GENERIC_SOURCES = \
    163         generic/src/adt/avl.c \
    164163        generic/src/adt/bitmap.c \
    165164        generic/src/adt/btree.c \
    … …  
    286285                test/btree/btree1.c \
    287286                test/cht/cht1.c \
    288                 test/avltree/avltree1.c \
    289287                test/fault/fault1.c \
    290288                test/mm/falloc1.c \

  • kernel/generic/include/proc/task.h

    rad2cf04 ref1eab7  
    4444#include <synch/futex.h>
    4545#include <synch/workqueue.h>
    46 #include <adt/avl.h>
    4746#include <adt/btree.h>
    4847#include <adt/cht.h>
    4948#include <adt/list.h>
     49#include <adt/odict.h>
    5050#include <security/perm.h>
    5151#include <arch/proc/task.h>
    … …  
    7070/** Task structure. */
    7171typedef struct task {
    72         /** Task's linkage for the tasks_tree AVL tree. */
    73         avltree_node_t tasks_tree_node;
     72        /** Link to @c tasks ordered dictionary */
     73        odlink_t ltasks;
    7474
    7575        /** Task lock.
    … …  
    146146} task_t;
    147147
     148/** Synchronize access to @c tasks */
    148149IRQ_SPINLOCK_EXTERN(tasks_lock);
    149 extern avltree_t tasks_tree;
     150/** Ordered dictionary of all tasks by ID (of task_t structures) */
     151extern odict_t tasks;
    150152
    151153extern void task_init(void);

  • kernel/generic/include/proc/thread.h

    rad2cf04 ref1eab7  
    4242#include <synch/spinlock.h>
    4343#include <synch/rcu_types.h>
    44 #include <adt/avl.h>
     44#include <adt/odict.h>
    4545#include <mm/slab.h>
    4646#include <arch/cpu.h>
    … …  
    7575        link_t th_link;  /**< Links to threads within containing task. */
    7676
    77         /** Threads linkage to the threads_tree. */
    78         avltree_node_t threads_tree_node;
     77        /** Link to @c threads ordered dictionary. */
     78        odlink_t lthreads;
    7979
    8080        /** Lock protecting thread structure.
    … …  
    224224} thread_t;
    225225
    226 /** Thread list lock.
    227  *
    228  * This lock protects the threads_tree.
    229  * Must be acquired before T.lock for each T of type thread_t.
    230  *
    231  */
    232226IRQ_SPINLOCK_EXTERN(threads_lock);
    233 
    234 /** AVL tree containing all threads. */
    235 extern avltree_t threads_tree;
     227extern odict_t threads;
    236228
    237229extern void thread_init(void);

  • kernel/generic/src/proc/task.c

    rad2cf04 ref1eab7  
    11/*
    22 * Copyright (c) 2010 Jakub Jermar
     3 * Copyright (c) 2018 Jiri Svoboda
    34 * All rights reserved.
    45 *
    … …  
    4748#include <arch.h>
    4849#include <barrier.h>
    49 #include <adt/avl.h>
    5050#include <adt/btree.h>
    5151#include <adt/list.h>
     52#include <adt/odict.h>
    5253#include <cap/cap.h>
    5354#include <ipc/ipc.h>
    … …  
    6162#include <macros.h>
    6263
    63 /** Spinlock protecting the tasks_tree AVL tree. */
     64/** Spinlock protecting the @c tasks ordered dictionary. */
    6465IRQ_SPINLOCK_INITIALIZE(tasks_lock);
    6566
    66 /** AVL tree of active tasks.
    67  *
    68  * The task is guaranteed to exist after it was found in the tasks_tree as
    69  * long as:
     67/** Ordered dictionary of active tasks.
     68 *
     69 * The task is guaranteed to exist after it was found in the @c tasks
     70 * dictionary as long as:
    7071 *
    7172 * @li the tasks_lock is held,
    … …  
    7576 *
    7677 */
    77 avltree_t tasks_tree;
     78odict_t tasks;
    7879
    7980static task_id_t task_counter = 0;
    … …  
    8485static void task_kill_internal(task_t *);
    8586static errno_t tsk_constructor(void *, unsigned int);
    86 static size_t tsk_destructor(void *obj);
     87static size_t tsk_destructor(void *);
     88
     89static void *tasks_getkey(odlink_t *);
     90static int tasks_cmp(void *, void *);
    8791
    8892/** Initialize kernel tasks support.
    … …  
    9296{
    9397        TASK = NULL;
    94         avltree_create(&tasks_tree);
     98        odict_initialize(&tasks, tasks_getkey, tasks_cmp);
    9599        task_cache = slab_cache_create("task_t", sizeof(task_t), 0,
    96100            tsk_constructor, tsk_destructor, 0);
    97101}
    98102
    99 /** Task finish walker.
    100  *
    101  * The idea behind this walker is to kill and count all tasks different from
    102  * TASK.
    103  *
    104  */
    105 static bool task_done_walker(avltree_node_t *node, void *arg)
    106 {
    107         task_t *task = avltree_get_instance(node, task_t, tasks_tree_node);
    108         size_t *cnt = (size_t *) arg;
    109 
    110         if (task != TASK) {
    111                 (*cnt)++;
    112 
    113 #ifdef CONFIG_DEBUG
    114                 printf("[%" PRIu64 "] ", task->taskid);
    115 #endif
    116 
    117                 task_kill_internal(task);
    118         }
    119 
    120         /* Continue the walk */
    121         return true;
    122 }
    123 
    124103/** Kill all tasks except the current task.
    125104 *
    … …  
    128107{
    129108        size_t tasks_left;
     109        odlink_t *odlink;
     110        task_t *task;
    130111
    131112        if (ipc_box_0) {
    … …  
    144125                printf("Killing tasks... ");
    145126#endif
    146 
    147127                irq_spinlock_lock(&tasks_lock, true);
    148128                tasks_left = 0;
    149                 avltree_walk(&tasks_tree, task_done_walker, &tasks_left);
     129
     130                odlink = odict_first(&tasks);
     131                while (odlink != NULL) {
     132                        task = odict_get_instance(odlink, task_t, ltasks);
     133
     134                        if (task != TASK) {
     135                                tasks_left++;
     136#ifdef CONFIG_DEBUG
     137                                printf("[%" PRIu64 "] ", task->taskid);
     138#endif
     139                                task_kill_internal(task);
     140                        }
     141
     142                        odlink = odict_next(odlink, &tasks);
     143                }
     144
    150145                irq_spinlock_unlock(&tasks_lock, true);
    151146
    … …  
    269264
    270265        task->taskid = ++task_counter;
    271         avltree_node_initialize(&task->tasks_tree_node);
    272         task->tasks_tree_node.key = task->taskid;
    273         avltree_insert(&tasks_tree, &task->tasks_tree_node);
     266        odlink_initialize(&task->ltasks);
     267        odict_insert(&task->ltasks, &tasks, NULL);
    274268
    275269        irq_spinlock_unlock(&tasks_lock, true);
    … …  
    289283         */
    290284        irq_spinlock_lock(&tasks_lock, true);
    291         avltree_delete(&tasks_tree, &task->tasks_tree_node);
     285        odict_remove(&task->ltasks);
    292286        irq_spinlock_unlock(&tasks_lock, true);
    293287
    … …  
    451445        assert(irq_spinlock_locked(&tasks_lock));
    452446
    453         avltree_node_t *node =
    454             avltree_search(&tasks_tree, (avltree_key_t) id);
    455 
    456         if (node)
    457                 return avltree_get_instance(node, task_t, tasks_tree_node);
     447        odlink_t *odlink = odict_find_eq(&tasks, &id, NULL);
     448        if (odlink != NULL)
     449                return odict_get_instance(odlink, task_t, ltasks);
    458450
    459451        return NULL;
    … …  
    604596}
    605597
    606 static bool task_print_walker(avltree_node_t *node, void *arg)
    607 {
    608         bool *additional = (bool *) arg;
    609         task_t *task = avltree_get_instance(node, task_t, tasks_tree_node);
     598static void task_print(task_t *task, bool additional)
     599{
    610600        irq_spinlock_lock(&task->lock, false);
    611601
    … …  
    618608
    619609#ifdef __32_BITS__
    620         if (*additional)
     610        if (additional)
    621611                printf("%-8" PRIu64 " %9zu", task->taskid,
    622612                    atomic_load(&task->refcount));
    … …  
    629619
    630620#ifdef __64_BITS__
    631         if (*additional)
     621        if (additional)
    632622                printf("%-8" PRIu64 " %9" PRIu64 "%c %9" PRIu64 "%c "
    633623                    "%9zu\n", task->taskid, ucycles, usuffix, kcycles,
    … …  
    639629
    640630        irq_spinlock_unlock(&task->lock, false);
    641         return true;
    642631}
    643632
    … …  
    669658#endif
    670659
    671         avltree_walk(&tasks_tree, task_print_walker, &additional);
     660        odlink_t *odlink;
     661        task_t *task;
     662
     663        odlink = odict_first(&tasks);
     664        while (odlink != NULL) {
     665                task = odict_get_instance(odlink, task_t, ltasks);
     666                task_print(task, additional);
     667                odlink = odict_next(odlink, &tasks);
     668        }
    672669
    673670        irq_spinlock_unlock(&tasks_lock, true);
    674671}
    675672
     673/** Get key function for the @c tasks ordered dictionary.
     674 *
     675 * @param odlink Link
     676 * @return Pointer to task ID cast as 'void *'
     677 */
     678static void *tasks_getkey(odlink_t *odlink)
     679{
     680        task_t *task = odict_get_instance(odlink, task_t, ltasks);
     681        return (void *) &task->taskid;
     682}
     683
     684/** Key comparison function for the @c tasks ordered dictionary.
     685 *
     686 * @param a Pointer to thread A ID
     687 * @param b Pointer to thread B ID
     688 * @return -1, 0, 1 iff ID A is less than, equal to, greater than B
     689 */
     690static int tasks_cmp(void *a, void *b)
     691{
     692        task_id_t ida = *(task_id_t *)a;
     693        task_id_t idb = *(task_id_t *)b;
     694
     695        if (ida < idb)
     696                return -1;
     697        else if (ida == idb)
     698                return 0;
     699        else
     700                return +1;
     701}
     702
    676703/** @}
    677704 */

  • kernel/generic/src/proc/thread.c

    rad2cf04 ref1eab7  
    11/*
    22 * Copyright (c) 2010 Jakub Jermar
     3 * Copyright (c) 2018 Jiri Svoboda
    34 * All rights reserved.
    45 *
    … …  
    5253#include <str.h>
    5354#include <context.h>
    54 #include <adt/avl.h>
    5555#include <adt/list.h>
     56#include <adt/odict.h>
    5657#include <time/clock.h>
    5758#include <time/timeout.h>
    … …  
    8081};
    8182
    82 typedef struct {
    83         thread_id_t thread_id;
    84         thread_t *thread;
    85 } thread_iterator_t;
    86 
    87 /** Lock protecting the threads_tree AVL tree.
     83/** Lock protecting the @c threads ordered dictionary .
    8884 *
    8985 * For locking rules, see declaration thereof.
    90  *
    9186 */
    9287IRQ_SPINLOCK_INITIALIZE(threads_lock);
    9388
    94 /** AVL tree of all threads.
    95  *
    96  * When a thread is found in the threads_tree AVL tree, it is guaranteed to
    97  * exist as long as the threads_lock is held.
    98  *
    99  */
    100 avltree_t threads_tree;
     89/** Ordered dictionary of all threads by their address (i.e. pointer to
     90 * the thread_t structure).
     91 *
     92 * When a thread is found in the @c threads ordered dictionary, it is
     93 * guaranteed to exist as long as the @c threads_lock is held.
     94 *
     95 * Members are of type thread_t.
     96 */
     97odict_t threads;
    10198
    10299IRQ_SPINLOCK_STATIC_INITIALIZE(tidlock);
    … …  
    108105slab_cache_t *fpu_context_cache;
    109106#endif
     107
     108static void *threads_getkey(odlink_t *);
     109static int threads_cmp(void *, void *);
    110110
    111111/** Thread wrapper.
    … …  
    252252#endif
    253253
    254         avltree_create(&threads_tree);
     254        odict_initialize(&threads, threads_getkey, threads_cmp);
    255255}
    256256
    … …  
    404404        thread->fpu_context_engaged = false;
    405405
    406         avltree_node_initialize(&thread->threads_tree_node);
    407         thread->threads_tree_node.key = (uintptr_t) thread;
     406        odlink_initialize(&thread->lthreads);
    408407
    409408#ifdef CONFIG_UDEBUG
    … …  
    447446        irq_spinlock_pass(&thread->lock, &threads_lock);
    448447
    449         avltree_delete(&threads_tree, &thread->threads_tree_node);
     448        odict_remove(&thread->lthreads);
    450449
    451450        irq_spinlock_pass(&threads_lock, &thread->task->lock);
    … …  
    492491
    493492        /*
    494          * Register this thread in the system-wide list.
    495          */
    496         avltree_insert(&threads_tree, &thread->threads_tree_node);
     493         * Register this thread in the system-wide dictionary.
     494         */
     495        odict_insert(&thread->lthreads, &threads, NULL);
    497496        irq_spinlock_unlock(&threads_lock, true);
    498497}
    … …  
    710709}
    711710
    712 static bool thread_walker(avltree_node_t *node, void *arg)
    713 {
    714         bool *additional = (bool *) arg;
    715         thread_t *thread = avltree_get_instance(node, thread_t, threads_tree_node);
    716 
     711static void thread_print(thread_t *thread, bool additional)
     712{
    717713        uint64_t ucycles, kcycles;
    718714        char usuffix, ksuffix;
    … …  
    727723
    728724#ifdef __32_BITS__
    729         if (*additional)
     725        if (additional)
    730726                printf("%-8" PRIu64 " %10p %10p %9" PRIu64 "%c %9" PRIu64 "%c ",
    731727                    thread->tid, thread->thread_code, thread->kstack,
    … …  
    738734
    739735#ifdef __64_BITS__
    740         if (*additional)
     736        if (additional)
    741737                printf("%-8" PRIu64 " %18p %18p\n"
    742738                    "         %9" PRIu64 "%c %9" PRIu64 "%c ",
    … …  
    749745#endif
    750746
    751         if (*additional) {
     747        if (additional) {
    752748                if (thread->cpu)
    753749                        printf("%-5u", thread->cpu->id);
    … …  
    767763                printf("\n");
    768764        }
    769 
    770         return true;
    771765}
    772766
    … …  
    778772void thread_print_list(bool additional)
    779773{
     774        odlink_t *odlink;
     775        thread_t *thread;
     776
    780777        /* Messing with thread structures, avoid deadlock */
    781778        irq_spinlock_lock(&threads_lock, true);
    … …  
    799796#endif
    800797
    801         avltree_walk(&threads_tree, thread_walker, &additional);
     798        odlink = odict_first(&threads);
     799        while (odlink != NULL) {
     800                thread = odict_get_instance(odlink, thread_t, lthreads);
     801                thread_print(thread, additional);
     802                odlink = odict_next(odlink, &threads);
     803        }
    802804
    803805        irq_spinlock_unlock(&threads_lock, true);
    … …  
    819821        assert(irq_spinlock_locked(&threads_lock));
    820822
    821         avltree_node_t *node =
    822             avltree_search(&threads_tree, (avltree_key_t) ((uintptr_t) thread));
    823 
    824         return node != NULL;
     823        odlink_t *odlink = odict_find_eq(&threads, thread, NULL);
     824        return odlink != NULL;
    825825}
    826826
    … …  
    848848}
    849849
    850 static bool thread_search_walker(avltree_node_t *node, void *arg)
    851 {
    852         thread_t *thread =
    853             (thread_t *) avltree_get_instance(node, thread_t, threads_tree_node);
    854         thread_iterator_t *iterator = (thread_iterator_t *) arg;
    855 
    856         if (thread->tid == iterator->thread_id) {
    857                 iterator->thread = thread;
    858                 return false;
    859         }
    860 
    861         return true;
    862 }
    863 
    864850/** Find thread structure corresponding to thread ID.
    865851 *
    … …  
    874860thread_t *thread_find_by_id(thread_id_t thread_id)
    875861{
     862        odlink_t *odlink;
     863        thread_t *thread;
     864
    876865        assert(interrupts_disabled());
    877866        assert(irq_spinlock_locked(&threads_lock));
    878867
    879         thread_iterator_t iterator;
    880 
    881         iterator.thread_id = thread_id;
    882         iterator.thread = NULL;
    883 
    884         avltree_walk(&threads_tree, thread_search_walker, (void *) &iterator);
    885 
    886         return iterator.thread;
     868        odlink = odict_first(&threads);
     869        while (odlink != NULL) {
     870                thread = odict_get_instance(odlink, thread_t, lthreads);
     871                if (thread->tid == thread_id)
     872                        return thread;
     873
     874                odlink = odict_next(odlink, &threads);
     875        }
     876
     877        return NULL;
    887878}
    888879
    … …  
    933924
    934925#endif /* CONFIG_UDEBUG */
     926
     927/** Get key function for the @c threads ordered dictionary.
     928 *
     929 * @param odlink Link
     930 * @return Pointer to thread structure cast as 'void *'
     931 */
     932static void *threads_getkey(odlink_t *odlink)
     933{
     934        thread_t *thread = odict_get_instance(odlink, thread_t, lthreads);
     935        return (void *) thread;
     936}
     937
     938/** Key comparison function for the @c threads ordered dictionary.
     939 *
     940 * @param a Pointer to thread A
     941 * @param b Pointer to thread B
     942 * @return -1, 0, 1 iff pointer to A is less than, equal to, greater than B
     943 */
     944static int threads_cmp(void *a, void *b)
     945{
     946        if (a > b)
     947                return -1;
     948        else if (a == b)
     949                return 0;
     950        else
     951                return +1;
     952}
    935953
    936954/** Process syscall to create new thread.

  • kernel/generic/src/sysinfo/stats.c

    rad2cf04 ref1eab7  
    22 * Copyright (c) 2010 Stanislav Kozina
    33 * Copyright (c) 2010 Martin Decky
     4 * Copyright (c) 2018 Jiri Svoboda
    45 * All rights reserved.
    56 *
    … …  
    123124}
    124125
    125 /** Count number of nodes in an AVL tree
    126  *
    127  * AVL tree walker for counting nodes.
    128  *
    129  * @param node AVL tree node (unused).
    130  * @param arg  Pointer to the counter (size_t).
    131  *
    132  * @param Always true (continue the walk).
    133  *
    134  */
    135 static bool avl_count_walker(avltree_node_t *node, void *arg)
    136 {
    137         size_t *count = (size_t *) arg;
    138         (*count)++;
    139 
    140         return true;
    141 }
    142 
    143126/** Get the size of a virtual address space
    144127 *
    … …  
    245228}
    246229
    247 /** Gather statistics of all tasks
    248  *
    249  * AVL task tree walker for gathering task statistics. Interrupts should
    250  * be already disabled while walking the tree.
    251  *
    252  * @param node AVL task tree node.
    253  * @param arg  Pointer to the iterator into the array of stats_task_t.
    254  *
    255  * @param Always true (continue the walk).
    256  *
    257  */
    258 static bool task_serialize_walker(avltree_node_t *node, void *arg)
    259 {
    260         stats_task_t **iterator = (stats_task_t **) arg;
    261         task_t *task = avltree_get_instance(node, task_t, tasks_tree_node);
    262 
    263         /* Interrupts are already disabled */
    264         irq_spinlock_lock(&(task->lock), false);
    265 
    266         /* Record the statistics and increment the iterator */
    267         produce_stats_task(task, *iterator);
    268         (*iterator)++;
    269 
    270         irq_spinlock_unlock(&(task->lock), false);
    271 
    272         return true;
    273 }
    274 
    275230/** Get task statistics
    276231 *
    … …  
    290245        irq_spinlock_lock(&tasks_lock, true);
    291246
    292         /* First walk the task tree to count the tasks */
    293         size_t count = 0;
    294         avltree_walk(&tasks_tree, avl_count_walker, (void *) &count);
     247        /* Count the tasks */
     248        size_t count = odict_count(&tasks);
    295249
    296250        if (count == 0) {
    … …  
    315269        }
    316270
    317         /* Walk tha task tree again to gather the statistics */
    318         stats_task_t *iterator = stats_tasks;
    319         avltree_walk(&tasks_tree, task_serialize_walker, (void *) &iterator);
     271        /* Gather the statistics for each task */
     272        size_t i = 0;
     273        odlink_t *odlink = odict_first(&tasks);
     274        while (odlink != NULL) {
     275                task_t *task = odict_get_instance(odlink, task_t, ltasks);
     276
     277                /* Interrupts are already disabled */
     278                irq_spinlock_lock(&(task->lock), false);
     279
     280                /* Record the statistics and increment the index */
     281                produce_stats_task(task, &stats_tasks[i]);
     282                i++;
     283
     284                irq_spinlock_unlock(&(task->lock), false);
     285                odlink = odict_next(odlink, &tasks);
     286        }
    320287
    321288        irq_spinlock_unlock(&tasks_lock, true);
    … …  
    351318}
    352319
    353 /** Gather statistics of all threads
    354  *
    355  * AVL three tree walker for gathering thread statistics. Interrupts should
    356  * be already disabled while walking the tree.
    357  *
    358  * @param node AVL thread tree node.
    359  * @param arg  Pointer to the iterator into the array of thread statistics.
    360  *
    361  * @param Always true (continue the walk).
    362  *
    363  */
    364 static bool thread_serialize_walker(avltree_node_t *node, void *arg)
    365 {
    366         stats_thread_t **iterator = (stats_thread_t **) arg;
    367         thread_t *thread = avltree_get_instance(node, thread_t, threads_tree_node);
    368 
    369         /* Interrupts are already disabled */
    370         irq_spinlock_lock(&thread->lock, false);
    371 
    372         /* Record the statistics and increment the iterator */
    373         produce_stats_thread(thread, *iterator);
    374         (*iterator)++;
    375 
    376         irq_spinlock_unlock(&thread->lock, false);
    377 
    378         return true;
    379 }
    380 
    381320/** Get thread statistics
    382321 *
    … …  
    396335        irq_spinlock_lock(&threads_lock, true);
    397336
    398         /* First walk the thread tree to count the threads */
    399         size_t count = 0;
    400         avltree_walk(&threads_tree, avl_count_walker, (void *) &count);
     337        /* Count the threads */
     338        size_t count = odict_count(&threads);
    401339
    402340        if (count == 0) {
    … …  
    422360
    423361        /* Walk tha thread tree again to gather the statistics */
    424         stats_thread_t *iterator = stats_threads;
    425         avltree_walk(&threads_tree, thread_serialize_walker, (void *) &iterator);
     362        size_t i = 0;
     363
     364        odlink_t *odlink = odict_first(&threads);
     365        while (odlink != NULL) {
     366                thread_t *thread = odict_get_instance(odlink, thread_t,
     367                    lthreads);
     368
     369                /* Interrupts are already disabled */
     370                irq_spinlock_lock(&thread->lock, false);
     371
     372                /* Record the statistics and increment the index */
     373                produce_stats_thread(thread, &stats_threads[i]);
     374                i++;
     375
     376                irq_spinlock_unlock(&thread->lock, false);
     377
     378                odlink = odict_next(odlink, &threads);
     379        }
    426380
    427381        irq_spinlock_unlock(&threads_lock, true);

  • kernel/test/test.c

    rad2cf04 ref1eab7  
    4141test_t tests[] = {
    4242#include <atomic/atomic1.def>
    43 #include <avltree/avltree1.def>
    4443#include <btree/btree1.def>
    4544#include <cht/cht1.def>
Note: See TracChangeset for help on using the changeset viewer.