diff options
Diffstat (limited to 'sos-code-article6/sos/main.c')
| -rw-r--r-- | sos-code-article6/sos/main.c | 1162 |
1 files changed, 1162 insertions, 0 deletions
diff --git a/sos-code-article6/sos/main.c b/sos-code-article6/sos/main.c new file mode 100644 index 0000000..37f1d68 --- /dev/null +++ b/sos-code-article6/sos/main.c @@ -0,0 +1,1162 @@ +/* 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) +{ + 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_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; + }; +}; + +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_context_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_context_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_context_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_context_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_context_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_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 */ + 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_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; + } +} |