root/kernel/sched.c

/* */

DEFINITIONS

1. math_state_restore
2. schedule
3. sys_pause
4. wake_up
5. wake_up_interruptible
6. __sleep_on
7. interruptible_sleep_on
8. sleep_on
9. add_timer
10. del_timer
11. count_active_tasks
12. calc_load
13. do_timer
14. sys_alarm
15. sys_getpid
16. sys_getppid
17. sys_getuid
18. sys_geteuid
19. sys_getgid
20. sys_getegid
21. sys_nice
22. show_task
23. show_state
24. sched_init

   1 /*
   2  *  linux/kernel/sched.c
   3  *
   4  *  Copyright (C) 1991, 1992  Linus Torvalds
   5  */
   6 
   7 /*
   8  * 'sched.c' is the main kernel file. It contains scheduling primitives
   9  * (sleep_on, wakeup, schedule etc) as well as a number of simple system
  10  * call functions (type getpid(), which just extracts a field from
  11  * current-task
  12  */
  13 
  14 #define TIMER_IRQ 0
  15 
  16 #include <linux/config.h>
  17 #include <linux/signal.h>
  18 #include <linux/sched.h>
  19 #include <linux/timer.h>
  20 #include <linux/kernel.h>
  21 #include <linux/sys.h>
  22 #include <linux/fdreg.h>
  23 #include <linux/errno.h>
  24 #include <linux/time.h>
  25 #include <linux/ptrace.h>
  26 #include <linux/segment.h>
  27 
  28 #include <asm/system.h>
  29 #include <asm/io.h>
  30 #include <asm/segment.h>
  31 
  32 int need_resched = 0;
  33 int hard_math = 0;              /* set by boot/head.S */
  34 int ignore_irq13 = 0;           /* set if exception 16 works */
  35 
  36 unsigned long * prof_buffer = NULL;
  37 unsigned long prof_len = 0;
  38 
  39 #define _S(nr) (1<<((nr)-1))
  40 
  41 #define LATCH ((1193180 + HZ/2)/HZ)
  42 
  43 extern void mem_use(void);
  44 
  45 extern int timer_interrupt(void);
  46 extern int system_call(void);
  47 
  48 static unsigned long init_kernel_stack[1024];
  49 static struct task_struct init_task = INIT_TASK;
  50 
  51 unsigned long volatile jiffies=0;
  52 unsigned long startup_time=0;
  53 int jiffies_offset = 0;         /* # clock ticks to add to get "true
  54                                    time".  Should always be less than
  55                                    1 second's worth.  For time fanatics
  56                                    who like to syncronize their machines
  57                                    to WWV :-) */
  58 
  59 struct task_struct *current = &init_task;
  60 struct task_struct *last_task_used_math = NULL;
  61 
  62 struct task_struct * task[NR_TASKS] = {&init_task, };
  63 
  64 long user_stack [ PAGE_SIZE>>2 ] ;
  65 
  66 struct {
  67         long * a;
  68         short b;
  69         } stack_start = { & user_stack [PAGE_SIZE>>2] , KERNEL_DS };
  70 /*
  71  *  'math_state_restore()' saves the current math information in the
  72  * old math state array, and gets the new ones from the current task
  73  */
  74 void math_state_restore(void)
     /*  */
  75 {
  76         if (last_task_used_math == current)
  77                 return;
  78         timer_table[COPRO_TIMER].expires = jiffies+50;
  79         timer_active |= 1<<COPRO_TIMER; 
  80         if (last_task_used_math) {
  81                 __asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
  82         }
  83         __asm__("fwait");
  84         last_task_used_math = current;
  85         if (current->used_math) {
  86                 __asm__("frstor %0"::"m" (current->tss.i387));
  87         } else {
  88                 __asm__("fninit"::);
  89                 current->used_math=1;
  90         }
  91         timer_active &= ~(1<<COPRO_TIMER);
  92 }
  93 
  94 /*
  95  *  'schedule()' is the scheduler function. It's a very simple and nice
  96  * scheduler: it's not perfect, but certainly works for most things.
  97  * The one thing you might take a look at is the signal-handler code here.
  98  *
  99  *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 100  * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 101  * information in task[0] is never used.
 102  */
 103 void schedule(void)
     /*  */
 104 {
 105         int i,next,c;
 106         struct task_struct ** p;
 107 
 108 /* check alarm, wake up any interruptible tasks that have got a signal */
 109 
 110         need_resched = 0;
 111         for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
 112                 if (!*p || ((*p)->state != TASK_INTERRUPTIBLE))
 113                         continue;
 114                 if ((*p)->timeout && (*p)->timeout < jiffies) {
 115                         (*p)->timeout = 0;
 116                         (*p)->state = TASK_RUNNING;
 117                 } else if ((*p)->signal & ~(*p)->blocked)
 118                         (*p)->state = TASK_RUNNING;
 119         }
 120 
 121 /* this is the scheduler proper: */
 122 
 123         while (1) {
 124                 c = -1;
 125                 next = 0;
 126                 i = NR_TASKS;
 127                 p = &task[NR_TASKS];
 128                 while (--i) {
 129                         if (!*--p)
 130                                 continue;
 131                         if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
 132                                 c = (*p)->counter, next = i;
 133                 }
 134                 if (c)
 135                         break;
 136                 for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
 137                         if (*p)
 138                                 (*p)->counter = ((*p)->counter >> 1) +
 139                                                 (*p)->priority;
 140         }
 141         sti();
 142         switch_to(next);
 143 }
 144 
 145 int sys_pause(void)
     /*  */
 146 {
 147         current->state = TASK_INTERRUPTIBLE;
 148         schedule();
 149         return -ERESTARTNOHAND;
 150 }
 151 
 152 /*
 153  * wake_up doesn't wake up stopped processes - they have to be awakened
 154  * with signals or similar.
 155  *
 156  * Note that this doesn't need cli-sti pairs: interrupts may not change
 157  * the wait-queue structures directly, but only call wake_up() to wake
 158  * a process. The process itself must remove the queue once it has woken.
 159  */
 160 void wake_up(struct wait_queue **q)
     /*  */
 161 {
 162         struct wait_queue *tmp;
 163         struct task_struct * p;
 164 
 165         if (!q || !(tmp = *q))
 166                 return;
 167         do {
 168                 if ((p = tmp->task) != NULL) {
 169                         if ((p->state == TASK_UNINTERRUPTIBLE) ||
 170                             (p->state == TASK_INTERRUPTIBLE)) {
 171                                 p->state = TASK_RUNNING;
 172                                 if (p->counter > current->counter)
 173                                         need_resched = 1;
 174                         }
 175                 }
 176                 if (!tmp->next) {
 177                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 178                         printk("        q = %08x\n",q);
 179                         printk("       *q = %08x\n",*q);
 180                         printk("      tmp = %08x\n",tmp);
 181                         break;
 182                 }
 183                 tmp = tmp->next;
 184         } while (tmp != *q);
 185 }
 186 
 187 void wake_up_interruptible(struct wait_queue **q)
     /*  */
 188 {
 189         struct wait_queue *tmp;
 190         struct task_struct * p;
 191 
 192         if (!q || !(tmp = *q))
 193                 return;
 194         do {
 195                 if ((p = tmp->task) != NULL) {
 196                         if (p->state == TASK_INTERRUPTIBLE) {
 197                                 p->state = TASK_RUNNING;
 198                                 if (p->counter > current->counter)
 199                                         need_resched = 1;
 200                         }
 201                 }
 202                 if (!tmp->next) {
 203                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 204                         printk("        q = %08x\n",q);
 205                         printk("       *q = %08x\n",*q);
 206                         printk("      tmp = %08x\n",tmp);
 207                         break;
 208                 }
 209                 tmp = tmp->next;
 210         } while (tmp != *q);
 211 }
 212 
 213 static inline void __sleep_on(struct wait_queue **p, int state)
     /*  */
 214 {
 215         unsigned long flags;
 216         struct wait_queue wait = { current, NULL };
 217 
 218         if (!p)
 219                 return;
 220         if (current == task[0])
 221                 panic("task[0] trying to sleep");
 222         current->state = state;
 223         add_wait_queue(p, &wait);
 224         save_flags(flags);
 225         sti();
 226         schedule();
 227         remove_wait_queue(p, &wait);
 228         restore_flags(flags);
 229 }
 230 
 231 void interruptible_sleep_on(struct wait_queue **p)
     /*  */
 232 {
 233         __sleep_on(p,TASK_INTERRUPTIBLE);
 234 }
 235 
 236 void sleep_on(struct wait_queue **p)
     /*  */
 237 {
 238         __sleep_on(p,TASK_UNINTERRUPTIBLE);
 239 }
 240 
 241 static struct timer_list * next_timer = NULL;
 242 
 243 void add_timer(struct timer_list * timer)
     /*  */
 244 {
 245         unsigned long flags;
 246         struct timer_list ** p;
 247 
 248         if (!timer)
 249                 return;
 250         timer->next = NULL;
 251         p = &next_timer;
 252         save_flags(flags);
 253         cli();
 254         while (*p) {
 255                 if ((*p)->expires > timer->expires) {
 256                         (*p)->expires -= timer->expires;
 257                         timer->next = *p;
 258                         break;
 259                 }
 260                 timer->expires -= (*p)->expires;
 261                 p = &(*p)->next;
 262         }
 263         *p = timer;
 264         restore_flags(flags);
 265 }
 266 
 267 void del_timer(struct timer_list * timer)
     /*  */
 268 {
 269         unsigned long flags;
 270         struct timer_list **p;
 271 
 272         p = &next_timer;
 273         save_flags(flags);
 274         cli();
 275         while (*p) {
 276                 if (*p == timer) {
 277                         if ((*p = timer->next) != NULL)
 278                                 (*p)->expires += timer->expires;
 279                         break;
 280                 }
 281                 p = &(*p)->next;
 282         }
 283         restore_flags(flags);
 284 }
 285 
 286 unsigned long timer_active = 0;
 287 struct timer_struct timer_table[32];
 288 
 289 /*
 290  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
 291  * imply that avenrun[] is the standard name for this kind of thing.
 292  * Nothing else seems to be standardized: the fractional size etc
 293  * all seem to differ on different machines.
 294  */
 295 unsigned long avenrun[3] = { 0,0,0 };
 296 
 297 /*
 298  * Nr of active tasks - counted in fixed-point numbers
 299  */
 300 static unsigned long count_active_tasks(void)
     /*  */
 301 {
 302         struct task_struct **p;
 303         unsigned long nr = 0;
 304 
 305         for(p = &LAST_TASK; p > &FIRST_TASK; --p)
 306                 if (*p && (*p)->state == TASK_RUNNING)
 307                         nr += FIXED_1;
 308         return nr;
 309 }
 310 
 311 static inline void calc_load(void)
     /*  */
 312 {
 313         unsigned long active_tasks; /* fixed-point */
 314         static int count = LOAD_FREQ;
 315 
 316         if (count-- > 0)
 317                 return;
 318         count = LOAD_FREQ;
 319         active_tasks = count_active_tasks();
 320         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 321         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 322         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 323 }
 324 
 325 /*
 326  * The int argument is really a (struct pt_regs *), in case the
 327  * interrupt wants to know from where it was called. The timer
 328  * irq uses this to decide if it should update the user or system
 329  * times.
 330  */
 331 static void do_timer(struct pt_regs * regs)
     /*  */
 332 {
 333         unsigned long mask;
 334         struct timer_struct *tp = timer_table+0;
 335         struct task_struct ** task_p;
 336 
 337         jiffies++;
 338         calc_load();
 339         if ((VM_MASK & regs->eflags) || (3 & regs->cs)) {
 340                 current->utime++;
 341                 /* Update ITIMER_VIRT for current task if not in a system call */
 342                 if (current->it_virt_value && !(--current->it_virt_value)) {
 343                         current->it_virt_value = current->it_virt_incr;
 344                         send_sig(SIGVTALRM,current,1);
 345                 }
 346         } else {
 347                 current->stime++;
 348 #ifdef CONFIG_PROFILE
 349                 if (prof_buffer && current != task[0]) {
 350                         unsigned long eip = regs->eip;
 351                         eip >>= 2;
 352                         if (eip < prof_len)
 353                                 prof_buffer[eip]++;
 354                 }
 355 #endif
 356         }
 357         if (current == task[0] || (--current->counter)<=0) {
 358                 current->counter=0;
 359                 need_resched = 1;
 360         }
 361         /* Update ITIMER_REAL for every task */
 362         for (task_p = &LAST_TASK; task_p >= &FIRST_TASK; task_p--)
 363                 if (*task_p && (*task_p)->it_real_value
 364                         && !(--(*task_p)->it_real_value)) {
 365                         send_sig(SIGALRM,*task_p,1);
 366                         (*task_p)->it_real_value = (*task_p)->it_real_incr;
 367                         need_resched = 1;
 368                 }
 369         /* Update ITIMER_PROF for the current task */
 370         if (current->it_prof_value && !(--current->it_prof_value)) {
 371                 current->it_prof_value = current->it_prof_incr;
 372                 send_sig(SIGPROF,current,1);
 373         }
 374         for (mask = 1 ; mask ; tp++,mask += mask) {
 375                 if (mask > timer_active)
 376                         break;
 377                 if (!(mask & timer_active))
 378                         continue;
 379                 if (tp->expires > jiffies)
 380                         continue;
 381                 timer_active &= ~mask;
 382                 tp->fn();
 383                 sti();
 384         }
 385         cli();
 386         while (next_timer && next_timer->expires == 0) {
 387                 void (*fn)(unsigned long) = next_timer->function;
 388                 unsigned long data = next_timer->data;
 389                 next_timer = next_timer->next;
 390                 sti();
 391                 fn(data);
 392                 cli();
 393         }
 394         if (next_timer)
 395                 next_timer->expires--;
 396         sti();
 397 }
 398 
 399 int sys_alarm(long seconds)
     /*  */
 400 {
 401         extern int _setitimer(int, struct itimerval *, struct itimerval *);
 402         struct itimerval new, old;
 403 
 404         new.it_interval.tv_sec = new.it_interval.tv_usec = 0;
 405         new.it_value.tv_sec = seconds;
 406         new.it_value.tv_usec = 0;
 407         _setitimer(ITIMER_REAL, &new, &old);
 408         return(old.it_value.tv_sec + (old.it_value.tv_usec / 1000000));
 409 }
 410 
 411 int sys_getpid(void)
     /*  */
 412 {
 413         return current->pid;
 414 }
 415 
 416 int sys_getppid(void)
     /*  */
 417 {
 418         return current->p_pptr->pid;
 419 }
 420 
 421 int sys_getuid(void)
     /*  */
 422 {
 423         return current->uid;
 424 }
 425 
 426 int sys_geteuid(void)
     /*  */
 427 {
 428         return current->euid;
 429 }
 430 
 431 int sys_getgid(void)
     /*  */
 432 {
 433         return current->gid;
 434 }
 435 
 436 int sys_getegid(void)
     /*  */
 437 {
 438         return current->egid;
 439 }
 440 
 441 int sys_nice(long increment)
     /*  */
 442 {
 443         if (increment < 0 && !suser())
 444                 return -EPERM;
 445         if (increment >= current->priority)
 446                 increment = current->priority-1;
 447         current->priority -= increment;
 448         return 0;
 449 }
 450 
 451 static void show_task(int nr,struct task_struct * p)
     /*  */
 452 {
 453         int i, j;
 454         unsigned char * stack;
 455 
 456         printk("%d: pid=%d, state=%d, father=%d, child=%d, ",(p == current)?-nr:nr,p->pid,
 457                 p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
 458         i = 0;
 459         j = 4096;
 460         if (!(stack = (char *) p->kernel_stack_page)) {
 461                 stack = (char *) init_kernel_stack;
 462                 j = sizeof(init_kernel_stack);
 463         }
 464         while (i<j && !*(stack++))
 465                 i++;
 466         printk("%d/%d chars free in kstack\n",i,j);
 467         printk("   PC=%08X.", *(1019 + (unsigned long *) p));
 468         if (p->p_ysptr || p->p_osptr) 
 469                 printk("   Younger sib=%d, older sib=%d\n", 
 470                         p->p_ysptr ? p->p_ysptr->pid : -1,
 471                         p->p_osptr ? p->p_osptr->pid : -1);
 472         else
 473                 printk("\n");
 474 }
 475 
 476 void show_state(void)
     /*  */
 477 {
 478         int i;
 479 
 480         printk("Task-info:\n");
 481         for (i=0 ; i<NR_TASKS ; i++)
 482                 if (task[i])
 483                         show_task(i,task[i]);
 484 }
 485 
 486 void sched_init(void)
     /*  */
 487 {
 488         int i;
 489         struct desc_struct * p;
 490 
 491         if (sizeof(struct sigaction) != 16)
 492                 panic("Struct sigaction MUST be 16 bytes");
 493         set_tss_desc(gdt+FIRST_TSS_ENTRY,&init_task.tss);
 494         set_ldt_desc(gdt+FIRST_LDT_ENTRY,&init_task.ldt);
 495         set_system_gate(0x80,&system_call);
 496         p = gdt+2+FIRST_TSS_ENTRY;
 497         for(i=1 ; i<NR_TASKS ; i++) {
 498                 task[i] = NULL;
 499                 p->a=p->b=0;
 500                 p++;
 501                 p->a=p->b=0;
 502                 p++;
 503         }
 504 /* Clear NT, so that we won't have troubles with that later on */
 505         __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
 506         load_TR(0);
 507         load_ldt(0);
 508         outb_p(0x34,0x43);              /* binary, mode 2, LSB/MSB, ch 0 */
 509         outb_p(LATCH & 0xff , 0x40);    /* LSB */
 510         outb(LATCH >> 8 , 0x40);        /* MSB */
 511         request_irq(TIMER_IRQ,(void (*)(int)) do_timer);
 512 }

/* */