reorganize file structure to match the upstream requirements

3 files changed, 486 insertions, 0 deletions

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 <write>
+          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