Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2420 → Rev 2421

/branches/rcu/kernel/generic/include/cpu.h
40,11 → 40,14
#include <proc/scheduler.h>
#include <arch/cpu.h>
#include <arch/context.h>
#ifdef CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
#include <adt/extavlrel.h>
#endif
 
 
#define CPU_STACK_SIZE STACK_SIZE
 
/** CPU structure.
/branches/rcu/kernel/generic/include/adt/avl.h
120,10 → 120,11
node->balance = 0;
}
 
avltree_node_t *avltree_find_min(avltree_t *t);
avltree_node_t *avltree_search(avltree_t *t, uint64_t key);
void avltree_insert(avltree_t *t, avltree_node_t *newnode);
void avltree_delete(avltree_t *t, avltree_node_t *node);
avltree_node_t *avltree_delete_min(avltree_t *t);
bool avltree_delete_min(avltree_t *t);
 
#endif
 
/branches/rcu/kernel/generic/include/adt/extavlrel.h
1,5 → 1,5
/*
* Copyright (C) 2006 Vojtech Mencl
* Copyright (C) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
94,7 → 94,6
};
 
/** Relative key Extended AVL tree structure (ExtAvlrel). */
#ifdef AVLTREE_TEST
struct extavlreltree
{
/*
114,7 → 113,7
*
* @param t Extended AVL tree structure.
*/
void extavlreltree_create (extavlreltree_t *t)
static inline void extavlreltree_create (extavlreltree_t *t)
{
t->root = NULL;
 
126,7 → 125,7
*
* @param node Node which is initialized.
*/
void extavlreltree_node_initialize(extavlreltree_node_t *node)
static inline void extavlreltree_node_initialize(extavlreltree_node_t *node)
{
node->lft = NULL;
node->rgt = NULL;
/branches/rcu/kernel/generic/src/time/timeout.c
59,7 → 59,7
avltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
extavlreltree_create(&CPU->timeout_active_tree);
#else
list_initialize(&CPU->timeout_active_head);
/branches/rcu/kernel/generic/src/time/clock.c
123,8 → 123,7
}
}
 
#if defined CONFIG_TIMEOUT_AVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVL_TREE
#if defined CONFIG_TIMEOUT_AVL_TREE
 
/** Clock routine
*
141,11 → 140,98
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;
 
/*
* To avoid lock ordering problems,
* run all expired timeouts as you visit them.
*/
 
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 (with the smallest key in the tree) time out. If so perform
* callback function and try next timeout (more timeouts can have same timeout).
*/
while ((expnode = avltree_find_min(&CPU->timeout_active_tree)) != NULL) {
h = avltree_get_instance(expnode,timeout_t,node);
spinlock_lock(&h->lock);
if (expnode->key != *i) {
spinlock_unlock(&h->lock);
break;
}
/*
* Delete minimal key from the tree and repair tree structure in
* logarithmic time.
*/
avltree_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();
}
}
}
 
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
 
/** Clock routine
*
* Clock routine executed from clock interrupt handler
* (assuming interrupts_disable()'d). Runs expired timeouts
* and preemptive scheduling.
*
*/
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.base);
uint64_t absolute_clock_ticks = *i + missed_clock_ticks;
extavltree_node_t *expnode;
#endif
 
/*
* To avoid lock ordering problems,
176,11 → 262,7
* 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;
233,7 → 315,7
*/
void clock(void)
{
extavltree_node_t *expnode;
extavlreltree_node_t *expnode;
timeout_t *h;
timeout_handler_t f;
void *arg;
253,7 → 335,7
* 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);
h = extavlreltree_get_instance(expnode,timeout_t,node);
spinlock_lock(&h->lock);
if (expnode->key != 0) {
expnode->key--;
265,7 → 347,7
* 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);
extavlreltree_delete_min(&CPU->timeout_active_tree);
f = h->handler;
arg = h->arg;
/branches/rcu/kernel/generic/src/adt/avl.c
1,5 → 1,5
/*
* Copyright (c) 2006 Vojtech Mencl
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
61,7 → 61,7
* @param t AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
avltree_node_t *avltree_search(avltree_t *t, uint64_t key)
{
84,6 → 84,30
}
 
 
/** Find node with smallest key in AVL tree.
*
* @param t AVL tree.
*
* @return Pointer to node or NULL if there is no node in the tree.
*/
avltree_node_t *avltree_find_min(avltree_t *t)
{
avltree_node_t *p = t->root;
/*
* Check whether tree is empty.
*/
if (!p) return NULL;
/*
* Iteratively descend to the leftmost leaf in the tree.
*/
while (p->lft != NULL)
p = p->lft;
return p;
}
 
/** Insert new node into AVL tree.
*
* @param t AVL tree.
114,7 → 138,7
dpc = &t->root;
gpa = NULL;
top = t->root;
while (par = *dpc) {
while ((par = (*dpc)) != NULL) {
if (par->balance != 0) {
top = par;
}
670,7 → 694,7
*
* @param t AVL tree structure.
*/
avltree_node_t *avltree_delete_min(avltree_t *t)
bool avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
uint64_t key;
/branches/rcu/kernel/generic/src/adt/extavl.c
63,7 → 63,7
* @param t Extended AVL tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
extavltree_node_t *extavltree_search(extavltree_t *t, uint64_t key)
{
/branches/rcu/kernel/generic/src/adt/extavlrel.c
60,7 → 60,7
 
 
/* Returns height of tree -1 */
#define extavlreltree_tree_height(node) ((node) == NULL) ? (-1) : max(((node)->lft_height),((node)->rgt_height))
#define extavlreltree_tree_height(node) (((node) == NULL) ? (-1) : (((node)->lft_height>(node)->rgt_height)?(node)->lft_height:(node)->rgt_height))
 
/** Search first occurence (oldest node with this real key) of given key in ExtAVLrel tree.
*
67,9 → 67,9
* @param t ExtAVLrel tree.
* @param key Key to be searched.
*
* @return Pointer to value or NULL if there is no such key.
* @return Pointer to node or NULL if there is no such key.
*/
extavlreltree_node_t *extavlreltree_search(extavlreltree_t t, uint64_t key)
extavlreltree_node_t *extavlreltree_search(extavlreltree_t *t, uint64_t key)
{
extavlreltree_node_t *cur;
uint64_t sum, s;
492,7 → 492,7
extavlreltree_node_t *gpa;
int8_t dir;
int8_t dir2=0;
uint64_t key;
uint64_t key=0;
int16_t balance;
/*
* Condition var - if true then all rgt_sums in the way down to root must be repaired in condition
700,7 → 700,7
if (gpa->par->lft == gpa) {
gpapar = &(gpa->par->lft);
dir2 = AVLTREE_LEFT;
repair_rgt_sum = falsi;
repair_rgt_sum = false;
} else {
gpapar = &(gpa->par->rgt);
dir2 = AVLTREE_RIGHT;