/* 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;
}
}