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

/* */