Return to sched.c CVS log

Up to [GnuMach] / Gnu-Mach / linux / dev / kernel

Annotation of Gnu-Mach/linux/dev/kernel/sched.c, revision 1.1

1.1     ! root        1: /*
        !             2:  * Linux scheduling support.
        !             3:  *
        !             4:  * Copyright (C) 1996 The University of Utah and the Computer Systems
        !             5:  * Laboratory at the University of Utah (CSL)
        !             6:  *
        !             7:  * This program is free software; you can redistribute it and/or modify
        !             8:  * it under the terms of the GNU General Public License as published by
        !             9:  * the Free Software Foundation; either version 2, or (at your option)
        !            10:  * any later version.
        !            11:  *
        !            12:  * This program is distributed in the hope that it will be useful,
        !            13:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
        !            14:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !            15:  * GNU General Public License for more details.
        !            16:  *
        !            17:  * You should have received a copy of the GNU General Public License
        !            18:  * along with this program; if not, write to the Free Software
        !            19:  * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
        !            20:  *
        !            21:  *      Author: Shantanu Goel, University of Utah CSL
        !            22:  */
        !            23: 
        !            24: /*
        !            25:  *  linux/kernel/sched.c
        !            26:  *
        !            27:  *  Copyright (C) 1991, 1992  Linus Torvalds
        !            28:  */
        !            29: 
        !            30: #include <sys/types.h>
        !            31: #include <machine/spl.h>
        !            32: 
        !            33: #include <mach/boolean.h>
        !            34: 
        !            35: #include <kern/thread.h>
        !            36: #include <kern/sched_prim.h>
        !            37: 
        !            38: #define MACH_INCLUDE
        !            39: #include <linux/sched.h>
        !            40: #include <linux/timer.h>
        !            41: #include <linux/fs.h>
        !            42: #include <linux/blkdev.h>
        !            43: #include <linux/interrupt.h>
        !            44: 
        !            45: #include <asm/system.h>
        !            46: #include <asm/atomic.h>
        !            47: 
        !            48: int securelevel = 0;
        !            49: 
        !            50: extern void *alloc_contig_mem (unsigned, unsigned, unsigned, vm_page_t *);
        !            51: extern void free_contig_mem (vm_page_t);
        !            52: extern spl_t splhigh (void);
        !            53: extern spl_t splx (spl_t);
        !            54: extern void linux_soft_intr (void);
        !            55: extern int issig (void);
        !            56: extern int printf (const char *, ...);
        !            57: extern int linux_auto_config;
        !            58: 
        !            59: static void timer_bh (void);
        !            60: 
        !            61: DECLARE_TASK_QUEUE (tq_timer);
        !            62: DECLARE_TASK_QUEUE (tq_immediate);
        !            63: DECLARE_TASK_QUEUE (tq_scheduler);
        !            64: 
        !            65: static struct wait_queue **auto_config_queue;
        !            66: 
        !            67: static inline void
        !            68: handle_soft_intr (void)
        !            69: {
        !            70:   if (bh_active & bh_mask)
        !            71:     {
        !            72:       intr_count = 1;
        !            73:       linux_soft_intr ();
        !            74:       intr_count = 0;
        !            75:     }
        !            76: }
        !            77: 
        !            78: static void
        !            79: tqueue_bh (void)
        !            80: {
        !            81:   run_task_queue(&tq_timer);
        !            82: }
        !            83: 
        !            84: static void
        !            85: immediate_bh (void)
        !            86: {
        !            87:   run_task_queue (&tq_immediate);
        !            88: }
        !            89: 
        !            90: void
        !            91: add_wait_queue (struct wait_queue **q, struct wait_queue *wait)
        !            92: {
        !            93:   unsigned long flags;
        !            94: 
        !            95:   if (! linux_auto_config)
        !            96:     {
        !            97:       save_flags (flags);
        !            98:       cli ();
        !            99:       assert_wait ((event_t) q, FALSE);
        !           100:       restore_flags (flags);
        !           101:       return;
        !           102:     }
        !           103: 
        !           104:   if (auto_config_queue)
        !           105:     printf ("add_wait_queue: queue not empty\n");
        !           106:   auto_config_queue = q;
        !           107: }
        !           108: 
        !           109: void
        !           110: remove_wait_queue (struct wait_queue **q, struct wait_queue *wait)
        !           111: {
        !           112:   unsigned long flags;
        !           113: 
        !           114:   if (! linux_auto_config)
        !           115:     {
        !           116:       save_flags (flags);
        !           117:       thread_wakeup ((event_t) q);
        !           118:       restore_flags (flags);
        !           119:       return;
        !           120:     }
        !           121: 
        !           122:   auto_config_queue = NULL;
        !           123: }
        !           124: 
        !           125: static inline int
        !           126: waking_non_zero (struct semaphore *sem)
        !           127: {
        !           128:   int ret;
        !           129:   unsigned long flags;
        !           130: 
        !           131:   get_buzz_lock (&sem->lock);
        !           132:   save_flags (flags);
        !           133:   cli ();
        !           134: 
        !           135:   if ((ret = (sem->waking > 0)))
        !           136:     sem->waking--;
        !           137: 
        !           138:   restore_flags (flags);
        !           139:   give_buzz_lock (&sem->lock);
        !           140:   return ret;
        !           141: }
        !           142: 
        !           143: void
        !           144: __up (struct semaphore *sem)
        !           145: {
        !           146:   atomic_inc (&sem->waking);
        !           147:   wake_up (&sem->wait);
        !           148: }
        !           149: 
        !           150: int
        !           151: __do_down (struct semaphore *sem, int task_state)
        !           152: {
        !           153:   unsigned long flags;
        !           154:   int ret = 0;
        !           155:   int s;
        !           156:   
        !           157:   if (!linux_auto_config)
        !           158:     {
        !           159:       save_flags (flags);
        !           160:       s = splhigh ();
        !           161:       for (;;)
        !           162:        {
        !           163:          if (waking_non_zero (sem))
        !           164:            break;
        !           165: 
        !           166:          if (task_state == TASK_INTERRUPTIBLE && issig ())
        !           167:            {
        !           168:              ret = -LINUX_EINTR;
        !           169:              atomic_inc (&sem->count);
        !           170:              break;
        !           171:            }
        !           172: 
        !           173:          assert_wait ((event_t) &sem->wait,
        !           174:                       task_state == TASK_INTERRUPTIBLE ? TRUE : FALSE);
        !           175:          splx (s);
        !           176:          schedule ();
        !           177:          s = splhigh ();
        !           178:        }
        !           179:       splx (s);
        !           180:       restore_flags (flags);
        !           181:       return ret;
        !           182:     }
        !           183: 
        !           184:   while (!waking_non_zero (sem))
        !           185:     {
        !           186:       if (task_state == TASK_INTERRUPTIBLE && issig ())
        !           187:        {
        !           188:          ret = -LINUX_EINTR;
        !           189:          atomic_inc (&sem->count);
        !           190:          break;
        !           191:        }
        !           192:       schedule ();
        !           193:     }
        !           194: 
        !           195:   return ret;
        !           196: }
        !           197: 
        !           198: void
        !           199: __down (struct semaphore *sem)
        !           200: {
        !           201:   __do_down(sem, TASK_UNINTERRUPTIBLE);
        !           202: }
        !           203: 
        !           204: int
        !           205: __down_interruptible (struct semaphore *sem)
        !           206: {
        !           207:   return __do_down (sem, TASK_INTERRUPTIBLE); 
        !           208: }
        !           209: 
        !           210: void
        !           211: __sleep_on (struct wait_queue **q, int state)
        !           212: {
        !           213:   unsigned long flags;
        !           214: 
        !           215:   if (!q)
        !           216:     return;
        !           217:   save_flags (flags);
        !           218:   if (!linux_auto_config)
        !           219:     {
        !           220:       assert_wait ((event_t) q, state == TASK_INTERRUPTIBLE ? TRUE : FALSE);
        !           221:       sti ();
        !           222:       schedule ();
        !           223:       restore_flags (flags);
        !           224:       return;
        !           225:     }
        !           226:   
        !           227:   add_wait_queue (q, NULL);
        !           228:   sti ();
        !           229:   while (auto_config_queue)
        !           230:     schedule ();
        !           231:   restore_flags (flags);
        !           232: }
        !           233: 
        !           234: void
        !           235: sleep_on (struct wait_queue **q)
        !           236: {
        !           237:   __sleep_on (q, TASK_UNINTERRUPTIBLE);
        !           238: }
        !           239: 
        !           240: void
        !           241: interruptible_sleep_on (struct wait_queue **q)
        !           242: {
        !           243:   __sleep_on (q, TASK_INTERRUPTIBLE);
        !           244: }
        !           245: 
        !           246: void
        !           247: wake_up (struct wait_queue **q)
        !           248: {
        !           249:   unsigned long flags;
        !           250: 
        !           251:   if (! linux_auto_config)
        !           252:     {
        !           253:       if (q != &wait_for_request)      /* ??? by OKUJI Yoshinori. */
        !           254:        {
        !           255:          save_flags (flags);
        !           256:          thread_wakeup ((event_t) q);
        !           257:          restore_flags (flags);
        !           258:        }
        !           259:       return;
        !           260:     }
        !           261: 
        !           262:   if (auto_config_queue == q)
        !           263:     auto_config_queue = NULL;
        !           264: }
        !           265: 
        !           266: void
        !           267: __wait_on_buffer (struct buffer_head *bh)
        !           268: {
        !           269:   unsigned long flags;
        !           270: 
        !           271:   save_flags (flags);
        !           272:   if (! linux_auto_config)
        !           273:     {
        !           274:       while (1)
        !           275:        {
        !           276:          cli ();
        !           277:          run_task_queue (&tq_disk);
        !           278:          if (! buffer_locked (bh))
        !           279:            break;
        !           280:          bh->b_wait = (struct wait_queue *) 1;
        !           281:          assert_wait ((event_t) bh, FALSE);
        !           282:          sti ();
        !           283:          schedule ();
        !           284:        }
        !           285:       restore_flags (flags);
        !           286:       return;
        !           287:     }
        !           288: 
        !           289:   sti ();
        !           290:   while (buffer_locked (bh))
        !           291:     {
        !           292:       run_task_queue (&tq_disk);
        !           293:       schedule ();
        !           294:     }
        !           295:   restore_flags (flags);
        !           296: }
        !           297: 
        !           298: void
        !           299: unlock_buffer (struct buffer_head *bh)
        !           300: {
        !           301:   unsigned long flags;
        !           302: 
        !           303:   save_flags (flags);
        !           304:   cli ();
        !           305:   clear_bit (BH_Lock, &bh->b_state);
        !           306:   if (bh->b_wait && ! linux_auto_config)
        !           307:     {
        !           308:       bh->b_wait = NULL;
        !           309:       thread_wakeup ((event_t) bh);
        !           310:     }
        !           311:   restore_flags (flags);
        !           312: }
        !           313: 
        !           314: void
        !           315: schedule (void)
        !           316: {
        !           317:   if (intr_count)
        !           318:     printk ("Aiee: scheduling in interrupt %p\n",
        !           319:            __builtin_return_address (0));
        !           320:   
        !           321:   handle_soft_intr ();
        !           322:   run_task_queue (&tq_scheduler);
        !           323: 
        !           324:   if (!linux_auto_config)
        !           325:     thread_block (0);
        !           326: }
        !           327: 
        !           328: void
        !           329: cdrom_sleep (int t)
        !           330: {
        !           331:   int xxx;
        !           332: 
        !           333:   assert_wait ((event_t) &xxx, TRUE);
        !           334:   thread_set_timeout (t);
        !           335:   schedule ();
        !           336: }
        !           337: 
        !           338: void
        !           339: linux_sched_init (void)
        !           340: {
        !           341:   /*
        !           342:    * Install software interrupt handlers.
        !           343:    */
        !           344:   init_bh (TIMER_BH, timer_bh);
        !           345:   init_bh (TQUEUE_BH, tqueue_bh);
        !           346:   init_bh (IMMEDIATE_BH, immediate_bh);
        !           347: }
        !           348: 
        !           349: /*
        !           350:  * Linux timers.
        !           351:  *
        !           352:  * Copyright (C) 1996 The University of Utah and the Computer Systems
        !           353:  * Laboratory at the University of Utah (CSL)
        !           354:  *
        !           355:  * This program is free software; you can redistribute it and/or modify
        !           356:  * it under the terms of the GNU General Public License as published by
        !           357:  * the Free Software Foundation; either version 2, or (at your option)
        !           358:  * any later version.
        !           359:  *
        !           360:  * This program is distributed in the hope that it will be useful,
        !           361:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
        !           362:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        !           363:  * GNU General Public License for more details.
        !           364:  *
        !           365:  * You should have received a copy of the GNU General Public License
        !           366:  * along with this program; if not, write to the Free Software
        !           367:  * Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
        !           368:  *
        !           369:  *      Author: Shantanu Goel, University of Utah CSL
        !           370:  */
        !           371: 
        !           372: unsigned long volatile jiffies = 0;
        !           373: 
        !           374: /*
        !           375:  * Mask of active timers.
        !           376:  */
        !           377: unsigned long timer_active = 0;
        !           378: 
        !           379: /*
        !           380:  * List of timeout routines.
        !           381:  */
        !           382: struct timer_struct timer_table[32];
        !           383: 
        !           384: #define TVN_BITS 6
        !           385: #define TVR_BITS 8
        !           386: #define TVN_SIZE (1 << TVN_BITS)
        !           387: #define TVR_SIZE (1 << TVR_BITS)
        !           388: #define TVN_MASK (TVN_SIZE - 1)
        !           389: #define TVR_MASK (TVR_SIZE - 1)
        !           390: 
        !           391: #define SLOW_BUT_DEBUGGING_TIMERS 0
        !           392: 
        !           393: struct timer_vec
        !           394:   {
        !           395:     int index;
        !           396:     struct timer_list *vec[TVN_SIZE];
        !           397:   };
        !           398: 
        !           399: struct timer_vec_root
        !           400:   {
        !           401:     int index;
        !           402:     struct timer_list *vec[TVR_SIZE];
        !           403:   };
        !           404: 
        !           405: static struct timer_vec tv5 =
        !           406: {0};
        !           407: static struct timer_vec tv4 =
        !           408: {0};
        !           409: static struct timer_vec tv3 =
        !           410: {0};
        !           411: static struct timer_vec tv2 =
        !           412: {0};
        !           413: static struct timer_vec_root tv1 =
        !           414: {0};
        !           415: 
        !           416: static struct timer_vec *const tvecs[] =
        !           417: {
        !           418:   (struct timer_vec *) &tv1, &tv2, &tv3, &tv4, &tv5
        !           419: };
        !           420: 
        !           421: #define NOOF_TVECS (sizeof(tvecs) / sizeof(tvecs[0]))
        !           422: 
        !           423: static unsigned long timer_jiffies = 0;
        !           424: 
        !           425: static inline void
        !           426: insert_timer (struct timer_list *timer, struct timer_list **vec, int idx)
        !           427: {
        !           428:   if ((timer->next = vec[idx]))
        !           429:     vec[idx]->prev = timer;
        !           430:   vec[idx] = timer;
        !           431:   timer->prev = (struct timer_list *) &vec[idx];
        !           432: }
        !           433: 
        !           434: static inline void
        !           435: internal_add_timer (struct timer_list *timer)
        !           436: {
        !           437:   /*
        !           438:    * must be cli-ed when calling this
        !           439:    */
        !           440:   unsigned long expires = timer->expires;
        !           441:   unsigned long idx = expires - timer_jiffies;
        !           442: 
        !           443:   if (idx < TVR_SIZE)
        !           444:     {
        !           445:       int i = expires & TVR_MASK;
        !           446:       insert_timer (timer, tv1.vec, i);
        !           447:     }
        !           448:   else if (idx < 1 << (TVR_BITS + TVN_BITS))
        !           449:     {
        !           450:       int i = (expires >> TVR_BITS) & TVN_MASK;
        !           451:       insert_timer (timer, tv2.vec, i);
        !           452:     }
        !           453:   else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS))
        !           454:     {
        !           455:       int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK;
        !           456:       insert_timer (timer, tv3.vec, i);
        !           457:     }
        !           458:   else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS))
        !           459:     {
        !           460:       int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK;
        !           461:       insert_timer (timer, tv4.vec, i);
        !           462:     }
        !           463:   else if (expires < timer_jiffies)
        !           464:     {
        !           465:       /* can happen if you add a timer with expires == jiffies,
        !           466:        * or you set a timer to go off in the past
        !           467:        */
        !           468:       insert_timer (timer, tv1.vec, tv1.index);
        !           469:     }
        !           470:   else if (idx < 0xffffffffUL)
        !           471:     {
        !           472:       int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
        !           473:       insert_timer (timer, tv5.vec, i);
        !           474:     }
        !           475:   else
        !           476:     {
        !           477:       /* Can only get here on architectures with 64-bit jiffies */
        !           478:       timer->next = timer->prev = timer;
        !           479:     }
        !           480: }
        !           481: 
        !           482: void
        !           483: add_timer (struct timer_list *timer)
        !           484: {
        !           485:   unsigned long flags;
        !           486: 
        !           487:   save_flags (flags);
        !           488:   cli ();
        !           489: #if SLOW_BUT_DEBUGGING_TIMERS
        !           490:   if (timer->next || timer->prev)
        !           491:     {
        !           492:       printk ("add_timer() called with non-zero list from %p\n",
        !           493:              __builtin_return_address (0));
        !           494:       goto out;
        !           495:     }
        !           496: #endif
        !           497:   internal_add_timer (timer);
        !           498: #if SLOW_BUT_DEBUGGING_TIMERS
        !           499: out:
        !           500: #endif
        !           501:   restore_flags (flags);
        !           502: }
        !           503: 
        !           504: static inline int
        !           505: detach_timer (struct timer_list *timer)
        !           506: {
        !           507:   int ret = 0;
        !           508:   struct timer_list *next, *prev;
        !           509: 
        !           510:   next = timer->next;
        !           511:   prev = timer->prev;
        !           512:   if (next)
        !           513:     {
        !           514:       next->prev = prev;
        !           515:     }
        !           516:   if (prev)
        !           517:     {
        !           518:       ret = 1;
        !           519:       prev->next = next;
        !           520:     }
        !           521:   return ret;
        !           522: }
        !           523: 
        !           524: int
        !           525: del_timer (struct timer_list *timer)
        !           526: {
        !           527:   int ret;
        !           528:   unsigned long flags;
        !           529: 
        !           530:   save_flags (flags);
        !           531:   cli ();
        !           532:   ret = detach_timer (timer);
        !           533:   timer->next = timer->prev = 0;
        !           534:   restore_flags (flags);
        !           535:   return ret;
        !           536: }
        !           537: 
        !           538: static inline void
        !           539: run_old_timers (void)
        !           540: {
        !           541:   struct timer_struct *tp;
        !           542:   unsigned long mask;
        !           543: 
        !           544:   for (mask = 1, tp = timer_table + 0; mask; tp++, mask += mask)
        !           545:     {
        !           546:       if (mask > timer_active)
        !           547:        break;
        !           548:       if (!(mask & timer_active))
        !           549:        continue;
        !           550:       if (tp->expires > jiffies)
        !           551:        continue;
        !           552:       timer_active &= ~mask;
        !           553:       tp->fn ();
        !           554:       sti ();
        !           555:     }
        !           556: }
        !           557: 
        !           558: static inline void
        !           559: cascade_timers (struct timer_vec *tv)
        !           560: {
        !           561:   /* cascade all the timers from tv up one level */
        !           562:   struct timer_list *timer;
        !           563: 
        !           564:   timer = tv->vec[tv->index];
        !           565:   /*
        !           566:    * We are removing _all_ timers from the list, so we don't  have to
        !           567:    * detach them individually, just clear the list afterwards.
        !           568:    */
        !           569:   while (timer)
        !           570:     {
        !           571:       struct timer_list *tmp = timer;
        !           572:       timer = timer->next;
        !           573:       internal_add_timer (tmp);
        !           574:     }
        !           575:   tv->vec[tv->index] = NULL;
        !           576:   tv->index = (tv->index + 1) & TVN_MASK;
        !           577: }
        !           578: 
        !           579: static inline void
        !           580: run_timer_list (void)
        !           581: {
        !           582:   cli ();
        !           583:   while ((long) (jiffies - timer_jiffies) >= 0)
        !           584:     {
        !           585:       struct timer_list *timer;
        !           586: 
        !           587:       if (!tv1.index)
        !           588:        {
        !           589:          int n = 1;
        !           590: 
        !           591:          do
        !           592:            {
        !           593:              cascade_timers (tvecs[n]);
        !           594:            }
        !           595:          while (tvecs[n]->index == 1 && ++n < NOOF_TVECS);
        !           596:        }
        !           597:       while ((timer = tv1.vec[tv1.index]))
        !           598:        {
        !           599:          void (*fn) (unsigned long) = timer->function;
        !           600:          unsigned long data = timer->data;
        !           601: 
        !           602:          detach_timer (timer);
        !           603:          timer->next = timer->prev = NULL;
        !           604:          sti ();
        !           605:          fn (data);
        !           606:          cli ();
        !           607:        }
        !           608:       ++timer_jiffies;
        !           609:       tv1.index = (tv1.index + 1) & TVR_MASK;
        !           610:     }
        !           611:   sti ();
        !           612: }
        !           613: 
        !           614: /*
        !           615:  * Timer software interrupt handler.
        !           616:  */
        !           617: static void
        !           618: timer_bh (void)
        !           619: {
        !           620:   run_old_timers ();
        !           621:   run_timer_list ();
        !           622: }
        !           623: 
        !           624: #if 0
        !           625: int linux_timer_print = 0;
        !           626: #endif
        !           627: 
        !           628: /*
        !           629:  * Timer interrupt handler.
        !           630:  */
        !           631: void
        !           632: linux_timer_intr (void)
        !           633: {
        !           634:   (*(unsigned long *) &jiffies)++;
        !           635:   mark_bh (TIMER_BH);
        !           636:   if (tq_timer)
        !           637:     mark_bh (TQUEUE_BH);
        !           638: #if 0
        !           639:   if (linux_timer_print)
        !           640:     printf ("linux_timer_intr: pic_mask[0] %x\n", pic_mask[0]);
        !           641: #endif
        !           642: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.