kernel/sched.c

/* */
This source file includes following definitions.
math_state_restore
schedule
sys_pause
wake_up
wake_up_interruptible
__sleep_on
interruptible_sleep_on
sleep_on
ticks_to_floppy_on
floppy_off
do_floppy_timer
add_timer
count_active_tasks
calc_load
do_timer
sys_alarm
sys_getpid
sys_getppid
sys_getuid
sys_geteuid
sys_getgid
sys_getegid
sys_nice
show_task
show_state
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 
  27 #include <asm/system.h>
  28 #include <asm/io.h>
  29 #include <asm/segment.h>
  30 
  31 int need_resched = 0;
  32 int hard_math = 0;              /* set by boot/head.S */
  33 int ignore_irq13 = 0;           /* set if exception 16 works */
  34 
  35 unsigned long * prof_buffer = NULL;
  36 unsigned long prof_len = 0;
  37 
  38 #define _S(nr) (1<<((nr)-1))
  39 #define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))
  40 
  41 #define LATCH (1193180/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] , 0x10 };
  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()
     /*  */
  75 {
  76         if (last_task_used_math == current)
  77                 return;
  78         if (last_task_used_math) {
  79                 __asm__("fnsave %0"::"m" (last_task_used_math->tss.i387));
  80         }
  81         __asm__("fwait");
  82         last_task_used_math = current;
  83         if (current->used_math) {
  84                 __asm__("frstor %0"::"m" (current->tss.i387));
  85         } else {
  86                 __asm__("fninit"::);
  87                 current->used_math=1;
  88         }
  89 }
  90 
  91 /*
  92  *  'schedule()' is the scheduler function. It's a very simple and nice
  93  * scheduler: it's not perfect, but certainly works for most things.
  94  * The one thing you might take a look at is the signal-handler code here.
  95  *
  96  *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
  97  * tasks can run. It can not be killed, and it cannot sleep. The 'state'
  98  * information in task[0] is never used.
  99  */
 100 void schedule(void)
     /*  */
 101 {
 102         int i,next,c;
 103         struct task_struct ** p;
 104 
 105 /* check alarm, wake up any interruptible tasks that have got a signal */
 106 
 107         need_resched = 0;
 108         for(p = &LAST_TASK ; p > &FIRST_TASK ; --p) {
 109                 if (!*p || ((*p)->state != TASK_INTERRUPTIBLE))
 110                         continue;
 111                 if ((*p)->timeout && (*p)->timeout < jiffies) {
 112                         (*p)->timeout = 0;
 113                         (*p)->state = TASK_RUNNING;
 114                 } else if ((*p)->signal & ~(*p)->blocked)
 115                         (*p)->state = TASK_RUNNING;
 116         }
 117 
 118 /* this is the scheduler proper: */
 119 
 120         while (1) {
 121                 c = -1;
 122                 next = 0;
 123                 i = NR_TASKS;
 124                 p = &task[NR_TASKS];
 125                 while (--i) {
 126                         if (!*--p)
 127                                 continue;
 128                         if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
 129                                 c = (*p)->counter, next = i;
 130                 }
 131                 if (c)
 132                         break;
 133                 for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
 134                         if (*p)
 135                                 (*p)->counter = ((*p)->counter >> 1) +
 136                                                 (*p)->priority;
 137         }
 138         sti();
 139         switch_to(next);
 140 }
 141 
 142 int sys_pause(void)
     /*  */
 143 {
 144         unsigned long old_blocked;
 145         unsigned long mask;
 146         struct sigaction * sa = current->sigaction;
 147 
 148         old_blocked = current->blocked;
 149         for (mask=1 ; mask ; sa++,mask += mask)
 150                 if (sa->sa_handler == SIG_IGN)
 151                         current->blocked |= mask;
 152         current->state = TASK_INTERRUPTIBLE;
 153         schedule();
 154         current->blocked = old_blocked;
 155         return -EINTR;
 156 }
 157 
 158 /*
 159  * wake_up doesn't wake up stopped processes - they have to be awakened
 160  * with signals or similar.
 161  *
 162  * Note that this doesn't need cli-sti pairs: interrupts may not change
 163  * the wait-queue structures directly, but only call wake_up() to wake
 164  * a process. The process itself must remove the queue once it has woken.
 165  */
 166 void wake_up(struct wait_queue **q)
     /*  */
 167 {
 168         struct wait_queue *tmp;
 169         struct task_struct * p;
 170 
 171         if (!q || !(tmp = *q))
 172                 return;
 173         do {
 174                 if ((p = tmp->task) != NULL) {
 175                         if ((p->state == TASK_UNINTERRUPTIBLE) ||
 176                             (p->state == TASK_INTERRUPTIBLE)) {
 177                                 p->state = TASK_RUNNING;
 178                                 if (p->counter > current->counter)
 179                                         need_resched = 1;
 180                         }
 181                 }
 182                 if (!tmp->next) {
 183                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 184                         printk("        q = %08x\n",q);
 185                         printk("       *q = %08x\n",*q);
 186                         printk("      tmp = %08x\n",tmp);
 187                         break;
 188                 }
 189                 tmp = tmp->next;
 190         } while (tmp != *q);
 191 }
 192 
 193 void wake_up_interruptible(struct wait_queue **q)
     /*  */
 194 {
 195         struct wait_queue *tmp;
 196         struct task_struct * p;
 197 
 198         if (!q || !(tmp = *q))
 199                 return;
 200         do {
 201                 if ((p = tmp->task) != NULL) {
 202                         if (p->state == TASK_INTERRUPTIBLE) {
 203                                 p->state = TASK_RUNNING;
 204                                 if (p->counter > current->counter)
 205                                         need_resched = 1;
 206                         }
 207                 }
 208                 if (!tmp->next) {
 209                         printk("wait_queue is bad (eip = %08x)\n",((unsigned long *) q)[-1]);
 210                         printk("        q = %08x\n",q);
 211                         printk("       *q = %08x\n",*q);
 212                         printk("      tmp = %08x\n",tmp);
 213                         break;
 214                 }
 215                 tmp = tmp->next;
 216         } while (tmp != *q);
 217 }
 218 
 219 static inline void __sleep_on(struct wait_queue **p, int state)
     /*  */
 220 {
 221         unsigned long flags;
 222         struct wait_queue wait = { current, NULL };
 223 
 224         if (!p)
 225                 return;
 226         if (current == task[0])
 227                 panic("task[0] trying to sleep");
 228         current->state = state;
 229         add_wait_queue(p, &wait);
 230         save_flags(flags);
 231         sti();
 232         schedule();
 233         remove_wait_queue(p, &wait);
 234         restore_flags(flags);
 235 }
 236 
 237 void interruptible_sleep_on(struct wait_queue **p)
     /*  */
 238 {
 239         __sleep_on(p,TASK_INTERRUPTIBLE);
 240 }
 241 
 242 void sleep_on(struct wait_queue **p)
     /*  */
 243 {
 244         __sleep_on(p,TASK_UNINTERRUPTIBLE);
 245 }
 246 
 247 /*
 248  * OK, here are some floppy things that shouldn't be in the kernel
 249  * proper. They are here because the floppy needs a timer, and this
 250  * was the easiest way of doing it.
 251  */
 252 static struct wait_queue * wait_motor[4] = {NULL,NULL,NULL,NULL};
 253 static int  mon_timer[4]={0,0,0,0};
 254 static int moff_timer[4]={0,0,0,0};
 255 unsigned char current_DOR = 0x0C;
 256 
 257 int ticks_to_floppy_on(unsigned int nr)
     /*  */
 258 {
 259         extern unsigned char selected;
 260         unsigned char mask = 0x10 << nr;
 261 
 262         if (nr>3)
 263                 panic("floppy_on: nr>3");
 264         moff_timer[nr]=10000;           /* 100 s = very big :-) */
 265         cli();                          /* use floppy_off to turn it off */
 266         mask |= current_DOR;
 267         if (!selected) {
 268                 mask &= 0xFC;
 269                 mask |= nr;
 270         }
 271         if (mask != current_DOR) {
 272                 outb(mask,FD_DOR);
 273                 if ((mask ^ current_DOR) & 0xf0)
 274                         mon_timer[nr] = HZ/2;
 275                 else if (mon_timer[nr] < 2)
 276                         mon_timer[nr] = 2;
 277                 current_DOR = mask;
 278         }
 279         sti();
 280         return mon_timer[nr];
 281 }
 282 
 283 void floppy_off(unsigned int nr)
     /*  */
 284 {
 285         moff_timer[nr]=3*HZ;
 286 }
 287 
 288 void do_floppy_timer(void)
     /*  */
 289 {
 290         int i;
 291         unsigned char mask = 0x10;
 292 
 293         for (i=0 ; i<4 ; i++,mask <<= 1) {
 294                 if (!(mask & current_DOR))
 295                         continue;
 296                 if (mon_timer[i]) {
 297                         if (!--mon_timer[i])
 298                                 wake_up(i+wait_motor);
 299                 } else if (!moff_timer[i]) {
 300                         current_DOR &= ~mask;
 301                         outb(current_DOR,FD_DOR);
 302                 } else
 303                         moff_timer[i]--;
 304         }
 305 }
 306 
 307 #define TIME_REQUESTS 64
 308 
 309 static struct timer_list {
 310         long jiffies;
 311         void (*fn)();
 312         struct timer_list * next;
 313 } timer_list[TIME_REQUESTS] = { { 0, NULL, NULL }, };
 314 
 315 static struct timer_list * next_timer = NULL;
 316 
 317 void add_timer(long jiffies, void (*fn)(void))
     /*  */
 318 {
 319         struct timer_list * p;
 320         unsigned long flags;
 321 
 322         if (!fn)
 323                 return;
 324         save_flags(flags);
 325         cli();
 326         if (jiffies <= 0)
 327                 (fn)();
 328         else {
 329                 for (p = timer_list ; p < timer_list + TIME_REQUESTS ; p++)
 330                         if (!p->fn)
 331                                 break;
 332                 if (p >= timer_list + TIME_REQUESTS)
 333                         panic("No more time requests free");
 334                 p->fn = fn;
 335                 p->jiffies = jiffies;
 336                 p->next = next_timer;
 337                 next_timer = p;
 338                 while (p->next && p->next->jiffies < p->jiffies) {
 339                         p->jiffies -= p->next->jiffies;
 340                         fn = p->fn;
 341                         p->fn = p->next->fn;
 342                         p->next->fn = fn;
 343                         jiffies = p->jiffies;
 344                         p->jiffies = p->next->jiffies;
 345                         p->next->jiffies = jiffies;
 346                         p = p->next;
 347                 }
 348                 if (p->next)
 349                         p->next->jiffies -= p->jiffies;
 350         }
 351         restore_flags(flags);
 352 }
 353 
 354 unsigned long timer_active = 0;
 355 struct timer_struct timer_table[32];
 356 
 357 /*
 358  * Hmm.. Changed this, as the GNU make sources (load.c) seems to
 359  * imply that avenrun[] is the standard name for this kind of thing.
 360  * Nothing else seems to be standardized: the fractional size etc
 361  * all seem to differ on different machines.
 362  */
 363 unsigned long avenrun[3] = { 0,0,0 };
 364 
 365 /*
 366  * Nr of active tasks - counted in fixed-point numbers
 367  */
 368 static unsigned long count_active_tasks(void)
     /*  */
 369 {
 370         struct task_struct **p;
 371         unsigned long nr = 0;
 372 
 373         for(p = &LAST_TASK; p > &FIRST_TASK; --p)
 374                 if (*p && (*p)->state == TASK_RUNNING)
 375                         nr += FIXED_1;
 376         return nr;
 377 }
 378 
 379 static inline void calc_load(void)
     /*  */
 380 {
 381         unsigned long active_tasks; /* fixed-point */
 382         static int count = LOAD_FREQ;
 383 
 384         if (count-- > 0)
 385                 return;
 386         count = LOAD_FREQ;
 387         active_tasks = count_active_tasks();
 388         CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 389         CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 390         CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 391 }
 392 
 393 /*
 394  * The int argument is really a (struct pt_regs *), in case the
 395  * interrupt wants to know from where it was called. The timer
 396  * irq uses this to decide if it should update the user or system
 397  * times.
 398  */
 399 static void do_timer(struct pt_regs * regs)
     /*  */
 400 {
 401         unsigned long mask;
 402         struct timer_struct *tp = timer_table+0;
 403         struct task_struct ** task_p;
 404 
 405         jiffies++;
 406         calc_load();
 407         if ((VM_MASK & regs->eflags) || (3 & regs->cs)) {
 408                 current->utime++;
 409                 /* Update ITIMER_VIRT for current task if not in a system call */
 410                 if (current->it_virt_value && !(--current->it_virt_value)) {
 411                         current->it_virt_value = current->it_virt_incr;
 412                         send_sig(SIGVTALRM,current,1);
 413                 }
 414         } else {
 415                 current->stime++;
 416 #ifdef CONFIG_PROFILE
 417                 if (prof_buffer && current != task[0]) {
 418                         unsigned long eip = regs->eip;
 419                         eip >>= 2;
 420                         if (eip < prof_len)
 421                                 prof_buffer[eip]++;
 422                 }
 423 #endif
 424         }
 425         if (current == task[0] || (--current->counter)<=0) {
 426                 current->counter=0;
 427                 need_resched = 1;
 428         }
 429         /* Update ITIMER_REAL for every task */
 430         for (task_p = &LAST_TASK; task_p >= &FIRST_TASK; task_p--)
 431                 if (*task_p && (*task_p)->it_real_value
 432                         && !(--(*task_p)->it_real_value)) {
 433                         send_sig(SIGALRM,*task_p,1);
 434                         (*task_p)->it_real_value = (*task_p)->it_real_incr;
 435                         need_resched = 1;
 436                 }
 437         /* Update ITIMER_PROF for the current task */
 438         if (current->it_prof_value && !(--current->it_prof_value)) {
 439                 current->it_prof_value = current->it_prof_incr;
 440                 send_sig(SIGPROF,current,1);
 441         }
 442         for (mask = 1 ; mask ; tp++,mask += mask) {
 443                 if (mask > timer_active)
 444                         break;
 445                 if (!(mask & timer_active))
 446                         continue;
 447                 if (tp->expires > jiffies)
 448                         continue;
 449                 timer_active &= ~mask;
 450                 tp->fn();
 451                 sti();
 452         }
 453         if (next_timer) {
 454                 next_timer->jiffies--;
 455                 while (next_timer && next_timer->jiffies <= 0) {
 456                         void (*fn)(void);
 457                         
 458                         fn = next_timer->fn;
 459                         next_timer->fn = NULL;
 460                         next_timer = next_timer->next;
 461                         (fn)();
 462                 }
 463         }
 464         if (current_DOR & 0xf0)
 465                 do_floppy_timer();
 466 }
 467 
 468 int sys_alarm(long seconds)
     /*  */
 469 {
 470         extern int _setitimer(int, struct itimerval *, struct itimerval *);
 471         struct itimerval new, old;
 472 
 473         new.it_interval.tv_sec = new.it_interval.tv_usec = 0;
 474         new.it_value.tv_sec = seconds;
 475         new.it_value.tv_usec = 0;
 476         _setitimer(ITIMER_REAL, &new, &old);
 477         return(old.it_value.tv_sec + (old.it_value.tv_usec / 1000000));
 478 }
 479 
 480 int sys_getpid(void)
     /*  */
 481 {
 482         return current->pid;
 483 }
 484 
 485 int sys_getppid(void)
     /*  */
 486 {
 487         return current->p_pptr->pid;
 488 }
 489 
 490 int sys_getuid(void)
     /*  */
 491 {
 492         return current->uid;
 493 }
 494 
 495 int sys_geteuid(void)
     /*  */
 496 {
 497         return current->euid;
 498 }
 499 
 500 int sys_getgid(void)
     /*  */
 501 {
 502         return current->gid;
 503 }
 504 
 505 int sys_getegid(void)
     /*  */
 506 {
 507         return current->egid;
 508 }
 509 
 510 int sys_nice(long increment)
     /*  */
 511 {
 512         if (increment < 0 && !suser())
 513                 return -EPERM;
 514         if (increment >= current->priority)
 515                 increment = current->priority-1;
 516         current->priority -= increment;
 517         return 0;
 518 }
 519 
 520 static void show_task(int nr,struct task_struct * p)
     /*  */
 521 {
 522         int i, j;
 523         unsigned char * stack;
 524 
 525         printk("%d: pid=%d, state=%d, father=%d, child=%d, ",(p == current)?-nr:nr,p->pid,
 526                 p->state, p->p_pptr->pid, p->p_cptr ? p->p_cptr->pid : -1);
 527         i = 0;
 528         j = 4096;
 529         if (!(stack = (char *) p->kernel_stack_page)) {
 530                 stack = (char *) init_kernel_stack;
 531                 j = sizeof(init_kernel_stack);
 532         }
 533         while (i<j && !*(stack++))
 534                 i++;
 535         printk("%d/%d chars free in kstack\n\r",i,j);
 536         printk("   PC=%08X.", *(1019 + (unsigned long *) p));
 537         if (p->p_ysptr || p->p_osptr) 
 538                 printk("   Younger sib=%d, older sib=%d\n\r", 
 539                         p->p_ysptr ? p->p_ysptr->pid : -1,
 540                         p->p_osptr ? p->p_osptr->pid : -1);
 541         else
 542                 printk("\n\r");
 543 }
 544 
 545 void show_state(void)
     /*  */
 546 {
 547         int i;
 548 
 549         printk("\rTask-info:\n\r");
 550         for (i=0 ; i<NR_TASKS ; i++)
 551                 if (task[i])
 552                         show_task(i,task[i]);
 553 }
 554 
 555 void sched_init(void)
     /*  */
 556 {
 557         int i;
 558         struct desc_struct * p;
 559 
 560         if (sizeof(struct sigaction) != 16)
 561                 panic("Struct sigaction MUST be 16 bytes");
 562         set_tss_desc(gdt+FIRST_TSS_ENTRY,&init_task.tss);
 563         set_ldt_desc(gdt+FIRST_LDT_ENTRY,&init_task.ldt);
 564         set_system_gate(0x80,&system_call);
 565         p = gdt+2+FIRST_TSS_ENTRY;
 566         for(i=1 ; i<NR_TASKS ; i++) {
 567                 task[i] = NULL;
 568                 p->a=p->b=0;
 569                 p++;
 570                 p->a=p->b=0;
 571                 p++;
 572         }
 573 /* Clear NT, so that we won't have troubles with that later on */
 574         __asm__("pushfl ; andl $0xffffbfff,(%esp) ; popfl");
 575         load_TR(0);
 576         load_ldt(0);
 577         outb_p(0x36,0x43);              /* binary, mode 3, LSB/MSB, ch 0 */
 578         outb_p(LATCH & 0xff , 0x40);    /* LSB */
 579         outb(LATCH >> 8 , 0x40);        /* MSB */
 580         request_irq(TIMER_IRQ,(void (*)(int)) do_timer);
 581 }
/* */
root/kernel/sched.c

DEFINITIONS
