Subversion Repositories HelenOS

Compare Revisions

Ignore whitespace Rev 2460 → Rev 2461

/branches/rcu/kernel/test/timeout/timeoutbench1.c
29,6 → 29,7
#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>
52,6 → 53,7
* Wrapper tree data structures.
*/
static avltree_t avltree;
static favltree_t favltree;
static extavltree_t extavltree;
static extavlreltree_t extavlreltree;
 
59,6 → 61,7
* 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;
 
66,6 → 69,7
* 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;
 
75,8 → 79,9
unsigned int i;
uint16_t s;
avltree_node_t *a = avl_ffn;
extavltree_node_t *b = extavl_ffn;
extavlreltree_node_t *c = extavlrel_ffn;
favltree_node_t *b = favl_ffn;
extavltree_node_t *c = extavl_ffn;
extavlreltree_node_t *d = extavlrel_ffn;
switch (type) {
case 0:
85,10 → 90,12
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:
96,9 → 103,11
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:
106,9 → 115,11
a->key = i;
b->key = i;
c->key = i;
d->key = i;
a = a->par;
b = b->par;
c = c->par;
c = c->par;
d = d->par;
}
break;
}
121,8 → 132,10
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;
 
142,12 → 155,19
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;
}
158,21 → 178,26
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;
if (!a || !b || !c) {
printf("Deleted nodes: %d, node count: %d, a: %p, b: %p,c: %p ",i,node_count,a,b,c);
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);
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);
}
}
 
186,6 → 211,16
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;
213,6 → 248,12
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;
229,12 → 270,13
*/
static void test1(void)
{
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][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");
311,11 → 353,37
}
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]);
332,6 → 400,9
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]);
346,12 → 417,13
*/
static void test2(void)
{
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][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");
430,11 → 502,39
}
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]);
451,6 → 551,9
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]);
465,12 → 568,13
*/
static void test3(void)
{
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t ds[3][TEST_COUNT],df[3][TEST_COUNT];
uint64_t s[4][TEST_COUNT],f[4][TEST_COUNT];
uint64_t ds[4][TEST_COUNT],df[4][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");
549,11 → 653,38
}
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]);
570,6 → 701,9
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]);
584,11 → 718,12
*/
static void test4(void)
{
uint64_t s[3][TEST_COUNT],f[3][TEST_COUNT];
uint64_t s[4][TEST_COUNT],f[4][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;
642,6 → 777,45
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;
725,6 → 899,9
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]);
742,6 → 919,7
 
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,6 → 60,7
#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,6 → 72,7
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/test/favltree/favltree1.def
0,0 → 1,6
{
"favltree1",
"Test Fast Avl tree operations",
&test_favltree1,
true
},
/branches/rcu/kernel/test/favltree/favltree1.c
0,0 → 1,289
/*
* Copyright (c) 2007 Vojtech Mencl
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* - Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* - Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* - The name of the author may not be used to endorse or promote products
* derived from this software without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
 
#include <test.h>
#include <print.h>
#include <adt/favl.h>
#include <debug.h>
 
 
#define NODE_COUNT 100
 
/*
* wrapper structure with a pointer to favl tree root
*/
static favltree_t favltree;
 
/*
* favl tree nodes in array for faster allocating
*/
static favltree_node_t favltree_nodes[NODE_COUNT];
 
/*
* head of free nodes' list:
*/
static favltree_node_t *first_free_node = NULL;
 
 
 
static int test_tree_balance(favltree_node_t *node);
static favltree_node_t *test_tree_parents(favltree_node_t *node);
static void print_tree_structure_flat (favltree_node_t *node, int level);
static favltree_node_t *alloc_favltree_node(void);
 
 
 
static favltree_node_t *test_tree_parents(favltree_node_t *node)
{
favltree_node_t *tmp;
if (!node) return NULL;
 
if (node->lft) {
tmp = test_tree_parents(node->lft);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->lft);
}
}
if (node->rgt) {
tmp = test_tree_parents(node->rgt);
if (tmp != node) {
printf("Bad parent pointer key: %d, address: %p\n",tmp->key,node->rgt);
}
}
return node->par;
}
 
int test_tree_balance(favltree_node_t *node)
{
int h1, h2, diff;
 
if (!node) return 0;
h1 = test_tree_balance(node->lft);
h2 = test_tree_balance(node->rgt);
diff = h2 - h1;
if (diff != node->balance || (diff != -1 && diff != 0 && diff != 1)) {
printf("Bad balance\n");
}
return h1 > h2 ? h1 + 1 : h2 + 1;
}
 
/**
* Prints the structure of node, which is level levels from the top of the tree.
*/
static void print_tree_structure_flat (favltree_node_t *node, int level)
{
/* You can set the maximum level as high as you like.
Most of the time, you'll want to debug code using small trees,
so that a large level indicates a loop, which is a bug. */
if (level > 16)
{
printf ("[...]");
return;
}
 
if (node == NULL)
return;
 
printf ("%d[%d]", node->key,node->balance);
if (node->lft != NULL || node->rgt != NULL)
{
printf("(");
 
print_tree_structure_flat (node->lft, level + 1);
if (node->rgt != NULL)
{
printf(",");
print_tree_structure_flat (node->rgt, level + 1);
}
 
printf(")");
}
}
 
 
//****************************************************************
static void alloc_favltree_node_prepare(void)
{
int i;
 
for (i = 0; i < NODE_COUNT - 1; i++) {
favltree_nodes[i].par = &(favltree_nodes[i+1]);
}
/*
* Node keys which will be used for insertion. Up to NODE_COUNT size of array.
*/
 
// First tree node and same key
favltree_nodes[0].key = 60;
favltree_nodes[1].key = 60;
favltree_nodes[2].key = 60;
//LL rotation
favltree_nodes[3].key = 50;
favltree_nodes[4].key = 40;
favltree_nodes[5].key = 30;
//LR rotation
favltree_nodes[6].key = 20;
favltree_nodes[7].key = 20;
favltree_nodes[8].key = 25;
favltree_nodes[9].key = 25;
//LL rotation in lower floor
favltree_nodes[10].key = 35;
//RR rotation
favltree_nodes[11].key = 70;
favltree_nodes[12].key = 80;
//RL rotation
favltree_nodes[13].key = 90;
favltree_nodes[14].key = 85;
//Insert 0 key
favltree_nodes[15].key = 0;
favltree_nodes[16].key = 0;
//Insert reverse
favltree_nodes[17].key = 600;
favltree_nodes[18].key = 500;
favltree_nodes[19].key = 400;
favltree_nodes[20].key = 300;
 
for (i = 21; i < NODE_COUNT; i++)
favltree_nodes[i].key = i * 3;
favltree_nodes[i].par = NULL;
first_free_node = &(favltree_nodes[0]);
}
 
static favltree_node_t *alloc_favltree_node(void)
{
favltree_node_t *node;
 
node = first_free_node;
first_free_node = first_free_node->par;
 
return node;
}
//****************************************************************
 
static void test_tree_insert(favltree_t *tree, unsigned int node_count, int quiet)
{
unsigned int i;
favltree_node_t *newnode;
 
/*
* Initialize tree before using.
*/
favltree_create(tree);
if (!quiet) printf("\nInserting %d nodes ...\n", node_count);
 
for (i = 0; i < node_count; i++) {
newnode = alloc_favltree_node();
//if (!quiet) printf("[[[%d]]]\n",newnode->key);
favltree_insert(tree, newnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
if (!quiet) printf("Inserting was finished\n");
}
 
 
static void test_tree_delete(favltree_t *tree, int node_count, int node_position, bool quiet)
{
favltree_node_t *delnode;
unsigned int i;
//aktualni pocet tiku:
if (!quiet) printf("Deleting tree...\n");
 
switch(node_position) {
case 0: //mazani vzdy korene
if (!quiet) printf("\nDelete root nodes\n");
while(tree->root != NULL) {
delnode = tree->root;
favltree_delete(tree,delnode);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
break;
case 1:
if (!quiet) printf("\nDelete nodes according to their time of origin\n");
for (i = 0; i < node_count; i++) {
favltree_delete(tree,&(favltree_nodes[i]));
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
 
break;
}
if (!quiet) printf("Deletion was finished\n");
}
 
static void timeout_tree(favltree_t *tree, int node_count, bool quiet)
{
int i = 0;
if (!quiet) printf("\nTimeout tree ...\n");
while(tree->root != NULL) {
i++;
favltree_delete_min(tree);
if (!quiet) {
test_tree_parents(tree->root);
test_tree_balance(tree->root);
}
}
 
if (!quiet && (i != node_count)) printf("Bad node count. Some nodes have been lost!\n");
 
if (!quiet) printf("Timeout tree finished\n");
}
 
char * test_favltree1(bool quiet)
{
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
test_tree_delete(&favltree, NODE_COUNT, 0, quiet);
 
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
test_tree_delete(&favltree, NODE_COUNT, 1, quiet);
 
alloc_favltree_node_prepare();
test_tree_insert(&favltree, NODE_COUNT, quiet);
timeout_tree(&favltree, NODE_COUNT, quiet);
 
return NULL;
}
/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"
@ "800"
@ "1024"
@ "1152"
@ "1280"
@ "1400"
@ "1440"
@ "1600"
@ "2048"
@ "640" 640
@ "800" 800
@ "1024" 1024
@ "1152" 1152
@ "1280" 1280
@ "1400" 1400
@ "1440" 1440
@ "1600" 1600
@ "2048" 2048
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_WIDTH (choice)
 
# Framebuffer height
@ "480"
@ "600"
@ "768"
@ "852"
@ "900"
@ "960"
@ "1024"
@ "1050"
@ "1200"
@ "1536"
@ "480" 480
@ "600" 600
@ "768" 768
@ "852" 852
@ "900" 900
@ "960" 960
@ "1024" 1024
@ "1050" 1050
@ "1200" 1200
@ "1536" 1546
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_HEIGHT (choice)
 
# Framebuffer depth
@ "8"
@ "16"
@ "24"
@ "8" 8
@ "16" 16
@ "24" 24
! [(ARCH=ia32|ARCH=amd64)&CONFIG_FB=y] CONFIG_VESA_BPP (choice)
 
# Support for SMP
137,6 → 137,7
# 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)
/branches/rcu/kernel/generic/include/time/timeout.h
38,6 → 38,8
#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
50,69 → 52,31
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.
*/
 
#if defined CONFIG_TIMEOUT_AVL_TREE
/** Avl tree holding information about connections with other timeouts.
* Experimental use only. */
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;
 
#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
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree node structure holds information
* about connections with other timeouts.
*/
/** Extended Avl tree holding 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
 
typedef struct {
SPINLOCK_DECLARE(lock);
/**
* Extended AVL tree with relative keys node structure holds information
* about connections with other timeouts.
*/
/** Extended Avl tree with relative keys holding 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. */
121,8 → 85,6
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/include/cpu.h
41,7 → 41,9
#include <arch/cpu.h>
#include <arch/context.h>
#if defined CONFIG_TIMEOUT_AVL_TREE
#include <adt/avl.h>
#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
70,6 → 72,9
#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/adt/avl.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
87,7 → 87,8
struct avltree_node *root;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
* Base of tree is value that is smaller or equal then every value in tree
* (valid for positive keys otherwise ignore this atribute).
*
* 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,7 → 98,8
extavltree_node_t head;
 
/**
* Base of tree is value that is smaller or equal then every value in tree.
* Base of tree is value that is smaller or equal then every value in tree
* (valid for positive keys otherwise ignore this atribute).
*
* 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/src/time/timeout.c
58,6 → 58,8
 
#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
83,6 → 85,8
 
#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
108,6 → 112,7
}
 
#if defined CONFIG_TIMEOUT_AVL_TREE || \
defined CONFIG_TIMEOUT_FAVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVL_TREE || \
defined CONFIG_TIMEOUT_EXTAVLREL_TREE
 
114,7 → 119,7
/** Register timeout
*
* Insert timeout handler f (with argument arg)
* to timeout ExtAVL tree and make it execute in
* to timeout tree and make it execute in
* time microseconds (or slightly more).
*
* @param t Timeout structure.
141,10 → 146,12
t->node.key = us2ticks(time);
 
/*
* Put timeout into tree structure.
* Insert 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
159,7 → 166,7
 
/** Unregister timeout
*
* Remove timeout from timeout ExtAVL tree structure.
* Remove timeout from timeout tree structure.
*
* @param t Timeout to unregister.
*
192,6 → 199,8
*/
#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,11 → 56,8
#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;
 
151,7 → 148,6
* To avoid lock ordering problems,
* run all expired timeouts as you visit them.
*/
 
for (; i <= last_clock_tick; i++) {
clock_update_counters();
219,6 → 215,97
}
}
 
#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/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,7 → 49,6
 
#include <adt/avl.h>
#include <debug.h>
#include <panic.h>
 
 
#define AVLTREE_LEFT 0
131,9 → 130,9
 
/*
* Iteratively descend to the leaf that can will contain new node.
* Iteratively descend to the leaf that can contain new node.
* Last node with non-zero balance in the way to leaf is stored as top -
* it si place of possible balance failure.
* it si place of possible balance fault.
*/
dpc = &t->root;
gpa = NULL;
697,7 → 696,6
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
711,9 → 709,8
node = node->lft;
/*
* Store key and use avltree_delete function to delete node from tree.
* Use avltree_delete function to delete node from tree.
*/
key = node->key;
avltree_delete(t,node);
 
return true;
/branches/rcu/kernel/Makefile
59,6 → 59,10
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
156,6 → 160,7
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 \
257,6 → 262,7
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 \