path: root/sos-code-article6/sos/main.c

/* Copyright (C) 2004  The SOS Team

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License
   as published by the Free Software Foundation; either version 2
   of the License, or (at your option) any later version.
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
   USA. 
*/

/* Include definitions of the multiboot standard */
#include <bootstrap/multiboot.h>
#include <hwcore/idt.h>
#include <hwcore/gdt.h>
#include <hwcore/irq.h>
#include <hwcore/exception.h>
#include <hwcore/i8254.h>
#include <sos/list.h>
#include <sos/physmem.h>
#include <hwcore/paging.h>
#include <sos/kmem_vmm.h>
#include <sos/kmalloc.h>
#include <sos/klibc.h>
#include <sos/assert.h>
#include <drivers/x86_videomem.h>
#include <drivers/bochs.h>


/* Helper function to display each bits of a 32bits integer on the
   screen as dark or light carrets */
void display_bits(unsigned char row, unsigned char col,
		  unsigned char attribute,
		  sos_ui32_t integer)
{
  int i;
  /* Scan each bit of the integer, MSb first */
  for (i = 31 ; i >= 0 ; i--)
    {
      /* Test if bit i of 'integer' is set */
      int bit_i = (integer & (1 << i));
      /* Ascii 219 => dark carret, Ascii 177 => light carret */
      unsigned char ascii_code = bit_i?219:177;
      sos_x86_videomem_putchar(row, col++,
			       attribute,
			       ascii_code);
    }
}


/* Clock IRQ handler */
static void clk_it(int intid)
{
  static sos_ui32_t clock_count = 0;

  display_bits(0, 48,
	       SOS_X86_VIDEO_FG_LTGREEN | SOS_X86_VIDEO_BG_BLUE,
	       clock_count);
  clock_count++;
}


/* ======================================================================
 * Page fault exception handling
 */

/* Helper function to dump a backtrace on bochs and/or the console */

static void dump_backtrace(const struct sos_cpu_state *cpu_state,
			   sos_vaddr_t stack_bottom,
			   sos_size_t  stack_size,
			   sos_bool_t on_console,
			   sos_bool_t on_bochs)
{
  void backtracer(sos_vaddr_t PC,
			 sos_vaddr_t params,
			 sos_ui32_t depth,
			 void *custom_arg)
    {
      sos_ui32_t invalid = 0xffffffff, *arg1, *arg2, *arg3, *arg4;

      /* Get the address of the first 3 arguments from the
	 frame. Among these arguments, 0, 1, 2, 3 arguments might be
	 meaningful (depending on how many arguments the function may
	 take). */
      arg1 = (sos_ui32_t*)params;
      arg2 = (sos_ui32_t*)(params+4);
      arg3 = (sos_ui32_t*)(params+8);
      arg4 = (sos_ui32_t*)(params+12);

      /* Make sure the addresses of these arguments fit inside the
	 stack boundaries */
#define INTERVAL_OK(b,v,u) ( ((b) <= (sos_vaddr_t)(v)) \
                             && ((sos_vaddr_t)(v) < (u)) )
      if (!INTERVAL_OK(stack_bottom, arg1, stack_bottom + stack_size))
	arg1 = &invalid;
      if (!INTERVAL_OK(stack_bottom, arg2, stack_bottom + stack_size))
	arg2 = &invalid;
      if (!INTERVAL_OK(stack_bottom, arg3, stack_bottom + stack_size))
	arg3 = &invalid;
      if (!INTERVAL_OK(stack_bottom, arg4, stack_bottom + stack_size))
	arg4 = &invalid;

      /* Print the function context for this frame */
      if (on_bochs)
	sos_bochs_printf("[%d] PC=0x%x arg1=0x%x arg2=0x%x arg3=0x%x\n",
			 (unsigned)depth, (unsigned)PC,
			 (unsigned)*arg1, (unsigned)*arg2,
			 (unsigned)*arg3);

      if (on_console)
	sos_x86_videomem_printf(23-depth, 3,
				SOS_X86_VIDEO_BG_BLUE
				  | SOS_X86_VIDEO_FG_LTGREEN,
				"[%d] PC=0x%x arg1=0x%x arg2=0x%x arg3=0x%x arg4=0x%x",
				(unsigned)depth, PC,
				(unsigned)*arg1, (unsigned)*arg2,
				(unsigned)*arg3, (unsigned)*arg4);
      
    }
  sos_backtrace(cpu_state, 15, stack_bottom, stack_size, backtracer, NULL);
}


/* Page fault exception handler with demand paging for the kernel */
static void pgflt_ex(int intid, const struct sos_cpu_state *ctxt)
{
  static sos_ui32_t demand_paging_count = 0;
  sos_vaddr_t faulting_vaddr = sos_cpu_context_get_EX_faulting_vaddr(ctxt);
  sos_paddr_t ppage_paddr;

  /* Check if address is covered by any VMM range */
  if (! sos_kmem_vmm_is_valid_vaddr(faulting_vaddr))
    {
      /* No: The page fault is out of any kernel virtual region. For
	 the moment, we don't handle this. */
      dump_backtrace(ctxt,
		     bootstrap_stack_bottom,
		     bootstrap_stack_size,
		     TRUE, TRUE);
      sos_display_fatal_error("Unresolved page Fault at instruction 0x%x on access to address 0x%x (info=%x)!",
			      sos_cpu_context_get_PC(ctxt),
			      (unsigned)faulting_vaddr,
			      (unsigned)sos_cpu_context_get_EX_info(ctxt));
      SOS_ASSERT_FATAL(! "Got page fault (note: demand paging is disabled)");
    }


  /*
   * Demand paging
   */
 
  /* Update the number of demand paging requests handled */
  demand_paging_count ++;
  display_bits(0, 0,
	       SOS_X86_VIDEO_FG_LTRED | SOS_X86_VIDEO_BG_BLUE,
	       demand_paging_count);

  /* Allocate a new page for the virtual address */
  ppage_paddr = sos_physmem_ref_physpage_new(FALSE);
  if (! ppage_paddr)
    SOS_ASSERT_FATAL(! "TODO: implement swap. (Out of mem in demand paging because no swap for kernel yet !)");
  SOS_ASSERT_FATAL(SOS_OK == sos_paging_map(ppage_paddr,
					    SOS_PAGE_ALIGN_INF(faulting_vaddr),
					    FALSE,
					    SOS_VM_MAP_PROT_READ
					    | SOS_VM_MAP_PROT_WRITE
					    | SOS_VM_MAP_ATOMIC));
  sos_physmem_unref_physpage(ppage_paddr);

  /* Ok, we can now return to interrupted context */
}



/* ======================================================================
 * Demonstrate the use of the CPU kernet context management API:
 *  - A coroutine prints "Hlowrd" and switches to the other after each
 *    letter
 *  - A coroutine prints "el ol\n" and switches back to the other after
 *    each letter.
 * The first to reach the '\n' returns back to main.
 */
struct sos_cpu_state *ctxt_hello1;
struct sos_cpu_state *ctxt_hello2;
struct sos_cpu_state *ctxt_main;
sos_vaddr_t hello1_stack, hello2_stack;

static void reclaim_stack(sos_vaddr_t stack_vaddr)
{
  sos_kfree(stack_vaddr);
}


static void exit_hello12(sos_vaddr_t stack_vaddr)
{
  sos_cpu_context_exit_to(ctxt_main,
			  (sos_cpu_kstate_function_arg1_t*) reclaim_stack,
			  stack_vaddr);
}


static void hello1 (char *str)
{
  for ( ; *str != '\n' ; str++)
    {
      sos_bochs_printf("hello1: %c\n", *str);
      sos_cpu_context_switch(& ctxt_hello1, ctxt_hello2);
    }

  /* You can uncomment this in case you explicitly want to exit
     now. But returning from the function will do the same */
  /* sos_cpu_context_exit_to(ctxt_main,
			     (sos_cpu_kstate_function_arg1_t*) reclaim_stack,
			     hello1_stack); */
}


static void hello2 (char *str)
{
  for ( ; *str != '\n' ; str++)
    {
      sos_bochs_printf("hello2: %c\n", *str);
      sos_cpu_context_switch(& ctxt_hello2, ctxt_hello1);
    }

  /* You can uncomment this in case you explicitly want to exit
     now. But returning from the function will do the same */
  /* sos_cpu_context_exit_to(ctxt_main,
			     (sos_cpu_kstate_function_arg1_t*) reclaim_stack,
			     hello2_stack); */
}


void print_hello_world ()
{
#define DEMO_STACK_SIZE 1024
  /* Allocate the stacks */
  hello1_stack = sos_kmalloc(DEMO_STACK_SIZE, 0);
  hello2_stack = sos_kmalloc(DEMO_STACK_SIZE, 0);

  /* Initialize the coroutines' contexts */
  sos_cpu_kstate_init(&ctxt_hello1,
                      (sos_cpu_kstate_function_arg1_t*) hello1,
		      (sos_ui32_t) "Hlowrd",
                      (sos_vaddr_t) hello1_stack, DEMO_STACK_SIZE,
                      (sos_cpu_kstate_function_arg1_t*) exit_hello12,
		      (sos_ui32_t) hello1_stack);
  sos_cpu_kstate_init(&ctxt_hello2,
                      (sos_cpu_kstate_function_arg1_t*) hello2,
		      (sos_ui32_t) "el ol\n",
                      (sos_vaddr_t) hello2_stack, DEMO_STACK_SIZE,
                      (sos_cpu_kstate_function_arg1_t*) exit_hello12,
		      (sos_ui32_t) hello2_stack);

  /* Go to first coroutine */
  sos_bochs_printf("Printing Hello World\\n...\n");
  sos_cpu_context_switch(& ctxt_main, ctxt_hello1);

  /* The first coroutine to reach the '\n' switched back to us */
  sos_bochs_printf("Back in main !\n");
}


/* ======================================================================
 * Generate page faults on an unmapped but allocated kernel virtual
 * region, which results in a series of physical memory mappings for the
 * faulted pages.
 */
static void test_demand_paging(int nb_alloc_vpages, int nb_alloc_ppages)
{
  int i;
  sos_vaddr_t base_vaddr;

  sos_x86_videomem_printf(10, 0,
			  SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_LTGREEN,
			  "Demand paging test (alloc %dMB of VMM, test %dkB RAM)",
			  nb_alloc_vpages >> 8, nb_alloc_ppages << 2);
  
  /* Allocate virtual memory */
  base_vaddr = sos_kmem_vmm_alloc(nb_alloc_vpages, 0);

  SOS_ASSERT_FATAL(base_vaddr != (sos_vaddr_t)NULL);
  sos_x86_videomem_printf(11, 0,
			  SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			  "Allocated virtual region [0x%x, 0x%x[",
			  base_vaddr,
			  base_vaddr + nb_alloc_vpages*SOS_PAGE_SIZE);

  /* Now use part of it in physical memory */
  for (i = 0 ; (i < nb_alloc_ppages) && (i < nb_alloc_vpages) ; i++)
    {
      /* Compute an address inside the range */
      sos_ui32_t *value, j;
      sos_vaddr_t vaddr = base_vaddr;
      vaddr += (nb_alloc_vpages - (i + 1))*SOS_PAGE_SIZE;
      vaddr += 2345;

      sos_x86_videomem_printf(12, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Writing %d at virtual address 0x%x...",
			      i, vaddr);

      /* Write at this address */
      value = (sos_ui32_t*)vaddr;
      *value = i;

      /* Yep ! A new page should normally have been allocated for us */
      sos_x86_videomem_printf(13, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Value read at address 0x%x = %d",
			      vaddr, (unsigned)*value);
    }

  SOS_ASSERT_FATAL(SOS_OK == sos_kmem_vmm_free(base_vaddr));
  /* Yep ! A new page should normally have been allocated for us */
  sos_x86_videomem_printf(14, 0,
			  SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			  "Done (area un-allocated)");
}



/* ======================================================================
 * Shows how the backtrace stuff works
 */

/* Recursive function. Print the backtrace from the innermost function */
static void test_backtrace(int i, int magic, sos_vaddr_t stack_bottom,
			   sos_size_t  stack_size)
{
  if (i <= 0)
    {
      /* The page fault exception handler will print the backtrace of
	 this function, because address 0x42 is not mapped */
      *((char*)0x42) = 12;

      /* More direct variant: */
      /* dump_backtrace(NULL, stack_bottom, stack_size, TRUE, TRUE); */
    }
  else
    test_backtrace(i-1, magic, stack_bottom, stack_size);
}


/* ======================================================================
 * Parsing of Mathematical expressions
 *
 * This is a recursive lexer/parser/evaluator for arithmetical
 * expressions. Supports both binary +/-* and unary +- operators, as
 * well as parentheses.
 *
 * Terminal tokens (Lexer):
 *  - Number: positive integer number
 *  - Variable: ascii name (regexp: [a-zA-Z]+)
 *  - Operator: +*-/
 *  - Opening/closing parentheses
 *
 * Grammar (Parser):
 *  Expression ::= Term E'
 *  Expr_lr    ::= + Term Expr_lr | - Term Expr_lr | Nothing
 *  Term       ::= Factor Term_lr
 *  Term_lr    ::= * Factor Term_lr | / Factor Term_lr | Nothing
 *  Factor     ::= - Factor | + Factor | Scalar | ( Expression )
 *  Scalar     ::= Number | Variable
 *
 * Note. This is the left-recursive equivalent of the following basic grammar:
 *  Expression ::= Expression + Term | Expression - Term
 *  Term       ::= Term * Factor | Term / Factor
 *  factor     ::= - Factor | + Factor | Scalar | Variable | ( Expression )
 *  Scalar     ::= Number | Variable
 *
 * The parsing is composed of a 3 stages pipeline:
 *  - The reader: reads a string 1 character at a time, transferring
 *    the control back to lexer after each char. This function shows the
 *    interest in using coroutines, because its state (str) is
 *    implicitely stored in the stack between each iteration.
 *  - The lexer: consumes the characters from the reader and identifies
 *    the terminal tokens, 1 token at a time, transferring control back
 *    to the parser after each token. This function shows the interest
 *    in using coroutines, because its state (c and got_what_before) is
 *    implicitely stored in the stack between each iteration.
 *  - The parser: consumes the tokens from the lexer and builds the
 *    syntax tree of the expression. There is no real algorithmic
 *    interest in defining a coroutine devoted to do this. HOWEVER, we
 *    do use one for that because this allows us to switch to a much
 *    deeper stack. Actually, the parser is highly recursive, so that
 *    the default 16kB stack of the sos_main() function might not be
 *    enough. Here, we switch to a 64kB stack, which is safer for
 *    recursive functions. The Parser uses intermediary functions: these
 *    are defined and implemented as internal nested functions. This is
 *    just for the sake of clarity, and is absolutely not mandatory for
 *    the algorithm: one can transfer these functions out of the parser
 *    function without restriction.
 *
 * The evaluator is another recursive function that reuses the
 * parser's stack to evaluate the parsed expression with the given
 * values for the variables present in the expression. As for the
 * parser function, this function defines and uses a nested function,
 * which can be extracted from the main evaluation function at will.
 *
 * All these functions support a kind of "exception" feature: when
 * something goes wrong, control is transferred DIRECTLY back to the
 * sos_main() context, without unrolling the recursions. This shows
 * how exceptions basically work, but one should not consider this as
 * a reference exceptions implementation. Real exception mechanisms
 * (such as that in the C++ language) call the destructors to the
 * objects allocated on the stack during the "stack unwinding" process
 * upon exception handling, which complicates a lot the mechanism. We
 * don't have real Objects here (in the OOP sense, full-featured with
 * destructors), so we don't have to complicate things.
 *
 * After this little coroutine demo, one should forget all about such
 * a low-level manual direct manipulation of stacks. This would
 * probably mess up the whole kernel to do what we do here (locked
 * resources such as mutex/semaphore won't be correctly unlocked,
 * ...). Higher level "kernel thread" primitives will soon be
 * presented, which provide a higher-level set of APIs to manage CPU
 * contexts. You'll have to use EXCLUSIVELY those APIs. If you still
 * need a huge stack to do recursion for example, please don't even
 * think of changing manually the stack for something bigger ! Simply
 * rethink your algorithm, making it non-recursive.
 */


/* The stacks involved */
static char stack_reader[1024];
static char stack_lexer[1024];
static char deep_stack[65536]; /* For the parser and the evaluator */

/* The CPU states for the various coroutines */
static struct sos_cpu_state *st_reader, *st_lexer, *st_parser,
  *st_eval, *st_free, *st_main;


/*
 * Default exit/reclaim functions: return control to the "sos_main()"
 * context
 */
static void reclaim(int unused)
{
}
static void func_exit(sos_ui32_t unused)
{
  sos_cpu_context_exit_to(st_main, (sos_cpu_kstate_function_arg1_t*)reclaim, 0);
}


/*
 * The reader coroutine and associated variable. This coroutine could
 * have been a normal function, except that the current parsed
 * character would have to be stored somewhere.
 */
static char data_reader_to_lexer;

static void func_reader(const char *str)
{
  for ( ; str && (*str != '\0') ; str++)
    {
      data_reader_to_lexer = *str;
      sos_cpu_context_switch(& st_reader, st_lexer);
    }

  data_reader_to_lexer = '\0';
  sos_cpu_context_switch(& st_reader, st_lexer);
}


/*
 * The Lexer coroutine and associated types/variables. This coroutine
 * could have been a normal function, except that the current parsed
 * character, token and previous token would have to be stored
 * somewhere.
 */
#define STR_VAR_MAXLEN 16
static struct lex_elem
{
  enum { LEX_IS_NUMBER, LEX_IS_OPER, LEX_IS_VAR,
	 LEX_IS_OPENPAR, LEX_IS_CLOSEPAR, LEX_END } type;
  union {
    int  number;
    char operator;
    char var[STR_VAR_MAXLEN];
  };
} data_lexer_to_parser;

static void func_lexer(sos_ui32_t unused)
{
  char c;
  enum { GOT_SPACE, GOT_NUM, GOT_OP, GOT_STR,
	 GOT_OPENPAR, GOT_CLOSEPAR } got_what, got_what_before;

  data_lexer_to_parser.number = 0;
  got_what_before = GOT_SPACE;
  do
    {
      /* Consume one character from the reader */
      sos_cpu_context_switch(& st_lexer, st_reader);
      c = data_reader_to_lexer;

      /* Classify the consumed character */
      if ( (c >= '0') && (c <= '9') )
	got_what = GOT_NUM;
      else if ( (c == '+') || (c == '-') || (c == '*') || (c == '/') )
	got_what = GOT_OP;
      else if ( ( (c >= 'a') && (c <= 'z') )
		|| ( (c >= 'A') && (c <= 'Z') ) )
	got_what = GOT_STR;
      else if (c == '(')
	got_what = GOT_OPENPAR;
      else if (c == ')')
	got_what = GOT_CLOSEPAR;
      else
	got_what = GOT_SPACE;

      /* Determine whether the current token is ended */
      if ( (got_what != got_what_before)
	   || (got_what_before == GOT_OP)
	   || (got_what_before == GOT_OPENPAR)
	   || (got_what_before == GOT_CLOSEPAR) )
	{
	  /* return control back to the parser if the previous token
	     has been recognized */
	  if ( (got_what_before != GOT_SPACE) )
	    sos_cpu_context_switch(& st_lexer, st_parser);

	  data_lexer_to_parser.number = 0;
	}

      /* Update the token being currently recognized */
      if (got_what == GOT_OP)
	{
	  data_lexer_to_parser.type = LEX_IS_OPER;
	  data_lexer_to_parser.operator = c;
	}
      else if (got_what == GOT_NUM)
	{
	  data_lexer_to_parser.type = LEX_IS_NUMBER;
	  data_lexer_to_parser.number *= 10;
	  data_lexer_to_parser.number += (c - '0');
	}
      else if (got_what == GOT_STR)
	{
	  char to_cat[] = { c, '\0' };
	  data_lexer_to_parser.type = LEX_IS_VAR;
	  strzcat(data_lexer_to_parser.var, to_cat, STR_VAR_MAXLEN);
	}
      else if (got_what == GOT_OPENPAR)
	data_lexer_to_parser.type = LEX_IS_OPENPAR;
      else if (got_what == GOT_CLOSEPAR)
	data_lexer_to_parser.type = LEX_IS_CLOSEPAR;

      got_what_before = got_what;
    }
  while (c != '\0');

  /* Transfer last recognized token to the parser */
  if ( (got_what_before != GOT_SPACE) )
    sos_cpu_context_switch(& st_lexer, st_parser);

  /* Signal that no more token are available */
  data_lexer_to_parser.type = LEX_END;
  sos_cpu_context_switch(& st_lexer, st_parser);

  /* Exception: parser asks for a token AFTER having received the last
     one */
  sos_bochs_printf("Error: end of string already reached !\n");
  sos_cpu_context_switch(& st_lexer, st_main);
}


/*
 * The Parser coroutine and associated types/variables
 */
struct syntax_node
{
  enum { YY_IS_BINOP, YY_IS_UNAROP, YY_IS_NUM, YY_IS_VAR } type;
  union
  {
    int  number;
    char var[STR_VAR_MAXLEN];
    struct
    {
      char op;
      struct syntax_node *parm_left, *parm_right;
    } binop;
    struct
    {
      char op;
      struct syntax_node *parm;
    } unarop;
  };
};

// BEGIN AUX FUNCTIONS
  struct syntax_node *alloc_node_num(int val);
  struct syntax_node *alloc_node_var(const char * name);
  struct syntax_node *alloc_node_binop(char op,
					      struct syntax_node *parm_left,
					      struct syntax_node *parm_right);
  struct syntax_node *alloc_node_unarop(char op,
					       struct syntax_node *parm);
  struct syntax_node * get_expr();
  struct syntax_node * get_expr_lr(struct syntax_node *n);
  struct syntax_node * get_term();
  struct syntax_node * get_term_lr(struct syntax_node *n);
  struct syntax_node * get_factor();
  struct syntax_node * get_scalar();

  /* Create a new node to store a number */
  struct syntax_node *alloc_node_num(int val)
    {
      struct syntax_node *n
	= (struct syntax_node*) sos_kmalloc(sizeof(struct syntax_node), 0);
      n->type   = YY_IS_NUM;
      n->number = val;
      return n;
    }
  /* Create a new node to store a variable */
  struct syntax_node *alloc_node_var(const char * name)
    {
      struct syntax_node *n
	= (struct syntax_node*) sos_kmalloc(sizeof(struct syntax_node), 0);
      n->type   = YY_IS_VAR;
      strzcpy(n->var, name, STR_VAR_MAXLEN);
      return n;
    }
  /* Create a new node to store a binary operator */
  struct syntax_node *alloc_node_binop(char op,
					      struct syntax_node *parm_left,
					      struct syntax_node *parm_right)
    {
      struct syntax_node *n
	= (struct syntax_node*) sos_kmalloc(sizeof(struct syntax_node), 0);
      n->type             = YY_IS_BINOP;
      n->binop.op         = op;
      n->binop.parm_left  = parm_left;
      n->binop.parm_right = parm_right;
      return n;
    }
  /* Create a new node to store a unary operator */
  struct syntax_node *alloc_node_unarop(char op,
					       struct syntax_node *parm)
    {
      struct syntax_node *n
	= (struct syntax_node*) sos_kmalloc(sizeof(struct syntax_node), 0);
      n->type        = YY_IS_UNAROP;
      n->unarop.op   = op;
      n->unarop.parm = parm;
      return n;
    }

  /* Raise an exception: transfer control back to main context,
     without unrolling the whole recursion */
  void parser_exception(const char *str)
    {
      sos_bochs_printf("Parser exception: %s\n", str);
      sos_cpu_context_switch(& st_parser, st_main);
    }

  /* Consume the current terminal "number" token and ask for a new
     token */
  int get_number()
    {
      int v;
      if (data_lexer_to_parser.type != LEX_IS_NUMBER)
	parser_exception("Expected number");
      v = data_lexer_to_parser.number;
      sos_cpu_context_switch(& st_parser, st_lexer);
      return v;
    }
  /* Consume the current terminal "variable" token and ask for a new
     token */
  void get_str(char name[STR_VAR_MAXLEN])
    {
      if (data_lexer_to_parser.type != LEX_IS_VAR)
	parser_exception("Expected variable");
      strzcpy(name, data_lexer_to_parser.var, STR_VAR_MAXLEN);
      sos_cpu_context_switch(& st_parser, st_lexer);
    }
  /* Consume the current terminal "operator" token and ask for a new
     token */
  char get_op()
    {
      char op;
      if (data_lexer_to_parser.type != LEX_IS_OPER)
	parser_exception("Expected operator");
      op = data_lexer_to_parser.operator;
      sos_cpu_context_switch(& st_parser, st_lexer);
      return op;
    }
  /* Consume the current terminal "parenthese" token and ask for a new
     token */
  void get_par()
    {
      if ( (data_lexer_to_parser.type != LEX_IS_OPENPAR)
	   && (data_lexer_to_parser.type != LEX_IS_CLOSEPAR) )
	parser_exception("Expected parenthese");
      sos_cpu_context_switch(& st_parser, st_lexer);
    }

  /* Parse an Expression */
  struct syntax_node * get_expr()
    {
      struct syntax_node *t = get_term();
      return get_expr_lr(t);
    }
  /* Parse an Expr_lr */
  struct syntax_node * get_expr_lr(struct syntax_node *n)
    {
      if ( (data_lexer_to_parser.type == LEX_IS_OPER)
	   && ( (data_lexer_to_parser.operator == '+')
		|| (data_lexer_to_parser.operator == '-') ) )
	{
	  char op = get_op();
	  struct syntax_node *term = get_term();
	  struct syntax_node *node_op = alloc_node_binop(op, n, term);
	  return get_expr_lr(node_op);
	}
      return n;
    }
  /* Parse a Term */
  struct syntax_node * get_term()
    {
      struct syntax_node *f1 = get_factor();
      return get_term_lr(f1);
    }
  /* Parse a Term_lr */
  struct syntax_node * get_term_lr(struct syntax_node *n)
    {
      if ( (data_lexer_to_parser.type == LEX_IS_OPER)
	   && ( (data_lexer_to_parser.operator == '*')
		|| (data_lexer_to_parser.operator == '/') ) )
	{
	  char op = get_op();
	  struct syntax_node *factor = get_factor();
	  struct syntax_node *node_op = alloc_node_binop(op, n, factor);
	  return get_term_lr(node_op);
	}
      return n;
    }
  /* Parse a Factor */
  struct syntax_node * get_factor()
    {
      if ( (data_lexer_to_parser.type == LEX_IS_OPER)
	   && ( (data_lexer_to_parser.operator == '-')
		|| (data_lexer_to_parser.operator == '+') ) )
	{ char op = data_lexer_to_parser.operator;
	get_op(); return alloc_node_unarop(op, get_factor()); }
      else if (data_lexer_to_parser.type == LEX_IS_OPENPAR)
	{
	  struct syntax_node *expr;
	  get_par();
	  expr = get_expr();
	  if (data_lexer_to_parser.type != LEX_IS_CLOSEPAR)
	    parser_exception("Mismatched parentheses");
	  get_par();
	  return expr;
	}
  
      return get_scalar();
    }
  /* Parse a Scalar */
  struct syntax_node * get_scalar()
    {
      if (data_lexer_to_parser.type != LEX_IS_NUMBER)
	{
	  char var[STR_VAR_MAXLEN];
	  get_str(var);
	  return alloc_node_var(var);
	}
      return alloc_node_num(get_number());
    }

// END AUX FUNCTIONS


static void func_parser(struct syntax_node ** syntax_tree)
{
  /*
   * Body of the function
   */

  /* Get the first token */
  sos_cpu_context_switch(& st_parser, st_lexer);

  /* Begin the parsing ! */
  *syntax_tree = get_expr();
  /* The result is returned in the syntax_tree parameter */
}


/*
 * Setup the parser's pipeline
 */
static struct syntax_node * parse_expression(const char *expr)
{
  struct syntax_node *retval = NULL;

  /* Build the context of the functions in the pipeline */
  sos_cpu_kstate_init(& st_reader,
		      (sos_cpu_kstate_function_arg1_t*)func_reader,
		      (sos_ui32_t)expr,
		      (sos_vaddr_t)stack_reader, sizeof(stack_reader),
		      (sos_cpu_kstate_function_arg1_t*)func_exit, 0);
  sos_cpu_kstate_init(& st_lexer,
		      (sos_cpu_kstate_function_arg1_t*)func_lexer,
		      0,
		      (sos_vaddr_t)stack_lexer, sizeof(stack_lexer),
		      (sos_cpu_kstate_function_arg1_t*)func_exit, 0);
  sos_cpu_kstate_init(& st_parser,
		      (sos_cpu_kstate_function_arg1_t*)func_parser,
		      (sos_ui32_t) /* syntax tree ! */&retval,
		      (sos_vaddr_t)deep_stack, sizeof(deep_stack),
		      (sos_cpu_kstate_function_arg1_t*)func_exit, 0);

  /* Parse the expression */
  sos_cpu_context_switch(& st_main, st_parser);
  return retval;
}


/*
 * The Evaluator coroutine and associated types/variables
 */
struct func_eval_params
{
  const struct syntax_node *e;
  const char **var_name;
  int *var_val;
  int nb_vars;

  int result;
};

static void func_eval(struct func_eval_params *parms)
{
  /* The internal (recursive) nested function to evaluate each node of
     the syntax tree */
  int rec_eval(const struct syntax_node *n,
		      const char* var_name[], int var_val[], int nb_vars)
    {
      switch (n->type)
	{
	case YY_IS_NUM:
	  return n->number;

	case YY_IS_VAR:
	  {
	    int i;
	    for (i = 0 ; i < nb_vars ; i++)
	      if (0 == strcmp(var_name[i], n->var))
		return var_val[i];

	    /* Exception: no variable with that name ! */
	    sos_bochs_printf("ERROR: unknown variable %s\n", n->var);
	    sos_cpu_context_switch(& st_eval, st_main);
	  }

	case YY_IS_BINOP:
	  {
	    int left = rec_eval(n->binop.parm_left,
				var_name, var_val, nb_vars);
	    int right = rec_eval(n->binop.parm_right,
				 var_name, var_val, nb_vars);
	    switch (n->binop.op)
	      {
	      case '+': return left + right;
	      case '-': return left - right;
	      case '*': return left * right;
	      case '/': return left / right;
	      default:
		/* Exception: no such operator (INTERNAL error) ! */
		sos_bochs_printf("ERROR: unknown binop %c\n", n->binop.op);
		sos_cpu_context_switch(& st_eval, st_main);
	      }
	  }

	case YY_IS_UNAROP:
	  {
	    int arg = rec_eval(n->unarop.parm, var_name, var_val, nb_vars);
	    switch (n->unarop.op)
	      {
	      case '-': return -arg;
	      case '+': return arg;
	      default:
		/* Exception: no such operator (INTERNAL error) ! */
		sos_bochs_printf("ERROR: unknown unarop %c\n", n->unarop.op);
		sos_cpu_context_switch(& st_eval, st_main);
	      }
	  }
	}
      
      /* Exception: no such syntax node (INTERNAL error) ! */
      sos_bochs_printf("ERROR: invalid node type\n");
      sos_cpu_context_switch(& st_eval, st_main);
      return -1; /* let's make gcc happy */
    }


  /*
   * Function BODY
   */
  /* Update p.result returned back to calling function */
  parms->result
    = rec_eval(parms->e, parms->var_name, parms->var_val, parms->nb_vars);
}

/*
 * Change the stack for something larger in order to call the
 * recursive function above in a safe way
 */
static int eval_expression(const struct syntax_node *e,
			   const char* var_name[], int var_val[], int nb_vars)
{
  struct func_eval_params p
    = (struct func_eval_params){ .e=e,
				 .var_name=var_name,
				 .var_val=var_val,
				 .nb_vars=nb_vars,
				 .result = 0 };

  sos_cpu_kstate_init(& st_eval,
		      (sos_cpu_kstate_function_arg1_t*)func_eval,
		      (sos_ui32_t)/* p.result is modified upon success */&p,
		      (sos_vaddr_t)deep_stack, sizeof(deep_stack),
		      (sos_cpu_kstate_function_arg1_t*)func_exit, 0);

  /* Go ! */
  sos_cpu_context_switch(& st_main, st_eval);
  return p.result;
}


/*
 * Function to free the syntax tree
 */
static void func_free(struct syntax_node *n)
{
  switch (n->type)
    {
    case YY_IS_NUM:
    case YY_IS_VAR:
      break;
      
    case YY_IS_BINOP:
      func_free(n->binop.parm_left);
      func_free(n->binop.parm_right);
      break;
      
    case YY_IS_UNAROP:
      func_free(n->unarop.parm);
      break;
    }
  
  sos_kfree((sos_vaddr_t)n);
}

/*
 * Change the stack for something larger in order to call the
 * recursive function above in a safe way
 */
static void free_syntax_tree(struct syntax_node *tree)
{
  sos_cpu_kstate_init(& st_free,
		      (sos_cpu_kstate_function_arg1_t*)func_free,
		      (sos_ui32_t)tree,
		      (sos_vaddr_t)deep_stack, sizeof(deep_stack),
		      (sos_cpu_kstate_function_arg1_t*)func_exit, 0);

  /* Go ! */
  sos_cpu_context_switch(& st_main, st_free);
}


/* ======================================================================
 * The C entry point of our operating system
 */
void sos_main(unsigned long magic, unsigned long addr)
{
  unsigned i;
  sos_paddr_t sos_kernel_core_base_paddr, sos_kernel_core_top_paddr;
  struct syntax_node *syntax_tree;

  /* Grub sends us a structure, called multiboot_info_t with a lot of
     precious informations about the system, see the multiboot
     documentation for more information. */
  multiboot_info_t *mbi;
  mbi = (multiboot_info_t *) addr;

  /* Setup bochs and console, and clear the console */
  sos_bochs_setup();

  sos_x86_videomem_setup();
  sos_x86_videomem_cls(SOS_X86_VIDEO_BG_BLUE);

  /* Greetings from SOS */
  if (magic == MULTIBOOT_BOOTLOADER_MAGIC)
    /* Loaded with Grub */
    sos_x86_videomem_printf(1, 0,
			    SOS_X86_VIDEO_FG_YELLOW | SOS_X86_VIDEO_BG_BLUE,
			    "Welcome From GRUB to %s%c RAM is %dMB (upper mem = 0x%x kB)",
			    "SOS article 6", ',',
			    (unsigned)(mbi->mem_upper >> 10) + 1,
			    (unsigned)mbi->mem_upper);
  else
    /* Not loaded with grub */
    sos_x86_videomem_printf(1, 0,
			    SOS_X86_VIDEO_FG_YELLOW | SOS_X86_VIDEO_BG_BLUE,
			    "Welcome to SOS article 6");

  sos_bochs_putstring("Message in a bochs: This is SOS article 6.\n");

  /* Setup CPU segmentation and IRQ subsystem */
  sos_gdt_subsystem_setup();
  sos_idt_subsystem_setup();

  /* Setup SOS IRQs and exceptions subsystem */
  sos_exception_subsystem_setup();
  sos_irq_subsystem_setup();

  /* Configure the timer so as to raise the IRQ0 at a 100Hz rate */
  sos_i8254_set_frequency(100);

  /* We need a multiboot-compliant boot loader to get the size of the RAM */
  if (magic != MULTIBOOT_BOOTLOADER_MAGIC)
    {
      sos_x86_videomem_putstring(20, 0,
				 SOS_X86_VIDEO_FG_LTRED
				   | SOS_X86_VIDEO_BG_BLUE
				   | SOS_X86_VIDEO_FG_BLINKING,
				 "I'm not loaded with Grub !");
      /* STOP ! */
      for (;;)
	continue;
    }

  /*
   * Some interrupt handlers
   */

  /* Binding some HW interrupts and exceptions to software routines */
  sos_irq_set_routine(SOS_IRQ_TIMER,
		      clk_it);

  /*
   * Setup physical memory management
   */

  /* Multiboot says: "The value returned for upper memory is maximally
     the address of the first upper memory hole minus 1 megabyte.". It
     also adds: "It is not guaranteed to be this value." aka "YMMV" ;) */
  sos_physmem_subsystem_setup((mbi->mem_upper<<10) + (1<<20),
			      & sos_kernel_core_base_paddr,
			      & sos_kernel_core_top_paddr);
  
  /*
   * Switch to paged-memory mode
   */

  /* Disabling interrupts should seem more correct, but it's not really
     necessary at this stage */
  SOS_ASSERT_FATAL(SOS_OK ==
		   sos_paging_subsystem_setup(sos_kernel_core_base_paddr,
					      sos_kernel_core_top_paddr));
  
  /* Bind the page fault exception */
  sos_exception_set_routine(SOS_EXCEPT_PAGE_FAULT,
			    pgflt_ex);

  /*
   * Setup kernel virtual memory allocator
   */

  if (sos_kmem_vmm_subsystem_setup(sos_kernel_core_base_paddr,
				   sos_kernel_core_top_paddr,
				   bootstrap_stack_bottom,
				   bootstrap_stack_bottom
				   + bootstrap_stack_size))
    sos_bochs_printf("Could not setup the Kernel virtual space allocator\n");

  if (sos_kmalloc_subsystem_setup())
    sos_bochs_printf("Could not setup the Kmalloc subsystem\n");

  /*
   * Enabling the HW interrupts here, this will make the timer HW
   * interrupt call our clk_it handler
   */
  asm volatile ("sti\n");

  /*
   * Print hello world using coroutines
   */
  print_hello_world();


  /*
   * Run coroutine tests
   */
  sos_x86_videomem_printf(4, 0,
			  SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_LTGREEN,
			  "Coroutine test");
  sos_x86_videomem_printf(5, 0,
			  SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			  "Parsing...");
  syntax_tree = parse_expression(" -  ( (69/ toto)+ ( (( - +-- 1))) + --toto*((toto+ - - y - +2*(y-toto))*y) +2*(y-toto) )/- (( y - toto)*2)");

  if (syntax_tree != NULL)
    {
      sos_x86_videomem_printf(6, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Evaluating...");
      sos_x86_videomem_printf(7, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Result=%d (if 0: check bochs output)",
			      eval_expression(syntax_tree,
					      (const char*[]){"toto", "y"},
					      (int[]){3, 4},
					      2));
      free_syntax_tree(syntax_tree);
      sos_x86_videomem_printf(8, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Done (un-allocated syntax tree)");
    }
  else
    {
      sos_x86_videomem_printf(6, 0,
			      SOS_X86_VIDEO_BG_BLUE | SOS_X86_VIDEO_FG_YELLOW,
			      "Error in parsing (see bochs output)");
    }

  /*
   * Run some demand-paging tests
   */
  test_demand_paging(234567, 500);


  /*
   * Create an un-resolved page fault, which will make the page fault
   * handler print the backtrace.
   */
  test_backtrace(6, 0xdeadbeef, bootstrap_stack_bottom, bootstrap_stack_size);

  /*
   * System should be halted BEFORE here !
   */


  /* An operatig system never ends */
  for (;;)
    {
      /* Remove this instruction if you get an "Invalid opcode" CPU
	 exception (old 80386 CPU) */
      asm("hlt\n");

      continue;
    }
}