Subversion Repositories HelenOS

Rev

Rev 1787 | Rev 1882 | Go to most recent revision | Only display areas with differences | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1787 Rev 1854
1
/*
1
/*
2
 * Copyright (C) 2001-2004 Jakub Jermar
2
 * Copyright (C) 2001-2004 Jakub Jermar
3
 * All rights reserved.
3
 * All rights reserved.
4
 *
4
 *
5
 * Redistribution and use in source and binary forms, with or without
5
 * Redistribution and use in source and binary forms, with or without
6
 * modification, are permitted provided that the following conditions
6
 * modification, are permitted provided that the following conditions
7
 * are met:
7
 * are met:
8
 *
8
 *
9
 * - Redistributions of source code must retain the above copyright
9
 * - Redistributions of source code must retain the above copyright
10
 *   notice, this list of conditions and the following disclaimer.
10
 *   notice, this list of conditions and the following disclaimer.
11
 * - Redistributions in binary form must reproduce the above copyright
11
 * - Redistributions in binary form must reproduce the above copyright
12
 *   notice, this list of conditions and the following disclaimer in the
12
 *   notice, this list of conditions and the following disclaimer in the
13
 *   documentation and/or other materials provided with the distribution.
13
 *   documentation and/or other materials provided with the distribution.
14
 * - The name of the author may not be used to endorse or promote products
14
 * - The name of the author may not be used to endorse or promote products
15
 *   derived from this software without specific prior written permission.
15
 *   derived from this software without specific prior written permission.
16
 *
16
 *
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
17
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
18
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
19
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
20
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
21
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
22
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
23
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
25
 * (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.
26
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
 */
27
 */
28
 
28
 
29
/** @addtogroup genericproc
29
/** @addtogroup genericproc
30
 * @{
30
 * @{
31
 */
31
 */
32
 
32
 
33
/**
33
/**
34
 * @file
34
 * @file
35
 * @brief   Scheduler and load balancing.
35
 * @brief   Scheduler and load balancing.
36
 *
36
 *
37
 * This file contains the scheduler and kcpulb kernel thread which
37
 * This file contains the scheduler and kcpulb kernel thread which
38
 * performs load-balancing of per-CPU run queues.
38
 * performs load-balancing of per-CPU run queues.
39
 */
39
 */
40
 
40
 
41
#include <proc/scheduler.h>
41
#include <proc/scheduler.h>
42
#include <proc/thread.h>
42
#include <proc/thread.h>
43
#include <proc/task.h>
43
#include <proc/task.h>
44
#include <mm/frame.h>
44
#include <mm/frame.h>
45
#include <mm/page.h>
45
#include <mm/page.h>
46
#include <mm/as.h>
46
#include <mm/as.h>
47
#include <time/delay.h>
47
#include <time/delay.h>
48
#include <arch/asm.h>
48
#include <arch/asm.h>
49
#include <arch/faddr.h>
49
#include <arch/faddr.h>
50
#include <atomic.h>
50
#include <atomic.h>
51
#include <synch/spinlock.h>
51
#include <synch/spinlock.h>
52
#include <config.h>
52
#include <config.h>
53
#include <context.h>
53
#include <context.h>
54
#include <func.h>
54
#include <func.h>
55
#include <arch.h>
55
#include <arch.h>
56
#include <adt/list.h>
56
#include <adt/list.h>
57
#include <panic.h>
57
#include <panic.h>
58
#include <typedefs.h>
58
#include <typedefs.h>
59
#include <cpu.h>
59
#include <cpu.h>
60
#include <print.h>
60
#include <print.h>
61
#include <debug.h>
61
#include <debug.h>
62
 
62
 
63
static void before_task_runs(void);
63
static void before_task_runs(void);
64
static void before_thread_runs(void);
64
static void before_thread_runs(void);
65
static void after_thread_ran(void);
65
static void after_thread_ran(void);
66
static void scheduler_separated_stack(void);
66
static void scheduler_separated_stack(void);
67
 
67
 
68
atomic_t nrdy;  /**< Number of ready threads in the system. */
68
atomic_t nrdy;  /**< Number of ready threads in the system. */
69
 
69
 
70
/** Carry out actions before new task runs. */
70
/** Carry out actions before new task runs. */
71
void before_task_runs(void)
71
void before_task_runs(void)
72
{
72
{
73
    before_task_runs_arch();
73
    before_task_runs_arch();
74
}
74
}
75
 
75
 
76
/** Take actions before new thread runs.
76
/** Take actions before new thread runs.
77
 *
77
 *
78
 * Perform actions that need to be
78
 * Perform actions that need to be
79
 * taken before the newly selected
79
 * taken before the newly selected
80
 * tread is passed control.
80
 * tread is passed control.
81
 *
81
 *
82
 * THREAD->lock is locked on entry
82
 * THREAD->lock is locked on entry
83
 *
83
 *
84
 */
84
 */
85
void before_thread_runs(void)
85
void before_thread_runs(void)
86
{
86
{
87
    before_thread_runs_arch();
87
    before_thread_runs_arch();
88
#ifdef CONFIG_FPU_LAZY
88
#ifdef CONFIG_FPU_LAZY
89
    if(THREAD==CPU->fpu_owner)
89
    if(THREAD==CPU->fpu_owner)
90
        fpu_enable();
90
        fpu_enable();
91
    else
91
    else
92
        fpu_disable();
92
        fpu_disable();
93
#else
93
#else
94
    fpu_enable();
94
    fpu_enable();
95
    if (THREAD->fpu_context_exists)
95
    if (THREAD->fpu_context_exists)
96
        fpu_context_restore(THREAD->saved_fpu_context);
96
        fpu_context_restore(THREAD->saved_fpu_context);
97
    else {
97
    else {
98
        fpu_init();
98
        fpu_init();
99
        THREAD->fpu_context_exists=1;
99
        THREAD->fpu_context_exists=1;
100
    }
100
    }
101
#endif
101
#endif
102
}
102
}
103
 
103
 
104
/** Take actions after THREAD had run.
104
/** Take actions after THREAD had run.
105
 *
105
 *
106
 * Perform actions that need to be
106
 * Perform actions that need to be
107
 * taken after the running thread
107
 * taken after the running thread
108
 * had been preempted by the scheduler.
108
 * had been preempted by the scheduler.
109
 *
109
 *
110
 * THREAD->lock is locked on entry
110
 * THREAD->lock is locked on entry
111
 *
111
 *
112
 */
112
 */
113
void after_thread_ran(void)
113
void after_thread_ran(void)
114
{
114
{
115
    after_thread_ran_arch();
115
    after_thread_ran_arch();
116
}
116
}
117
 
117
 
118
#ifdef CONFIG_FPU_LAZY
118
#ifdef CONFIG_FPU_LAZY
119
void scheduler_fpu_lazy_request(void)
119
void scheduler_fpu_lazy_request(void)
120
{
120
{
121
restart:
121
restart:
122
    fpu_enable();
122
    fpu_enable();
123
    spinlock_lock(&CPU->lock);
123
    spinlock_lock(&CPU->lock);
124
 
124
 
125
    /* Save old context */
125
    /* Save old context */
126
    if (CPU->fpu_owner != NULL) {  
126
    if (CPU->fpu_owner != NULL) {  
127
        spinlock_lock(&CPU->fpu_owner->lock);
127
        spinlock_lock(&CPU->fpu_owner->lock);
128
        fpu_context_save(CPU->fpu_owner->saved_fpu_context);
128
        fpu_context_save(CPU->fpu_owner->saved_fpu_context);
129
        /* don't prevent migration */
129
        /* don't prevent migration */
130
        CPU->fpu_owner->fpu_context_engaged=0;
130
        CPU->fpu_owner->fpu_context_engaged=0;
131
        spinlock_unlock(&CPU->fpu_owner->lock);
131
        spinlock_unlock(&CPU->fpu_owner->lock);
132
        CPU->fpu_owner = NULL;
132
        CPU->fpu_owner = NULL;
133
    }
133
    }
134
 
134
 
135
    spinlock_lock(&THREAD->lock);
135
    spinlock_lock(&THREAD->lock);
136
    if (THREAD->fpu_context_exists) {
136
    if (THREAD->fpu_context_exists) {
137
        fpu_context_restore(THREAD->saved_fpu_context);
137
        fpu_context_restore(THREAD->saved_fpu_context);
138
    } else {
138
    } else {
139
        /* Allocate FPU context */
139
        /* Allocate FPU context */
140
        if (!THREAD->saved_fpu_context) {
140
        if (!THREAD->saved_fpu_context) {
141
            /* Might sleep */
141
            /* Might sleep */
142
            spinlock_unlock(&THREAD->lock);
142
            spinlock_unlock(&THREAD->lock);
143
            spinlock_unlock(&CPU->lock);
143
            spinlock_unlock(&CPU->lock);
144
            THREAD->saved_fpu_context = slab_alloc(fpu_context_slab,
144
            THREAD->saved_fpu_context = slab_alloc(fpu_context_slab, 0);
145
                                   0);
-
 
146
            /* We may have switched CPUs during slab_alloc */
145
            /* We may have switched CPUs during slab_alloc */
147
            goto restart;
146
            goto restart;
148
        }
147
        }
149
        fpu_init();
148
        fpu_init();
150
        THREAD->fpu_context_exists=1;
149
        THREAD->fpu_context_exists=1;
151
    }
150
    }
152
    CPU->fpu_owner=THREAD;
151
    CPU->fpu_owner=THREAD;
153
    THREAD->fpu_context_engaged = 1;
152
    THREAD->fpu_context_engaged = 1;
154
    spinlock_unlock(&THREAD->lock);
153
    spinlock_unlock(&THREAD->lock);
155
 
154
 
156
    spinlock_unlock(&CPU->lock);
155
    spinlock_unlock(&CPU->lock);
157
}
156
}
158
#endif
157
#endif
159
 
158
 
160
/** Initialize scheduler
159
/** Initialize scheduler
161
 *
160
 *
162
 * Initialize kernel scheduler.
161
 * Initialize kernel scheduler.
163
 *
162
 *
164
 */
163
 */
165
void scheduler_init(void)
164
void scheduler_init(void)
166
{
165
{
167
}
166
}
168
 
167
 
169
/** Get thread to be scheduled
168
/** Get thread to be scheduled
170
 *
169
 *
171
 * Get the optimal thread to be scheduled
170
 * Get the optimal thread to be scheduled
172
 * according to thread accounting and scheduler
171
 * according to thread accounting and scheduler
173
 * policy.
172
 * policy.
174
 *
173
 *
175
 * @return Thread to be scheduled.
174
 * @return Thread to be scheduled.
176
 *
175
 *
177
 */
176
 */
178
static thread_t *find_best_thread(void)
177
static thread_t *find_best_thread(void)
179
{
178
{
180
    thread_t *t;
179
    thread_t *t;
181
    runq_t *r;
180
    runq_t *r;
182
    int i;
181
    int i;
183
 
182
 
184
    ASSERT(CPU != NULL);
183
    ASSERT(CPU != NULL);
185
 
184
 
186
loop:
185
loop:
187
    interrupts_enable();
186
    interrupts_enable();
188
   
187
   
189
    if (atomic_get(&CPU->nrdy) == 0) {
188
    if (atomic_get(&CPU->nrdy) == 0) {
190
        /*
189
        /*
191
         * For there was nothing to run, the CPU goes to sleep
190
         * For there was nothing to run, the CPU goes to sleep
192
         * until a hardware interrupt or an IPI comes.
191
         * until a hardware interrupt or an IPI comes.
193
         * This improves energy saving and hyperthreading.
192
         * This improves energy saving and hyperthreading.
194
         */
193
         */
195
 
194
 
196
        /*
195
        /*
197
         * An interrupt might occur right now and wake up a thread.
196
         * An interrupt might occur right now and wake up a thread.
198
         * In such case, the CPU will continue to go to sleep
197
         * In such case, the CPU will continue to go to sleep
199
         * even though there is a runnable thread.
198
         * even though there is a runnable thread.
200
         */
199
         */
201
 
200
 
202
         cpu_sleep();
201
         cpu_sleep();
203
         goto loop;
202
         goto loop;
204
    }
203
    }
205
 
204
 
206
    interrupts_disable();
205
    interrupts_disable();
207
   
206
   
208
    for (i = 0; i<RQ_COUNT; i++) {
207
    for (i = 0; i<RQ_COUNT; i++) {
209
        r = &CPU->rq[i];
208
        r = &CPU->rq[i];
210
        spinlock_lock(&r->lock);
209
        spinlock_lock(&r->lock);
211
        if (r->n == 0) {
210
        if (r->n == 0) {
212
            /*
211
            /*
213
             * If this queue is empty, try a lower-priority queue.
212
             * If this queue is empty, try a lower-priority queue.
214
             */
213
             */
215
            spinlock_unlock(&r->lock);
214
            spinlock_unlock(&r->lock);
216
            continue;
215
            continue;
217
        }
216
        }
218
 
217
 
219
        atomic_dec(&CPU->nrdy);
218
        atomic_dec(&CPU->nrdy);
220
        atomic_dec(&nrdy);
219
        atomic_dec(&nrdy);
221
        r->n--;
220
        r->n--;
222
 
221
 
223
        /*
222
        /*
224
         * Take the first thread from the queue.
223
         * Take the first thread from the queue.
225
         */
224
         */
226
        t = list_get_instance(r->rq_head.next, thread_t, rq_link);
225
        t = list_get_instance(r->rq_head.next, thread_t, rq_link);
227
        list_remove(&t->rq_link);
226
        list_remove(&t->rq_link);
228
 
227
 
229
        spinlock_unlock(&r->lock);
228
        spinlock_unlock(&r->lock);
230
 
229
 
231
        spinlock_lock(&t->lock);
230
        spinlock_lock(&t->lock);
232
        t->cpu = CPU;
231
        t->cpu = CPU;
233
 
232
 
234
        t->ticks = us2ticks((i+1)*10000);
233
        t->ticks = us2ticks((i+1)*10000);
235
        t->priority = i;    /* correct rq index */
234
        t->priority = i;    /* correct rq index */
236
 
235
 
237
        /*
236
        /*
238
         * Clear the X_STOLEN flag so that t can be migrated when load balancing needs emerge.
237
         * Clear the THREAD_FLAG_STOLEN flag so that t can be migrated
-
 
238
         * when load balancing needs emerge.
239
         */
239
         */
240
        t->flags &= ~X_STOLEN;
240
        t->flags &= ~THREAD_FLAG_STOLEN;
241
        spinlock_unlock(&t->lock);
241
        spinlock_unlock(&t->lock);
242
 
242
 
243
        return t;
243
        return t;
244
    }
244
    }
245
    goto loop;
245
    goto loop;
246
 
246
 
247
}
247
}
248
 
248
 
249
/** Prevent rq starvation
249
/** Prevent rq starvation
250
 *
250
 *
251
 * Prevent low priority threads from starving in rq's.
251
 * Prevent low priority threads from starving in rq's.
252
 *
252
 *
253
 * When the function decides to relink rq's, it reconnects
253
 * When the function decides to relink rq's, it reconnects
254
 * respective pointers so that in result threads with 'pri'
254
 * respective pointers so that in result threads with 'pri'
255
 * greater or equal start are moved to a higher-priority queue.
255
 * greater or equal start are moved to a higher-priority queue.
256
 *
256
 *
257
 * @param start Threshold priority.
257
 * @param start Threshold priority.
258
 *
258
 *
259
 */
259
 */
260
static void relink_rq(int start)
260
static void relink_rq(int start)
261
{
261
{
262
    link_t head;
262
    link_t head;
263
    runq_t *r;
263
    runq_t *r;
264
    int i, n;
264
    int i, n;
265
 
265
 
266
    list_initialize(&head);
266
    list_initialize(&head);
267
    spinlock_lock(&CPU->lock);
267
    spinlock_lock(&CPU->lock);
268
    if (CPU->needs_relink > NEEDS_RELINK_MAX) {
268
    if (CPU->needs_relink > NEEDS_RELINK_MAX) {
269
        for (i = start; i<RQ_COUNT-1; i++) {
269
        for (i = start; i<RQ_COUNT-1; i++) {
270
            /* remember and empty rq[i + 1] */
270
            /* remember and empty rq[i + 1] */
271
            r = &CPU->rq[i + 1];
271
            r = &CPU->rq[i + 1];
272
            spinlock_lock(&r->lock);
272
            spinlock_lock(&r->lock);
273
            list_concat(&head, &r->rq_head);
273
            list_concat(&head, &r->rq_head);
274
            n = r->n;
274
            n = r->n;
275
            r->n = 0;
275
            r->n = 0;
276
            spinlock_unlock(&r->lock);
276
            spinlock_unlock(&r->lock);
277
       
277
       
278
            /* append rq[i + 1] to rq[i] */
278
            /* append rq[i + 1] to rq[i] */
279
            r = &CPU->rq[i];
279
            r = &CPU->rq[i];
280
            spinlock_lock(&r->lock);
280
            spinlock_lock(&r->lock);
281
            list_concat(&r->rq_head, &head);
281
            list_concat(&r->rq_head, &head);
282
            r->n += n;
282
            r->n += n;
283
            spinlock_unlock(&r->lock);
283
            spinlock_unlock(&r->lock);
284
        }
284
        }
285
        CPU->needs_relink = 0;
285
        CPU->needs_relink = 0;
286
    }
286
    }
287
    spinlock_unlock(&CPU->lock);
287
    spinlock_unlock(&CPU->lock);
288
 
288
 
289
}
289
}
290
 
290
 
291
/** The scheduler
291
/** The scheduler
292
 *
292
 *
293
 * The thread scheduling procedure.
293
 * The thread scheduling procedure.
294
 * Passes control directly to
294
 * Passes control directly to
295
 * scheduler_separated_stack().
295
 * scheduler_separated_stack().
296
 *
296
 *
297
 */
297
 */
298
void scheduler(void)
298
void scheduler(void)
299
{
299
{
300
    volatile ipl_t ipl;
300
    volatile ipl_t ipl;
301
 
301
 
302
    ASSERT(CPU != NULL);
302
    ASSERT(CPU != NULL);
303
 
303
 
304
    ipl = interrupts_disable();
304
    ipl = interrupts_disable();
305
 
305
 
306
    if (atomic_get(&haltstate))
306
    if (atomic_get(&haltstate))
307
        halt();
307
        halt();
308
   
308
   
309
    if (THREAD) {
309
    if (THREAD) {
310
        spinlock_lock(&THREAD->lock);
310
        spinlock_lock(&THREAD->lock);
311
#ifndef CONFIG_FPU_LAZY
311
#ifndef CONFIG_FPU_LAZY
312
        fpu_context_save(THREAD->saved_fpu_context);
312
        fpu_context_save(THREAD->saved_fpu_context);
313
#endif
313
#endif
314
        if (!context_save(&THREAD->saved_context)) {
314
        if (!context_save(&THREAD->saved_context)) {
315
            /*
315
            /*
316
             * This is the place where threads leave scheduler();
316
             * This is the place where threads leave scheduler();
317
             */
317
             */
318
            spinlock_unlock(&THREAD->lock);
318
            spinlock_unlock(&THREAD->lock);
319
            interrupts_restore(THREAD->saved_context.ipl);
319
            interrupts_restore(THREAD->saved_context.ipl);
320
           
320
           
321
            return;
321
            return;
322
        }
322
        }
323
 
323
 
324
        /*
324
        /*
325
         * Interrupt priority level of preempted thread is recorded here
325
         * Interrupt priority level of preempted thread is recorded here
326
         * to facilitate scheduler() invocations from interrupts_disable()'d
326
         * to facilitate scheduler() invocations from interrupts_disable()'d
327
         * code (e.g. waitq_sleep_timeout()).
327
         * code (e.g. waitq_sleep_timeout()).
328
         */
328
         */
329
        THREAD->saved_context.ipl = ipl;
329
        THREAD->saved_context.ipl = ipl;
330
    }
330
    }
331
 
331
 
332
    /*
332
    /*
333
     * Through the 'THE' structure, we keep track of THREAD, TASK, CPU, VM
333
     * Through the 'THE' structure, we keep track of THREAD, TASK, CPU, VM
334
     * and preemption counter. At this point THE could be coming either
334
     * and preemption counter. At this point THE could be coming either
335
     * from THREAD's or CPU's stack.
335
     * from THREAD's or CPU's stack.
336
     */
336
     */
337
    the_copy(THE, (the_t *) CPU->stack);
337
    the_copy(THE, (the_t *) CPU->stack);
338
 
338
 
339
    /*
339
    /*
340
     * We may not keep the old stack.
340
     * We may not keep the old stack.
341
     * Reason: If we kept the old stack and got blocked, for instance, in
341
     * Reason: If we kept the old stack and got blocked, for instance, in
342
     * find_best_thread(), the old thread could get rescheduled by another
342
     * find_best_thread(), the old thread could get rescheduled by another
343
     * CPU and overwrite the part of its own stack that was also used by
343
     * CPU and overwrite the part of its own stack that was also used by
344
     * the scheduler on this CPU.
344
     * the scheduler on this CPU.
345
     *
345
     *
346
     * Moreover, we have to bypass the compiler-generated POP sequence
346
     * Moreover, we have to bypass the compiler-generated POP sequence
347
     * which is fooled by SP being set to the very top of the stack.
347
     * which is fooled by SP being set to the very top of the stack.
348
     * Therefore the scheduler() function continues in
348
     * Therefore the scheduler() function continues in
349
     * scheduler_separated_stack().
349
     * scheduler_separated_stack().
350
     */
350
     */
351
    context_save(&CPU->saved_context);
351
    context_save(&CPU->saved_context);
352
    context_set(&CPU->saved_context, FADDR(scheduler_separated_stack), (uintptr_t) CPU->stack, CPU_STACK_SIZE);
352
    context_set(&CPU->saved_context, FADDR(scheduler_separated_stack),
-
 
353
        (uintptr_t) CPU->stack, CPU_STACK_SIZE);
353
    context_restore(&CPU->saved_context);
354
    context_restore(&CPU->saved_context);
354
    /* not reached */
355
    /* not reached */
355
}
356
}
356
 
357
 
357
/** Scheduler stack switch wrapper
358
/** Scheduler stack switch wrapper
358
 *
359
 *
359
 * Second part of the scheduler() function
360
 * Second part of the scheduler() function
360
 * using new stack. Handling the actual context
361
 * using new stack. Handling the actual context
361
 * switch to a new thread.
362
 * switch to a new thread.
362
 *
363
 *
363
 * Assume THREAD->lock is held.
364
 * Assume THREAD->lock is held.
364
 */
365
 */
365
void scheduler_separated_stack(void)
366
void scheduler_separated_stack(void)
366
{
367
{
367
    int priority;
368
    int priority;
368
   
369
   
369
    ASSERT(CPU != NULL);
370
    ASSERT(CPU != NULL);
370
   
371
   
371
    if (THREAD) {
372
    if (THREAD) {
372
        /* must be run after the switch to scheduler stack */
373
        /* must be run after the switch to scheduler stack */
373
        after_thread_ran();
374
        after_thread_ran();
374
 
375
 
375
        switch (THREAD->state) {
376
        switch (THREAD->state) {
376
            case Running:
377
            case Running:
377
            spinlock_unlock(&THREAD->lock);
378
            spinlock_unlock(&THREAD->lock);
378
            thread_ready(THREAD);
379
            thread_ready(THREAD);
379
            break;
380
            break;
380
 
381
 
381
            case Exiting:
382
            case Exiting:
382
repeat:
383
repeat:
383
                if (THREAD->detached) {
384
                if (THREAD->detached) {
384
                thread_destroy(THREAD);
385
                thread_destroy(THREAD);
385
            } else {
386
            } else {
386
                /*
387
                /*
387
                 * The thread structure is kept allocated until somebody
388
                 * The thread structure is kept allocated until somebody
388
                 * calls thread_detach() on it.
389
                 * calls thread_detach() on it.
389
                 */
390
                 */
390
                if (!spinlock_trylock(&THREAD->join_wq.lock)) {
391
                if (!spinlock_trylock(&THREAD->join_wq.lock)) {
391
                    /*
392
                    /*
392
                     * Avoid deadlock.
393
                     * Avoid deadlock.
393
                     */
394
                     */
394
                    spinlock_unlock(&THREAD->lock);
395
                    spinlock_unlock(&THREAD->lock);
395
                    delay(10);
396
                    delay(10);
396
                    spinlock_lock(&THREAD->lock);
397
                    spinlock_lock(&THREAD->lock);
397
                    goto repeat;
398
                    goto repeat;
398
                }
399
                }
399
                _waitq_wakeup_unsafe(&THREAD->join_wq, false);
400
                _waitq_wakeup_unsafe(&THREAD->join_wq, false);
400
                spinlock_unlock(&THREAD->join_wq.lock);
401
                spinlock_unlock(&THREAD->join_wq.lock);
401
               
402
               
402
                THREAD->state = Undead;
403
                THREAD->state = Undead;
403
                spinlock_unlock(&THREAD->lock);
404
                spinlock_unlock(&THREAD->lock);
404
            }
405
            }
405
            break;
406
            break;
406
           
407
           
407
            case Sleeping:
408
            case Sleeping:
408
            /*
409
            /*
409
             * Prefer the thread after it's woken up.
410
             * Prefer the thread after it's woken up.
410
             */
411
             */
411
            THREAD->priority = -1;
412
            THREAD->priority = -1;
412
 
413
 
413
            /*
414
            /*
414
             * We need to release wq->lock which we locked in waitq_sleep().
415
             * We need to release wq->lock which we locked in waitq_sleep().
415
             * Address of wq->lock is kept in THREAD->sleep_queue.
416
             * Address of wq->lock is kept in THREAD->sleep_queue.
416
             */
417
             */
417
            spinlock_unlock(&THREAD->sleep_queue->lock);
418
            spinlock_unlock(&THREAD->sleep_queue->lock);
418
 
419
 
419
            /*
420
            /*
420
             * Check for possible requests for out-of-context invocation.
421
             * Check for possible requests for out-of-context invocation.
421
             */
422
             */
422
            if (THREAD->call_me) {
423
            if (THREAD->call_me) {
423
                THREAD->call_me(THREAD->call_me_with);
424
                THREAD->call_me(THREAD->call_me_with);
424
                THREAD->call_me = NULL;
425
                THREAD->call_me = NULL;
425
                THREAD->call_me_with = NULL;
426
                THREAD->call_me_with = NULL;
426
            }
427
            }
427
 
428
 
428
            spinlock_unlock(&THREAD->lock);
429
            spinlock_unlock(&THREAD->lock);
429
 
430
 
430
            break;
431
            break;
431
 
432
 
432
            default:
433
            default:
433
            /*
434
            /*
434
             * Entering state is unexpected.
435
             * Entering state is unexpected.
435
             */
436
             */
436
            panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);
437
            panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);
437
            break;
438
            break;
438
        }
439
        }
439
 
440
 
440
        THREAD = NULL;
441
        THREAD = NULL;
441
    }
442
    }
442
 
443
 
443
    THREAD = find_best_thread();
444
    THREAD = find_best_thread();
444
   
445
   
445
    spinlock_lock(&THREAD->lock);
446
    spinlock_lock(&THREAD->lock);
446
    priority = THREAD->priority;
447
    priority = THREAD->priority;
447
    spinlock_unlock(&THREAD->lock);
448
    spinlock_unlock(&THREAD->lock);
448
 
449
 
449
    relink_rq(priority);       
450
    relink_rq(priority);       
450
 
451
 
451
    /*
452
    /*
452
     * If both the old and the new task are the same, lots of work is avoided.
453
     * If both the old and the new task are the same, lots of work is avoided.
453
     */
454
     */
454
    if (TASK != THREAD->task) {
455
    if (TASK != THREAD->task) {
455
        as_t *as1 = NULL;
456
        as_t *as1 = NULL;
456
        as_t *as2;
457
        as_t *as2;
457
 
458
 
458
        if (TASK) {
459
        if (TASK) {
459
            spinlock_lock(&TASK->lock);
460
            spinlock_lock(&TASK->lock);
460
            as1 = TASK->as;
461
            as1 = TASK->as;
461
            spinlock_unlock(&TASK->lock);
462
            spinlock_unlock(&TASK->lock);
462
        }
463
        }
463
 
464
 
464
        spinlock_lock(&THREAD->task->lock);
465
        spinlock_lock(&THREAD->task->lock);
465
        as2 = THREAD->task->as;
466
        as2 = THREAD->task->as;
466
        spinlock_unlock(&THREAD->task->lock);
467
        spinlock_unlock(&THREAD->task->lock);
467
       
468
       
468
        /*
469
        /*
469
         * Note that it is possible for two tasks to share one address space.
470
         * Note that it is possible for two tasks to share one address space.
470
         */
471
         */
471
        if (as1 != as2) {
472
        if (as1 != as2) {
472
            /*
473
            /*
473
             * Both tasks and address spaces are different.
474
             * Both tasks and address spaces are different.
474
             * Replace the old one with the new one.
475
             * Replace the old one with the new one.
475
             */
476
             */
476
            as_switch(as1, as2);
477
            as_switch(as1, as2);
477
        }
478
        }
478
        TASK = THREAD->task;
479
        TASK = THREAD->task;
479
        before_task_runs();
480
        before_task_runs();
480
    }
481
    }
481
 
482
 
482
    spinlock_lock(&THREAD->lock);  
483
    spinlock_lock(&THREAD->lock);  
483
    THREAD->state = Running;
484
    THREAD->state = Running;
484
 
485
 
485
#ifdef SCHEDULER_VERBOSE
486
#ifdef SCHEDULER_VERBOSE
-
 
487
    printf("cpu%d: tid %d (priority=%d,ticks=%lld,nrdy=%ld)\n",
486
    printf("cpu%d: tid %d (priority=%d,ticks=%lld,nrdy=%ld)\n", CPU->id, THREAD->tid, THREAD->priority, THREAD->ticks, atomic_get(&CPU->nrdy));
488
        CPU->id, THREAD->tid, THREAD->priority, THREAD->ticks, atomic_get(&CPU->nrdy));
487
#endif  
489
#endif  
488
 
490
 
489
    /*
491
    /*
490
     * Some architectures provide late kernel PA2KA(identity)
492
     * Some architectures provide late kernel PA2KA(identity)
491
     * mapping in a page fault handler. However, the page fault
493
     * mapping in a page fault handler. However, the page fault
492
     * handler uses the kernel stack of the running thread and
494
     * handler uses the kernel stack of the running thread and
493
     * therefore cannot be used to map it. The kernel stack, if
495
     * therefore cannot be used to map it. The kernel stack, if
494
     * necessary, is to be mapped in before_thread_runs(). This
496
     * necessary, is to be mapped in before_thread_runs(). This
495
     * function must be executed before the switch to the new stack.
497
     * function must be executed before the switch to the new stack.
496
     */
498
     */
497
    before_thread_runs();
499
    before_thread_runs();
498
 
500
 
499
    /*
501
    /*
500
     * Copy the knowledge of CPU, TASK, THREAD and preemption counter to thread's stack.
502
     * Copy the knowledge of CPU, TASK, THREAD and preemption counter to thread's stack.
501
     */
503
     */
502
    the_copy(THE, (the_t *) THREAD->kstack);
504
    the_copy(THE, (the_t *) THREAD->kstack);
503
   
505
   
504
    context_restore(&THREAD->saved_context);
506
    context_restore(&THREAD->saved_context);
505
    /* not reached */
507
    /* not reached */
506
}
508
}
507
 
509
 
508
#ifdef CONFIG_SMP
510
#ifdef CONFIG_SMP
509
/** Load balancing thread
511
/** Load balancing thread
510
 *
512
 *
511
 * SMP load balancing thread, supervising thread supplies
513
 * SMP load balancing thread, supervising thread supplies
512
 * for the CPU it's wired to.
514
 * for the CPU it's wired to.
513
 *
515
 *
514
 * @param arg Generic thread argument (unused).
516
 * @param arg Generic thread argument (unused).
515
 *
517
 *
516
 */
518
 */
517
void kcpulb(void *arg)
519
void kcpulb(void *arg)
518
{
520
{
519
    thread_t *t;
521
    thread_t *t;
520
    int count, average, i, j, k = 0;
522
    int count, average, i, j, k = 0;
521
    ipl_t ipl;
523
    ipl_t ipl;
522
 
524
 
523
    /*
525
    /*
524
     * Detach kcpulb as nobody will call thread_join_timeout() on it.
526
     * Detach kcpulb as nobody will call thread_join_timeout() on it.
525
     */
527
     */
526
    thread_detach(THREAD);
528
    thread_detach(THREAD);
527
   
529
   
528
loop:
530
loop:
529
    /*
531
    /*
530
     * Work in 1s intervals.
532
     * Work in 1s intervals.
531
     */
533
     */
532
    thread_sleep(1);
534
    thread_sleep(1);
533
 
535
 
534
not_satisfied:
536
not_satisfied:
535
    /*
537
    /*
536
     * Calculate the number of threads that will be migrated/stolen from
538
     * Calculate the number of threads that will be migrated/stolen from
537
     * other CPU's. Note that situation can have changed between two
539
     * other CPU's. Note that situation can have changed between two
538
     * passes. Each time get the most up to date counts.
540
     * passes. Each time get the most up to date counts.
539
     */
541
     */
540
    average = atomic_get(&nrdy) / config.cpu_active + 1;
542
    average = atomic_get(&nrdy) / config.cpu_active + 1;
541
    count = average - atomic_get(&CPU->nrdy);
543
    count = average - atomic_get(&CPU->nrdy);
542
 
544
 
543
    if (count <= 0)
545
    if (count <= 0)
544
        goto satisfied;
546
        goto satisfied;
545
 
547
 
546
    /*
548
    /*
547
     * Searching least priority queues on all CPU's first and most priority queues on all CPU's last.
549
     * Searching least priority queues on all CPU's first and most priority queues on all CPU's last.
548
     */
550
     */
549
    for (j=RQ_COUNT-1; j >= 0; j--) {
551
    for (j=RQ_COUNT-1; j >= 0; j--) {
550
        for (i=0; i < config.cpu_active; i++) {
552
        for (i=0; i < config.cpu_active; i++) {
551
            link_t *l;
553
            link_t *l;
552
            runq_t *r;
554
            runq_t *r;
553
            cpu_t *cpu;
555
            cpu_t *cpu;
554
 
556
 
555
            cpu = &cpus[(i + k) % config.cpu_active];
557
            cpu = &cpus[(i + k) % config.cpu_active];
556
 
558
 
557
            /*
559
            /*
558
             * Not interested in ourselves.
560
             * Not interested in ourselves.
559
             * Doesn't require interrupt disabling for kcpulb is X_WIRED.
561
             * Doesn't require interrupt disabling for kcpulb has THREAD_FLAG_WIRED.
560
             */
562
             */
561
            if (CPU == cpu)
563
            if (CPU == cpu)
562
                continue;
564
                continue;
563
            if (atomic_get(&cpu->nrdy) <= average)
565
            if (atomic_get(&cpu->nrdy) <= average)
564
                continue;
566
                continue;
565
 
567
 
566
            ipl = interrupts_disable();
568
            ipl = interrupts_disable();
567
            r = &cpu->rq[j];
569
            r = &cpu->rq[j];
568
            spinlock_lock(&r->lock);
570
            spinlock_lock(&r->lock);
569
            if (r->n == 0) {
571
            if (r->n == 0) {
570
                spinlock_unlock(&r->lock);
572
                spinlock_unlock(&r->lock);
571
                interrupts_restore(ipl);
573
                interrupts_restore(ipl);
572
                continue;
574
                continue;
573
            }
575
            }
574
       
576
       
575
            t = NULL;
577
            t = NULL;
576
            l = r->rq_head.prev;    /* search rq from the back */
578
            l = r->rq_head.prev;    /* search rq from the back */
577
            while (l != &r->rq_head) {
579
            while (l != &r->rq_head) {
578
                t = list_get_instance(l, thread_t, rq_link);
580
                t = list_get_instance(l, thread_t, rq_link);
579
                /*
581
                /*
580
                 * We don't want to steal CPU-wired threads neither threads already stolen.
582
                 * We don't want to steal CPU-wired threads neither threads already
581
                 * The latter prevents threads from migrating between CPU's without ever being run.
583
                 * stolen. The latter prevents threads from migrating between CPU's
582
                 * We don't want to steal threads whose FPU context is still in CPU.
584
                 * without ever being run. We don't want to steal threads whose FPU
-
 
585
                 * context is still in CPU.
583
                 */
586
                 */
584
                spinlock_lock(&t->lock);
587
                spinlock_lock(&t->lock);
585
                if ( (!(t->flags & (X_WIRED | X_STOLEN))) && (!(t->fpu_context_engaged)) ) {
588
                if ((!(t->flags & (THREAD_FLAG_WIRED | THREAD_FLAG_STOLEN))) &&
-
 
589
                    (!(t->fpu_context_engaged)) ) {
586
                    /*
590
                    /*
587
                     * Remove t from r.
591
                     * Remove t from r.
588
                     */
592
                     */
589
                    spinlock_unlock(&t->lock);
593
                    spinlock_unlock(&t->lock);
590
                   
594
                   
591
                    atomic_dec(&cpu->nrdy);
595
                    atomic_dec(&cpu->nrdy);
592
                    atomic_dec(&nrdy);
596
                    atomic_dec(&nrdy);
593
 
597
 
594
                    r->n--;
598
                    r->n--;
595
                    list_remove(&t->rq_link);
599
                    list_remove(&t->rq_link);
596
 
600
 
597
                    break;
601
                    break;
598
                }
602
                }
599
                spinlock_unlock(&t->lock);
603
                spinlock_unlock(&t->lock);
600
                l = l->prev;
604
                l = l->prev;
601
                t = NULL;
605
                t = NULL;
602
            }
606
            }
603
            spinlock_unlock(&r->lock);
607
            spinlock_unlock(&r->lock);
604
 
608
 
605
            if (t) {
609
            if (t) {
606
                /*
610
                /*
607
                 * Ready t on local CPU
611
                 * Ready t on local CPU
608
                 */
612
                 */
609
                spinlock_lock(&t->lock);
613
                spinlock_lock(&t->lock);
610
#ifdef KCPULB_VERBOSE
614
#ifdef KCPULB_VERBOSE
611
                printf("kcpulb%d: TID %d -> cpu%d, nrdy=%ld, avg=%nd\n", CPU->id, t->tid, CPU->id, atomic_get(&CPU->nrdy), atomic_get(&nrdy) / config.cpu_active);
615
                printf("kcpulb%d: TID %d -> cpu%d, nrdy=%ld, avg=%nd\n",
-
 
616
                    CPU->id, t->tid, CPU->id, atomic_get(&CPU->nrdy),
-
 
617
                    atomic_get(&nrdy) / config.cpu_active);
612
#endif
618
#endif
613
                t->flags |= X_STOLEN;
619
                t->flags |= THREAD_FLAG_STOLEN;
614
                t->state = Entering;
620
                t->state = Entering;
615
                spinlock_unlock(&t->lock);
621
                spinlock_unlock(&t->lock);
616
   
622
   
617
                thread_ready(t);
623
                thread_ready(t);
618
 
624
 
619
                interrupts_restore(ipl);
625
                interrupts_restore(ipl);
620
   
626
   
621
                if (--count == 0)
627
                if (--count == 0)
622
                    goto satisfied;
628
                    goto satisfied;
623
                   
629
                   
624
                /*
630
                /*
625
                 * We are not satisfied yet, focus on another CPU next time.
631
                 * We are not satisfied yet, focus on another CPU next time.
626
                 */
632
                 */
627
                k++;
633
                k++;
628
               
634
               
629
                continue;
635
                continue;
630
            }
636
            }
631
            interrupts_restore(ipl);
637
            interrupts_restore(ipl);
632
        }
638
        }
633
    }
639
    }
634
 
640
 
635
    if (atomic_get(&CPU->nrdy)) {
641
    if (atomic_get(&CPU->nrdy)) {
636
        /*
642
        /*
637
         * Be a little bit light-weight and let migrated threads run.
643
         * Be a little bit light-weight and let migrated threads run.
638
         */
644
         */
639
        scheduler();
645
        scheduler();
640
    } else {
646
    } else {
641
        /*
647
        /*
642
         * We failed to migrate a single thread.
648
         * We failed to migrate a single thread.
643
         * Give up this turn.
649
         * Give up this turn.
644
         */
650
         */
645
        goto loop;
651
        goto loop;
646
    }
652
    }
647
       
653
       
648
    goto not_satisfied;
654
    goto not_satisfied;
649
 
655
 
650
satisfied:
656
satisfied:
651
    goto loop;
657
    goto loop;
652
}
658
}
653
 
659
 
654
#endif /* CONFIG_SMP */
660
#endif /* CONFIG_SMP */
655
 
661
 
656
 
662
 
657
/** Print information about threads & scheduler queues */
663
/** Print information about threads & scheduler queues */
658
void sched_print_list(void)
664
void sched_print_list(void)
659
{
665
{
660
    ipl_t ipl;
666
    ipl_t ipl;
661
    int cpu,i;
667
    int cpu,i;
662
    runq_t *r;
668
    runq_t *r;
663
    thread_t *t;
669
    thread_t *t;
664
    link_t *cur;
670
    link_t *cur;
665
 
671
 
666
    /* We are going to mess with scheduler structures,
672
    /* We are going to mess with scheduler structures,
667
     * let's not be interrupted */
673
     * let's not be interrupted */
668
    ipl = interrupts_disable();
674
    ipl = interrupts_disable();
669
    for (cpu=0;cpu < config.cpu_count; cpu++) {
675
    for (cpu=0;cpu < config.cpu_count; cpu++) {
670
 
676
 
671
        if (!cpus[cpu].active)
677
        if (!cpus[cpu].active)
672
            continue;
678
            continue;
673
 
679
 
674
        spinlock_lock(&cpus[cpu].lock);
680
        spinlock_lock(&cpus[cpu].lock);
675
        printf("cpu%d: address=%p, nrdy=%ld, needs_relink=%ld\n",
681
        printf("cpu%d: address=%p, nrdy=%ld, needs_relink=%ld\n",
676
               cpus[cpu].id, &cpus[cpu], atomic_get(&cpus[cpu].nrdy), cpus[cpu].needs_relink);
682
               cpus[cpu].id, &cpus[cpu], atomic_get(&cpus[cpu].nrdy), cpus[cpu].needs_relink);
677
       
683
       
678
        for (i=0; i<RQ_COUNT; i++) {
684
        for (i=0; i<RQ_COUNT; i++) {
679
            r = &cpus[cpu].rq[i];
685
            r = &cpus[cpu].rq[i];
680
            spinlock_lock(&r->lock);
686
            spinlock_lock(&r->lock);
681
            if (!r->n) {
687
            if (!r->n) {
682
                spinlock_unlock(&r->lock);
688
                spinlock_unlock(&r->lock);
683
                continue;
689
                continue;
684
            }
690
            }
685
            printf("\trq[%d]: ", i);
691
            printf("\trq[%d]: ", i);
686
            for (cur=r->rq_head.next; cur!=&r->rq_head; cur=cur->next) {
692
            for (cur=r->rq_head.next; cur!=&r->rq_head; cur=cur->next) {
687
                t = list_get_instance(cur, thread_t, rq_link);
693
                t = list_get_instance(cur, thread_t, rq_link);
688
                printf("%d(%s) ", t->tid,
694
                printf("%d(%s) ", t->tid,
689
                       thread_states[t->state]);
695
                       thread_states[t->state]);
690
            }
696
            }
691
            printf("\n");
697
            printf("\n");
692
            spinlock_unlock(&r->lock);
698
            spinlock_unlock(&r->lock);
693
        }
699
        }
694
        spinlock_unlock(&cpus[cpu].lock);
700
        spinlock_unlock(&cpus[cpu].lock);
695
    }
701
    }
696
   
702
   
697
    interrupts_restore(ipl);
703
    interrupts_restore(ipl);
698
}
704
}
699
 
705
 
700
/** @}
706
/** @}
701
 */
707
 */
702
 
708