Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2416 → Rev 2415

/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