From b7002c53057d4ae049237786d26f00a762dbc2ea Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Filip=20Str=C3=B6mb=C3=A4ck?= Date: Tue, 16 Mar 2021 13:01:32 +0100 Subject: Updated names in standalone/ to match new lab numbering. --- src/standalone/lab01/about-main.c | 6 + src/standalone/lab02/main.c | 124 +++++++++++++++++ src/standalone/lab02/map.c | 1 + src/standalone/lab02/map.h | 1 + src/standalone/lab07/setup-argv.c | 277 ++++++++++++++++++++++++++++++++++++++ src/standalone/lab14/pagedir.c | 8 ++ src/standalone/lab14/pagedir.h | 42 ++++++ src/standalone/lab14/pagedir.o | Bin 0 -> 8784 bytes src/standalone/lab14/thread.h | 16 +++ src/standalone/lab14/verify_adr.c | 90 +++++++++++++ src/standalone/labx1/basics.c | 6 + src/standalone/labx2/fork-wait.c | 95 +++++++++++++ src/standalone/labx3/use-list.c | 42 ++++++ src/standalone/labx4/debug.c | 27 ++++ src/standalone/upg1/basics.c | 6 - src/standalone/upg2/about-main.c | 6 - src/standalone/upg3/fork-wait.c | 95 ------------- src/standalone/upg4/use-list.c | 42 ------ src/standalone/upg5/pagedir.c | 8 -- src/standalone/upg5/pagedir.h | 42 ------ src/standalone/upg5/pagedir.o | Bin 8784 -> 0 bytes src/standalone/upg5/thread.h | 16 --- src/standalone/upg5/verify_adr.c | 90 ------------- src/standalone/upg6/main.c | 124 ----------------- src/standalone/upg6/map.c | 1 - src/standalone/upg6/map.h | 1 - src/standalone/upg7/debug.c | 27 ---- src/standalone/upg8/setup-argv.c | 277 -------------------------------------- 28 files changed, 735 insertions(+), 735 deletions(-) create mode 100644 src/standalone/lab01/about-main.c create mode 100644 src/standalone/lab02/main.c create mode 100644 src/standalone/lab02/map.c create mode 100644 src/standalone/lab02/map.h create mode 100644 src/standalone/lab07/setup-argv.c create mode 100644 src/standalone/lab14/pagedir.c create mode 100644 src/standalone/lab14/pagedir.h create mode 100644 src/standalone/lab14/pagedir.o create mode 100644 src/standalone/lab14/thread.h create mode 100644 src/standalone/lab14/verify_adr.c create mode 100644 src/standalone/labx1/basics.c create mode 100644 src/standalone/labx2/fork-wait.c create mode 100644 src/standalone/labx3/use-list.c create mode 100644 src/standalone/labx4/debug.c delete mode 100644 src/standalone/upg1/basics.c delete mode 100644 src/standalone/upg2/about-main.c delete mode 100644 src/standalone/upg3/fork-wait.c delete mode 100644 src/standalone/upg4/use-list.c delete mode 100644 src/standalone/upg5/pagedir.c delete mode 100644 src/standalone/upg5/pagedir.h delete mode 100644 src/standalone/upg5/pagedir.o delete mode 100644 src/standalone/upg5/thread.h delete mode 100644 src/standalone/upg5/verify_adr.c delete mode 100644 src/standalone/upg6/main.c delete mode 100644 src/standalone/upg6/map.c delete mode 100644 src/standalone/upg6/map.h delete mode 100644 src/standalone/upg7/debug.c delete mode 100644 src/standalone/upg8/setup-argv.c diff --git a/src/standalone/lab01/about-main.c b/src/standalone/lab01/about-main.c new file mode 100644 index 0000000..2407c23 --- /dev/null +++ b/src/standalone/lab01/about-main.c @@ -0,0 +1,6 @@ +#include +#include + +int main(int argc, char* argv[]) +{ +} diff --git a/src/standalone/lab02/main.c b/src/standalone/lab02/main.c new file mode 100644 index 0000000..c481d40 --- /dev/null +++ b/src/standalone/lab02/main.c @@ -0,0 +1,124 @@ +#include +#include +#include + +#include "map.h" + +/* Recommended compile commmand: + * + * gcc -Wall -Wextra -std=gnu99 -pedantic -g main.c map.c + * + * Recommended way to test your solution: + * + * valgrind --tool=memcheck ./a.out + */ +#error Read comments above, then remove this line. + + +/* Can be used to inform compiler about unused parameters (prevent + * warning). Useful when a funtion pointer expect a certain set of + * parameters, but you only need some of them. */ +#define UNUSED __attribute__((unused)) + +/* The code assumes that key_t is `int' and value_t is `char*' */ + +/* function passed as parameter to map_remove_if in order to free the + * memory for all inseted values, and return true to remove them from + * the map */ +bool do_free(key_t k UNUSED, value_t v, int aux UNUSED) +{ + free(v); /*! free memory */ + return true; /* and remove from collection */ +} + +/* function to display all values in the map that are less than the + * aux argument */ +void print_less(key_t k UNUSED, value_t v, int aux) +{ + /* atoi converst from sequence of character to integer, it will fail + * when the characters are letters, check the manpage to see how */ + if ( atoi(v) < aux) + { + printf("%s ", v); + } +} + + +#define LOOPS 10 + +char* my_strdup(char* str) +{ + /*! calculate the length and add space for '\0' */ + int len = strlen(str) + 1; + /*! allocate memory just large enough */ + char* dst = (char*)malloc(len); + /*! copy all characters in src to dst */ + strncpy(dst, str, len); + + return dst; /*(!) return our deep copy of str */ +} + +int main() +{ + struct map container; + char input_buffer[10]; + char* obj; + int id; + int i; + + map_init(&container); + + /* remember to try to insert more values than you map can hold */ + printf("Insert values: "); + for ( i = 0; i < LOOPS; ++i) + { + /* insecure, scanf may overflow the input buffer array * + * very serious, but we ignore it in this test program */ + scanf("%s", input_buffer); + + /*! allocates a copy of the input and inserts in map */ + obj = my_strdup(input_buffer); + id = map_insert(&container, obj); + } + + /* remember to test with invalid keys (like 4711, or -1) */ + for ( i = 0; i < LOOPS; ++i) + { + printf("Enter id to find value for: "); + scanf("%d", &id); + + /*! find the value for a key in the map */ + obj = map_find(&container, id); + + /*! if it was found, display it */ +YOUR CODE + + /* since we leave the value in the map we may use it again and + * should not free the memory */ + } + + /* remember to test with invalid keys (like 4711, or -1) */ + for ( i = 0; i < LOOPS; ++i) + { + printf("Enter id to remove value for: "); + scanf("%d", &id); + + /*! find and remove a value for a key in the map */ + obj = map_remove(&container, id); + + /*! if it was found, display it */ +YOUR CODE + /* since we removed the value from the map we will never use it again and + * must properly free the memory (if it was allocated) */ + } + + /*! print all strings representing an integer less than N */ + printf("Will now display all values less than N. Choose N: "); + scanf("%d", &i); + map_for_each(&container, print_less, i); + + /*! free all remaining memory and remove from map */ + map_remove_if(&container, do_free, 0); + + return 0; +} diff --git a/src/standalone/lab02/map.c b/src/standalone/lab02/map.c new file mode 100644 index 0000000..b323fbb --- /dev/null +++ b/src/standalone/lab02/map.c @@ -0,0 +1 @@ +#include "map.h" diff --git a/src/standalone/lab02/map.h b/src/standalone/lab02/map.h new file mode 100644 index 0000000..9029ff5 --- /dev/null +++ b/src/standalone/lab02/map.h @@ -0,0 +1 @@ +/* do not forget the guard against multiple includes */ diff --git a/src/standalone/lab07/setup-argv.c b/src/standalone/lab07/setup-argv.c new file mode 100644 index 0000000..f2bd04a --- /dev/null +++ b/src/standalone/lab07/setup-argv.c @@ -0,0 +1,277 @@ +#define _POSIX_C_SOURCE 2 +#include +#include +#include + +/* + YOUR WORK: + + You will complete the function setup_main_stack below. Missing code + and calculations are expressed with a questionmark (?). The + assignment is mostly about doing the correct math. To do that math + you will need to learn or understand: + + - How the stack is used during program execution + - How the stack is expected to look like at start of a C-program + - What a pointer variable is, how it is used + - How a C-array (pointer to many) is laid-out in memory + - How pointer arithmetic behaves + - How to cast from one pointer type to another + - How to use printf to print good debug information + - How to use a C-struct, both object and pointer to + + Some manual-pages of interest: + + man -s3 printf + man -s3 strlen + man -s3 strncpy + man -s3 strtok_r + + The prototype for above functions: + + int printf(const char *restrict format, ...); + size_t strlen(const char *s); + size_t strncpy(char *dst, const char *src, size_t dstsize); + char *strtok_r(char *s1, const char *s2, char **lasts); + + The above functions exist in Pintos code. Note the Pintos use + 'strlcpy' instead of 'strncpy'. If 'dst' is large enough they behave + identical. You can find Pintos implementations in + /home/TDIU16/labs/skel/pintos/src/lib, see string.c and stdio.c. It + is strongly recommendable to look at the strtok_r examples given in + string.c + + About *restrict: http://en.wikipedia.org/wiki/Pointer_alias + + + Recommended compile command: + + gcc -m32 -Wall -Wextra -std=gnu99 -g setup-argv.c + +*/ +#error Read comments above, then remove this line. + +#define true 1 +#define false 0 + +typedef int bool; + +/* "struct main_args" represent the stack as it must look when + * entering main. The only issue: argv must point somewhere... + * + * The members of this structure is is directly related to the + * arguments of main in a C-program, of course. + * + * int main(int argc, char* argv[]); + * + * (char** argv is a more generic form of char* argv[]) + * + * The function pointer is normally handled by the compiler + * automatically, and determine the address at where a function shall + * continue when it returns. The main function does not use it, as the + * operating system arrange for the program to stop execution when + * main is finished. + */ +struct main_args +{ + /* Hint: When try to interpret C-declarations, read from right to + * left! It is often easier to get the correct interpretation, + * altough it does not always work. */ + + /* Variable "ret" that stores address (*ret) to a function taking no + * parameters (void) and returning nothing. */ + void (*ret)(void); + + /* Just a normal integer. */ + int argc; + + /* Variable "argv" that stores address to an address storing char. + * That is: argv is a pointer to char* + */ + char** argv; +}; + +/* A function that dumps 'size' bytes of memory starting at 'ptr' + * it will dump the higher adress first letting the stack grow down. + */ +void dump(void* ptr, int size) +{ + int i; + const int S = sizeof(void*); + + printf("%2$-*1$s \t%3$-*1$s \t%4$-*1$s\n", S*2, "Address", "hex-data", "char-data"); + + for (i = size - 1; i >= 0; --i) + { + void** adr = (void**)((unsigned long)ptr + i); + unsigned char* byte = (unsigned char*)((unsigned long)ptr + i); + + printf("%0*lx\t", S*2, (unsigned long)ptr + i); /* address */ + + if ((i % S) == 0) + /* seems we're actually forbidden to read unaligned adresses */ + printf("%0*lx\t", S*2, (unsigned long)*adr); /* content interpreted as address */ + else + printf("%*c\t", S*2, ' '); /* fill */ + + if(*byte >= 32 && *byte < 127) + printf("%c\n", *byte); /* content interpreted as character */ + else + printf("\\%o\n", *byte); + + if ((i % S) == 0) + printf("----------------------------------------------------------------\n"); + } +} + +/* Read one line of input ... + */ +void custom_getline(char buf[], int size) +{ + int i; + for (i = 0; i < (size - 1); ++i) + { + buf[i] = getchar(); + if (buf[i] == '\n') + break; + } + buf[i] = '\0'; +} + +/* Return true if 'c' is fount in the c-string 'd' + * NOTE: 'd' must be a '\0'-terminated c-string + */ +bool exists_in(char c, const char* d) +{ + int i = 0; + while (d[i] != '\0' && d[i] != c) + ++i; + return (d[i] == c); +} + +/* Return the number of words in 'buf'. A word is defined as a + * sequence of characters not containing any of the characters in + * 'delimeters'. + * NOTE: arguments must be '\0'-terminated c-strings + */ +int count_args(const char* buf, const char* delimeters) +{ + int i = 0; + bool prev_was_delim; + bool cur_is_delim = true; + int argc = 0; + + while (buf[i] != '\0') + { + prev_was_delim = cur_is_delim; + cur_is_delim = exists_in(buf[i], delimeters); + argc += (prev_was_delim && !cur_is_delim); + ++i; + } + return argc; +} + +/* Replace calls to STACK_DEBUG with calls to printf. All such calls + * easily removed later by replacing with nothing. */ +#define STACK_DEBUG(...) printf(__VA_ARGS__) + +void* setup_main_stack(const char* command_line, void* stack_top) +{ + /* Variable "esp" stores an address, and at the memory loaction + * pointed out by that address a "struct main_args" is found. + * That is: "esp" is a pointer to "struct main_args" */ + struct main_args* esp; + int argc; + int total_size; + int line_size; + int cmdl_size; + + /* "cmd_line_on_stack" and "ptr_save" are variables that each store + * one address, and at that address (the first) char (of a possible + * sequence) can be found. */ + char* cmd_line_on_stack; + char* ptr_save; + int i = 0; + + + /* calculate the bytes needed to store the command_line */ + line_size = YOUR_CODE_HERE; + STACK_DEBUG("# line_size = %d\n", line_size); + + /* round up to make it even divisible by 4 */ + line_size = YOUR_CODE_HERE; + STACK_DEBUG("# line_size (aligned) = %d\n", line_size); + + /* calculate how many words the command_line contain */ + argc = YOUR_CODE_HERE; + STACK_DEBUG("# argc = %d\n", argc); + + /* calculate the size needed on our simulated stack */ + total_size = YOUR_CODE_HERE; + STACK_DEBUG("# total_size = %d\n", total_size); + + + /* calculate where the final stack top will be located */ + esp = YOUR_CODE_HERE; + + /* setup return address and argument count */ + esp->ret = YOUR_CODE_HERE; + esp->argc = YOUR_CODE_HERE; + /* calculate where in the memory the argv array starts */ + esp->argv = YOUR_CODE_HERE; + + /* calculate where in the memory the words is stored */ + cmd_line_on_stack = YOUR_CODE_HERE; + + /* copy the command_line to where it should be in the stack */ + + /* build argv array and insert null-characters after each word */ + + return esp; /* the new stack top */ +} + +/* The C way to do constants ... */ +#define LINE_SIZE 1024 + +int main() +{ + struct main_args* esp; + char line[LINE_SIZE]; + void* simulated_stack = malloc(4096); + void* simulated_stack_top = (void*)((unsigned long)simulated_stack + 4096); + int i; + const int S = sizeof(void*); + + /* read one line of input, this will be the command-line */ + printf("Enter a command line: "); + custom_getline(line, LINE_SIZE); + + /* put initial content on our simulated stack */ + esp = setup_main_stack(line, simulated_stack_top); + printf("# esp = %0*lx\n", 2*S, (unsigned long)esp); + + if ( (char*)esp >= (char*)simulated_stack_top || + (char*)esp < (char*)simulated_stack ) + { + printf("# ERROR: esp is not inside the allocated stack\n"); + return 1; + } + + /* dump memory area for verification */ + dump(esp, (char*)simulated_stack_top - (char*)esp); + + /* original command-line should not be needed anymore */ + for (i = 0; i < LINE_SIZE; ++i) + line[i] = (char)0xCC; + + /* print the argument vector to see if it worked */ + for (i = 0; i < esp->argc; ++i) + { + printf("argv[%d] = %s\n", i, esp->argv[i]); + } + printf("argv[%d] = %p\n", i, esp->argv[i]); + + free(simulated_stack); + + return 0; +} diff --git a/src/standalone/lab14/pagedir.c b/src/standalone/lab14/pagedir.c new file mode 100644 index 0000000..b60d871 --- /dev/null +++ b/src/standalone/lab14/pagedir.c @@ -0,0 +1,8 @@ +/* The code that simulates and tests your address verification. How + this is done is disclosed. As a student you shall not compile this + file, but instead compile your program with the .o file as: + + gcc -Wall -Wextra -std=c99 -pedantic -m32 -g verify_adr.c pagedir.o + */ +#error Read comment above. Leave this line in place. + diff --git a/src/standalone/lab14/pagedir.h b/src/standalone/lab14/pagedir.h new file mode 100644 index 0000000..2919d1a --- /dev/null +++ b/src/standalone/lab14/pagedir.h @@ -0,0 +1,42 @@ +#ifndef PAGEDIR_H +#define PAGEDIR_H + +typedef int bool; +#define false 0 +#define true 1 + +/* Returns true iff 'adr' contains a null-character ('\0'). */ +bool is_end_of_string(char* adr); + +/* Returns the start address of the page that contains 'adr'. */ +void* pg_round_down(const void* adr); + +/* Returns the page number of the page that contains 'adr'. + * Page numbers are counted with start at zero (0). + */ +unsigned pg_no(const void* adr); + +/* Uses the page table to translate from logic to physical + * address. Returns NULL if the translation fail. + * + * The first parameter specify the top level page table to + * use. Normally you will find it in the structure corresponding + * to your operating systems PCB (Process Control Block). + */ +void *pagedir_get_page (void *pagetable, const void *adr); + +/* Page size: The number of bytes in each page. */ +#define PGSIZE 100 + +/* Functions used to simulate a paging system and testing your + * solution. */ +void start_evaluate_algorithm(void* start, int size); +void evaluate(bool result); +void end_evaluate_algorithm(); + +/* Let us decide how costly a simulated page fault is in terms of + * time. Does not exist in Pintos. Set to zero (0) for faster + * testing. */ +void simulator_set_pagefault_time(unsigned i); + +#endif diff --git a/src/standalone/lab14/pagedir.o b/src/standalone/lab14/pagedir.o new file mode 100644 index 0000000..470080a Binary files /dev/null and b/src/standalone/lab14/pagedir.o differ diff --git a/src/standalone/lab14/thread.h b/src/standalone/lab14/thread.h new file mode 100644 index 0000000..62568ab --- /dev/null +++ b/src/standalone/lab14/thread.h @@ -0,0 +1,16 @@ +#ifndef THREAD_H +#define THREAD_H + +struct thread +{ + /* This is just a part of the Pintos Thread. */ + void* pagedir; +}; + +/* Initiate the threading system. */ +void thread_init(); + +/* Return a pointer to the currently active thread. */ +struct thread* thread_current(); + +#endif diff --git a/src/standalone/lab14/verify_adr.c b/src/standalone/lab14/verify_adr.c new file mode 100644 index 0000000..9bac64f --- /dev/null +++ b/src/standalone/lab14/verify_adr.c @@ -0,0 +1,90 @@ +#include +#include "pagedir.h" +#include "thread.h" + +/* verfy_*_lenght are intended to be used in a system call that accept + * parameters containing suspisious (user mode) adresses. The + * operating system (executng the system call in kernel mode) must not + * be fooled into using (reading or writing) addresses not available + * to the user mode process performing the system call. + * + * In pagedir.h you can find some supporting functions that will help + * you dermining if a logic address can be translated into a physical + * addrerss using the process pagetable. A single translation is + * costly. Work out a way to perform as few translations as + * possible. + * + * Recommended compilation command: + * + * gcc -Wall -Wextra -std=gnu99 -pedantic -m32 -g pagedir.o verify_adr.c + */ +#error Read comment above and then remove this line. + +/* Verify all addresses from and including 'start' up to but excluding + * (start+length). */ +bool verify_fix_length(void* start, int length) +{ + // ADD YOUR CODE HERE +} + +/* Verify all addresses from and including 'start' up to and including + * the address first containg a null-character ('\0'). (The way + * C-strings are stored.) + */ +bool verify_variable_length(char* start) +{ + // ADD YOUR CODE HERE +} + +/* Definition of test cases. */ +struct test_case_t +{ + void* start; + unsigned length; +}; + +#define TEST_CASE_COUNT 6 + +const struct test_case_t test_case[TEST_CASE_COUNT] = +{ + {(void*)100, 100}, /* one full page */ + {(void*)199, 102}, + {(void*)101, 98}, + {(void*)250, 190}, + {(void*)250, 200}, + {(void*)250, 210} +}; + +/* This main program will evalutate your solution. */ +int main(int argc, char* argv[]) +{ + int i; + bool result; + + if ( argc == 2 ) + { + simulator_set_pagefault_time( atoi(argv[1]) ); + } + thread_init(); + + /* Test the algorithm with a given intervall (a buffer). */ + for (i = 0; i < TEST_CASE_COUNT; ++i) + { + start_evaluate_algorithm(test_case[i].start, test_case[i].length); + result = verify_fix_length(test_case[i].start, test_case[i].length); + evaluate(result); + end_evaluate_algorithm(); + } + + /* Test the algorithm with a C-string (start address with + * terminating null-character). + */ + for (i = 0; i < TEST_CASE_COUNT; ++i) + { + start_evaluate_algorithm(test_case[i].start, test_case[i].length); + result = verify_variable_length(test_case[i].start); + evaluate(result); + end_evaluate_algorithm(); + } + return 0; +} diff --git a/src/standalone/labx1/basics.c b/src/standalone/labx1/basics.c new file mode 100644 index 0000000..62bc52c --- /dev/null +++ b/src/standalone/labx1/basics.c @@ -0,0 +1,6 @@ +#include +#include + +int main() +{ +} diff --git a/src/standalone/labx2/fork-wait.c b/src/standalone/labx2/fork-wait.c new file mode 100644 index 0000000..8ef4c07 --- /dev/null +++ b/src/standalone/labx2/fork-wait.c @@ -0,0 +1,95 @@ +#include +#include +#include +#include +#include + +/* The printf text serve as further comments. Read it. */ + +int main(int argc, char* argv[]) +{ + pid_t pid; + char dummy[16]; + + if (argc < 2) + { + printf("You need to specify a program as argument 1.\n"); + exit(1); /* Terminate the process with error (1). */ + } + + printf("P | Switch to a differen terminal.\n" + "P | Execute the command \"pstree $USER\".\n" + "P | It will show a list of processes you are running.\n" + "P | You should see the process '%s' once.\n" + "P | Press enter when you verified that.\n\n", argv[0]); + + /* Wait until enter is pressed (gives you time...) */ + fgets(dummy, 16, stdin); + + printf("P | This process will now clone itself with fork.\n" + "P | One (almost) identical copy will be started.\n" + "P | The only difference is the result of fork()\n\n"); + + pid = fork(); + + if (pid == 0) + { + printf(" C | This is printed by the new process (the CHILD)\n" + " C | The child get a 0 return value from fork.\n\n"); + + printf(" C | Repeat the previous command in the other terminal.\n" + " C | You should see the process '%s' twice now.\n" + " C | (grep for it if you run many processes)\n" + " C | Press enter when you verified that.\n\n", argv[0]); + + /* Wait until enter is pressed (gives you time...) */ + fgets(dummy, 16, stdin); + + printf(" C | The program specified as first argument (%s) on the \n" + " C | command line will now be started by the child process.\n" + " C | This will REPLACE the code of the child with the code\n" + " C | of the specified program.\n\n", argv[1]); + + /* specify a terminal as argument 1 and check ptree again ... + * you will see that the child is replaced, it have the same + * process number, but a new command line + */ + execv(argv[1], argv + 1); + + printf(" C | This will never be printed, since after starting the new\n" + " C | program by calling exec this old program is replaced by\n" + " C | the new. This is only printed if the new program could not\n" + " C | be started for some reason.\n\n"); + + exit(-1); /* Terminate the child with error (-1). */ + } + else + { + int ret = 0; /* Used to save the result of the child. */ + + printf("P | This is printed by the origingal process (the PARENT)\n" + "P | It got the number (%d) from fork to identify the child.\n" + "P | This process will now work for 5 seconds.\n\n", (int)pid); + sleep(5); /* pretend */ + + printf("P | This is printed by the origingal process (the PARENT)\n" + "P | It got the number (%d) from fork to identify the child.\n" + "P | It is now used to wait for the result of that child\n\n", + (int)pid); + + /* Wait for the child to finish and get it's status in ret. */ + waitpid(pid, &ret, 0); + + /* Print the exit status of the child. */ + if (WIFEXITED(ret)) + { + printf("P | Child finished with code %d\n\n", WEXITSTATUS(ret)); + } + else if (WIFSIGNALED(ret)) + { + printf("P | Child finished due to signal %d\n\n", WTERMSIG(ret)); + } + } + + return 0; +} diff --git a/src/standalone/labx3/use-list.c b/src/standalone/labx3/use-list.c new file mode 100644 index 0000000..065f71a --- /dev/null +++ b/src/standalone/labx3/use-list.c @@ -0,0 +1,42 @@ +#include +#include +#include + +/* Pintos contain an implementation of a doubly linked list. It is + * found in ../../lib/kernel/list.[ch]. + * + * Recommended compilation commands: + * + * This is done once: + * gcc -Wall -Wextra -std=gnu99 -pedantic -g -c ../../lib/kernel/list.c + * + * Then use the precomplied list.o: + * gcc -Wall -Wextra -std=gnu99 -pedantic -g use-list.c list.o + */ +#error Read comments above, then remove this line. + +#include "../../lib/kernel/list.h" + +int main() +{ + int i, j; + int N = 1000; + + /* create a list */ + for (i = 2; i < N; ++i) + { + /* insert the value of the loop variable 'i' in the list */ + } + + for (i = 2; i < N; ++i) + { + for (j = i*2; j < N; j += i) + { + /* remove every with 'j' even divisible number from the list */ + } + } + + /* print all remaining numbers in the list and free any memory + * allocated */ + return 0; +} diff --git a/src/standalone/labx4/debug.c b/src/standalone/labx4/debug.c new file mode 100644 index 0000000..d6a3707 --- /dev/null +++ b/src/standalone/labx4/debug.c @@ -0,0 +1,27 @@ +#include + +int main() +{ + char str[] = "sihtgubed"; + char *stri = &str[8]; + char *buf[9]; + char **bufi, **bufend; + bufi = buf; + bufend = &buf[9]; + + while (bufi != bufend){ + *bufi = stri; + bufi++; + stri--; + } + + while (bufi != buf){ + *(*bufi) -= 32; + bufi--; + } + + while (bufi != bufend){ + printf("%c", **bufi); + bufi++; + } +} diff --git a/src/standalone/upg1/basics.c b/src/standalone/upg1/basics.c deleted file mode 100644 index 62bc52c..0000000 --- a/src/standalone/upg1/basics.c +++ /dev/null @@ -1,6 +0,0 @@ -#include -#include - -int main() -{ -} diff --git a/src/standalone/upg2/about-main.c b/src/standalone/upg2/about-main.c deleted file mode 100644 index 2407c23..0000000 --- a/src/standalone/upg2/about-main.c +++ /dev/null @@ -1,6 +0,0 @@ -#include -#include - -int main(int argc, char* argv[]) -{ -} diff --git a/src/standalone/upg3/fork-wait.c b/src/standalone/upg3/fork-wait.c deleted file mode 100644 index 8ef4c07..0000000 --- a/src/standalone/upg3/fork-wait.c +++ /dev/null @@ -1,95 +0,0 @@ -#include -#include -#include -#include -#include - -/* The printf text serve as further comments. Read it. */ - -int main(int argc, char* argv[]) -{ - pid_t pid; - char dummy[16]; - - if (argc < 2) - { - printf("You need to specify a program as argument 1.\n"); - exit(1); /* Terminate the process with error (1). */ - } - - printf("P | Switch to a differen terminal.\n" - "P | Execute the command \"pstree $USER\".\n" - "P | It will show a list of processes you are running.\n" - "P | You should see the process '%s' once.\n" - "P | Press enter when you verified that.\n\n", argv[0]); - - /* Wait until enter is pressed (gives you time...) */ - fgets(dummy, 16, stdin); - - printf("P | This process will now clone itself with fork.\n" - "P | One (almost) identical copy will be started.\n" - "P | The only difference is the result of fork()\n\n"); - - pid = fork(); - - if (pid == 0) - { - printf(" C | This is printed by the new process (the CHILD)\n" - " C | The child get a 0 return value from fork.\n\n"); - - printf(" C | Repeat the previous command in the other terminal.\n" - " C | You should see the process '%s' twice now.\n" - " C | (grep for it if you run many processes)\n" - " C | Press enter when you verified that.\n\n", argv[0]); - - /* Wait until enter is pressed (gives you time...) */ - fgets(dummy, 16, stdin); - - printf(" C | The program specified as first argument (%s) on the \n" - " C | command line will now be started by the child process.\n" - " C | This will REPLACE the code of the child with the code\n" - " C | of the specified program.\n\n", argv[1]); - - /* specify a terminal as argument 1 and check ptree again ... - * you will see that the child is replaced, it have the same - * process number, but a new command line - */ - execv(argv[1], argv + 1); - - printf(" C | This will never be printed, since after starting the new\n" - " C | program by calling exec this old program is replaced by\n" - " C | the new. This is only printed if the new program could not\n" - " C | be started for some reason.\n\n"); - - exit(-1); /* Terminate the child with error (-1). */ - } - else - { - int ret = 0; /* Used to save the result of the child. */ - - printf("P | This is printed by the origingal process (the PARENT)\n" - "P | It got the number (%d) from fork to identify the child.\n" - "P | This process will now work for 5 seconds.\n\n", (int)pid); - sleep(5); /* pretend */ - - printf("P | This is printed by the origingal process (the PARENT)\n" - "P | It got the number (%d) from fork to identify the child.\n" - "P | It is now used to wait for the result of that child\n\n", - (int)pid); - - /* Wait for the child to finish and get it's status in ret. */ - waitpid(pid, &ret, 0); - - /* Print the exit status of the child. */ - if (WIFEXITED(ret)) - { - printf("P | Child finished with code %d\n\n", WEXITSTATUS(ret)); - } - else if (WIFSIGNALED(ret)) - { - printf("P | Child finished due to signal %d\n\n", WTERMSIG(ret)); - } - } - - return 0; -} diff --git a/src/standalone/upg4/use-list.c b/src/standalone/upg4/use-list.c deleted file mode 100644 index 065f71a..0000000 --- a/src/standalone/upg4/use-list.c +++ /dev/null @@ -1,42 +0,0 @@ -#include -#include -#include - -/* Pintos contain an implementation of a doubly linked list. It is - * found in ../../lib/kernel/list.[ch]. - * - * Recommended compilation commands: - * - * This is done once: - * gcc -Wall -Wextra -std=gnu99 -pedantic -g -c ../../lib/kernel/list.c - * - * Then use the precomplied list.o: - * gcc -Wall -Wextra -std=gnu99 -pedantic -g use-list.c list.o - */ -#error Read comments above, then remove this line. - -#include "../../lib/kernel/list.h" - -int main() -{ - int i, j; - int N = 1000; - - /* create a list */ - for (i = 2; i < N; ++i) - { - /* insert the value of the loop variable 'i' in the list */ - } - - for (i = 2; i < N; ++i) - { - for (j = i*2; j < N; j += i) - { - /* remove every with 'j' even divisible number from the list */ - } - } - - /* print all remaining numbers in the list and free any memory - * allocated */ - return 0; -} diff --git a/src/standalone/upg5/pagedir.c b/src/standalone/upg5/pagedir.c deleted file mode 100644 index b60d871..0000000 --- a/src/standalone/upg5/pagedir.c +++ /dev/null @@ -1,8 +0,0 @@ -/* The code that simulates and tests your address verification. How - this is done is disclosed. As a student you shall not compile this - file, but instead compile your program with the .o file as: - - gcc -Wall -Wextra -std=c99 -pedantic -m32 -g verify_adr.c pagedir.o - */ -#error Read comment above. Leave this line in place. - diff --git a/src/standalone/upg5/pagedir.h b/src/standalone/upg5/pagedir.h deleted file mode 100644 index 2919d1a..0000000 --- a/src/standalone/upg5/pagedir.h +++ /dev/null @@ -1,42 +0,0 @@ -#ifndef PAGEDIR_H -#define PAGEDIR_H - -typedef int bool; -#define false 0 -#define true 1 - -/* Returns true iff 'adr' contains a null-character ('\0'). */ -bool is_end_of_string(char* adr); - -/* Returns the start address of the page that contains 'adr'. */ -void* pg_round_down(const void* adr); - -/* Returns the page number of the page that contains 'adr'. - * Page numbers are counted with start at zero (0). - */ -unsigned pg_no(const void* adr); - -/* Uses the page table to translate from logic to physical - * address. Returns NULL if the translation fail. - * - * The first parameter specify the top level page table to - * use. Normally you will find it in the structure corresponding - * to your operating systems PCB (Process Control Block). - */ -void *pagedir_get_page (void *pagetable, const void *adr); - -/* Page size: The number of bytes in each page. */ -#define PGSIZE 100 - -/* Functions used to simulate a paging system and testing your - * solution. */ -void start_evaluate_algorithm(void* start, int size); -void evaluate(bool result); -void end_evaluate_algorithm(); - -/* Let us decide how costly a simulated page fault is in terms of - * time. Does not exist in Pintos. Set to zero (0) for faster - * testing. */ -void simulator_set_pagefault_time(unsigned i); - -#endif diff --git a/src/standalone/upg5/pagedir.o b/src/standalone/upg5/pagedir.o deleted file mode 100644 index 470080a..0000000 Binary files a/src/standalone/upg5/pagedir.o and /dev/null differ diff --git a/src/standalone/upg5/thread.h b/src/standalone/upg5/thread.h deleted file mode 100644 index 62568ab..0000000 --- a/src/standalone/upg5/thread.h +++ /dev/null @@ -1,16 +0,0 @@ -#ifndef THREAD_H -#define THREAD_H - -struct thread -{ - /* This is just a part of the Pintos Thread. */ - void* pagedir; -}; - -/* Initiate the threading system. */ -void thread_init(); - -/* Return a pointer to the currently active thread. */ -struct thread* thread_current(); - -#endif diff --git a/src/standalone/upg5/verify_adr.c b/src/standalone/upg5/verify_adr.c deleted file mode 100644 index 9bac64f..0000000 --- a/src/standalone/upg5/verify_adr.c +++ /dev/null @@ -1,90 +0,0 @@ -#include -#include "pagedir.h" -#include "thread.h" - -/* verfy_*_lenght are intended to be used in a system call that accept - * parameters containing suspisious (user mode) adresses. The - * operating system (executng the system call in kernel mode) must not - * be fooled into using (reading or writing) addresses not available - * to the user mode process performing the system call. - * - * In pagedir.h you can find some supporting functions that will help - * you dermining if a logic address can be translated into a physical - * addrerss using the process pagetable. A single translation is - * costly. Work out a way to perform as few translations as - * possible. - * - * Recommended compilation command: - * - * gcc -Wall -Wextra -std=gnu99 -pedantic -m32 -g pagedir.o verify_adr.c - */ -#error Read comment above and then remove this line. - -/* Verify all addresses from and including 'start' up to but excluding - * (start+length). */ -bool verify_fix_length(void* start, int length) -{ - // ADD YOUR CODE HERE -} - -/* Verify all addresses from and including 'start' up to and including - * the address first containg a null-character ('\0'). (The way - * C-strings are stored.) - */ -bool verify_variable_length(char* start) -{ - // ADD YOUR CODE HERE -} - -/* Definition of test cases. */ -struct test_case_t -{ - void* start; - unsigned length; -}; - -#define TEST_CASE_COUNT 6 - -const struct test_case_t test_case[TEST_CASE_COUNT] = -{ - {(void*)100, 100}, /* one full page */ - {(void*)199, 102}, - {(void*)101, 98}, - {(void*)250, 190}, - {(void*)250, 200}, - {(void*)250, 210} -}; - -/* This main program will evalutate your solution. */ -int main(int argc, char* argv[]) -{ - int i; - bool result; - - if ( argc == 2 ) - { - simulator_set_pagefault_time( atoi(argv[1]) ); - } - thread_init(); - - /* Test the algorithm with a given intervall (a buffer). */ - for (i = 0; i < TEST_CASE_COUNT; ++i) - { - start_evaluate_algorithm(test_case[i].start, test_case[i].length); - result = verify_fix_length(test_case[i].start, test_case[i].length); - evaluate(result); - end_evaluate_algorithm(); - } - - /* Test the algorithm with a C-string (start address with - * terminating null-character). - */ - for (i = 0; i < TEST_CASE_COUNT; ++i) - { - start_evaluate_algorithm(test_case[i].start, test_case[i].length); - result = verify_variable_length(test_case[i].start); - evaluate(result); - end_evaluate_algorithm(); - } - return 0; -} diff --git a/src/standalone/upg6/main.c b/src/standalone/upg6/main.c deleted file mode 100644 index c481d40..0000000 --- a/src/standalone/upg6/main.c +++ /dev/null @@ -1,124 +0,0 @@ -#include -#include -#include - -#include "map.h" - -/* Recommended compile commmand: - * - * gcc -Wall -Wextra -std=gnu99 -pedantic -g main.c map.c - * - * Recommended way to test your solution: - * - * valgrind --tool=memcheck ./a.out - */ -#error Read comments above, then remove this line. - - -/* Can be used to inform compiler about unused parameters (prevent - * warning). Useful when a funtion pointer expect a certain set of - * parameters, but you only need some of them. */ -#define UNUSED __attribute__((unused)) - -/* The code assumes that key_t is `int' and value_t is `char*' */ - -/* function passed as parameter to map_remove_if in order to free the - * memory for all inseted values, and return true to remove them from - * the map */ -bool do_free(key_t k UNUSED, value_t v, int aux UNUSED) -{ - free(v); /*! free memory */ - return true; /* and remove from collection */ -} - -/* function to display all values in the map that are less than the - * aux argument */ -void print_less(key_t k UNUSED, value_t v, int aux) -{ - /* atoi converst from sequence of character to integer, it will fail - * when the characters are letters, check the manpage to see how */ - if ( atoi(v) < aux) - { - printf("%s ", v); - } -} - - -#define LOOPS 10 - -char* my_strdup(char* str) -{ - /*! calculate the length and add space for '\0' */ - int len = strlen(str) + 1; - /*! allocate memory just large enough */ - char* dst = (char*)malloc(len); - /*! copy all characters in src to dst */ - strncpy(dst, str, len); - - return dst; /*(!) return our deep copy of str */ -} - -int main() -{ - struct map container; - char input_buffer[10]; - char* obj; - int id; - int i; - - map_init(&container); - - /* remember to try to insert more values than you map can hold */ - printf("Insert values: "); - for ( i = 0; i < LOOPS; ++i) - { - /* insecure, scanf may overflow the input buffer array * - * very serious, but we ignore it in this test program */ - scanf("%s", input_buffer); - - /*! allocates a copy of the input and inserts in map */ - obj = my_strdup(input_buffer); - id = map_insert(&container, obj); - } - - /* remember to test with invalid keys (like 4711, or -1) */ - for ( i = 0; i < LOOPS; ++i) - { - printf("Enter id to find value for: "); - scanf("%d", &id); - - /*! find the value for a key in the map */ - obj = map_find(&container, id); - - /*! if it was found, display it */ -YOUR CODE - - /* since we leave the value in the map we may use it again and - * should not free the memory */ - } - - /* remember to test with invalid keys (like 4711, or -1) */ - for ( i = 0; i < LOOPS; ++i) - { - printf("Enter id to remove value for: "); - scanf("%d", &id); - - /*! find and remove a value for a key in the map */ - obj = map_remove(&container, id); - - /*! if it was found, display it */ -YOUR CODE - /* since we removed the value from the map we will never use it again and - * must properly free the memory (if it was allocated) */ - } - - /*! print all strings representing an integer less than N */ - printf("Will now display all values less than N. Choose N: "); - scanf("%d", &i); - map_for_each(&container, print_less, i); - - /*! free all remaining memory and remove from map */ - map_remove_if(&container, do_free, 0); - - return 0; -} diff --git a/src/standalone/upg6/map.c b/src/standalone/upg6/map.c deleted file mode 100644 index b323fbb..0000000 --- a/src/standalone/upg6/map.c +++ /dev/null @@ -1 +0,0 @@ -#include "map.h" diff --git a/src/standalone/upg6/map.h b/src/standalone/upg6/map.h deleted file mode 100644 index 9029ff5..0000000 --- a/src/standalone/upg6/map.h +++ /dev/null @@ -1 +0,0 @@ -/* do not forget the guard against multiple includes */ diff --git a/src/standalone/upg7/debug.c b/src/standalone/upg7/debug.c deleted file mode 100644 index d6a3707..0000000 --- a/src/standalone/upg7/debug.c +++ /dev/null @@ -1,27 +0,0 @@ -#include - -int main() -{ - char str[] = "sihtgubed"; - char *stri = &str[8]; - char *buf[9]; - char **bufi, **bufend; - bufi = buf; - bufend = &buf[9]; - - while (bufi != bufend){ - *bufi = stri; - bufi++; - stri--; - } - - while (bufi != buf){ - *(*bufi) -= 32; - bufi--; - } - - while (bufi != bufend){ - printf("%c", **bufi); - bufi++; - } -} diff --git a/src/standalone/upg8/setup-argv.c b/src/standalone/upg8/setup-argv.c deleted file mode 100644 index f2bd04a..0000000 --- a/src/standalone/upg8/setup-argv.c +++ /dev/null @@ -1,277 +0,0 @@ -#define _POSIX_C_SOURCE 2 -#include -#include -#include - -/* - YOUR WORK: - - You will complete the function setup_main_stack below. Missing code - and calculations are expressed with a questionmark (?). The - assignment is mostly about doing the correct math. To do that math - you will need to learn or understand: - - - How the stack is used during program execution - - How the stack is expected to look like at start of a C-program - - What a pointer variable is, how it is used - - How a C-array (pointer to many) is laid-out in memory - - How pointer arithmetic behaves - - How to cast from one pointer type to another - - How to use printf to print good debug information - - How to use a C-struct, both object and pointer to - - Some manual-pages of interest: - - man -s3 printf - man -s3 strlen - man -s3 strncpy - man -s3 strtok_r - - The prototype for above functions: - - int printf(const char *restrict format, ...); - size_t strlen(const char *s); - size_t strncpy(char *dst, const char *src, size_t dstsize); - char *strtok_r(char *s1, const char *s2, char **lasts); - - The above functions exist in Pintos code. Note the Pintos use - 'strlcpy' instead of 'strncpy'. If 'dst' is large enough they behave - identical. You can find Pintos implementations in - /home/TDIU16/labs/skel/pintos/src/lib, see string.c and stdio.c. It - is strongly recommendable to look at the strtok_r examples given in - string.c - - About *restrict: http://en.wikipedia.org/wiki/Pointer_alias - - - Recommended compile command: - - gcc -m32 -Wall -Wextra -std=gnu99 -g setup-argv.c - -*/ -#error Read comments above, then remove this line. - -#define true 1 -#define false 0 - -typedef int bool; - -/* "struct main_args" represent the stack as it must look when - * entering main. The only issue: argv must point somewhere... - * - * The members of this structure is is directly related to the - * arguments of main in a C-program, of course. - * - * int main(int argc, char* argv[]); - * - * (char** argv is a more generic form of char* argv[]) - * - * The function pointer is normally handled by the compiler - * automatically, and determine the address at where a function shall - * continue when it returns. The main function does not use it, as the - * operating system arrange for the program to stop execution when - * main is finished. - */ -struct main_args -{ - /* Hint: When try to interpret C-declarations, read from right to - * left! It is often easier to get the correct interpretation, - * altough it does not always work. */ - - /* Variable "ret" that stores address (*ret) to a function taking no - * parameters (void) and returning nothing. */ - void (*ret)(void); - - /* Just a normal integer. */ - int argc; - - /* Variable "argv" that stores address to an address storing char. - * That is: argv is a pointer to char* - */ - char** argv; -}; - -/* A function that dumps 'size' bytes of memory starting at 'ptr' - * it will dump the higher adress first letting the stack grow down. - */ -void dump(void* ptr, int size) -{ - int i; - const int S = sizeof(void*); - - printf("%2$-*1$s \t%3$-*1$s \t%4$-*1$s\n", S*2, "Address", "hex-data", "char-data"); - - for (i = size - 1; i >= 0; --i) - { - void** adr = (void**)((unsigned long)ptr + i); - unsigned char* byte = (unsigned char*)((unsigned long)ptr + i); - - printf("%0*lx\t", S*2, (unsigned long)ptr + i); /* address */ - - if ((i % S) == 0) - /* seems we're actually forbidden to read unaligned adresses */ - printf("%0*lx\t", S*2, (unsigned long)*adr); /* content interpreted as address */ - else - printf("%*c\t", S*2, ' '); /* fill */ - - if(*byte >= 32 && *byte < 127) - printf("%c\n", *byte); /* content interpreted as character */ - else - printf("\\%o\n", *byte); - - if ((i % S) == 0) - printf("----------------------------------------------------------------\n"); - } -} - -/* Read one line of input ... - */ -void custom_getline(char buf[], int size) -{ - int i; - for (i = 0; i < (size - 1); ++i) - { - buf[i] = getchar(); - if (buf[i] == '\n') - break; - } - buf[i] = '\0'; -} - -/* Return true if 'c' is fount in the c-string 'd' - * NOTE: 'd' must be a '\0'-terminated c-string - */ -bool exists_in(char c, const char* d) -{ - int i = 0; - while (d[i] != '\0' && d[i] != c) - ++i; - return (d[i] == c); -} - -/* Return the number of words in 'buf'. A word is defined as a - * sequence of characters not containing any of the characters in - * 'delimeters'. - * NOTE: arguments must be '\0'-terminated c-strings - */ -int count_args(const char* buf, const char* delimeters) -{ - int i = 0; - bool prev_was_delim; - bool cur_is_delim = true; - int argc = 0; - - while (buf[i] != '\0') - { - prev_was_delim = cur_is_delim; - cur_is_delim = exists_in(buf[i], delimeters); - argc += (prev_was_delim && !cur_is_delim); - ++i; - } - return argc; -} - -/* Replace calls to STACK_DEBUG with calls to printf. All such calls - * easily removed later by replacing with nothing. */ -#define STACK_DEBUG(...) printf(__VA_ARGS__) - -void* setup_main_stack(const char* command_line, void* stack_top) -{ - /* Variable "esp" stores an address, and at the memory loaction - * pointed out by that address a "struct main_args" is found. - * That is: "esp" is a pointer to "struct main_args" */ - struct main_args* esp; - int argc; - int total_size; - int line_size; - int cmdl_size; - - /* "cmd_line_on_stack" and "ptr_save" are variables that each store - * one address, and at that address (the first) char (of a possible - * sequence) can be found. */ - char* cmd_line_on_stack; - char* ptr_save; - int i = 0; - - - /* calculate the bytes needed to store the command_line */ - line_size = YOUR_CODE_HERE; - STACK_DEBUG("# line_size = %d\n", line_size); - - /* round up to make it even divisible by 4 */ - line_size = YOUR_CODE_HERE; - STACK_DEBUG("# line_size (aligned) = %d\n", line_size); - - /* calculate how many words the command_line contain */ - argc = YOUR_CODE_HERE; - STACK_DEBUG("# argc = %d\n", argc); - - /* calculate the size needed on our simulated stack */ - total_size = YOUR_CODE_HERE; - STACK_DEBUG("# total_size = %d\n", total_size); - - - /* calculate where the final stack top will be located */ - esp = YOUR_CODE_HERE; - - /* setup return address and argument count */ - esp->ret = YOUR_CODE_HERE; - esp->argc = YOUR_CODE_HERE; - /* calculate where in the memory the argv array starts */ - esp->argv = YOUR_CODE_HERE; - - /* calculate where in the memory the words is stored */ - cmd_line_on_stack = YOUR_CODE_HERE; - - /* copy the command_line to where it should be in the stack */ - - /* build argv array and insert null-characters after each word */ - - return esp; /* the new stack top */ -} - -/* The C way to do constants ... */ -#define LINE_SIZE 1024 - -int main() -{ - struct main_args* esp; - char line[LINE_SIZE]; - void* simulated_stack = malloc(4096); - void* simulated_stack_top = (void*)((unsigned long)simulated_stack + 4096); - int i; - const int S = sizeof(void*); - - /* read one line of input, this will be the command-line */ - printf("Enter a command line: "); - custom_getline(line, LINE_SIZE); - - /* put initial content on our simulated stack */ - esp = setup_main_stack(line, simulated_stack_top); - printf("# esp = %0*lx\n", 2*S, (unsigned long)esp); - - if ( (char*)esp >= (char*)simulated_stack_top || - (char*)esp < (char*)simulated_stack ) - { - printf("# ERROR: esp is not inside the allocated stack\n"); - return 1; - } - - /* dump memory area for verification */ - dump(esp, (char*)simulated_stack_top - (char*)esp); - - /* original command-line should not be needed anymore */ - for (i = 0; i < LINE_SIZE; ++i) - line[i] = (char)0xCC; - - /* print the argument vector to see if it worked */ - for (i = 0; i < esp->argc; ++i) - { - printf("argv[%d] = %s\n", i, esp->argv[i]); - } - printf("argv[%d] = %p\n", i, esp->argv[i]); - - free(simulated_stack); - - return 0; -} -- cgit v1.2.1