/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; |