← Back to branch summary

~ubuntu-branches/ubuntu/utopic/xen/utopic

« back to all changes in this revision

Viewing changes to extras/mini-os/sched.c

  • Committer: Bazaar Package Importer
  • Author(s): Bastian Blank
  • Date: 2010-05-06 15:47:38 UTC
  • mto: (1.3.1) (15.1.1 sid) (4.1.1 experimental)
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20100506154738-agoz0rlafrh1fnq7
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
extras/mini-os/sched.c
 
1
/* 
 
2
 ****************************************************************************
 
3
 * (C) 2005 - Grzegorz Milos - Intel Research Cambridge
 
4
 ****************************************************************************
 
5
 *
 
6
 *        File: sched.c
 
7
 *      Author: Grzegorz Milos
 
8
 *     Changes: Robert Kaiser
 
9
 *              
 
10
 *        Date: Aug 2005
 
11
 * 
 
12
 * Environment: Xen Minimal OS
 
13
 * Description: simple scheduler for Mini-Os
 
14
 *
 
15
 * The scheduler is non-preemptive (cooperative), and schedules according 
 
16
 * to Round Robin algorithm.
 
17
 *
 
18
 ****************************************************************************
 
19
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 
20
 * of this software and associated documentation files (the "Software"), to
 
21
 * deal in the Software without restriction, including without limitation the
 
22
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
 
23
 * sell copies of the Software, and to permit persons to whom the Software is
 
24
 * furnished to do so, subject to the following conditions:
 
25
 * 
 
26
 * The above copyright notice and this permission notice shall be included in
 
27
 * all copies or substantial portions of the Software.
 
28
 * 
 
29
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 
 
30
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 
 
31
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 
 
32
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 
 
33
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 
 
34
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
 
35
 * DEALINGS IN THE SOFTWARE.
 
36
 */
 
37
 
 
38
#include <mini-os/os.h>
 
39
#include <mini-os/hypervisor.h>
 
40
#include <mini-os/time.h>
 
41
#include <mini-os/mm.h>
 
42
#include <mini-os/types.h>
 
43
#include <mini-os/lib.h>
 
44
#include <mini-os/xmalloc.h>
 
45
#include <mini-os/list.h>
 
46
#include <mini-os/sched.h>
 
47
#include <mini-os/semaphore.h>
 
48
 
 
49
 
 
50
#ifdef SCHED_DEBUG
 
51
#define DEBUG(_f, _a...) \
 
52
    printk("MINI_OS(file=sched.c, line=%d) " _f "\n", __LINE__, ## _a)
 
53
#else
 
54
#define DEBUG(_f, _a...)    ((void)0)
 
55
#endif
 
56
 
 
57
struct thread *idle_thread = NULL;
 
58
MINIOS_LIST_HEAD(exited_threads);
 
59
static int threads_started;
 
60
 
 
61
struct thread *main_thread;
 
62
 
 
63
void inline print_runqueue(void)
 
64
{
 
65
    struct minios_list_head *it;
 
66
    struct thread *th;
 
67
    minios_list_for_each(it, &idle_thread->thread_list)
 
68
    {
 
69
        th = minios_list_entry(it, struct thread, thread_list);
 
70
        printk("   Thread \"%s\", runnable=%d\n", th->name, is_runnable(th));
 
71
    }
 
72
    printk("\n");
 
73
}
 
74
 
 
75
void schedule(void)
 
76
{
 
77
    struct thread *prev, *next, *thread;
 
78
    struct minios_list_head *iterator, *next_iterator;
 
79
    unsigned long flags;
 
80
 
 
81
    prev = current;
 
82
    local_irq_save(flags); 
 
83
 
 
84
    if (in_callback) {
 
85
        printk("Must not call schedule() from a callback\n");
 
86
        BUG();
 
87
    }
 
88
    if (flags) {
 
89
        printk("Must not call schedule() with IRQs disabled\n");
 
90
        BUG();
 
91
    }
 
92
 
 
93
    do {
 
94
        /* Examine all threads.
 
95
           Find a runnable thread, but also wake up expired ones and find the
 
96
           time when the next timeout expires, else use 10 seconds. */
 
97
        s_time_t now = NOW();
 
98
        s_time_t min_wakeup_time = now + SECONDS(10);
 
99
        next = NULL;   
 
100
        minios_list_for_each_safe(iterator, next_iterator, &idle_thread->thread_list)
 
101
        {
 
102
            thread = minios_list_entry(iterator, struct thread, thread_list);
 
103
            if (!is_runnable(thread) && thread->wakeup_time != 0LL)
 
104
            {
 
105
                if (thread->wakeup_time <= now)
 
106
                    wake(thread);
 
107
                else if (thread->wakeup_time < min_wakeup_time)
 
108
                    min_wakeup_time = thread->wakeup_time;
 
109
            }
 
110
            if(is_runnable(thread)) 
 
111
            {
 
112
                next = thread;
 
113
                /* Put this thread on the end of the list */
 
114
                minios_list_del(&thread->thread_list);
 
115
                minios_list_add_tail(&thread->thread_list, &idle_thread->thread_list);
 
116
                break;
 
117
            }
 
118
        }
 
119
        if (next)
 
120
            break;
 
121
        /* block until the next timeout expires, or for 10 secs, whichever comes first */
 
122
        block_domain(min_wakeup_time);
 
123
        /* handle pending events if any */
 
124
        force_evtchn_callback();
 
125
    } while(1);
 
126
    local_irq_restore(flags);
 
127
    /* Interrupting the switch is equivalent to having the next thread
 
128
       inturrupted at the return instruction. And therefore at safe point. */
 
129
    if(prev != next) switch_threads(prev, next);
 
130
 
 
131
    minios_list_for_each_safe(iterator, next_iterator, &exited_threads)
 
132
    {
 
133
        thread = minios_list_entry(iterator, struct thread, thread_list);
 
134
        if(thread != prev)
 
135
        {
 
136
            minios_list_del(&thread->thread_list);
 
137
            free_pages(thread->stack, STACK_SIZE_PAGE_ORDER);
 
138
            xfree(thread);
 
139
        }
 
140
    }
 
141
}
 
142
 
 
143
struct thread* create_thread(char *name, void (*function)(void *), void *data)
 
144
{
 
145
    struct thread *thread;
 
146
    unsigned long flags;
 
147
    /* Call architecture specific setup. */
 
148
    thread = arch_create_thread(name, function, data);
 
149
    /* Not runable, not exited, not sleeping */
 
150
    thread->flags = 0;
 
151
    thread->wakeup_time = 0LL;
 
152
#ifdef HAVE_LIBC
 
153
    _REENT_INIT_PTR((&thread->reent))
 
154
#endif
 
155
    set_runnable(thread);
 
156
    local_irq_save(flags);
 
157
    if(idle_thread != NULL) {
 
158
        minios_list_add_tail(&thread->thread_list, &idle_thread->thread_list); 
 
159
    } else if(function != idle_thread_fn)
 
160
    {
 
161
        printk("BUG: Not allowed to create thread before initialising scheduler.\n");
 
162
        BUG();
 
163
    }
 
164
    local_irq_restore(flags);
 
165
    return thread;
 
166
}
 
167
 
 
168
#ifdef HAVE_LIBC
 
169
static struct _reent callback_reent;
 
170
struct _reent *__getreent(void)
 
171
{
 
172
    struct _reent *_reent;
 
173
 
 
174
    if (!threads_started)
 
175
        _reent = _impure_ptr;
 
176
    else if (in_callback)
 
177
        _reent = &callback_reent;
 
178
    else
 
179
        _reent = &get_current()->reent;
 
180
 
 
181
#ifndef NDEBUG
 
182
#if defined(__x86_64__) || defined(__x86__)
 
183
    {
 
184
#ifdef __x86_64__
 
185
        register unsigned long sp asm ("rsp");
 
186
#else
 
187
        register unsigned long sp asm ("esp");
 
188
#endif
 
189
        if ((sp & (STACK_SIZE-1)) < STACK_SIZE / 16) {
 
190
            static int overflowing;
 
191
            if (!overflowing) {
 
192
                overflowing = 1;
 
193
                printk("stack overflow\n");
 
194
                BUG();
 
195
            }
 
196
        }
 
197
    }
 
198
#endif
 
199
#endif
 
200
    return _reent;
 
201
}
 
202
#endif
 
203
 
 
204
void exit_thread(void)
 
205
{
 
206
    unsigned long flags;
 
207
    struct thread *thread = current;
 
208
    printk("Thread \"%s\" exited.\n", thread->name);
 
209
    local_irq_save(flags);
 
210
    /* Remove from the thread list */
 
211
    minios_list_del(&thread->thread_list);
 
212
    clear_runnable(thread);
 
213
    /* Put onto exited list */
 
214
    minios_list_add(&thread->thread_list, &exited_threads);
 
215
    local_irq_restore(flags);
 
216
    /* Schedule will free the resources */
 
217
    while(1)
 
218
    {
 
219
        schedule();
 
220
        printk("schedule() returned!  Trying again\n");
 
221
    }
 
222
}
 
223
 
 
224
void block(struct thread *thread)
 
225
{
 
226
    thread->wakeup_time = 0LL;
 
227
    clear_runnable(thread);
 
228
}
 
229
 
 
230
void msleep(uint32_t millisecs)
 
231
{
 
232
    struct thread *thread = get_current();
 
233
    thread->wakeup_time = NOW()  + MILLISECS(millisecs);
 
234
    clear_runnable(thread);
 
235
    schedule();
 
236
}
 
237
 
 
238
void wake(struct thread *thread)
 
239
{
 
240
    thread->wakeup_time = 0LL;
 
241
    set_runnable(thread);
 
242
}
 
243
 
 
244
void idle_thread_fn(void *unused)
 
245
{
 
246
    threads_started = 1;
 
247
    while (1) {
 
248
        block(current);
 
249
        schedule();
 
250
    }
 
251
}
 
252
 
 
253
DECLARE_MUTEX(mutex);
 
254
 
 
255
void th_f1(void *data)
 
256
{
 
257
    struct timeval tv1, tv2;
 
258
 
 
259
    for(;;)
 
260
    {
 
261
        down(&mutex);
 
262
        printk("Thread \"%s\" got semaphore, runnable %d\n", current->name, is_runnable(current));
 
263
        schedule();
 
264
        printk("Thread \"%s\" releases the semaphore\n", current->name);
 
265
        up(&mutex);
 
266
        
 
267
        
 
268
        gettimeofday(&tv1, NULL);
 
269
        for(;;)
 
270
        {
 
271
            gettimeofday(&tv2, NULL);
 
272
            if(tv2.tv_sec - tv1.tv_sec > 2) break;
 
273
        }
 
274
                
 
275
        
 
276
        schedule(); 
 
277
    }
 
278
}
 
279
 
 
280
void th_f2(void *data)
 
281
{
 
282
    for(;;)
 
283
    {
 
284
        printk("Thread OTHER executing, data 0x%lx\n", data);
 
285
        schedule();
 
286
    }
 
287
}
 
288
 
 
289
 
 
290
 
 
291
void init_sched(void)
 
292
{
 
293
    printk("Initialising scheduler\n");
 
294
 
 
295
#ifdef HAVE_LIBC
 
296
    _REENT_INIT_PTR((&callback_reent))
 
297
#endif
 
298
    idle_thread = create_thread("Idle", idle_thread_fn, NULL);
 
299
    MINIOS_INIT_LIST_HEAD(&idle_thread->thread_list);
 
300
}
 
301