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

/* */