Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2461 → Rev 2460

/branches/rcu/kernel/test/favltree/favltree1.def
File deleted
/branches/rcu/kernel/test/favltree/favltree1.c
File deleted
/branches/rcu/kernel/test/timeout/timeoutbench1.c
29,7 → 29,6
#include <test.h>
#include <print.h>
#include <adt/avl.h>
#include <adt/favl.h>
#include <adt/extavl.h>
#include <adt/extavlrel.h>
#include <debug.h>
53,7 → 52,6
* Wrapper tree data structures.
*/
static avltree_t avltree;
static favltree_t favltree;
static extavltree_t extavltree;
static extavlreltree_t extavlreltree;
 
61,7 → 59,6
* Slab cache variables.
*/
static slab_cache_t *avl_slab;
static slab_cache_t *favl_slab;
static slab_cache_t *extavl_slab;
static slab_cache_t *extavlrel_slab;
 
69,7 → 66,6
* Head of free nodes' list:
*/
static avltree_node_t *avl_ffn = NULL;
static favltree_node_t *favl_ffn = NULL;
static extavltree_node_t *extavl_ffn = NULL;
static extavlreltree_node_t *extavlrel_ffn = NULL;
 
79,9 → 75,8
unsigned int i;
uint16_t s;
avltree_node_t *a = avl_ffn;
favltree_node_t *b = favl_ffn;
extavltree_node_t *c = extavl_ffn;
extavlreltree_node_t *d = extavlrel_ffn;
extavltree_node_t *b = extavl_ffn;
extavlreltree_node_t *c = extavlrel_ffn;
switch (type) {
case 0:
90,12 → 85,10
a->key = s;
b->key = s;
c->key = s;
d->key = s;
s += GEN_NUM;
a = a->par;
b = b->par;
c = c->par;
d = d->par;
}
break;
case 1:
103,11 → 96,9
a->key = i;
b->key = i;
c->key = i;
d->key = i;
a = a->par;
b = b->par;
c = c->par;
d = d->par;
}
break;
case 2:
115,11 → 106,9
a->key = i;
b->key = i;
c->key = i;
d->key = i;
a = a->par;
b = b->par;
c = c->par;
d = d->par;
c = c->par;
}
break;
}
132,10 → 121,8
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
avl_ffn = NULL;
favl_ffn = NULL;
extavl_ffn = NULL;
extavlrel_ffn = NULL;
 
155,19 → 142,12
printf("Not enough memory to allocate test arrays.");
return false;
}
d = (favltree_node_t *) slab_alloc(favl_slab,0);
if (!d) {
printf("Not enough memory to allocate test arrays.");
return false;
}
a->par = avl_ffn;
b->par = extavl_ffn;
c->par = extavlrel_ffn;
d->par = favl_ffn;
avl_ffn = a;
extavl_ffn = b;
extavlrel_ffn = c;
favl_ffn = d;
}
return true;
}
178,26 → 158,21
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
for (i = 0; i < node_count; i++) {
a = avl_ffn;
b = extavl_ffn;
c = extavlrel_ffn;
d = favl_ffn;
if (!a || !b || !c || !d) {
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p, c: %p, d: %p\n",
i,node_count,a,b,c,d);
if (!a || !b || !c) {
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c);
panic("Some nodes have been lost!");
}
avl_ffn = avl_ffn->par;
extavl_ffn = extavl_ffn->par;
extavlrel_ffn = extavlrel_ffn->par;
favl_ffn = favl_ffn->par;
slab_free(avl_slab,a);
slab_free(extavl_slab,b);
slab_free(extavlrel_slab,c);
slab_free(favl_slab,d);
}
}
 
211,16 → 186,6
return node;
}
 
static favltree_node_t *alloc_favltree_node(void)
{
favltree_node_t *node;
 
node = favl_ffn;
favl_ffn = favl_ffn->par;
 
return node;
}
 
static extavltree_node_t *alloc_extavltree_node(void)
{
extavltree_node_t *node;
248,12 → 213,6
avl_ffn = node;
}
 
static void free_favltree_node(favltree_node_t *node)
{
node->par = favl_ffn;
favl_ffn = node;
}
 
static void free_extavltree_node(extavltree_node_t *node)
{
node->par = extavl_ffn;
270,13 → 229,12
*/
static void test1(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
printf("INSERT nodes with keys of ascending sequence.\n");
353,37 → 311,11
}
df[2][ii] = get_cycle();
 
/*
* FAVL INSERT
*/
s[3][ii] = get_cycle();
favltree_create(&favltree);
for (i = 0; i < node_count[ii]; i++) {
favltree_insert(&favltree,alloc_favltree_node());
}
f[3][ii] = get_cycle();
/*
* FAVL DELETE
*/
ds[3][ii] = get_cycle();
while ((d = favltree.root) != NULL) {
favltree_delete(&favltree,d);
free_favltree_node(d);
}
df[3][ii] = get_cycle();
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[3][ii]-s[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
400,9 → 332,6
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[3][ii]-ds[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
417,13 → 346,12
*/
static void test2(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
 
 
printf("INSERT nodes with keys of descending sequence.\n");
502,39 → 430,11
}
df[2][ii] = get_cycle();
 
/*
* FAVL INSERT
*/
s[3][ii] = get_cycle();
favltree_create(&favltree);
for (i = 0; i < node_count[ii]; i++) {
favltree_insert(&favltree,alloc_favltree_node());
}
f[3][ii] = get_cycle();
/*
* AVL DELETE
*/
ds[3][ii] = get_cycle();
while (favltree.root != NULL) {
d = favltree_find_min(&favltree);
favltree_delete_min(&favltree);
free_favltree_node(d);
}
df[3][ii] = get_cycle();
 
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[3][ii]-s[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
551,9 → 451,6
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[3][ii]-ds[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
568,13 → 465,12
*/
static void test3(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
 
printf("INSERT nodes with keys of random sequence 1-65536.\n");
653,38 → 549,11
}
df[2][ii] = get_cycle();
 
/*
* FAVL INSERT
*/
s[3][ii] = get_cycle();
favltree_create(&favltree);
for (i = 0; i < node_count[ii]; i++) {
favltree_insert(&favltree,alloc_favltree_node());
}
f[3][ii] = get_cycle();
/*
* AVL DELETE
*/
ds[3][ii] = get_cycle();
while (favltree.root != NULL) {
d = favltree_find_min(&favltree);
favltree_delete_min(&favltree);
free_favltree_node(d);
}
df[3][ii] = get_cycle();
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[3][ii]-s[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
701,9 → 570,6
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[0][ii]-ds[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[3][ii]-ds[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",df[1][ii]-ds[1][ii]);
718,12 → 584,11
*/
static void test4(void)
{
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
extavltree_node_t *b;
extavlreltree_node_t *c;
favltree_node_t *d;
uint64_t r;
uint16_t rr;
unsigned int mn,nc;
777,45 → 642,6
f[0][ii] = get_cycle();
 
/*
* FAVL
*/
rr = r;
nc = 0;
s[3][ii] = get_cycle();
avltree_create(&avltree);
for (i = 0; i < OPERATION_COUNT; i++) {
if (((rr % mn) <= nc) && nc) {
/*
* Delete min.
*/
d = favltree_find_min(&favltree);
favltree_delete_min(&favltree);
free_favltree_node(d);
nc--;
} else {
/*
* Insert.
*/
d = alloc_favltree_node();
d->key = rr;
favltree_insert(&favltree,d);
nc++;
}
rr += GEN_NUM;
}
/*
* Delete rest tree.
*/
while (favltree.root != NULL) {
d = favltree_find_min(&favltree);
favltree_delete_min(&favltree);
free_favltree_node(d);
}
f[3][ii] = get_cycle();
 
/*
* ExtAVL
*/
rr = r;
899,9 → 725,6
printf("\nAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[0][ii]-s[0][ii]);
printf("\nFAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[3][ii]-s[3][ii]);
printf("\nExtAVL\t\t");
for (ii = 0; ii < TEST_COUNT; ii++)
printf("%20llu",f[1][ii]-s[1][ii]);
919,7 → 742,6
 
avl_slab = slab_cache_create("avl_slab",sizeof(avltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
favl_slab = slab_cache_create("favl_slab",sizeof(favltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
extavl_slab = slab_cache_create("extavl_slab",sizeof(extavltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
extavlrel_slab = slab_cache_create("extavlrel_slab",sizeof(extavlreltree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
 
/branches/rcu/kernel/test/test.c
60,7 → 60,6
#include <tasklet/tasklet1.def>
#include <synch/rcu1.def>
#include <avltree/avltree1.def>
#include <favltree/favltree1.def>
#include <extavltree/extavltree1.def>
#include <extavlreltree/extavlreltree1.def>
#include <timeout/timeout1.def>
/branches/rcu/kernel/test/test.h
72,7 → 72,6
extern char * test_tasklet1(bool quiet);
extern char * test_rcu1(bool quiet);
extern char * test_avltree1(bool quiet);
extern char * test_favltree1(bool quiet);
extern char * test_extavltree1(bool quiet);
extern char * test_extavlreltree1(bool quiet);
extern char * test_timeout1(bool quiet);
/branches/rcu/kernel/generic/include/adt/avl.h
1,5 → 1,5
/*
* Copyright (C) 2007 Vojtech Mencl
* Copyright (C) 2006 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
87,8 → 87,7
struct avltree_node *root;
 
/**
* Base of tree is value that is smaller or equal then every value in tree
* (valid for positive keys otherwise ignore this atribute).
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
/branches/rcu/kernel/generic/include/adt/extavl.h
98,8 → 98,7
extavltree_node_t head;
 
/**
* Base of tree is value that is smaller or equal then every value in tree
* (valid for positive keys otherwise ignore this atribute).
* Base of tree is value that is smaller or equal then every value in tree.
*
* Base is added to current key when new node is inserted into tree.
* Base is changed to the key of node which is deleted with function
/branches/rcu/kernel/generic/include/cpu.h
41,9 → 41,7
#include <arch/cpu.h>
#include <arch/context.h>
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_FAVL_TREE
#include <adt/favl.h>
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
72,9 → 70,6
#if defined CONFIG_TIMEOUT_AVL_TREE
/** AVL tree structure. */
avltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_FAVL_TREE
/** Fast AVL tree structure. */
favltree_t timeout_active_tree;
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
/** Extended AVL tree structure. */
extavltree_t timeout_active_tree;
/branches/rcu/kernel/generic/include/time/timeout.h
38,8 → 38,6
#include <arch/types.h>
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#elif defined CONFIG_TIMEOUT_FAVL_TREE
#include <adt/favl.h>
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <adt/extavl.h>
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
52,31 → 50,69
typedef void (* timeout_handler_t)(void *arg);
 
 
#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;
 
#if defined CONFIG_TIMEOUT_AVL_TREE
/** Avl tree holding information about connections with other timeouts.
* Experimental use only. */
avltree_node_t node;
#elif defined CONFIG_TIMEOUT_FAVL_TREE
/** Fast Avl tree holding information about connections with other timeouts.
* Use this structure instead of Avl tree. */
favltree_node_t node;
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
/** Extended Avl tree holding information about connections with other timeouts. */
 
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;
 
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
/** Extended Avl tree with relative keys holding information about connections
* with other timeouts. */
 
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 {
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. */
uint64_t ticks;
#endif
 
/** Function that will be called on timeout activation. */
timeout_handler_t handler;
/** Argument to be passed to handler() function. */
85,6 → 121,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/src/adt/avl.c
37,7 → 37,7
* This file implements AVL tree type and operations.
*
* Implemented AVL tree has the following properties:
* @li It is binary search tree with non-unique keys.
* @li it is binary search tree with non-unique keys
* @li Difference of heights of left and right subtree of every node is max 1.
*
* Every node has pointer to its parent which allows insertion of multiple identical keys
49,6 → 49,7
 
#include <adt/avl.h>
#include <debug.h>
#include <panic.h>
 
 
#define AVLTREE_LEFT 0
130,9 → 131,9
 
/*
* Iteratively descend to the leaf that can contain new node.
* Iteratively descend to the leaf that can will contain new node.
* Last node with non-zero balance in the way to leaf is stored as top -
* it si place of possible balance fault.
* it si place of possible balance failure.
*/
dpc = &t->root;
gpa = NULL;
696,6 → 697,7
bool avltree_delete_min(avltree_t *t)
{
avltree_node_t *node;
uint64_t key;
/*
* Start search of smallest key in tree in the root node and
709,8 → 711,9
node = node->lft;
/*
* Use avltree_delete function to delete node from tree.
* Store key and use avltree_delete function to delete node from tree.
*/
key = node->key;
avltree_delete(t,node);
 
return true;
/branches/rcu/kernel/generic/src/time/timeout.c
58,8 → 58,6
 
#if defined CONFIG_TIMEOUT_AVL_TREE
avltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_FAVL_TREE
favltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_create(&CPU->timeout_active_tree);
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
85,8 → 83,6
 
#if defined CONFIG_TIMEOUT_AVL_TREE
avltree_node_initialize(&t->node);
#elif defined CONFIG_TIMEOUT_FAVL_TREE
favltree_node_initialize(&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_node_initialize(&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
112,7 → 108,6
}
 
#if defined CONFIG_TIMEOUT_AVL_TREE || \
defined CONFIG_TIMEOUT_FAVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVLREL_TREE
 
119,7 → 114,7
/** Register timeout
*
* Insert timeout handler f (with argument arg)
* to timeout tree and make it execute in
* to timeout ExtAVL tree and make it execute in
* time microseconds (or slightly more).
*
* @param t Timeout structure.
146,12 → 141,10
t->node.key = us2ticks(time);
 
/*
* Insert timeout into tree structure.
* Put timeout into tree structure.
*/
#if defined CONFIG_TIMEOUT_AVL_TREE
avltree_insert(&CPU->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_FAVL_TREE
favltree_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
166,7 → 159,7
 
/** Unregister timeout
*
* Remove timeout from timeout tree structure.
* Remove timeout from timeout ExtAVL tree structure.
*
* @param t Timeout to unregister.
*
199,8 → 192,6
*/
#if defined CONFIG_TIMEOUT_AVL_TREE
avltree_delete(&t->cpu->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_FAVL_TREE
favltree_delete(&t->cpu->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_delete(&t->cpu->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
/branches/rcu/kernel/generic/src/time/clock.c
56,8 → 56,11
#include <arch/barrier.h>
#include <mm/frame.h>
#include <ddi/ddi.h>
 
 
#if defined CONFIG_TIMEOUT_AVL_TREE || defined CONFIG_TIMEOUT_EXTAVL_TREE
#include <arch/asm.h>
#include <arch/types.h>
#include <panic.h>
#endif
/* Pointer to variable with uptime */
uptime_t *uptime;
 
148,6 → 151,7
* To avoid lock ordering problems,
* run all expired timeouts as you visit them.
*/
 
for (; i <= last_clock_tick; i++) {
clock_update_counters();
215,97 → 219,6
}
}
 
#elif defined CONFIG_TIMEOUT_FAVL_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 last_clock_tick = i + missed_clock_ticks;
favltree_node_t *expnode;
 
/*
* To avoid lock ordering problems,
* run all expired timeouts as you visit them.
*/
for (; i <= last_clock_tick; i++) {
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).
* Function favltree_find_min works in contant time.
*/
while ((expnode = favltree_find_min(&CPU->timeout_active_tree)) != NULL) {
h = favltree_get_instance(expnode,timeout_t,node);
spinlock_lock(&h->lock);
if (expnode->key != i) {
/*
* Base is increased every for cycle.
*/
(CPU->timeout_active_tree.base)++;
spinlock_unlock(&h->lock);
break;
}
/*
* Delete minimal key from the tree and repair tree structure in
* logarithmic time.
*/
favltree_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
/branches/rcu/kernel/Makefile
59,10 → 59,6
DEFS += -DCONFIG_TIMEOUT_AVL_TREE
endif
 
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),favl-tree)
DEFS += -DCONFIG_TIMEOUT_FAVL_TREE
endif
 
ifeq ($(CONFIG_TIMEOUT_DATA_STRUCTURE),ext-avl-tree)
DEFS += -DCONFIG_TIMEOUT_EXTAVL_TREE
endif
160,7 → 156,6
generic/src/adt/list.c \
generic/src/adt/listrcu.c \
generic/src/adt/avl.c \
generic/src/adt/favl.c \
generic/src/adt/extavl.c \
generic/src/adt/extavlrel.c \
generic/src/console/chardev.c \
262,7 → 257,6
test/thread/thread1.c \
test/sysinfo/sysinfo1.c \
test/avltree/avltree1.c \
test/favltree/favltree1.c \
test/extavltree/extavltree1.c \
test/extavlreltree/extavlreltree1.c \
test/timeout/timeout1.c \
/branches/rcu/kernel/kernel.config
50,34 → 50,34
! [(ARCH=mips32&MACHINE=lgxemul)|(ARCH=mips32&MACHINE=bgxemul)|(ARCH=ia32)|(ARCH=amd64)] CONFIG_FB (y/n)
 
# Framebuffer width
@ "640" 640
@ "800" 800
@ "1024" 1024
@ "1152" 1152
@ "1280" 1280
@ "1400" 1400
@ "1440" 1440
@ "1600" 1600
@ "2048" 2048
@ "640"
@ "800"
@ "1024"
@ "1152"
@ "1280"
@ "1400"
@ "1440"
@ "1600"
@ "2048"
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_WIDTH (choice)
 
# Framebuffer height
@ "480" 480
@ "600" 600
@ "768" 768
@ "852" 852
@ "900" 900
@ "960" 960
@ "1024" 1024
@ "1050" 1050
@ "1200" 1200
@ "1536" 1546
@ "480"
@ "600"
@ "768"
@ "852"
@ "900"
@ "960"
@ "1024"
@ "1050"
@ "1200"
@ "1536"
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_HEIGHT (choice)
 
# Framebuffer depth
@ "8" 8
@ "16" 16
@ "24" 24
@ "8"
@ "16"
@ "24"
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_BPP (choice)
 
# Support for SMP
137,7 → 137,6
# Timeout data structure
@ "doubly-linked-list" Doubly linked list
@ "avl-tree" Avl tree
@ "favl-tree" Fast Avl tree
@ "ext-avl-tree" Extended Avl tree
@ "extrel-avl-tree" Extended Avl tree with relative keys
! CONFIG_TIMEOUT_DATA_STRUCTURE (choice)