/* Copyright (C) 2004  The SOS Team
    Copyright (C) 1999  Free Software Foundation, Inc.
 
    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,
                    const struct sos_cpu_kstate *cpu_kstate)
 {
   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_kstate *cpu_kstate,
                            sos_vaddr_t stack_bottom,
                            sos_size_t  stack_size,
                            sos_bool_t on_console,
                            sos_bool_t on_bochs)
 {
   static 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_kstate, 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_kstate *ctxt)
 {
   static sos_ui32_t demand_paging_count = 0;
   sos_vaddr_t faulting_vaddr = sos_cpu_kstate_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 on access to address 0x%x (info=%x)!",
                               (unsigned)faulting_vaddr,
                               (unsigned)sos_cpu_kstate_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_kstate *ctxt_hello1;
 struct sos_cpu_kstate *ctxt_hello2;
 struct sos_cpu_kstate *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_kstate_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_kstate_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_kstate_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_kstate_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_kstate_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_kstate_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_kstate *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_kstate_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_kstate_switch(& st_reader, st_lexer);
     }
 
   data_reader_to_lexer = '\0';
   sos_cpu_kstate_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_kstate_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_kstate_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_kstate_switch(& st_lexer, st_parser);
 
   /* Signal that no more token are available */
   data_lexer_to_parser.type = LEX_END;
   sos_cpu_kstate_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_kstate_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;
   };
 };
 
 static void func_parser(struct syntax_node ** syntax_tree)
 {
   static struct syntax_node *alloc_node_num(int val);
   static struct syntax_node *alloc_node_var(const char * name);
   static struct syntax_node *alloc_node_binop(char op,
                                               struct syntax_node *parm_left,
                                               struct syntax_node *parm_right);
   static struct syntax_node *alloc_node_unarop(char op,
                                                struct syntax_node *parm);
   static struct syntax_node * get_expr();
   static struct syntax_node * get_expr_lr(struct syntax_node *n);
   static struct syntax_node * get_term();
   static struct syntax_node * get_term_lr(struct syntax_node *n);
   static struct syntax_node * get_factor();
   static struct syntax_node * get_scalar();
 
   /* Create a new node to store a number */
   static 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 */
   static 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 */
   static 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 */
   static 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 */
   static void parser_exception(const char *str)
     {
       sos_bochs_printf("Parser exception: %s\n", str);
       sos_cpu_kstate_switch(& st_parser, st_main);
     }
 
   /* Consume the current terminal "number" token and ask for a new
      token */
   static 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_kstate_switch(& st_parser, st_lexer);
       return v;
     }
   /* Consume the current terminal "variable" token and ask for a new
      token */
   static 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_kstate_switch(& st_parser, st_lexer);
     }
   /* Consume the current terminal "operator" token and ask for a new
      token */
   static 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_kstate_switch(& st_parser, st_lexer);
       return op;
     }
   /* Consume the current terminal "parenthese" token and ask for a new
      token */
   static 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_kstate_switch(& st_parser, st_lexer);
     }
 
   /* Parse an Expression */
   static struct syntax_node * get_expr()
     {
       struct syntax_node *t = get_term();
       return get_expr_lr(t);
     }
   /* Parse an Expr_lr */
   static 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 */
   static struct syntax_node * get_term()
     {
       struct syntax_node *f1 = get_factor();
       return get_term_lr(f1);
     }
   /* Parse a Term_lr */
   static 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 */
   static 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 */
   static 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());
     }
 
 
   /*
    * Body of the function
    */
 
   /* Get the first token */
   sos_cpu_kstate_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_kstate_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 */
   static 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_kstate_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_kstate_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_kstate_switch(& st_eval, st_main);
               }
           }
         }
       
       /* Exception: no such syntax node (INTERNAL error) ! */
       sos_bochs_printf("ERROR: invalid node type\n");
       sos_cpu_kstate_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_kstate_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_kstate_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", ',',
                             (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");
 
   sos_bochs_putstring("Message in a bochs\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;
     }
 }