Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2335 → Rev 2336

/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();
186,8 → 279,7
}
if (!spinlock_trylock(&t->cpu->timeoutlock)) {
spinlock_unlock(&t->lock);
interrupts_restore(ipl);
DEADLOCK_PROBE(p_tolock, DEADLOCK_THRESHOLD);
interrupts_restore(ipl);
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,36 → 53,46
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)
UARCH = mips32
IMAGE = ecoff
endif
ifeq ($(MACHINE),bgxemul)
UARCH = mips32eb
IMAGE = ecoff
endif
ifeq ($(MACHINE),lgxemul)
UARCH = mips32
IMAGE = ecoff
endif
ifeq ($(MACHINE),indy)
UARCH = mips32eb
IMAGE = ecoff
endif
IMAGE = binary
endif
 
ifeq ($(PLATFORM),mips32sim)
KARCH = mips32
MACHINE = simics
UARCH = mips32
BARCH = mips32
IMAGE = ecoff
endif
 
ifeq ($(PLATFORM),mips32gbe)
KARCH = mips32
MACHINE = bgxemul
UARCH = mips32eb
BARCH = mips32
IMAGE = ecoff
endif
 
ifeq ($(PLATFORM),mips32gle)
KARCH = mips32
MACHINE = lgxemul
UARCH = mips32
BARCH = mips32
IMAGE = ecoff
endif
 
ifeq ($(PLATFORM),mips32sgi)
KARCH = mips32
MACHINE = indy
UARCH = mips32eb
BARCH = mips32
IMAGE = ecoff
endif
 
ifeq ($(PLATFORM),ppc32)
KARCH = ppc32
UARCH = ppc32