/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; |
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 |
---|
42,6 → 42,8 |
#include <arch/context.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 |
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; |
152,7 → 149,6 |
* run all expired timeouts as you visit them. |
*/ |
for (; i <= last_clock_tick; i++) { |
clock_update_counters(); |
spinlock_lock(&CPU->timeoutlock); |
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 \ |