From 4f670845ff9ab6c48bcb5f7bf4d4ef6dc3c3064b Mon Sep 17 00:00:00 2001 From: manuel Date: Tue, 27 Mar 2012 11:51:08 +0200 Subject: reorganize file structure to match the upstream requirements --- notes/1.txt | 81 ++++++++++++++++++++ notes/2.txt | 164 +++++++++++++++++++++++++++++++++++++++++ notes/3.txt | 241 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 486 insertions(+) create mode 100644 notes/1.txt create mode 100644 notes/2.txt create mode 100644 notes/3.txt (limited to 'notes') diff --git a/notes/1.txt b/notes/1.txt new file mode 100644 index 0000000..9d478f7 --- /dev/null +++ b/notes/1.txt @@ -0,0 +1,81 @@ +Getting Started with PINTOS +=========================== + +Building Project 1 +------------------ + +pintos $ cd src/threads +threads $ make + + +Building Bochs +-------------- +You should have a patched bochs install available. + +See + + http://courses.mpi-sws.org/os-ss11/assignments/pintos/pintos_12.html#SEC160 + +There is a build script src/misc/bochs-2.3.7-build.sh in the pintos fork from Saarland, +which (after small modifications) works on a modern Ubuntu x86. + +For Ubuntu 11 with a Linux 3.0 kernel, you need to: + + * Regenerate the configure script (autoconf configure.in) + * Patch the test for Linux 2.4 or 2.6 + +After building, copy bochs and bochs-gdb to the pintos/src/utils directory + +Running +------- + + # [pintos/src] + PATH=`pwd`/utils:$PATH + + cd threads/build + # [pintos/src/threads/build] + pintos run alarm-multiple > logfile + + +### Reproducability + +This command line flags to pintos influence reproducability. +Remember: you need the patched bochs build. + + -j seed ... Reproducible behavior + -r ... Real-Time behavior + +Running with qemu +----------------- + + # [pintos/src] + vim utils/pintos # comment line with -no-kqemu flag + + cd threads/build + # [pintos/src/threads/build] + pintos --qemu -- run alarm-multiple + +Debugging +--------- + +pintos $ vim utils/pintos-gdb + + GDBMACROS=${PINTOS_SRC}/misc/gdb-macros + +[pts/0 build] $ pintos --gdb -- run alarm-multiple +[pts/1 build] $ pintos-gdb kernel.o +(gdb) debugpintos + +Testing +------- + +* Running all tests + + build $ make check + +* Running a single test + + build $ rm tests/threads/alarm-multiple.result + build $ make tests/threads/alarm-multiple.result + + diff --git a/notes/2.txt b/notes/2.txt new file mode 100644 index 0000000..c81b980 --- /dev/null +++ b/notes/2.txt @@ -0,0 +1,164 @@ +Projekt 1 - Threads +=================== + +alarm clock +----------- +The simplest strategy is to maintain a wait list for +all threads blocked for sleep. + + * In 'timer_interrupt', check for threads which can be + unblocked from sleeping + * In 'sleep', set sleep timeout in thread, block the + thread and put it on the sleep list + +Notes: + + * There are three places where a thread is added to the + ready list: + - thread_init + - thread_yield + - thread_unblock + * Iterate list with removal: + for (e = list_begin (&list); e != list_end (&list); ) + if(...) + e = list_remove(e)->prev; + /* Unblock must be called AFTER removing, as thread.elem is reused */ + else + e = list_next(e); + +Stats: + + pintos/src/devices/timer.c | 40 ++++++++++++++++++++++++++++++++++++++-- + pintos/src/threads/thread.h | 3 +++ + 2 files changed, 41 insertions(+), 2 deletions(-) + + Design & Implementation time: 4 hours + +Priority Scheduler +------------------ + +A simple implementation of the priority scheduler (64 priority levels, round robin within +one priority group). + + * If a new task arrives with a higher priority, switch to this group + * If the currently active group is empty, search for the group with the next highest priority + +Notes: + + * thread_{init,unblock,yield} now call thread_ready, which updates the lowest ready priority + * The thread_unblock operation does not yield a new thread immediately. Therefore, we need to check + later whether we need to switch to a higher priority thread (via thread_yield). + As thread_unblock is called with interrupts off, it seemed best to perform + this check when interrupts are enabled. This is only necessary if a higher priority task + is ready. + * First attempt passed alarm-priority, but failed to pass the priority-preempt test. + But the debugging facilities are fantastic, so it was easy to spot the problem + * Wolfgang suggested to yield a software interrupt when unblocking instead of modifying + interrupt_enable. + +Stats: + + pintos/src/threads/interrupt.c | 3 +- + pintos/src/threads/thread.c | 60 ++++++++++++++++++++++++++++++++-------- + pintos/src/threads/thread.h | 1 + + 3 files changed, 51 insertions(+), 13 deletions(-) + + Design and implementation time: 3 hours + +Priority Locks +-------------- + +We also need to select higher priority task first from locks, semaphores and condition variables. +This easiest implementation searches for the thread with the highest priority in the wait queue. + +Notes: + + * It is sufficient to implement the priority based selection twice, for sema_up and + cond_signal. cond_signal is a little bit harder, as we need to store the priority + (or the waiting thread) in the semaphore_elem type + * There are some handy list utility functions; in this case, list_max does a fine job + for both sema_up and cond_signal + * It is difficult to implement this in an efficient (sublinear) way, because priority donation + may boost a thread at any time! + +Stats: + + pintos/src/threads/synch.c | 40 ++++++++++++++++++++++++++++++++++------ + 1 files changed, 34 insertions(+), 6 deletions(-) + + Design and Implementation time: 1 hour + +Priority Donation +----------------- +If a thread aquires a lock, the lock holder needs to be boosted to the donated priority. +We need to deal with nesting and chaining: + + * Lock/Thread correspondence: Each lock is associated with at most one thread that holds it. + Therefore, donated priority can be associated with a lock. + * If a thread t wants to obtain a lock L, and a thread with a lower priority holds it, + the thread holding the lock is boosted to the priority of the requesting thread + * Chaining: If the boosted thread is also blocked on a lock, than we also need to donate + the priority to that lock, in a transitive way. + * Nesting: If a thread may hold more than one lock, we need to keep track of the donation + to each lock. When a lock is released or the static priority changes, the highest priority + donated to other locks is assigned to the thread. + +With this information, the following rules seem suitable (without proof of correctness): + + * If thread T tries to aquire lock L + + ==> if(L.owner) + T.locked_on = L + donate_priority (L, T.priority) + end + donate_priority (L ,p) := + L.priority v= p + L.holder.priority v= p + donate_priority( L.holder.locked_on, p) + end + + * If a thread T aquires a lock L + + ==> L.holder = T + T.locks += L + T.lock_on = none + + + * If a thread T releases a lock L + + ==> L.holder = none + T.locks -= L + T.priority = max (T.locks.priority, static_priority) + +To implement this, each thread needs to maintain a list of locks, a static priority, +and a reference to the lock blocking it. + +Notes: + + * Difficult to design, really a challenge. + Literature (short paper) could be helpful. + Maybe it would be interesting to ask for correctness proof sketches? + + * First design was wrong, because I assumed locks are aquired in FIFO fashion + * First implementation failed to pass donate tests, due to a typo. Debugging + facilities are fantastic, no problem to spot this one. + * Next try, priority-donate-lower failed. Looking at the source code revealed that + we need to recompute the priority at the end of thread_set_priority. + * Next try, priority-donate-chain failed. Chaining is tricky to get right; + in my implementation, chained donations were lost after one lock was released. + + * It would be an interesting option to ask for new test cases from the students + * I think it would also be a cool task to write a test for a RMS scheduling + scenario with blocking. + +Stats: + + pintos/src/threads/synch.c | 15 ++++++++++++ + pintos/src/threads/synch.h | 6 +++- + pintos/src/threads/thread.c | 53 +++++++++++++++++++++++++++++++++++++++++- + pintos/src/threads/thread.h | 9 ++++++- + pintos/src/utils/pintos | 2 +- + + Design: 5h + Implementation: 3h + diff --git a/notes/3.txt b/notes/3.txt new file mode 100644 index 0000000..bc64f88 --- /dev/null +++ b/notes/3.txt @@ -0,0 +1,241 @@ +Project 2 +========= + +Working with Disks +------------------ + +Assumes you ran make in src/userprog and src/examples. + + * Create a 2 MB hard disk for pintos + + # [src/userprog/build] + pintos-mkdisk filesys.dsk --filesys-size=2 + + * Format Disk + + # -f ... format virtual disk + pintos -f -q + + * Copy file to filesystem + + # -p FILE ... file to put on virtual disk + # -a FILE ... newname on virtual disk + pintos -p ../../examples/echo -a echo -- -q + + * Execute echo, and get file 'echo' from the virtual disk + + pintos -g echo -- -q run 'echo x' + +Putting all together, we can run an minimal example like that: + + # [src/userprog/build] + pintos --filesys-size=2 -p ../../examples/halt -a halt -- -f -q run 'halt' + +Getting Started +--------------- + + * Fix the problem with the .note.gnu.build-id segment + + * Change the stack setup in process.c#setup_stack() to + + *esp = PHYS_BASE - 12; + + * Change process_wait() to an infinite loop + +This should be enough to see 'system call!' when executing +the 'halt' example. + +Next, we need to implement user memory access and the +the system call dispatcher, as well as the basic +system calls halt, exit and write. + +A simple implementation of user memory access first checks +whether the address is in user space, and the calls load_page. + +For an initial system call dispatcher, we convert the stack pointer +saved by the processor during the interrupt to kernel space, and +then dispatch to halt, exit and write. For now, exit just terminates +the process, and write uses printf, ignoring the fd argument. +The return value is stored into %eax. + +Notes: + * halt(): There is no function shutdown() in init.h, only + shutdown_poweroff in shutdown.h + + * When accessing data from user space in kernel space, we need to be + sure that the entire address ranged accessed is in user space. + Note that pointers are not necessarily aligned, and thus might + involve two user pages. + Furthermore, buffers need to be copied to kernel space; + otherwise, concurrent user space operations could corrupt the kernel. + Linux allows at most one kernel page for such buffers; we follow + the same route. + + * Debugging: the function hex_dump() is useful; no need to + reimplement it. + + * Something went wrong with the write system call, and this + is rather tricky to debug. + I invoked the system call directly, using inline + assembly; this worked fine? + Then I tried to debug the user space program; to this + end, lookup the code address you are interested in, + and use gdb together with objdump for debugging: + + Debugging 'write(1,"USA\n",4)' + + break *0x0804820e # break at + cont # pushl 0xc(%esp) + info registers # esp = 0xbfffffbc + x/1w (0xbfffffbc+0xc) # ==> 4 (length) + stepi # pushl 0x8(%esp) + info registers # esp = 0x......b8 + x/1w 0xbfffffb8 # ==> 4 (TOS) + x/1w (0xbfffffb8+8) # ==> 1 (wrong) !!! + + Apparently, the inline assembler in pintos does not use + the right constraints. + +Stat: + pintos/src/lib/user/syscall.c | 6 +- + pintos/src/userprog/process.c | 5 ++- + pintos/src/userprog/syscall.c | 92 ++++++++++++++++++++++++++++++++++++++-- + + Reading and Implementation Time: 6 hours + Debugging Syscalls: 5 hours + + +Argument Passing +---------------- +First, we tokenize the command using strtok_r, and then setup +the stack. + +Notes: + * As noted in the doc, just using strtok_r seems fine. + However, as strtok_r modifies the string even if only + the first token is needed, some copying is involved + if it is used to obtain the filename. + * Due to the detailed description in the documentation, + setting up the stack is mostly implementation work. + * One of the trickier implementation aspects is that we + modify the stack in kernel space, but need to convert + pointers to user space before pushing them on the stack. + * Debugging: Optimizations were really troublesome debugging + this task; making setup_stack non-static at least helped + to set a suitable breakpoint. In the end, printf was the + better debugging aid for this task. + +Stat: + pintos/src/userprog/process.c | 116 +++++++++++++++++++++++++++++++++-------- + + Design and Implementation Time: 4 hours + + +Process Management: exec, wait and exit +--------------------------------------- +The wait system call requires that all children +of a process are known, that the exit code of +a process is stored until collected by the parent, +and that the parent can block until the child +process terminates. + +One difficult aspect in the design is that kernel +threads are not processes, and that child threads +may exit after their parent. It is important to +note that threads do not need to wait for their +children, but that we need to keep the exit status +until the parent exits. + +In the original design, a thread is cleaned up when +in the scheduler right after it died. In our design +we delay the cleanup if the parent thread is still alive. + +Another issue is that thread_create needs to block +until the load process of the child thread has finished. + +Notes: + * I wanted to use the same semaphore for startup and wait. + This works, but we need one additional variable (or bit) + to distinguish failure at load time from failure at + runtime. + * Ugly 1: thread_create only gives back a tid, + so it is not possible to directly access the semaphore + in process_execute. Therefore we need to iterate over the + child list (which is not that bad, because if loading failed, + the child needs to be removed from the list anyway). + * Ugly 2: We up the semaphore used to synchronize + with process_execute and process_wait in thread.c, for + all threads. + * As also noted by rene, it is important to identifiy memory leaks, + as early as possible. To this end, first add debug messages to + page_alloc/page_free, and then run test programs to identify leaking + pages. Then debug, add conditional breakpoints to stop when a leaking + page is allocated, and inspect the stacktrace to find the culprit. + +Stats: + pintos/src/threads/thread.c | 31 +++++++++++++++++--- + pintos/src/threads/thread.h | 8 +++++ + pintos/src/userprog/process.c | 60 ++++++++++++++++++++++++++++++++-------- + pintos/src/userprog/syscall.c | 19 +++++++++--- + + Design and Implementation Time: 7 hours + +File I/O System Calls +--------------------- +For file I/O we need to implement synchronization (filesys is not thread safe). +The documentation states that it is not recommended to modify the code in +the filesys directory for now. A very simple solution is to use one lock for all filesystem operations, including process.c#load. +Furthermore, we need to deny writes to a a file currently running as a user +space process. + +Notes: + * init_thread() must not aquire locks, and thus not allocate pages. + Otherwise, the initialization of the init thread fails. + * The {lg,sm}-full tests failed in the initial implementation; + apparently, the read/write system calls should always read/write the + full amount of bytes specified to pass this tests. This was not + clear from the assignment. + * It is not obvious that file_close calls file_allow_write. But an + executable should not be writeable during its execution. Therefore, + one needs to make sure that it stays write protected after loading + has finished. I solve this by keeping the executable open during + execution. + * The multi-oom test failed again; debugging revealed that I forgot + to close all files at process_exit. + +Stats: + + pintos/src/threads/thread.c | 1 + + pintos/src/threads/thread.h | 6 +- + pintos/src/userprog/process.c | 53 ++++- + pintos/src/userprog/process.h | 2 + + pintos/src/userprog/syscall.c | 435 +++++++++++++++++++++++++++++++----- + pintos/src/userprog/syscall.h | 1 + + 6 files changed, 381 insertions(+), 117 deletions(-) + Design and Implementation Time: 8 hours + +Improved User Memory Access +--------------------------- +Looking at Project 3, it is a much better idea to not check whether a user +space page is valid, but just let the page fault handler do the job. +I decided to exit the process in the page fault handler if the address +is in user space. One needs to take care of temporary memory allocated +by the syscall handler, to avoid memory leaks. To this end, temporary kernel +pages allocated in the handler are recorded and either freed at the end +of the syscall or the end of the process. + +Notes: + * When using this approach, it is vital to copy user buffers + before reading or writing. With virtual memory, a page fault may + require to access the file system, and thus may cause race + conditions during access to the file system + +Stats: + pintos/src/threads/thread.h | 5 +- + pintos/src/userprog/exception.c | 17 ++- + pintos/src/userprog/process.c | 2 +- + pintos/src/userprog/syscall.c | 314 +++++++++++++++++++-------------------- + pintos/src/userprog/syscall.h | 2 +- + 5 files changed, 173 insertions(+), 167 deletions(-) + + Implementation Time: 3 hours -- cgit v1.2.3