/branches/rcu/kernel/test/avltree/avltree1.def |
---|
File deleted |
/branches/rcu/kernel/test/avltree/avltree1.c |
---|
File deleted |
/branches/rcu/kernel/test/extavlreltree/extavlreltree1.c |
---|
File deleted |
/branches/rcu/kernel/test/extavlreltree/extavlreltree1.def |
---|
File deleted |
/branches/rcu/kernel/test/extavltree/extavltree1.def |
---|
File deleted |
/branches/rcu/kernel/test/extavltree/extavltree1.c |
---|
File deleted |
/branches/rcu/kernel/test/test.c |
---|
59,9 → 59,6 |
#include <sysinfo/sysinfo1.def> |
#include <tasklet/tasklet1.def> |
#include <synch/rcu1.def> |
#include <avltree/avltree1.def> |
#include <extavltree/extavltree1.def> |
#include <extavlreltree/extavlreltree1.def> |
{NULL, NULL, NULL} |
}; |
/branches/rcu/kernel/test/test.h |
---|
71,9 → 71,6 |
extern char * test_sysinfo1(bool quiet); |
extern char * test_tasklet1(bool quiet); |
extern char * test_rcu1(bool quiet); |
extern char * test_avltree1(bool quiet); |
extern char * test_extavltree1(bool quiet); |
extern char * test_extavlreltree1(bool quiet); |
extern test_t tests[]; |
/branches/rcu/kernel/generic/include/time/timeout.h |
---|
36,44 → 36,20 |
#define KERN_TIMEOUT_H_ |
#include <arch/types.h> |
#if defined CONFIG_TIMEOUT_AVL_TREE |
#include <adt/avl.h> |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#include <adt/extavl.h> |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
#include <adt/extavlrel.h> |
#else |
#endif |
#include <adt/list.h> |
#endif |
#include <cpu.h> |
typedef void (* timeout_handler_t)(void *arg); |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#if defined CONFIG_TIMEOUT_AVL_TREE |
typedef struct { |
SPINLOCK_DECLARE(lock); |
/** |
* AVL tree node structure holds information |
* about connections with other timeouts. |
*/ |
avltree_node_t node; |
/** Function that will be called on timeout activation. */ |
timeout_handler_t handler; |
/** Argument to be passed to handler() function. */ |
void *arg; |
/** On which processor is this timeout registered. */ |
cpu_t *cpu; |
} timeout_t; |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
typedef struct { |
SPINLOCK_DECLARE(lock); |
/** |
* Extended AVL tree node structure holds information |
* about connections with other timeouts. |
*/ |
86,24 → 62,6 |
cpu_t *cpu; |
} timeout_t; |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
typedef struct { |
SPINLOCK_DECLARE(lock); |
/** |
* Extended AVL tree with relative keys node structure holds information |
* about connections with other timeouts. |
*/ |
extavlreltree_node_t node; |
/** Function that will be called on timeout activation. */ |
timeout_handler_t handler; |
/** Argument to be passed to handler() function. */ |
void *arg; |
/** On which processor is this timeout registered. */ |
cpu_t *cpu; |
} timeout_t; |
#else |
typedef struct { |
/branches/rcu/kernel/generic/include/cpu.h |
---|
64,15 → 64,9 |
volatile count_t needs_relink; |
SPINLOCK_DECLARE(timeoutlock); |
#if defined CONFIG_TIMEOUT_AVL_TREE |
/** AVL tree structure. */ |
avltree_t timeout_active_tree; |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Extended AVL tree structure. */ |
extavltree_t timeout_active_tree; |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
/** Extended AVL tree structure with relative keys. */ |
extavlreltree_t timeout_active_tree; |
#else |
/** Head of list of timeouts. */ |
link_t timeout_active_head; |
/branches/rcu/kernel/generic/include/adt/extavlrel.h |
---|
File deleted |
/branches/rcu/kernel/generic/include/adt/extavl.h |
---|
File deleted |
/branches/rcu/kernel/generic/include/adt/avl.h |
---|
File deleted |
/branches/rcu/kernel/generic/src/time/timeout.c |
---|
55,12 → 55,8 |
{ |
spinlock_initialize(&CPU->timeoutlock, "timeout_lock"); |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_create(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_create(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavlreltree_create(&CPU->timeout_active_tree); |
#else |
list_initialize(&CPU->timeout_active_head); |
#endif |
79,13 → 75,9 |
t->cpu = NULL; |
t->handler = NULL; |
t->arg = NULL; |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_node_initialize(&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_node_initialize(&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_node_initialize(&t->node); |
#else |
t->ticks = 0; |
link_initialize(&t->link); |
106,14 → 98,11 |
timeout_reinitialize(t); |
} |
#if defined CONFIG_TIMEOUT_AVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Register timeout |
* |
* Insert timeout handler f (with argument arg) |
* to timeout ExtAVL tree and make it execute in |
* to timeout list and make it execute in |
* time microseconds (or slightly more). |
* |
* @param t Timeout structure. |
135,21 → 124,14 |
panic("t->cpu != 0"); |
t->cpu = CPU; |
//tiky nejsou, musim zmenit klice primo v uzlech |
t->handler = f; |
t->arg = arg; |
t->node.key = us2ticks(time); |
/* |
* Put timeout into tree structure. |
*/ |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_insert(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_insert(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_insert(&CPU->timeout_active_tree,&t->node); |
#endif |
spinlock_unlock(&t->lock); |
spinlock_unlock(&CPU->timeoutlock); |
interrupts_restore(ipl); |
158,7 → 140,7 |
/** Unregister timeout |
* |
* Remove timeout from timeout ExtAVL tree structure. |
* Remove timeout from timeout list. |
* |
* @param t Timeout to unregister. |
* |
181,22 → 163,14 |
interrupts_restore(ipl); |
goto grab_locks; |
} |
/* |
* Now we know for sure that t hasn't been activated yet |
* and is lurking in t->cpu->timeout_active_head queue. |
*/ |
/* |
* Delete timeout from tree structure. |
*/ |
#if defined CONFIG_TIMEOUT_AVL_TREE |
avltree_delete(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_delete(&CPU->timeout_active_tree,&t->node); |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
extavlreltree_delete(&CPU->timeout_active_tree,&t->node); |
#endif |
spinlock_unlock(&t->cpu->timeoutlock); |
timeout_reinitialize(t); |
/branches/rcu/kernel/generic/src/time/clock.c |
---|
123,8 → 123,7 |
} |
} |
#if defined CONFIG_TIMEOUT_AVL_TREE || \ |
defined CONFIG_TIMEOUT_EXTAVL_TREE |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Clock routine |
* |
139,14 → 138,12 |
timeout_handler_t f; |
void *arg; |
count_t missed_clock_ticks = CPU->missed_clock_ticks; |
uint64_t *i = &(CPU->timeout_active_tree.base); |
uint64_t absolute_clock_ticks = *i + missed_clock_ticks; |
#if defined CONFIG TIMEOUT_AVL_TREE |
avltree_node_t *expnode; |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_node_t *expnode; |
#endif |
uint64_t *i = &(CPU->timeout_active_tree.basetime); |
uint64_t absolute_clock_ticks = *i + |
missed_clock_ticks; |
extavltree_node_t *head = &(CPU->timeout_active_tree.head); |
extavltree_node_t *expnode = head->next; |
/* |
* To avoid lock ordering problems, |
* run all expired timeouts as you visit them. |
153,18 → 150,10 |
*/ |
for (; *i <= absolute_clock_ticks; (*i)++) { |
/* |
* Basetime is encreased by missed clock ticks + 1 !! |
*/ |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
/* |
* Check whether first timeout in list time out. If so perform callback function and try |
* next timeout (more timeouts can have same timeout). |
*/ |
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) { |
while ((expnode = head->next) != head) { |
h = extavltree_get_instance(expnode,timeout_t,node); |
spinlock_lock(&h->lock); |
if (expnode->key != *i) { |
172,15 → 161,7 |
break; |
} |
/* |
* Delete first node in the list and repair tree structure in |
* constant time. |
*/ |
#if defined CONFIG TIMEOUT_AVL_TREE |
avltree_delete_min(&CPU->timeout_active_tree); |
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_delete_min(&CPU->timeout_active_tree); |
#endif |
f = h->handler; |
arg = h->arg; |
222,93 → 203,7 |
} |
} |
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE |
/** Clock routine |
* |
* Clock routine executed from clock interrupt handler |
* (assuming interrupts_disable()'d). Runs expired timeouts |
* and preemptive scheduling. |
* |
*/ |
void clock(void) |
{ |
extavltree_node_t *expnode; |
timeout_t *h; |
timeout_handler_t f; |
void *arg; |
count_t missed_clock_ticks = CPU->missed_clock_ticks; |
int i; |
/* |
* To avoid lock ordering problems, |
* run all expired timeouts as you visit them. |
*/ |
for (i = 0; i <= missed_clock_ticks; i++) { |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
/* |
* Check whether first timeout in list time out. If so perform callback function and try |
* next timeout (more timeouts can have same timeout). |
*/ |
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) { |
h = list_get_instance(l, timeout_t, link); |
spinlock_lock(&h->lock); |
if (expnode->key != 0) { |
expnode->key--; |
spinlock_unlock(&h->lock); |
break; |
} |
/* |
* Delete first node in the list and repair tree structure in |
* constant time. Be careful of expnode's key, it must be 0! |
*/ |
extavltree_delete_min(&CPU->timeout_active_tree); |
f = h->handler; |
arg = h->arg; |
timeout_reinitialize(h); |
spinlock_unlock(&h->lock); |
spinlock_unlock(&CPU->timeoutlock); |
f(arg); |
spinlock_lock(&CPU->timeoutlock); |
} |
spinlock_unlock(&CPU->timeoutlock); |
} |
CPU->missed_clock_ticks = 0; |
/* |
* Do CPU usage accounting and find out whether to preempt THREAD. |
*/ |
if (THREAD) { |
uint64_t ticks; |
spinlock_lock(&CPU->lock); |
CPU->needs_relink += 1 + missed_clock_ticks; |
spinlock_unlock(&CPU->lock); |
spinlock_lock(&THREAD->lock); |
if ((ticks = THREAD->ticks)) { |
if (ticks >= 1 + missed_clock_ticks) |
THREAD->ticks -= 1 + missed_clock_ticks; |
else |
THREAD->ticks = 0; |
} |
spinlock_unlock(&THREAD->lock); |
if (!ticks && !PREEMPTION_DISABLED) { |
scheduler(); |
} |
} |
} |
#else |
381,6 → 276,7 |
scheduler(); |
} |
} |
} |
#endif |
/branches/rcu/kernel/generic/src/adt/avl.c |
---|
File deleted |
/branches/rcu/kernel/generic/src/adt/extavlrel.c |
---|
File deleted |
/branches/rcu/kernel/generic/src/adt/extavl.c |
---|
File deleted |
/branches/rcu/kernel/kernel.config |
---|
137,6 → 137,5 |
# Timeout data structure |
@ "doubly-linked-list" Doubly linked list |
@ "avl-tree" Avl tree |
@ "ext-avl-tree" Extended Avl tree |
@ "extrel-avl-tree" Extended Avl tree with relative keys |
@ "extended-avl-tree" Extended Avl tree |
! CONFIG_TIMEOUT_DATA_STRUCTURE (choice) |
/branches/rcu/kernel/Makefile |
---|
59,14 → 59,10 |
DEFS += -DCONFIG_TIMEOUT_AVL_TREE |
endif |
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),ext-avl-tree) |
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),extended-avl-tree) |
DEFS += -DCONFIG_TIMEOUT_EXTAVL_TREE |
endif |
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),extrel-avl-tree) |
DEFS += -DCONFIG_TIMEOUT_EXTAVLREL_TREE |
endif |
ifeq ($(CONFIG_DEBUG),y) |
DEFS += -DCONFIG_DEBUG |
endif |
154,9 → 150,7 |
generic/src/adt/btree.c \ |
generic/src/adt/hash_table.c \ |
generic/src/adt/list.c \ |
generic/src/adt/avl.c \ |
generic/src/adt/extavl.c \ |
generic/src/adt/extavlrel.c \ |
generic/src/console/chardev.c \ |
generic/src/console/console.c \ |
generic/src/console/kconsole.c \ |
254,8 → 248,7 |
test/print/print1.c \ |
test/tasklet/tasklet1.c \ |
test/thread/thread1.c \ |
test/sysinfo/sysinfo1.c \ |
test/extavltree/extavltree1.c |
test/sysinfo/sysinfo1.c |
endif |
## Experimental features |
/branches/rcu/uspace/tester/Makefile |
---|
53,7 → 53,6 |
ipc/answer.c \ |
ipc/hangup.c |
OBJECTS := $(addsuffix .o,$(basename $(SOURCES))) |
.PHONY: all clean depend disasm |