/branches/rcu/kernel/kernel.config |
---|
133,3 → 133,9 |
# Enable experimental features |
! CONFIG_EXPERIMENTAL (n/y) |
# Timeout data structure |
@ "doubly-linked-list" Doubly linked list |
@ "avl-tree" Avl tree |
@ "extended-avl-tree" Extended Avl tree |
! CONFIG_TIMEOUT_DATA_STRUCTURE (choice) |
/branches/rcu/kernel/generic/include/time/timeout.h |
---|
36,14 → 36,37 |
#define KERN_TIMEOUT_H_ |
#include <arch/types.h> |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#include <adt/extavl.h> |
#endif |
#include <adt/list.h> |
#include <cpu.h> |
typedef void (* timeout_handler_t)(void *arg); |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
typedef struct { |
SPINLOCK_DECLARE(lock); |
/** |
* Extended AVL tree node structure holds information |
* about connections with other timeouts. |
*/ |
extavltree_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 { |
SPINLOCK_DECLARE(lock); |
/** Link to the list of active timeouts on THE->cpu */ |
link_t link; |
/** Timeout will be activated in this amount of clock() ticks. */ |
56,6 → 79,8 |
cpu_t *cpu; |
} timeout_t; |
#endif |
#define us2ticks(us) ((uint64_t) (((uint32_t) (us) / (1000000 / HZ)))) |
extern void timeout_init(void); |
/branches/rcu/kernel/generic/include/cpu.h |
---|
1,5 → 1,5 |
/* |
* Copyright (c) 2001-2004 Jakub Jermar |
* Copyright (C) 2001-2004 Jakub Jermar |
* All rights reserved. |
* |
* Redistribution and use in source and binary forms, with or without |
40,7 → 40,11 |
#include <proc/scheduler.h> |
#include <arch/cpu.h> |
#include <arch/context.h> |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
#include <adt/extavl.h> |
#endif |
#define CPU_STACK_SIZE STACK_SIZE |
/** CPU structure. |
47,7 → 51,7 |
* |
* There is one structure like this for every processor. |
*/ |
typedef struct { |
typedef struct cpu { |
SPINLOCK_DECLARE(lock); |
tlb_shootdown_msg_t tlb_messages[TLB_MESSAGE_QUEUE_LEN]; |
60,7 → 64,13 |
volatile count_t needs_relink; |
SPINLOCK_DECLARE(timeoutlock); |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Extended AVL tree structure. */ |
extavltree_t timeout_active_tree; |
#else |
/** Head of list of timeouts. */ |
link_t timeout_active_head; |
#endif |
count_t missed_clock_ticks; /**< When system clock loses a tick, it is recorded here |
so that clock() can react. This variable is |
/branches/rcu/kernel/generic/src/time/timeout.c |
---|
1,5 → 1,5 |
/* |
* Copyright (c) 2001-2004 Jakub Jermar |
* Copyright (C) 2001-2004 Jakub Jermar |
* All rights reserved. |
* |
* Redistribution and use in source and binary forms, with or without |
45,6 → 45,7 |
#include <arch/asm.h> |
#include <arch.h> |
/** Initialize timeouts |
* |
* Initialize kernel timeouts. |
53,7 → 54,12 |
void timeout_init(void) |
{ |
spinlock_initialize(&CPU->timeoutlock, "timeout_lock"); |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_create(&CPU->timeout_active_tree); |
#else |
list_initialize(&CPU->timeout_active_head); |
#endif |
} |
67,10 → 73,15 |
void timeout_reinitialize(timeout_t *t) |
{ |
t->cpu = NULL; |
t->ticks = 0; |
t->handler = NULL; |
t->arg = NULL; |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
extavltree_node_initialize(&t->node); |
#else |
t->ticks = 0; |
link_initialize(&t->link); |
#endif |
} |
87,7 → 98,90 |
timeout_reinitialize(t); |
} |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Register timeout |
* |
* Insert timeout handler f (with argument arg) |
* to timeout list and make it execute in |
* time microseconds (or slightly more). |
* |
* @param t Timeout structure. |
* @param time Number of usec in the future to execute |
* the handler. |
* @param f Timeout handler function. |
* @param arg Timeout handler argument. |
* |
*/ |
void timeout_register(timeout_t *t, uint64_t time, timeout_handler_t f, void *arg) |
{ |
ipl_t ipl; |
ipl = interrupts_disable(); |
spinlock_lock(&CPU->timeoutlock); |
spinlock_lock(&t->lock); |
if (t->cpu) |
panic("t->cpu != 0"); |
t->cpu = CPU; |
//tiky nejsou, musim zmenit klice primo v uzlech |
t->handler = f; |
t->arg = arg; |
extavltree_insert(&CPU->timeout_active_tree,&t->node); |
spinlock_unlock(&t->lock); |
spinlock_unlock(&CPU->timeoutlock); |
interrupts_restore(ipl); |
} |
/** Unregister timeout |
* |
* Remove timeout from timeout list. |
* |
* @param t Timeout to unregister. |
* |
* @return true on success, false on failure. |
*/ |
bool timeout_unregister(timeout_t *t) |
{ |
ipl_t ipl; |
grab_locks: |
ipl = interrupts_disable(); |
spinlock_lock(&t->lock); |
if (!t->cpu) { |
spinlock_unlock(&t->lock); |
interrupts_restore(ipl); |
return false; |
} |
if (!spinlock_trylock(&t->cpu->timeoutlock)) { |
spinlock_unlock(&t->lock); |
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. |
*/ |
extavltree_delete(&CPU->timeout_active_tree,&t->node); |
spinlock_unlock(&t->cpu->timeoutlock); |
timeout_reinitialize(t); |
spinlock_unlock(&t->lock); |
interrupts_restore(ipl); |
return true; |
} |
#else |
/** Register timeout |
* |
* Insert timeout handler f (with argument arg) |
174,7 → 268,6 |
timeout_t *hlp; |
link_t *l; |
ipl_t ipl; |
DEADLOCK_PROBE_INIT(p_tolock); |
grab_locks: |
ipl = interrupts_disable(); |
187,7 → 280,6 |
if (!spinlock_trylock(&t->cpu->timeoutlock)) { |
spinlock_unlock(&t->lock); |
interrupts_restore(ipl); |
DEADLOCK_PROBE(p_tolock, DEADLOCK_THRESHOLD); |
goto grab_locks; |
} |
214,5 → 306,6 |
return true; |
} |
#endif |
/** @} |
*/ |
/branches/rcu/kernel/generic/src/time/clock.c |
---|
1,5 → 1,5 |
/* |
* Copyright (c) 2001-2004 Jakub Jermar |
* Copyright (C) 2001-2004 Jakub Jermar |
* All rights reserved. |
* |
* Redistribution and use in source and binary forms, with or without |
123,6 → 123,8 |
} |
} |
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE |
/** Clock routine |
* |
* Clock routine executed from clock interrupt handler |
132,6 → 134,88 |
*/ |
void clock(void) |
{ |
timeout_t *h; |
timeout_handler_t f; |
void *arg; |
count_t missed_clock_ticks = CPU->missed_clock_ticks; |
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. |
*/ |
for (; *i <= absolute_clock_ticks; (*i)++) { |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
while ((expnode = head->next) != head) { |
h = extavltree_get_instance(expnode,timeout_t,node); |
spinlock_lock(&h->lock); |
if (expnode->key != *i) { |
spinlock_unlock(&h->lock); |
break; |
} |
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 |
/** Clock routine |
* |
* Clock routine executed from clock interrupt handler |
* (assuming interrupts_disable()'d). Runs expired timeouts |
* and preemptive scheduling. |
* |
*/ |
void clock(void) |
{ |
link_t *l; |
timeout_t *h; |
timeout_handler_t f; |
195,5 → 279,6 |
} |
#endif |
/** @} |
*/ |
/branches/rcu/kernel/Makefile |
---|
55,6 → 55,14 |
-include arch/$(ARCH)/Makefile.inc |
-include genarch/Makefile.inc |
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),avl-tree) |
DEFS += -DCONFIG_TIMEOUT_AVL_TREE |
endif |
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),extended-avl-tree) |
DEFS += -DCONFIG_TIMEOUT_EXTAVL_TREE |
endif |
ifeq ($(CONFIG_DEBUG),y) |
DEFS += -DCONFIG_DEBUG |
endif |
142,6 → 150,7 |
generic/src/adt/btree.c \ |
generic/src/adt/hash_table.c \ |
generic/src/adt/list.c \ |
generic/src/adt/extavl.c \ |
generic/src/console/chardev.c \ |
generic/src/console/console.c \ |
generic/src/console/kconsole.c \ |
/branches/rcu/Makefile |
---|
1,5 → 1,5 |
# |
# Copyright (c) 2006 Martin Decky |
# Copyright (C) 2006 Martin Decky |
# All rights reserved. |
# |
# Redistribution and use in source and binary forms, with or without |
41,12 → 41,6 |
BARCH = amd64 |
endif |
ifeq ($(PLATFORM),arm32) |
KARCH = arm32 |
UARCH = arm32 |
BARCH = arm32 |
endif |
ifeq ($(PLATFORM),ia32) |
KARCH = ia32 |
UARCH = ia32 |
59,35 → 53,45 |
BARCH = ia64 |
endif |
ifeq ($(PLATFORM),mips32) |
ifeq ($(PLATFORM),mips32msim) |
KARCH = mips32 |
MACHINE = msim |
UARCH = mips32 |
BARCH = mips32 |
ifeq ($(MACHINE),msim) |
UARCH = mips32 |
IMAGE = binary |
endif |
ifeq ($(MACHINE),simics) |
ifeq ($(PLATFORM),mips32sim) |
KARCH = mips32 |
MACHINE = simics |
UARCH = mips32 |
BARCH = mips32 |
IMAGE = ecoff |
endif |
ifeq ($(MACHINE),bgxemul) |
ifeq ($(PLATFORM),mips32gbe) |
KARCH = mips32 |
MACHINE = bgxemul |
UARCH = mips32eb |
BARCH = mips32 |
IMAGE = ecoff |
endif |
ifeq ($(MACHINE),lgxemul) |
ifeq ($(PLATFORM),mips32gle) |
KARCH = mips32 |
MACHINE = lgxemul |
UARCH = mips32 |
BARCH = mips32 |
IMAGE = ecoff |
endif |
ifeq ($(MACHINE),indy) |
ifeq ($(PLATFORM),mips32sgi) |
KARCH = mips32 |
MACHINE = indy |
UARCH = mips32eb |
BARCH = mips32 |
IMAGE = ecoff |
endif |
endif |
ifeq ($(PLATFORM),ppc32) |
KARCH = ppc32 |