Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2449 → Rev 2450

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