WebSVN – HelenOS – Diff – /branches/rcu/kernel/generic/src/time/clock.c


/*
 * 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
 * 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.
 */
 
/** @addtogroup time
 * @{
 */
 
/**
 * @file
 * @brief   High-level clock interrupt handler.
 *
 * This file contains the clock() function which is the source
 * of preemption. It is also responsible for executing expired
 * timeouts.
 */
 
#include <time/clock.h>
#include <time/timeout.h>
#include <config.h>
#include <synch/spinlock.h>
#include <synch/waitq.h>
#include <func.h>
#include <proc/scheduler.h>
#include <cpu.h>
#include <arch.h>
#include <adt/list.h>
#include <atomic.h>
#include <proc/thread.h>
#include <sysinfo/sysinfo.h>
#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;
 
/** Physical memory area of the real time clock */
static parea_t clock_parea;
 
/* Variable holding fragment of second, so that we would update
 * seconds correctly
 */
static unative_t secfrag = 0;
 
/** Initialize realtime clock counter
 *
 * The applications (and sometimes kernel) need to access accurate
 * information about realtime data. We allocate 1 page with these
 * data and update it periodically.
 */
void clock_counter_init(void)
{
    void *faddr;
 
    faddr = frame_alloc(ONE_FRAME, FRAME_ATOMIC);
    if (!faddr)
        panic("Cannot allocate page for clock");
   
    uptime = (uptime_t *) PA2KA(faddr);
   
    uptime->seconds1 = 0;
    uptime->seconds2 = 0;
    uptime->useconds = 0;
 
    clock_parea.pbase = (uintptr_t) faddr;
    clock_parea.vbase = (uintptr_t) uptime;
    clock_parea.frames = 1;
    clock_parea.cacheable = true;
    ddi_parea_register(&clock_parea);
 
    /*
     * Prepare information for the userspace so that it can successfully
     * physmem_map() the clock_parea.
     */
    sysinfo_set_item_val("clock.cacheable", NULL, (unative_t) true);
    sysinfo_set_item_val("clock.faddr", NULL, (unative_t) faddr);
}
 
 
/** Update public counters
 *
 * Update it only on first processor
 * TODO: Do we really need so many write barriers?
 */
static void clock_update_counters(void)
{
    if (CPU->id == 0) {
        secfrag += 1000000 / HZ;
        if (secfrag >= 1000000) {
            secfrag -= 1000000;
            uptime->seconds1++;
            write_barrier();
            uptime->useconds = secfrag;
            write_barrier();
            uptime->seconds2 = uptime->seconds1;
        } else
            uptime->useconds += 1000000 / HZ;
    }
}
 
#if defined CONFIG_TIMEOUT_AVL_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;
    avltree_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).
         */
        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)++;
                spinlock_unlock(&h->lock);
                break;
            }
           
            /*
             * Delete minimal key from the tree and repair tree structure in
             * logarithmic time.
             */
            avltree_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
 *
 * 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;
    extavltree_node_t *expnode;
    //ipl_t ipl;
 
    /*
     * 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 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_unlock(&h->lock);
                break;
            }
           
            /*
             * Delete first node in the list and repair tree structure in
             * constant time.
             */
            extavltree_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_EXTAVLREL_TREE
 
/** Clock routine
 *
 * Clock routine executed from clock interrupt handler
 * (assuming interrupts_disable()'d). Runs expired timeouts
 * and preemptive scheduling.
 *
 */
void clock(void)
{
    extavlreltree_node_t *expnode;
    timeout_t *h;
    timeout_handler_t f;
    void *arg;
    count_t missed_clock_ticks = CPU->missed_clock_ticks;
    int i;
 
    /*
     * To avoid lock ordering problems,
     * run all expired timeouts as you visit them.
     */
    for (i = 0; i <= missed_clock_ticks; i++) {
        clock_update_counters();
        spinlock_lock(&CPU->timeoutlock);
 
        /*
         * 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 = extavlreltree_get_instance(expnode,timeout_t,node);
            spinlock_lock(&h->lock);
            if (expnode->key != 0) {
                expnode->key--;
                spinlock_unlock(&h->lock);
                break;
            }
           
            /*
             * Delete first node in the list and repair tree structure in
             * constant time. Be careful of expnode's key, it must be 0!
             */
            extavlreltree_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();
        }
    }
}
 
 
 
#else
 
 
/** Clock routine
 *
 * Clock routine executed from clock interrupt handler
 * (assuming interrupts_disable()'d). Runs expired timeouts
 * and preemptive scheduling.
 *
 */
void clock(void)
{
    link_t *l;
    timeout_t *h;
    timeout_handler_t f;
    void *arg;
    count_t missed_clock_ticks = CPU->missed_clock_ticks;
    int i;
 
    /*
     * To avoid lock ordering problems,
     * run all expired timeouts as you visit them.
     */
    for (i = 0; i <= missed_clock_ticks; i++) {
        clock_update_counters();
        spinlock_lock(&CPU->timeoutlock);
        while ((l = CPU->timeout_active_head.next) != &CPU->timeout_active_head) {
            h = list_get_instance(l, timeout_t, link);
            spinlock_lock(&h->lock);
            if (h->ticks-- != 0) {
                spinlock_unlock(&h->lock);
                break;
            }
            list_remove(l);
            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();
        }
    }
}
 
#endif
/** @}
 */
 

Rev 2421	Rev 2450
1	/*	1	/*
2	* Copyright (C) 2001-2004 Jakub Jermar	2	* Copyright (C) 2001-2004 Jakub Jermar
-		3	* Copyright (C) 2007 Vojtech Mencl
3	* All rights reserved.	4	* All rights reserved.
4	*	5	*
5	* Redistribution and use in source and binary forms, with or without	6	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	7	* modification, are permitted provided that the following conditions
7	* are met:	8	* are met:
8	*	9	*
9	* - Redistributions of source code must retain the above copyright	10	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	11	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	12	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	13	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	14	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	15	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	16	* derived from this software without specific prior written permission.
16	*	17	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	18	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	19	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	20	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	21	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	22	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	23	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	24	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	25	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	26	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	27	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	28	*/
28		29
29	/** @addtogroup time	30	/** @addtogroup time
30	* @{	31	* @{
31	*/	32	*/
32		33
33	/**	34	/**
34	* @file	35	* @file
35	* @brief High-level clock interrupt handler.	36	* @brief High-level clock interrupt handler.
36	*	37	*
37	* This file contains the clock() function which is the source	38	* This file contains the clock() function which is the source
38	* of preemption. It is also responsible for executing expired	39	* of preemption. It is also responsible for executing expired
39	* timeouts.	40	* timeouts.
40	*/	41	*/
41		42
42	#include <time/clock.h>	43	#include <time/clock.h>
43	#include <time/timeout.h>	44	#include <time/timeout.h>
44	#include <config.h>	45	#include <config.h>
45	#include <synch/spinlock.h>	46	#include <synch/spinlock.h>
46	#include <synch/waitq.h>	47	#include <synch/waitq.h>
47	#include <func.h>	48	#include <func.h>
48	#include <proc/scheduler.h>	49	#include <proc/scheduler.h>
49	#include <cpu.h>	50	#include <cpu.h>
50	#include <arch.h>	51	#include <arch.h>
51	#include <adt/list.h>	52	#include <adt/list.h>
52	#include <atomic.h>	53	#include <atomic.h>
53	#include <proc/thread.h>	54	#include <proc/thread.h>
54	#include <sysinfo/sysinfo.h>	55	#include <sysinfo/sysinfo.h>
55	#include <arch/barrier.h>	56	#include <arch/barrier.h>
56	#include <mm/frame.h>	57	#include <mm/frame.h>
57	#include <ddi/ddi.h>	58	#include <ddi/ddi.h>
-		59	#if defined CONFIG_TIMEOUT_AVL_TREE \|\| defined CONFIG_TIMEOUT_EXTAVL_TREE
-		60	#include <arch/asm.h>
-		61	#include <arch/types.h>
-		62	#include <panic.h>
58		63	#endif
59	/* Pointer to variable with uptime */	64	/* Pointer to variable with uptime */
60	uptime_t *uptime;	65	uptime_t *uptime;
61		66
62	/** Physical memory area of the real time clock */	67	/** Physical memory area of the real time clock */
63	static parea_t clock_parea;	68	static parea_t clock_parea;
64		69
65	/* Variable holding fragment of second, so that we would update	70	/* Variable holding fragment of second, so that we would update
66	* seconds correctly	71	* seconds correctly
67	*/	72	*/
68	static unative_t secfrag = 0;	73	static unative_t secfrag = 0;
69		74
70	/** Initialize realtime clock counter	75	/** Initialize realtime clock counter
71	*	76	*
72	* The applications (and sometimes kernel) need to access accurate	77	* The applications (and sometimes kernel) need to access accurate
73	* information about realtime data. We allocate 1 page with these	78	* information about realtime data. We allocate 1 page with these
74	* data and update it periodically.	79	* data and update it periodically.
75	*/	80	*/
76	void clock_counter_init(void)	81	void clock_counter_init(void)
77	{	82	{
78	void *faddr;	83	void *faddr;
79		84
80	faddr = frame_alloc(ONE_FRAME, FRAME_ATOMIC);	85	faddr = frame_alloc(ONE_FRAME, FRAME_ATOMIC);
81	if (!faddr)	86	if (!faddr)
82	panic("Cannot allocate page for clock");	87	panic("Cannot allocate page for clock");
83		88
84	uptime = (uptime_t *) PA2KA(faddr);	89	uptime = (uptime_t *) PA2KA(faddr);
85		90
86	uptime->seconds1 = 0;	91	uptime->seconds1 = 0;
87	uptime->seconds2 = 0;	92	uptime->seconds2 = 0;
88	uptime->useconds = 0;	93	uptime->useconds = 0;
89		94
90	clock_parea.pbase = (uintptr_t) faddr;	95	clock_parea.pbase = (uintptr_t) faddr;
91	clock_parea.vbase = (uintptr_t) uptime;	96	clock_parea.vbase = (uintptr_t) uptime;
92	clock_parea.frames = 1;	97	clock_parea.frames = 1;
93	clock_parea.cacheable = true;	98	clock_parea.cacheable = true;
94	ddi_parea_register(&clock_parea);	99	ddi_parea_register(&clock_parea);
95		100
96	/*	101	/*
97	* Prepare information for the userspace so that it can successfully	102	* Prepare information for the userspace so that it can successfully
98	* physmem_map() the clock_parea.	103	* physmem_map() the clock_parea.
99	*/	104	*/
100	sysinfo_set_item_val("clock.cacheable", NULL, (unative_t) true);	105	sysinfo_set_item_val("clock.cacheable", NULL, (unative_t) true);
101	sysinfo_set_item_val("clock.faddr", NULL, (unative_t) faddr);	106	sysinfo_set_item_val("clock.faddr", NULL, (unative_t) faddr);
102	}	107	}
103		108
104		109
105	/** Update public counters	110	/** Update public counters
106	*	111	*
107	* Update it only on first processor	112	* Update it only on first processor
108	* TODO: Do we really need so many write barriers?	113	* TODO: Do we really need so many write barriers?
109	*/	114	*/
110	static void clock_update_counters(void)	115	static void clock_update_counters(void)
111	{	116	{
112	if (CPU->id == 0) {	117	if (CPU->id == 0) {
113	secfrag += 1000000 / HZ;	118	secfrag += 1000000 / HZ;
114	if (secfrag >= 1000000) {	119	if (secfrag >= 1000000) {
115	secfrag -= 1000000;	120	secfrag -= 1000000;
116	uptime->seconds1++;	121	uptime->seconds1++;
117	write_barrier();	122	write_barrier();
118	uptime->useconds = secfrag;	123	uptime->useconds = secfrag;
119	write_barrier();	124	write_barrier();
120	uptime->seconds2 = uptime->seconds1;	125	uptime->seconds2 = uptime->seconds1;
121	} else	126	} else
122	uptime->useconds += 1000000 / HZ;	127	uptime->useconds += 1000000 / HZ;
123	}	128	}
124	}	129	}
125		130
126	#if defined CONFIG_TIMEOUT_AVL_TREE	131	#if defined CONFIG_TIMEOUT_AVL_TREE
127		132
128	/** Clock routine	133	/** Clock routine
129	*	134	*
130	* Clock routine executed from clock interrupt handler	135	* Clock routine executed from clock interrupt handler
131	* (assuming interrupts_disable()'d). Runs expired timeouts	136	* (assuming interrupts_disable()'d). Runs expired timeouts
132	* and preemptive scheduling.	137	* and preemptive scheduling.
133	*	138	*
134	*/	139	*/
135	void clock(void)	140	void clock(void)
136	{	141	{
137	timeout_t *h;	142	timeout_t *h;
138	timeout_handler_t f;	143	timeout_handler_t f;
139	void *arg;	144	void *arg;
140	count_t missed_clock_ticks = CPU->missed_clock_ticks;	145	count_t missed_clock_ticks = CPU->missed_clock_ticks;
141	uint64_t *i = &(CPU->timeout_active_tree.base);	146	uint64_t i = CPU->timeout_active_tree.base;
142	uint64_t absolute_clock_ticks = *i + missed_clock_ticks;	147	uint64_t last_clock_tick = i + missed_clock_ticks;
143	avltree_node_t *expnode;	148	avltree_node_t *expnode;
144		149
145	/*	150	/*
146	* To avoid lock ordering problems,	151	* To avoid lock ordering problems,
147	* run all expired timeouts as you visit them.	152	* run all expired timeouts as you visit them.
148	*/	153	*/
149		154
150	for (; i <= absolute_clock_ticks; (i)++) {	-
151	/*	155
152	* Basetime is encreased by missed clock ticks + 1 !!	156	for (; i <= last_clock_tick; i++) {
153	*/	-
154		-
155	clock_update_counters();	157	clock_update_counters();
156	spinlock_lock(&CPU->timeoutlock);	158	spinlock_lock(&CPU->timeoutlock);
157		159
158		-
159	/*	160	/*
160	* Check whether first timeout (with the smallest key in the tree) time out. If so perform	161	* Check whether first timeout (with the smallest key in the tree) time out. If so perform
161	* callback function and try next timeout (more timeouts can have same timeout).	162	* callback function and try next timeout (more timeouts can have same timeout).
162	*/	163	*/
163	while ((expnode = avltree_find_min(&CPU->timeout_active_tree)) != NULL) {	164	while ((expnode = avltree_find_min(&CPU->timeout_active_tree)) != NULL) {
164	h = avltree_get_instance(expnode,timeout_t,node);	165	h = avltree_get_instance(expnode,timeout_t,node);
165	spinlock_lock(&h->lock);	166	spinlock_lock(&h->lock);
166	if (expnode->key != *i) {	167	if (expnode->key != i) {
-		168	/*
-		169	* Base is increased every for cycle.
-		170	*/
-		171	(CPU->timeout_active_tree.base)++;
167	spinlock_unlock(&h->lock);	172	spinlock_unlock(&h->lock);
168	break;	173	break;
169	}	174	}
170		175
171	/*	176	/*
172	* Delete minimal key from the tree and repair tree structure in	177	* Delete minimal key from the tree and repair tree structure in
173	* logarithmic time.	178	* logarithmic time.
174	*/	179	*/
175	avltree_delete_min(&CPU->timeout_active_tree);	180	avltree_delete_min(&CPU->timeout_active_tree);
176		181
177	f = h->handler;	182	f = h->handler;
178	arg = h->arg;	183	arg = h->arg;
179	timeout_reinitialize(h);	184	timeout_reinitialize(h);
180	spinlock_unlock(&h->lock);	185	spinlock_unlock(&h->lock);
181	spinlock_unlock(&CPU->timeoutlock);	186	spinlock_unlock(&CPU->timeoutlock);
182		187
183	f(arg);	188	f(arg);
184		189
185	spinlock_lock(&CPU->timeoutlock);	190	spinlock_lock(&CPU->timeoutlock);
186	}	191	}
187	spinlock_unlock(&CPU->timeoutlock);	192	spinlock_unlock(&CPU->timeoutlock);
188	}	193	}
189		194
190	CPU->missed_clock_ticks = 0;	195	CPU->missed_clock_ticks = 0;
191		196
192	/*	197	/*
193	* Do CPU usage accounting and find out whether to preempt THREAD.	198	* Do CPU usage accounting and find out whether to preempt THREAD.
194	*/	199	*/
195	if (THREAD) {	200	if (THREAD) {
196	uint64_t ticks;	201	uint64_t ticks;
197		202
198	spinlock_lock(&CPU->lock);	203	spinlock_lock(&CPU->lock);
199	CPU->needs_relink += 1 + missed_clock_ticks;	204	CPU->needs_relink += 1 + missed_clock_ticks;
200	spinlock_unlock(&CPU->lock);	205	spinlock_unlock(&CPU->lock);
201		206
202	spinlock_lock(&THREAD->lock);	207	spinlock_lock(&THREAD->lock);
203	if ((ticks = THREAD->ticks)) {	208	if ((ticks = THREAD->ticks)) {
204	if (ticks >= 1 + missed_clock_ticks)	209	if (ticks >= 1 + missed_clock_ticks)
205	THREAD->ticks -= 1 + missed_clock_ticks;	210	THREAD->ticks -= 1 + missed_clock_ticks;
206	else	211	else
207	THREAD->ticks = 0;	212	THREAD->ticks = 0;
208	}	213	}
209	spinlock_unlock(&THREAD->lock);	214	spinlock_unlock(&THREAD->lock);
210		215
211	if (!ticks && !PREEMPTION_DISABLED) {	216	if (!ticks && !PREEMPTION_DISABLED) {
212	scheduler();	217	scheduler();
213	}	218	}
214	}	219	}
215	}	220	}
216		221
217	#elif defined CONFIG_TIMEOUT_EXTAVL_TREE	222	#elif defined CONFIG_TIMEOUT_EXTAVL_TREE
218		223
219	/** Clock routine	224	/** Clock routine
220	*	225	*
221	* Clock routine executed from clock interrupt handler	226	* Clock routine executed from clock interrupt handler
222	* (assuming interrupts_disable()'d). Runs expired timeouts	227	* (assuming interrupts_disable()'d). Runs expired timeouts
223	* and preemptive scheduling.	228	* and preemptive scheduling.
224	*	229	*
225	*/	230	*/
226	void clock(void)	231	void clock(void)
227	{	232	{
228	timeout_t *h;	233	timeout_t *h;
229	timeout_handler_t f;	234	timeout_handler_t f;
230	void *arg;	235	void *arg;
231	count_t missed_clock_ticks = CPU->missed_clock_ticks;	236	count_t missed_clock_ticks = CPU->missed_clock_ticks;
232	uint64_t *i = &(CPU->timeout_active_tree.base);	237	uint64_t i = CPU->timeout_active_tree.base;
233	uint64_t absolute_clock_ticks = *i + missed_clock_ticks;	238	uint64_t last_clock_tick = i + missed_clock_ticks;
234	extavltree_node_t *expnode;	239	extavltree_node_t *expnode;
-		240	//ipl_t ipl;
235		241
236	/*	242	/*
237	* To avoid lock ordering problems,	243	* To avoid lock ordering problems,
238	* run all expired timeouts as you visit them.	244	* run all expired timeouts as you visit them.
239	*/	245	*/
240		246
241	for (; i <= absolute_clock_ticks; (i)++) {	247	for (; i <= last_clock_tick; i++) {
242	/*	-
243	* Basetime is encreased by missed clock ticks + 1 !!	-
244	*/	-
245		-
246	clock_update_counters();	248	clock_update_counters();
247	spinlock_lock(&CPU->timeoutlock);	249	spinlock_lock(&CPU->timeoutlock);
248		250
249	/*	251	/*
250	* Check whether first timeout in list time out. If so perform callback function and try	252	* Check whether first timeout in list time out. If so perform callback function and try
251	* next timeout (more timeouts can have same timeout).	253	* next timeout (more timeouts can have same timeout).
252	*/	254	*/
253	while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {	255	while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {
254	h = extavltree_get_instance(expnode,timeout_t,node);	256	h = extavltree_get_instance(expnode,timeout_t,node);
255	spinlock_lock(&h->lock);	257	spinlock_lock(&h->lock);
256	if (expnode->key != *i) {	258	if (expnode->key != i) {
-		259	/*
-		260	* Base is increased every for cycle.
-		261	*/
-		262	(CPU->timeout_active_tree.base)++;
257	spinlock_unlock(&h->lock);	263	spinlock_unlock(&h->lock);
258	break;	264	break;
259	}	265	}
260		266
261	/*	267	/*
262	* Delete first node in the list and repair tree structure in	268	* Delete first node in the list and repair tree structure in
263	* constant time.	269	* constant time.
264	*/	270	*/
265	extavltree_delete_min(&CPU->timeout_active_tree);	271	extavltree_delete_min(&CPU->timeout_active_tree);
266		272
267	f = h->handler;	273	f = h->handler;
268	arg = h->arg;	274	arg = h->arg;
269	timeout_reinitialize(h);	275	timeout_reinitialize(h);
270	spinlock_unlock(&h->lock);	276	spinlock_unlock(&h->lock);
271	spinlock_unlock(&CPU->timeoutlock);	277	spinlock_unlock(&CPU->timeoutlock);
272		278
273	f(arg);	279	f(arg);
274		280
275	spinlock_lock(&CPU->timeoutlock);	281	spinlock_lock(&CPU->timeoutlock);
276	}	282	}
277	spinlock_unlock(&CPU->timeoutlock);	283	spinlock_unlock(&CPU->timeoutlock);
278	}	284	}
279		285
280	CPU->missed_clock_ticks = 0;	286	CPU->missed_clock_ticks = 0;
281		287
282	/*	288	/*
283	* Do CPU usage accounting and find out whether to preempt THREAD.	289	* Do CPU usage accounting and find out whether to preempt THREAD.
284	*/	290	*/
285	if (THREAD) {	291	if (THREAD) {
286	uint64_t ticks;	292	uint64_t ticks;
287		293
288	spinlock_lock(&CPU->lock);	294	spinlock_lock(&CPU->lock);
289	CPU->needs_relink += 1 + missed_clock_ticks;	295	CPU->needs_relink += 1 + missed_clock_ticks;
290	spinlock_unlock(&CPU->lock);	296	spinlock_unlock(&CPU->lock);
291		297
292	spinlock_lock(&THREAD->lock);	298	spinlock_lock(&THREAD->lock);
293	if ((ticks = THREAD->ticks)) {	299	if ((ticks = THREAD->ticks)) {
294	if (ticks >= 1 + missed_clock_ticks)	300	if (ticks >= 1 + missed_clock_ticks)
295	THREAD->ticks -= 1 + missed_clock_ticks;	301	THREAD->ticks -= 1 + missed_clock_ticks;
296	else	302	else
297	THREAD->ticks = 0;	303	THREAD->ticks = 0;
298	}	304	}
299	spinlock_unlock(&THREAD->lock);	305	spinlock_unlock(&THREAD->lock);
300		306
301	if (!ticks && !PREEMPTION_DISABLED) {	307	if (!ticks && !PREEMPTION_DISABLED) {
302	scheduler();	308	scheduler();
303	}	309	}
304	}	310	}
305	}	311	}
306		312
307	#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE	313	#elif defined CONFIG_TIMEOUT_EXTAVLREL_TREE
308		314
309	/** Clock routine	315	/** Clock routine
310	*	316	*
311	* Clock routine executed from clock interrupt handler	317	* Clock routine executed from clock interrupt handler
312	* (assuming interrupts_disable()'d). Runs expired timeouts	318	* (assuming interrupts_disable()'d). Runs expired timeouts
313	* and preemptive scheduling.	319	* and preemptive scheduling.
314	*	320	*
315	*/	321	*/
316	void clock(void)	322	void clock(void)
317	{	323	{
318	extavlreltree_node_t *expnode;	324	extavlreltree_node_t *expnode;
319	timeout_t *h;	325	timeout_t *h;
320	timeout_handler_t f;	326	timeout_handler_t f;
321	void *arg;	327	void *arg;
322	count_t missed_clock_ticks = CPU->missed_clock_ticks;	328	count_t missed_clock_ticks = CPU->missed_clock_ticks;
323	int i;	329	int i;
324		330
325	/*	331	/*
326	* To avoid lock ordering problems,	332	* To avoid lock ordering problems,
327	* run all expired timeouts as you visit them.	333	* run all expired timeouts as you visit them.
328	*/	334	*/
329	for (i = 0; i <= missed_clock_ticks; i++) {	335	for (i = 0; i <= missed_clock_ticks; i++) {
330	clock_update_counters();	336	clock_update_counters();
331	spinlock_lock(&CPU->timeoutlock);	337	spinlock_lock(&CPU->timeoutlock);
332		338
333	/*	339	/*
334	* Check whether first timeout in list time out. If so perform callback function and try	340	* Check whether first timeout in list time out. If so perform callback function and try
335	* next timeout (more timeouts can have same timeout).	341	* next timeout (more timeouts can have same timeout).
336	*/	342	*/
337	while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {	343	while ((expnode = CPU->timeout_active_tree.head.next) != &(CPU->timeout_active_tree.head)) {
338	h = extavlreltree_get_instance(expnode,timeout_t,node);	344	h = extavlreltree_get_instance(expnode,timeout_t,node);
339	spinlock_lock(&h->lock);	345	spinlock_lock(&h->lock);
340	if (expnode->key != 0) {	346	if (expnode->key != 0) {
341	expnode->key--;	347	expnode->key--;
342	spinlock_unlock(&h->lock);	348	spinlock_unlock(&h->lock);
343	break;	349	break;
344	}	350	}
345		351
346	/*	352	/*
347	* Delete first node in the list and repair tree structure in	353	* Delete first node in the list and repair tree structure in
348	* constant time. Be careful of expnode's key, it must be 0!	354	* constant time. Be careful of expnode's key, it must be 0!
349	*/	355	*/
350	extavlreltree_delete_min(&CPU->timeout_active_tree);	356	extavlreltree_delete_min(&CPU->timeout_active_tree);
351		357
352	f = h->handler;	358	f = h->handler;
353	arg = h->arg;	359	arg = h->arg;
354	timeout_reinitialize(h);	360	timeout_reinitialize(h);
355	spinlock_unlock(&h->lock);	361	spinlock_unlock(&h->lock);
356	spinlock_unlock(&CPU->timeoutlock);	362	spinlock_unlock(&CPU->timeoutlock);
357		363
358	f(arg);	364	f(arg);
359		365
360	spinlock_lock(&CPU->timeoutlock);	366	spinlock_lock(&CPU->timeoutlock);
361	}	367	}
362	spinlock_unlock(&CPU->timeoutlock);	368	spinlock_unlock(&CPU->timeoutlock);
363	}	369	}
364	CPU->missed_clock_ticks = 0;	370	CPU->missed_clock_ticks = 0;
365		371
366	/*	372	/*
367	* Do CPU usage accounting and find out whether to preempt THREAD.	373	* Do CPU usage accounting and find out whether to preempt THREAD.
368	*/	374	*/
369		375
370	if (THREAD) {	376	if (THREAD) {
371	uint64_t ticks;	377	uint64_t ticks;
372		378
373	spinlock_lock(&CPU->lock);	379	spinlock_lock(&CPU->lock);
374	CPU->needs_relink += 1 + missed_clock_ticks;	380	CPU->needs_relink += 1 + missed_clock_ticks;
375	spinlock_unlock(&CPU->lock);	381	spinlock_unlock(&CPU->lock);
376		382
377	spinlock_lock(&THREAD->lock);	383	spinlock_lock(&THREAD->lock);
378	if ((ticks = THREAD->ticks)) {	384	if ((ticks = THREAD->ticks)) {
379	if (ticks >= 1 + missed_clock_ticks)	385	if (ticks >= 1 + missed_clock_ticks)
380	THREAD->ticks -= 1 + missed_clock_ticks;	386	THREAD->ticks -= 1 + missed_clock_ticks;
381	else	387	else
382	THREAD->ticks = 0;	388	THREAD->ticks = 0;
383	}	389	}
384	spinlock_unlock(&THREAD->lock);	390	spinlock_unlock(&THREAD->lock);
385		391
386	if (!ticks && !PREEMPTION_DISABLED) {	392	if (!ticks && !PREEMPTION_DISABLED) {
387	scheduler();	393	scheduler();
388	}	394	}
389	}	395	}
390	}	396	}
391		397
392		398
393		399
394	#else	400	#else
395		401
396		402
397	/** Clock routine	403	/** Clock routine
398	*	404	*
399	* Clock routine executed from clock interrupt handler	405	* Clock routine executed from clock interrupt handler
400	* (assuming interrupts_disable()'d). Runs expired timeouts	406	* (assuming interrupts_disable()'d). Runs expired timeouts
401	* and preemptive scheduling.	407	* and preemptive scheduling.
402	*	408	*
403	*/	409	*/
404	void clock(void)	410	void clock(void)
405	{	411	{
406	link_t *l;	412	link_t *l;
407	timeout_t *h;	413	timeout_t *h;
408	timeout_handler_t f;	414	timeout_handler_t f;
409	void *arg;	415	void *arg;
410	count_t missed_clock_ticks = CPU->missed_clock_ticks;	416	count_t missed_clock_ticks = CPU->missed_clock_ticks;
411	int i;	417	int i;
412		418
413	/*	419	/*
414	* To avoid lock ordering problems,	420	* To avoid lock ordering problems,
415	* run all expired timeouts as you visit them.	421	* run all expired timeouts as you visit them.
416	*/	422	*/
417	for (i = 0; i <= missed_clock_ticks; i++) {	423	for (i = 0; i <= missed_clock_ticks; i++) {
418	clock_update_counters();	424	clock_update_counters();
419	spinlock_lock(&CPU->timeoutlock);	425	spinlock_lock(&CPU->timeoutlock);
420	while ((l = CPU->timeout_active_head.next) != &CPU->timeout_active_head) {	426	while ((l = CPU->timeout_active_head.next) != &CPU->timeout_active_head) {
421	h = list_get_instance(l, timeout_t, link);	427	h = list_get_instance(l, timeout_t, link);
422	spinlock_lock(&h->lock);	428	spinlock_lock(&h->lock);
423	if (h->ticks-- != 0) {	429	if (h->ticks-- != 0) {
424	spinlock_unlock(&h->lock);	430	spinlock_unlock(&h->lock);
425	break;	431	break;
426	}	432	}
427	list_remove(l);	433	list_remove(l);
428	f = h->handler;	434	f = h->handler;
429	arg = h->arg;	435	arg = h->arg;
430	timeout_reinitialize(h);	436	timeout_reinitialize(h);
431	spinlock_unlock(&h->lock);	437	spinlock_unlock(&h->lock);
432	spinlock_unlock(&CPU->timeoutlock);	438	spinlock_unlock(&CPU->timeoutlock);
433		439
434	f(arg);	440	f(arg);
435		441
436	spinlock_lock(&CPU->timeoutlock);	442	spinlock_lock(&CPU->timeoutlock);
437	}	443	}
438	spinlock_unlock(&CPU->timeoutlock);	444	spinlock_unlock(&CPU->timeoutlock);
439	}	445	}
440	CPU->missed_clock_ticks = 0;	446	CPU->missed_clock_ticks = 0;
441		447
442	/*	448	/*
443	* Do CPU usage accounting and find out whether to preempt THREAD.	449	* Do CPU usage accounting and find out whether to preempt THREAD.
444	*/	450	*/
445		451
446	if (THREAD) {	452	if (THREAD) {
447	uint64_t ticks;	453	uint64_t ticks;
448		454
449	spinlock_lock(&CPU->lock);	455	spinlock_lock(&CPU->lock);
450	CPU->needs_relink += 1 + missed_clock_ticks;	456	CPU->needs_relink += 1 + missed_clock_ticks;
451	spinlock_unlock(&CPU->lock);	457	spinlock_unlock(&CPU->lock);
452		458
453	spinlock_lock(&THREAD->lock);	459	spinlock_lock(&THREAD->lock);
454	if ((ticks = THREAD->ticks)) {	460	if ((ticks = THREAD->ticks)) {
455	if (ticks >= 1 + missed_clock_ticks)	461	if (ticks >= 1 + missed_clock_ticks)
456	THREAD->ticks -= 1 + missed_clock_ticks;	462	THREAD->ticks -= 1 + missed_clock_ticks;
457	else	463	else
458	THREAD->ticks = 0;	464	THREAD->ticks = 0;
459	}	465	}
460	spinlock_unlock(&THREAD->lock);	466	spinlock_unlock(&THREAD->lock);
461		467
462	if (!ticks && !PREEMPTION_DISABLED) {	468	if (!ticks && !PREEMPTION_DISABLED) {
463	scheduler();	469	scheduler();
464	}	470	}
465	}	471	}
466	}	472	}
467		473
468	#endif	474	#endif
469	/** @}	475	/** @}
470	*/	476	*/
471		477

Subversion Repositories HelenOS

(root)/branches/rcu/kernel/generic/src/time/clock.c – Rev 2421 → 2450