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 extern "C" 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 extern "C" 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 extern "C" 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 
 147         c = -1;
 148         next = p = &init_task;
 149         for (;;) {
 150                 if ((p = p->next_task) == &init_task)
 151                         goto confuse_gcc2;
 152                 if (p->state == TASK_RUNNING && p->counter > c)
 153                         c = p->counter, next = p;
 154         }
 155 confuse_gcc2:
 156         if (!c) {
 157                 for_each_task(p)
 158                         p->counter = (p->counter >> 1) + p->priority;
 159         }
 160         switch_to(next);
 161 }
 162 
 163 extern "C" int sys_pause(void)
     /*  */
 164 {
 165         current->state = TASK_INTERRUPTIBLE;
 166         schedule();
 167         return -ERESTARTNOHAND;
 168 }
 169 
 170 /*
 171  * wake_up doesn't wake up stopped processes - they have to be awakened
 172  * with signals or similar.
 173  *
 174  * Note that this doesn't need cli-sti pairs: interrupts may not change
 175  * the wait-queue structures directly, but only call wake_up() to wake
 176  * a process. The process itself must remove the queue once it has woken.
 177  */
 178 void wake_up(struct wait_queue **q)
     /*  */
 179 {
 180         struct wait_queue *tmp;
 181         struct task_struct * p;
 182 
 183         if (!q || !(tmp = *q))
 184                 return;
 185         do {
 186                 if ((p = tmp->task) != NULL) {
 187                         if ((p->state == TASK_UNINTERRUPTIBLE) ||
 188                             (p->state == TASK_INTERRUPTIBLE)) {
 189                                 p->state = TASK_RUNNING;
 190                                 if (p->counter > current->counter)
 191                                         need_resched = 1;
 192                         }
 193                 }
 194                 if (!tmp->next) {
 195                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 196                         printk("        q = %08x\n",q);
 197                         printk("       *q = %08x\n",*q);
 198                         printk("      tmp = %08x\n",tmp);
 199                         break;
 200                 }
 201                 tmp = tmp->next;
 202         } while (tmp != *q);
 203 }
 204 
 205 void wake_up_interruptible(struct wait_queue **q)
     /*  */
 206 {
 207         struct wait_queue *tmp;
 208         struct task_struct * p;
 209 
 210         if (!q || !(tmp = *q))
 211                 return;
 212         do {
 213                 if ((p = tmp->task) != NULL) {
 214                         if (p->state == TASK_INTERRUPTIBLE) {
 215                                 p->state = TASK_RUNNING;
 216                                 if (p->counter > current->counter)
 217                                         need_resched = 1;
 218                         }
 219                 }
 220                 if (!tmp->next) {
 221                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 222                         printk("        q = %08x\n",q);
 223                         printk("       *q = %08x\n",*q);
 224                         printk("      tmp = %08x\n",tmp);
 225                         break;
 226                 }
 227                 tmp = tmp->next;
 228         } while (tmp != *q);
 229 }
 230 
 231 static inline void __sleep_on(struct wait_queue **p, int state)
     /*  */
 232 {
 233         unsigned long flags;
 234         struct wait_queue wait = { current, NULL };
 235 
 236         if (!p)
 237                 return;
 238         if (current == task[0])
 239                 panic("task[0] trying to sleep");
 240         current->state = state;
 241         add_wait_queue(p, &wait);
 242         save_flags(flags);
 243         sti();
 244         schedule();
 245         remove_wait_queue(p, &wait);
 246         restore_flags(flags);
 247 }
 248 
 249 void interruptible_sleep_on(struct wait_queue **p)
     /*  */
 250 {
 251         __sleep_on(p,TASK_INTERRUPTIBLE);
 252 }
 253 
 254 void sleep_on(struct wait_queue **p)
     /*  */
 255 {
 256         __sleep_on(p,TASK_UNINTERRUPTIBLE);
 257 }
 258 
 259 static struct timer_list * next_timer = NULL;
 260 
 261 void add_timer(struct timer_list * timer)
     /*  */
 262 {
 263         unsigned long flags;
 264         struct timer_list ** p;
 265 
 266         if (!timer)
 267                 return;
 268         timer->next = NULL;
 269         p = &next_timer;
 270         save_flags(flags);
 271         cli();
 272         while (*p) {
 273                 if ((*p)->expires > timer->expires) {
 274                         (*p)->expires -= timer->expires;
 275                         timer->next = *p;
 276                         break;
 277                 }
 278                 timer->expires -= (*p)->expires;
 279                 p = &(*p)->next;
 280         }
 281         *p = timer;
 282         restore_flags(flags);
 283 }
 284 
 285 int del_timer(struct timer_list * timer)
     /*  */
 286 {
 287         unsigned long flags;
 288         unsigned long expires = 0;
 289         struct timer_list **p;
 290 
 291         p = &next_timer;
 292         save_flags(flags);
 293         cli();
 294         while (*p) {
 295                 if (*p == timer) {
 296                         if ((*p = timer->next) != NULL)
 297                                 (*p)->expires += timer->expires;
 298                         timer->expires += expires;
 299                         restore_flags(flags);
 300                         return 1;
 301                 }
 302                 expires += (*p)->expires;
 303                 p = &(*p)->next;
 304         }
 305         restore_flags(flags);
 306         return 0;
 307 }
 308 
 309 unsigned long timer_active = 0;
 310 struct timer_struct timer_table[32];
 311 
 312 /*
 313  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
 314  * imply that avenrun[] is the standard name for this kind of thing.
 315  * Nothing else seems to be standardized: the fractional size etc
 316  * all seem to differ on different machines.
 317  */
 318 unsigned long avenrun[3] = { 0,0,0 };
 319 
 320 /*
 321  * Nr of active tasks - counted in fixed-point numbers
 322  */
 323 static unsigned long count_active_tasks(void)
     /*  */
 324 {
 325         struct task_struct **p;
 326         unsigned long nr = 0;
 327 
 328         for(p = &LAST_TASK; p > &FIRST_TASK; --p)
 329                 if (*p && (*p)->state == TASK_RUNNING)
 330                         nr += FIXED_1;
 331         return nr;
 332 }
 333 
 334 static inline void calc_load(void)
     /*  */
 335 {
 336         unsigned long active_tasks; /* fixed-point */
 337         static int count = LOAD_FREQ;
 338 
 339         if (count-- > 0)
 340                 return;
 341         count = LOAD_FREQ;
 342         active_tasks = count_active_tasks();
 343         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 344         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 345         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 346 }
 347 
 348 /*
 349  * The int argument is really a (struct pt_regs *), in case the
 350  * interrupt wants to know from where it was called. The timer
 351  * irq uses this to decide if it should update the user or system
 352  * times.
 353  */
 354 static void do_timer(struct pt_regs * regs)
     /*  */
 355 {
 356         unsigned long mask;
 357         struct timer_struct *tp = timer_table+0;
 358         struct task_struct * task_p;
 359 
 360         jiffies++;
 361         calc_load();
 362         if ((VM_MASK & regs->eflags) || (3 & regs->cs)) {
 363                 current->utime++;
 364                 /* Update ITIMER_VIRT for current task if not in a system call */
 365                 if (current->it_virt_value && !(--current->it_virt_value)) {
 366                         current->it_virt_value = current->it_virt_incr;
 367                         send_sig(SIGVTALRM,current,1);
 368                 }
 369         } else {
 370                 current->stime++;
 371 #ifdef CONFIG_PROFILE
 372                 if (prof_buffer && current != task[0]) {
 373                         unsigned long eip = regs->eip;
 374                         eip >>= 2;
 375                         if (eip < prof_len)
 376                                 prof_buffer[eip]++;
 377                 }
 378 #endif
 379         }
 380         if (current == task[0] || (--current->counter)<=0) {
 381                 current->counter=0;
 382                 need_resched = 1;
 383         }
 384         /* Update ITIMER_REAL for every task */
 385         for_each_task(task_p) {
 386                 if (!task_p->it_real_value)
 387                         continue;
 388                 if (--task_p->it_real_value)
 389                         continue;
 390                 send_sig(SIGALRM,task_p,1);
 391                 task_p->it_real_value = task_p->it_real_incr;
 392                 need_resched = 1;
 393         }
 394         /* Update ITIMER_PROF for the current task */
 395         if (current->it_prof_value && !(--current->it_prof_value)) {
 396                 current->it_prof_value = current->it_prof_incr;
 397                 send_sig(SIGPROF,current,1);
 398         }
 399         for (mask = 1 ; mask ; tp++,mask += mask) {
 400                 if (mask > timer_active)
 401                         break;
 402                 if (!(mask & timer_active))
 403                         continue;
 404                 if (tp->expires > jiffies)
 405                         continue;
 406                 timer_active &= ~mask;
 407                 tp->fn();
 408                 sti();
 409         }
 410         cli();
 411         while (next_timer && next_timer->expires == 0) {
 412                 void (*fn)(unsigned long) = next_timer->function;
 413                 unsigned long data = next_timer->data;
 414                 next_timer = next_timer->next;
 415                 sti();
 416                 fn(data);
 417                 cli();
 418         }
 419         if (next_timer)
 420                 next_timer->expires--;
 421         sti();
 422 }
 423 
 424 extern "C" int sys_alarm(long seconds)
     /*  */
 425 {
 426         struct itimerval it_new, it_old;
 427 
 428         it_new.it_interval.tv_sec = it_new.it_interval.tv_usec = 0;
 429         it_new.it_value.tv_sec = seconds;
 430         it_new.it_value.tv_usec = 0;
 431         _setitimer(ITIMER_REAL, &it_new, &it_old);
 432         return(it_old.it_value.tv_sec + (it_old.it_value.tv_usec / 1000000));
 433 }
 434 
 435 extern "C" int sys_getpid(void)
     /*  */
 436 {
 437         return current->pid;
 438 }
 439 
 440 extern "C" int sys_getppid(void)
     /*  */
 441 {
 442         return current->p_pptr->pid;
 443 }
 444 
 445 extern "C" int sys_getuid(void)
     /*  */
 446 {
 447         return current->uid;
 448 }
 449 
 450 extern "C" int sys_geteuid(void)
     /*  */
 451 {
 452         return current->euid;
 453 }
 454 
 455 extern "C" int sys_getgid(void)
     /*  */
 456 {
 457         return current->gid;
 458 }
 459 
 460 extern "C" int sys_getegid(void)
     /*  */
 461 {
 462         return current->egid;
 463 }
 464 
 465 extern "C" int sys_nice(long increment)
     /*  */
 466 {
 467         int newprio;
 468 
 469         if (increment < 0 && !suser())
 470                 return -EPERM;
 471         newprio = current->priority - increment;
 472         if (newprio < 1)
 473                 newprio = 1;
 474         if (newprio > 35)
 475                 newprio = 35;
 476         current->priority = newprio;
 477         return 0;
 478 }
 479 
 480 static void show_task(int nr,struct task_struct * p)
     /*  */
 481 {
 482         int i, j;
 483         unsigned char * stack;
 484 
 485         printk("%d: pid=%d, state=%d, father=%d, child=%d, ",(p == current)?-nr:nr,p->pid,
 486                 p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
 487         i = 0;
 488         j = PAGE_SIZE;
 489         if (!(stack = (unsigned char *) p->kernel_stack_page)) {
 490                 stack = (unsigned char *) init_kernel_stack;
 491                 j = sizeof(init_kernel_stack);
 492         }
 493         while (i<j && !*(stack++))
 494                 i++;
 495         printk("%d/%d chars free in kstack\n",i,j);
 496         printk("   PC=%08X.", *(1019 + (unsigned long *) p));
 497         if (p->p_ysptr || p->p_osptr) 
 498                 printk("   Younger sib=%d, older sib=%d\n", 
 499                         p->p_ysptr ? p->p_ysptr->pid : -1,
 500                         p->p_osptr ? p->p_osptr->pid : -1);
 501         else
 502                 printk("\n");
 503 }
 504 
 505 void show_state(void)
     /*  */
 506 {
 507         int i;
 508 
 509         printk("Task-info:\n");
 510         for (i=0 ; i<NR_TASKS ; i++)
 511                 if (task[i])
 512                         show_task(i,task[i]);
 513 }
 514 
 515 void sched_init(void)
     /*  */
 516 {
 517         int i;
 518         struct desc_struct * p;
 519 
 520         if (sizeof(struct sigaction) != 16)
 521                 panic("Struct sigaction MUST be 16 bytes");
 522         set_tss_desc(gdt+FIRST_TSS_ENTRY,&init_task.tss);
 523         set_ldt_desc(gdt+FIRST_LDT_ENTRY,&default_ldt,1);
 524         set_system_gate(0x80,&system_call);
 525         p = gdt+2+FIRST_TSS_ENTRY;
 526         for(i=1 ; i<NR_TASKS ; i++) {
 527                 task[i] = NULL;
 528                 p->a=p->b=0;
 529                 p++;
 530                 p->a=p->b=0;
 531                 p++;
 532         }
 533 /* Clear NT, so that we won't have troubles with that later on */
 534         __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
 535         load_TR(0);
 536         load_ldt(0);
 537         outb_p(0x34,0x43);              /* binary, mode 2, LSB/MSB, ch 0 */
 538         outb_p(LATCH & 0xff , 0x40);    /* LSB */
 539         outb(LATCH >> 8 , 0x40);        /* MSB */
 540         if (request_irq(TIMER_IRQ,(void (*)(int)) do_timer)!=0)
 541                 panic("Could not allocate timer IRQ!");
 542 }

/* */