Merge branch 'master' into external_pager_mechanism

Conflicts:
	microkernel/mach/external_pager_mechanism.mdwn

10 files changed, 363 insertions, 0 deletions

diff --git a/microkernel/viengoos/building.mdwn b/microkernel/viengoos/building.mdwn
new file mode 100644
index 00000000..45111c35
--- /dev/null
+++ b/microkernel/viengoos/building.mdwn
@@ -0,0 +1,100 @@
+[[!meta copyright="Copyright © 2008, 2009 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+Check out Viengoos and switch to the viengoos-on-bare-metal branch
+(all development is currently done on this branch and it will
+eventually be merged into the master branch):
+
+    $ git clone git://git.savannah.gnu.org/hurd/viengoos.git
+    $ cd viengoos
+    $ git checkout -b viengoos-on-bare-metal origin/viengoos-on-bare-metal
+
+Generate the autoconf environment (note that --force is not specified
+as we have our own version of config.guess and config.sub):
+
+    $ autoreconf -i
+
+Configure a build directory:
+
+    $ mkdir build
+    $ cd build
+    $ ../configure --host=x86_64-pc-viengoos-gnu --with-newlib
+
+Now, build Viengoos.  Running make the first time will automatically
+fetch binutils and gcc from the Internet and build a cross compiler.
+Running make again will build the Viengoos proper.  Again, the build
+process with fetch several tarballs including Newlib, the Boehm GC and
+Sqlite.
+
+    $ make
+    ...
+    The cross compiler is now set-up.  Re-run `make' and proceed as usual.
+    make[2]: Leaving directory `.../viengoos/build'
+    make[1]: Leaving directory `.../viengoos/build'
+    $ make
+
+# Booting Using QEMU
+
+To boot Viengoos, use Grub 2.  You cannot use Grub Legacy: Viengoos is
+an ELF64 executable, which Grub Legacy does not support.
+
+First, check out Grub 2 from svn:
+
+    $ svn co svn://svn.savannah.gnu.org/grub/trunk/grub2
+    $ cd grub2
+
+Before building Grub 2, you should apply the following patch, which
+makes it easy to tell Grub to load a specific grub.cfg at start up
+([details](http://lists.gnu.org/archive/html/grub-devel/2009-01/msg00099.html)).
+
+    $ wget http://www.gnu.org/software/hurd/microkernel/viengoos/grub2-config.diff -O /dev/stdout | patch -p0
+
+Next, build Grub 2:
+
+    $ ./autogen.sh
+    $ mkdir build
+    $ cd build
+    $ ../configure --prefix=`pwd`/../install
+    $ make && make install
+
+Create the boot disk:
+
+    $ cd ../install
+    $ bin/grub-mkrescue boot.img  --configfile="(hd0,1)/grub.cfg" --image-type=floppy --modules='help reboot serial multiboot pc configfile normal boot fat'
+
+Now, create /viengoos and link viengoos and hieronymus into that
+directory:
+
+    $ mkdir /viengoos
+    $ cd /viengoos
+    $ ln -s ~/viengoos/build/viengoos/viengoos.stripped viengoos
+    $ ln -s ~/viengoos/build/hieronymus/hieronymus.stripped hieronymus
+
+Also, create a grub.cfg file in /viengoos/grub.cfg:
+
+    set timeout=1
+    set default=0
+    set root=hd0,1
+    
+    menuentry "Viengoos" {
+        multiboot /viengoos -D 3 -o serial
+        module /hieronymus
+    }
+
+NB: If you edit grub.cfg and a backup file called grub.cfg~ is
+created, qemu will use grub.cfg~ instead of grub.cfg!  Thus, after
+editing grub.cfg, be sure to delete any grub.cfg~ file!
+
+Finally, boot!
+
+    $ qemu-system-x86_64 -serial stdio -fda ~/grub2/install/boot.img -hda fat:/viengoos -boot a
+
+By default, Hieronymus is configured to load ruth, a test suite.  Ruth
+can take a long time to complete.
diff --git a/microkernel/viengoos/documentation.mdwn b/microkernel/viengoos/documentation.mdwn
new file mode 100644
index 00000000..52ff7a48
--- /dev/null
+++ b/microkernel/viengoos/documentation.mdwn
@@ -0,0 +1,56 @@
+[[!meta copyright="Copyright © 2008 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+The most up-to-date documentation is in the source code itself, see in
+particular the header files in the hurd directory.
+
+There is a started but as-of-yet incomplete manual in the doc
+directory, which documents the Viengoos API and the Hurd API.  A
+version of that is available [[here|reference-guide.pdf]].  It is
+not, however, automatically regenerated, and thus may not be up to
+date.
+
+Academic Papers:
+
+  * [Viengoos: A Framework for Stakeholder-Directed Resource
+    Allocation](http://walfield.org/papers/2009-walfield-viengoos-a-framework-for-stakeholder-directed-resource-allocation.pdf).
+    By Neal H. Walfield.  Submitted to EuroSys 2009.
+
+    General-purpose operating systems not only fail to provide adaptive
+    applications the information they need to intelligently adapt, but
+    also schedule resources in such a way that were applications to
+    aggressively adapt, resources would be inappropriately scheduled.  The
+    problem is that these systems use demand as the primary indicator of
+    utility, which is a poor indicator of utility for adaptive
+    applications.
+
+    We present a resource management framework appropriate for traditional
+    as well as adaptive applications.  The primary difference from current
+    schedulers is the use of stakeholder preferences in addition to
+    demand.  We also show how to revoke memory, compute the amount of
+    memory available to each principal, and account shared
+    memory.  Finally, we introduce a prototype system, Viengoos, and
+    present some benchmarks that demonstrate that it can efficiently
+    support multiple aggressively adaptive applications simultaneously.
+
+  * [Improving Usability via Access Decomposition and Policy
+    Refinement](http://walfield.org/papers/20070104-walfield-access-decomposition-policy-refinement.pdf).
+    By Neal H. Walfield and Marcus Brinkmann.  Technical report
+    (submitted to HotOS 2007).
+
+    Commodity operating systems fail to meet the security, resource
+    management and integration expectations of users.  We propose a unified
+    solution based on a capability framework as it supports fine grained
+    objects, straightforward access propagation and virtualizable
+    interfaces and explore how to improve resource use via access
+    decomposition and policy refinement with minimum interposition.  We
+    argue that only a small static number of scheduling policies are
+    needed in practice and advocate hierarchical policy specification and
+    central realization.
diff --git a/microkernel/viengoos/documentation/reference-guide.pdf b/microkernel/viengoos/documentation/reference-guide.pdf
new file mode 100644
index 00000000..6fbea23b
--- /dev/null
+++ b/microkernel/viengoos/documentation/reference-guide.pdf
diff --git a/microkernel/viengoos/grub2-config.diff b/microkernel/viengoos/grub2-config.diff
new file mode 100644
index 00000000..e4b1ef40
--- /dev/null
+++ b/microkernel/viengoos/grub2-config.diff
@@ -0,0 +1,47 @@
+2009-01-17  Neal H. Walfield  <address@hidden>
+
+        * util/i386/pc/grub-mkrescue.in: Add new option --configfile.  If
+        not the set and not the empty string, load it from the generated
+        config file on boot.
+
+Index: util/i386/pc/grub-mkrescue.in
+===================================================================
+--- util/i386/pc/grub-mkrescue.in	(revision 2148)
++++ util/i386/pc/grub-mkrescue.in	(working copy)
+@@ -49,6 +49,7 @@
+   --image-type=TYPE       select floppy or cdrom (default)
+   --emulation=TYPE        select El Torito boot emulation type floppy
+                           or none (default) (cdrom only)
++  --configfile=FILE       config file to load (default: none)
+ 
+ grub-mkimage generates a bootable rescue image of the specified type.
+ 
+@@ -93,6 +94,9 @@
+             echo "Unknown emulation type \`$emulation'" 1>&2
+             exit 1 ;;
+         esac ;;
++    --configfile=*)
++       configfile=`echo "$option" | sed 's/--configfile=//'`
++        ;;
+     -*)
+ 	echo "Unrecognized option \`$option'" 1>&2
+ 	usage
+@@ -121,9 +125,15 @@
+   ${aux_dir}/boot/grub/
+ 
+ modules="biosdisk `cat ${input_dir}/partmap.lst` ${modules}"
+-for i in ${modules} ; do
+-  echo "insmod $i"
+-done > ${aux_dir}/boot/grub/grub.cfg
++{
++  for i in ${modules} ; do
++    echo "insmod $i"
++  done
++  if test x$configfile != x
++  then
++    echo "configfile $configfile"
++  fi
++} > ${aux_dir}/boot/grub/grub.cfg
+ 
+ for d in ${overlay}; do
+   echo "Overlaying $d"
diff --git a/microkernel/viengoos/hardware.mdwn b/microkernel/viengoos/hardware.mdwn
new file mode 100644
index 00000000..aff70604
--- /dev/null
+++ b/microkernel/viengoos/hardware.mdwn
@@ -0,0 +1,50 @@
+[[!meta copyright="Copyright © 2008 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+I boot over the network using PXE.
+
+On my build machine, I have installed a tftpserver.  Specifically, I use
+the one built into dnscache.  In /tftpboot, I have symlinks to pistachio,
+sigma0, and the root of the build tree.
+
+My build machine boots using PXE.  It gets an IP address, contacts
+my build machine and loads [grub2pxe](http://grub.enbug.org/PXEBOOT).
+Note that there is no need to use pxelinux; grub2 is a valid PXE
+executable.  Further, grub2 uses the PXE interface for accessing the
+network, so if your hardware supports PXE, then you do not need to
+worry about a network driver.  Here is how I build grub2 and the
+grub2 image:
+
+    cd ~/src
+    svn co svn://svn.savannah.gnu.org/grub/trunk/grub2
+    cd grub2
+    mkdir build
+    cd build
+    ../configure --prefix=$HOME/src/grub2/install && make && make install
+    cd ~/src/grub2/install
+    bin/grub-mkimage --output=core.img --prefix="(pxe)" pxe pxecmd help reboot serial multiboot pc configfile normal boot
+    cat lib/grub/i386-pc/pxeboot.img core.img > grub2pxe
+
+Here is my /tftpboot/grub.cfg, which sends output to the first
+[[serial_port]]:
+
+    # Timeout for menu
+    set timeout=1
+    
+    # Set default boot entry as Entry 0
+    set default=0
+    
+    menuentry "Viengoos" {
+        multiboot /viengoos/laden/laden -o serial -D
+        module /pistachio
+        module /sigma0
+        module /viengoos/viengoos/viengoos.stripped -D 3 -o serial
+        module /viengoos/hieronymus/hieronymus.stripped
+    }
diff --git a/microkernel/viengoos/projects.mdwn b/microkernel/viengoos/projects.mdwn
new file mode 100644
index 00000000..971206bb
--- /dev/null
+++ b/microkernel/viengoos/projects.mdwn
@@ -0,0 +1,17 @@
+[[!meta copyright="Copyright © 2008, 2009 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+Some projects:
+
+[[!inline
+pages="microkernel/viengoos/projects/* and !microkernel/viengoos/projects/*/*"
+show=0
+feeds=no
+actions=yes]]
diff --git a/microkernel/viengoos/projects/address_space_management.mdwn b/microkernel/viengoos/projects/address_space_management.mdwn
new file mode 100644
index 00000000..2d00e4f4
--- /dev/null
+++ b/microkernel/viengoos/projects/address_space_management.mdwn
@@ -0,0 +1,40 @@
+[[!meta copyright="Copyright © 2008, 2009 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled [[GNU Free Documentation
+License|/fdl]]."]]"""]]
+
+[[!tag open_issue_viengoos]]
+
+In Viengoos, a process's address space is managed entirely in user
+space by the process itself.  This creates two interesting problems:
+dealing with circular dependencies resulting from having to manage the
+address space data structures and accessing and manipulating the
+address space data structures.
+
+First, managing the address space requires resources, which in turn
+may require address space (e.g., data structures require memory which
+require address space, etc.).  We currently break this circular
+dependency by trying to keep enough resources in reserve that
+allocating resources for managing the address space never requires
+more resources than are minimally in the reserve.  The reserve is
+currently chosen in an ad-hoc fashion.  It would be nice to determine
+it more systematically.  Moreover, it would be nice to reduce the
+cases in which a reserve is required.  This may be possible by
+restructuring some of the code.
+
+Second, the address space data structures are protected using a single
+lock.  This not only means that only a single thread can be updating
+the address space at a time, but that if a thread faults and the
+address space is locked, then the process dead locks!  It should be
+possible to at least walk the address space using lock-free
+techniques.  This requires updating the address space construction
+code such that all addresses remain valid during any given
+manipulation.  Second, to avoid the mentioned dead-lock problem, we
+try to ensure that accessing the data structures will never result in
+a fault.  This means protecting the stack.  An alternative approach is
+to use undo buffers.
diff --git a/microkernel/viengoos/projects/capability-aware_compiler.mdwn b/microkernel/viengoos/projects/capability-aware_compiler.mdwn
new file mode 100644
index 00000000..b4e465d9
--- /dev/null
+++ b/microkernel/viengoos/projects/capability-aware_compiler.mdwn
@@ -0,0 +1,16 @@
+[[!meta copyright="Copyright © 2008, 2009 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+[[!tag open_issue_viengoos]]
+
+Modify, e.g., gcc to understand capability semantics and teach gcc how
+to optimize it, e.g., how to batch and combine calls.
+
+This project is deemed suitable for a thesis.
diff --git a/microkernel/viengoos/projects/new_hash_function.mdwn b/microkernel/viengoos/projects/new_hash_function.mdwn
new file mode 100644
index 00000000..d0374720
--- /dev/null
+++ b/microkernel/viengoos/projects/new_hash_function.mdwn
@@ -0,0 +1,22 @@
+[[!meta copyright="Copyright © 2008, 2009, 2010 Free Software Foundation,
+Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled [[GNU Free Documentation
+License|/fdl]]."]]"""]]
+
+[[!tag open_issue_viengoos]]
+
+The current hash function in libhurd-ihash results in a lot of
+collisions when the hash table is 80% full.  To overcome this, we keep
+hash tables at most 30% full.  This represents a fair amount of
+overhead.  Find a better algorithm.  There can either be one that is
+appropriate in the general case or one that works well in a relevant,
+specific case, e.g., viengoos/object.c uses a hash to find the object
+corresponding to a frame, which is keyed on its physical address.
+
+Note that this applies to the Hurd's [[hurd/libihash]], too.
diff --git a/microkernel/viengoos/serial_port.mdwn b/microkernel/viengoos/serial_port.mdwn
new file mode 100644
index 00000000..14efcb9f
--- /dev/null
+++ b/microkernel/viengoos/serial_port.mdwn
@@ -0,0 +1,15 @@
+[[!meta copyright="Copyright © 2008 Free Software Foundation, Inc."]]
+
+[[!meta license="""[[!toggle id="license" text="GFDL 1.2+"]][[!toggleable
+id="license" text="Permission is granted to copy, distribute and/or modify this
+document under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with no Invariant
+Sections, no Front-Cover Texts, and no Back-Cover Texts.  A copy of the license
+is included in the section entitled
+[[GNU Free Documentation License|/fdl]]."]]"""]]
+
+Viengoos can be configured to send output to the serial port (in fact,
+this is the only configuration that I use).  To talk to the serial
+port, I use ser2net, which provides a telnet interface to the serial
+port.  Be sure to edit /etc/ser2net.conf to use 115200 bps, which
+Viengoos uses by default.