Re: [Syllable-kernel] C99 kernel source preview - needs more work

[Jake H. <jh...@po...>]

Daniel Gryniewicz wrote:
> 
> Sounds good, I'll take a look if I get a chance.  I'm going on vacation
> next week, tho, so don't hold your breath...

No problem.  My reason for posting now was simply to get a "sanity 
check" and make sure I'm not way off target or trying to do something 
crazy.  I've invested quite a few hours into this already, and I have 
quite a few ahead (I deliberately said I was 90% complete knowing the 
old adage that the last 10% takes 90% of the time!), and a simple 
"sounds good" from someone else is a great motivator for me to continue 
compared to working completely in a vacuum with no feedback.

> I've locally modified the spin_lock() setup to automatically
> save/restore interrupt masks, because it's almost always done that way,
> but that can wait.

Yeah.  It's probably good to combine those two functions, b/c even if 
interrupts are already disabled, cli() and put_cpu_flags() can safely be 
nested.  I'm just not very keen on the whole concept of having to 
disable interrupts all the time for extended periods of time, although 
having SMP or HT will alleviate the performance hit somewhat. 
Ultimately, I would like for us to have super fine-grained locking with 
real-time capabilities, like Solaris has, but I don't even understand 
how our existing semaphore code works, much less the reader/writer locks 
that the kernel exports to drivers but that aren't being used at all 
internally.  Once I've finished reading sema.c and can grok what's going 
on and document it, I suspect we'll be able to get rid of 90% of the 
cases where we're currently using spinlocks by switching over to 
semaphores and r/w locks, or possibly the seqlock primitive I copied 
from Linux.

The spinlock problem really bit me when I added the timer offset code to 
get_system_time() b/c it's called a lot internally and disables 
interrupts to acquire the PIT timer spinlock.  Until we have a proper 
high-performance timer (I'll probably copy the Linux code which supports 
several types of timers and chooses the best one at boot-time), I'll 
probably hack this by reverting the kernel version to 1ms accuracy and 
returning the more accurate result in the syscall version.  I assume 
that in the cases where the kernel gets the time (mostly in bcache.c, 
sema.c, and in the TCP/IP stack), it doesn't need to be more accurate 
than it was before or else it would never have worked!

>>/**
>> * Description of function.
>> * \param nFoo param 1
>> * \return the answer to life, the universe, and everything (42).
>> * \pre precondition
>> * \post postcondition
>> * \invariant pre- and post- and in-between condition :-)
>> */
> 
> I've added to this, and it might be generally useful:
>  * \par Locks Required:
>  * \par Locks Taken:
> 
> Then again, it might not, but the scheduler locks all over the place, so
> I think it's usefull there.

Yes, definitely!  This is a big learning experience for me and I want to 
leverage my understanding of each function by documenting its 
assumptions and requirements.  In the short run, we can do a certain 
amount of static analysis by reading the comments and seeing what calls 
what; in the long run, if we follow a consistent notation, we could even 
do an automatic parsing of the code and a full static analysis of the 
call graph and locking requirements.  See, e.g. _Code Generation in 
Action_ by Jack Herrington, a great book with a lot of examples written 
in Ruby.

>>I also have a question for Daniel:  I would like to use the DLIST_ 
>>macros in more places but unfortunately your version doesn't have a 
>>pointer to the tail of the list so there's no quick way to append an 
>>item to the end of a list or get the last item, operations which are 
>>needed by most of the kernel's lists.  Do you have any plans for a new 
>>version of dlist.h that might address this?  If you can add that 
>>functionality to DLIST, then I'll take care of patching up the rest of 
>>the kernel to use it.
> 
> 
> It could definitely be done.  I have a version that does that locally.
> However, there are two ways to do it, and I want an opinion on which to
> use.  The first way is to just make the DLIST macros be a tail-queue.
> The second is to introduce a second set of DLIST macros that are a
> tail-queue, and keep the old ones unchanged.  The problem with a tail
> queue is that you need the head pointer more often (in particular,
> append and remove both need the head pointer in the tail-queue version,
> but not in the current version).  Opinions?

My inclination would be for correctness over optimization, and 
optimization at a gross level before we start fine-tuning.  Right now, 
DLIST is O(n) for appending or removing from the tail, while a 
tail-queue would be O(1), and with only a constant additional overhead 
for the other operations.  What I don't know is whether the additional 
use of the head pointer would screw things up from a caching or SMP 
perspective since it would be one additional cache line being modified 
every time.

But since we aren't at the stage for that type of low-level tuning to be 
productive (too many things in flux), I would argue for the single set 
of DLIST macros to be a tail-queue.  By supporting both kinds of lists, 
we would introduce two problems:  1) for the cases where the head-list 
is used, we will be "locked in" and perhaps miss the opportunity to try 
different algorithms or optimizations requiring tail access out of a 
desire to avoid switching over to the other kind of list, and 2) the 
confusion to others and possible introduction of bugs that could result 
from having two different sets of objects and primitives that do, 
essentially, the same thing.

-Jake