Merge origin/netpush (networking code) (XCC)
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 22 Mar 2013 00:04:19 +0000 (17:04 -0700)
committerBarret Rhoden <brho@cs.berkeley.edu>
Fri, 22 Mar 2013 04:12:23 +0000 (21:12 -0700)
Had some compilation issues (missing mbuf.h, etc), but compiles now.

Other than basic conflicts, this also was using the old semaphore style,
as well as having a few other issues in semaphore usage, so please check
that out.

Rebuild your cross compiler.  There are a bunch of new files in the -ros
folder, so either copy them over, or just make clean.  Here are the new
glibc files:

glibc-2.14.1-ros/sysdeps/ros/accept.c
glibc-2.14.1-ros/sysdeps/ros/bind.c
glibc-2.14.1-ros/sysdeps/ros/connect.c
glibc-2.14.1-ros/sysdeps/ros/listen.c
glibc-2.14.1-ros/sysdeps/ros/recv.c
glibc-2.14.1-ros/sysdeps/ros/recvfrom.c
glibc-2.14.1-ros/sysdeps/ros/select.c
glibc-2.14.1-ros/sysdeps/ros/send.c
glibc-2.14.1-ros/sysdeps/ros/sendto.c
glibc-2.14.1-ros/sysdeps/ros/socket.c

Conflicts:
Makeconfig
kern/include/kthread.h
kern/include/time.h
kern/include/vfs.h
kern/src/Makefrag
kern/src/kthread.c
kern/src/syscall.c

264 files changed:
Documentation/async_events.txt
Documentation/glibc.txt
Documentation/howtos/make-bootable-grub-hdd.txt [new file with mode: 0644]
Documentation/kernel_messages.txt
Documentation/kref.txt
Documentation/memory_barriers.txt
Documentation/process-internals.txt
GETTING_STARTED [new file with mode: 0644]
GNUmakefile
Makeconfig
Makelocal.template
kern/arch/i686/Makefrag
kern/arch/i686/apic.c
kern/arch/i686/apic.h
kern/arch/i686/arch.h
kern/arch/i686/atomic.h
kern/arch/i686/console.c
kern/arch/i686/console.h
kern/arch/i686/cpuinfo.c
kern/arch/i686/init.c
kern/arch/i686/init.h
kern/arch/i686/nic_common.c
kern/arch/i686/page_alloc.c
kern/arch/i686/rdtsc_test.c [new file with mode: 0644]
kern/arch/i686/smp.c
kern/arch/i686/smp_boot.c
kern/arch/i686/trap.c
kern/arch/i686/x86.h
kern/arch/riscv/Makefrag
kern/arch/riscv/arch.h
kern/arch/riscv/atomic.c
kern/arch/riscv/atomic.h
kern/arch/riscv/boot.S
kern/arch/riscv/console.c
kern/arch/riscv/console.h
kern/arch/riscv/cpuinfo.c
kern/arch/riscv/entry.S
kern/arch/riscv/env.c
kern/arch/riscv/fpu.c [new file with mode: 0644]
kern/arch/riscv/init.c
kern/arch/riscv/opcodes.h [new file with mode: 0644]
kern/arch/riscv/page_alloc.c
kern/arch/riscv/pcr.h
kern/arch/riscv/process.c
kern/arch/riscv/riscv.h
kern/arch/riscv/ros/arch.h
kern/arch/riscv/ros/trapframe.h
kern/arch/riscv/smp.c
kern/arch/riscv/softfloat-macros.h [new file with mode: 0644]
kern/arch/riscv/softfloat-specialize.h [new file with mode: 0644]
kern/arch/riscv/softfloat.c [new file with mode: 0644]
kern/arch/riscv/softfloat.h [new file with mode: 0644]
kern/arch/riscv/time.c
kern/arch/riscv/time.h
kern/arch/riscv/trap.c
kern/arch/riscv/trap.h
kern/arch/sparc/arch.h
kern/arch/sparc/atomic.h
kern/arch/sparc/console.c
kern/arch/sparc/page_alloc.c
kern/arch/sparc/sparc.h
kern/arch/sparc/time.h
kern/arch/sparc/trap.c
kern/arch/sparc/trap.h
kern/include/alarm.h
kern/include/atomic.h
kern/include/bitmask.h
kern/include/devfs.h
kern/include/env.h
kern/include/event.h
kern/include/kfs.h
kern/include/kthread.h
kern/include/process.h
kern/include/ros/bits/posix_signum.h [new file with mode: 0644]
kern/include/ros/bits/syscall.h
kern/include/ros/common.h
kern/include/ros/errno.h
kern/include/ros/event.h
kern/include/ros/procinfo.h
kern/include/ros/ring_buffer.h
kern/include/ros/time.h [deleted file]
kern/include/ros/ucq.h
kern/include/schedule.h
kern/include/smp.h
kern/include/stdint.h
kern/include/string.h
kern/include/sys/types.h
kern/include/termios.h [new file with mode: 0644]
kern/include/time.h
kern/include/trap.h
kern/include/vfs.h
kern/src/Makefrag
kern/src/alarm.c
kern/src/arsc.c
kern/src/atomic.c
kern/src/blockdev.c
kern/src/colored_caches.c
kern/src/console.c
kern/src/devfs.c
kern/src/elf.c
kern/src/eth_audio.c
kern/src/event.c
kern/src/ext2fs.c
kern/src/init.c
kern/src/kfs.c
kern/src/kthread.c
kern/src/manager.c
kern/src/mm.c
kern/src/monitor.c
kern/src/net/tcp.c
kern/src/net/udp.c
kern/src/page_alloc.c
kern/src/printf.c
kern/src/process.c
kern/src/readline.c
kern/src/schedule.c
kern/src/slab.c
kern/src/smp.c
kern/src/socket.c
kern/src/string.c
kern/src/syscall.c
kern/src/testing.c
kern/src/time.c
kern/src/trap.c [new file with mode: 0644]
kern/src/ucq.c
kern/src/umem.c
kern/src/vfs.c
scripts/fill-kfs.sh [new file with mode: 0755]
scripts/kvm-up.sh [new file with mode: 0755]
scripts/make_errlist.sh [new file with mode: 0755]
scripts/pxeboot/akaros-pxecfg.bak [new file with mode: 0644]
scripts/pxeboot/mboot.c32 [new file with mode: 0755]
scripts/pxeboot/message.txt [new file with mode: 0644]
scripts/pxeboot/notes [new file with mode: 0644]
tests/Makefrag
tests/block_test.c
tests/c3po/Makefrag
tests/cpp_streams.cc [new file with mode: 0644]
tests/dtls_test.c [new file with mode: 0644]
tests/eth_audio.c
tests/file_test.c
tests/hello.c
tests/mhello.c
tests/microb_test.c [new file with mode: 0644]
tests/msr_get_cores.c
tests/msr_get_singlecore.c
tests/openmp/Makefrag [new file with mode: 0644]
tests/openmp/omp_hello.c [new file with mode: 0644]
tests/prov.c [new file with mode: 0644]
tests/pthread_test.c
tests/raise.c [new file with mode: 0644]
tests/slab.c [new file with mode: 0644]
tests/spawn.c
tests/ucq.c
tools/compilers/gcc-glibc/Makefile
tools/compilers/gcc-glibc/Makelocal.template
tools/compilers/gcc-glibc/binutils-2.21.1-riscv.patch
tools/compilers/gcc-glibc/gcc-4.6.1-compile.patch [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-riscv.patch
tools/compilers/gcc-glibc/gcc-4.6.1-ros.patch [deleted file]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/config.sub [new file with mode: 0755]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/gcc/config.gcc [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/gcc/config/i386/ros.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/gcc/config/ros.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgcc/config.host [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/Makefile.am [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/Makefile.in [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/aclocal.m4 [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/configure [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/configure.ac [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/go/debug/proc/proc_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/go/net/fd_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/go/os/sys_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/runtime/chan.goc [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/runtime/go-reflect-call.c [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/runtime/runtime.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/syscalls/errstr_decl_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/syscalls/exec_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/syscalls/sleep_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/syscalls/socket_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/syscalls/syscall_akaros.go [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgo/testsuite/Makefile.in [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgomp/config/ros/bar.c [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgomp/config/ros/bar.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgomp/config/ros/libgomp_futex.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgomp/config/ros/wait.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libgomp/configure.tgt [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/config/os/ros/ctype_base.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/config/os/ros/ctype_inline.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/config/os/ros/ctype_noninline.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/config/os/ros/os_defines.h [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/configure [new file with mode: 0755]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/configure.host [new file with mode: 0644]
tools/compilers/gcc-glibc/gcc-4.6.1-ros/libstdc++-v3/crossconfig.m4 [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.11.1-ros/sysdeps/ros/recvfrom.c [deleted file]
tools/compilers/gcc-glibc/glibc-2.11.1-ros/sysdeps/ros/sendto.c [deleted file]
tools/compilers/gcc-glibc/glibc-2.11.1-ros/sysdeps/ros/socket.c [deleted file]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/Makefile
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/Versions
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/_G_config.h [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/bits/sigaction.h [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/errlist.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/fork.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/getsysstats.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/i386/tls.h
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/init-first.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/kill.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/lseek.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/lseek64.c [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/riscv/tls.h
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/start.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/sys/syscall.h
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/sys/vcore-tls.h [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/syscall.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/sysconf.c
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/vcore-tls.c [new file with mode: 0644]
tools/compilers/gcc-glibc/glibc-2.14.1-ros/sysdeps/ros/waitpid.c
tools/patches/busybox-1.17.3-config [new file with mode: 0644]
tools/patches/busybox-1.17.3-parlib.patch [deleted file]
user/c3po/aio/diskio_aio.c
user/c3po/threads/ucontext.c
user/c3po/threads/vcore.c
user/parlib/Makefile
user/parlib/bthread.c [deleted file]
user/parlib/debug.c
user/parlib/dtls.c [new file with mode: 0644]
user/parlib/event.c
user/parlib/include/bitmask.h
user/parlib/include/bthread.h [deleted file]
user/parlib/include/dtls.h [new file with mode: 0644]
user/parlib/include/event.h
user/parlib/include/glibc-tls.h [deleted file]
user/parlib/include/i686/arch.h
user/parlib/include/i686/vcore.h
user/parlib/include/mcs.h
user/parlib/include/parlib.h
user/parlib/include/rassert.h
user/parlib/include/riscv/arch.h
user/parlib/include/riscv/atomic.h
user/parlib/include/riscv/vcore.h
user/parlib/include/ros_debug.h
user/parlib/include/slab.h [new file with mode: 0644]
user/parlib/include/sparc/arch.h
user/parlib/include/sparc/vcore.h
user/parlib/include/spinlock.h [new file with mode: 0644]
user/parlib/include/timing.h
user/parlib/include/uthread.h
user/parlib/include/vcore.h
user/parlib/mcs.c
user/parlib/riscv/atomic.c [new file with mode: 0644]
user/parlib/riscv/vcore.S
user/parlib/signal.c [new file with mode: 0644]
user/parlib/slab.c [new file with mode: 0644]
user/parlib/spinlock.c [new file with mode: 0644]
user/parlib/syscall.c
user/parlib/ucq.c
user/parlib/uthread.c
user/parlib/vcore.c
user/pthread/futex.c [new file with mode: 0644]
user/pthread/futex.h [new file with mode: 0644]
user/pthread/pthread.c
user/pthread/pthread.h
user/pthread/semaphore.c [new file with mode: 0644]
user/pthread/semaphore.h [new file with mode: 0644]

index e7fde52..9d3fee4 100644 (file)
@@ -416,7 +416,7 @@ not work if the vcore yielded and then the entire process was preempted or
 otherwise not running.  Another way to put this is that we need a field to
 determine whether a vcore is offline temporarily or permanently.
 
-This is why we have the VCPD field 'can_rcv_msg'.  It tells the kernel's event
+This is why we have the VCPD flag 'VC_CAN_RCV_MSG'.  It tells the kernel's event
 delivery code that the vcore will check the messages: it is an acceptable
 destination for a FALLBACK.  There are two reasons to put this in VCPD:
 1) Userspace can remotely turn off a vcore's msg reception.  This is necessary
@@ -428,7 +428,7 @@ about turning off that flag - userspace can do it when it wants to yield.  (turn
 off the flag, check messages, then yield).  This is less big of a deal now that
 the kernel races with vcore membership in the online_vcs list.
 
-Two aspects of the code make this work nicely.  The 'can_rcv_msg' flag greatly
+Two aspects of the code make this work nicely.  The VC_CAN_RCV_MSG flag greatly
 simplifies the kernel's job.  There are a lot of weird races we'd have to deal
 with, such as process state (RUNNING_M), whether a mass preempt is going on, or
 just one core, or a bunch of cores, mass yields, etc.  A flag that does one
@@ -437,11 +437,11 @@ other useful thing is being able to handle spurious events.  Vcore code can
 handle extra IPIs and INDIRs to non-VCPD ev_qs.  Any vcore can handle an ev_q
 that is "non-VCPD business".
 
-Worth mentioning is the difference between 'notif_pending' and 'can_rcv_msg'.
-'can_rcv_msg' is the process saying it will check for messages.  'notif_pending'
-is when the kernel says it *has* sent a message.  'notif_pending' is also used
-by the kernel in proc_yield() and the 2LS in pop_ros_tf() to make sure the sent
-message is not missed.
+Worth mentioning is the difference between 'notif_pending' and VC_CAN_RCV_MSG.
+VC_CAN_RCV_MSG is the process saying it will check for messages.
+'notif_pending' is when the kernel says it *has* sent a message.
+'notif_pending' is also used by the kernel in proc_yield() and the 2LS in
+pop_ros_tf() to make sure the sent message is not missed.
 
 Also, in case this comes up, there's a slight race on changing the mbox* and the
 vcore number within the event_q.  The message could have gone to the wrong (old)
@@ -496,7 +496,7 @@ are good for process management, but also for helping alert_vcore() find
 potentially alertable vcores.  alert_vcore() and its associated helpers are
 failry complicated and heavily commented.  I've set things up so both the
 online_vcs and the bulk_preempted_vcs lists can be handled the same way: post to
-the first element, then see if it still 'can_rcv_msg'.  If not, if it is still
+the first element, then see if it still VC_CAN_RCV_MSG.  If not, if it is still
 the first on the list, then it hasn't proc_yield()ed yet, and it will eventually
 restart when it tries to yield.  And this all works without locking the
 proc_lock.  There are a bunch more details and races avoided.  Check the code
@@ -690,6 +690,139 @@ migrate a notif_safe locking uthread.  The whole point of it is in case it grabs
 a lock that would be held by vcore context, and there's no way to know it isn't
 a lock on the restart-path.
 
+3.9 Why Preemption Handling Doesn't Lock Up (probably)
+---------------------------------------
+One of the concerns of preemption handling is that we don't get into some form
+of livelock, where we ping-pong back and forth between vcores (or a set of
+vcores), all of which are trying to handle each other's preemptions.  Part of
+the concern is that when a vcore sys_changes to another, it can result in
+another preemption message being sent.  We want to be sure that we're making
+progress, and not just livelocked doing sys_change_vcore()s.
+
+A few notes first:
+1) If a vcore is holding locks or otherwise isn't handling events and is
+preempted, it will let go of its locks before it gets to the point of
+attempting to handle any other vcore preemption events.  Event handling is only
+done when it is okay to never return (meaning no locks are held).  If this is
+the situation, eventually it'll work itself out or get to a potential ping-pong
+scenario.
+
+2) When you change_to while handling preemption, once you start back up, you
+will leave change_to and eventually fetch a new event.  This means any
+potential ping-pong needs to happen on a fresh event.
+
+3) If there are enough pcores for the vcores to all run, we won't issue any
+change_tos, since the vcores are no longer preempted.  This means we only are
+worried about situations with insufficient vcores.  We'll mostly talk about 1
+pcore and 2 vcores.
+
+4) Preemption handlers will not call change_to on their target vcore if they
+are also the one STEALING from that vcore.  The handler will stop STEALING
+first.
+
+So the only way to get stuck permanently is if both cores are stuck doing a
+sys_change_to(FALSE).  This means we want to become the other vcore, *and* we
+need to restart our vcore where it left off.  This is due to some invariant
+that keeps us from abandoning vcore context.  If we were to abandon vcore
+context (with a sys_change_to(TRUE)), we basically don't need to be
+preempt-recovered.  We already packaged up our cur_uthread, and we know we
+aren't holding any locks or otherwise breaking any invariants.  The system will
+work fine if we never run again.  (Someone just needs to check our messages).
+
+Now, there are only two cases where we will do a sys_change_to(FALSE) *while*
+handling preemptions.  Again, we aren't concerned about things like MCS-PDR
+locks; those all work because the change_tos are done where we'd normally just
+busy loop.  We are only concerned about change_tos during handle_vc_preempt.
+These two cases are when the changing/handling vcore has a DONT_MIGRATE uthread
+or when someone else is STEALING its uthread.  Note that both of these cases
+are about the calling vcore, not its target.
+
+If a vcore (referred to as "us") has a DONT_MIGRATE uthread and it is handling
+events, it is because someone else is STEALING from our vcore, and we are in
+the short one-shot event handling loop at the beginning of
+uthread_vcore_entry().  Whichever vcore is STEALING will quickly realize it
+can't steal (it sees the DONT_MIGRATE), and bail out.  If that vcore isn't
+running now, we will change_to it (which is the purpose of our handling their
+preemption).  Once that vcore realizes it can't steal, it will stop STEALING
+and change to us.  At this point, no one is STEALING from us, and we move along
+in the code.  Specifically, we do *not* handle events (we now have an event
+about the other vcore being preempted when it changed_to us), and instead we
+start up the DONT_MIGRATE uthread and let it run until it is migratable, at
+which point we handle events and will deal with the other vcore.  
+
+So DONT_MIGRATE will be sorted out.  Likewise, STEALING gets sorted out too,
+quite easily.  If someone is STEALING from us, they will quickly stop STEALING
+and change to us.  There are only two ways this could even happen: they are
+running concurrently with us, and somehow saw us out of vcore context before
+deciding to STEAL, or they were in the process of STEALING and got preempted by
+the kernel.  They would not have willingly stopped running while STEALING our
+cur_uthread.  So if we are running and someone is stealing, after a round of
+change_tos, eventually they run, and stop STEALING.
+
+Note that once someone stops STEALING from us, they will not start again,
+unless we leave vcore context.  If that happened, we basically broke out of the
+ping-pong, and now we're onto another set of preemptions.  We wouldn't leave
+vcore context if we still had preemption events to deal with.
+
+Finally, note that we needed to only check for one message at a time at the
+beginning of uthread_vcore_entry().  If we just handled the entire mbox without
+checking STEALING, then we might not break out of that loop if there is a
+constant supply of messages (perhaps from a vcore in a similar loop).
+
+Anyway, that's the basic plan behind the preemption handler and how we avoid
+the ping-ponging.  change_to_vcore() is built so that we handle our own
+preemption before changing (pack up our current uthread), so that we make
+progress.  The two cases where we can't do that get sorted out after everyone
+gets to run once, and since you can't steal or have other uthread's turn on
+DONT_MIGRATE while we're in vcore context, eventually we clear everything up.
+There might be other bugs or weird corner cases, possibly involving multiple
+vcores, but I think we're okay for now.
+
+3.10: Handling Messages for Other Vcores
+---------------------------------------
+First, remember that when a vcore handles an event, there's no guarantee that
+the vcore will return from the handler.  It may start fresh in vcore_entry().
+
+The issue is that when you handle another vcore's INDIRs, you may handle
+preemption messages.  If you have to do a change_to, the kernel will make sure
+a message goes out about your demise.  Thus someone who recovers that will
+check your public mbox.  However, the recoverer won't know that you were
+working on another vcore's mbox, so those messages might never be checked.
+
+The way around it is to send yourself a "check the other guy's messages" event.
+When we might change_to and never return, if we were dealing with another
+vcores mbox, we'll send ourselves a message to finish up that mbox (if there
+are any messages left).  Whoever reads our messages will eventually get that
+message, and deal with it.
+
+One thing that is a little ugly is that the way you deal with messages two
+layers deep is to send yourself the message.  So if VC1 is handling VC2's
+messages, and then wants to change_to VC3, VC1 sends a message to VC1 to check
+VC2.  Later, when VC3 is checking VC1's messages, it'll handle the "check VC2's messages"
+message.  VC3 can't directly handle VC2's messages, since it could run a
+handler that doesn't return.  Nor can we just forget about VC2.  So VC3 sends
+itself a message to check VC2 later.  Alternatively, VC3 could send itself a
+message to continue checking VC1, and then move on to VC2.  Both seem
+equivalent.  In either case, we ought to check to make sure the mbox has
+something before bothering sending the message.
+
+So for either a "change_to that might not return" or for a "check INDIRs on yet
+another vcore", we send messages to ourself so that we or someone else will
+deal with it.
+
+Note that we use TLS to track whether or not we are handling another vcore's
+messages, and if we do plan to change_to that might not return, we clear the
+bool so that when our vcore starts over at vcore_entry(), it starts over and
+isn't still checking someone elses message.
+
+As a reminder of why this is important: these messages we are hunting down
+include INDIRs, specifically ones to ev_qs such as the "syscall completed
+ev_q".  If we never get that message, a uthread will block forever.  If we
+accidentally yield a vcore instead of checking that message, we would end up
+yielding the process forever since that uthread will eventually be the last
+one, but our main thread is probably blocked on a join call.  Our process is
+blocked on a message that already came, but we just missed it. 
+
 4. Single-core Process (SCP) Events:
 ====================
 4.1 Basics:
index ea5d901..963cb34 100644 (file)
@@ -184,6 +184,14 @@ Tips, Questions, and Misc Notes
   shared vs static, and it can get complicated with start.c, tls.c, etc.
 - What things in one file rely heavily on another file?  Are there non-obvious
   gotchas?  (yes, and no one documented them).
+- Is the build failing without any clear error messages?  Scroll up a lot, and
+  there may be messages farther up (like a hundred+ lines up).  I've had some
+  gcc stage2 builds that fail with no obvious issue in the short term console
+  output, but the real error is much higher.  Some aspect of the build system
+  will continue on failures and only fail much later, after building other
+  packages.
+- Note that libstdc++ is a subpart of gcc, built during stage2, and has its
+  own configure script and settings.
 
 Ghetto Things (Feel free to fix them):
 --------------------------
diff --git a/Documentation/howtos/make-bootable-grub-hdd.txt b/Documentation/howtos/make-bootable-grub-hdd.txt
new file mode 100644 (file)
index 0000000..7f8e5a2
--- /dev/null
@@ -0,0 +1,196 @@
+make-bootable-grub-hdd.txt
+Barret Rhoden
+2013-02-22
+
+This document explains how to make a hard disk image file, install grub on the
+image, and load your kernel (Akaros in the examples).
+
+
+Initial Setup:
+--------------------------
+Commands that begin with # need root access.  Commands beginning with $ should
+be done as your development user.
+
+You need the loop module loaded with max_part=10 (or something more than the
+number of partions you are making on an image file).
+
+# modprobe loop max_part=10
+
+If your loop device is compiled into the kernel, add the kernel parameter "loop.max_part=10"
+
+For example, once you partition an image file and connect it to a loopback
+device (e.g., loop1), you will see the following devices:
+
+/dev/loop1
+/dev/loop1p1
+/dev/loop1p2
+..etc
+
+
+Build your Image File:
+--------------------------
+This makes an image of size 268MB, which is 256MiB):
+
+$ dd if=/dev/zero of=mnt/hdd.img bs=512 count=1 seek=524287
+
+Connect to the image via a loopback device:
+
+# losetup /dev/loop0 mnt/hdd.img 
+
+Fdisk the device:
+
+# fdisk /dev/loop0
+       Create a new linux partition
+       Note it has 524288 sectors (1 + the seek offset)
+       Also note the partition begins at 2048, not 512 like it used to (changes
+       to fdisk, probably to get away from 512 byte alignments)
+
+Disconnect and reconnect the loopback device, so we now can see the
+partitions:
+
+# losetup -d /dev/loop0
+# losetup /dev/loop0 mnt/hdd.img 
+# ls /dev/loop0*
+/dev/loop0  /dev/loop0p1
+
+Make the filesystem:
+
+# mkfs /dev/loop0p1
+
+Create a mount point for your image file (as your user);
+
+$ mkdir mnt/hdd/
+
+Mount and chown.  The chown only needs to be done the first time you mount the
+device.
+
+# mount /dev/loop0p1 mnt/hdd/
+# chown -R brho:brho mnt/hdd/
+
+
+Install Grub on the Image file:
+--------------------------
+
+This assumes legacy grub:  for gentoo, emerge sys-boot/grub-static to get the
+legacy grub.  I glanced at grub2, but don't particularly want to mess with
+that.
+
+Set up the grub1 files and directories (assuming you still have the image
+mounted and have access to stage1 and stage2 files).
+
+$ mkdir -p mnt/hdd/boot/grub
+$ cp /boot/grub/stage1 /boot/grub/stage2 /boot/grub/menu.lst mnt/hdd/boot/grub/
+
+Edit menu.lst.  Here's one similar to mine that works with Akaros:
+       default 0
+       timeout 5
+       serial --unit=0 --speed=115200 --word=8 --parity=no --stop=1
+       terminal --timeout=5 serial console
+       
+       title=Akaros
+       root (hd0,0)
+       kernel /kernel
+
+Now put the kernel on the mounted image.  You can do this whenever, btw, and
+you'll do this whenever you want to update the kernel (my Makelocal has a
+target that does this).  So feel free to do this later.
+
+$ cp obj/kern/kernel mnt/hdd/kernel
+
+Actually install grub on the device.  Do this as a regular user (not root), to
+limit damage in case you mess up (e.g., accidentally write to /dev/sda instead
+of your image file)
+
+$ /sbin/grub --device-map=/dev/null
+
+       Enter the commands at the grub> prompt.  I've included the output you
+       should see if things are going well:
+       
+       grub> device (hd0) mnt/hdd.img
+       device (hd0) mnt/hdd.img
+
+       grub> root (hd0,0)
+       root (hd0,0)
+        Filesystem type is ext2fs, partition type 0x83
+
+       grub> setup (hd0)
+       setup (hd0)
+        Checking if "/boot/grub/stage1" exists... yes
+        Checking if "/boot/grub/stage2" exists... yes
+        Checking if "/boot/grub/e2fs_stage1_5" exists... no
+        Running "install /boot/grub/stage1 (hd0) /boot/grub/stage2 p /boot/grub/menu.lst "... succeeded
+       Done.
+
+       grub> quit
+       quit
+
+
+That's it.  Whenever you reboot, you'll need to recreate the loopback device
+and remount the image at mnt/hdd/.  Check out my "kvm-up.sh" script for how I
+do this (it's basically just losetup, sleep, and mount).
+
+Whenever you update the kernel, cp it into mnt/hdd/kernel, and sync.  The sync
+is necessary so the image file / backing store gets updated right away.  If
+you don't do this, your VM might see the old version of kernel if you run the
+VM right away (before the FS naturally syncs).  Check out my Makelocal target
+for kvm for how to do this.
+
+
+Old Stuff:
+--------------------------
+I originally wrote this back in 2009.  It works for older versions of fdisk
+and has some acrobatics with loopback devices that will help if you can't use
+the max_part parameter to the loop module.  Also, it has some examples with
+using bochs
+
+
+# make a 8MB image.  picked these values so there is 1 cyl (minimum, it seems)
+dd if=/dev/zero of=mnt/hdd.img bs=512 count=16065
+losetup /dev/loop1 mnt/hdd.img 
+fdisk /dev/loop1
+# determine the offset, in sectors
+fdisk -ul /dev/loop1
+# mult the sector offset by 512, since losetup offsets by bytes
+# this will have us point loop2 to the partition on the disk
+losetup -o 32256 /dev/loop2 /dev/loop1
+mkfs /dev/loop2
+mount /dev/loop2 mnt/hdd/
+# copy over grub info
+mkdir -p mnt/hdd/boot/grub
+cp -r /boot/grub/stage1 /boot/grub/stage2 /boot/grub/menu.lst mnt/hdd/boot/grub
+cp -r the_kernel mnt/hdd/
+# edit accordingly
+vi mnt/hdd/boot/grub/menu.lst 
+grub --device-map=/dev/null 
+       # in here:
+       # important to not use the /dev/loop1, since there is a bug in grub
+       # use the image instead, since it bypasses whatever checks fail later
+       device (hd0) mnt/hdd.img
+       root (hd0,0)
+       setup (hd0) # make sure you don't do (hd0,0).  it'll still work, but not the way you want
+kvm mnt/hdd.img
+# or
+bochs -q 'ata0-master: type=disk, mode=flat, path="./mnt/hdd.img", cylinders=1, heads=255, spt=63'
+# to use a floppy image (made similarly)
+bochs -q 'floppya: 1_44=mnt/floppy.img, status=inserted' 'boot:a'
+
+# to easily edit, keep the hdd image mounted and just copy in your kernel or
+# whatever
+# list the loops, delete them with -d to keep things nice and clean
+losetup -a 
+losetup -o 32256 /dev/loop0 mnt/hdd.img 
+mount /dev/loop0 mnt/hdd
+chown -R brho:brho mnt/hdd
+
+# you'll need to make sure changes to the mnt/hdd take effect immediately
+# if you want to run a VM right away with the .img
+sync
+
+
+Notes:
+--------------------------
+http://www.linuxjournal.com/article/4622
+http://sig9.com/bochs-grub
+http://web2.clarkson.edu/projects/itl/honeypot/ddtutorial.txt
+http://www.mail-archive.com/bug-grub@gnu.org/msg09648.html
+http://www.omninerd.com/articles/Installing_GRUB_on_a_Hard_Disk_Image_File
index 692993d..df96c54 100644 (file)
 kernel_messages.txt
 Barret Rhoden
 2010-03-19
+Updated 2012-11-14
 
-This document explains the basic ideas behind our "kernel messages" and some of
-the arcane bits behind the implementation.  These were formerly called active
-messages, since they were an implementation of the low-level hardware messaging.
+This document explains the basic ideas behind our "kernel messages" (KMSGs) and
+some of the arcane bits behind the implementation.  These were formerly called
+active messages, since they were an implementation of the low-level hardware
+messaging.
 
 Overview:
 --------------------------------
-Our kernel messages are just work that is shipped remotely, delayed, or both.
-They currently consist of a PC and a few arguments.  Initially, they were meant
-to be a way to immediately execute code on another core (once interrupts are
-enabled), in the order in which the messages were sent.  This is insufficient
-(and wasn't what we wanted for the task, incidentally).  We simply want to do
-work on another core, but not necessarily instantly.  And not necessarily on
-another core.
+Our kernel messages are just work that is shipped remotely, delayed in time, or
+both.  They currently consist of a function pointer and a few arguments.  Kernel
+messages of a given type will be executed in order, with guaranteed delivery.
 
-Currently, there are two types, distinguished by which list they are sent to per
-core: immediate and routine.  Urgent messages will get executed as soon as
-possible (once interrupts are enabled).  Routine messages will be executed at
-convenient points in the kernel.  This includes when the kernel is about to pop
-back to userspace, or smp_idle()ing.  Routine messages are necessary when their
-function does not return, such as a __startcore, __death, or anything else that
-can ruin whatever the kernel was doing.  They should also be used if the work is
-not worth fully interrupting the kernel.  (An IPI will still be sent, but the
-work will be delayed)
-
-Kernel messages of a given type will be executed in order.  If immediate
-messages show up while processing a routine message, the immediate message will
-get processed next, at the latest.  Even if the routine function doesn't return,
-once interrupts are reenabled (like when popping to userspace), the
-__kernel_message() handler will fire again.
-
-Immediate kernel messages are executed in interrupt context.  Routine messages
-may technically be done in interrupt context (it's a nebulous term) because they
-are executed because of an interrupt handler, but from the kernel's perspective
-they are like executing in regular context (like when a process makes a syscall,
-aka real "process context").  This is because there are no concerns about the
-kernel holding locks or otherwise "interrupting" its own execution.  Routine
-messages are a little different than just trapping into the kernel, since the
-functions don't have to return and may result in clobbering the kernel stack.
-Also note that this behavior is dependent on where we call
-process_routine_kmsg().  Don't call it somewhere you need to return to.
+Initially, they were meant to be a way to immediately execute code on another
+core (once interrupts are enabled), in the order in which the messages were
+sent.  This is insufficient (and wasn't what we wanted for the task,
+incidentally).  We simply want to do work on another core, but not necessarily
+instantly.  And not necessarily on another core.
 
-History:
---------------------------------
-A bit of history: we used to use "immediate" messages (when all messages were
-immediate) for __death calls.  The idea was that we didn't care what the core
-was doing, since we didn't need to save state or anything.  I could see that
-there were going to be issues with preemption, since we would want to do some
-saving of what the core was doing (and what the kernel was doing on its behalf),
-so we prepared to deal with that.  However, even __death could break certain
-codes that were holding a reference (and hence a refcnt) for a process, which
-would prevent the process from ever being cleaned up.  It was a specific case of
-a job that the kernel needed to finish before executing the message.
+Currently, there are two types, distinguished by which list they are sent to per
+core: immediate and routine.   Routine messages are often referred to as RKMs.
+Immediate messages will get executed as soon as possible (once interrupts are
+enabled).  Routine messages will be executed at convenient points in the kernel.
+This includes when the kernel is about to pop back to userspace
+(proc_restartcore()), or smp_idle()ing.  Routine messages are necessary when
+their function does not return, such as a __launch_kthread.  They should also be
+used if the work is not worth fully interrupting the kernel.  (An IPI will still
+be sent, but the work will be delayed).  Finally, they should be used if their
+work could affect currently executing kernel code (like a syscall).
+
+For example, some older KMSGs such as __startcore used to not return and would
+pop directly into user space.  This complicted the KMSG code quite a bit.  While
+these functions now return, they still can't be immediate messages.  Proc
+management KMSGs change the cur_tf out from under a syscall, which can lead to a
+bunch of issues.
+
+Immediate kernel messages are executed in interrupt context, with interrupts
+disabled.  Routine messages are only executed from places in the code where the
+kernel doesn't care if the functions don't return or otherwise cause trouble.
+This means RKMs aren't run in interrupt context in the kernel (or if the kernel
+code itself traps).  We don't have a 'process context' like Linux does, instead
+its more of a 'default context'.  That's where RKMs run, and they run with IRQs
+disabled.
+
+RKMs can enable IRQs, or otherwise cause IRQs to be enabled.  __launch_kthread
+is a good example: it runs a kthread, which may have had IRQs enabled.
+
+With RKMs, there are no concerns about the kernel holding locks or otherwise
+"interrupting" its own execution.  Routine messages are a little different than
+just trapping into the kernel, since the functions don't have to return and may
+result in clobbering the kernel stack.  Also note that this behavior is
+dependent on where we call process_routine_kmsg().  Don't call it somewhere you
+need to return to.
 
 An example of an immediate message would be a TLB_shootdown.  Check current,
 flush if applicable, and return.  It doesn't harm the kernel at all.  Another
 example would be certain debug routines.
 
-Kernel messages are currently an arch-dependent thing, but this ought to change
-when sparc has IPI functions similar to x86.
+History:
+--------------------------------
+KMSGs have a long history tied to process management code.  The main issues were
+related to which KMSG functions return and which ones mess with local state (like
+clobbering cur_tf or the owning_proc).  Returning was a big deal because you
+can't just arbitrarily abandon a kernel context (locks or refcnts could be held,
+etc).  This is why immediates must return.  Likewise, there are certain
+invariants about what a core is doing that shouldn't be changed by an IRQ
+handler (which is what an immed message really is).  See all the old proc
+management commits if you want more info (check for changes to __startcore).
 
 Other Uses:
 --------------------------------
 Kernel messages will also be the basis for the alarm system.  All it is is
 expressing work that needs to be done.  That being said, the k_msg struct will
 probably receive a timestamp field, among other things.  Routine messages also
-will replace the old workqueue, which hasn't really been used in 10 months or
+will replace the old workqueue, which hasn't really been used in 40 months or
 so.
 
+Blocking:
+--------------------------------
+If a routine kernel message blocks (or has a chance to block), it must
+smp_idle() at the end.  If it were to return to PRKM(), it could be on a new
+core, due to kthread migration.  We might have a way to enforce this later.
+
 To Return or Not:
 --------------------------------
-Routine k_msgs do not have to return.  Urgent messages must.  The distinction is
-in how they are sent (send_kernel_message() will take a flag), so be careful.
-Technically, an immediate message could not return, but only if the kernel code
-that was interrupted was not holding any locks, mucking with any invariants, or
-otherwise doing work that needed to be done.  Those cases seem rather rare.
+Routine k_msgs do not have to return.  Immediate messages must.  The distinction
+is in how they are sent (send_kernel_message() will take a flag), so be careful.
 
 To retain some sort of sanity, the functions that do not return must adhere to
 some rules.  At some point they need to end in a place where they check routine
-messages or enable interrupts.  Returning to userspace will do this (interrupts
-are enabled).  __death will eventually call smp_idle(), which will check.  The
-idea behind this is that route messages will get processed once the kernel is
-able to (at a convenient place).
-
-Since some routine messages do not return by popping to userspace, we need to
-self-ipi to make sure the kernel regains control (this need might go away in the
-future).  Since we also want immediate messages to get processed before routine
-messages, and we want the system to be able to have a bunch of outstanding
-routine messages (though that is unlikely at this point), we briefly check
-for immed's inside process_routine_kmsg().  By only turning interrupts on for
-this means we avoid receiving excessive self_ipis for potentially not-returning
-routine messages.  Keep in mind that each one of those IPIs would be useless,
-since they will only run their functions when interrupting from userspace.
-
-Trickiness:
+messages or enable interrupts.  Simply calling smp_idle() will do this.  The
+idea behind this is that routine messages will get processed once the kernel is
+able to (at a convenient place). 
+
+Missing Routine Messages:
 --------------------------------
-If a function does not return, then the code might not check the list again, or
-send the EOI.  This is one reason why we send the EOI first, and insist that the
-__kernel_message() handler execute with interrupts disabled.  The routine
-messages do not need to have their interrupts disabled (if they are executed
-somewhere else).  If another IPI comes in, immediate messages will run, but
-other routine messages won't (they will get executed when the list is checked
-again).  However, enabling interrupts in the __kernel_message() handler can be
-problematic, depending on when the EOI is sent (nesting on the same code).
-
-The other reason we send_eoi() first is that we can only send it once per
-handler (not per message).  Otherwise, it can start acknowleding other interrupt
-vectors, which is bad.  We might move it in the while loop and protect it with a
-static check, but it doesn't seem worth it.  We still can't turn on interrupts,
-since the self_ipi could would fire and return while processing a routine
-function, negating the intent of the self_ipi.
-
-Since IPIs get "squashed" (my word, meaning if a core receives more than two at
-a time, future IPIs for a vector are ignored), and since functions might not
-return, there is the possibility of losing a message.  There can be more
-messages than IPIs (imagine three k_msgs, each that doesn't return).  To protect
-against this, if there is not an IPI pending (you can check on x86), and if
-there are messages in the routine list, then the code self_ipi's the current
-core.
-
-We don't need to check the immediate list, since we just checked it higher in
-the code (o/w, we wouldn't be executing routine messages).  If an immediate
-showed up since we executed the lapic_send_eoi(), an IPI will be on the way
-(messages are enqueued before sending the IPI).
-
-When we check the routine list, we don't need to lock.  All that macro does is
-check to see if head->item == 0 (and the list head won't get changed).  It's
-basically just a read, which gains no protection from a lock.
+It's important that the kernel always checks for routine messages before leaving
+the kernel, either to halt the core or to pop into userspace.  There is a race
+involved with messages getting posted after we check the list, but before we
+pop/halt.  In that time, we send an IPI.  This IPI will force us back into the
+kernel at some point in the code before process_routine_kmsg(), thus keeping us
+from missing the RKM.
+
+In the future, if we know the kernel code on a particular core is not attempting
+to halt/pop, then we could avoid sending this IPI.  This is the essence of the
+optimization in send_kernel_message() where we don't IPI ourselves.  A more
+formal/thorough way to do this would be useful, both to avoid bugs and to
+improve cross-core KMSG performance.
+
+IRQ Trickiness:
+--------------------------------
+You cannot enable interrupts in the handle_kmsg_ipi() handler, either in the
+code or in any immediate kmsg.  Since we send the EOI before running the handler
+(on x86), another IPI could cause us to reenter the handler, which would spin on
+the lock the previous context is holding (nested IRQ stacks).  Using irqsave
+locks is not sufficient, since they assume IRQs are not turned on in the middle
+of their operation (such as in the body of an immediate kmsg).
 
 Other Notes:
 --------------------------------
@@ -138,13 +127,6 @@ dynamically create the k_msgs (can pass them around easily, delay with them
 easily (alarms), and most importantly we can't deadlock by running out of room
 in a static buffer).
 
-When running our process_routine_kmsg()s, we could have made a userspace process
-that would get interrupted if there were any outstanding IPIs for routine
-messages.  We'd have to self_ipi, then switch to this process.  That kinda
-sucks, and would also mean that when we want to actually smp_idle, we'd have to
-be in userspace (and probably not cpu_halt()ing).  Making it possible to process
-the messages from within the kernel seemed much more flexible and better.
-
 Architecture Dependence:
 --------------------------------
 Some details will differ, based on architectural support.  For instance,
@@ -153,3 +135,6 @@ with maskable IPI vectors can use a different IPI for routine messages, and that
 interrupt can get masked whenever we enter the kernel (note, that means making
 every trap gate an interrupt gate), and we unmask that interrupt when we want to
 process routine messages.
+
+However, given the main part of kmsgs is arch-independent, I've consolidated all
+of it in one location until we need to have separate parts of the implementation.
index 17e2473..7cb11c0 100644 (file)
@@ -33,7 +33,7 @@ kref_get_not_zero().  You must have an internal reference for this.  And to
 protect that *internal* reference, you often need to lock or otherwise sync
 around the source of that internal reference (usually a list-like structure
 (LLS)), unless that ref is otherwise protected from concurrent freeing.
-4. If you plan to ressurect an object (make its refcnt go from 0 to 1), you
+4. If you plan to resurrect an object (make its refcnt go from 0 to 1), you
 need to use some other form of sync between the final freeing and the
 resurrection.
 
@@ -46,7 +46,7 @@ put the release function in the kref, which is what Linux used to do.  We do it
 to cut down on the number of places the function pointer is writen, since I
 expect those to change a lot as subsystems use krefs.  Finally, we only use
 krefs to trigger an object's release function, which might not free them
-forever.  They can be "ressurectd" back to having an external reference.  You
+forever.  They can be "resurrected" back to having an external reference.  You
 can do similar things in Linux, but it's not clear (to me) how separate that
 idea is from a kref.
 
@@ -133,7 +133,7 @@ which then the cache reader gets instead of failing at trying to get the
 original object.  The kref refcount only helps when the refcount goes from 1 to
 0, and on triggering the followup/release action.
 
-To ressurect, we can't just do:
+To resurrect, we can't just do:
        if (!kref_refcnt(&dentry->d_kref))
                kref_init(&dentry->d_kref, dentry_release, 1);
        else
@@ -143,7 +143,7 @@ There is a race on reading the refcnt and mucking with it.  If it is
 concurrently going from 1 -> 0, and we read 0, it is okay.  We still up it to 1.
 However, if we go from 1 -> 0 and read 1, we'll panic when we try to kref_get a
 0'd kref.  Also, doing this would be dangerous going from 0 -> 1 if other code
-would ressurect (which it does not!).  The solution is to use a kref_get that
+would resurrect (which it does not!).  The solution is to use a kref_get that
 doesn't care about 0 (__kref_get()).
 
 Elsewhere in this documentation, we talk about kref_get_not_zero().  That one
@@ -154,7 +154,7 @@ what we want.
 Trickiness with lockless data structures:
 ----------------------------
 Ideally, we want concurrent access to the dentry cache (or whatever cache has
-krefd objects that we want to ressurect).  Perhaps this is with CAS on linked
+krefd objects that we want to resurrect).  Perhaps this is with CAS on linked
 lists, or locks per hash bucket.  Since we need to prevent the resurrection of
 objects from proceeding while another thread could be trying to remove them, we
 need some sync between readers and writers.  Both threads in the scenario we've
index 29b186b..125d3e6 100644 (file)
@@ -101,8 +101,8 @@ of the 5 memory barriers.
 When writing code that synchronizes with other threads via shared memory, we
 have a variety of patterns.  Most infamous is the "signal, then check if the
 receiver is still listening", which is the critical part of the "check,
-signal, check again" pattern.  For exmaples, look at things like
-'notif_pending' and 'can_rcv_msg'.  
+signal, check again" pattern.  For examples, look at things like
+'notif_pending' and when we check VC_CAN_RCV_MSG in event.c.
 
 In these examples, "write" and "read" include things such as posting events or
 checking flags (which ultimately involve writes and reads).  You need to be
index f1f07ce..7f06ba6 100644 (file)
@@ -15,7 +15,8 @@ Contents:
 6. Locking!
 7. TLB Coherency
 8. Process Management
-9. TBD
+9. On the Ordering of Messages
+10. TBD
 
 1. Reference Counting
 ===========================
@@ -387,12 +388,14 @@ something.
 ----------------
 There are two ways to deal with this.  One (and the better one, I think) is to
 check state, and determine if it should proceed or abort.  This requires that
-all local-fate dependent calls always have enough state, meaning that any
-function that results in sending a directive to a vcore store enough info in
-the proc struct that a local call can determine if it should take action or
-abort.  This might be sufficient.  This works for death already, since you
-aren't supposed to do anything other than die (and restore any invariants
-first, handled in Section 3).  We'll go with this way.
+all local-fate dependent calls always have enough state to do its job.  In the
+past, this meant that any function that results in sending a directive to a
+vcore store enough info in the proc struct that a local call can determine if
+it should take action or abort.  In the past, we used the vcore/pcoremap as a
+way to send info to the receiver about what vcore they are (or should be).
+Now, we store that info in pcpui (for '__startcore', we send it as a
+parameter.  Either way, the general idea is still true: local calls can
+proceed when they are called, and not self-ipi'd to a nebulous later time.
 
 The other way is to send the work (including the checks) in a self-ipi kernel
 message.  This will guarantee that the message is executed after any existing
@@ -411,23 +414,29 @@ for a proc until AFTER the preemption is completed.
 4.2: Preempt-Served Flag
 ----------------
 We want to be able to consider a pcore free once its owning proc has dealt
-with removing it (not necessarily taken from the vcoremap, but at least it is
-a done-deal that the core will go away and the messages are sent).  This
-allows a scheduler-like function to easily take a core and then give it to
-someone else, without waiting for each vcore to respond, saying that the pcore
-is free/idle.
-
-Since we want to keep the pcore in the vcoremap, we need another signal to let
-a process know a message is already on its way.  preempt_pending is a signal
-to userspace that the alarm was set, not that an actual message is on its way
-and that a vcore's fate is sealed.  Since we can't use a pcore's presence in
-the vcoremap to determine that the core should be revoked, we have to check
-the "fate sealed"/preempt-served flag. 
-
-It's a bit of a pain to have this flag, just to resolve this race in the
-kernel, though the local call would have to check the vcoremap anyway,
-incurring a cache miss if we go with using the vcoremap to signal the
-impending message.
+with removing it.  This allows a scheduler-like function to easily take a core
+and then give it to someone else, without waiting for each vcore to respond,
+saying that the pcore is free/idle.
+
+We used to not unmap until we were in '__preempt' or '__death', and we needed
+a flag to tell yield-like calls that a message was already on the way and to
+not rely on the vcoremap.  This is pretty fucked up for a number of reasons,
+so we changed that.  But we still wanted to know when a preempt was in
+progress so that the kernel could avoid giving out the vcore until the preempt
+was complete.
+
+Here's the scenario: we send a '__startcore' to core 3 for VC5->PC3.  Then we
+quickly send a '__preempt' to 3, and then a '__startcore' to core 4 (a
+different pcore) for VC5->PC4.  Imagine all of this happens before the first
+'__startcore' gets processed (IRQ delay, fast ksched, whatever).  We need to
+not run the second '__startcore' on pcore 4 before the preemption has saved
+all of the state of the VC5.  So we spin on preempt_served (which may get
+renamed to preempt_in_progress).  We need to do this in the sender, and not
+the receiver (not in the kmsg), because the kmsgs can't tell which one they
+are.  Specifically, the first '__startcore' on core 3 runs the same code as
+the '__startcore' on core 4, working on the same vcore.  Anything we tell VC5
+will be seen by both PC3 and PC4.  We'd end up deadlocking on PC3 while it
+spins waiting for the preempt message that also needs to run on PC3.
 
 The preempt_pending flag is actual a timestamp, with the expiration time of
 the core at which the message will be sent.  We could try to use that, but
@@ -585,14 +594,13 @@ flexibility in schedule()-like functions (no need to wait to give the core
 out), quicker dispatch latencies, less contention on shared structs (like the
 idle-core-map), etc.
 
-Also, we don't remove the pcore from the vcoremap, even if it is being
-allocated to another core (the same pcore can exist in two vcoremaps, contrary
-to older statements).  Taking the pcore from the vcoremap would mean some
-non-fate related local calls (sys_get_vcoreid()) will fail, since the vcoreid
-is gone!  Additionally, we don't need a vcoreid in the k_msg (we would have if
-we could not use the vcore/pcoremappings).  There should not be any issues
-with the new process sending messages to the pcore before the core is sorted,
-since k_msgs are delivered in order.
+This 'freeing' of the pcore is from the perspective of the kernel scheduler
+and the proc struct.  Contrary to all previous announcements, vcores are
+unmapped from pcores when sending k_msgs (technically right after), while
+holding the lock.  The pcore isn't actually not-running-the-proc until the
+kmsg completes and we abandon_core().  Previously, we used the vcoremap to
+communicate to other cores in a lock-free manner, but that was pretty shitty
+and now we just store the vcoreid in pcpu info.
 
 Another tricky part is the seq_ctr used to signal userspace of changes to the
 coremap or num_vcores (coremap_seqctr).  While we may not even need this in the
@@ -618,13 +626,24 @@ future, we would like to have broadcast messaging of some sort (literally a
 broadcast, like the IPIs, and if not that, then a communication tree of
 sorts).  
 
-Given those desires, we want to make sure that no message we send needs
-details specific to a pcore (such as the vcoreid running on it, a history
-number, or anything like that).  Thus no k_msg related to process management
-should have anything that cannot apply to the entire process.  At this point,
-most just have a struct proc *.  A pcore ought to be able to figure out what
-is happening based on the pcoremap, information in the struct proc, and in the
-preempt struct in procdata.
+In the past, (OLD INFO): given those desires, we wanted to make sure that no
+message we send needs details specific to a pcore (such as the vcoreid running
+on it, a history number, or anything like that).  Thus no k_msg related to
+process management would have anything that cannot apply to the entire
+process.  At this point, most just have a struct proc *.  A pcore was be able
+to figure out what is happening based on the pcoremap, information in the
+struct proc, and in the preempt struct in procdata.
+
+In more recent revisions, the coremap no longer is meant to be used across
+kmsgs, so some messages ('__startcore') send the vcoreid.  This means we can't
+easily broadcast the message.  However, many broadcast mechanisms wouldn't
+handle '__startcore' naturally.  For instance, logical IPIs need something
+already set in the LAPIC, or maybe need to be sent to a somewhat predetermined
+group (again, bits in the LAPIC).  If we tried this for '__startcore', we
+could add something in to the messaging to carry these vcoreids.  More likely,
+we'll have a broadcast tree.  Keeping vcoreid (or any arg) next to whoever
+needs to receive the message is a very small amount of bookkeeping on a struct
+that already does bookkeeping.
 
 4.10: Other Things We Thought of but Don't Like
 ---------------------------
@@ -666,6 +685,30 @@ We also considered using the transition stack as a signal that a process is in
 a notification handler.  The kernel can inspect the stack pointer to determine
 this.  It's possible, but unnecessary.
 
+Using the pcoremap as a way to pass info with kmsgs: it worked a little, but
+had some serious problems, as well as making life difficult.  It had two
+purposes: help with local fate calls (yield) and allow broadcast messaging.
+The main issue is that it was using a global struct to pass info with
+messages, but it was based on the snapshot of state at the time the message
+was sent.  When you send a bunch of messages, certain state may have changed
+between messages, and the old snapshot isn't there anymore by the time the
+message gets there.  To avoid this, we went through some hoops and had some
+fragile code that would use other signals to avoid those scenarios where the
+global state change would send the wrong message.  It was tough to understand,
+and not clear it was correct (hint: it wasn't).  Here's an example (on one
+pcore): if we send a preempt and we then try to map that pcore to another
+vcore in the same process before the preempt call checks its pcoremap, we'll
+clobber the pcore->vcore mapping (used by startcore) and the preempt will
+think it is the new vcore, not the one it was when the message was sent.
+While this is a bit convoluted, I can imagine a ksched doing this, and
+perhaps with weird IRQ delays, the messages might get delayed enough for it to
+happen.  I'd rather not have to have the ksched worry about this just because
+proc code was old and ghetto.  Another reason we changed all of this was so
+that you could trust the vcoremap while holding the lock.  Otherwise, it's
+actually non-trivial to know the state of a vcore (need to check a combination
+of preempt_served and is_mapped), and even if you do that, there are some
+complications with doing this in the ksched.
+
 5. current_tf and owning_proc
 ===========================
 Originally, current_tf is a per-core macro that returns a struct trapframe *
@@ -710,6 +753,25 @@ iret.  At which point, if the code path is deep enough that we don't want to
 carry the TF pointer, we may revisit this.  Until then, current_tf is just for
 userspace contexts, and is simply stored in per_cpu_info.
 
+Brief note from the future (months after this paragraph was written): cur_tf
+has two aspects/jobs:
+1) tell the kernel what we should do (trap, fault, sysc, etc), how we came
+into the kernel (the fact that it is a user tf), which is why we copy-out
+early on
+2) be a vehicle for us to restart the process/vcore
+
+We've been focusing on the latter case a lot, since that is what gets
+removed when preempted, changed during a notify, created during a startcore,
+etc.  Don't forget it was also an instruction of sorts.  The former case is
+always true throughout the life of the syscall.  The latter only happens to be
+true throughout the life of a *non-blocking* trap since preempts are routine
+KMSGs.  But if we block in a syscall, the cur_tf is no longer the TF we came
+in on (and possibly the one we are asked to operate on), and that old cur_tf
+has probably restarted.
+
+(Note that cur_tf is a pointer, and syscalls/traps actually operate on the TF
+they came in on regardless of what happens to cur_tf or pcpui->actual_tf.)
+
 6. Locking!
 ===========================
 6.1: proc_lock
@@ -931,5 +993,404 @@ on), and then that vcore gets granted in the next round of vcore_requests().
 The preemption recovery handlers will need to deal with concurrent handlers
 and the vcore itself starting back up.
 
-9. TBD
+9. On the Ordering of Messages and Bugs with Old State
+===========================
+This is a sordid tale involving message ordering, message delivery times, and
+finding out (sometimes too late) that the state you expected is gone and
+having to deal with that error.
+
+A few design issues:
+- being able to send messages and have them execute in the order they are
+  sent
+- having message handlers resolve issues with global state.  Some need to know
+  the correct 'world view', and others need to know what was the state at the
+  time they were sent.
+- realizing syscalls, traps, faults, and any non-IRQ entry into the kernel is
+  really a message.
+
+Process management messages have alternated from ROUTINE to IMMEDIATE and now
+back to ROUTINE.  These messages include such family favorites as
+'__startcore', '__preempt', etc.  Meanwhile, syscalls were coming in that
+needed to know about the core and the process's state (specifically, yield,
+change_to, and get_vcoreid).  Finally, we wanted to avoid locking, esp in
+KMSGs handlers (imagine all cores grabbing the lock to check the vcoremap or
+something).
+
+Incidentally, events were being delivered concurretly to vcores, though that
+actually didn't matter much (check out async_events.txt for more on that).
+
+9.1: Design Guidelines
+---------------------------
+Initially, we wanted to keep broadcast messaging available as an option.  As
+noted elsewhere, we can't really do this well for startcore, since most
+hardware broadcast options need some initial per-core setup, and any sort of
+broadcast tree we make should be able to handle a small message.  Anyway, this
+desire in the early code to keep all messages identical lead to a few
+problems.
+
+Another objective of the kernel messaging was to avoid having the message
+handlers grab any locks, especially the same lock (the proc lock is used to
+protect the vcore map, for instance).
+
+Later on, a few needs popped up that motivated the changes discussed below:
+- Being able to find out which proc/vcore was on a pcore
+- Not having syscalls/traps require crazy logic if the carpet was pulled out
+  from under them.
+- Having proc management calls return.  This one was sorted out by making all
+  kmsg handlers return.  It would be a nightmare making a ksched without this.
+
+9.2: Looking at Old State: a New Bug for an Old Problem
+---------------------------
+We've always had issues with syscalls coming in and already had the fate of a
+core determined.  This is referred to in a few places as "predetermined fate"
+vs "local state".  A remote lock holder (ksched) already determined a core
+should be unmapped and sent a message.  Only later does some call like
+proc_yield() realize its core is already *unmapped*. (I use that term poorly
+here).  This sort of code had to realize it was working on an old version of
+state and just abort.  This was usually safe, though looking at the vcoremap
+was a bad idea.  Initially, we used preempt_served as the signal, which was
+okay.  Around 12b06586 yield started to use the vcoremap, which turned out to
+be wrong.
+
+A similar issue happens for the vcore messages (startcore, preempt, etc).  The
+way startcore used to work was that it would only know what pcore it was on,
+and then look into the vcoremap to figure out what vcoreid it should be
+running.  This was to keep broadcast messaging available as an option.  The
+problem with it is that the vcoremap may have changed between when the
+messages were sent and when they were executed.  Imagine a startcore followed
+by a preempt, afterwhich the vcore was unmapped.  Well, to get around that, we
+had the unmapping happen in the preempt or death handlers.  Yikes!  This was
+the case back in the early days of ROS.  This meant the vcoremap wasn't
+actually representative of the decisions the ksched made - we also needed to
+look at the state we'd have after all outstanding messages executed.  And this
+would differ from the vcore lists (which were correct for a lock holder).
+
+This was managable for a little while, until I tried to conclusively know who
+owned a particular pcore.  This came up while making a provisioning scheduler.
+Given a pcore, tell me which process/vcore (if any) were on it.  It was rather
+tough.  Getting the proc wasn't too hard, but knowing which vcore was a little
+tougher.  (Note the ksched doesn't care about which vcore is running, and the
+process can change vcores on a pcore at will).  But once you start looking at
+the process, you can't tell which vcore a certain pcore has.  The vcoremap may
+be wrong, since a preempt is already on the way.  You would have had to scan
+the vcore lists to see if the proc code thought that vcore was online or not
+(which would mean there had been no preempts).  This is the pain I was talking
+about back around commit 5343a74e0.
+
+So I changed things so that the vcoremap was always correct for lock holders,
+and used pcpui to track owning_vcoreid (for preempt/notify), and used an extra
+KMSG variable to tell startcore which vcoreid it should use.  In doing so, we
+(re)created the issue that the delayed unmapping dealt with: the vcoremap
+would represent *now*, and not the vcoremap of when the messages were first
+sent.  However, this had little to do with the KMSGs, which I was originally
+worried about.  No one was looking at the vcoremap without the lock, so the
+KMSGs were okay, but remember: syscalls are like messages too.  They needed to
+figure out what vcore they were on, i.e. what vcore userspace was making
+requests on (viewing a trap/fault as a type of request).
+
+Now the problem was that we were using the vcoremap to figure out which vcore
+we were supposed to be.  When a syscall finally ran, the vcoremap could be
+completely wrong, and with immediate KMSGs (discussed below), the pcpui was
+already changed!  We dealt with the problem for KMSGs, but not syscalls, and
+basically reintroduced the bug of looking at current state and thinking it
+represented the state from when the 'message' was sent (when we trapped into
+the kernel, for a syscall/exception).
+
+9.3: Message Delivery, Circular Waiting, and Having the Carpet Pulled Out
+---------------------------
+In-order message delivery was what drove me to build the kernel messaging
+system in the first place.  It provides in-order messages to a particular
+pcore.  This was enough for a few scenarios, such as preempts racing ahead of
+startcores, or deaths racing a head of preempts, etc.  However, I also wanted
+an ordering of messages related to a particular vcore, and this wasn't
+apparent early on.
+
+The issue first popped up with a startcore coming quickly on the heals of a
+preempt for the same VC, but on different PCs.  The startcore cannot proceed
+until the preempt saved the TF into the VCPD.  The old way of dealing with
+this was to spin in '__map_vcore()'.  This was problematic, since it meant we
+were spinning while holding a lock, and resulted in some minor bugs and issues
+with lock ordering and IRQ disabling (couldn't disable IRQs and then try to
+grab the lock, since the lock holder could have sent you a message and is
+waiting for you to handle the IRQ/IMMED KMSG).  However, it was doable.  But
+what wasn't doable was to have the KMSGs be ROUTINE.  Any syscalls that tried
+to grab the proc lock (lots of them) would deadlock, since the lock holder was
+waiting on us to handle the preempt (same circular waiting issue as above).
+
+This was fine, albeit subpar, until a new issue showed up.  Sending IMMED
+KMSGs worked fine if we were coming from userspace already, but if we were in
+the kernel, those messages would run immediately (hence the name), just like
+an IRQ handler, and could confuse syscalls that touched cur_tf/pcpui.  If a
+preempt came in during a syscall, the process/vcore could be changed before
+the syscall took place.  Some syscalls could handle this, albeit poorly.
+sys_proc_yield() and sys_change_vcore() delicately tried to detect if they
+were still mapped or not and use that to determine if a preemption happened.
+
+As mentioned above, looking at the vcoremap only tells you what is currently
+happening, and not what happened in the past.  Specifically, it doesn't tell
+you the state of the mapping when a particular core trapped into the kernel
+for a syscall (referred to as when the 'message' was sent up above).  Imagine
+sys_get_vcoreid(): you trap in, then immediately get preempted, then startcore
+for the same process but a different vcoreid.  The syscall would return with
+the vcoreid of the new vcore, since it cannot tell there was a change.  The
+async syscall would complete and we'd have a wrong answer.  While this never
+happened to me, I had a similar issue while debugging some other bugs (I'd get
+a vcoreid of 0xdeadbeef, for instance, which was the old poison value for an
+unmapped vcoreid).  There are a bunch of other scenarios that trigger similar
+disasters, and they are very hard to avoid.
+
+One way out of this was a per-core history counter, that changed whenever we
+changed cur_tf.  Then when we trapped in for a syscall, we could save the
+value, enable_irqs(), and go about our business.  Later on, we'd have to
+disable_irqs() and compare the counters.  If they were different, we'd have to
+bail out some how.  This could have worked for change_to and yield, and some
+others.  But any syscall that wanted to operate on cur_tf in some way would
+fail (imagine a hypothetical sys_change_stack_pointer()).  The context that
+trapped has already returned on another core.  I guess we could just fail that
+syscall, though it seems a little silly to not be able to do that.
+
+The previous example was a bit contrived, but lets also remember that it isn't
+just syscalls: all exceptions have the same issue.  Faults might be fixable,
+since if you restart a faulting context, it will start on the faulting
+instruction.  However all traps (like syscall) restart on the next
+instruction.  Hope we don't want to do anything fancy with breakpoint!  Note
+that I had breakpointing contexts restart on other pcores and continue while I
+was in the breakpoint handler (noticed while I was debugging some bugs with
+lots of preempts).  Yikes.  And don't forget we eventually want to do some
+complicated things with the page fault handler, and may want to turn on
+interrupts / kthread during a page fault (imaging hitting disk).  Yikes.
+
+So I looked into going back to ROUTINE kernel messages.  With ROUTINE
+messages, I didn't have to worry about having the carpet pulled out from under
+syscalls and exceptions (traps, faults, etc).  The 'carpet' is stuff like
+cur_tf, owning_proc, owning_vcoreid, etc.  We still cannot trust the vcoremap,
+unless we *know* there were no preempts or other KMSGs waiting for us.
+(Incidentally, in the recent fix a93aa7559, we merely use the vcoremap as a
+sanity check).
+
+However, we can't just switch back to ROUTINEs.  Remember: with ROUTINEs,
+we will deadlock in '__map_vcore()', when it waits for the completion of
+preempt.  Ideally, we would have had startcore spin on the signal.  Since we
+already gave up on using x86-style broadcast IPIs for startcore (in
+5343a74e0), we might as well pass along a history counter, so it knows to wait
+on preempt.
+
+9.4: The Solution
+---------------------------
+To fix up all of this, we now detect preemptions in syscalls/traps and order
+our kernel messages with two simple per-vcore counters.  Whenever we send a
+preempt, we up one counter.  Whenever that preempt finishes, it ups another
+counter.  When we send out startcores, we send a copy of the first counter.
+This is a way of telling startcore where it belongs in the list of messages.
+More specifically, it tells it which preempt happens-before it.
+
+Basically, I wanted a partial ordering on my messages, so that messages sent
+to a particular vcore are handled in the order they were sent, even if those
+messages run on different physical cores.
+
+It is not sufficient to use a seq counter (one integer, odd values for
+'preempt in progress' and even values for 'preempt done').  It is possible to
+have multiple preempts in flight for the same vcore, albeit with startcores in
+between.  Still, there's no way to encode that scenario in just one counter.
+
+Here's a normal example of traffic to some vcore.  I note both the sending and
+the execution of the kmsgs:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0)
+   0              0              X         startcore (executes)
+   1              0              X         preempt   (kmsg sent)
+   1              1              Y         preempt   (executes)
+   1              1              Y         startcore (nr_pre_sent == 1)
+   1              1              Y         startcore (executes)
+
+Note the messages are always sent by the lockholder in the order of the
+example above.
+
+Here's when the startcore gets ahead of the prior preempt:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0) 
+   0              0              X         startcore (executes)
+   1              0              X         preempt   (kmsg sent)
+   1              0              Y         startcore (nr_pre_sent == 1)
+   1              1              X         preempt   (executes)
+   1              1              Y         startcore (executes)
+
+Note that this can only happen across cores, since KMSGs to a particular core
+are handled in order (for a given class of message).  The startcore blocks on
+the prior preempt.
+
+Finally, here's an example of what a seq ctr can't handle:
+   nr_pre_sent    nr_pre_done    pcore     message sent/status
+   -------------------------------------------------------------
+   0              0              X         startcore (nr_pre_sent == 0) 
+   1              0              X         preempt   (kmsg sent)
+   1              0              Y         startcore (nr_pre_sent == 1)
+   2              0              Y         preempt   (kmsg sent)
+   2              0              Z         startcore (nr_pre_sent == 2)
+   2              1              X         preempt   (executes (upped to 1))
+   2              1              Y         startcore (executes (needed 1))
+   2              2              Y         preempt   (executes (upped to 2))
+   2              Z              Z         startcore (executes (needed 2))
+
+As a nice bonus, it is easy for syscalls that care about the vcoreid (yield,
+change_to, get_vcoreid) to check if they have a preempt_served.  Just grab the
+lock (to prevent further messages being sent), then check the counters.  If
+they are equal, there is no preempt on its way.  This actually was the
+original way we checked for preempts in proc_yield back in the day.  It was
+just called preempt_served.  Now, it is split into two counters, instead of
+just being a bool.  
+
+Regardless of whether or not we were preempted, we still can look at
+pcpui->owning_proc and owning_vcoreid to figure out what the vcoreid of the
+trap/syscall is, and we know that the cur_tf is still the correct cur_tf (no
+carpet pulled out), since while there could be a preempt ROUTINE message
+waiting for us, we simply haven't run it yet.  So calls like yield should
+still fail (since your core has been unmapped and you need to bail out and run
+the preempt handler), but calls like sys_change_stack_pointer can proceed.
+More importantly than that old joke syscall, the page fault handler can try to
+do some cool things without worrying about really crazy stuff.
+
+9.5: Why We (probably) Don't Deadlock
+---------------------------
+It's worth thinking about why this setup of preempts and startcores can't
+deadlock.  Anytime we spin in the kernel, we ought to do this.  Perhaps there
+is some issue with other KMSGs for other processes, or other vcores, or
+something like that that can cause a deadlock.
+
+Hypothetical case: pcore 1 has a startcore for vc1 which is stuck behind vc2's
+startcore on PC2, with time going upwards.  In these examples, startcores are
+waiting on particular preempts, subject to the nr_preempts_sent parameter sent
+along with the startcores.
+
+^                       
+|            _________                 _________
+|           |         |               |         |
+|           | pr vc 2 |               | pr vc 1 |
+|           |_________|               |_________|
+|
+|            _________                 _________
+|           |         |               |         |
+|           | sc vc 1 |               | sc vc 2 |
+|           |_________|               |_________|
+t           
+---------------------------------------------------------------------------
+              ______                    ______
+             |      |                  |      |
+             | PC 1 |                  | PC 2 |
+             |______|                  |______|
+
+Here's the same picture, but with certain happens-before arrows.  We'll use X --> Y to
+mean X happened before Y, was sent before Y.  e.g., a startcore is sent after
+a preempt.
+
+^                       
+|            _________                 _________
+|           |         |               |         |
+|       .-> | pr vc 2 | --.    .----- | pr vc 1 | <-.
+|       |   |_________|    \  /   &   |_________|   |  
+|     * |                   \/                      | * 
+|       |    _________      /\         _________    |  
+|       |   |         |    /  \   &   |         |   |  
+|       '-- | sc vc 1 | <-'    '----> | sc vc 2 | --'
+|           |_________|               |_________|
+t           
+---------------------------------------------------------------------------
+              ______                    ______
+             |      |                  |      |
+             | PC 1 |                  | PC 2 |
+             |______|                  |______|
+
+The arrows marked with * are ordered like that due to the property of KMSGs,
+in that we have in order delivery.  Messages are executed in the order in
+which they were sent (serialized with a spinlock btw), so on any pcore,
+messages that are further ahead in the queue were sent before (and thus will
+be run before) other messages.
+
+The arrows marked with a & are ordered like that due to how the proc
+management code works.  The kernel won't send out a startcore for a particular
+vcore before it sent out a preempt.  (Note that techincally, preempts follow
+startcores.  The startcores in this example are when we start up a vcore after
+it had been preempted in the past.).
+
+Anyway, note that we have a cycle, where all events happened before each
+other, which isn't possible.  The trick to connecting "unrelated" events like
+this (unrelated meaning 'not about the same vcore') in a happens-before manner
+is the in-order properties of the KMSGs.
+
+Based on this example, we can derive general rules.  Note that 'sc vc 2' could
+be any kmsg that waits on another message placed behind 'sc vc 1'.  This would
+require us having sent a KMSG that waits on a KMSGs that we send later.  Bad
+idea!  (you could have sent that KMSGs to yourself, aside from just being
+dangerous).  If you want to spin, make sure you send the work that should
+happen-before actually-before the waiter.
+
+In fact, we don't even need 'sc vc 2' to be a KMSG.  It could be miscellaneous
+kernel code, like a proc mgmt syscall.  Imagine if we did something like the
+old '__map_vcore' call from within the ksched.  That would be code that holds
+the lock, and then waits on the execution of a message handler.  That would
+deadlock (which is why we don't do it anymore).
+
+Finally, in case this isn't clear, all of the startcores and preempts for
+a given vcore exist in a happens-before relation, both in sending and in
+execution.  The sending aspect is handled by proc mgmt code.  For execution,
+preempts always follow startcores due to the KMSG ordering property.  For
+execution of startcores, startcores always spin until the preempt they follow
+is complete, ensuring the execution of the main part of their handler happens
+after the prior preempt.
+
+Here's some good ideas for the ordering of locks/irqs/messages:
+- You can't hold a spinlock of any sort and then wait on a routine kernel
+  message.  The core where that runs may be waiting on you, or some scenario
+  like above.
+       - Similarly, think about how this works with kthreads.  A kthread restart
+         is a routine KMSG.  You shouldn't be waiting on code that could end up
+         kthreading, mostly because those calls block!
+- You can hold a spinlock and wait on an IMMED kmsg, if the waiters of the
+  spinlock have irqs enabled while spinning (this is what we used to do with
+  the proc lock and IMMED kmsgs, and 54c6008 is an example of doing it wrong)
+       - As a corollary, locks like this cannot be irqsave, since the other
+         attempted locker will have irq disabled
+- For broadcast trees, you'd have to send IMMEDs for the intermediates, and
+  then it'd be okay to wait on those intermediate, immediate messages (if we
+  wanted confirmation of the posting of RKM)
+       - The main thing any broadcast mechanism needs to do is make sure all
+         messages get delivered in order to particular pcores (the central
+         premise of KMSGs) (and not deadlock due to waiting on a KMSG improperly)
+- Alternatively, we could use routines for the intermediates if we didn't want
+  to wait for RKMs to hit their destination, we'd need to always use the same
+  proxy for the same destination pcore, e.g., core 16 always covers 16-31.
+       - Otherwise, we couldn't guarantee the ordering of SC before PR before
+         another SC (which the proc_lock and proc mgmt code does); we need the
+         ordering of intermediate msgs on the message queues of a particular
+         core.
+       - All kmsgs would need to use this broadcasting style (couldn't mix
+         regular direct messages with broadcast), so odds are this style would be
+         of limited use.
+       - since we're not waiting on execution of a message, we could use RKMs
+         (while holding a spinlock)
+- There might be some bad effects with kthreads delaying the reception of RKMS
+  for a while, but probably not catastrophically.
+
+9.6: Things That We Don't Handle Nicely
+---------------------------
+If for some reason a syscall or fault handler blocks *unexpectedly*, we could
+have issues.  Imagine if change_to happens to block in some early syscall code
+(like instrumentation, or who knows what, that blocks in memory allocation).
+When the syscall kthread restarts, its old cur_tf is gone.  It may or may not
+be running on a core owned by the original process.  If it was, we probably
+would accidentally yield that vcore (clearly a bug).  
+
+For now, any of these calls that care about cur_tf/pcpui need to not block
+without some sort of protection.  None of them do, but in the future we might
+do something that causes them to block.  We could deal with it by having a
+pcpu or per-kthread/syscall flag that says if it ever blocked, and possibly
+abort.  We get into similar nasty areas as with preempts, but this time, we
+can't solve it by making preempt a routine KMSG - we block as part of that
+syscall/handler code.  Odds are, we'll just have to outlaw this, now and
+forever.  Just note that if a syscall/handler blocks, the TF it came in on is
+probably not cur_tf any longer, and that old cur_tf has probably restarted.
+
+10. TBD
 ===========================
diff --git a/GETTING_STARTED b/GETTING_STARTED
new file mode 100644 (file)
index 0000000..e8d41cf
--- /dev/null
@@ -0,0 +1,347 @@
+GETTING_STARTED
+Barret Rhoden
+
+Last updated 2013-02-07
+
+
+1. Overview
+---------------------
+In this document, I outline what steps I go through to set up my development
+environment.  Some devs use other setups, and they can put sections farther
+down in this document describing their steps.
+
+Due to the nature of different workflows and different Linux distros, you'll
+need to do some configuration of your environment.  Things won't magically work
+out of the box.
+
+
+2. Need help?
+---------------------
+First off, if you get stuck, email someone.  You can join our mailing list by
+sending an email to akaros-request@lists.eecs.berkeley.edu.  Send your messages
+to akaros@lists.eecs.berkeley.edu.  Or just email me (brho@cs), though the
+mailing list is a more scalable method in the long run.
+
+Alternatively, you can poke your head in #akaros on irc.freenode.net.  I'm
+usually idling in there (alone), and if I'm at my computer, I'll respond.
+
+
+3. From Download to Hello World
+---------------------
+I'll describe how to get x86 working.  RISCV is similar.
+
+
+3.1 Cross compiler (and glibc)
+----------
+First step is to build the cross compiler, which lives in
+tools/compilers/gcc-glibc
+
+$ cd tools/compilers/gcc-glibc
+
+In this directory, you first need to set up your Makelocal file.  There is a
+template to work from.
+
+$ cp Makelocal.template Makelocal
+
+You need to set your INSTDIRS to some place where you want the cross compiler
+installed.  I have a directory named ros-gcc-glibc for this.
+
+You can also set up MAKE_JOBS, so you don't over or under load your system when
+building.  I have a 2 core laptop, so I use MAKE_JOBS := 3
+
+At this point, you can build:
+
+$ make x86
+
+This might take a while (10-20 minutes for me on a 2007 era laptop).
+
+Finally, add the cross compiler's bin directories to your PATH.  This will vary
+based on where you installed things.  For instance, my path contains:
+
+/home/brho/classes/ros/ros-gcc-glibc/install-i386-ros-gcc/bin
+
+Just to double check, you should be able to run i686-ros-gcc from your shell.
+
+Now, you have a cross compiler ready, and you can start to build Akaros.
+
+
+3.2 Kernel
+----------
+cd back into the repo root.
+
+Like the cross compiler, the kernel has its own Makelocal.
+
+$ cp Makelocal.template Makelocal
+
+There are a lot of settings in here, which you need to uncomment to turn on.
+
+Most everyone wants KFS turned on (CONFIG_KFS).  This is the in-memory
+filesystem that the kernel uses.  The kernel build scripts will look at
+INITRAMFS_PATHS and take any of those directories and add them to a CPIO
+archive that will eventually become the root filesystem when Akaros runs.  I
+set CONFIG_KFS and suggested a INITRAMFS_PATH in the Makelocal.template.
+
+There are also settings for ext2.  If you turn on ext2 support, you need to
+point to an img file that has been formatted with ext2 and has files in it.  If
+you aren't messing with filesystems at all, feel free to ignore this.  It's an
+in-memory filesystem, like KFS (linked to the end of the kernel), so you won't
+gain much by using it for now.
+
+Now you're ready to build the kernel:
+
+$ make x86
+
+On future makes, you can just 'make'.  The initial make x86 is to pick a target
+architecture.
+
+So the kernel built, but you can't do much with it, and you probably have no
+programs.
+
+3.3 Userspace
+---------
+To build userspace and test programs:
+
+$ make tests
+
+You now have programs and libraries, and need to put them in KFS.  To do this,
+I have a script called 'fill_kfs.sh'.  I usually have it in the directory above
+my repo root.  I put a copy of it in scripts/fill_kfs.sh in the repo.  You will
+need to edit it for your own setup.  Or you can do everything manually.  Either
+way, you need to make sure shared libraries are copied into kern/kfs/lib (given
+kern/kfs as your INITRAMFS_PATH) and you want your programs copied to
+kern/kfs/bin.
+
+Now that you've changed the contents of KFS's source, remake the kernel.  You
+should see something like
+       Building initramfs:
+               Adding kern/kfs to initramfs...
+before the kernel links.  If you don't see this, then you probably didn't
+actually fill KFS properly.
+
+3.4 Busybox
+---------
+If you don't care about busybox or just want to get started immediately, skip
+this section.
+
+Other userspace programs, like busybox need to be compiled with the cross
+compiler and then have their binaries copied to kern/kfs/bin (I do this
+manually).
+
+I'm running busybox 1.17.3, and the config file I use is in tools/patches.
+Copy that to your busybox directory (once you download and untar it, etc) and
+name it ".config".  You can get busybox from http://www.busybox.net/downloads/.
+Eventually I'll upgrade, though it hasn't been a big deal yet.
+
+$ cp tools/patches/busybox-1.17.3.config BUSYBOXDIR/.config
+
+$ cd BUSYBOXDIR ; make
+
+Then I copy the unstripped binary to KFS.
+
+$ cp busybox_unstripped AKAROS-REPO/kern/kfs/bin/busybox
+
+Note I change the name to busybox (dropping the unstripped).  I want the
+unstripped binary for debugging reasons.
+
+Busybox can do core commands like ls and rm, as well as run a shell (ash), all
+from within one binary.  It can tell which command it should execute based on
+the name of the binary (or symlink to it).  I have a bunch of symlinks for
+whatever 'busybox' programs I want to run inside kern/kfs/bin.
+
+For instance, from my AKAROS-ROOT:
+$ ls -l kern/kfs/bin/ | grep busybox
+lrwxrwxrwx 1 brho brho      7 Aug 24  2010 ash -> busybox
+-rwxr-xr-x 1 brho brho 337917 Dec 19 17:39 busybox
+lrwxrwxrwx 1 brho brho      7 Sep 29  2010 cat -> busybox
+lrwxrwxrwx 1 brho brho      7 Sep  1  2010 cp -> busybox
+lrwxrwxrwx 1 brho brho      7 Oct 18 13:12 kill -> busybox
+lrwxrwxrwx 1 brho brho      7 Sep  5  2010 ln -> busybox
+lrwxrwxrwx 1 brho brho      7 Aug 23  2010 ls -> busybox
+lrwxrwxrwx 1 brho brho      7 Sep  5  2010 mkdir -> busybox
+lrwxrwxrwx 1 brho brho      7 Sep  5  2010 rmdir -> busybox
+lrwxrwxrwx 1 brho brho      7 Apr  9  2012 stty -> busybox
+lrwxrwxrwx 1 brho brho      7 Apr  9  2012 tty -> busybox
+
+Note I don't need to update the symlinks (almost ever...).  I just recopy the
+busybox binary whenever I update it.
+
+I think some of the other devs build busybox so that it spits out the links
+into an install directory.  Feel free to do whatever.  I'll probably just add a
+bunch of symlinks to the repos default KFS contents one of these days.
+Incidentally, kern/kfs/* is now ignored by git.
+
+Now that you've changed KFS, don't forget to remake the kernel.
+
+3.5 Building and Loading a Virtual Machine Image
+---------
+At this point, you probably have a runnable kernel with programs in KFS.  It
+should be sitting at obj/kernel/kernel.  However, you need a place to run it.
+
+I run my kernels either in KVM (Qemu) or off a bootable USB stick.
+
+You'll need an image file that looks like a hard disk to boot qemu off of.  I
+put one similar to mine at: http://akaros.cs.berkeley.edu/files/hdd268mb.img
+
+It's around 268MB (256MiB, or whatever).  If you want to make your own, check
+out Documentation/howtos/make-bootable-grub-hdd.txt.  That's actually the
+original document I made back when I first figured it out back in 2009, which
+has been updated again in 2013.    In between, I wrote it up online at
+http://www.omninerd.com/articles/Installing_GRUB_on_a_Hard_Disk_Image_File,
+which has some other tidbits in the comments.  Both methods still use grub1.
+
+Anyway, I put that img in AKAROS-ROOT/mnt/, and make a folder next to it:
+AKAROS-ROOT/mnt/hdd.  mnt/hdd is the mount point where I mount hdd.img (Note I
+don't call it hdd64mb.img on my dev machine).
+
+Personally, I always have hdd.img mounted.  Some of the other devs have make
+targets that mount and umount it.  Whenever I reboot my development machine, I
+run a script (as root) that mounts the image file and sets up a few things for
+networking.  I put a script I use for this in scripts/kvm-up.sh.  You'll need
+to edit this to use it, and feel free to comment out the networking stuff.
+That's for using networking in qemu.
+
+Now that your image file is mounted at mnt/hdd, you'll want to copy your
+freshly built kernel to the root of the image.  I have a make target in my
+makelocal for this, so that whenever I do a make kvm, it builds the kernel and
+copies it to my hdd.img.
+
+I added edited versions of my KVM (and USB) make targets to the
+Makelocal.template.  Uncomment the KVM one (at least).
+
+Incidentally, I also have the following in my Makelocal, so that make (and make
+all) also make kvm:
+
+all: kvm
+
+Now, make kvm.  You should be able to see the new kernel in mnt/hdd/ (do an ls
+-l and check the timestamp).
+
+
+3.6 Running Qemu
+---------
+Here is the command I use to run qemu/kvm.  It's evolved over the years, and it
+will vary based on your linux distribution.  Don't run it just yet:
+
+$ qemu-system-i386 -s -enable-kvm -cpu coreduo -smp 8 -m 1024 -nographic -monitor /dev/pts/3 -net nic,model=e1000 -net tap,ifname=tap0,script=no mnt/hdd.img
+
+The -monitor is the qemu monitor, which is a CLI for qemu.  Pick a
+tab/terminal/pty in Linux that you will only use for qemu monitoring, and enter
+'tty'.  Whatever it tells you, put in place of /dev/pts/3.  I've been using the
+same tab for about 4 years now.  In that tab, enter 'sleep 999999999'.  Qemu
+will still access it, but you won't have to worry about bash trying to handle
+your inputs.
+
+-nographic allows qemu to work in the terminal you run qemu from, instead of
+spawning off a fake cpu crt/monitor.
+
+If you don't have networking set up (including the tun/tap stuff from
+kvm-up.sh), remove the -net commands/options.
+
+Fell free to pick different values for the number of cpus and RAM (8 and 1024
+in the example).
+
+Once you finally run it, you can stop the VM by entering 'q' to the qemu
+monitor (or just killing the process)..  Other help commands from the monitor
+include 'info cpus', 'info registers', 'x', and 'help'.
+
+
+3.7 Running on Hardware
+---------
+I have a few bootable USB sticks with grub set up to run Akaros.  The make usb
+target (example in Makelocal.template) will copy freshly made kernels to your
+USB device.  You'll need to adjust those paths according to your distro.  My
+usb sticks are usually /dev/sdc, for instance (some odd USB device in the last
+couple of years has taken over /dev/sdb.  Probably something to do with udev
+changing over the years).
+
+Anyway, you'll need to mess around a bit to get that working.  Or I can dd one
+for you (I have 4GB disks in my office that I use).  If you make your own, the
+critical part is getting grub to pick the right device (from what I remember),
+and its fairly similar to installing grub on any old hard drive (since it's
+just a bloc device).  Much easier than a hard disk image file.
+
+
+3.8 Hello World
+---------
+So now you can run the kernel.  It's time to edit a program (or make your own).
+In this, I'll go through my workflow for making changes.
+
+$ vi tests/hello.c
+(edit, save)
+
+$ make tests
+(new version in obj/tests/hello)
+
+$ ../fill-kfs.sh
+(updates kfs)
+
+$ make
+(rebuilds kernel with the new KFS)
+
+$ qemu...
+
+(following commands are in Akaros)
+Shift-G (to get to the kernel monitor)
+
+ROS(Core 0)> bb (to run busybox)
+
+/ $ hello
+(Should print your message)
+
+
+3.9 Other Dev Workflow stuff
+---------
+One thing to note is that while we use dynamic linking for libc, parlib
+libraries are statically linked with applications.  In fact, nowadays *all*
+Akaros programs need to be linked againt parlib (used to be that single-core
+processes (SCPs) didn't need it).
+
+The makefiles won't notice if you change a file in parlib and then remake a
+binary.  So if you edit user/parlib/uthread.c for example, tests/pthread_test
+won't get rebuilt.  Here's what I do:
+
+$ vi user/parlib/uthread.c (make awesome change)
+
+$ touch tests/pthread_test.c ; make tests
+
+This will force the rebuild of pthread_test.  Older, untouched binaries (e.g.
+block_test), won't get rebuilt.  I actually want this in some cases (different
+versions of parlib when I'm running certain tests).  Anyway, just pay attention
+to what you're building.  There's not much output in the console, so you should
+be able to see what's going on all the time.  (unlike when building glibc...).
+
+Oh, and don't forget to:
+
+$ ../fill-kfs.sh (or whatever you do)
+
+to make sure you run the new pthread_test. 
+
+Early on as a dev, there are lots of times where you accidentally don't run the
+right program (or kernel) and won't understand why your change isn't happening.
+A few printk("WTF\n")'s later, you realize you didn't have the hdd.img mounted,
+or you didn't fill KFS, or you didn't relink your binaries, or you forgot to
+save all files in vi (and not just the current buffer).  But after doing a
+couple hello worlds, you're set. 
+
+Alternatively, you could have a make target to run qemu, which also touches all
+binaries (or otherwise enforces a rebuild), auto-fills KFS, remakes the kernel,
+and mounts/copies/unmounts your hdd.img.  Kevin's sim repo has stuff like this,
+so check it out if that's what you're into.  (I think it is at
+http://akaros.cs.berkeley.edu/ros-sim.tar.gz).  Personally, I'm not that into
+it, since I like to keep track of what is going on under the hood, esp if I
+want to do something a little differently (like with testing ext2, having
+different versions of parlib with some binaries, or being picky about my
+mount/umounts).
+
+
+4. RISCV
+---------------------
+TODO.
+
+For now, you need a 64 bit distro to build the RISCV stuff, so I don't do it
+very often.  I'll eventually sync up with Andrew and we'll get this part sorted
+out.
+
+
+5. Other Developer's Stuff
+---------------------
index 39ffd74..0c67d05 100644 (file)
@@ -95,6 +95,7 @@ endif
 
 # Default programs for compilation
 USER_CFLAGS += -O2 -std=gnu99
+USER_CXXFLAGS += -O2
 ifeq ($(COMPILER),IVY)
 KERN_CFLAGS += --deputy \
                --no-rc-sharc \
@@ -110,6 +111,7 @@ else
 CC         := $(GCCPREFIX)gcc 
 endif
 
+CPP        := $(GCCPREFIX)g++
 AS         := $(GCCPREFIX)as
 AR         := $(GCCPREFIX)ar
 LD         := $(GCCPREFIX)ld
@@ -164,7 +166,8 @@ GCC_ROOT := $(shell which $(GCCPREFIX)gcc | xargs dirname)/../
 tests/: tests
 tests: install-libs
        @$(MAKE) -j $(MAKE_JOBS) realtests
-realtests: $(TESTS_EXECS)
+
+realtests: $(TESTS_EXECS_C) $(TESTS_EXECS_CPP)
 # No longer automatically copying to the FS dir (deprecated)
 #      @mkdir -p fs/$(TARGET_ARCH)/tests
 #      cp -R $(OBJDIR)/$(TESTS_DIR)/* $(TOP_DIR)/fs/$(TARGET_ARCH)/tests
index b5bc512..1dd07c4 100644 (file)
@@ -3,6 +3,7 @@
 # To enable any of these options, add a line like the following to your Makelocal
 # CFLAGS += $(CONFIG_APPSERVER)
 CONFIG_APPSERVER:=                 -D__CONFIG_APPSERVER__
+CONFIG_DEMO_SLAVE:=                -D__CONFIG_DEMO_SLAVE__
 CONFIG_ARSC_SERVER:=               -D__CONFIG_ARSC_SERVER__
 
 # Kernel configuration parameters
@@ -11,13 +12,13 @@ CONFIG_ARSC_SERVER:=               -D__CONFIG_ARSC_SERVER__
 # KERN_CFLAGS += $(CONFIG_KFS) $(CONFIG_BSD_ON_CORE0)
 CONFIG_KFS:=                       -D__CONFIG_KFS__
 CONFIG_EXT2FS:=                    -D__CONFIG_EXT2FS__
-CONFIG_DEDICATED_MONITOR:=         -D__CONFIG_DEDICATED_MONITOR__
 CONFIG_SINGLE_CORE:=               -D__CONFIG_SINGLE_CORE__
 CONFIG_NETWORKING:=                -D__CONFIG_NETWORKING__
 CONFIG_SERIAL_IO:=                 -D__CONFIG_SERIAL_IO__
 CONFIG_BSD_ON_CORE0:=              -D__CONFIG_BSD_ON_CORE0__
 CONFIG_SEQLOCK_DEBUG:=             -D__CONFIG_SEQLOCK_DEBUG__
 CONFIG_SPINLOCK_DEBUG:=            -D__CONFIG_SPINLOCK_DEBUG__
+CONFIG_SPINPDR_NO_CAS:=            -D__CONFIG_SPINPDR_NO_CAS__
 CONFIG_PAGE_COLORING:=             -D__CONFIG_PAGE_COLORING__
 CONFIG_DEMAND_PAGING:=             -D__CONFIG_DEMAND_PAGING__
 CONFIG_NOMTRRS:=                   -D__CONFIG_NOMTRRS__
@@ -33,7 +34,8 @@ CONFIG_PCI_VERBOSE:=               -D__CONFIG_PCI_VERBOSE__
 CONFIG_ETH_AUDIO:=                 -D__CONFIG_ETH_AUDIO__
 CONFIG_KB_CORE0_ONLY:=             -D__CONFIG_KB_CORE0_ONLY__
 CONFIG_KTHREAD_POISON:=            -D__CONFIG_KTHREAD_POISON__
-CONFIG_SOCKET:=                    -D__CONFIG_SOCKET__                                                                         
+CONFIG_PRINTK_NO_BACKSPACE:=       -D__CONFIG_PRINTK_NO_BACKSPACE__
+CONFIG_SOCKET:=                    -D__CONFIG_SOCKET__
 
 # Userspace configuration parameters
 # By default, each of these options will be turned off
index a676a17..81ea586 100644 (file)
@@ -1,10 +1,10 @@
 # General Purpose configuration parameters
 #CFLAGS += $(CONFIG_APPSERVER)
+#CFLAGS += $(CONFIG_DEMO_SLAVE)
 
 # Kernel configuration parameters
-#KERN_CFLAGS += $(CONFIG_KFS)
+KERN_CFLAGS += $(CONFIG_KFS)
 #KERN_CFLAGS += $(CONFIG_EXT2FS)
-#KERN_CFLAGS += $(CONFIG_DEDICATED_MONITOR)
 #KERN_CFLAGS += $(CONFIG_SINGLE_CORE)
 #KERN_CFLAGS += $(CONFIG_NETWORKING)
 #KERN_CFLAGS += $(CONFIG_SERIAL_IO)
@@ -12,6 +12,7 @@
 # Enabling this can cause userspace to make the kernel panic.
 #KERN_CFLAGS += $(CONFIG_SEQLOCK_DEBUG)
 #KERN_CFLAGS += $(CONFIG_SPINLOCK_DEBUG)
+#KERN_CFLAGS += $(CONFIG_SPINPDR_NO_CAS)
 #KERN_CFLAGS += $(CONFIG_PAGE_COLORING)
 #KERN_CFLAGS += $(CONFIG_DEMAND_PAGING)
 #KERN_CFLAGS += $(CONFIG_NOMTRRS)
@@ -32,6 +33,7 @@
 # Avoid KB input on buggy nehalems (brho's machine)
 #KERN_CFLAGS += $(CONFIG_KB_CORE0_ONLY)
 #KERN_CFLAGS += $(CONFIG_KTHREAD_POISON)
+#KERN_CFLAGS += $(CONFIG_PRINTK_NO_BACKSPACE)
 
 #KERN_CFLAGS += -DDEVELOPER_NAME=waterman
 #KERN_CFLAGS += -DDEVELOPER_NAME=brho
@@ -39,6 +41,7 @@
 
 # Paths for the initramfs (need to be directories)
 #INITRAMFS_PATHS = kern/kfs obj/tests
+INITRAMFS_PATHS = kern/kfs
 # Program to execute before building the initramfs
 #INITRAMFS_BIN = tools/whatever.sh
 # Image for ext2 (RAM version) (only brho uses this )
 # User tests configuration parameters
 #TESTS_CFLAGS += $(CONFIG_STATIC_APPS)
 
+# Number of jobs in make
+#MAKE_JOBS := 4
+#
 # Default for sparc (i.e. needs an appserver)
 ifeq ($(TARGET_ARCH),sparc)
 KERN_CFLAGS += $(CONFIG_APPSERVER)
 KERN_CFLAGS += -DDEVELOPER_NAME=waterman
 endif
 
+# brho's (edited) KVM, USB, PXE, ETC make targets
+#kvm: $(OBJDIR)/kern/kernel
+#      $(V)echo "+ (KVM) Copying to mnt/hdd"
+#      $(V)cp $(OBJDIR)/kern/kernel mnt/hdd/kernel
+#      $(V)sync
+#endif
+#
+#usb: $(OBJDIR)/kern/kernel
+#      $(V)echo "+ (USB) Copying to /dev/sdc4"
+#      $(V)mount /dev/sdc4
+#      $(V)cp $(OBJDIR)/kern/kernel /mnt/usbstick/kernel
+#      $(V)sync
+#      $(V)umount /mnt/usbstick
+#
+#pxe: $(OBJDIR)/kern/kernel
+#      $(V)echo "+ (PXE) Compressing..."
+#      $(V)gzip -c $(OBJDIR)/kern/kernel > $(OBJDIR)/kern/akaros-kernel.gz
+#      $(V)echo "+ (PXE) Copying to Watson"
+#      $(V)scp $(OBJDIR)/kern/akaros-kernel.gz watson.millennium.berkeley.edu:/tftpboot/akaros/akaros-kernel.gz
+
 x86:
        $(MAKE) TARGET_ARCH=i686
 
index 41cbe7e..7a6b35d 100644 (file)
@@ -36,5 +36,6 @@ KERN_ARCH_SRCFILES := $(KERN_ARCH_SRC_DIR)/entry.S \
                       $(KERN_ARCH_SRC_DIR)/init.c \
                       $(KERN_ARCH_SRC_DIR)/env.c \
                       $(KERN_ARCH_SRC_DIR)/frontend.c \
+                      $(KERN_ARCH_SRC_DIR)/rdtsc_test.c \
                       $(KERN_ARCH_SRC_DIR)/perfmon.c
 
index 5c4aa2b..7a6267e 100644 (file)
 #include <time.h>
 #include <assert.h>
 #include <stdio.h>
+#include <bitmask.h>
 
 system_timing_t RO system_timing = {0, 0, 0xffff, 0};
 
-/*
- * Remaps the Programmable Interrupt Controller to use IRQs 32-47
+/* * Remaps the Programmable Interrupt Controller to use IRQs 32-47
  * http://wiki.osdev.org/PIC
- * Not 100% on this stuff, after looking over 
- * http://bochs.sourceforge.net/techspec/PORTS.LST  The cascading and other 
- * stuff might need to be in one command, and after that all we are doing
- * is toggling masks.
- */
+ * Check osdev for a more thorough explanation/implementation.
+ * http://bochs.sourceforge.net/techspec/PORTS.LST  */
 void pic_remap() 
 {
-       // start initialization
+       /* start initialization (ICW1) */
        outb(PIC1_CMD, 0x11);
        outb(PIC2_CMD, 0x11);
-       // set new offsets
+       /* set new offsets (ICW2) */
        outb(PIC1_DATA, PIC1_OFFSET);
        outb(PIC2_DATA, PIC2_OFFSET);
-       // set up cascading
+       /* set up cascading (ICW3) */
        outb(PIC1_DATA, 0x04);
        outb(PIC2_DATA, 0x02);
-       // other stuff (put in 8086/88 mode, or whatever)
+       /* other stuff (put in 8086/88 mode, or whatever) (ICW4) */
        outb(PIC1_DATA, 0x01);
        outb(PIC2_DATA, 0x01);
-       // set masks, defaulting to all masked for now
+       /* Init done, further data R/W access the interrupt mask */
+       /* set masks, defaulting to all masked for now */
        outb(PIC1_DATA, 0xff);
        outb(PIC2_DATA, 0xff);
 }
@@ -63,6 +61,79 @@ void pic_unmask_irq(uint8_t irq)
                outb(PIC1_DATA, inb(PIC1_DATA) & ~(1 << irq));
 }
 
+/* Aka, the IMR.  Simply reading the data port are OCW1s. */
+uint16_t pic_get_mask(void)
+{
+       return (inb(PIC2_DATA) << 8) | inb(PIC1_DATA);
+}
+
+static uint16_t __pic_get_irq_reg(int ocw3)
+{
+       /* OCW3 to PIC CMD to get the register values.  PIC2 is chained, and
+        * represents IRQs 8-15.  PIC1 is IRQs 0-7, with 2 being the chain */
+       outb(PIC1_CMD, ocw3);
+       outb(PIC2_CMD, ocw3);
+       return (inb(PIC2_CMD) << 8) | inb(PIC1_CMD);
+}
+
+/* Returns the combined value of the cascaded PICs irq request register */
+uint16_t pic_get_irr(void)
+{
+       return __pic_get_irq_reg(PIC_READ_IRR);
+}
+
+/* Returns the combined value of the cascaded PICs irq service register */
+uint16_t pic_get_isr(void)
+{
+       return __pic_get_irq_reg(PIC_READ_ISR);
+}
+
+/* Debugging helper.  Note the ISR/IRR are 32 bits at a time, spaced every 16
+ * bytes in the LAPIC address space. */
+void lapic_print_isr(void)
+{
+       printk("LAPIC ISR on core %d\n--------------\n", core_id());
+       for (int i = 7; i >= 0; i--)
+               printk("%3d-%3d: %08p\n", (i + 1) * 32 - 1, i * 32,
+                      *(uint32_t*)(LAPIC_ISR + i * 0x10));
+       printk("LAPIC IRR on core %d\n--------------\n", core_id());
+       for (int i = 7; i >= 0; i--)
+               printk("%3d-%3d: %08p\n", (i + 1) * 32 - 1, i * 32,
+                      *(uint32_t*)(LAPIC_IRR + i * 0x10));
+}
+
+/* Returns TRUE if the bit 'vector' is set in the LAPIC ISR or IRR (whatever you
+ * pass in.  These registers consist of 8, 32 byte registers spaced every 16
+ * bytes from the base in the LAPIC. */
+static bool __lapic_get_isrr_bit(uint32_t base, uint8_t vector)
+{
+       int which_reg = vector >> 5;    /* 32 bits per reg */
+       uint32_t *lapic_reg = (uint32_t*)(base + which_reg * 0x10);     /* offset 16 */
+       return (*lapic_reg & (1 << (vector % 32)) ? 1 : 0);
+}
+
+bool lapic_get_isr_bit(uint8_t vector)
+{
+       return __lapic_get_isrr_bit(LAPIC_ISR, vector);
+}
+
+bool lapic_get_irr_bit(uint8_t vector)
+{
+       return __lapic_get_isrr_bit(LAPIC_IRR, vector);
+}
+
+/* This works for any interrupt that goes through the LAPIC, but not things like
+ * ExtInts.  To prevent abuse, we'll use it just for IPIs for now (which only
+ * come via the APIC).
+ *
+ * Note that if you call this from an interrupt handler for 'vector' before you
+ * EOI, the ISR will show your bit as set.  It is the EOI that clears the bit
+ * from the ISR. */
+bool ipi_is_pending(uint8_t vector)
+{
+       return lapic_get_isr_bit(vector) || lapic_get_isr_bit(vector);
+}
+
 /*
  * Sets the LAPIC timer to go off after a certain number of ticks.  The primary
  * clock freq is actually the bus clock, which we figure out during timer_init
@@ -84,11 +155,17 @@ void __lapic_set_timer(uint32_t ticks, uint8_t vec, bool periodic, uint8_t div)
 
 void lapic_set_timer(uint32_t usec, bool periodic)
 {
-       // divide the bus clock by 128, which is the max.
-       uint32_t ticks = (usec * system_timing.bus_freq / 128) / 1000000;
-       assert(ticks > 0);
-       __lapic_set_timer(ticks, LAPIC_TIMER_DEFAULT_VECTOR, periodic,
-                         LAPIC_TIMER_DEFAULT_DIVISOR);
+       /* If we overflowed a uint32, send in the max timer possible.  The lapic can
+        * only handle a 32 bit.  We could muck with changing the divisor, but even
+        * then, we might not be able to match 4000 sec (based on the bus speed).
+        * The kernel alarm code can handle spurious timer interrupts, so we just
+        * set the timer for as close as we can get to the desired time. */
+       uint64_t ticks64 = (usec * system_timing.bus_freq) / LAPIC_TIMER_DIVISOR_VAL
+                           / 1000000;
+       uint32_t ticks32 = ((ticks64 >> 32) ? 0xffffffff : ticks64);
+       assert(ticks32 > 0);
+       __lapic_set_timer(ticks32, LAPIC_TIMER_DEFAULT_VECTOR, periodic,
+                         LAPIC_TIMER_DIVISOR_BITS);
 }
 
 void set_core_timer(uint32_t usec, bool periodic)
@@ -117,18 +194,20 @@ void timer_init(void){
        udelay_pit(1000000);
        tscval[1] = read_tsc();
        system_timing.tsc_freq = SINIT(tscval[1] - tscval[0]);
-       
        cprintf("TSC Frequency: %llu\n", system_timing.tsc_freq);
-
        __lapic_set_timer(0xffffffff, LAPIC_TIMER_DEFAULT_VECTOR, FALSE,
-                         LAPIC_TIMER_DEFAULT_DIVISOR);
+                         LAPIC_TIMER_DIVISOR_BITS);
        // Mask the LAPIC Timer, so we never receive this interrupt (minor race)
        mask_lapic_lvt(LAPIC_LVT_TIMER);
        timercount[0] = read_mmreg32(LAPIC_TIMER_CURRENT);
        udelay_pit(1000000);
        timercount[1] = read_mmreg32(LAPIC_TIMER_CURRENT);
-       system_timing.bus_freq = SINIT((timercount[0] - timercount[1])*128);
-               
+       system_timing.bus_freq = (timercount[0] - timercount[1])
+                                * LAPIC_TIMER_DIVISOR_VAL;
+       /* The time base for the timer is derived from the processor's bus clock,
+        * divided by the value specified in the divide configuration register.
+        * Note we mult and div by the divisor, saving the actual freq (even though
+        * we don't use it yet). */
        cprintf("Bus Frequency: %llu\n", system_timing.bus_freq);
 }
 
@@ -232,4 +311,3 @@ uint64_t getfreq(void)
 {
        return system_timing.tsc_freq;
 }
-
index b1d5bad..47dec11 100644 (file)
 #include <arch/x86.h>
 #include <arch/ioapic.h>
 
-// PIC
+/* PIC (8259A)
+ * When looking at the specs, A0 is our CMD line, and A1 is the DATA line.  This
+ * means that blindly writing to PIC1_DATA is an OCW1 (interrupt masks).  When
+ * writing to CMD (A0), the chip can determine betweeb OCW2 and OCW3 by the
+ * setting of a few specific bits (OCW2 has bit 3 unset, OCW3 has it set). */
 #define PIC1_CMD                                       0x20
 #define PIC1_DATA                                      0x21
 #define PIC2_CMD                                       0xA0
 // These are also hardcoded into the IRQ_HANDLERs of kern/trapentry.S
 #define PIC1_OFFSET                                    0x20
 #define PIC2_OFFSET                                    0x28
-#define PIC_EOI                                                0x20
+#define PIC1_SPURIOUS                          (7 + PIC1_OFFSET)
+#define PIC2_SPURIOUS                          (7 + PIC2_OFFSET)
+#define PIC_EOI                                                0x20    /* OCW2 EOI */
+/* These set the next CMD read to return specific values.  Note that the chip
+ * remembers what setting we had before (IRR or ISR), if you do other reads of
+ * CMD. (not tested, written in the spec sheet) */
+#define PIC_READ_IRR                           0x0a    /* OCW3 irq ready next CMD read */
+#define PIC_READ_ISR                           0x0b    /* OCW3 irq service next CMD read */
 
 // Local APIC
 /* PBASE is the physical address.  It is mapped in at the VADDR LAPIC_BASE */
 #define LAPIC_TIMER_CURRENT                    (LAPIC_BASE + 0x390)
 #define LAPIC_TIMER_DIVIDE                     (LAPIC_BASE + 0x3e0)
 #define LAPIC_TIMER_DEFAULT_VECTOR     0xeb            /* Aka 235, IRQ203 */
-#define LAPIC_TIMER_DEFAULT_DIVISOR    0xa // This is 128.  Ref SDM 3.a 9.6.4
+/* Quick note on the divisor.  The LAPIC timer ticks once per divisor-bus ticks
+ * (system bus or APIC bus, depending on the model).  Ex: A divisor of 128 means
+ * 128 bus ticks results in 1 timer tick.  The divisor increases the time range
+ * and decreases the granularity of the timer.  Numbers are appx, based on 4
+ * billion ticks, vs 2^32 ticks.
+ * Ex:   1GHz bus, div 001:    4sec max,    1ns granularity
+ * Ex:   1GHz bus, div 128:  512sec max,  128ns granularity
+ * Ex: 100MHz bus, div 001:   40sec max,   10ns granularity
+ * Ex: 100MHz bus, div 128: 5120sec max, 1280ns granularity */
+#define LAPIC_TIMER_DIVISOR_VAL                32      /* seems reasonable */
+#define LAPIC_TIMER_DIVISOR_BITS       0x8     /* Div = 32 */
+
 // IPI Interrupt Command Register
 #define LAPIC_IPI_ICR_LOWER                    (LAPIC_BASE + 0x300)
 #define LAPIC_IPI_ICR_UPPER                    (LAPIC_BASE + 0x310)
-// Interrupts being serviced (in-service) and pending (interrupt request reg)
-#define LAPIC_ISR                                      (LAPIC_BASE + 0x170)
-#define LAPIC_IRR                                      (LAPIC_BASE + 0x310)
+/* Interrupts being serviced (in-service) and pending (interrupt request reg).
+ * Note these registers are not normal bitmaps, but instead are 8 separate
+ * 32-bit registers, spaced/aligned on 16 byte boundaries in the LAPIC address
+ * space. */
+#define LAPIC_ISR                                      (LAPIC_BASE + 0x100)
+#define LAPIC_IRR                                      (LAPIC_BASE + 0x200)
 
 // PIT (Programmable Interval Timer)
 #define        TIMER_REG_CNTR0 0       /* timer 0 counter port */
 typedef struct system_timing {
        uint64_t tsc_freq;
        uint64_t bus_freq;
+       uint64_t timing_overhead;
        uint16_t pit_divisor;
        uint8_t pit_mode;
 } system_timing_t;
@@ -96,6 +122,13 @@ extern system_timing_t system_timing;
 void pic_remap(void);
 void pic_mask_irq(uint8_t irq);
 void pic_unmask_irq(uint8_t irq);
+uint16_t pic_get_mask(void);
+uint16_t pic_get_irr(void);
+uint16_t pic_get_isr(void);
+bool lapic_get_isr_bit(uint8_t vector);
+bool lapic_get_irr_bit(uint8_t vector);
+void lapic_print_isr(void);
+bool ipi_is_pending(uint8_t vector);
 void __lapic_set_timer(uint32_t ticks, uint8_t vec, bool periodic, uint8_t div);
 void lapic_set_timer(uint32_t usec, bool periodic);
 uint32_t lapic_get_default_id(void);
@@ -124,10 +157,9 @@ static inline void send_startup_ipi(uint8_t vector);
 static inline void send_self_ipi(uint8_t vector);
 static inline void send_broadcast_ipi(uint8_t vector);
 static inline void send_all_others_ipi(uint8_t vector);
-static inline void send_ipi(uint8_t hw_coreid, uint8_t vector);
+static inline void __send_ipi(uint8_t hw_coreid, uint8_t vector);
 static inline void send_group_ipi(uint8_t hw_groupid, uint8_t vector);
-static inline void __send_nmi(uint8_t os_coreid);
-static inline bool ipi_is_pending(uint8_t vector);
+static inline void __send_nmi(uint8_t hw_coreid);
 
 #define mask_lapic_lvt(entry) \
        write_mmreg32(entry, read_mmreg32(entry) | LAPIC_LVT_MASK)
@@ -243,16 +275,6 @@ static inline void __send_ipi(uint8_t hw_coreid, uint8_t vector)
        lapic_wait_to_send();
 }
 
-static inline void send_ipi(uint8_t hw_coreid, uint8_t vector)
-{
-       /* 255 is a broadcast, which should use send_broadcast_ipi, and it is also
-        * what would come in if you tried sending an IPI to an os_coreid that
-        * doesn't exist (since they are initialized to -1). */
-       if (hw_coreid == 255)
-               return;
-       __send_ipi(hw_coreid, vector);
-}
-
 static inline void send_group_ipi(uint8_t hw_groupid, uint8_t vector)
 {
        write_mmreg32(LAPIC_IPI_ICR_UPPER, hw_groupid << 24);
@@ -269,13 +291,6 @@ static inline void __send_nmi(uint8_t hw_coreid)
        lapic_wait_to_send();
 }
 
-/* This works for any interrupt that goes through the LAPIC, but not things like
- * ExtInts.  To prevent abuse, we'll use it just for IPIs for now. */
-static inline bool ipi_is_pending(uint8_t vector)
-{
-       return (LAPIC_ISR & vector) || (LAPIC_IRR & vector);
-}
-
 /* To change the LAPIC Base (not recommended):
        msr_val = read_msr(IA32_APIC_BASE);
        msr_val = msr_val & ~MSR_APIC_BASE_ADDRESS | 0xfaa00000;
index 335fca2..99efed8 100644 (file)
@@ -8,7 +8,7 @@
 #include <arch/apic.h>
 
 /* Arch Constants */
-#define HW_CACHE_ALIGN                          64
+#define ARCH_CL_SIZE                            64
 /* Top of the kernel virtual mapping area (KERNBASE) */
 /* For sanity reasons, I don't plan to map the top page */
 #define KERN_VMAP_TOP                          0xfffff000
@@ -27,13 +27,16 @@ static __inline void cpu_relax(void) __attribute__((always_inline));
 static __inline void cpu_halt(void) __attribute__((always_inline));
 static __inline void clflush(uintptr_t* addr) __attribute__((always_inline));
 static __inline int irq_is_enabled(void) __attribute__((always_inline));
-static __inline int get_hw_coreid(int coreid);
+static __inline int get_hw_coreid(uint32_t coreid);
 static __inline int hw_core_id(void) __attribute__((always_inline));
 static __inline int get_os_coreid(int hw_coreid);
 static __inline int core_id(void) __attribute__((always_inline));
 static __inline void cache_flush(void) __attribute__((always_inline));
 static __inline void reboot(void) __attribute__((always_inline)) __attribute__((noreturn));
 
+/* in trap.c */
+void send_ipi(uint32_t os_coreid, uint8_t vector);
+/* in cpuinfo.c */
 void print_cpuinfo(void);
 void show_mapping(uintptr_t start, size_t size);
 
@@ -75,13 +78,21 @@ read_tsc(void)
        return tsc;
 }
 
+/* non-core-id reporting style (it is in ecx) */
+static __inline uint64_t
+read_tscp(void)
+{
+       uint64_t tsc;
+       __asm __volatile("rdtscp" : "=A" (tsc) : : "ecx");
+       return tsc;
+}
+
+/* Check out k/a/i686/rdtsc_test.c for more info */
 static __inline uint64_t 
 read_tsc_serialized(void)
 {
-    uint64_t tsc;
-       cpuid(0x0, 0x0, 0, 0, 0, 0);
-       tsc = read_tsc();
-       return tsc;
+       asm volatile("lfence"); /* mfence on amd */
+       return read_tsc();
 }
 
 static __inline void
@@ -153,7 +164,7 @@ irq_is_enabled(void)
 
 /* os_coreid -> hw_coreid */
 static __inline int
-get_hw_coreid(int coreid)
+get_hw_coreid(uint32_t coreid)
 {
        return hw_coreid_lookup[coreid];
 }
index db50465..839cb3e 100644 (file)
@@ -144,7 +144,7 @@ static inline bool spin_locked(spinlock_t *lock)
        return lock->rlock & 0xff;
 }
 
-static inline void __spin_lock(volatile uint32_t *rlock)
+static inline void __spin_lock_raw(volatile uint32_t *rlock)
 {
        asm volatile(
                        "1:                       "
@@ -158,39 +158,25 @@ static inline void __spin_lock(volatile uint32_t *rlock)
                        "       cmpb $0, %%al;        "
                        "       jne 1b;               "
                : : "m"(*rlock) : "eax", "cc");
+       cmb();  /* need cmb(), the CPU mb() was handled by the xchg */
 }
 
-static inline void spin_lock(spinlock_t *lock)
+static inline void __spin_lock(spinlock_t *lock)
 {
-       __spin_lock(&lock->rlock);
-#ifdef __CONFIG_SPINLOCK_DEBUG__
-       lock->call_site = (void RACY*CT(1))TC(read_eip());
-       lock->calling_core = core_id();
-#endif
-       cmb();  /* need cmb(), the CPU mb() was handled by the xchgb */
+       __spin_lock_raw(&lock->rlock);
 }
 
-static inline void spin_unlock(spinlock_t *lock)
+static inline void __spin_unlock(spinlock_t *lock)
 {
-       /* Need to prevent the compiler (and some arches) from reordering older
-        * stores. */
+       /* Need to prevent the compiler from reordering older stores. */
        wmb();
        rwmb(); /* x86 makes both of these a cmb() */
        lock->rlock = 0;
 }
 
-static inline void spinlock_init(spinlock_t *lock)
-#ifdef __CONFIG_SPINLOCK_DEBUG__
-WRITES(lock->rlock,lock->call_site,lock->calling_core)
-#else
-WRITES(lock->rlock)
-#endif
+static inline void __spinlock_init(spinlock_t *lock)
 {
        lock->rlock = 0;
-#ifdef __CONFIG_SPINLOCK_DEBUG__
-       lock->call_site = 0;
-       lock->calling_core = 0;
-#endif
 }
 
 #endif /* ROS_KERN_ARCH_ATOMIC_H */
index a192a60..b8b2abc 100644 (file)
@@ -8,16 +8,16 @@
 #include <string.h>
 #include <assert.h>
 #include <stdio.h>
+#include <sys/queue.h>
 
 #include <ros/memlayout.h>
 
-void cons_intr(int (*proc)(void));
-void scroll_screen(void);
-
-
 /***** Serial I/O code *****/
 
-#define COM1           0x3F8
+#define COM1                   0x3F8   /* irq 4 */
+#define COM2                   0x2F8   /* irq 3 */
+#define COM3                   0x3E8   /* irq 4 */
+#define COM4                   0x2E8   /* irq 3 */
 
 #define        COM_RX                  0               // In:  Receive buffer (DLAB=0)
 #define COM_DLL                        0               // Out: Divisor Latch Low (DLAB=1)
@@ -33,91 +33,174 @@ void scroll_screen(void);
 #define        COM_MCR_RTS             0x02    // RTS complement
 #define        COM_MCR_DTR             0x01    // DTR complement
 #define        COM_MCR_OUT2    0x08    // Out2 complement
+#define        COM_MCR_GLB_IRQ 0x08    /* global irq controlled via MCR */
 #define COM_LSR                        5               // In:  Line Status Register
 #define COM_LSR_DATA   0x01    //   Data available
 #define COM_LSR_READY  0x20    //   Ready to send
+#define COM_SCRATCH            7               /* Scratch register */
 
-static bool SREADONLY serial_exists;
+/* List of all initialized console devices */
+struct cons_dev_slist cdev_list = SLIST_HEAD_INITIALIZER(cdev_list);
+/* need to statically allocate these, since cons_init is called so damn early */
+struct cons_dev com1, com2, com3, com4, kb;
 
-int
-serial_proc_data(void)
+static int __serial_get_char(int com, uint8_t *data)
 {
-       if (!(inb(COM1+COM_LSR) & COM_LSR_DATA))
+       if (!(inb(com + COM_LSR) & COM_LSR_DATA))
                return -1;
-       return inb(COM1+COM_RX);
+       *data = inb(com + COM_RX);
+       return 0;
 }
 
-int serial_read_byte()
+static int serial_get_char(struct cons_dev *cdev, uint8_t *data)
 {
-       return serial_proc_data();
+       return __serial_get_char(cdev->val, data);
 }
 
-void
-serial_intr(void)
+static void __serial_put_char(int com, uint8_t c)
 {
-       if (serial_exists)
-               cons_intr(serial_proc_data);
+       while (!(inb(com + COM_LSR) & COM_LSR_READY))
+               cpu_relax();
+       outb(com, c);
 }
 
-void
-serial_init(void)
+/* Writes c (or some variant of) to the serial cdev */
+static void serial_put_char(struct cons_dev *cdev, uint8_t c)
 {
-       // Turn off the FIFO
-       outb(COM1+COM_FCR, 0);
-       
-       // Set speed; requires DLAB latch
-       outb(COM1+COM_LCR, COM_LCR_DLAB);
-       // Setting speed to 115200 (setting the divider to 1)
-       outb(COM1+COM_DLL, 1);
-       outb(COM1+COM_DLM, 0);
-
-       // 8 data bits, 1 stop bit, parity off; turn off DLAB latch
-       outb(COM1+COM_LCR, COM_LCR_WLEN8 & ~COM_LCR_DLAB);
-
-       // This should turn on hardware flow control
-       outb(COM1+COM_MCR, COM_MCR_RTS | COM_MCR_DTR);
-       // Enable rcv interrupts
-       outb(COM1+COM_IER, COM_IER_RDI);
-
-       // Clear any preexisting overrun indications and interrupts
-       // Serial port doesn't exist if COM_LSR returns 0xFF
-       {
-               bool lbool = ((inb(COM1+COM_LSR) != 0xFF));
-               serial_exists = SINIT(lbool);
+       assert(cdev->type == CONS_SER_DEV);
+       /* We do some funky editing of a few chars, to suit what minicom seems to
+        * expect (at least for brho). */
+       switch (c & 0xff) {
+               case '\b':
+               case 0x7f:
+               #ifdef __CONFIG_PRINTK_NO_BACKSPACE__
+                       __serial_put_char(cdev->val, (uint8_t)('^'));
+                       __serial_put_char(cdev->val, (uint8_t)('H'));
+               #else
+                       __serial_put_char(cdev->val, '\b');
+                       __serial_put_char(cdev->val, (uint8_t)(' '));
+                       __serial_put_char(cdev->val, '\b');
+               #endif /* __CONFIG_PRINTK_NO_BACKSPACE__ */
+                       break;
+               case '\n':
+               case '\r':
+                       __serial_put_char(cdev->val, (uint8_t)('\n'));
+                       __serial_put_char(cdev->val, (uint8_t)('\r'));
+                       break;
+               default:
+                       __serial_put_char(cdev->val, (uint8_t)(c & 0xff));
+                       break;
        }
-       (void) inb(COM1+COM_IIR);
-       (void) inb(COM1+COM_RX);
-
 }
 
-void serial_send_byte(uint8_t b)
+/* Writes c to every initialized serial port */
+static void serial_spam_char(int c)
 {
-       while (!(inb(COM1+COM_LSR) & COM_LSR_READY));
-       outb(COM1, b);
+       struct cons_dev *i;
+       SLIST_FOREACH(i, &cdev_list, next) {
+               if (i->type == CONS_SER_DEV)
+                       serial_put_char(i, c);
+       }
 }
 
-static void
-serial_putc(int c)
+/* http://en.wikibooks.org/wiki/Serial_Programming/8250_UART_Programming \
+ * #Software_Identification_of_the_UART
+ *
+ * We return 0 for unknown (probably not there), and the char * o/w */
+static char *__serial_detect_type(int com)
 {
-       switch (c & 0xff) {
-       case '\b':
-               serial_send_byte('\b');
-               serial_send_byte((uint8_t)(' '));
-               serial_send_byte('\b');
-               break;
-       case '\n':
-       case '\r':
-               serial_send_byte((uint8_t)('\n'));
-               serial_send_byte((uint8_t)('\r'));
-               break;
-       default:
-               serial_send_byte((uint8_t)(c & 0xff));
-               break;
+       uint8_t val;
+       char *model = 0;
+       /* First, check that the port actually exists.  I haven't seen any
+        * documentation of the LSR 0xff check, but it seems to work on qemu and
+        * hardware (brho's nehalem).  Perhaps 0xff is the default state for
+        * 'unmapped' ports. */
+       /* Serial port doesn't exist if COM_LSR returns 0xff */
+       if (inb(com + COM_LSR) == 0xff)
+               return model;
+       /* Try to set FIFO, then based on the bits enabled, we can tell what model
+        * it is */
+       outb(com + COM_FCR, 0xe7);
+       val = inb(com + COM_IIR);
+       if (val & (1 << 6)) {
+               if (val & (1 << 7)) {
+                       if (val & (1 << 5))
+                               model = "UART 16750";
+                       else
+                               model = "UART 16550A";
+               } else {
+                       model = "UART 16550";
+               }
+       } else {
+               /* no FIFO at all.  the 8250 had a buggy scratch register. */
+               outb(com + COM_SCRATCH, 0x2a);
+               val = inb(com + COM_SCRATCH);
+               if (val == 0x2a)
+                       model = "UART 16450";
+               else
+                       model = "UART 8250";
        }
-       return;
+       return model;
 }
 
+/* Helper: attempts to initialize the serial device cdev with COM com.  If it
+ * succeeds, the cdev will be on the cdev_list. */ 
+static void serial_com_init(struct cons_dev *cdev, int com)
+{
+       cdev->model = __serial_detect_type(com);
+       /* Bail if detection failed */
+       if (!cdev->model)
+               return;
+       /* Set up the struct */
+       cdev->type = CONS_SER_DEV;
+       cdev->val = com;
+       switch (com) {
+               case (COM1):
+               case (COM3):
+                       cdev->irq = 4;
+                       break;
+               case (COM2):
+               case (COM4):
+                       cdev->irq = 3;
+                       break;
+               default:
+                       /* not that printing is the safest thing right now... */
+                       panic("Unknown COM %d", com);
+       }
+       cdev->getc = serial_get_char;
+       /* Turn off the FIFO (not sure this is needed) */
+       outb(com + COM_FCR, 0);
+       /* Set speed; requires DLAB latch */
+       outb(com + COM_LCR, COM_LCR_DLAB);
+       /* Setting speed to 115200 (setting the divider to 1) */
+       outb(com + COM_DLL, 1);
+       outb(com + COM_DLM, 0);
+       /* 8 data bits, 1 stop bit, parity off; turn off DLAB latch */
+       outb(com + COM_LCR, COM_LCR_WLEN8 & ~COM_LCR_DLAB);
+       /* This should turn on hardware flow control and make sure the global irq
+        * bit is on.  This bit is definitely used some hardware's 16550As, though
+        * not for qemu.  Also, on both qemu and hardware, this whole line is a
+        * noop, since the COM_MCR is already 0x0b, so we're just making sure the
+        * three bits are still turned on (and leaving other bits unchanged) */
+       outb(com + COM_MCR, inb(com + COM_MCR) | COM_MCR_RTS | COM_MCR_DTR |
+                                                COM_MCR_GLB_IRQ);
+       /* Enable rx interrupts */
+       outb(com + COM_IER, COM_IER_RDI);
+       /* Clear any preexisting overrun indications and interrupts */
+       inb(com + COM_IIR);
+       inb(com + COM_RX);
+       /* Put us on the list of initialized cdevs (now that it is init'd) */
+       SLIST_INSERT_HEAD(&cdev_list, cdev, next);
+}
 
+static void serial_init(void)
+{
+       /* attempt to init all four COMs */
+       serial_com_init(&com1, COM1);
+       serial_com_init(&com2, COM2);
+       serial_com_init(&com3, COM3);
+       serial_com_init(&com4, COM4);
+}
 
 /***** Parallel port output code *****/
 // For information on PC parallel port programming, see the class References
@@ -145,14 +228,20 @@ lpt_putc(int c)
        outb(0x378+2, 0x08);
 }
 
+/***** Text-mode CGA/VGA display output with scrolling *****/
+#define MONO_BASE      0x3B4
+#define MONO_BUF       0xB0000
+#define CGA_BASE       0x3D4
+#define CGA_BUF                0xB8000
 
+#define CRT_ROWS       25
+#define CRT_COLS       80
+#define CRT_SIZE       (CRT_ROWS * CRT_COLS)
 
-
-/***** Text-mode CGA/VGA display output with scrolling *****/
 #define MAX_SCROLL_LENGTH      20
 #define SCROLLING_CRT_SIZE     (MAX_SCROLL_LENGTH * CRT_SIZE)
 
-static spinlock_t SRACY lock = SPINLOCK_INITIALIZER;
+static spinlock_t SRACY lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
 static unsigned SREADONLY addr_6845;
 static uint16_t *SLOCKED(&lock) COUNT(CRT_SIZE) crt_buf;
@@ -233,13 +322,18 @@ cga_putc(int c)
 
        switch (c & 0xff) {
        case '\b':
+       case 0x7f:
+       #ifdef __CONFIG_PRINTK_NO_BACKSPACE__
+               cga_putc('^');
+               cga_putc('H');
+       #else
                if (crt_pos > 0) {
                        crt_pos--;
                        scrolling_crt_pos--;
-
                        crt_buf[crt_pos] = (c & ~0xff) | ' ';
                        scrolling_crt_buf[scrolling_crt_pos] = crt_buf[crt_pos];
                }
+       #endif /* __CONFIG_PRINTK_NO_BACKSPACE__ */
                break;
        case '\n':
                crt_pos += CRT_COLS;
@@ -399,6 +493,7 @@ static uint8_t * COUNT(256) (SREADONLY charcode)[4] = {
 static uint32_t SLOCKED(&lock) shift;
 static bool SLOCKED(&lock) crt_scrolled = FALSE;
 
+/* TODO: i'm concerned about the (lack of) locking when scrolling the screen. */
 static int
 kbd_proc_data(void)
 {
@@ -483,105 +578,71 @@ kbd_proc_data(void)
        return c;
 }
 
-void
-kbd_intr(void)
+static int kb_get_char(struct cons_dev *cdev, uint8_t *data)
 {
-       cons_intr(kbd_proc_data);
+       int kb_d;
+       /* kbd_proc_data returns 0 if we should keep asking.  It return -1 when
+        * there is no data, and anything else is a char */
+       while ((kb_d = kbd_proc_data()) == 0)
+               cpu_relax();
+       if (kb_d == -1)
+               return -1;
+       *data = (uint8_t)kb_d;
+       return 0;
 }
 
-void
-kbd_init(void)
+void kbd_init(void)
 {
+       /* init and post the kb cons_dev */
+       kb.type = CONS_KB_DEV;
+       kb.val = 0;
+       kb.irq = 1;             /* default PC keyboard IRQ */
+       kb.model = "PC Keyboard";
+       kb.getc = kb_get_char;
+       SLIST_INSERT_HEAD(&cdev_list, &kb, next);
 }
 
-
-
 /***** General device-independent console code *****/
-// Here we manage the console input buffer,
-// where we stash characters received from the keyboard or serial port
-// whenever the corresponding interrupt occurs.
-
-#define CONSBUFSIZE    512
-struct cons {
-       uint8_t buf[CONSBUFSIZE];
-       uint32_t rpos;
-       uint32_t wpos;
-};
-
-static struct cons SLOCKED(&lock) cons;
 
-// called by device interrupt routines to feed input characters
-// into the circular console input buffer.
-void
-cons_intr(int (*proc)(void))
+/* Initialize the console devices */
+void cons_init(void)
 {
-       int c;
-
-       while ((c = (*proc)()) != -1) {
-               if (c == 0)
-                       continue;
-               spin_lock_irqsave(&lock);
-               cons.buf[cons.wpos++] = c;
-               if (cons.wpos == CONSBUFSIZE)
-                       cons.wpos = 0;
-               spin_unlock_irqsave(&lock);
-       }
+       cga_init();
+       kbd_init();
+       serial_init();
 }
 
-// return the next input character from the console, or 0 if none waiting
-int
-cons_getc(void)
+/* Returns 0 on success, with the char in *data */
+int cons_get_char(struct cons_dev *cdev, uint8_t *data)
 {
-       int c;
-
-       // poll for any pending input characters,
-       // so that this function works even when interrupts are disabled
-       // (e.g., when called from the kernel monitor).
-       #ifndef __CONFIG_SERIAL_IO__
-               serial_intr();
-       #endif
-       kbd_intr();
+       return cdev->getc(cdev, data);
+}
 
-       // grab the next character from the input buffer.
-       spin_lock_irqsave(&lock);
-       if (cons.rpos != cons.wpos) {
-               c = cons.buf[cons.rpos++];
-               if (cons.rpos == CONSBUFSIZE)
-                       cons.rpos = 0;
-               spin_unlock_irqsave(&lock);
-               return c;
+/* Returns any available character, or 0 for none (legacy helper) */
+int cons_get_any_char(void)
+{
+       uint8_t c;
+       struct cons_dev *i;
+       /* First to succeed gets returned */
+       SLIST_FOREACH(i, &cdev_list, next) {
+               if (!cons_get_char(i, &c))
+                       return c;
        }
-       spin_unlock_irqsave(&lock);
        return 0;
 }
 
-// output a character to the console
-void
-cons_putc(int c)
+/* output a character to all console outputs (monitor and all serials) */
+void cons_putc(int c)
 {
-       //static uint32_t lock; zra: moving up for sharC annotations
        spin_lock_irqsave(&lock);
        #ifndef __CONFIG_SERIAL_IO__
-               serial_putc(c);
+               serial_spam_char(c);
        #endif
-       //lpt_putc(c);
+       //lpt_putc(c);  /* very slow on the nehalem */
        cga_putc(c);
        spin_unlock_irqsave(&lock);
 }
 
-// initialize the console devices
-void
-cons_init(void)
-{
-       cga_init();
-       kbd_init();
-       serial_init();
-
-       if (!serial_exists)
-               cprintf("Serial port does not exist!\n");
-}
-
-
 // `High'-level console I/O.  Used by readline and cprintf.
 
 void
@@ -603,7 +664,7 @@ getchar(void)
 {
        int c;
 
-       while ((c = cons_getc()) == 0)
+       while ((c = cons_get_any_char()) == 0)
                /* do nothing */;
        return c;
 }
@@ -614,3 +675,13 @@ iscons(int fdnum)
        // used by readline
        return 1;
 }
+
+/* TODO: remove us (and serial IO) */
+void serial_send_byte(uint8_t b)
+{
+}
+
+int serial_read_byte(void)
+{
+       return -1;
+}
index 205581a..b1e4290 100644 (file)
@@ -1,29 +1,42 @@
-/* See COPYRIGHT for copyright information. */
+/* Copyright (c) 2012 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * x86 Console (keyboard/serial/monitor) interfaces */
 
-#ifndef _CONSOLE_H_
-#define _CONSOLE_H_
-#ifndef ROS_KERNEL
-# error "This is a ROS kernel header; user programs should not #include it"
-#endif
+#ifndef ROS_KERN_ARCH_CONSOLE_H
+#define ROS_KERN_ARCH_CONSOLE_H
 
 #include <ros/common.h>
+#include <sys/queue.h>
 
-#define MONO_BASE      0x3B4
-#define MONO_BUF       0xB0000
-#define CGA_BASE       0x3D4
-#define CGA_BUF                0xB8000
+/* Types of console devices */
+#define CONS_KB_DEV            1
+#define CONS_SER_DEV   2
 
-#define CRT_ROWS       25
-#define CRT_COLS       80
-#define CRT_SIZE       (CRT_ROWS * CRT_COLS)
+struct cons_dev;
+/* Interrupt-driven console input devices */
+struct cons_dev {
+       SLIST_ENTRY(cons_dev)           next;
+       int                                                     type;           /* e.g., CONS_KB_DEV */
+       int                                                     val;            /* e.g., COM1 */
+       int                                                     irq;            /* desired irq */
+       char                                            *model;         /* descriptive string */
+       int (*getc)(struct cons_dev *, uint8_t *);
+};
+SLIST_HEAD(cons_dev_slist, cons_dev);
+extern struct cons_dev_slist cdev_list;
 
 void cons_init(void);
+/* Returns 0 on success, with the char in *data */
+int cons_get_char(struct cons_dev *cdev, uint8_t *data);
+/* Returns any available character, or 0 for none (legacy helper) */
+int cons_get_any_char(void);
+/* Writes c to the monitor and to all CONS_SER_DEV console devices */
 void cons_putc(int c);
-int cons_getc(void);
 
-void kbd_intr(void); // irq 1
-void serial_intr(void); // irq 4
+/* TODO: remove us (and serial IO) */
 void serial_send_byte(uint8_t b);
 int serial_read_byte();
 
-#endif /* _CONSOLE_H_ */
+#endif /* ROS_KERN_ARCH_CONSOLE_H */
index d54bd19..60cddec 100644 (file)
@@ -128,7 +128,20 @@ void print_cpuinfo(void)
                printk("FS/GS Base RD/W supported\n");
        else
                printk("FS/GS Base RD/W not supported\n");
-
+       cpuid(0x80000001, 0x0, &eax, &ebx, &ecx, &edx);
+       if (edx & (1 << 27))
+               printk("RDTSCP supported\n");
+       else
+               printk("RDTSCP not supported: don't trust detailed measurements\n");
+       msr_val = read_msr(IA32_MISC_ENABLE);
+       /* we want this to be not set for cpuid.6h to work. */
+       if (msr_val & (1 << 22))
+               write_msr(IA32_MISC_ENABLE, msr_val & ~(1 << 22));
+       cpuid(0x00000006, 0x0, &eax, 0, 0, 0);
+       if (eax & (1 << 2))
+               printk("Always running APIC detected\n");
+       else
+               printk("Always running APIC *not* detected\n");
 }
 
 void show_mapping(uintptr_t start, size_t size)
index 47d7c28..ff72649 100644 (file)
 #include <arch/ioapic.h>
 #include <arch/console.h>
 #include <arch/perfmon.h>
+#include <arch/init.h>
 #include <console.h>
 
 /* irq handler for the console (kb, serial, etc) */
 static void irq_console(struct trapframe *tf, void *data)
 {
-       int c = cons_getc();
-       if (!c)
+       uint8_t c;
+       struct cons_dev *cdev = (struct cons_dev*)data;
+       assert(cdev);
+       if (cons_get_char(cdev, &c))
                return;
-       /* Do our work in an RKM, instead of interrupt context */
+       /* Do our work in an RKM, instead of interrupt context.  Note the RKM will
+        * cast 'c' to a char. */
        if (c == 'G')
                send_kernel_message(core_id(), __run_mon, 0, 0, 0, KMSG_ROUTINE);
        else
@@ -32,23 +36,21 @@ static void irq_console(struct trapframe *tf, void *data)
 
 static void cons_irq_init(void)
 {
-       register_interrupt_handler(interrupt_handlers, 1 + PIC1_OFFSET, irq_console,
-                                  0);
-       register_interrupt_handler(interrupt_handlers, 3 + PIC1_OFFSET, irq_console,
-                                  0);
-       register_interrupt_handler(interrupt_handlers, 4 + PIC1_OFFSET, irq_console,
-                                  0);
-       /* route kb and both serial interrupts to core 0 */
-#ifdef __CONFIG_ENABLE_MPTABLES__
-       ioapic_route_irq(1, 0);
-       ioapic_route_irq(3, 0);
-       ioapic_route_irq(4, 0);
-#else 
-       pic_unmask_irq(1);      /* keyboard */
-       pic_unmask_irq(3);      /* serial 2 or 4 */
-       pic_unmask_irq(4);      /* serial 1 or 3 */
-       unmask_lapic_lvt(LAPIC_LVT_LINT0);
-#endif /* __CONFIG_ENABLE_MPTABLES__ */
+       struct cons_dev *i;
+       /* Register interrupt handlers for all console devices */
+       SLIST_FOREACH(i, &cdev_list, next) {
+               register_interrupt_handler(interrupt_handlers, i->irq + PIC1_OFFSET,
+                                          irq_console, i);
+               /* Route any console IRQs to core 0 */
+       #ifdef __CONFIG_ENABLE_MPTABLES__
+               ioapic_route_irq(i->irq, 0);
+       #else
+               pic_unmask_irq(i->irq);
+               unmask_lapic_lvt(LAPIC_LVT_LINT0);
+       #endif /* __CONFIG_ENABLE_MPTABLES__ */
+               printd("Registered handler for IRQ %d (ISR %d)\n", i->irq,
+                      i->irq + PIC1_OFFSET);
+       }
 }
 
 void arch_init()
@@ -91,4 +93,5 @@ void arch_init()
 
        perfmon_init();
        cons_irq_init();
+       check_timing_stability();
 }
index 77c4361..57ad0bc 100644 (file)
@@ -4,6 +4,7 @@
 #define ROS_ARCH_INIT_H
 
 void arch_init();
+bool check_timing_stability(void);     /* in rdtsc_test.c */
 
 #endif // !ROS_ARCH_INIT_H
 
index c011640..71f2403 100644 (file)
@@ -32,5 +32,5 @@ char* packet_buffers[MAX_PACKET_BUFFERS];
 uint32_t packet_buffers_sizes[MAX_PACKET_BUFFERS];
 uint32_t packet_buffers_head = 0;
 uint32_t packet_buffers_tail = 0;
-spinlock_t packet_buffers_lock = SPINLOCK_INITIALIZER;
+spinlock_t packet_buffers_lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
index 9d29eaf..6039636 100644 (file)
@@ -15,7 +15,7 @@
 #include <pmap.h>
 #include <kmalloc.h>
 
-spinlock_t colored_page_free_list_lock;
+spinlock_t colored_page_free_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
 page_list_t LCKD(&colored_page_free_list_lock) * CT(llc_cache->num_colors) RO
   colored_page_free_list = NULL;
diff --git a/kern/arch/i686/rdtsc_test.c b/kern/arch/i686/rdtsc_test.c
new file mode 100644 (file)
index 0000000..414d3f7
--- /dev/null
@@ -0,0 +1,761 @@
+/* Barret Rhoden
+ *
+ * Code heavily ported from "How to Benchmark Code Execution Times on Intel(R)
+ * IA-32 and IA-64 Instruction Set Architectures" for linux, except for
+ * check_timing_stability().
+ *
+ * The idea behind this was that the traditional style of using rdtsc was to
+ * call:
+ *                     cpuid;
+ *                     rdtsc;
+ * since rdtsc does no serialization (meaning later instructions can get
+ * executed before it, or vice versa).  While this first cpuid isn't a big deal,
+ * doing this in pairs means reading the end time also measures cpuid.  This is
+ * a problem since cpuid can vary quite a bit.
+ *
+ * If we use rdtscp for the end call, we can put the cpuid after rdtscp, thereby
+ * not including cpuid's overhead (and variability) in our measurement.  That's
+ * where the intel doc ends.  For more info, check out:
+ *             http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/ia-32-ia-64-benchmark-code-execution-paper.pdf
+ *
+ * Note that the Intel SDM says you can serialize rdtsc with lfence, such as:
+ *                     lfence;
+ *                     rdtsc;
+ * Linux uses this (mfence on amd64, lfence on intel).  For more info:
+ *             https://lkml.org/lkml/2008/1/2/353
+ * Note this use of lfence before rdtsc is supposedly serializing any
+ * instruction, not just loads.  Some stranger on the internet suggested that
+ * while lfence only serializes memory (and not arbitrary instructions), in
+ * actual hardware there is no point to reorder non-memory instructions around
+ * rdtsc:
+ *             http://stackoverflow.com/questions/12631856/difference-between-rdtscp-rdtsc-memory-and-cpuid-rdtsc
+ *             (look for janneb's response to questions about his comment)
+ *
+ * Its not clear from what anyone writes as to whether or not you need to
+ * serialize below rdtsc.  Supposedly, you'd need cpuid/lfence on both sides of
+ * rdtsc to prevent reordering in both directions.  Andi Kleen does this in a
+ * few places
+ *             https://lkml.org/lkml/2008/1/7/276
+ * though other places in the kernel suggest it is unnecessary (at least for
+ * loads:
+ *             http://lxr.linux.no/#linux+v3.8.2/arch/x86/kvm/x86.c#L1258
+ * The intel docs don't mention it (otherwise we would be told to use
+ * lfence;rdtsc;lfence).  The howto this file is based off of didn't mention it
+ * either, other than to say rdtscp needs to serialize from below.  AFAIK,
+ * rdtscp is like rdtsc, except that it serializes from above (and also returns
+ * the CPU id).  If rdtscp needs to serialize from below, then so should rdtsc.
+ *
+ * That being said, if these rdtsc(p) calls do not need serialization from
+ * below, then rdtscp (which provides serialization from above) should not need
+ * any additional serialization (lfence or cpuid).
+ *
+ * I tried out a few options for the assembly for the start and end time
+ * measurements, using the intel benchmark.  The benchmark reports variance, max
+ * deviation, and minimum per inner loop (line), as well as an overall variance,
+ * max dev, and variance of vars/mins.
+ *
+ * CASE    START ASM            END ASM
+ * ---------------------------------------------------
+ * case 0: cpuid;rdtsc;                        cpuid;rdtscp;
+ * case 1: cpuid;rdtsc;                        rdtscp;cpuid; (or rdtscp;lfence)
+ * case 2: lfence;rdtsc;               rdtscp;cpuid; (or rdtscp;lfence)
+ * case 3: rdtscp;                             rdtscp;cpuid; (or rdtscp;lfence)
+ * case 4: rdtscp;                             rdtscp;
+ * case 5: lfence;rdtsc;               lfence;rdtsc;
+ * case 6: lfence;rdtsc;lfence;        lfence;rdtsc;lfence;
+ *
+ * Note I only ran these a couple times, with 1000x10000, and I did notice some
+ * slight variation between runs (on cases 3 and 4).
+ *
+ * case 0:       wildly variant, variance of variances wasn't 0, etc (as
+ * reported by intel).
+ * case 0:  some lines     0 var, 0-8 max dev, 420 min
+ * case 0: other lines 50-60 var,  20 max dev, 388 min
+ *
+ * For all of the other cases, variance of variances and of minvalues was 0.
+ *
+ * case 1: most lines 2-3 var, 4 max dev, 44 min, 2 var 4 max dev overall
+ * case 2: most lines 2-3 var, 4 max dev, 44 min, 2 var 4 max dev overall
+ * case 3: most lines   0 var, 0 max dev, 32 min, 0 var 0 max dev overall
+ * case 4: most lines   0 var, 0 max dev, 32 min, 0 var 4 max dev overall
+ * case 5: most lines   3 var, 4 max dev, 28 min, 2 var 4 max dev overall
+ * case 6: most lines   3 var, 4 max dev, 44 min, 2 var 4 max dev overall
+ *
+ *             case 1-3: cpuid vs lfence: both seem to work the same and have no effect
+ *             (since they are outside the loop)
+ *
+ * So running with rdtscp for both start and stop (case 3 and 4) had the least
+ * amount of variance (both per line and total).  When these cases have had any
+ * deviation, it was because one run had a min of 28, but o/w was 32.  (1 out of
+ * 10000000, often the first run).
+ *
+ * All the others have a little deviation, but with a more stable min.  Again,
+ * this is taken mostly from a small number of runs (of 1kx10k).
+ *
+ * Note that cases 5 and 6 have lfences inside the measurement area, and this
+ * does not seem to cause problems the same way cpuid does.  However, lfences
+ * inside the critical section (esp after whatever code we are measuring)
+ * probably will have an effect on real code that has made memory accesses (keep
+ * in mind we need to do an mfence on amd64 here).
+ *
+ * All that being said, it's not clear which option to use.  Ideally, we want
+ * an isolated region of code to be measured, with very little variance and max
+ * deviation.  If cases 1-6 are all the same in terms of protection (which I'm
+ * not sure about), then 3-4 look nice.  However, the fact that sometimes the
+ * min is less than 'normal', means that we could get negative numbers for some
+ * measurements (the goal is to determine the overhead and subtract that from
+ * our total measurement, and if we think the overhead is 32 but was actually 28
+ * for a run, we could have issues). 
+ *
+ * But wait, there's more:
+ * 
+ * When we add code around (and inside) the measurement, things get even worse:
+ * - If we put variable (a volatile btw) = j + i; in the loop, there's no real
+ *   change.  I checked cases 1, 4 and 5, 1 being the intel recommended, 4 being
+ *   the one with the best variance with no code, and 5 being a good symmetric
+ *   choice (same on start and end).  Case 1 had no change at all.  4 and 5 had
+ *   little change (min was the same, occasional deviation).  Note that case 5
+ *   doesn't use rdtscp at the end either.
+ * - If we put in variable = i; as well, the minimum still is unaffected, and
+ *   there is a little more variance.  For example, for case 4, the min is still
+ *   32, and sometimes you get a 36.
+ *
+ * If we add more code (like a for loop that grows in length with each outer
+ * loop), eventually we can detect the existence of the instructions.  The Intel
+ * author talks about this in 3.3 when he finds the resolution of the benchmark.
+ *
+ * My hunch is that the rdtsc(p) calls hide the latency of some previous
+ * instructions, regardless of serialization commands.  We see this 'hiding' of
+ * the cost of instructions regardless of whether or not the first or last
+ * commands are rdtscp (I'm more concerned with the end time call, which is
+ * where this hiding may be happening).  Perhaps the pipeline needs to be
+ * drained (or something), and it takes a certain amount of time to do so, 
+ * regardless of a few extra instructions squeezed in.  Meaning we can't tell
+ * the difference between 0 and a few cycles, and probably a few cycles are
+ * 'free' / hidden by the rdtsc call. 
+ *
+ * Bottom line?  Our measurements are inexact, despite the stable minimum and
+ * low variance.  Everything will be +/- our max deviation, as well as
+ * potentially underestimating by a few cycles/ticks.  One thing we can do is
+ * try to see what the resolution is of the different methods.
+ *
+ * case 1: cpuid;rdtsc;                        rdtscp;cpuid; (or rdtscp;lfence)
+ * -------------------
+ * loop_size:0 >>>> variance(cycles): 3; max_deviation: 8; min time: 44
+ * loop_size:1 >>>> variance(cycles): 6; max_deviation: 28; min time: 44
+ * loop_size:2 >>>> variance(cycles): 4; max_deviation: 16; min time: 44
+ * loop_size:3 >>>> variance(cycles): 12; max_deviation: 44; min time: 44
+ * loop_size:4 >>>> variance(cycles): 10; max_deviation: 32; min time: 44
+ * loop_size:5 >>>> variance(cycles): 10; max_deviation: 32; min time: 44
+ * loop_size:6 >>>> variance(cycles): 12; max_deviation: 36; min time: 44
+ * loop_size:7 >>>> variance(cycles): 5; max_deviation: 32; min time: 48
+ * loop_size:8 >>>> variance(cycles): 16; max_deviation: 52; min time: 48
+ * loop_size:9 >>>> variance(cycles): 13; max_deviation: 48; min time: 52
+ * loop_size:10 >>>> variance(cycles): 9; max_deviation: 36; min time: 52
+ * loop_size:11 >>>> variance(cycles): 16; max_deviation: 64; min time: 56
+ *
+ * case 4: rdtscp;                             rdtscp;
+ * -------------------
+ * loop_size:0 >>>> variance(cycles): 1; max_deviation: 20; min time: 32
+ * loop_size:1 >>>> variance(cycles): 12; max_deviation: 36; min time: 36
+ * loop_size:2 >>>> variance(cycles): 13; max_deviation: 32; min time: 36
+ * loop_size:3 >>>> variance(cycles): 7; max_deviation: 32; min time: 40
+ * loop_size:4 >>>> variance(cycles): 1; max_deviation: 16; min time: 44
+ * loop_size:5 >>>> variance(cycles): 4; max_deviation: 28; min time: 44
+ * loop_size:6 >>>> variance(cycles): 12; max_deviation: 48; min time: 44
+ * loop_size:7 >>>> variance(cycles): 8; max_deviation: 32; min time: 44
+ * loop_size:8 >>>> variance(cycles): 10; max_deviation: 48; min time: 48
+ *
+ * case 5: lfence;rdtsc;               lfence;rdtsc;
+ * -------------------
+ * loop_size:0 >>>> variance(cycles): 3; max_deviation: 12; min time: 28
+ * loop_size:1 >>>> variance(cycles): 8; max_deviation: 28; min time: 32
+ * loop_size:2 >>>> variance(cycles): 8; max_deviation: 28; min time: 32
+ * loop_size:3 >>>> variance(cycles): 6; max_deviation: 28; min time: 32
+ * loop_size:4 >>>> variance(cycles): 2; max_deviation: 24; min time: 36
+ * loop_size:5 >>>> variance(cycles): 6; max_deviation: 28; min time: 36
+ * loop_size:6 >>>> variance(cycles): 11; max_deviation: 44; min time: 36
+ * loop_size:7 >>>> variance(cycles): 7; max_deviation: 32; min time: 36
+ * loop_size:8 >>>> variance(cycles): 1; max_deviation: 16; min time: 40
+ *
+ * For cases 4 and 5, we notice quite quickly.  The for loop itself has some
+ * overhead (probably more than our simple stores and adds).  So the resolution
+ * of these methods is a little more than a loop's overhead.  For case 1, we
+ * need about 7 loops, in addition to the overhead, until we can reliably detect
+ * the additional instructions.  Note the deviation and variation increases for
+ * all cases.
+ *
+ *
+ * What about extra code before the measurement?  I reran the test cases with
+ * some extra tsc-related code above the measurement (an accidental asm
+ * insertion of lfence;rdtsc above reading the start time) and with no work in
+ * between:
+ *             case 1: no effect
+ *             case 2: no effect
+ * These both had some form of serialization (cpuid or lfence) above the rdtsc
+ * command.  But when we try using just rdtscp (with no extra serialization:)
+ *             case 3, normal: lines   0 var, 0 max dev, 32 min, 0 var 0 max dev
+ *             case 3, extras: lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
+ * Similar deal with case 4.  Lots of 28s and deviation.  It looks like some
+ * times the rdtsc diff is only 28, and others 32 (hence the deviation of 4).
+ * Note this means the measurement interval is *lower*, which means the code was
+ * *faster*.  Was the rdtscp not serializing instructions from above (which
+ * doesn't make sense, since anything sneaking in from above should make the
+ * code *slower*)?  Or is it because the previous command was rdtsc, which might
+ * 'speed up' subsequent rdtscs.  I tried it again, with a little work between
+ * the unused TSC read and the start tsc read:
+ *             case 3, more crap : lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
+ * So no real change from adding minor code in between.  What about adding an
+ * lfence above the rdtscp (so it is almost exactly like case 2)?
+ * Our assembly code now looks like:
+ *             lfence;
+ *             rdtsc;
+ *             mov %edx, (memory);     // these get overwritten
+ *             mov %eax, (memory);     // these get overwritten
+ *
+ *             mov (memory), %eax;             // misc work (variable = i + j)
+ *             add %esi, %eax;                 // misc work (variable = i + j)
+ *             mov %eax, (memory);             // misc work (variable = i + j)
+ *
+ *             lfence;
+ *             rdtscp;                                 // this is the real start measurement
+ *             mov %edx, (memory);
+ *             mov %eax, (memory);
+ *
+ *      // no extra work here
+ *
+ *             rdtscp;                                 // this is the real end measurement
+ *             mov %edx, (memory);
+ *             mov %eax, (memory);
+ *             cpuid;                                  // this is case 3, with sync after
+ *
+ * Even with this extra lfence, case 3-style still shows numbers like:
+ *             case 3, added crap: lines 2-3 var, 4 max dev, 28 min, 2 var 4 max dev
+ * So either rdtscp is somehow faster due to internal-processor-caching (a
+ * previous rdtsc makes the next rdtscp somewhat faster sometimes, including
+ * after some instructions and an lfence), or the baseline case of no variation
+ * is "wrong", and we really should expect between 28 and 32.  FWIW, the Intel
+ * author also had a max deviation of 4 (per line).  And remember, on rare
+ * occasions we get a 28 for case 3 and 4 (the other 9999999 times it is 32).
+ *
+ * Note how the modified case 3 is pretty much the same *in performance* as a
+ * case 5.  But its code is nearly identical to case 2.  If you change the start
+ * measurement's rdtscp to an rdtsc, the min goes from 28 -> 44 (this is case
+ * 2).  And if you change the end measurements rdtscp to an lfence; rdtscp, we
+ * go from 44->48 (this is no case).  Then if you change that rdtscp to an
+ * rdtsc, we drop from 48->28 (this is case 5).  Based on this, it looks like
+ * the different types of rdtsc take their time measurement at different points
+ * within their execution.  rdtsc probably takes its measurement earlier in the
+ * instruction (~16-20 cycles/ticks earlier perhaps?), based on the 48->28
+ * back-side step and the front-side 28->44 step.
+ *             
+ * Anyway, what matters is a relatively stable method without a lot of variance
+ * that has a solid floor/min that we can detect at runtime (to run tests on a
+ * given machine).  Using rdtscp for the start measurement seems unreliable
+ * (when run alone we get 32, when run with things we get 28, on the corei7).
+ * So even though case 3 and 4 had nice low variances and deviations, I don't
+ * trust it, and would rather go with something that always gives me the same
+ * result (as well as being a low result).  So case 5 will be my go-to for now.
+ * It should have the same protection as the others (perhaps 6 is better), it is
+ * stable, and it has a low overhead and low resolution (less capacity to hide
+ * instruction latency).  Finally, the start and end measurements use the same
+ * code, which is very convenient.
+ *
+ * This isn't conclusive - we'd need to do more tests with different workloads
+ * on different machines, and probably talk to an intel architect.
+ *
+ * Still reading?  There's one more thing: System Management Mode!  This is an
+ * interrupt context that is invisible to the OS, but we can see its effects in
+ * our measurements.  If you run this code with the default settings, you often
+ * won't see it (unless you have some loops).  However, if you run with
+ * 1024x16384 (0x400 by 0x4000), you are likely to see very large max
+ * deviations, such as 100, 600, or even 1500000.  From what I can tell, the
+ * likelihood depends on how long the inner loop.  Using case 5 at 0x400,
+ * 0x4000, after 3-4 runs, I had one line out of 1024 lines that was much
+ * higher.  Three were 112, one was 1659260.  AFAIK, this is system management
+ * mode kicking in.  You can mitigate this by disabling all types of USB legacy
+ * support in the BIOS.  Specifically, faking USB keyboards and mice (making
+ * them look like PS/2) and USB mass storage (making them look like a HDD) all
+ * lead to an increase in SMIs.  For more info, check out:
+ *             https://rt.wiki.kernel.org/index.php/HOWTO:_Build_an_RT-application
+ * It is not sufficient to merely not use things like the USB mass storage.  It
+ * needs to be disabled in the BIOS.  At least, this is true on my nehalem.  A
+ * while back, we had an issue with microbenchmarks taking 10% longer if you
+ * held down a key on the keyboard, even if the code was running on a core that
+ * did not receive the keyboard IRQ.  Turns out this was due to a USB keyboard
+ * in legacy mode.  The real root of this problem was SMM, which forces all
+ * cores to enter SMM whenever any core enters SMM (hence the cross-core
+ * interference).
+ *
+ * So finally, disable anything that may lead to SMM interference.  I have some
+ * code that runs at startup that tries to determine the min time for the given
+ * approved method of measurement (i.e., case 5), and also tries to detect SMIs
+ * via massive latency spikes.  */
+
+#include <ros/common.h>
+#include <arch/arch.h>
+#include <stdio.h>
+#include <kmalloc.h>
+
+#define STAT_SIZE_DEF 10000
+#define LOOP_BOUND_DEF 1000
+
+/* Fills in the **times with the results of the double loop measurement.  There
+ * are many options for start and end time measurements, all inside #if 0 #endif
+ * comments.  Copy/paste whichever you'd like to test out. */
+static inline void filltimes(uint64_t **times, unsigned int loop_bound,
+                             unsigned int stat_size)
+{
+       unsigned long flags;
+       int i, j;
+       uint64_t start, end;
+       unsigned int start_low, start_high, end_low, end_high;
+       unsigned int dummy_low, dummy_high;
+       volatile int variable = 0;
+       int8_t state = 0;
+
+       /* Variety of warmups.  recommended for cpuid... */
+       asm volatile ("cpuid\n\t"
+                     "rdtsc\n\t"
+                     "cpuid\n\t"
+                     "rdtsc\n\t"
+                     "cpuid\n\t"
+                     "rdtsc\n\t"
+                     "mov %%edx, %0\n\t"
+                     "mov %%eax, %1\n\t": "=m" (dummy_high), "=m" (dummy_low)::
+                     "%eax", "%ebx", "%ecx", "%edx");
+       for (j = 0; j < loop_bound; j++) {
+               for (i = 0; i < stat_size; i++) {
+                       variable = 0;
+                       /* starting side, i want to make sure we always copy out to memory
+                        * (stack), instead of sometimes using registers (and other times
+                        * not).  if you use =a, for instance, with no work, the compiler
+                        * will use esi and edi to store start_high and _low.
+                        *
+                        * The same concern is probably unnecessary at the end, but it might
+                        * keep the compiler from reserving the use of those registers.*/
+
+                       #if 0 /* extra crap before the measurement code */
+                       asm volatile (
+                                                 "lfence;"
+                                     "rdtsc;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                 : "=m" (dummy_high), "=m" (dummy_low)
+                                                 :
+                                                 : "%eax", "%edx");
+
+                       variable = i + j;
+                       #endif
+
+                       asm volatile (
+                                                 "lfence;"
+                                     "rdtsc;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                 : "=m" (start_high), "=m" (start_low)
+                                                 :
+                                                 : "%eax", "%edx");
+                       #if 0   /* types of start time measurements */
+                       asm volatile (
+                                     "cpuid;"
+                                     "rdtsc;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                 : "=m" (start_high), "=m" (start_low)
+                                                 :
+                                                 : "%eax", "%ebx", "%ecx", "%edx");
+                       asm volatile (
+                                                 "lfence;"
+                                     "rdtsc;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                 : "=m" (start_high), "=m" (start_low)
+                                                 :
+                                                 : "%eax", "%edx");
+                       asm volatile (
+                                                 "lfence;"
+                                     "rdtsc;"
+                                                 "lfence;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                 : "=m" (start_high), "=m" (start_low)
+                                                 :
+                                                 : "%eax", "%edx");
+
+                       asm volatile(
+                                    "rdtscp;"
+                                                 "mov %%edx, %0;"
+                                                 "mov %%eax, %1;"
+                                                : "=m" (start_high), "=m" (start_low)
+                                                :
+                                                : "%eax", "%ecx", "%edx");
+                       #endif
+
+                       /* call the function to measure here */
+
+                       #if 0 /* some options for code to measure */
+                       variable = j;
+
+                       variable = i + j;
+
+                       for (int k = 0; k < j; k++)
+                               variable = k;
+                       #endif
+
+                       asm volatile("lfence;"
+                                    "rdtsc;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%edx");
+                       #if 0   /* types of end time measurements */
+                       asm volatile("cpuid;"
+                                    "rdtsc;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%ebx", "%ecx", "%edx");
+                       asm volatile("lfence;"
+                                    "rdtsc;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%edx");
+                       asm volatile("lfence;"
+                                    "rdtsc;"
+                                                 "lfence;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%edx");
+
+                       asm volatile(
+                                    "rdtscp;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%ecx", "%edx");
+                       asm volatile(
+                                    "rdtscp;"
+                                                "lfence;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%ecx", "%edx");
+                       asm volatile(
+                                    "rdtscp;"
+                                    "mov %%edx, %0;"
+                                    "mov %%eax, %1;"
+                                    "cpuid;"
+                                                : "=m" (end_high), "=m" (end_low)
+                                                :
+                                                : "%eax", "%ebx", "%ecx", "%edx");
+                       #endif
+                       
+                       start = ( ((uint64_t)start_high << 32) | start_low );
+                       end = ( ((uint64_t)end_high << 32) | end_low );
+                       
+                       if ( (int64_t)(end - start) < 0) {
+                               printk("CRITICAL ERROR IN TAKING THE TIME!!!!!!\n"
+                       "loop(%d) stat(%d) start = %llu, end = %llu, "
+                       "variable = %u\n", j, i, start, end, variable);
+                               times[j][i] = 0;
+                       } else {
+                               times[j][i] = end - start;
+                       }
+               }
+       }
+}
+
+/* http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance, doing pop
+ * variance, multiplying by N/N, and not checking overflow of size*size */
+uint64_t var_calc(uint64_t *inputs, int size)
+{
+       int i;
+       uint64_t acc = 0, previous = 0, temp_var = 0;
+       for (i = 0; i < size; i++) {
+               if (acc < previous)
+                       goto overflow;
+               previous = acc;
+               acc += inputs[i];
+       }
+       acc = acc * acc;
+       if (acc < previous)
+               goto overflow;
+       previous = 0;
+       for (i = 0; i < size; i++) {
+               if (temp_var < previous)
+                       goto overflow;
+               previous = temp_var;
+               temp_var+= (inputs[i]*inputs[i]);
+       }
+       temp_var = temp_var * size;
+       if (temp_var < previous)
+               goto overflow;
+       temp_var = (temp_var - acc)/(((uint64_t)(size))*((uint64_t)(size)));
+       return (temp_var);
+overflow:
+       printk("CRITICAL OVERFLOW ERROR IN var_calc!!!!!!\n\n");
+       return -1;
+}
+
+int test_rdtsc(unsigned int loop_bound, unsigned int stat_size)
+{
+       int8_t state = 0;
+
+       int i = 0, j = 0, spurious = 0, k = 0;
+       uint64_t **times;
+       uint64_t *variances;
+       uint64_t *min_values;
+       uint64_t max_dev = 0, min_time = 0, max_time = 0, prev_min = 0;
+       uint64_t tot_var = 0, max_dev_all = 0, var_of_vars = 0, var_of_mins = 0;
+       loop_bound = loop_bound ?: LOOP_BOUND_DEF;
+       stat_size = stat_size ?: STAT_SIZE_DEF;
+       
+       printk("Running rdtsc tests...\n");
+       
+       times = kmalloc(loop_bound * sizeof(uint64_t*), 0);
+       if (!times) {
+               printk("unable to allocate memory for times\n");
+               return 0;
+       }
+
+       for (j = 0; j < loop_bound; j++) {
+               times[j] = kmalloc(stat_size * sizeof(uint64_t), 0);
+               if (!times[j]) {
+                       printk("unable to allocate memory for times[%d]\n", j);
+                       for (k = 0; k < j; k++)
+                               kfree(times[k]);
+                       return 0;
+               }
+       }
+       
+       variances = kmalloc(loop_bound * sizeof(uint64_t), 0);
+       if (!variances) {
+               printk("unable to allocate memory for variances\n");
+               // not bothering to free **times
+               return 0;
+       }
+       
+       min_values = kmalloc(loop_bound * sizeof(uint64_t), 0);
+       if (!min_values) {
+               printk("unable to allocate memory for min_values\n");
+               // not bothering to free **times or variances
+               return 0;
+       }
+       
+       disable_irqsave(&state);
+
+       filltimes(times, loop_bound, stat_size);
+
+       enable_irqsave(&state);
+
+       for (j = 0; j < loop_bound; j++) {
+               max_dev = 0;
+               min_time = 0;
+               max_time = 0;
+       
+               for (i = 0; i < stat_size; i++) {
+                       if ((min_time == 0) || (min_time > times[j][i]))
+                               min_time = times[j][i];
+                       if (max_time < times[j][i])
+                               max_time = times[j][i];
+               }
+               max_dev = max_time - min_time;
+               min_values[j] = min_time;
+               if ((prev_min != 0) && (prev_min > min_time))
+                       spurious++;
+               if (max_dev > max_dev_all)
+                       max_dev_all = max_dev;
+               variances[j] = var_calc(times[j], stat_size);
+               tot_var += variances[j];
+               
+               printk("loop_size:%d >>>> variance(cycles): %llu; "
+               "max_deviation: %llu; min time: %llu\n", j, variances[j],
+               max_dev, min_time);
+               prev_min = min_time;
+       }
+       
+       var_of_vars = var_calc(variances, loop_bound);
+       var_of_mins = var_calc(min_values, loop_bound);
+       
+       printk("total number of spurious min values = %d\n", spurious);
+       /* is this next one the mean variance, not the total? */
+       printk("total variance = %llu\n", (tot_var/loop_bound));
+       printk("absolute max deviation = %llu\n", max_dev_all);
+       printk("variance of variances = %llu\n", var_of_vars);
+       printk("variance of minimum values = %llu\n", var_of_mins);
+       
+       for (j = 0; j < loop_bound; j++) {
+               kfree(times[j]);
+       }
+       kfree(times);
+       kfree(variances);
+       kfree(min_values);
+       return 0;
+}
+
+
+/* Crude SMI or other TSC-instability detection. */
+bool check_timing_stability(void)
+{
+       uint64_t min_overhead = UINT64_MAX;
+       uint64_t max_overhead = 0;
+       uint64_t start, end, diff;
+       uint32_t edx;
+       int8_t irq_state = 0;
+       volatile int dummy = 0;
+
+       /* Don't even bother if we don't have an invariant TSC */
+       cpuid(0x80000007, 0x0, 0, 0, 0, &edx);
+       if (!(edx & (1 << 8))) {
+               printk("Invariant TSC not present.  Do not benchmark!\n");
+               return FALSE;
+       }
+       disable_irqsave(&irq_state);
+       /* 2mil detected an SMI about 95% of the time on my nehalem. */
+       for (int i = 0; i < 3000000; i++) {
+               start = read_tsc_serialized();
+               for (int j = 0; j < 500; j++) 
+                       dummy = j;
+               end = read_tsc_serialized();
+               if ((int64_t)(end - start) < 0) {
+                       printk("TSC stability overflow error!\n");
+                       return FALSE;
+               }
+               diff = end - start;
+               min_overhead = MIN(min_overhead, diff);
+               max_overhead = MAX(max_overhead, diff);
+       }
+       enable_irqsave(&irq_state);
+       if (max_overhead - min_overhead > 50) {
+               printk("Test TSC overhead unstable (Min: %llu, Max: %llu).  "
+                      "Do not benchmark!\n", min_overhead, max_overhead);
+               return FALSE;
+       }
+       return TRUE;
+}
+
+void test_tsc_cycles(void)
+{
+       uint64_t start, end;
+       int8_t irq_state = 0;
+
+       disable_irqsave(&irq_state);
+       start = read_tsc_serialized();
+       for (int i = 0; i < 1000; i++) {
+               asm volatile ("addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                         "addl $1, %%eax;"
+                                     : : : "eax", "cc");
+       }
+       end = read_tsc_serialized();
+       end = end - start - system_timing.timing_overhead;
+       printk("%llu (100,000) ticks passed, run twice to load the icache\n", end);
+
+       enable_irqsave(&irq_state);
+}
index 1655cdf..a3d8555 100644 (file)
@@ -131,7 +131,7 @@ static int smp_call_function(uint8_t type, uint32_t dest, poly_isr_t handler, TV
                        send_all_others_ipi(wrapper->vector);
                        break;
                case 4: // physical mode
-                       send_ipi(get_hw_coreid(dest), wrapper->vector);
+                       send_ipi(dest, wrapper->vector);
                        break;
                case 5: // logical mode
                        send_group_ipi(dest, wrapper->vector);
index 4c13660..d5bf3ef 100644 (file)
@@ -160,7 +160,7 @@ void smp_boot(void)
        // booting.  Specifically, it's when they turn on paging and have that temp
        // mapping pulled out from under them.  Now, if a core loses, it will spin
        // on the trampoline (which we must be careful to not deallocate)
-       __spin_lock(get_smp_bootlock());
+       __spin_lock_raw(get_smp_bootlock());
        printk("Number of Cores Detected: %d\n", num_cpus);
 #ifdef __CONFIG_DISABLE_SMT__
        assert(!(num_cpus % 2));
index 48ae3e8..1258592 100644 (file)
@@ -43,9 +43,6 @@ pseudodesc_t RO idt_pd = {
 spinlock_t iht_lock;
 handler_t TP(TV(t)) LCKD(&iht_lock) (RO interrupt_handlers)[NUM_INTERRUPT_HANDLERS];
 
-/* x86-specific interrupt handlers */
-void __kernel_message(struct trapframe *tf, void *data);
-
 static const char *NTS trapname(int trapno)
 {
     // zra: excnames is SREADONLY because Ivy doesn't trust const
@@ -200,7 +197,7 @@ void idt_init(void)
                                   timer_interrupt, NULL);
        /* register the kernel message handler */
        register_interrupt_handler(interrupt_handlers, I_KERNEL_MSG,
-                                  __kernel_message, NULL);
+                                  handle_kmsg_ipi, NULL);
 }
 
 void
@@ -219,8 +216,13 @@ print_regs(push_regs_t *regs)
 void
 print_trapframe(trapframe_t *tf)
 {
-       static spinlock_t ptf_lock;
+       static spinlock_t ptf_lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
+       struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
+       /* This is only called in debug scenarios, and often when the kernel trapped
+        * and needs to tell us about it.  Disable the lock checker so it doesn't go
+        * nuts when we print/panic */
+       pcpui->__lock_depth_disabled++;
        spin_lock_irqsave(&ptf_lock);
        printk("TRAP frame at %p on core %d\n", tf, core_id());
        print_regs(&tf->tf_regs);
@@ -239,24 +241,67 @@ print_trapframe(trapframe_t *tf)
                printk("  ss   0x----%04x\n", tf->tf_ss);
        }
        spin_unlock_irqsave(&ptf_lock);
+       pcpui->__lock_depth_disabled--;
+}
+
+static void fake_rdtscp(struct trapframe *tf)
+{
+       uint64_t tsc_time = read_tsc();
+       tf->tf_eip += 3;
+       tf->tf_regs.reg_eax = tsc_time & 0xffffffff;
+       tf->tf_regs.reg_edx = tsc_time >> 32;
+       tf->tf_regs.reg_ecx = core_id();
 }
 
 /* Certain traps want IRQs enabled, such as the syscall.  Others can't handle
  * it, like the page fault handler.  Turn them on on a case-by-case basis. */
 static void trap_dispatch(struct trapframe *tf)
 {
+       struct per_cpu_info *pcpui;
        // Handle processor exceptions.
        switch(tf->tf_trapno) {
                case T_NMI:
+                       /* Temporarily disable deadlock detection when we print.  We could
+                        * deadlock if we were printing when we NMIed. */
+                       pcpui = &per_cpu_info[core_id()];
+                       pcpui->__lock_depth_disabled++;
                        print_trapframe(tf);
                        char *fn_name = get_fn_name(tf->tf_eip);
                        printk("Core %d is at %08p (%s)\n", core_id(), tf->tf_eip, fn_name);
                        kfree(fn_name);
+                       print_kmsgs(core_id());
+                       pcpui->__lock_depth_disabled--;
                        break;
                case T_BRKPT:
                        enable_irq();
                        monitor(tf);
                        break;
+               case T_ILLOP:
+                       pcpui = &per_cpu_info[core_id()];
+                       pcpui->__lock_depth_disabled++;         /* for print debugging */
+                       /* We will muck with the actual TF.  If we're dealing with
+                        * userspace, we need to make sure we edit the actual TF that will
+                        * get restarted (pcpui), and not the TF on the kstack (which aren't
+                        * the same).  See set_current_tf() for more info. */
+                       if (!in_kernel(tf))
+                               tf = pcpui->cur_tf;
+                       printd("bad opcode, eip: %08p, next 3 bytes: %x %x %x\n",
+                              tf->tf_eip, 
+                              *(uint8_t*)(tf->tf_eip + 0), 
+                              *(uint8_t*)(tf->tf_eip + 1), 
+                              *(uint8_t*)(tf->tf_eip + 2)); 
+                       /* rdtscp: 0f 01 f9 */
+                       if (*(uint8_t*)(tf->tf_eip + 0) == 0x0f, 
+                           *(uint8_t*)(tf->tf_eip + 1) == 0x01, 
+                           *(uint8_t*)(tf->tf_eip + 2) == 0xf9) {
+                               fake_rdtscp(tf);
+                               pcpui->__lock_depth_disabled--; /* for print debugging */
+                               return;
+                       }
+                       enable_irq();
+                       monitor(tf);
+                       pcpui->__lock_depth_disabled--;         /* for print debugging */
+                       break;
                case T_PGFLT:
                        page_fault_handler(tf);
                        break;
@@ -275,6 +320,7 @@ static void trap_dispatch(struct trapframe *tf)
                                panic("Damn Damn!  Unhandled trap in the kernel!");
                        else {
                                warn("Unexpected trap from userspace");
+                               enable_irq();
                                proc_destroy(current);
                        }
        }
@@ -295,7 +341,17 @@ env_pop_ancillary_state(env_t* e)
 }
 
 /* Helper.  For now, this copies out the TF to pcpui.  Eventually, we should
- * consider doing this in trapentry.S */
+ * consider doing this in trapentry.S
+ *
+ * TODO: consider having this return pcpui->cur_tf, so we can set tf in trap and
+ * irq handlers to edit the TF that will get restarted.  Right now, the kernel
+ * uses and restarts tf, but userspace restarts the old pcpui tf.  It is
+ * tempting to do this, but note that tf stays on the stack of the kthread,
+ * while pcpui->cur_tf is for the core we trapped in on.  Meaning if we ever
+ * block, suddenly cur_tf is pointing to some old clobbered state that was
+ * already returned to and can't be trusted.  Meanwhile tf can always be trusted
+ * (like with an in_kernel() check).  The only types of traps from the user that
+ * can be expected to have editable trapframes are ones that don't block. */
 static void set_current_tf(struct per_cpu_info *pcpui, struct trapframe *tf)
 {
        assert(!irq_is_enabled());
@@ -325,9 +381,11 @@ static void abort_halt(struct trapframe *tf)
 void trap(struct trapframe *tf)
 {
        struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
-       /* Copy out the TF for now, set tf to point to it.  */
+       /* Copy out the TF for now */
        if (!in_kernel(tf))
                set_current_tf(pcpui, tf);
+       else
+               inc_ktrap_depth(pcpui);
 
        printd("Incoming TRAP %d on core %d, TF at %p\n", tf->tf_trapno, core_id(),
               tf);
@@ -339,57 +397,127 @@ void trap(struct trapframe *tf)
        /* Return to the current process, which should be runnable.  If we're the
         * kernel, we should just return naturally.  Note that current and tf need
         * to still be okay (might not be after blocking) */
-       if (in_kernel(tf))
-               return; /* TODO: think about this, might want a helper instead. */
+       if (in_kernel(tf)) {
+               dec_ktrap_depth(pcpui);
+               return;
+       }
        proc_restartcore();
        assert(0);
 }
 
-/* Note IRQs are disabled unless explicitly turned on. */
+/* Tells us if an interrupt (trap_nr) came from the PIC or not */
+static bool irq_from_pic(uint32_t trap_nr)
+{
+       /* The 16 IRQs within the range [PIC1_OFFSET, PIC1_OFFSET + 15] came from
+        * the PIC.  [32-47] */
+       if (trap_nr < PIC1_OFFSET)
+               return FALSE;
+       if (trap_nr > PIC1_OFFSET + 15)
+               return FALSE;
+       return TRUE;
+}
+
+/* Helper: returns TRUE if the irq is spurious.  Pass in the trap_nr, not the
+ * IRQ number (trap_nr = PIC_OFFSET + irq) */
+static bool check_spurious_irq(uint32_t trap_nr)
+{
+#ifndef __CONFIG_ENABLE_MPTABLES__             /* TODO: our proxy for using the PIC */
+       /* the PIC may send spurious irqs via one of the chips irq 7.  if the isr
+        * doesn't show that irq, then it was spurious, and we don't send an eoi.
+        * Check out http://wiki.osdev.org/8259_PIC#Spurious_IRQs */
+       if ((trap_nr == PIC1_SPURIOUS) && !(pic_get_isr() & PIC1_SPURIOUS)) {
+               printk("Spurious PIC1 irq!\n"); /* want to know if this happens */
+               return TRUE;
+       }
+       if ((trap_nr == PIC2_SPURIOUS) && !(pic_get_isr() & PIC2_SPURIOUS)) {
+               printk("Spurious PIC2 irq!\n"); /* want to know if this happens */
+               /* for the cascaded PIC, we *do* need to send an EOI to the master's
+                * cascade irq (2). */
+               pic_send_eoi(2);
+               return TRUE;
+       }
+       /* At this point, we know the PIC didn't send a spurious IRQ */
+       if (irq_from_pic(trap_nr))
+               return FALSE;
+#endif
+       /* Either way (with or without a PIC), we need to check the LAPIC.
+        * FYI: lapic_spurious is 255 on qemu and 15 on the nehalem..  We actually
+        * can set bits 4-7, and P6s have 0-3 hardwired to 0.  YMMV.
+        *
+        * The SDM recommends not using the spurious vector for any other IRQs (LVT
+        * or IOAPIC RTE), since the handlers don't send an EOI.  However, our check
+        * here allows us to use the vector since we can tell the diff btw a
+        * spurious and a real IRQ. */
+       uint8_t lapic_spurious = read_mmreg32(LAPIC_SPURIOUS) & 0xff;
+       /* Note the lapic's vectors are not shifted by an offset. */
+       if ((trap_nr == lapic_spurious) && !lapic_get_isr_bit(lapic_spurious)) {
+               printk("Spurious LAPIC irq %d, core %d!\n", lapic_spurious, core_id());
+               lapic_print_isr();
+               return TRUE;
+       }
+       return FALSE;
+}
+
+/* Helper, sends an end-of-interrupt for the trap_nr (not HW IRQ number). */
+static void send_eoi(uint32_t trap_nr)
+{
+#ifndef __CONFIG_ENABLE_MPTABLES__             /* TODO: our proxy for using the PIC */
+       /* WARNING: this will break if the LAPIC requests vectors that overlap with
+        * the PIC's range. */
+       if (irq_from_pic(trap_nr))
+               pic_send_eoi(trap_nr - PIC1_OFFSET);
+       else
+               lapic_send_eoi();
+#else
+       lapic_send_eoi();
+#endif
+}
+
+/* Note IRQs are disabled unless explicitly turned on.
+ *
+ * In general, we should only get trapno's >= PIC1_OFFSET (32).  Anything else
+ * should be a trap.  Even if we don't use the PIC, that should be the standard.
+ * It is possible to get a spurious LAPIC IRQ with vector 15 (or similar), but
+ * the spurious check should catch that.
+ *
+ * Note that from hardware's perspective (PIC, etc), IRQs start from 0, but they
+ * are all mapped up at PIC1_OFFSET for the cpu / irq_handler. */
 void irq_handler(struct trapframe *tf)
 {
        struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
-       /* Copy out the TF for now, set tf to point to it. */
+       /* Copy out the TF for now */
        if (!in_kernel(tf))
                set_current_tf(pcpui, tf);
+       inc_irq_depth(pcpui);
        /* Coupled with cpu_halt() and smp_idle() */
        abort_halt(tf);
        //if (core_id())
                printd("Incoming IRQ, ISR: %d on core %d\n", tf->tf_trapno, core_id());
+       if (check_spurious_irq(tf->tf_trapno))
+               goto out_no_eoi;
+       /* Send the EOI.  This means the PIC/LAPIC can send us the same IRQ vector,
+        * and we'll handle it as soon as we reenable IRQs.  This does *not* mean
+        * the hardware device that triggered the IRQ had its IRQ reset.  This does
+        * mean we shouldn't enable irqs in a handler that isn't reentrant. */
+       assert(tf->tf_trapno >= 32);
+       send_eoi(tf->tf_trapno);
 
        extern handler_wrapper_t (RO handler_wrappers)[NUM_HANDLER_WRAPPERS];
-
        // determine the interrupt handler table to use.  for now, pick the global
        handler_t TP(TV(t)) LCKD(&iht_lock) * handler_tbl = interrupt_handlers;
-
        if (handler_tbl[tf->tf_trapno].isr != 0)
                handler_tbl[tf->tf_trapno].isr(tf, handler_tbl[tf->tf_trapno].data);
        // if we're a general purpose IPI function call, down the cpu_list
        if ((I_SMP_CALL0 <= tf->tf_trapno) && (tf->tf_trapno <= I_SMP_CALL_LAST))
                down_checklist(handler_wrappers[tf->tf_trapno & 0x0f].cpu_list);
-
-       // Send EOI.  might want to do this in assembly, and possibly earlier
-       // This is set up to work with an old PIC for now
-       // Convention is that all IRQs between 32 and 47 are for the PIC.
-       // All others are LAPIC (timer, IPIs, perf, non-ExtINT LINTS, etc)
-       // For now, only 235-255 are available
-       assert(tf->tf_trapno >= 32); // slows us down, but we should never have this
-
-#ifdef __CONFIG_ENABLE_MPTABLES__
-       /* TODO: this should be for any IOAPIC EOI, not just MPTABLES */
-       lapic_send_eoi();
-#else
-       //Old PIC relatd code. Should be gone for good, but leaving it just incase.
-       if (tf->tf_trapno < 48)
-               pic_send_eoi(tf->tf_trapno - PIC1_OFFSET);
-       else
-               lapic_send_eoi();
-#endif
+       /* Fall-through */
+out_no_eoi:
+       dec_irq_depth(pcpui);
        /* Return to the current process, which should be runnable.  If we're the
         * kernel, we should just return naturally.  Note that current and tf need
         * to still be okay (might not be after blocking) */
        if (in_kernel(tf))
-               return; /* TODO: think about this, might want a helper instead. */
+               return;
        proc_restartcore();
        assert(0);
 }
@@ -412,7 +540,12 @@ void page_fault_handler(struct trapframe *tf)
        if ((tf->tf_cs & 3) == 0) {
                print_trapframe(tf);
                panic("Page Fault in the Kernel at 0x%08x!", fault_va);
+               /* if we want to do something like kill a process or other code, be
+                * aware we are in a sort of irq-like context, meaning the main kernel
+                * code we 'interrupted' could be holding locks - even irqsave locks. */
        }
+       /* safe to reenable after rcr2 */
+       enable_irq();
        if ((err = handle_page_fault(current, fault_va, prot))) {
                /* Destroy the faulting process */
                printk("[%08x] user %s fault va %08x ip %08x on core %d with err %d\n",
@@ -434,14 +567,13 @@ void sysenter_init(void)
 void sysenter_callwrapper(struct trapframe *tf)
 {
        struct per_cpu_info *pcpui = &per_cpu_info[core_id()];
-       /* Copy out the TF for now, set tf to point to it. */
-       if (!in_kernel(tf))
-               set_current_tf(pcpui, tf);
-       /* Once we've set_current_tf, we can enable interrupts */
+       assert(!in_kernel(tf));
+       set_current_tf(pcpui, tf);
+       /* Once we've set_current_tf, we can enable interrupts.  This used to be
+        * mandatory (we had immediate KMSGs that would muck with cur_tf).  Now it
+        * should only help for sanity/debugging. */
        enable_irq();
 
-       if (in_kernel(tf))
-               panic("sysenter from a kernel TF!!");
        /* Set up and run the async calls */
        prep_syscalls(current, (struct syscall*)tf->tf_regs.reg_eax,
                      tf->tf_regs.reg_esi);
@@ -449,186 +581,13 @@ void sysenter_callwrapper(struct trapframe *tf)
        proc_restartcore();
 }
 
-struct kmem_cache *kernel_msg_cache;
-void kernel_msg_init(void)
-{
-       kernel_msg_cache = kmem_cache_create("kernel_msgs",
-                          sizeof(struct kernel_message), HW_CACHE_ALIGN, 0, 0, 0);
-}
-
-void kmsg_queue_stat(void)
-{
-       struct kernel_message *kmsg;
-       bool immed_emp, routine_emp;
-       for (int i = 0; i < num_cpus; i++) {
-               spin_lock_irqsave(&per_cpu_info[i].immed_amsg_lock);
-               immed_emp = STAILQ_EMPTY(&per_cpu_info[i].immed_amsgs);
-               spin_unlock_irqsave(&per_cpu_info[i].immed_amsg_lock);
-               spin_lock_irqsave(&per_cpu_info[i].routine_amsg_lock);
-               routine_emp = STAILQ_EMPTY(&per_cpu_info[i].routine_amsgs);
-               spin_unlock_irqsave(&per_cpu_info[i].routine_amsg_lock);
-               printk("Core %d's immed_emp: %d, routine_emp %d\n", i, immed_emp, routine_emp);
-               if (!immed_emp) {
-                       kmsg = STAILQ_FIRST(&per_cpu_info[i].immed_amsgs);
-                       printk("Immed msg on core %d:\n", i);
-                       printk("\tsrc:  %d\n", kmsg->srcid);
-                       printk("\tdst:  %d\n", kmsg->dstid);
-                       printk("\tpc:   %08p\n", kmsg->pc);
-                       printk("\targ0: %08p\n", kmsg->arg0);
-                       printk("\targ1: %08p\n", kmsg->arg1);
-                       printk("\targ2: %08p\n", kmsg->arg2);
-               }
-               if (!routine_emp) {
-                       kmsg = STAILQ_FIRST(&per_cpu_info[i].routine_amsgs);
-                       printk("Routine msg on core %d:\n", i);
-                       printk("\tsrc:  %d\n", kmsg->srcid);
-                       printk("\tdst:  %d\n", kmsg->dstid);
-                       printk("\tpc:   %08p\n", kmsg->pc);
-                       printk("\targ0: %08p\n", kmsg->arg0);
-                       printk("\targ1: %08p\n", kmsg->arg1);
-                       printk("\targ2: %08p\n", kmsg->arg2);
-               }
-                       
-       }
-}
-
-uint32_t send_kernel_message(uint32_t dst, amr_t pc, long arg0, long arg1,
-                             long arg2, int type)
-{
-       kernel_message_t *k_msg;
-       assert(pc);
-       // note this will be freed on the destination core
-       k_msg = (kernel_message_t *CT(1))TC(kmem_cache_alloc(kernel_msg_cache, 0));
-       k_msg->srcid = core_id();
-       k_msg->dstid = dst;
-       k_msg->pc = pc;
-       k_msg->arg0 = arg0;
-       k_msg->arg1 = arg1;
-       k_msg->arg2 = arg2;
-       switch (type) {
-               case KMSG_IMMEDIATE:
-                       spin_lock_irqsave(&per_cpu_info[dst].immed_amsg_lock);
-                       STAILQ_INSERT_TAIL(&per_cpu_info[dst].immed_amsgs, k_msg, link);
-                       spin_unlock_irqsave(&per_cpu_info[dst].immed_amsg_lock);
-                       break;
-               case KMSG_ROUTINE:
-                       spin_lock_irqsave(&per_cpu_info[dst].routine_amsg_lock);
-                       STAILQ_INSERT_TAIL(&per_cpu_info[dst].routine_amsgs, k_msg, link);
-                       spin_unlock_irqsave(&per_cpu_info[dst].routine_amsg_lock);
-                       break;
-               default:
-                       panic("Unknown type of kernel message!");
-       }
-       /* since we touched memory the other core will touch (the lock), we don't
-        * need an wmb_f() */
-       /* if we're sending a routine message locally, we don't want/need an IPI */
-       if ((dst != k_msg->srcid) || (type == KMSG_IMMEDIATE))
-               send_ipi(get_hw_coreid(dst), I_KERNEL_MSG);
-       return 0;
-}
-
-/* Helper function.  Returns 0 if the list was empty. */
-static kernel_message_t *get_next_amsg(struct kernel_msg_list *list_head,
-                                       spinlock_t *list_lock)
-{
-       kernel_message_t *k_msg;
-       spin_lock_irqsave(list_lock);
-       k_msg = STAILQ_FIRST(list_head);
-       if (k_msg)
-               STAILQ_REMOVE_HEAD(list_head, link);
-       spin_unlock_irqsave(list_lock);
-       return k_msg;
-}
-
-/* Kernel message handler.  Extensive documentation is in
- * Documentation/kernel_messages.txt.
- *
- * In general: this processes immediate messages, then routine messages.
- * Routine messages might not return (__startcore, etc), so we need to be
- * careful about a few things.
- *
- * Note that all of this happens from interrupt context, and interrupts are
- * currently disabled for this gate.  Interrupts need to be disabled so that the
- * self-ipi doesn't preempt the execution of this kernel message. */
-void __kernel_message(struct trapframe *tf, void *data)
+/* Declared in i686/arch.h */
+void send_ipi(uint32_t os_coreid, uint8_t vector)
 {
-       per_cpu_info_t *myinfo = &per_cpu_info[core_id()];
-       kernel_message_t msg_cp, *k_msg;
-
-       lapic_send_eoi();
-       while (1) { // will break out when there are no more messages
-               /* Try to get an immediate message.  Exec and free it. */
-               k_msg = get_next_amsg(&myinfo->immed_amsgs, &myinfo->immed_amsg_lock);
-               if (k_msg) {
-                       assert(k_msg->pc);
-                       k_msg->pc(tf, k_msg->srcid, k_msg->arg0, k_msg->arg1, k_msg->arg2);
-                       kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-               } else { // no immediate, might be a routine
-                       if (in_kernel(tf))
-                               return; // don't execute routine msgs if we were in the kernel
-                       k_msg = get_next_amsg(&myinfo->routine_amsgs,
-                                             &myinfo->routine_amsg_lock);
-                       if (!k_msg) // no routines either
-                               return;
-                       /* copy in, and then free, in case we don't return */
-                       msg_cp = *k_msg;
-                       kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-                       /* make sure an IPI is pending if we have more work */
-                       /* techincally, we don't need to lock when checking */
-                       if (!STAILQ_EMPTY(&myinfo->routine_amsgs) &&
-                              !ipi_is_pending(I_KERNEL_MSG))
-                               send_self_ipi(I_KERNEL_MSG);
-                       /* Execute the kernel message */
-                       assert(msg_cp.pc);
-                       assert(msg_cp.dstid == core_id());
-                       /* TODO: when batching syscalls, this should be reread from cur_tf*/
-                       msg_cp.pc(tf, msg_cp.srcid, msg_cp.arg0, msg_cp.arg1, msg_cp.arg2);
-               }
-       }
-}
-
-/* Runs any outstanding routine kernel messages from within the kernel.  Will
- * make sure immediates still run first (or when they arrive, if processing a
- * bunch of these messages).  This will disable interrupts, and restore them to
- * whatever state you left them. */
-void process_routine_kmsg(struct trapframe *tf)
-{
-       per_cpu_info_t *myinfo = &per_cpu_info[core_id()];
-       kernel_message_t msg_cp, *k_msg;
-       int8_t irq_state = 0;
-
-       disable_irqsave(&irq_state);
-       /* If we were told what our TF was, use that.  o/w, go with current_tf. */
-       tf = tf ? tf : current_tf;
-       while (1) {
-               /* normally, we want ints disabled, so we don't have an empty self-ipi
-                * for every routine message. (imagine a long list of routines).  But we
-                * do want immediates to run ahead of routines.  This enabling should
-                * work (might not in some shitty VMs).  Also note we can receive an
-                * extra self-ipi for routine messages before we turn off irqs again.
-                * Not a big deal, since we will process it right away. 
-                * TODO: consider calling __kernel_message() here. */
-               if (!STAILQ_EMPTY(&myinfo->immed_amsgs)) {
-                       enable_irq();
-                       cpu_relax();
-                       disable_irq();
-               }
-               k_msg = get_next_amsg(&myinfo->routine_amsgs,
-                                     &myinfo->routine_amsg_lock);
-               if (!k_msg) {
-                       enable_irqsave(&irq_state);
-                       return;
-               }
-               /* copy in, and then free, in case we don't return */
-               msg_cp = *k_msg;
-               kmem_cache_free(kernel_msg_cache, (void*)k_msg);
-               /* make sure an IPI is pending if we have more work */
-               if (!STAILQ_EMPTY(&myinfo->routine_amsgs) &&
-                      !ipi_is_pending(I_KERNEL_MSG))
-                       send_self_ipi(I_KERNEL_MSG);
-               /* Execute the kernel message */
-               assert(msg_cp.pc);
-               assert(msg_cp.dstid == core_id());
-               msg_cp.pc(tf, msg_cp.srcid, msg_cp.arg0, msg_cp.arg1, msg_cp.arg2);
+       int hw_coreid = get_hw_coreid(os_coreid);
+       if (hw_coreid == -1) {
+               warn("Unmapped OS coreid!\n");
+               return;
        }
+       __send_ipi(hw_coreid, vector);
 }
index dc610aa..0632e9c 100644 (file)
@@ -7,6 +7,8 @@
 /* Model Specific Registers */
 #define IA32_APIC_BASE                         0x1b
 #define IA32_FEATURE_CONTROL           0x3a
+#define IA32_MISC_ENABLE                       0x1a0
+
 #define IA32_MTRR_DEF_TYPE                     0x2ff
 #define IA32_MTRR_PHYSBASE0                    0x200
 #define IA32_MTRR_PHYSMASK0                    0x201
index 836ce9d..7b8cc97 100644 (file)
@@ -27,3 +27,5 @@ KERN_ARCH_SRCFILES := $(KERN_ARCH_SRC_DIR)/boot.S \
                       $(KERN_ARCH_SRC_DIR)/env.c \
                       $(KERN_ARCH_SRC_DIR)/init.c \
                       $(KERN_ARCH_SRC_DIR)/kdebug.c \
+                      $(KERN_ARCH_SRC_DIR)/fpu.c \
+                      $(KERN_ARCH_SRC_DIR)/softfloat.c \
index 746e696..240b03b 100644 (file)
@@ -10,7 +10,7 @@
 #include <arch/time.h>
 
 /* Arch Constants */
-#define HW_CACHE_ALIGN 64
+#define ARCH_CL_SIZE 64
 
 #ifdef __riscv64
 # define KERN64
@@ -52,32 +52,42 @@ read_tsc(void)
        return t;
 }
 
+/* Continuing the poor tradition of x86 opcode functions... */
+static __inline uint64_t
+read_tscp(void)
+{
+       return read_tsc();
+}
+
 static __inline uint64_t 
 read_tsc_serialized(void)
 {
-       uint64_t tsc;
-  mb();
-       tsc = read_tsc();
        mb();
-       return tsc;
+       return read_tsc();
 }
 
-static __inline void
+static __inline uintptr_t
 enable_irq(void)
 {
-  asm volatile("ei");
+       return setpcr(PCR_SR, SR_ET);
 }
 
-static __inline void
+static __inline uintptr_t
 disable_irq(void)
 {
-  asm volatile("di");
+       return clearpcr(PCR_SR, SR_ET);
+}
+
+static __inline void
+restore_irq(uintptr_t val)
+{
+       mtpcr(PCR_SR, val);
 }
 
 static __inline int
 irq_is_enabled(void)
 {
-  return mfpcr(PCR_SR) & SR_ET;
+       return mfpcr(PCR_SR) & SR_ET;
 }
 
 static __inline void
@@ -158,9 +168,8 @@ cache_flush(void)
 static __inline void
 reboot(void)
 {
-  extern void fesvr_die();
-       fesvr_die();
-       while(1);
+       extern void cputchar(int ch);
+       cputchar(0);
 }
 
 extern void cpu_halt(void);
index ba5f307..d4b8ac6 100644 (file)
@@ -9,10 +9,12 @@ bool atomic_cas(atomic_t *addr, long exp_val, long new_val)
                return 0;
        
   #define K 17
-       static spinlock_t cas_locks[K*HW_CACHE_ALIGN/sizeof(spinlock_t)];
+       /* TODO: not sure if this initialization works. */
+       static spinlock_t cas_locks[K*ARCH_CL_SIZE/sizeof(spinlock_t)] =
+                         {SPINLOCK_INITIALIZER_IRQSAVE};
 
   uintptr_t bucket = (uintptr_t)addr / sizeof(uintptr_t) % K;
-       spinlock_t* lock = &cas_locks[bucket*HW_CACHE_ALIGN/sizeof(spinlock_t)];
+       spinlock_t* lock = &cas_locks[bucket*ARCH_CL_SIZE/sizeof(spinlock_t)];
        
        bool retval = 0;
        spin_lock_irqsave(lock);
@@ -36,10 +38,12 @@ bool atomic_cas_u32(uint32_t *addr, uint32_t exp_val, uint32_t new_val)
                return 0;
        
   #define K 17
-       static spinlock_t cas_locks[K*HW_CACHE_ALIGN/sizeof(spinlock_t)];
+       /* TODO: not sure if this initialization works. */
+       static spinlock_t cas_locks[K*ARCH_CL_SIZE/sizeof(spinlock_t)] =
+                         {SPINLOCK_INITIALIZER_IRQSAVE};
 
   uintptr_t bucket = (uintptr_t)addr / sizeof(uintptr_t) % K;
-       spinlock_t* lock = &cas_locks[bucket*HW_CACHE_ALIGN/sizeof(spinlock_t)];
+       spinlock_t* lock = &cas_locks[bucket*ARCH_CL_SIZE/sizeof(spinlock_t)];
        
        bool retval = 0;
        spin_lock_irqsave(lock);
index fd94e9e..0d35bc8 100644 (file)
@@ -112,20 +112,23 @@ static inline uint32_t spin_trylock(spinlock_t* lock)
        return __sync_fetch_and_or(&lock->rlock, 1);
 }
 
-static inline void spin_lock(spinlock_t *lock)
+static inline void __spin_lock(spinlock_t *lock)
 {
-       while(spin_trylock(lock))
-               while(lock->rlock);
+       do
+       {
+               while (lock->rlock)
+                       ;
+       } while (spin_trylock(lock));
        mb();
 }
 
-static inline void spin_unlock(spinlock_t *lock)
+static inline void __spin_unlock(spinlock_t *lock)
 {
        mb();
        lock->rlock = 0;
 }
 
-static inline void spinlock_init(spinlock_t *lock)
+static inline void __spinlock_init(spinlock_t *lock)
 {
        lock->rlock = 0;
 }
index 14af7f1..fb41ecd 100644 (file)
@@ -16,7 +16,7 @@
 // entry point
 ///////////////////////////////////////////////////////////////////
 
-#define PCR0 (SR_S | SR_ET | SR_SX)
+#define PCR0 (SR_S | SR_S64 | (1 << (IRQ_IPI + SR_IM_SHIFT)))
 .text
 
 .global _start
@@ -40,7 +40,7 @@ _start:
 
   // terminate frame pointer for backtracing and set up stack
   li     s9, 0
-  la     sp, bootstacktop
+  la     sp, percore_stacks + KSTKSIZE
   li     t1, KERN_LOAD_ADDR
   sub    sp, sp, t1
 
@@ -64,11 +64,21 @@ _start:
   // relocate stack and call into C code using absolute jump, not pc-relative
   move   a0, s0
   move   a1, s1
-  la     sp, bootstacktop
+  la     sp, percore_stacks + KSTKSIZE
   la     t0, cmain
   jr     t0
 
 notcore0:
+  // wait for core 0 to boot
+  la     t2, num_cpus_booted - KERN_LOAD_ADDR
+1:lw     t3, 0(t2)
+  beqz   t3, 1b
+
+  // if for some reason coreid >= num_cpus, don't boot this core
+  la     t2, num_cpus - KERN_LOAD_ADDR
+  lw     t2, 0(t2)
+1:bgeu   t0, t2, 1b
+
   // set up stack: sp = percoore_stacks+(core_id()+1)*KSTKSIZE
   la     sp, percore_stacks
   add    t0, t0, 1
@@ -113,12 +123,6 @@ l1pt:
 l2pt:
   .space  PGSIZE
 
-  .space  KSTKSIZE
-  .global bootstacktop
-bootstacktop:
-
-.bss
-  .align  PGSHIFT
   .global percore_stacks
 percore_stacks:
   .space  KSTKSIZE*MAX_NUM_CPUS
index 8cba973..29c7b46 100644 (file)
@@ -1,93 +1,61 @@
 #include <arch/console.h>
+#include <console.h>
 #include <pmap.h>
 #include <atomic.h>
+#include <smp.h>
+#include <kmalloc.h>
+#include <monitor.h>
+#include <process.h>
 
-long
-fesvr_syscall(long n, long a0, long a1, long a2, long a3)
+int cons_get_any_char(void)
 {
-  static volatile uint64_t magic_mem[8];
-
-  static spinlock_t lock = SPINLOCK_INITIALIZER;
-  spin_lock_irqsave(&lock);
-
-  magic_mem[0] = n;
-  magic_mem[1] = a0;
-  magic_mem[2] = a1;
-  magic_mem[3] = a2;
-  magic_mem[4] = a3;
-
-  asm volatile ("cflush; fence");
-
-  mtpcr(PCR_TOHOST, PADDR(magic_mem));
-  while(mfpcr(PCR_FROMHOST) == 0);
-
-  long ret = magic_mem[0];
-
-  spin_unlock_irqsave(&lock);
-  return ret;
-}
-
-void
-fesvr_die()
-{
-       fesvr_syscall(FESVR_SYS_exit, 0, 0, 0, 0);
+       assert(0);
 }
 
 void
 cons_init(void)
 {
+       while (mtpcr(PCR_TOHOST, 0x0180000000000000));
 }
 
 // `High'-level console I/O.  Used by readline and cprintf.
 
 void
-cputbuf(const char* buf, int len)
+cputbuf(const char* str, int len)
 {
-       fesvr_syscall(FESVR_SYS_write, 1, PADDR((uintptr_t)buf), len, 0);
+       for (int i = 0; i < len; i++)
+               cputchar(str[i]);
 }
 
-// Low-level console I/O
-
-void
-cons_putc(int c)
+void poll_keyboard()
 {
-       if(c == '\b' || c == 0x7F)
-       {
-               char buf[3] = {'\b', ' ', '\b'};
-               cputbuf(buf,3);
-       }
+       uintptr_t fh = mtpcr(PCR_FROMHOST, 0);
+       if (fh == 0)
+               return;
+       assert((fh >> 56) == 0x01);
+
+       char c = fh;
+       if (c == 'G')
+               send_kernel_message(core_id(), __run_mon, 0, 0, 0, KMSG_ROUTINE);
        else
-       {
-               char ch = c;
-               cputbuf(&ch,1);
-       }
+               send_kernel_message(core_id(), __cons_add_char, (long)&cons_buf,
+                                   (long)c, 0, KMSG_ROUTINE);
+       cons_init();
 }
 
+// Low-level console I/O
+
 void
 cputchar(int c)
 {
-       char ch = c;
-       cputbuf(&ch,1);
-}
-
-int
-cons_getc()
-{
-       char ch;
-       uintptr_t paddr = PADDR((uintptr_t)&ch);
-       long ret = fesvr_syscall(FESVR_SYS_read, 0, paddr, 1, 0);
-       if(ch == 0x7F)
-               ch = '\b';
-       return ret <= 0 ? 0 : ch;
+       while (mtpcr(PCR_TOHOST, 0x0101000000000000 | (unsigned char)c));
 }
 
 int
 getchar(void)
 {
-       int c;
-
-       while ((c = cons_getc()) == 0)
-               /* do nothing */;
+       char c;
+       kb_get_from_buf(&cons_buf, &c, 1);
        return c;
 }
 
index 3d54d5b..a9e8683 100644 (file)
 #define CRT_SIZE       (CRT_ROWS * CRT_COLS)
 
 void cons_init(void);
-void cons_putc(int c);
-int cons_getc(void);
-
-#define        FESVR_SYS_exit  1
-#define        FESVR_SYS_getpid        20
-#define        FESVR_SYS_kill  37
-#define        FESVR_SYS_read  3
-#define        FESVR_SYS_write 4
-#define        FESVR_SYS_open  5
-#define        FESVR_SYS_close 6
-#define        FESVR_SYS_lseek 19
-#define        FESVR_SYS_brk           17
-#define        FESVR_SYS_link  9
-#define        FESVR_SYS_unlink        10
-#define        FESVR_SYS_chdir 12
-#define FESVR_SYS_stat 18
-#define FESVR_SYS_fstat        28
-#define        FESVR_SYS_lstat 84
-#define        FESVR_SYS_pread 180
-#define        FESVR_SYS_pwrite 181
-#define FESVR_SYS_getmainvars 201
-
-long fesvr_syscall(long n, long a0, long a1, long a2, long a3);
-void fesvr_die();
+/* Returns any available character, or 0 for none (legacy helper) */
+int cons_get_any_char(void);
+void poll_keyboard();
 
 #endif /* _CONSOLE_H_ */
index 066c05b..83f3641 100644 (file)
@@ -15,7 +15,13 @@ static_asserts_can_go_here()
 void
 print_cpuinfo(void)
 {
-       cprintf("CPU Info: Not Just Any Other RISC-V Core (TM)\n");
+       int id = mfpcr(PCR_IMPL);
+       const char* name = "(unknown implementation)";
+       if (id == 1)
+         name = "ISA Simulator";
+       else if (id == 2)
+         name = "Rocket64";
+       cprintf("CPU Info: RISC-V %s\n", name);
 }
 
 void show_mapping(uintptr_t start, size_t size)
index c301061..4707db5 100644 (file)
@@ -5,12 +5,13 @@
 #ifdef __riscv64
 # define STORE    sd
 # define LOAD     ld
-# define REGBYTES 8
+# define LOG_REGBYTES 3
 #else
 # define STORE    sw
 # define LOAD     lw
-# define REGBYTES 4
+# define LOG_REGBYTES 2
 #endif
+#define REGBYTES (1 << LOG_REGBYTES)
 
   .text
   .ent    save_kernel_tf_asm
@@ -32,8 +33,8 @@ save_kernel_tf_asm:
   STORE  t0,32*REGBYTES(a0)
 
   # set EPC to this function's return address
-  STORE  ra,33*REGBYTES(x2)
-
+  STORE  ra,33*REGBYTES(a0)
+  ret
   .end  save_kernel_tf_asm
 
   .text
@@ -41,7 +42,7 @@ save_kernel_tf_asm:
   .global pop_kernel_tf
 pop_kernel_tf:
   LOAD  t0,32*REGBYTES(a0)
-  LOAD  ra,33*REGBYTES(x2)
+  LOAD  ra,33*REGBYTES(a0)
 
   LOAD  s0,20*REGBYTES(a0)
   LOAD  s1,21*REGBYTES(a0)
@@ -71,7 +72,11 @@ save_tf:  # write the trap frame onto the stack
 env_pop_tf:  # write the trap frame onto the stack
   # restore gprs
   LOAD  t0,32*REGBYTES(a0)  # restore sr (should disable interrupts)
-  mtpcr  t0,ASM_CR(PCR_SR)
+  mfpcr t1, ASM_CR(PCR_SR)
+  andi  t1, t1, ~(SR_PS | SR_EF | SR_U64)
+  andi  t0, t0, SR_PS | SR_EF | SR_U64
+  or    t0, t0, t1
+  mtpcr t0, ASM_CR(PCR_SR)
 
   LOAD  x1,1*REGBYTES(a0)
   mtpcr  x1,ASM_CR(PCR_K0)
@@ -130,11 +135,12 @@ trap_entry:
   bnez  x1, 1f
 
   # otherwise, start at the top of the per-core stack
-  la    x2, percore_stacks - SIZEOF_TRAPFRAME_T
+  la    x2, core_stacktops
   mfpcr x1, ASM_CR(PCR_COREID)
-  add   x1, x1, 1
-  sll   x1, x1, KSTKSHIFT
+  sll   x1, x1, LOG_REGBYTES
   add   x2, x2, x1
+  LOAD  x2, 0(x2)
+  add   x2, x2, -SIZEOF_TRAPFRAME_T
 
 1:# save gprs
   STORE  x3,3*REGBYTES(x2)
@@ -182,16 +188,6 @@ trap_entry:
   mfpcr  x3,ASM_CR(PCR_CAUSE)        # cause
   STORE  x3,35*REGBYTES(x2)
 
-  # get faulting insn, if it wasn't a fetch-related trap
-  li    x5, CAUSE_MISALIGNED_FETCH
-  li    x6, CAUSE_FAULT_FETCH
-  beq   x3, x5, 1f
-  beq   x3, x6, 1f
-  lh    x3,0(x4)
-  lh    x4,2(x4)
-  sh    x3,  36*REGBYTES(x2)
-  sh    x4,2+36*REGBYTES(x2)
-1:
   li    s9, 0
   move  sp, x2
   move  a0, x2
@@ -199,8 +195,11 @@ trap_entry:
   .end  trap_entry
 
   .global  cpu_halt
+  .global  after_cpu_halt
   .ent  cpu_halt
 cpu_halt:
+  setpcr ASM_CR(PCR_SR), SR_ET
 1:b     1b   # handle_ipi can advance the PC to break out of this loop.
   ret
+after_cpu_halt:
   .end  cpu_halt
index 0f9f3e8..a2ed60a 100644 (file)
@@ -14,6 +14,7 @@ env_push_ancillary_state(env_t* e)
 void
 save_fp_state(ancillary_state_t* silly)
 {
+       return; // don't save FP state for now
        uintptr_t sr = mfpcr(PCR_SR);
        mtpcr(PCR_SR, sr | SR_EF);
 
@@ -65,6 +66,7 @@ env_pop_ancillary_state(env_t* e)
 void
 restore_fp_state(ancillary_state_t* silly)
 {
+       return; // don't restore FP state for now
        uintptr_t sr = mfpcr(PCR_SR);
        mtpcr(PCR_SR, sr | SR_EF);
 
@@ -121,7 +123,7 @@ user_mem_walk_recursive(env_t* e, uintptr_t start, size_t len,
 
        for(uintptr_t idx = start_idx; idx <= end_idx; idx++)
        {
-               uintptr_t pgaddr = ROUNDDOWN(start, pgsize) + idx*pgsize;
+               uintptr_t pgaddr = ROUNDDOWN(start, pgsize) + (idx-start_idx)*pgsize;
                pte_t* pte = &pt[idx];
 
                if(*pte & PTE_T)
diff --git a/kern/arch/riscv/fpu.c b/kern/arch/riscv/fpu.c
new file mode 100644 (file)
index 0000000..e314278
--- /dev/null
@@ -0,0 +1,129 @@
+#include <arch/trap.h>
+#include <smp.h>
+#include <umem.h>
+#include <arch/softfloat.h>
+
+static uint32_t ls(uint64_t* addr)
+{
+       uint32_t r;
+       asm ("fld f0, %1; mftx.s %0, f0" : "=r"(r) : "m"(*addr));
+       return r;
+}
+
+static void ss(uint64_t* addr, uint32_t val)
+{
+       asm ("mxtf.s f0, %0; fsd f0, %1" : : "r"(val), "m"(*addr));
+}
+
+static int emulate_fpu_silly(struct trapframe* state, ancillary_state_t* silly)
+{
+       int insn;
+       if (memcpy_from_user(current, &insn, (void*)state->epc, 4))
+       {
+               state->cause = CAUSE_FAULT_FETCH;
+               handle_trap(state);
+       }
+
+       #define DECLARE_INSN(name, match, mask) bool is_##name = (insn & mask) == match;
+       #include <arch/opcodes.h>
+       #undef DECLARE_INSN
+
+       int rd  = (insn >> 27) & 0x1f;
+       int rs1 = (insn >> 22) & 0x1f;
+       int rs2 = (insn >> 17) & 0x1f;
+       int rs3 = (insn >> 12) & 0x1f;
+
+       int imm = (insn << 10) >> 20;
+       int bimm = ((insn >> 10) & 0x7f) | ((insn & 0xf8000000) >> 20);
+
+       void* load_address = (void*)(state->gpr[rs1] + imm);
+       void* store_address = (void*)(state->gpr[rs1] + bimm);
+
+       softfloat_t sf;
+       sf.float_rounding_mode = silly->fsr >> 5;
+       sf.float_exception_flags = silly->fsr & 0x1f;
+
+       if (is_fsqrt_s)
+               ss(&silly->fpr[rd], float32_sqrt(&sf, ls(&silly->fpr[rs1])));
+       else if (is_fsqrt_d)
+               silly->fpr[rd] = float64_sqrt(&sf, silly->fpr[rs1]);
+       else if (is_fdiv_s)
+               ss(&silly->fpr[rd], float32_div(&sf, ls(&silly->fpr[rs1]), ls(&silly->fpr[rs2])));
+       else if (is_fdiv_d)
+               silly->fpr[rd] = float64_div(&sf, silly->fpr[rs1], silly->fpr[rs2]);
+       /* Eventually, we will emulate the full FPU, including the below insns
+       else if (is_mffsr)
+       {
+               // use sf instead of silly->fsr
+               state->gpr[rd] = silly->fsr;
+       }
+       else if (is_mtfsr)
+       {
+               // use sf instead of silly->fsr
+               int temp = silly->fsr;
+               silly->fsr = state->gpr[rs1] & 0xFF;
+               state->gpr[rd] = silly->fsr;
+       }
+       else if (is_fld)
+       {
+               uint64_t dest;
+               if (!memcpy_from_user(current, &dest, load_address, sizeof(dest)))
+               {
+                       state->cause = CAUSE_FAULT_LOAD;
+                       state->badvaddr = (long)load_address;
+                       handle_trap(state);
+               }
+               silly->fpr[rd] = dest;
+       }
+       else if (is_flw)
+       {
+               uint32_t dest;
+               if (!memcpy_from_user(current, &dest, load_address, sizeof(dest)))
+               {
+                       state->cause = CAUSE_FAULT_LOAD;
+                       state->badvaddr = (long)load_address;
+                       handle_trap(state);
+               }
+               silly->fpr[rd] = dest;
+       }
+       else if (is_fsd)
+       {
+               if (!memcpy_to_user(current, store_address, &silly->fpr[rs2], sizeof(uint64_t)))
+               {
+                       state->cause = CAUSE_FAULT_STORE;
+                       state->badvaddr = (long)store_address;
+                       handle_trap(state);
+               }
+       }
+       else if (is_flw)
+       {
+               if (!memcpy_to_user(current, store_address, &silly->fpr[rs2], sizeof(uint32_t)))
+               {
+                       state->cause = CAUSE_FAULT_STORE;
+                       state->badvaddr = (long)store_address;
+                       handle_trap(state);
+               }
+       }
+       */
+       else
+         return 1;
+       
+       silly->fsr = sf.float_rounding_mode << 5 | sf.float_exception_flags;
+       return 0;
+}
+
+/* For now we can only emulate missing compute insns, not the whole FPU */
+int emulate_fpu(struct trapframe* state)
+{
+       if (!(state->sr & SR_EF))
+       {
+               state->cause = CAUSE_FP_DISABLED;
+               handle_trap(state);
+       }
+
+       ancillary_state_t fp_state;
+       save_fp_state(&fp_state);
+       int code = emulate_fpu_silly(state, &fp_state);
+       restore_fp_state(&fp_state);
+       return code;
+}
index cade583..d810da7 100644 (file)
@@ -2,6 +2,7 @@
 
 #include <smp.h>
 #include <arch/init.h>
+#include <arch/console.h>
 
 void arch_init()
 {              
diff --git a/kern/arch/riscv/opcodes.h b/kern/arch/riscv/opcodes.h
new file mode 100644 (file)
index 0000000..519a75f
--- /dev/null
@@ -0,0 +1,272 @@
+DECLARE_INSN(movn, 0x6f7, 0x1ffff)
+DECLARE_INSN(vfsstw, 0x150f, 0x1ffff)
+DECLARE_INSN(remuw, 0x7bb, 0x1ffff)
+DECLARE_INSN(fmin_d, 0x180d3, 0x1ffff)
+DECLARE_INSN(vlsthu, 0x128b, 0x1ffff)
+DECLARE_INSN(c_swsp, 0x8, 0x1f)
+DECLARE_INSN(bltu, 0x363, 0x3ff)
+DECLARE_INSN(vlsegstwu, 0xb0b, 0xfff)
+DECLARE_INSN(movz, 0x2f7, 0x1ffff)
+DECLARE_INSN(fcvt_lu_s, 0x9053, 0x3ff1ff)
+DECLARE_INSN(fence_l_cv, 0x32f, 0x3ff)
+DECLARE_INSN(fmin_s, 0x18053, 0x1ffff)
+DECLARE_INSN(c_lw0, 0x12, 0x801f)
+DECLARE_INSN(slliw, 0x9b, 0x3f83ff)
+DECLARE_INSN(lb, 0x3, 0x3ff)
+DECLARE_INSN(vlwu, 0x30b, 0x3fffff)
+DECLARE_INSN(fcvt_d_l, 0xc0d3, 0x3ff1ff)
+DECLARE_INSN(lh, 0x83, 0x3ff)
+DECLARE_INSN(fcvt_d_w, 0xe0d3, 0x3ff1ff)
+DECLARE_INSN(lw, 0x103, 0x3ff)
+DECLARE_INSN(add, 0x33, 0x1ffff)
+DECLARE_INSN(fcvt_d_s, 0x100d3, 0x3ff1ff)
+DECLARE_INSN(fence_g_v, 0x2af, 0x3ff)
+DECLARE_INSN(mfpcr, 0x17b, 0x7c1ffff)
+DECLARE_INSN(c_fsd, 0x18, 0x1f)
+DECLARE_INSN(fmax_d, 0x190d3, 0x1ffff)
+DECLARE_INSN(bne, 0xe3, 0x3ff)
+DECLARE_INSN(rdcycle, 0x277, 0x7ffffff)
+DECLARE_INSN(fcvt_s_d, 0x11053, 0x3ff1ff)
+DECLARE_INSN(vlh, 0x8b, 0x3fffff)
+DECLARE_INSN(bgeu, 0x3e3, 0x3ff)
+DECLARE_INSN(vflstd, 0x158b, 0x1ffff)
+DECLARE_INSN(c_li, 0x0, 0x1f)
+DECLARE_INSN(di, 0xfb, 0x7ffffff)
+DECLARE_INSN(sltiu, 0x193, 0x3ff)
+DECLARE_INSN(mtpcr, 0x1fb, 0xf801ffff)
+DECLARE_INSN(vlb, 0xb, 0x3fffff)
+DECLARE_INSN(stop, 0x177, 0xffffffff)
+DECLARE_INSN(vld, 0x18b, 0x3fffff)
+DECLARE_INSN(c_slli, 0x19, 0x1c1f)
+DECLARE_INSN(break, 0xf7, 0xffffffff)
+DECLARE_INSN(cflush, 0x2fb, 0xffffffff)
+DECLARE_INSN(fcvt_s_w, 0xe053, 0x3ff1ff)
+DECLARE_INSN(vflstw, 0x150b, 0x1ffff)
+DECLARE_INSN(mul, 0x433, 0x1ffff)
+DECLARE_INSN(c_lw, 0xa, 0x1f)
+DECLARE_INSN(vlw, 0x10b, 0x3fffff)
+DECLARE_INSN(vssegstw, 0x90f, 0xfff)
+DECLARE_INSN(amominu_d, 0x19ab, 0x1ffff)
+DECLARE_INSN(c_sdsp, 0x6, 0x1f)
+DECLARE_INSN(utidx, 0x1f7, 0x7ffffff)
+DECLARE_INSN(srli, 0x293, 0x3f03ff)
+DECLARE_INSN(c_srli, 0x819, 0x1c1f)
+DECLARE_INSN(c_ldsp, 0x4, 0x1f)
+DECLARE_INSN(c_flw, 0x14, 0x1f)
+DECLARE_INSN(c_srai32, 0x1419, 0x1c1f)
+DECLARE_INSN(amominu_w, 0x192b, 0x1ffff)
+DECLARE_INSN(divuw, 0x6bb, 0x1ffff)
+DECLARE_INSN(mulw, 0x43b, 0x1ffff)
+DECLARE_INSN(vssegstd, 0x98f, 0xfff)
+DECLARE_INSN(srlw, 0x2bb, 0x1ffff)
+DECLARE_INSN(vssegstb, 0x80f, 0xfff)
+DECLARE_INSN(mftx_d, 0x1c0d3, 0x3fffff)
+DECLARE_INSN(div, 0x633, 0x1ffff)
+DECLARE_INSN(c_ld, 0x9, 0x1f)
+DECLARE_INSN(mftx_s, 0x1c053, 0x3fffff)
+DECLARE_INSN(vssegsth, 0x88f, 0xfff)
+DECLARE_INSN(vvcfgivl, 0xf3, 0x3ff)
+DECLARE_INSN(j, 0x67, 0x7f)
+DECLARE_INSN(ei, 0x7b, 0x7ffffff)
+DECLARE_INSN(fence, 0x12f, 0x3ff)
+DECLARE_INSN(vsw, 0x10f, 0x3fffff)
+DECLARE_INSN(fnmsub_s, 0x4b, 0x1ff)
+DECLARE_INSN(vfssegstd, 0xd8f, 0xfff)
+DECLARE_INSN(fcvt_l_s, 0x8053, 0x3ff1ff)
+DECLARE_INSN(fle_s, 0x17053, 0x1ffff)
+DECLARE_INSN(vsb, 0xf, 0x3fffff)
+DECLARE_INSN(mffsr, 0x1d053, 0x7ffffff)
+DECLARE_INSN(fdiv_s, 0x3053, 0x1f1ff)
+DECLARE_INSN(vlstbu, 0x120b, 0x1ffff)
+DECLARE_INSN(vsetvl, 0x2f3, 0x3fffff)
+DECLARE_INSN(fle_d, 0x170d3, 0x1ffff)
+DECLARE_INSN(fence_i, 0xaf, 0x3ff)
+DECLARE_INSN(vlsegbu, 0x220b, 0x1ffff)
+DECLARE_INSN(fnmsub_d, 0xcb, 0x1ff)
+DECLARE_INSN(addw, 0x3b, 0x1ffff)
+DECLARE_INSN(sll, 0xb3, 0x1ffff)
+DECLARE_INSN(xor, 0x233, 0x1ffff)
+DECLARE_INSN(sub, 0x10033, 0x1ffff)
+DECLARE_INSN(eret, 0x27b, 0xffffffff)
+DECLARE_INSN(blt, 0x263, 0x3ff)
+DECLARE_INSN(vsstw, 0x110f, 0x1ffff)
+DECLARE_INSN(mtfsr, 0x1f053, 0x3fffff)
+DECLARE_INSN(vssth, 0x108f, 0x1ffff)
+DECLARE_INSN(rem, 0x733, 0x1ffff)
+DECLARE_INSN(srliw, 0x29b, 0x3f83ff)
+DECLARE_INSN(lui, 0x37, 0x7f)
+DECLARE_INSN(vsstb, 0x100f, 0x1ffff)
+DECLARE_INSN(fcvt_s_lu, 0xd053, 0x3ff1ff)
+DECLARE_INSN(vsstd, 0x118f, 0x1ffff)
+DECLARE_INSN(addi, 0x13, 0x3ff)
+DECLARE_INSN(vfmst, 0x1173, 0x1ffff)
+DECLARE_INSN(mulh, 0x4b3, 0x1ffff)
+DECLARE_INSN(fmul_s, 0x2053, 0x1f1ff)
+DECLARE_INSN(vlsegsthu, 0xa8b, 0xfff)
+DECLARE_INSN(srai, 0x10293, 0x3f03ff)
+DECLARE_INSN(amoand_d, 0x9ab, 0x1ffff)
+DECLARE_INSN(flt_d, 0x160d3, 0x1ffff)
+DECLARE_INSN(sraw, 0x102bb, 0x1ffff)
+DECLARE_INSN(fmul_d, 0x20d3, 0x1f1ff)
+DECLARE_INSN(ld, 0x183, 0x3ff)
+DECLARE_INSN(ori, 0x313, 0x3ff)
+DECLARE_INSN(flt_s, 0x16053, 0x1ffff)
+DECLARE_INSN(addiw, 0x1b, 0x3ff)
+DECLARE_INSN(amoand_w, 0x92b, 0x1ffff)
+DECLARE_INSN(feq_s, 0x15053, 0x1ffff)
+DECLARE_INSN(fsgnjx_d, 0x70d3, 0x1ffff)
+DECLARE_INSN(sra, 0x102b3, 0x1ffff)
+DECLARE_INSN(c_lwsp, 0x5, 0x1f)
+DECLARE_INSN(bge, 0x2e3, 0x3ff)
+DECLARE_INSN(c_add3, 0x1c, 0x31f)
+DECLARE_INSN(sraiw, 0x1029b, 0x3f83ff)
+DECLARE_INSN(vssegd, 0x218f, 0x1ffff)
+DECLARE_INSN(srl, 0x2b3, 0x1ffff)
+DECLARE_INSN(vfmts, 0x1973, 0x1ffff)
+DECLARE_INSN(fsgnjx_s, 0x7053, 0x1ffff)
+DECLARE_INSN(vfmsv, 0x973, 0x3fffff)
+DECLARE_INSN(feq_d, 0x150d3, 0x1ffff)
+DECLARE_INSN(fcvt_d_wu, 0xf0d3, 0x3ff1ff)
+DECLARE_INSN(vmts, 0x1873, 0x1ffff)
+DECLARE_INSN(or, 0x333, 0x1ffff)
+DECLARE_INSN(rdinstret, 0xa77, 0x7ffffff)
+DECLARE_INSN(fcvt_wu_d, 0xb0d3, 0x3ff1ff)
+DECLARE_INSN(subw, 0x1003b, 0x1ffff)
+DECLARE_INSN(jalr_c, 0x6b, 0x3ff)
+DECLARE_INSN(fmax_s, 0x19053, 0x1ffff)
+DECLARE_INSN(amomaxu_d, 0x1dab, 0x1ffff)
+DECLARE_INSN(c_slliw, 0x1819, 0x1c1f)
+DECLARE_INSN(jalr_j, 0x16b, 0x3ff)
+DECLARE_INSN(c_fld, 0x15, 0x1f)
+DECLARE_INSN(vlstw, 0x110b, 0x1ffff)
+DECLARE_INSN(vlsth, 0x108b, 0x1ffff)
+DECLARE_INSN(xori, 0x213, 0x3ff)
+DECLARE_INSN(jalr_r, 0xeb, 0x3ff)
+DECLARE_INSN(amomaxu_w, 0x1d2b, 0x1ffff)
+DECLARE_INSN(fcvt_wu_s, 0xb053, 0x3ff1ff)
+DECLARE_INSN(vlstb, 0x100b, 0x1ffff)
+DECLARE_INSN(vlstd, 0x118b, 0x1ffff)
+DECLARE_INSN(c_ld0, 0x8012, 0x801f)
+DECLARE_INSN(rdtime, 0x677, 0x7ffffff)
+DECLARE_INSN(andi, 0x393, 0x3ff)
+DECLARE_INSN(c_srli32, 0xc19, 0x1c1f)
+DECLARE_INSN(fsgnjn_d, 0x60d3, 0x1ffff)
+DECLARE_INSN(fnmadd_s, 0x4f, 0x1ff)
+DECLARE_INSN(jal, 0x6f, 0x7f)
+DECLARE_INSN(lwu, 0x303, 0x3ff)
+DECLARE_INSN(vlsegstbu, 0xa0b, 0xfff)
+DECLARE_INSN(c_beq, 0x10, 0x1f)
+DECLARE_INSN(vlhu, 0x28b, 0x3fffff)
+DECLARE_INSN(vfsstd, 0x158f, 0x1ffff)
+DECLARE_INSN(c_bne, 0x11, 0x1f)
+DECLARE_INSN(fnmadd_d, 0xcf, 0x1ff)
+DECLARE_INSN(fence_g_cv, 0x3af, 0x3ff)
+DECLARE_INSN(amoadd_d, 0x1ab, 0x1ffff)
+DECLARE_INSN(c_sw, 0xd, 0x1f)
+DECLARE_INSN(amomax_w, 0x152b, 0x1ffff)
+DECLARE_INSN(c_move, 0x2, 0x801f)
+DECLARE_INSN(fmovn, 0xef7, 0x1ffff)
+DECLARE_INSN(c_fsw, 0x16, 0x1f)
+DECLARE_INSN(c_j, 0x8002, 0x801f)
+DECLARE_INSN(mulhsu, 0x533, 0x1ffff)
+DECLARE_INSN(c_sd, 0xc, 0x1f)
+DECLARE_INSN(amoadd_w, 0x12b, 0x1ffff)
+DECLARE_INSN(fcvt_d_lu, 0xd0d3, 0x3ff1ff)
+DECLARE_INSN(amomax_d, 0x15ab, 0x1ffff)
+DECLARE_INSN(fcvt_w_d, 0xa0d3, 0x3ff1ff)
+DECLARE_INSN(fmovz, 0xaf7, 0x1ffff)
+DECLARE_INSN(c_or3, 0x21c, 0x31f)
+DECLARE_INSN(vmvv, 0x73, 0x3fffff)
+DECLARE_INSN(vfssegstw, 0xd0f, 0xfff)
+DECLARE_INSN(slt, 0x133, 0x1ffff)
+DECLARE_INSN(mxtf_d, 0x1e0d3, 0x3fffff)
+DECLARE_INSN(sllw, 0xbb, 0x1ffff)
+DECLARE_INSN(amoor_d, 0xdab, 0x1ffff)
+DECLARE_INSN(slti, 0x113, 0x3ff)
+DECLARE_INSN(remu, 0x7b3, 0x1ffff)
+DECLARE_INSN(flw, 0x107, 0x3ff)
+DECLARE_INSN(remw, 0x73b, 0x1ffff)
+DECLARE_INSN(sltu, 0x1b3, 0x1ffff)
+DECLARE_INSN(slli, 0x93, 0x3f03ff)
+DECLARE_INSN(c_and3, 0x31c, 0x31f)
+DECLARE_INSN(vssegw, 0x210f, 0x1ffff)
+DECLARE_INSN(amoor_w, 0xd2b, 0x1ffff)
+DECLARE_INSN(vsd, 0x18f, 0x3fffff)
+DECLARE_INSN(beq, 0x63, 0x3ff)
+DECLARE_INSN(fld, 0x187, 0x3ff)
+DECLARE_INSN(mxtf_s, 0x1e053, 0x3fffff)
+DECLARE_INSN(fsub_s, 0x1053, 0x1f1ff)
+DECLARE_INSN(and, 0x3b3, 0x1ffff)
+DECLARE_INSN(vtcfgivl, 0x1f3, 0x3ff)
+DECLARE_INSN(lbu, 0x203, 0x3ff)
+DECLARE_INSN(vf, 0x3f3, 0xf80003ff)
+DECLARE_INSN(vlsegstw, 0x90b, 0xfff)
+DECLARE_INSN(syscall, 0x77, 0xffffffff)
+DECLARE_INSN(fsgnj_s, 0x5053, 0x1ffff)
+DECLARE_INSN(c_addi, 0x1, 0x1f)
+DECLARE_INSN(vfmvv, 0x173, 0x3fffff)
+DECLARE_INSN(vlstwu, 0x130b, 0x1ffff)
+DECLARE_INSN(c_sub3, 0x11c, 0x31f)
+DECLARE_INSN(vsh, 0x8f, 0x3fffff)
+DECLARE_INSN(vlsegstb, 0x80b, 0xfff)
+DECLARE_INSN(vlsegstd, 0x98b, 0xfff)
+DECLARE_INSN(vflsegd, 0x258b, 0x1ffff)
+DECLARE_INSN(vflsegw, 0x250b, 0x1ffff)
+DECLARE_INSN(vlsegsth, 0x88b, 0xfff)
+DECLARE_INSN(fsgnj_d, 0x50d3, 0x1ffff)
+DECLARE_INSN(vflsegstw, 0xd0b, 0xfff)
+DECLARE_INSN(c_sub, 0x801a, 0x801f)
+DECLARE_INSN(mulhu, 0x5b3, 0x1ffff)
+DECLARE_INSN(fcvt_l_d, 0x80d3, 0x3ff1ff)
+DECLARE_INSN(vmsv, 0x873, 0x3fffff)
+DECLARE_INSN(vmst, 0x1073, 0x1ffff)
+DECLARE_INSN(fadd_d, 0xd3, 0x1f1ff)
+DECLARE_INSN(fcvt_s_wu, 0xf053, 0x3ff1ff)
+DECLARE_INSN(rdnpc, 0x26b, 0x7ffffff)
+DECLARE_INSN(fcvt_s_l, 0xc053, 0x3ff1ff)
+DECLARE_INSN(vflsegstd, 0xd8b, 0xfff)
+DECLARE_INSN(c_add, 0x1a, 0x801f)
+DECLARE_INSN(fcvt_lu_d, 0x90d3, 0x3ff1ff)
+DECLARE_INSN(vfld, 0x58b, 0x3fffff)
+DECLARE_INSN(fsub_d, 0x10d3, 0x1f1ff)
+DECLARE_INSN(fmadd_s, 0x43, 0x1ff)
+DECLARE_INSN(fcvt_w_s, 0xa053, 0x3ff1ff)
+DECLARE_INSN(vssegh, 0x208f, 0x1ffff)
+DECLARE_INSN(fsqrt_s, 0x4053, 0x3ff1ff)
+DECLARE_INSN(c_srai, 0x1019, 0x1c1f)
+DECLARE_INSN(amomin_w, 0x112b, 0x1ffff)
+DECLARE_INSN(fsgnjn_s, 0x6053, 0x1ffff)
+DECLARE_INSN(c_slli32, 0x419, 0x1c1f)
+DECLARE_INSN(vlsegwu, 0x230b, 0x1ffff)
+DECLARE_INSN(vfsw, 0x50f, 0x3fffff)
+DECLARE_INSN(amoswap_d, 0x5ab, 0x1ffff)
+DECLARE_INSN(fence_l_v, 0x22f, 0x3ff)
+DECLARE_INSN(fsqrt_d, 0x40d3, 0x3ff1ff)
+DECLARE_INSN(vflw, 0x50b, 0x3fffff)
+DECLARE_INSN(fdiv_d, 0x30d3, 0x1f1ff)
+DECLARE_INSN(fmadd_d, 0xc3, 0x1ff)
+DECLARE_INSN(divw, 0x63b, 0x1ffff)
+DECLARE_INSN(amomin_d, 0x11ab, 0x1ffff)
+DECLARE_INSN(divu, 0x6b3, 0x1ffff)
+DECLARE_INSN(amoswap_w, 0x52b, 0x1ffff)
+DECLARE_INSN(vfsd, 0x58f, 0x3fffff)
+DECLARE_INSN(fadd_s, 0x53, 0x1f1ff)
+DECLARE_INSN(vlsegb, 0x200b, 0x1ffff)
+DECLARE_INSN(fsd, 0x1a7, 0x3ff)
+DECLARE_INSN(vlsegd, 0x218b, 0x1ffff)
+DECLARE_INSN(vlsegh, 0x208b, 0x1ffff)
+DECLARE_INSN(sw, 0x123, 0x3ff)
+DECLARE_INSN(fmsub_s, 0x47, 0x1ff)
+DECLARE_INSN(vfssegw, 0x250f, 0x1ffff)
+DECLARE_INSN(c_addiw, 0x1d, 0x1f)
+DECLARE_INSN(lhu, 0x283, 0x3ff)
+DECLARE_INSN(sh, 0xa3, 0x3ff)
+DECLARE_INSN(vlsegw, 0x210b, 0x1ffff)
+DECLARE_INSN(fsw, 0x127, 0x3ff)
+DECLARE_INSN(vlbu, 0x20b, 0x3fffff)
+DECLARE_INSN(sb, 0x23, 0x3ff)
+DECLARE_INSN(fmsub_d, 0xc7, 0x1ff)
+DECLARE_INSN(vlseghu, 0x228b, 0x1ffff)
+DECLARE_INSN(vssegb, 0x200f, 0x1ffff)
+DECLARE_INSN(vfssegd, 0x258f, 0x1ffff)
+DECLARE_INSN(sd, 0x1a3, 0x3ff)
index d109a4a..c98a857 100644 (file)
@@ -21,7 +21,7 @@
 #include <colored_caches.h>
 
 page_list_t *COUNT(llc_cache->num_colors) colored_page_free_list = NULL;
-spinlock_t colored_page_free_list_lock;
+spinlock_t colored_page_free_list_lock = SPINLOCK_INITIALIZER_IRQSAVE;
 
 void page_alloc_bootstrap() {
        // Allocate space for the array required to manage the free lists
index f2ebaab..7659a97 100644 (file)
@@ -1,18 +1,18 @@
-#ifndef _RISCV_COP0_H
-#define _RISCV_COP0_H
+#ifndef _RISCV_PCR_H
+#define _RISCV_PCR_H
 
-#define SR_ET    0x0000000000000001
-#define SR_EF    0x0000000000000002
-#define SR_EV    0x0000000000000004
-#define SR_EC    0x0000000000000008
-#define SR_PS    0x0000000000000010
-#define SR_S     0x0000000000000020
-#define SR_UX    0x0000000000000040
-#define SR_SX    0x0000000000000080
-#define SR_IM    0x000000000000FF00
-#define SR_VM    0x0000000000010000
-
-#define SR_IM_SHIFT 8
+#define SR_ET    0x00000001
+#define SR_EF    0x00000002
+#define SR_EV    0x00000004
+#define SR_EC    0x00000008
+#define SR_PS    0x00000010
+#define SR_S     0x00000020
+#define SR_U64   0x00000040
+#define SR_S64   0x00000080
+#define SR_VM    0x00000100
+#define SR_IM    0x00FF0000
+#define SR_ZERO  ~(SR_ET|SR_EF|SR_EV|SR_EC|SR_PS|SR_S|SR_U64|SR_S64|SR_VM|SR_IM)
+#define SR_IM_SHIFT 16
 
 #define PCR_SR       0
 #define PCR_EPC      1
 #define PCR_SEND_IPI 8
 #define PCR_CLR_IPI  9
 #define PCR_COREID   10
+#define PCR_IMPL     11
 #define PCR_K0       12
 #define PCR_K1       13
-#define PCR_TOHOST   16
-#define PCR_FROMHOST 17
-#define PCR_CONSOLE  18
+#define PCR_VECBANK  18
+#define PCR_VECCFG   19
+#define PCR_RESET    29
+#define PCR_TOHOST   30
+#define PCR_FROMHOST 31
 
-#define IPI_IRQ   5
-#define TIMER_IRQ 7
+#define IRQ_IPI   5
+#define IRQ_TIMER 7
 
 #define CAUSE_MISALIGNED_FETCH 0
 #define CAUSE_FAULT_FETCH 1
 #define CAUSE_FAULT_LOAD 10
 #define CAUSE_FAULT_STORE 11
 #define CAUSE_VECTOR_DISABLED 12
-#define CAUSE_IRQ0 16
-#define CAUSE_IRQ1 17
-#define CAUSE_IRQ2 18
-#define CAUSE_IRQ3 19
-#define CAUSE_IRQ4 20
-#define CAUSE_IRQ5 21
-#define CAUSE_IRQ6 22
-#define CAUSE_IRQ7 23
-#define NUM_CAUSES 24
+#define CAUSE_VECTOR_BANK 13
+
+#define CAUSE_VECTOR_MISALIGNED_FETCH 24
+#define CAUSE_VECTOR_FAULT_FETCH 25
+#define CAUSE_VECTOR_ILLEGAL_INSTRUCTION 26
+#define CAUSE_VECTOR_ILLEGAL_COMMAND 27
+#define CAUSE_VECTOR_MISALIGNED_LOAD 28
+#define CAUSE_VECTOR_MISALIGNED_STORE 29
+#define CAUSE_VECTOR_FAULT_LOAD 30
+#define CAUSE_VECTOR_FAULT_STORE 31
+
+#ifdef __riscv
 
 #define ASM_CR(r)   _ASM_CR(r)
 #define _ASM_CR(r)  cr##r
 
 #ifndef __ASSEMBLER__
 
-#define mtpcr(reg,val) ({ long __tmp = (long)(val); \
-          asm volatile ("mtpcr %0,cr%1"::"r"(__tmp),"i"(reg)); })
+#define mtpcr(reg,val) ({ long __tmp = (long)(val), __tmp2; \
+          asm volatile ("mtpcr %0,%1,cr%2" : "=r"(__tmp2) : "r"(__tmp),"i"(reg)); \
+          __tmp2; })
 
 #define mfpcr(reg) ({ long __tmp; \
           asm volatile ("mfpcr %0,cr%1" : "=r"(__tmp) : "i"(reg)); \
           __tmp; })
 
-#define irq_disable() asm volatile("di")
-#define irq_enable() asm volatile("ei")
+#define setpcr(reg,val) ({ long __tmp; \
+          asm volatile ("setpcr %0,cr%2,%1" : "=r"(__tmp) : "i"(val), "i"(reg)); \
+          __tmp; })
+
+#define clearpcr(reg,val) ({ long __tmp; \
+          asm volatile ("clearpcr %0,cr%2,%1" : "=r"(__tmp) : "i"(val), "i"(reg)); \
+          __tmp; })
+
+#endif
 
 #endif
 
index f7d29a3..1bd28e8 100644 (file)
@@ -14,7 +14,7 @@ void proc_init_trapframe(trapframe_t *tf, uint32_t vcoreid,
        memset(tf, 0, sizeof(*tf));
 
        tf->gpr[30] = stack_top-64;
-       tf->sr = SR_S | SR_IM | SR_SX | SR_UX | SR_VM;
+       tf->sr = SR_U64;
 
        tf->epc = entryp;
 
@@ -25,7 +25,7 @@ void proc_init_trapframe(trapframe_t *tf, uint32_t vcoreid,
 
 void proc_secure_trapframe(struct trapframe *tf)
 {
-       tf->sr = SR_S | SR_IM | SR_SX | SR_UX | SR_VM;
+       tf->sr = SR_U64;
 }
 
 /* Called when we are currently running an address space on our core and want to
index 7be96e8..29e5cc3 100644 (file)
@@ -24,7 +24,7 @@ read_pc(void)
 }
 
 static __inline void
-send_ipi(uint32_t who)
+send_ipi(uint32_t who, uint8_t vector)
 {
        mtpcr(PCR_SEND_IPI, who);
 }
index 6c32ea5..f5968d6 100644 (file)
@@ -1,6 +1,6 @@
 #ifndef _ROS_ARCH_ARCH_H
 #define _ROS_ARCH_ARCH_H
 
-#define MAX_NUM_CPUS                           64
+#define MAX_NUM_CPUS                           16 // it's safe to change this as needed
 
 #endif
index b41b7c3..23092eb 100644 (file)
@@ -10,8 +10,7 @@ typedef struct trapframe
   uintptr_t sr;
   uintptr_t epc;
   uintptr_t badvaddr;
-  uintptr_t cause;
-  uintptr_t insn;
+  long cause;
 } trapframe_t;
 
 /* TODO: consider using a user-space specific trapframe, since they don't need
index d3279ef..5f57ff2 100644 (file)
@@ -8,20 +8,14 @@
 #include <atomic.h>
 #include <pmap.h>
 
-static volatile uint32_t num_cpus_booted = 1;
+volatile uint32_t num_cpus_booted = 0;
 
 void
 smp_boot(void)
 {
        smp_percpu_init();
-
-       printd("Cores, report in!\n");
-
-       for(uint32_t i = 1; i < num_cpus; i++)
-               send_ipi(i);
-       
+       num_cpus_booted = 1;
        while(num_cpus_booted < num_cpus);
-
        printd("%d cores reporting!\n", num_cpus);
 }
 
@@ -147,4 +141,7 @@ void __arch_pcpu_init(uint32_t coreid)
        // has the [0,KERNSIZE-1] identity mapping.
        extern pte_t l1pt[NPTENTRIES];
        lcr3(PADDR(l1pt));
+
+       register uintptr_t sp asm ("sp");
+       set_stack_top(ROUNDUP(sp, PGSIZE));
 }
diff --git a/kern/arch/riscv/softfloat-macros.h b/kern/arch/riscv/softfloat-macros.h
new file mode 100644 (file)
index 0000000..a707c8d
--- /dev/null
@@ -0,0 +1,720 @@
+\r
+/*============================================================================\r
+\r
+This C source fragment is part of the SoftFloat IEC/IEEE Floating-point\r
+Arithmetic Package, Release 2b.\r
+\r
+Written by John R. Hauser.  This work was made possible in part by the\r
+International Computer Science Institute, located at Suite 600, 1947 Center\r
+Street, Berkeley, California 94704.  Funding was partially provided by the\r
+National Science Foundation under grant MIP-9311980.  The original version\r
+of this code was written as part of a project to build a fixed-point vector\r
+processor in collaboration with the University of California at Berkeley,\r
+overseen by Profs. Nelson Morgan and John Wawrzynek.  More information\r
+is available through the Web page `http://www.cs.berkeley.edu/~jhauser/\r
+arithmetic/SoftFloat.html'.\r
+\r
+THIS SOFTWARE IS DISTRIBUTED AS IS, FOR FREE.  Although reasonable effort has\r
+been made to avoid it, THIS SOFTWARE MAY CONTAIN FAULTS THAT WILL AT TIMES\r
+RESULT IN INCORRECT BEHAVIOR.  USE OF THIS SOFTWARE IS RESTRICTED TO PERSONS\r
+AND ORGANIZATIONS WHO CAN AND WILL TAKE FULL RESPONSIBILITY FOR ALL LOSSES,\r
+COSTS, OR OTHER PROBLEMS THEY INCUR DUE TO THE SOFTWARE, AND WHO FURTHERMORE\r
+EFFECTIVELY INDEMNIFY JOHN HAUSER AND THE INTERNATIONAL COMPUTER SCIENCE\r
+INSTITUTE (possibly via similar legal notice) AGAINST ALL LOSSES, COSTS, OR\r
+OTHER PROBLEMS INCURRED BY THEIR CUSTOMERS AND CLIENTS DUE TO THE SOFTWARE.\r
+\r
+Derivative works are acceptable, even for commercial purposes, so long as\r
+(1) the source code for the derivative work includes prominent notice that\r
+the work is derivative, and (2) the source code includes prominent notice with\r
+these four paragraphs for those parts of this code that are retained.\r
+\r
+=============================================================================*/\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts `a' right by the number of bits given in `count'.  If any nonzero\r
+| bits are shifted off, they are ``jammed'' into the least significant bit of\r
+| the result by setting the least significant bit to 1.  The value of `count'\r
+| can be arbitrarily large; in particular, if `count' is greater than 32, the\r
+| result will be either 0 or 1, depending on whether `a' is zero or nonzero.\r
+| The result is stored in the location pointed to by `zPtr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void shift32RightJamming( bits32 a, int16_t count, bits32 *zPtr )\r
+{\r
+    bits32 z;\r
+\r
+    if ( count == 0 ) {\r
+        z = a;\r
+    }\r
+    else if ( count < 32 ) {\r
+        z = ( a>>count ) | ( ( a<<( ( - count ) & 31 ) ) != 0 );\r
+    }\r
+    else {\r
+        z = ( a != 0 );\r
+    }\r
+    *zPtr = z;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts `a' right by the number of bits given in `count'.  If any nonzero\r
+| bits are shifted off, they are ``jammed'' into the least significant bit of\r
+| the result by setting the least significant bit to 1.  The value of `count'\r
+| can be arbitrarily large; in particular, if `count' is greater than 64, the\r
+| result will be either 0 or 1, depending on whether `a' is zero or nonzero.\r
+| The result is stored in the location pointed to by `zPtr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void shift64RightJamming( bits64 a, int16_t count, bits64 *zPtr )\r
+{\r
+    bits64 z;\r
+\r
+    if ( count == 0 ) {\r
+        z = a;\r
+    }\r
+    else if ( count < 64 ) {\r
+        z = ( a>>count ) | ( ( a<<( ( - count ) & 63 ) ) != 0 );\r
+    }\r
+    else {\r
+        z = ( a != 0 );\r
+    }\r
+    *zPtr = z;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 128-bit value formed by concatenating `a0' and `a1' right by 64\r
+| _plus_ the number of bits given in `count'.  The shifted result is at most\r
+| 64 nonzero bits; this is stored at the location pointed to by `z0Ptr'.  The\r
+| bits shifted off form a second 64-bit result as follows:  The _last_ bit\r
+| shifted off is the most-significant bit of the extra result, and the other\r
+| 63 bits of the extra result are all zero if and only if _all_but_the_last_\r
+| bits shifted off were all zero.  This extra result is stored in the location\r
+| pointed to by `z1Ptr'.  The value of `count' can be arbitrarily large.\r
+|     (This routine makes more sense if `a0' and `a1' are considered to form\r
+| a fixed-point value with binary point between `a0' and `a1'.  This fixed-\r
+| point value is shifted right by the number of bits given in `count', and\r
+| the integer part of the result is returned at the location pointed to by\r
+| `z0Ptr'.  The fractional part of the result may be slightly corrupted as\r
+| described above, and is returned at the location pointed to by `z1Ptr'.)\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shift64ExtraRightJamming(\r
+     bits64 a0, bits64 a1, int16_t count, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+    bits64 z0, z1;\r
+    int8_t negCount = ( - count ) & 63;\r
+\r
+    if ( count == 0 ) {\r
+        z1 = a1;\r
+        z0 = a0;\r
+    }\r
+    else if ( count < 64 ) {\r
+        z1 = ( a0<<negCount ) | ( a1 != 0 );\r
+        z0 = a0>>count;\r
+    }\r
+    else {\r
+        if ( count == 64 ) {\r
+            z1 = a0 | ( a1 != 0 );\r
+        }\r
+        else {\r
+            z1 = ( ( a0 | a1 ) != 0 );\r
+        }\r
+        z0 = 0;\r
+    }\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 128-bit value formed by concatenating `a0' and `a1' right by the\r
+| number of bits given in `count'.  Any bits shifted off are lost.  The value\r
+| of `count' can be arbitrarily large; in particular, if `count' is greater\r
+| than 128, the result will be 0.  The result is broken into two 64-bit pieces\r
+| which are stored at the locations pointed to by `z0Ptr' and `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shift128Right(\r
+     bits64 a0, bits64 a1, int16_t count, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+    bits64 z0, z1;\r
+    int8_t negCount = ( - count ) & 63;\r
+\r
+    if ( count == 0 ) {\r
+        z1 = a1;\r
+        z0 = a0;\r
+    }\r
+    else if ( count < 64 ) {\r
+        z1 = ( a0<<negCount ) | ( a1>>count );\r
+        z0 = a0>>count;\r
+    }\r
+    else {\r
+        z1 = ( count < 64 ) ? ( a0>>( count & 63 ) ) : 0;\r
+        z0 = 0;\r
+    }\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 128-bit value formed by concatenating `a0' and `a1' right by the\r
+| number of bits given in `count'.  If any nonzero bits are shifted off, they\r
+| are ``jammed'' into the least significant bit of the result by setting the\r
+| least significant bit to 1.  The value of `count' can be arbitrarily large;\r
+| in particular, if `count' is greater than 128, the result will be either\r
+| 0 or 1, depending on whether the concatenation of `a0' and `a1' is zero or\r
+| nonzero.  The result is broken into two 64-bit pieces which are stored at\r
+| the locations pointed to by `z0Ptr' and `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shift128RightJamming(\r
+     bits64 a0, bits64 a1, int16_t count, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+    bits64 z0, z1;\r
+    int8_t negCount = ( - count ) & 63;\r
+\r
+    if ( count == 0 ) {\r
+        z1 = a1;\r
+        z0 = a0;\r
+    }\r
+    else if ( count < 64 ) {\r
+        z1 = ( a0<<negCount ) | ( a1>>count ) | ( ( a1<<negCount ) != 0 );\r
+        z0 = a0>>count;\r
+    }\r
+    else {\r
+        if ( count == 64 ) {\r
+            z1 = a0 | ( a1 != 0 );\r
+        }\r
+        else if ( count < 128 ) {\r
+            z1 = ( a0>>( count & 63 ) ) | ( ( ( a0<<negCount ) | a1 ) != 0 );\r
+        }\r
+        else {\r
+            z1 = ( ( a0 | a1 ) != 0 );\r
+        }\r
+        z0 = 0;\r
+    }\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 192-bit value formed by concatenating `a0', `a1', and `a2' right\r
+| by 64 _plus_ the number of bits given in `count'.  The shifted result is\r
+| at most 128 nonzero bits; these are broken into two 64-bit pieces which are\r
+| stored at the locations pointed to by `z0Ptr' and `z1Ptr'.  The bits shifted\r
+| off form a third 64-bit result as follows:  The _last_ bit shifted off is\r
+| the most-significant bit of the extra result, and the other 63 bits of the\r
+| extra result are all zero if and only if _all_but_the_last_ bits shifted off\r
+| were all zero.  This extra result is stored in the location pointed to by\r
+| `z2Ptr'.  The value of `count' can be arbitrarily large.\r
+|     (This routine makes more sense if `a0', `a1', and `a2' are considered\r
+| to form a fixed-point value with binary point between `a1' and `a2'.  This\r
+| fixed-point value is shifted right by the number of bits given in `count',\r
+| and the integer part of the result is returned at the locations pointed to\r
+| by `z0Ptr' and `z1Ptr'.  The fractional part of the result may be slightly\r
+| corrupted as described above, and is returned at the location pointed to by\r
+| `z2Ptr'.)\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shift128ExtraRightJamming(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 a2,\r
+     int16_t count,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2;\r
+    int8_t negCount = ( - count ) & 63;\r
+\r
+    if ( count == 0 ) {\r
+        z2 = a2;\r
+        z1 = a1;\r
+        z0 = a0;\r
+    }\r
+    else {\r
+        if ( count < 64 ) {\r
+            z2 = a1<<negCount;\r
+            z1 = ( a0<<negCount ) | ( a1>>count );\r
+            z0 = a0>>count;\r
+        }\r
+        else {\r
+            if ( count == 64 ) {\r
+                z2 = a1;\r
+                z1 = a0;\r
+            }\r
+            else {\r
+                a2 |= a1;\r
+                if ( count < 128 ) {\r
+                    z2 = a0<<negCount;\r
+                    z1 = a0>>( count & 63 );\r
+                }\r
+                else {\r
+                    z2 = ( count == 128 ) ? a0 : ( a0 != 0 );\r
+                    z1 = 0;\r
+                }\r
+            }\r
+            z0 = 0;\r
+        }\r
+        z2 |= ( a2 != 0 );\r
+    }\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 128-bit value formed by concatenating `a0' and `a1' left by the\r
+| number of bits given in `count'.  Any bits shifted off are lost.  The value\r
+| of `count' must be less than 64.  The result is broken into two 64-bit\r
+| pieces which are stored at the locations pointed to by `z0Ptr' and `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shortShift128Left(\r
+     bits64 a0, bits64 a1, int16_t count, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+\r
+    *z1Ptr = a1<<count;\r
+    *z0Ptr =\r
+        ( count == 0 ) ? a0 : ( a0<<count ) | ( a1>>( ( - count ) & 63 ) );\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Shifts the 192-bit value formed by concatenating `a0', `a1', and `a2' left\r
+| by the number of bits given in `count'.  Any bits shifted off are lost.\r
+| The value of `count' must be less than 64.  The result is broken into three\r
+| 64-bit pieces which are stored at the locations pointed to by `z0Ptr',\r
+| `z1Ptr', and `z2Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ shortShift192Left(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 a2,\r
+     int16_t count,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2;\r
+    int8_t negCount;\r
+\r
+    z2 = a2<<count;\r
+    z1 = a1<<count;\r
+    z0 = a0<<count;\r
+    if ( 0 < count ) {\r
+        negCount = ( ( - count ) & 63 );\r
+        z1 |= a2>>negCount;\r
+        z0 |= a1>>negCount;\r
+    }\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Adds the 128-bit value formed by concatenating `a0' and `a1' to the 128-bit\r
+| value formed by concatenating `b0' and `b1'.  Addition is modulo 2^128, so\r
+| any carry out is lost.  The result is broken into two 64-bit pieces which\r
+| are stored at the locations pointed to by `z0Ptr' and `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ add128(\r
+     bits64 a0, bits64 a1, bits64 b0, bits64 b1, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+    bits64 z1;\r
+\r
+    z1 = a1 + b1;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = a0 + b0 + ( z1 < a1 );\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Adds the 192-bit value formed by concatenating `a0', `a1', and `a2' to the\r
+| 192-bit value formed by concatenating `b0', `b1', and `b2'.  Addition is\r
+| modulo 2^192, so any carry out is lost.  The result is broken into three\r
+| 64-bit pieces which are stored at the locations pointed to by `z0Ptr',\r
+| `z1Ptr', and `z2Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ add192(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 a2,\r
+     bits64 b0,\r
+     bits64 b1,\r
+     bits64 b2,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2;\r
+    int8_t carry0, carry1;\r
+\r
+    z2 = a2 + b2;\r
+    carry1 = ( z2 < a2 );\r
+    z1 = a1 + b1;\r
+    carry0 = ( z1 < a1 );\r
+    z0 = a0 + b0;\r
+    z1 += carry1;\r
+    z0 += ( z1 < carry1 );\r
+    z0 += carry0;\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Subtracts the 128-bit value formed by concatenating `b0' and `b1' from the\r
+| 128-bit value formed by concatenating `a0' and `a1'.  Subtraction is modulo\r
+| 2^128, so any borrow out (carry out) is lost.  The result is broken into two\r
+| 64-bit pieces which are stored at the locations pointed to by `z0Ptr' and\r
+| `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ sub128(\r
+     bits64 a0, bits64 a1, bits64 b0, bits64 b1, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+\r
+    *z1Ptr = a1 - b1;\r
+    *z0Ptr = a0 - b0 - ( a1 < b1 );\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Subtracts the 192-bit value formed by concatenating `b0', `b1', and `b2'\r
+| from the 192-bit value formed by concatenating `a0', `a1', and `a2'.\r
+| Subtraction is modulo 2^192, so any borrow out (carry out) is lost.  The\r
+| result is broken into three 64-bit pieces which are stored at the locations\r
+| pointed to by `z0Ptr', `z1Ptr', and `z2Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ sub192(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 a2,\r
+     bits64 b0,\r
+     bits64 b1,\r
+     bits64 b2,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2;\r
+    int8_t borrow0, borrow1;\r
+\r
+    z2 = a2 - b2;\r
+    borrow1 = ( a2 < b2 );\r
+    z1 = a1 - b1;\r
+    borrow0 = ( a1 < b1 );\r
+    z0 = a0 - b0;\r
+    z0 -= ( z1 < borrow1 );\r
+    z1 -= borrow1;\r
+    z0 -= borrow0;\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Multiplies `a' by `b' to obtain a 128-bit product.  The product is broken\r
+| into two 64-bit pieces which are stored at the locations pointed to by\r
+| `z0Ptr' and `z1Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void mul64To128( bits64 a, bits64 b, bits64 *z0Ptr, bits64 *z1Ptr )\r
+{\r
+    bits32 aHigh, aLow, bHigh, bLow;\r
+    bits64 z0, zMiddleA, zMiddleB, z1;\r
+\r
+    aLow = a;\r
+    aHigh = a>>32;\r
+    bLow = b;\r
+    bHigh = b>>32;\r
+    z1 = ( (bits64) aLow ) * bLow;\r
+    zMiddleA = ( (bits64) aLow ) * bHigh;\r
+    zMiddleB = ( (bits64) aHigh ) * bLow;\r
+    z0 = ( (bits64) aHigh ) * bHigh;\r
+    zMiddleA += zMiddleB;\r
+    z0 += ( ( (bits64) ( zMiddleA < zMiddleB ) )<<32 ) + ( zMiddleA>>32 );\r
+    zMiddleA <<= 32;\r
+    z1 += zMiddleA;\r
+    z0 += ( z1 < zMiddleA );\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Multiplies the 128-bit value formed by concatenating `a0' and `a1' by\r
+| `b' to obtain a 192-bit product.  The product is broken into three 64-bit\r
+| pieces which are stored at the locations pointed to by `z0Ptr', `z1Ptr', and\r
+| `z2Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ mul128By64To192(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 b,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2, more1;\r
+\r
+    mul64To128( a1, b, &z1, &z2 );\r
+    mul64To128( a0, b, &z0, &more1 );\r
+    add128( z0, more1, 0, z1, &z0, &z1 );\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Multiplies the 128-bit value formed by concatenating `a0' and `a1' to the\r
+| 128-bit value formed by concatenating `b0' and `b1' to obtain a 256-bit\r
+| product.  The product is broken into four 64-bit pieces which are stored at\r
+| the locations pointed to by `z0Ptr', `z1Ptr', `z2Ptr', and `z3Ptr'.\r
+*----------------------------------------------------------------------------*/\r
+\r
+INLINE void\r
+ mul128To256(\r
+     bits64 a0,\r
+     bits64 a1,\r
+     bits64 b0,\r
+     bits64 b1,\r
+     bits64 *z0Ptr,\r
+     bits64 *z1Ptr,\r
+     bits64 *z2Ptr,\r
+     bits64 *z3Ptr\r
+ )\r
+{\r
+    bits64 z0, z1, z2, z3;\r
+    bits64 more1, more2;\r
+\r
+    mul64To128( a1, b1, &z2, &z3 );\r
+    mul64To128( a1, b0, &z1, &more2 );\r
+    add128( z1, more2, 0, z2, &z1, &z2 );\r
+    mul64To128( a0, b0, &z0, &more1 );\r
+    add128( z0, more1, 0, z1, &z0, &z1 );\r
+    mul64To128( a0, b1, &more1, &more2 );\r
+    add128( more1, more2, 0, z2, &more1, &z2 );\r
+    add128( z0, z1, 0, more1, &z0, &z1 );\r
+    *z3Ptr = z3;\r
+    *z2Ptr = z2;\r
+    *z1Ptr = z1;\r
+    *z0Ptr = z0;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Returns an approximation to the 64-bit integer quotient obtained by dividing\r
+| `b' into the 128-bit value formed by concatenating `a0' and `a1'.  The\r
+| divisor `b' must be at least 2^63.  If q is the exact quotient truncated\r
+| toward zero, the approximation returned lies between q and q + 2 inclusive.\r
+| If the exact quotient q is larger than 64 bits, the maximum positive 64-bit\r
+| unsigned integer is returned.\r
+*----------------------------------------------------------------------------*/\r
+\r
+static bits64 estimateDiv128To64( bits64 a0, bits64 a1, bits64 b )\r
+{\r
+    bits64 b0, b1;\r
+    bits64 rem0, rem1, term0, term1;\r
+    bits64 z;\r
+\r
+    if ( b <= a0 ) return LIT64( 0xFFFFFFFFFFFFFFFF );\r
+    b0 = b>>32;\r
+    z = ( b0<<32 <= a0 ) ? LIT64( 0xFFFFFFFF00000000 ) : ( a0 / b0 )<<32;\r
+    mul64To128( b, z, &term0, &term1 );\r
+    sub128( a0, a1, term0, term1, &rem0, &rem1 );\r
+    while ( ( (sbits64) rem0 ) < 0 ) {\r
+        z -= LIT64( 0x100000000 );\r
+        b1 = b<<32;\r
+        add128( rem0, rem1, b0, b1, &rem0, &rem1 );\r
+    }\r
+    rem0 = ( rem0<<32 ) | ( rem1>>32 );\r
+    z |= ( b0<<32 <= rem0 ) ? 0xFFFFFFFF : rem0 / b0;\r
+    return z;\r
+\r
+}\r
+\r
+/*----------------------------------------------------------------------------\r
+| Returns an approximation to the square root of the 32-bit significand given\r
+| by `a'.  Considered as an integer, `a' must be at least 2^31.  If bit 0 of\r
+| `aExp' (the least significant bit) is 1, the integer returned approximates\r
+| 2^31*sqrt(`a'/2^31), where `a' is considered an integer.  If bit 0 of `aExp'\r
+| is 0, the integer returned approximates 2^31*sqrt(`a'/2^30).  In either\r
+| case, the approximation returned lies strictly within +/-2 of the exact\r
+| value.\r
+*----------------------------------------------------------------------------*/\r
+\r
+static bits32 estimateSqrt32( int16_t aExp, bits32 a )\r
+{\r
+    static const bits16 sqrtOddAdjustments[] = {\r
+        0x0004, 0x0022, 0x005D, 0x00B1, 0x011D, 0x019F, 0x0236, 0x02E0,\r
+        0x039C, 0x0468, 0x0545, 0x0631, 0x072B, 0x0832, 0x0946, 0x0A67\r
+    };\r
+    static const bits16 sqrtEvenAdjustments[] = {\r
+        0x0A2D, 0x08AF, 0x075A, 0x0629, 0x051A, 0x0429, 0x0356, 0x029E,\r
+        0x0200, 0x0179, 0x0109, 0x00AF, 0x0068, 0x0034, 0x0012, 0x0002\r
+    };\r
+    int8_t index;\r
+    bits32 z;\r
+\r
+    index = ( a>>27 ) & 15;\r
+    if ( aExp & 1 ) {\r
+        z = 0x4000 + ( a>>17 ) - sqrtOddAdjustments[ index ];\r
+        z = ( ( a / z )<<14 ) + ( z<<15 );\r
+        a >>= 1;\r
+    }\r
+    else {\r