Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2450 → Rev 2449

/branches/rcu/kernel/test/timeout/timeoutbench1.c
41,9 → 41,9
/*
* Node count must be more then 1000!
*/
#define NODE_COUNT 100000
#define NODE_COUNT 1000000
#define GEN_NUM 275604541
#define OPERATION_COUNT 1000000
#define OPERATION_COUNT 100000000
#define TEST_COUNT 3
 
static unsigned int node_count[TEST_COUNT] = {100,1000,NODE_COUNT};
229,6 → 229,7
*/
static void test1(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
246,6 → 247,7
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
254,9 → 256,11
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while ((a = avltree.root) != NULL) {
265,10 → 269,12
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
277,9 → 283,11
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while ((b = extavltree.root) != NULL) {
288,10 → 296,12
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
300,9 → 310,11
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while ((c = extavlreltree.root) != NULL) {
311,6 → 323,7
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
346,6 → 359,7
*/
static void test2(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
363,6 → 377,7
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
371,9 → 386,11
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while (avltree.root != NULL) {
383,10 → 400,12
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
395,9 → 414,11
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while (extavltree.root != NULL) {
407,9 → 428,11
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
418,9 → 441,11
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while (extavlreltree.root != NULL) {
430,6 → 455,7
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
465,6 → 491,7
*/
static void test3(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
unsigned int i,ii;
482,6 → 509,7
/*
* AVL INSERT
*/
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
490,9 → 518,11
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
/*
* AVL DELETE
*/
ipl = interrupts_disable();
ds[0][ii] = get_cycle();
while (avltree.root != NULL) {
502,10 → 532,12
}
df[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL INSERT
*/
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
514,9 → 546,11
}
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVL DELETE
*/
ipl = interrupts_disable();
ds[1][ii] = get_cycle();
while (extavltree.root != NULL) {
526,9 → 560,11
}
df[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel INSERT
*/
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
537,9 → 573,11
}
f[2][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel DELETE
*/
ipl = interrupts_disable();
ds[2][ii] = get_cycle();
while (extavlreltree.root != NULL) {
549,6 → 587,7
}
df[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
584,6 → 623,7
*/
static void test4(void)
{
ipl_t ipl;
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
unsigned int i,ii;
avltree_node_t *a;
607,6 → 647,7
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[0][ii] = get_cycle();
avltree_create(&avltree);
640,6 → 681,7
}
f[0][ii] = get_cycle();
interrupts_restore(ipl);
 
/*
* ExtAVL
646,6 → 688,7
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[1][ii] = get_cycle();
extavltree_create(&extavltree);
679,6 → 722,7
}
 
f[1][ii] = get_cycle();
interrupts_restore(ipl);
/*
* ExtAVLrel
685,6 → 729,7
*/
rr = r;
nc = 0;
ipl = interrupts_disable();
s[2][ii] = get_cycle();
extavlreltree_create(&extavlreltree);
720,6 → 765,7
}
 
f[2][ii] = get_cycle();
interrupts_restore(ipl);
}
printf("\n----------------------------------------------------------------------------");
printf("\nAVL\t\t");
749,9 → 795,11
return NULL;
 
/*
* Disable interrupts,
* store initial cycle count,
* do test,
* store finish cycle count,
* enable interrupts,
* show results
*/
 
/branches/rcu/kernel/generic/src/time/timeout.c
191,11 → 191,11
* Delete timeout from tree structure.
*/
#if defined CONFIG_TIMEOUT_AVL_TREE
avltree_delete(&t->cpu->timeout_active_tree,&t->node);
avltree_delete(&CPU->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
extavltree_delete(&t->cpu->timeout_active_tree,&t->node);
extavltree_delete(&CPU->timeout_active_tree,&t->node);
#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
extavlreltree_delete(&t->cpu->timeout_active_tree,&t->node);
extavlreltree_delete(&CPU->timeout_active_tree,&t->node);
#endif
 
spinlock_unlock(&t->cpu->timeoutlock);
/branches/rcu/kernel/generic/src/time/clock.c
1,6 → 1,5
/*
* Copyright (C) 2001-2004 Jakub Jermar
* Copyright (C) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
56,11 → 55,7
#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;
 
143,8 → 138,8
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;
uint64_t *i = &(CPU->timeout_active_tree.base);
uint64_t absolute_clock_ticks = *i + missed_clock_ticks;
avltree_node_t *expnode;
 
/*
152,11 → 147,15
* run all expired timeouts as you visit them.
*/
 
for (; i <= last_clock_tick; i++) {
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).
164,11 → 163,7
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) {
/*
* Base is increased every for cycle.
*/
(CPU->timeout_active_tree.base)++;
if (expnode->key != *i) {
spinlock_unlock(&h->lock);
break;
}
234,10 → 229,9
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;
uint64_t *i = &(CPU->timeout_active_tree.base);
uint64_t absolute_clock_ticks = *i + missed_clock_ticks;
extavltree_node_t *expnode;
//ipl_t ipl;
 
/*
* To avoid lock ordering problems,
244,7 → 238,11
* run all expired timeouts as you visit them.
*/
 
for (; i <= last_clock_tick; i++) {
for (; *i <= absolute_clock_ticks; (*i)++) {
/*
* Basetime is encreased by missed clock ticks + 1 !!
*/
clock_update_counters();
spinlock_lock(&CPU->timeoutlock);
251,15 → 249,11
/*
* Check whether first timeout in list time out. If so perform callback function and try
* next timeout (more timeouts can have same timeout).
*/
*/
while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {
h = extavltree_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_lock(&h->lock);
if (expnode->key != *i) {
spinlock_unlock(&h->lock);
break;
}
/branches/rcu/kernel/generic/src/adt/extavl.c
84,7 → 84,7
/** Insert new node into ExtAVL tree.
*
* New node's key must be set - to that key will be added base (default 0).
* New node's key must be set.
*
* @param t ExtAVL tree structure.
* @param newnode New node to be inserted.
705,7 → 705,7
}
 
 
/** Delete node from ExtAVL tree with the smallest key.
/** Delete node from ExtAVL tree with the smallest key and set base of tree to that key.
*
* @param t ExtAVL tree structure.
*/
753,7 → 753,7
*/
t->root = NULL;
}
 
/*
* Delete node from the list.
*/
/branches/rcu/kernel/generic/src/adt/avl.c
690,7 → 690,7
}
 
 
/** Delete node from AVL tree with the smallest key.
/** Delete node from AVL tree with the smallest key and set base of tree to that key.
*
* @param t AVL tree structure.
*/
716,5 → 716,10
key = node->key;
avltree_delete(t,node);
 
/*
* Change base to the key of deleted node.
*/
t->base = key;
 
return true;
}