HelenOSHelenOS-docHelenOS-historic

Català-Valencià – Catalan中文 – Chinese (Simplified)中文 – Chinese (Traditional)Česky – CzechDansk – DanishNederlands – DutchEnglish – EnglishSuomi – FinnishFrançais – FrenchDeutsch – Germanעברית – Hebrewहिंदी – HindiMagyar – HungarianBahasa Indonesia – IndonesianItaliano – Italian日本語 – Japanese한국어 – KoreanМакедонски – Macedonianमराठी – MarathiNorsk – NorwegianPolski – PolishPortuguês – PortuguesePortuguês – Portuguese (Brazil)Русский – RussianSlovenčina – SlovakSlovenščina – SlovenianEspañol – SpanishSvenska – SwedishTürkçe – TurkishУкраїнська – UkrainianOëzbekcha – Uzbek

Compare Revisions

• This comparison shows the changes necessary to convert path

  → /branches/rcu/kernel/generic/ @ 2460

  → /branches/rcu/kernel/generic/ @ 2461

  ↔ Reverse comparison

• Compare Path:	Rev

  With Path:	Rev

Ignore whitespace Rev 2460 → Rev 2461

/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;