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