Quest Cross Reference 0.1.0/​kernel/​docs/​NOTES	Source navigation Diff markup Identifier search General search
	Version: 0.1.0 experimental Revert   Change

 Monday 2011-01-24 md
 
   I'm picking up my project to revamp the virtual memory system in
   Quest.  I have some utility functions from the summer, though it
   turns out they were missing a lot.  I've ripped out the virtual
   memory manipulation found in _fork and changed it to use
   clone_page_directory instead.  I found a bug in duplicate_TSS where
   it happened to modify both the parent and the child stacks when
   forking.  I've changed it to modify only the child's stack, doing a
   physical address lookup using the child's page directory explicitly.
   This bug did not crop up in practice because it would only overwrite
   a variable on the stack in the parent, and that variable happened
   not to be needed any longer.
 
 Wednesday 2011-01-19 md
 
   Implement disjunctive dependencies and subtree dependencies for
   module system.  For example, the VFS might depend on
   {"storage___ata|netsetup"} and netsetup might depend on {"net___"}.
   This ensures either ATA or networking is supported, and the network
   is configured only after all available networking modules have been
   loaded.
 
 Thursday 2010-12-09 md
 
   Measured round-trip VM-ENTER/VM-EXIT at about 1500 cycles.
 
 Monday 2010-12-06 md
 
   There's a bug somewhere that's preventing my old BIOS mode 013h
   graphical demos from working inside of VMX/VM86.  This worked
   originally on percy last year.  I tested "real" real-mode and the
   graphics worked, so the problem is something to do with either my
   virtualization code, or something else in the Quest bootup sequence.
 
 Friday 2010-12-02 md
 
   Merged old VMX/VM86 code that creates hardware VT virtual machines
   using VM86 to emulate real mode.
 
 Monday 2010-11-22 md
 
   Scratched a long-standing itch by implementing a "module system" for
   drivers and other components which can be loaded in any particular
   order, with dependencies.
 
 Friday 2010-11-19 md
 
   So it turns out that the LAPIC IDs on baldrick are not contiguously
   numbered, which breaks a few assumptions.  I instituted a numbering
   system accessible via a percpu variable, and that fixed that
   problem.  The LAPIC ID numbering scheme for Xeon non-HT processors
   fixes the least significant bit at 0.  In addition, the LAPIC ID
   register disagrees with the CPUID initial LAPIC value and the ACPI
   MADT entry.  I'm not sure how IPIs are managing to work, but if I
   stick with the initial LAPIC value things seem to be ok.  According
   to the manual 3A, the LAPIC ID 0x16 breaks down to "cluster ID 2,
   processor 3" on this Xeon.
 
 Thursday 2010-11-18 md
 
   I'm hesitant to finish implementing synchronous IPC because of the
   various problems it has, especially on SMP.  What is the meaning of
   sync. IPC across CPUs?  On a single CPU it is simple because you can
   just switch threads back and forth.  With multiple CPUs then you
   have to consider whether or not the thread is currently running on
   the target CPU: do you wrest control away from some poor hapless
   third thread if that is currently running?  What do you do with the
   source CPU while the target CPU is processing your message?  There's
   a lot of potential for inefficiency or unpredictable interference
   from other threads.  Also sync. IPC has lots of disadvantages when
   it comes to providing service to large numbers of client threads.
   Asynchronous IPC scales better but has issues with buffer
   management, and possible unpredictability.
 
   Barrelfish implements async. IPC by using shared memory to exploit
   cache coherency protocols.  This seems like the best way to go for
   interprocessor communication.  Might need some kind of hybrid
   sync/async communication depending on where the target is running.
 
 Wednesday 2010-11-17 md
 
   Fixed up synchronous IPC call/replywait functions.  Debating further
   designs.
 
 Tuesday 2010-11-16 md
 
   Micro-benchmarked SYSENTER vs software INT.  SYSENTER takes ~128
   cycles where software INT takes ~300 cycles.  Is that worth losing
   two register parameters?
 
   Back to measuring IPC.  Kernel thread to thread.  One thread sends 2
   words to the other, then there is a response of 2 words.  Times in
   cycles.
 
   Call (REG): avg 342, stddev 25
   Call (MEM): avg 366, stddev 33
   Ret (REG): avg 361, stddev 24
   Ret (MEM): avg 385, stddev 25
 
   Seems to be a fairly consistent 24 cycle difference between using
   two registers to pass two parameters, or writing (and reading) those
   two parameters from memory in the TSS.  Still, that is just within
   one standard deviation from the average, so it's not necessarily
   that big a deal.
 
   Discussion of Nehalem L1 cache leads me to believe that 8 of those
   24 cycles come from the two memory references to retrieve the passed
   parameters.  The remaining 16 cycles are due to "lookup_TSS (str
   ())" in order to get the pointer to the current TSS.  That can
   probably be eliminated or reduced with better book-keeping.
 
 Monday 2010-11-15 md
 
   Non-root PCI buses show up in ACPI with an "ADR" field that is not
   actually the bus number, but rather the device number of the
   PCI-to-PCI bridge device.  Then you must read the bus number from
   the PCI configuration space header of that bridge.  Now I can obtain
   PCI routing information from ACPI alone.
 
   Added fast_send/recv register-passing IPC mechanism.  Seems to take
   about 400-600 cycles per message.  Investigating SYSENTER for fast
   userspace invocation of the IPC mechanism.  The problem with
   SYSENTER is that it does not save the user's EIP/ESP for you.  You
   must find some way of passing them to the kernel.  Usually by
   storing them in registers.  Which takes away two registers from
   syscall/IPC purposes.
 
 Wednesday 2010-09-01 md
 
   Introduced UDP logging to help avoid overhead.  It seems to drop
   lines a bit, though.  Since the overhead seems to hold consistently
   at about 120us, I tried introducing a constant "fudge" factor of
   0x40000 cycles.  This seems to do a pretty good job of avoiding
   massive budget overruns while not messing up the local APIC timer.
   Putting the logger and lwip threads on the fourth VCPU has some
   interesting results which can be observed in the output: for example
   if you set the ratio to C=1 over T=50 then the logging thread output
   actually slows considerably.
 
 Tuesday 2010-08-31 md
 
   Measuring scheduler overhead by recording how much larger tdelta is
   than cur->b.  In English, how much time elapsed between the previous
   invocation of the scheduler and the current time, compared to the
   budget of the VCPU that was supposed to be running then.  I am
   finding a pretty consistent pattern of ~120us difference.  When I
   attempt to account for the overhead by subtracting it from the
   computed tdelta, I manage to reduce it to dozens of nanoseconds,
   but, I also bottom out the local APIC timer resolution (setting it
   to a value of 1).
 
 Monday 2010-08-30 md
 
   Finished tweaking main VCPU algorithm and implemented it using the
   current VCPU architecture.  In the meantime, I noticed that my
   per-CPU macros don't work with 64-bit data, because they use 64-bit
   operations that are not allowed on IA-32.  I have to use
   special-cased macros that do two 32-bit movs instead.
 
 Thursday 2010-08-26 md
 
   I noticed that __exit destroys the current page directory.  That
   means we are reliant on the TLB cache until the next CR3 load.  But
   my optimization from yesterday means that a kernel thread switch
   will not load CR3.  So calling __exit and switching to an idle task,
   for example, would try to continue using the destroyed page
   directory.
 
 Wednesday 2010-08-25 md
 
   Optimize software task switch so it does not load CR3 when switching
   into a kernel thread, or if CR3 already has the desired value.
 
 Tuesday 2010-08-24 md
 
   Implemented software task switching but still re-using the TSS data
   structure for software task information.
 
 Thursday 2010-08-19 md
 
   Worked out a bit of theory on second-level VCPU scheduling.
   Implemented VCPU internal scheduling with fixed quantum.
 
 Wednesday 2010-08-18 md
 
   Merged basic two-level VCPU scheduler.  Added some basic accounting
   mechanisms.
 
 Tuesday 2010-08-10 md
 
   New branch for VCPU scheduler.
 
 Monday 2010-08-09 md
 
   Added some performance measuring code.
 
 Friday 2010-08-06 md
 
   Added API to access other CPU's variables.  Need this to queue tasks
   back on their assigned CPU (at least, until proper inter-CPU
   messaging exists).  Now the "MPQ" per-CPU queue scheduler will keep
   pulling tasks from the local queue, then fall back to a global
   queue.
 
 Thursday 2010-08-05 md
 
   Tinkering with a per-CPU queue scheduler.
 
 Wednesday 2010-08-04 md
 
   Finished implementing per-CPU memory areas including per-CPU
   initialization functions which are invoked immediately after the
   memory areas are configured for each CPU.
   
   All per-CPU variables are declared in a special non-loaded section
   so they all gain distinct addresses.  Then space is allocated after
   the number of CPUs is determined.  A segment descriptor for each
   space is setup, and each CPU loads a spare segment register with it
   (like %fs).  Per-CPU variable access is done, via macros, relative
   to that segment override.  The segment selector is currently stored
   in %dr3 so that when we return from userspace, we can setup %fs with
   the proper value again.  In the future, when we switch to software
   tasks, it will be possible to avoid using %dr3 by exploiting the
   fact that every CPU has a different selector in %tr.  For example,
   you can allocate the per-CPU TSS next to the per-CPU %fs descriptor,
   so in the end all you need to do is
 
     str %eax; leal 8(%eax), %eax; movw %ax, %fs
 
   which should be faster than debug registers.
 
   Another section is declared, adjacent to read-only data, which
   contains a null-terminated array of pointers to initialization
   functions.  Each CPU invokes these functions to initialize per-CPU
   variables.  This is similar to how C++ global constructors work.
 
   Ye notes that if we have software task switching then we can have
   separate GDTs per CPU and then hard-code the per-CPU segment number.
   Or, perhaps the LDT will work.
 
 Tuesday 2010-08-03 md
 
   Started implementing per-CPU memory areas based on segment register
   %fs and debug register %dr3.
 
 Monday 2010-08-02 md
 
   Investigating options for per-CPU memory areas.  Using %dr3 has some
   advantages, like the fact that task-switch does not touch it.  Best
   measurements I can make show a 30-50 cycle cost to read %dr3, and a
   110-170 cycle cost to write %dr3.  Reading LAPIC ID register seems
   to cost around 25-45 cycles.  Loading an index into segment register
   %fs takes about 15-25 cycles.  Probably looking at up to 25-45
   cycles for a segment load plus memory read: though this is likely
   coming from cache.  STR is another option for getting an index
   quickly, but only works with software task switching because then
   each CPU gets one exclusive TSS entry.
 
 Friday 2010-07-30 md
 
   Did some measurement of scheduler tick jitter.
 
 Thursday 2010-07-29 md
 
   Adding the beginning of a performance monitoring counter module.
 
 Tuesday 2010-07-27 md
 
   I found some more information about the protocol headers surrounding
   ARP and IP packets in IEEE 802.11 frames.  I think part of my
   problem is that I was tagging every packet as "ARP" even if it
   wasn't.  At least that would cause tcpdump to get confused.  I'm
   also trying to maintain a proper timestamp function and some
   semblance of synchronization with the IBSS.  I imported a duration
   function from the old rtl8180 driver.  Another problem is that many
   packets are missing from the Kismet output.  I'm not sure why: is my
   transmitter failing to launch packets?  Or is Kismet just not
   picking them up?
 
   I've realized that lwIP etharp input is expecting Ethernet frame
   headers and that I'm not supplying that.  A quick hack to rewrite
   headers received into Ethernet format, and to cut off the Ethernet
   header on transmitted packets, and now I can ping/echo.  There is
   still a lot of packet loss.  Not sure where the loss is occurring:
   is transmitter dropping packets?  Is receiver still doing that?  Is
   even Kismet getting all the packets?
 
 Monday 2010-07-26 md
 
   I wrote a function to quickly parse the SSID from various MAC
   frames, but it had a couple of flaws: the length variable was
   unsigned, but I was using a "len > 0" test in a loop, which is
   dangerous.  Then it was mis-reading the length of the header, and
   also forgetting to skip the first 2 bytes of every EI.  Somehow,
   that it managed to work at all is amazing.  Anyway, it would lead to
   seemingly random "crashes" (spinning w/o interrupts) that are now
   resolved.  In other news, my laptop seems to be fairly happy with
   the combination of beacon frames and probe responses that I throw at
   it.  I've observed some ARP and IP packets in the wild, attempting
   to duplicate their structure in combination with lwIP now.
   Unfortunately, for some reason, my rtl8187b transmitter is deciding
   to glob separate packets together to spit out some giant mal-formed
   thing, according to Kismet.
 
 Sunday 2010-07-25 md
 
   Set priority of rx_thread to highest, in an effort to ensure that it
   runs as soon as possible after the IRQ handler queues it.  That
   still could mean up to a 10ms delay before a CPU quantum is
   finished.  Found bug in bulk transfer clean-up of non-short packets:
   it is redundant to set the QH vertical pointer back to TERMINATE
   since the HC did it already.  But since the HC did it already,
   another thread might have started using that QH.  Therefore, we
   might end up cutting off someone's TDs.  That's what kept happening
   to the rx_thread when the status thread cleaned itself up.
 
 Saturday 2010-07-24 md
 
   Finally implemented exit_kernel_thread and start_kernel_thread with
   arguments.  It writes the new stack with the appropriate values.  I
   don't think it is possible to do hardware thread switching that
   avoids flushing the TLB.  The Intel manual says it loads CR3 every
   time you task switch.  This issue will have to be revisited with
   either a full implementation of software task switching, or a hybrid
   scheme.
 
 Friday 2010-07-23 md
 
   I decided that the rtl8187b driver was dropping too many
   packets because it is too slow at processing and requeuing TDs.
   I tried doing a direct call to schedule() in the USB IRQ
   handler to expedite matters, but it seemed to cause other
   problems.  I removed all logging and observed that, in the
   Kismet tcpdump, Quest seemed to be producing ACKs in a much
   more timely manner.  So perhaps there is something to this.  So
   I added a separate logging thread which is preemptible, going
   to move all serial port output to this thread in hopes of
   speeding up debugging output.
 
 Thursday 2010-07-22 md
 
   Moving packet formation out of rtl8187b into a software MAC
   implementation based on Linux's idea of mac80211.  Also, there seems
   to be a problem having multiple threads directly queue up
   transmission TDs.  It seems that every transmission bulk output has
   to be paired with a status bulk input.  That seems to defeat the
   point of having four transmission endpoints, but oh well.  Putting
   tranmission into its own thread with a feeder circular buffer.
 
 Wednesday 2010-07-21 md
 
   Importing a lot of Linux headers in order to set the stage for
   software MAC.
 
 Tuesday 2010-07-20 md
 
   First confirmed successful packet transmission.  Seems I do need to
   initialize radio completely.  Don't need to add frame checksum
   myself, apparently the card does it after all.  Start to separate TX
   code to do more than one kind of packet.
 
 Monday 2010-07-19 md
 
   Various attempts to get transmission working.  Trying various
   approaches to frame checksum.  Imported CRC32 code from Linux.
   Seems card sends me a status update after each TX: parsing status
   code and displaying info based what Linux driver does.  Try to skip
   some radio initialization, since it takes forever.
 
 Friday 2010-07-16 md
 
   Parse and dump debugging info about some more kinds of received packets.
 
 Wednesday 2010-07-14 md
 
   Imported a bunch of initialization code from Linux driver.  First
   successful packet reception.  Ensure that all TDs are unlinked even
   in the case of a short packet.  Use the IEEE 802.11 constant and
   struct definitions from Linux.  Do some parsing of simple packets,
   like Beacon.
 
 Tuesday 2010-07-13 md
 
   Instead of having a single QH for bulk transfers, have a list of
   them and use the first available.  This permits concurrent bulk
   transfers.  Begin rtl8187b driver: there is no publicly available
   datasheet.  Begin the process of reverse-engineering by importing
   pieces of the Linux driver wholesale.  There are many tables of
   constants with no documentation, especially in the rtl8225 radio
   initialization code.  Not sure what to do, but copy it.  Also, it
   appears there is a 93c*6 model EEPROM buried in the card, so import
   Linux's generic driver for that (which can operate via USB, or any
   transfer mechanism).  Successfully read the hardware address from
   EEPROM.
 
 Friday 2010-07-09 md
 
   Give up on probing for root device: there is now a "root=..."
   command-line option added to every GRUB configuration and parsed in
   boot/init.c startup.  Implement a TFTP client using the LWIP client
   API, arrange for it to be viewed as a "filesystem" by the simple VFS
   code.
 
 Wednesday 2010-07-07 md
 
   It is necessary to switch to GRUB2 if we want network-booting
   support.  Why?  Because GRUB-legacy does not support the Intel 8254x
   cards (ugh).  GRUB2 doesn't support any cards, but it does support
   PXE, which apparently provides a simple API for TFTP and UDP code,
   and gPXE can fill that role.  However, Quest will not work with
   GRUB2: I found that the reason is because GRUB2 does not put modules
   in low physical memory -- for whatever reason, it likes to put them
   higher up.  But the old Quest init code assumes all modules are in
   low physical memory: modified it to explicitly map all memory it
   uses.  After applying a workaround "fix" to gPXE, I've put new
   images in the repository, and we have network booting.  Also, for
   good measure, I added a CTRL-ALT-DEL handler to the keyboard driver.
 
 Friday 2010-07-02 md
 
   Finally got the Intel 82544GM NIC working.  There was some funky
   initialization that was possibly required.  But the main problem
   seemed to be that the NIC would not add a frame checksum unless you
   set a certain bit in the TX descriptor.  This manifested by having
   everything seem to work, LEDs flashing on both ends, but no packets
   arriving.  Then I got the idea to check the ethtool output for RX
   errors on the Linux side; sure enough, rx_fcs_error count was
   rising.
 
 Thursday 2010-07-01 md
 
   Found a cache of Intel 8254x compatible cards.  Doesn't work with
   the e1000 driver I wrote for QEMU.  Had to read the hardware address
   using the bitbanging 4-wire method instead of the easy EERD way that
   QEMU supports.  Not so hard to do after reading the Linux driver
   source.  Probably should get the SPI NVM-reading code in there too,
   for future reference.  I think the 82577LM is going to need it.
 
 Wednesday 2010-06-30 md
 
   Short packet transfers should be considered complete, many network
   cards seem to terminate transmission with a short packet.  Got the
   ASIX driver working, that should handle many common USB Ethernet
   adapters.
 
 Tuesday 2010-06-29 md
 
   Better logging of USB device info.  Began a driver for the ASIX chip
   commonly found in USB Ethernet adapters.
 
 Thursday 2010-06-24 md
 
   Small project for a long bus ride: trying to clean up and separate
   the code which does virtual memory manipulation like
   clone_page_directory, which is currently mixed into _fork, _exec,
   and other places.
 
 Wednesday 2010-06-23 md
 
   Leave NAKs alone, try to let HC clean it up.  Make sure kernel
   threads do not get woken up until after scheduling is really
   enabled.
 
 Tuesday 2010-06-22 md
 
   Short packet detection, necessary for USB network drivers.  Managed
   to get an echo server working with QEMU's emulated USB network
   adapter.  Bulk transfers now have an output parameter called
   "actual_length".  The USB network driver, and others, are going to
   require some kind of kernel threads.  Since there is no per-device
   IRQ, instead the drivers need kernel threads which block while
   waiting for their TDs to complete.  I suppose there are other ways
   to do this, but this was actually rather simple.  I've consolidated
   the "kernel thread" creating code into a new API:
   start_kernel_thread.  It is also useful for running the LWIP TCP
   timers, instead of hacking that into the PIT IRQ handler.
 
 Monday 2010-06-21 md
 
   Wake up tasks blocked on USB transfers when the IRQ comes.  Clean up
   UHCI a tad, and add String descriptors.
 
 Sunday 2010-06-20 md
 
   Add a crude version of blocking usleep integrated with the scheduler.
 
 Saturday 2010-06-19 md
 
   Have VFAT driver skip 32256 bytes into the disk before reading the
   partition.  Just like our simple EXT2 driver.
 
 Friday 2010-06-18 md
 
   Finally introduce a simple but proper PCI IRQ routing framework.
   The only way to get the correct information is by parsing the MP
   tables, or by interpreting AML code in ACPI (ACPICA handles this).
   Remove various hacks associated with IRQ handling.
 
 Thursday 2010-06-17 md
 
   Fixed a bunch of things and finally worked out what was wrong with
   my PCI drivers.  First of all, the INT_LN field in PCI configuration
   space is just useless on modern systems.  You must parse PCI routing
   table information from ACPI or MP tables.  Secondly, I didn't
   realize that not only are PCI IRQs by default level-triggered
   active-LOW, but the IO-APIC has to be configured with polarity too.
   Emulators just don't care about this sort of stuff.  Also, ACPICA
   does something special when you invoke "\_PIC(1)" method, else you
   can't get the right PCI routing tables out of it.  Now I can get the
   IRQ from the UHCI controller device.  Also it turns out there is no
   standard vendor, product ID for UHCI: you have to rely on the class,
   subclass, and progIF fields.
 
 Monday 2010-06-14 md
 
   Create a framework for USB drivers, each with a probe function.
   Enumerate devices and invoke probe to get the drivers to the
   addresses they need.  Move hub, umsc drivers into this framework.
 
 Saturday 2010-06-12 md
 
   Created uhci_enumerate and the beginning of a hub driver with
   probe_hub.
 
 Friday 2010-06-11 md
 
   Separate USB mass storage controller driver into its own file.
 
 Thursday 2010-06-10 md
 
   First successful USB mass storage sector read.  Add array of toggle
   bits, one for each possible endpoint, to maintain state and
   correctly set the TDs.
 
 Wednesday 2010-06-09 md
 
   Fix up UHCI driver a bit, use PCI decode_bar to get the base address
   properly.  Add a bulk transfer function.
 
 Monday 2010-06-07 md
 
   Get USB working on percy and my laptop.  Added Quest-specific stub
   to MAME.  Added "getcode" variation of "getchar" syscall, to replace
   the old code in MAME which stole keycodes directly from the I/O
   port.  We use IRQ-driver keyboard I/O now.
 
 Sunday 2010-06-06 md
 
   Merge Ye Li's USB UHCI driver.  Probe PCI bus for UHCI controller.
 
 Saturday 2010-06-05 md
 
   Add what I got for e1000e (Intel 82567LM/82577LM).  It doesn't work.
   Use -fno-strict-aliasing because we do stupid pointer tricks.
 
 Friday 2010-06-04 md
 
   Poll TX as well as RX.  Also, it is okay to output serial-port
   logging if we are using GDBSTUB_TCP.
 
 Thursday 2010-06-03 md
 
   Got e1000 packet reception, IRQ, and transmission working.  Create
   an ethernet_device to integrate with LWIP.
 
 Wednesday 2010-06-02 md
 
   Begin e1000 driver, configure descriptors, reset the card, and
   enable reception.
 
 Tuesday 2010-06-01 md
 
   Network cards now must also support a polling interface.  This is
   used to implement GDBSTUB_TCP: over-the-network kernel debugger.
 
 Monday 2010-05-31 md
 
   Create a framework for ethernet cards and have the PCnet driver
   implement it.
 
 Sunday 2010-05-30 md
 
   Implement PCnet transmit.  Import LWIP source into Quest.  Add
   ethernetif template and modify it for Quest.  Get a basic echo
   server working with PCnet card, and use DHCP client.
 
 Saturday 2010-05-29 md
 
   Got IRQ handling working for PCnet.
 
 Friday 2010-05-28 md
 
   Careful about preserving registers across syscalls.  Finally add
   check on argv in _exec.  Import database of PCI vendors and cards.
   Enumerate the PCI bus.  Implement basic PCI bus API.  Begin PCnet
   driver: PCI bus scan, initialization, and reset.
 
 Thursday 2010-05-27 md
 
   Syscalls can clobber memory and flags too, so make sure gcc is
   aware.  Preserve %ebx register properly during splash screen, so
   terminal_server doesn't output garbage for the first character.
   Improper inline asm turns out to be the culprit with the
   optimization woes.
 
 Sunday 2010-05-23 md
 
   Begin PCI driver.  But before that, there seems to be a problem with
   gcc optimization enabled.