/*
 * linux/kernel/sched.c
 *
 * (C) 1991 Linus Torvalds
 */

/*
 * 'sched.c' is the main kernel file. It contains scheduling primitives
 * (sleep_on, wakeup, schedule etc) as well as a number of simple system
 * call functions (type getpid(), which just extracts a field from
 * current-task
 */
/*
 * 'sched.c'ҪںļайصȵĻ(sleep_onwakeupschedule )Լ
 * һЩ򵥵ϵͳúgetpid()ӵǰлȡһֶΣ
 */
#include <linux/sched.h>	// ȳͷļṹtask_struct1 ʼ
// ݡһЩԺʽйúͻȡ
// Ƕʽຯ
#include <linux/kernel.h>	// ںͷļһЩں˳úԭζ塣
#include <linux/sys.h>		// ϵͳͷļ72 ϵͳC ,'sys_'ͷ
#include <linux/fdreg.h>	// ͷļ̿һЩ塣
#include <asm/system.h>		// ϵͳͷļû޸/жŵȵǶʽꡣ
#include <asm/io.h>		// io ͷļӲ˿/䡣
#include <asm/segment.h>	// βͷļйضμĴǶʽຯ

#include <signal.h>		// źͷļźŷųsigaction ṹԭ͡

#define _S(nr) (1<<((nr)-1))	// ȡźnr źλͼжӦλĶֵźű1-32
// ź5 λͼֵ = 1<<(5-1) = 16 = 00010000b
#define _BLOCKABLE (~(_S(SIGKILL) | _S(SIGSTOP)))	// SIGKILL SIGSTOP ź
// (10111111111011111111b)

// ʾnr Ľ̺š״̬ں˶ջֽԼ
void
show_task (int nr, struct task_struct *p)
{
  int i, j = 4096 - sizeof (struct task_struct);

  printk ("%d: pid=%d, state=%d, ", nr, p->pid, p->state);
  i = 0;
  while (i < j && !((char *) (p + 1))[i])	// ָݽṹԺ0 ֽ
    i++;
  printk ("%d (of %d) chars free in kernel stack\n\r", i, j);
}

// ʾš̺š״̬ں˶ջֽԼ
void
show_stat (void)
{
  int i;

  for (i = 0; i < NR_TASKS; i++)	// NR_TASKS ϵͳɵ̣64 
    if (task[i])		// include/kernel/sched.h 4 С
      show_task (i, task[i]);
}

// ÿʱƬĵδ?
#define LATCH (1193180/HZ)

extern void mem_use (void);	// [??]ûκεطøú

extern int timer_interrupt (void);	// ʱжϴ(kernel/system_call.s,176)
extern int system_call (void);	// ϵͳжϴ(kernel/system_call.s,80)

union task_union
{				// (ṹԱstack ַԱ)
  struct task_struct task;	// ΪһݽṹջͬһڴҳУ
  char stack[PAGE_SIZE];	// ӶջμĴss Իݶѡ
};

static union task_union init_task = { INIT_TASK, };	// ʼ(sched.h )

long volatile jiffies = 0;	// ӿʼĵδʱֵ10ms/δ𣩡
// ǰ޶volatileӢĽױ䡢ȶ˼Ҫgcc ҪԸñŻ
// ҲҪŲλãΪҲĳ޸ֵ
long startup_time = 0;		// ʱ䡣1970:0:0:0 ʼʱ
struct task_struct *current = &(init_task.task);	// ǰָ루ʼΪʼ񣩡
struct task_struct *last_task_used_math = NULL;	// ʹùЭָ롣

struct task_struct *task[NR_TASKS] = { &(init_task.task), };	// ָ顣

long user_stack[PAGE_SIZE >> 2];	// ϵͳջָ룬4Kָָһ

// ýṹöջss:espݶѡָ룩head.s23 С
struct
{
  long *a;
  short b;
}
stack_start =
{
&user_stack[PAGE_SIZE >> 2], 0x10};

/*
 * 'math_state_restore()' saves the current math information in the
 * old math state array, and gets the new ones from the current task
 */
/*
 * ǰЭݱ浽Э״̬УǰЭ
 * ݼؽЭ
 */
// 񱻵ȽԺ󣬸úԱԭЭ״̬ģָµȽ
// ǰЭִ״̬
void
math_state_restore ()
{
  if (last_task_used_math == current)	// û򷵻(һǵǰ)
    return;			// ָ"һ"Ǹձȥ
  __asm__ ("fwait");		// ڷЭ֮ǰҪȷWAIT ָ
  if (last_task_used_math)
    {				// ϸʹЭ򱣴״̬
      __asm__ ("fnsave %0"::"m" (last_task_used_math->tss.i387));
    }
  last_task_used_math = current;	// ڣlast_task_used_math ָǰ
  // Աǰ񱻽ȥʱʹá
  if (current->used_math)
    {				// ǰùЭָ״̬
      __asm__ ("frstor %0"::"m" (current->tss.i387));
    }
  else
    {				// Ļ˵ǵһʹã
      __asm__ ("fninit"::);	// ǾЭʼ
      current->used_math = 1;	// ʹЭ־
    }
}

/*
 * 'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 * NOTE!! Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
/*
 * 'schedule()'ǵȺǸܺõĴ룡ûκɶ޸ģΪе
 * ¹ܹIO-߽紦ܺõӦȣֻһֵ⣬Ǿź
 * 롣
 * ע⣡0 Ǹ('idle')ֻеûʱŵܱɱ
 * Ҳ˯ߡ0 е״̬Ϣ'state'Ǵõġ
 */
void
schedule (void)
{
  int i, next, c;
  struct task_struct **p;	// ṹָָ롣

  /* check alarm, wake up any interruptible tasks that have got a signal */
  /* alarm̵ıʱֵκѵõźŵĿж */

  // һʼalarm
  for (p = &LAST_TASK; p > &FIRST_TASK; --p)
    if (*p)
      {
	// alarm ʱѾ(alarm<jiffies),źλͼSIGALRM źţȻalarm
	// jiffies ϵͳӿʼĵδ10ms/δ𣩡sched.h 139 С
	if ((*p)->alarm && (*p)->alarm < jiffies)
	  {
	    (*p)->signal |= (1 << (SIGALRM - 1));
	    (*p)->alarm = 0;
	  }
	// źλͼгź⻹źţڿж״̬Ϊ״̬
	// '~(_BLOCKABLE & (*p)->blocked)'ںԱźţSIGKILL SIGSTOP ܱ
	if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
	    (*p)->state == TASK_INTERRUPTIBLE)
	  (*p)->state = TASK_RUNNING;	//ΪִУ״̬
      }

  /* this is the scheduler proper: */
  /* ǵȳҪ */

  while (1)
    {
      c = -1;
      next = 0;
      i = NR_TASKS;
      p = &task[NR_TASKS];
      // δҲǴһʼѭۡȽÿ
      // ״̬counterʱĵݼδֵһֵʱ仹next 
      // ָĸš
      while (--i)
	{
	  if (!*--p)
	    continue;
	  if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
	    c = (*p)->counter, next = i;
	}
      // Ƚϵócounter ֵ0 Ľ˳124 пʼѭִл141 У
      if (c)
	break;
      // ͸ÿȨֵÿһcounter ֵȻص125 ±Ƚϡ
      // counter ֵļ㷽ʽΪcounter = counter /2 + priority[ұcounter=0??]
      for (p = &LAST_TASK; p > &FIRST_TASK; --p)
	if (*p)
	  (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
    }
  switch_to (next);		// лΪnext 񣬲֮
}

//// pause()ϵͳáתǰ״̬Ϊжϵĵȴ״̬µȡ
// ϵͳý½̽˯״ֱ̬յһźšźֹ̻ʹ̵
// һźŲֻеһźţźŲأpause()Ż᷵ء
// ʱpause()ֵӦ-1errno ΪEINTRﻹûȫʵֱ֣0.95 棩
int
sys_pause (void)
{
  current->state = TASK_INTERRUPTIBLE;
  schedule ();
  return 0;
}

// ѵǰΪжϵĵȴ״̬˯߶ͷָָǰ
// ֻȷػʱŻ᷵ءúṩ˽жϴ֮ͬơ
// *p ǷõȴĶͷָ롣μб˵
void
sleep_on (struct task_struct **p)
{
  struct task_struct *tmp;

  // ָЧ˳ָָĶNULLָ뱾Ϊ0)
  if (!p)
    return;
  if (current == &(init_task.task))	// ǰ0(impossible!)
    panic ("task[0] trying to sleep");
  tmp = *p;			// tmp ָѾڵȴϵ(еĻ)
  *p = current;			// ˯߶ͷĵȴָָǰ
  current->state = TASK_UNINTERRUPTIBLE;	// ǰΪжϵĵȴ״̬
  schedule ();			// µȡ
  // ֻеȴ񱻻ʱȳַصʾѱȷػѡ
  // ȻҶڵȴͬԴôԴʱбҪеȴԴĽ̡ú
  // Ƕ׵ãҲǶ׻еȴԴĽ̡ȻϵͳЩ̵µ
  // ӦĸʹԴҲЩ̾ϸڡ
  if (tmp)			// ڵȴҲΪ״̬ѣ
    tmp->state = 0;
}

// ǰΪжϵĵȴ״̬*p ָĵȴСμбsleep_on()˵
void
interruptible_sleep_on (struct task_struct **p)
{
  struct task_struct *tmp;

  if (!p)
    return;
  if (current == &(init_task.task))
    panic ("task[0] trying to sleep");
  tmp = *p;
  *p = current;
repeat:current->state = TASK_INTERRUPTIBLE;
  schedule ();
  // ȴлеȴ񣬲Ҷͷָָǵǰʱ򽫸õȴΪ
  // еľ״ִ̬еȳ򡣵ָ*p ָĲǵǰʱʾڵǰ񱻷
  // кµ񱻲ȴУˣȻǿжϵģӦִ
  // ĵȴ
  if (*p && *p != current)
    {
      (**p).state = 0;
      goto repeat;
    }
  // һӦ*p = tmpöͷָָȴ񣬷ڵǰ֮ǰ
  // ȴеĨˡμͼ4.3
  *p = NULL;
  if (tmp)
    tmp->state = 0;
}

// ָ*p
void
wake_up (struct task_struct **p)
{
  if (p && *p)
    {
      (**p).state = 0;		// ΪУ״̬
      *p = NULL;
    }
}

/*
 * OK, here are some floppy things that shouldn't be in the kernel
 * proper. They are here because the floppy needs a timer, and this
 * was the easiest way of doing it.
 */
/*
 * ˣ￪ʼһЩй̵ӳ򣬱Ӧ÷ں˵ҪеġǷ
 * ΪҪһʱӣİ취
 */
static struct task_struct *wait_motor[4] = { NULL, NULL, NULL, NULL };
static int mon_timer[4] = { 0, 0, 0, 0 };
static int moff_timer[4] = { 0, 0, 0, 0 };
unsigned char current_DOR = 0x0C;	// Ĵ(ֵDMA жϡFDC)

// ̵ָת״̬ӳٵδʱ䣩
// nr -- (0-3)ֵΪδ
int
ticks_to_floppy_on (unsigned int nr)
{
  extern unsigned char selected;	// ǰѡе̺(kernel/blk_drv/floppy.c,122)
  unsigned char mask = 0x10 << nr;	// ѡӦĴλ

  if (nr > 3)
    panic ("floppy_on: nr>3");	// 4 
  moff_timer[nr] = 10000;	/* 100 s = very big :-) */
  cli ();			/* use floppy_off to turn it off */
  mask |= current_DOR;
  // ǵǰȸλѡλȻöӦѡλ
  if (!selected)
    {
      mask &= 0xFC;
      mask |= nr;
    }
  // ĴĵǰֵҪֵͬFDC ˿ֵ(mask)
  // ҪﻹûӦʱֵ(HZ/2 = 0.5 50 δ)
  // ˺µǰĴֵcurrent_DOR
  if (mask != current_DOR)
    {
      outb (mask, FD_DOR);
      if ((mask ^ current_DOR) & 0xf0)
	mon_timer[nr] = HZ / 2;
      else if (mon_timer[nr] < 2)
	mon_timer[nr] = 2;
      current_DOR = mask;
    }
  sti ();
  return mon_timer[nr];
}

// ȴָʱ䡣
void
floppy_on (unsigned int nr)
{
  cli ();			// жϡ
  while (ticks_to_floppy_on (nr))	// ʱûһֱѵǰ
    sleep_on (nr + wait_motor);	// Ϊж˯״̬ȴеĶС
  sti ();			// жϡ
}

// ùرӦͣתʱ3 룩
void
floppy_off (unsigned int nr)
{
  moff_timer[nr] = 3 * HZ;
}

// ̶ʱӳ򡣸ʱֵرͣתʱֵӳʱӶʱ
// жбãÿһδ(10ms)һΣ￪ͣתʱֵĳ
// һͣתʱĴλλ
void
do_floppy_timer (void)
{
  int i;
  unsigned char mask = 0x10;

  for (i = 0; i < 4; i++, mask <<= 1)
    {
      if (!(mask & current_DOR))	// DOR ָ
	continue;
      if (mon_timer[i])
	{
	  if (!--mon_timer[i])
	    wake_up (i + wait_motor);	// ʱѽ̡
	}
      else if (!moff_timer[i])
	{			// ͣתʱ
	  current_DOR &= ~mask;	// λӦλ
	  outb (current_DOR, FD_DOR);	// Ĵ
	}
      else
	moff_timer[i]--;	// ͣתʱݼ
    }
}

#define TIME_REQUESTS 64	// 64 ʱ64 񣩡

// ʱṹͶʱ顣
static struct timer_list
{
  long jiffies;			// ʱδ
  void (*fn) ();		// ʱ
  struct timer_list *next;	// һʱ
}
timer_list[TIME_REQUESTS], *next_timer = NULL;

// ӶʱΪָĶʱֵ(δ)ӦĴָ롣
// jiffies C 10 Ƶĵδ*fn()- ʱʱ䵽ʱִеĺ
void
add_timer (long jiffies, void (*fn) (void))
{
  struct timer_list *p;

  // ʱָΪգ˳
  if (!fn)
    return;
  cli ();
  // ʱֵ<=0̵䴦򡣲ҸöʱС
  if (jiffies <= 0)
    (fn) ();
  else
    {
      // ӶʱУһ
      for (p = timer_list; p < timer_list + TIME_REQUESTS; p++)
	if (!p->fn)
	  break;
      // Ѿ˶ʱ飬ϵͳ?
      if (p >= timer_list + TIME_REQUESTS)
	panic ("No more time requests free");
      // ʱݽṹӦϢͷ
      p->fn = fn;
      p->jiffies = jiffies;
      p->next = next_timer;
      next_timer = p;
      // ʱֵСʱȥǰҪĵδڴʱʱֻҪ
      // 鿴ͷĵһĶʱǷڼɡ[[?? γûпȫ²Ķʱ
      // ֵ < ԭͷһʱֵʱҲӦýкĶʱֵȥµĵ1 Ķʱֵ]]
      while (p->next && p->next->jiffies < p->jiffies)
	{
	  p->jiffies -= p->next->jiffies;
	  fn = p->fn;
	  p->fn = p->next->fn;
	  p->next->fn = fn;
	  jiffies = p->jiffies;
	  p->jiffies = p->next->jiffies;
	  p->next->jiffies = jiffies;
	  p = p->next;
	}
    }
  sti ();
}

//// ʱжC kernel/system_call.s е_timer_interrupt176 Уá
// cpl ǵǰȨ0 30 ʾں˴ִС
// һִʱƬʱлִһʱ¹
void
do_timer (long cpl)
{
  extern int beepcount;		// ʱδ(kernel/chr_drv/console.c,697)
  extern void sysbeepstop (void);	// ر(kernel/chr_drv/console.c,691)

  // رշ(0x61 ڷλλ0 1λ0 8253
  // 2 Ĺλ1 )
  if (beepcount)
    if (!--beepcount)
      sysbeepstop ();

  // ǰȨ(cpl)Ϊ0ߣʾں˳ڹ򽫳ûʱstime 
  // cpl > 0ʾһûڹutime
  if (cpl)
    current->utime++;
  else
    current->stime++;

  // ûĶʱڣ1 ʱֵ1ѵ0ӦĴ
  // 򣬲ôָΪաȻȥʱ
  if (next_timer)
    {				// next_timer Ƕʱͷָ(270 )
      next_timer->jiffies--;
      while (next_timer && next_timer->jiffies <= 0)
	{
	  void (*fn) (void);	// һָ붨壡??

	  fn = next_timer->fn;
	  next_timer->fn = NULL;
	  next_timer = next_timer->next;
	  (fn) ();		// ô
	}
    }
  // ǰ̿FDC Ĵλλģ̶ִʱ(245 )
  if (current_DOR & 0xf0)
    do_floppy_timer ();
  if ((--current->counter) > 0)
    return;			// ʱ仹û꣬˳
  current->counter = 0;
  if (!cpl)
    return;			// ڳû򣬲counter ֵеȡ
  schedule ();
}

// ϵͳù - ñʱʱֵ()
// Ѿùalarm ֵ򷵻ؾֵ򷵻0
int
sys_alarm (long seconds)
{
  int old = current->alarm;

  if (old)
    old = (old - jiffies) / HZ;
  current->alarm = (seconds > 0) ? (jiffies + HZ * seconds) : 0;
  return (old);
}

// ȡǰ̺pid
int
sys_getpid (void)
{
  return current->pid;
}

// ȡ̺ppid
int
sys_getppid (void)
{
  return current->father;
}

// ȡûuid
int
sys_getuid (void)
{
  return current->uid;
}

// ȡeuid
int
sys_geteuid (void)
{
  return current->euid;
}

// ȡgid
int
sys_getgid (void)
{
  return current->gid;
}

// ȡegid
int
sys_getegid (void)
{
  return current->egid;
}

// ϵͳù -- ͶCPU ʹȨ˻?
// Ӧincrement 0Ļ,ʹȨ󣡣
int
sys_nice (long increment)
{
  if (current->priority - increment > 0)
    current->priority -= increment;
  return 0;
}

// ȳĳʼӳ
void
sched_init (void)
{
  int i;
  struct desc_struct *p;	// ṹָ롣

  if (sizeof (struct sigaction) != 16)	// sigaction Ǵйź״̬Ľṹ
    panic ("Struct sigaction MUST be 16 bytes");
  // óʼ0״̬;ֲݱ(include/asm/system.h,65)
  set_tss_desc (gdt + FIRST_TSS_ENTRY, &(init_task.task.tss));
  set_ldt_desc (gdt + FIRST_LDT_ENTRY, &(init_task.task.ldt));
  // עi=1 ʼԳʼڣ
  p = gdt + 2 + FIRST_TSS_ENTRY;
  for (i = 1; i < NR_TASKS; i++)
    {
      task[i] = NULL;
      p->a = p->b = 0;
      p++;
      p->a = p->b = 0;
      p++;
    }
  /* Clear NT, so that we won't have troubles with that later on */
  /* ־ĴеλNTԺͲ鷳 */
  // NT ־ڿƳĵݹ(Nested Task)NT λʱôǰжִ
  // iret ָʱͻлNT ָTSS еback_link ֶǷЧ
  __asm__ ("pushfl ; andl $0xffffbfff,(%esp) ; popfl");	// λNT ־
  ltr (0);			// 0 TSS صĴtr
  lldt (0);			// ֲصֲĴ
  // ע⣡ǽGDT ӦLDT ѡصldtrֻȷһΣԺ
  // LDT ļأCPU TSS еLDT Զء
  // ڳʼ8253 ʱ
  outb_p (0x36, 0x43);		/* binary, mode 3, LSB/MSB, ch 0 */
  outb_p (LATCH & 0xff, 0x40);	/* LSB */// ʱֵֽڡ
  outb (LATCH >> 8, 0x40);	/* MSB */// ʱֵֽڡ
  // ʱжϴʱжţ
  set_intr_gate (0x20, &timer_interrupt);
  // ޸жϿ룬ʱжϡ
  outb (inb_p (0x21) & ~0x01, 0x21);
  // ϵͳжš
  set_system_gate (0x80, &system_call);
}
