Re: Yet another updated entropy patch

[Michael Casadevall]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

(this is a response to both emails about said patch)

Marcus: I don't think I've ever been nitpicked that badly in my  
life.  Congratulations!
On Jul 13, 2007, at 4:30 AM, Marcus Brinkmann wrote:

> Hi,
>
> some comments, not in order of importance.
>
> > It also has the patch in the proper format:
>
> Well, I prefer diff -rup, but what the heck.

To each his own. You can always apply the patch, and then cvs diff it  
however you want ;-)

> >      AM_CONDITIONAL([enable_kmsg], [false])
>
> I was going to suggest uppercase for automake conditionals, but you
> can refer to prior art, so nevermind :)
>
> > ! 
>
> Where have all your page breaks gone?

What page breaks?

> > ! 
>
> > + #ifdef MACH_ENTROPY
> > +           // Lets grab the cyclinder numbers for entropy

> Typo "cyclinder" -> "cylinder" and "Lets" -> "Let's" or even "We".  Do
> not use C++ style comments.  End your sentences with a period. <- The
> little thing at the end.  :)

If you were rating Mach on being grammatically correct, you'd be in  
for the
shock of your life. Periods are the exceptions, not the rule (I did  
however add it
to suit thy master, and I did correct the typos; if you know of a C/C+ 
+ aware spell
checker that works with vim, I'd use it in a heartbeat)

> > +           entropy_putdata(prev, sizeof(io_req_t));
>
> Put a spacef before an open parenthesis.  This should be:
>
>             entropy_putdata (prev, sizeof (io_req_t));
>
> Read the GNU coding style standards as well, if you haven't already.

Changed. I have read the GNU coding style, and quite honestly, it  
just makes
code look very ugly to me. I prefer classic K&R with tabs; much  
cleaner and
easier code to read without taking up too much screen real estate.
> > ! #ifdef MACH_KERNEL
> > ! #ifdef MACH_ENTROPY
>
> Maybe
>
> #if defined (MACH_KERNEL) && defined (MACH_ENTROPY)

Changed. I always though #if changed() was a non-standard extension
hence why I avoided using it.

> to keep it on a single line?
>
> > !               return ((*cn_tab->cn_getc)(cn_tab->cn_dev, 1));
>
> Should be
>                 return ((*cn_tab->cn_getc) (cn_tab->cn_dev, 1));
>
> space-wise, but don't change (or pay attention to) existing code like
> this:
>
> >                 return ((*romgetc)(1));

Changed to tabs. (you really love to nitpick, don't you :-P)

> > + #define entropyname           "entropy"
> > + extern int    entropyopen(), entropyclose(), entropyread(),
> > entropygetstat();
>
> Wrap your lines at 78 characters.  Use software which doesn't wrap
> overlong lines for you when you cut&paste it in emails.

I'll switch back to using Pine with fetchmail then, it's just it  
doesn't have native support for GPG signing messages.

> > +       /***
> > +        * Kirkeby put the get entropy function here, so will I
> > +        * the OR causes it to only get a some of the keypresses
> > +        * making this even more random when it fires (he got this
> > +        * from Linux originally
> > +        ***/
>
> Drop the ASCII art (***), end sentences with a period and match
> parenthesis (you are missing this one ->).  There should be a comma
> before "making".  It would be nice to let the reader know who Kirkeby
> is and where you got it from.

You call it art, I call it readability. I changed it to this:

/* Sune Kirkeby's entropy patch (which was a port of the
 * linux entropy drivers for GNU mach) placed the keyboard
 * entropy source here. I looked at that for an idea of
 * where how to do write this driver. */

> > +       /* Kick some mouse data to the entropy driver */
>
> Should be:
>
>         /* Kick some mouse data to the entropy driver.  */
>
> Note the two white spaces at the end.  If you always put two white
> spaces after a period, Emacs reflow magic will take care of overlong
> lines for you properly (M-q).
>
> > +       entropy_putchar((buttonchanges + moved.mm_deltaX
> > +                       + moved.mm_deltaY) | 0122);
>
> This is one of the most important lines in the whole patch for
> graphical desktop systems.  The mouse is one of the higher quality
> entropy generators in the system.  What's the OR 0122 for here?

The OR 122 is from how Linux does it. Now that I actually sit down  
and think about it,
especially with the addition of twisting code, it doesn't really make  
too much sense to
have it there, so its gone!

> > + #ifdef MACH_ENTROPY
> > +   /* Linux provides a nice way to get random bits, so lets use  
> > it */
> > +   // This generates a LOT of Ctrl-Cs for some reason. No idea whats
> > +   // going on here
> > +
> > +   // THe problem is that mach only has 1 block device, floppy
> > (major 3- Ctrl-C)
> > +   // so this is useless for entropic sources. If we ever get more
> > block devices
> > +   // Uncomment this to get it for additional entropy
> > +   //entropy_putchar(major);
> > + #endif
>
> Again, // -> /* */, especially for multi-line comments.
> May I suggest "(major 3- Ctrl-C)" -> "(major 3 corresponds to Ctrl- 
> C)"?

Changed .
> > + #include "entropy.h"
> > + #include <string.h>
> > + #include <kern/mach_clock.h>
>
> Please include local header files after project header files (unless
> there is an important reason for the order, which should be
> documented).  System header files come first, so the string.h can
> stay.
 Changed

> > + /* Variable Declrations */
>
> Missing "a".

Changed

> > + static char entropy_buffer[ENTROPYBUFSIZE]; /* Entropy Buffer */
> > + decl_simple_lock_data(static,entropy_lock); /* Lock to each
> > function */
> > + static int entropy_read_offset; /* Current read offset */
> > + static int entropy_write_offset; /* Current write offset */
> > + static int entropy_init_done = 0; /* If this device is already
> > initalized */
>
> You can do that (it's still put in the bss section these days), but if
> you do, be consistent and initialize all of them.  The alternative is
> to drop the "= 0".  If you initialize them here, why do you initialize
> them again in entropy_init()?

Changed

> > + static int entropy_in_use; /* Mark that this device is in use */
> > + static queue_head_t entropy_read_queue; /* I/O queue requests for
> > blocking read */
>
> Please put comments in an extra line before the definition, and
> seperate these two-line blocks with a blank line.
Done
> > +
> > + void entropyinit() {
>
> Put curly braces on their own line.  Put the function name in a new
> line in column 0, such that "rgrep ^entropyinit ." will find the
> definition.
Also done
> > +   // Sanity check!
> > +   if (entropy_init_done == 1) {
> > +     // should never happen
> > +     return;
> > +   }
>
> Can't you use an assert()?
I didn't know assert was available in mach. Done!

> > +   /* Initalize all variables to zero, and
> > +    * setup our queues and locks */
> > +   entropy_read_offset = 0;
> > +   entropy_write_offset = 0;
> > +   entropy_in_use = 0;
> > +   queue_init(&entropy_read_queue);
> > +   simple_lock_init(&entropy_lock);
> > +   entropy_init_done = 1;
> > + }
> > +
> > + io_return_t entropyopen(dev_t dev, int flag, io_req_t ior) {
> > +   /* Check to see if we've initalized entropy */
> > +   if(entropy_init_done == 0) {
> > +         entropyinit();
> > +   }
> > +
> > +   /* Lock the function so we don't get a race condition */
> > +   simple_lock(&entropy_lock);
>
> Note: Mach is not preemptive, so on a uniprocessor the whole locking
> stuff is defined away.  We talk about SMP only:
>
> You can not check for initialization without a lock that protects
> entropy_init_done.  Another CPU may already have done the
> initialization, but reordered writes such that entropy_init_done is
> set to 1 before the other stuff that should be initialized is written
> out.  Thus the sequence above doesn't do what you think it does, and
> it is wrong in kmsg.c also.
>
> You can do one of two things: Not care about SMP and put in a:
>
> #if NCPUS > 1
> #error Not SMP safe.
> #endif
>
> Or you can fix it properly by calling entropyinit() somewhere during
> machine initialization at boot time (in the assumption that if
> somebody implements SMP eventually, they will be careful to put a
> memory barrier after all machine initialization).
>
> What's entropy_in_use used for anyway?
Entropy_in_use was from an older version of the driver, its an  
artifact. I should have gone through this code much more throughly; I  
apologize :-/

As for entropy_init, it SHOULD be called by mach when it sets up its  
own internal devices, or the first time the driver is opened (see  
i386/i386at/conf.c). That being said, mach makes entropic output  
(such as from the console device) before the initialization happens  
so both putchar and putdata check and then initialize the driver. If  
you want to recommend a good spot to put entropyinit so I don't need  
this, I'd be glad to do it)
> > +   entropy_in_use = 1;
>
> > +   /* Lock so we don't get a race condition or something worse */
>
> There is nothing worse ;)

There is always something worse, we just can't see it ahead of time.

> > + /* Needed to make the compiler happy */
> > + static boolean_t entropy_read_done(io_req_t ior);
>
> We call this a "/* Forward declaration.  */".
>
> > + io_return_t entropyread(dev_t dev, io_req_t ior) {
> > +   int err, amt, len;
>
> Use one line for each variable.  Thanks for using at least three
> characters per variable, this makes searching much easier.
>
> > +  /* Determine how much we're reading out  */
> > +  /* amt is how much we want to copy out   */
> > +  /* len is how much we can copy out       */
>
> /* Determine how much we're reading out.  AMT is how much we want to
>    copy out, and LEN is how much we can copy out.  */
>
> > + void entropy_putchar(int c) {
>
> > +   /* We'll get data from a given source, and stick it in the  
> > buffer */
> > +   io_req_t ior;
> > +   /* Its possible we MIGHT get here before the device is opened */
> > +   /* so just make sure we're initalized before doing anythign!  */
> > +
> > +   if(!entropy_init_done) {
> > +     entropyinit();
> > +   }
>
> See above.
>
> > +   /* See if the buffer is full, if it is, bail out */
> > +   if (entropy_write_offset+1 == entropy_read_offset) {
> > +     return;
> > +   }
>
> This is a shame!  You shall not waste perfectly good entropy like
> this.  In fact, you just convinced me that we should do pool mixing in
> the kernel.  (But this is not the only reason).
>
> > +   // Advance the pointer for the next write
> > +   entropy_write_offset += 1;

I had it like this originally. At least when I sample I/O, if the  
device is constantly
getting entropy, it actually slows down the system by at least 5% to  
10% percent.
Other things like keyboard and mouse, which aren't as time sensitive  
as I/O aren't effected.
A potential solution is below

> Now for the more serious stuff: All entropy ain't equal.  Entropy from
> the network, keyboard, hard drive and mouse have very different
> quality.  There is no perfect way to estimate the amount of entropy
> from any of these sources, but I will give you a quick example why
> this is a problem.  Consider keyboard input.  Typically, we use maybe
> 70-80 characters, and not all equally often.  However, you store these
> in 8 bit which can hold 256 distinct values.  Clearly the 256 distinct
> possible values are not going to be evenly distributed.  Some will
> never occur, some will occur more often than others.  Network packets
> are similar, and mouse data is also not perfectly random (in fact, you
> OR a constant into the byte, and these bits will always be on no
> matter what).  In any case, entropy is often over-rated.
>
> There are two things missing in your patch:
>
> 1. Entropy, when collected, must be weighted with a conservative
> qualify *estimation*.  This is difficult to do, but the actual
> estimations can be tweaked.  However, the infrastructure must be put
> in place.  Linux for example separates the process of adding bytes to
> the pool (__add_entropy_words) and crediting the pool with entropy
> (credit_entropy_store).  An older version used to have a second
> parameter along with the entropy byte, I think.

That itself isn't that hard, I can simply add a new argument to the  
end of putchar and putdata.
I'm not really sure a good solution to this problem, but if we add  
quality, what we could do is
only sample from I/O sources to increase the general quality, and  
have a configurable setting
on when the buffer should top off so to speak.

For instance, lets say keyboard entropy is a 2, mouse entropy is a 4,  
and I/O is a 7 (on a scale of 1-10). For the sake of
simplicity, lets make our imaginary buffer 4 bites long, and lets  
assume we have get four bites of entropy from the keyboard.

Entropy Buffer: abcd
Entropy Quality : 8 (2*4)

The entropy device should block if the quality is above a specific  
point. At this point, since
no more keyboard entropy will make the entropy any strong, it should  
block

Now lets assume the user starts X11, and the system gets some data  
from the mouse. The
driver shouldn't block when getting mouse entropic data because it  
will raise the quality

Entropy Buffer: 8231
Entropy Quality: 16

At this point, the device should block taking in mouse or keyboard  
entropy
because it will not improve the entropy, but it still should accept  
disk I/O

Now lets assume the machine needs to get VM, and swaps out

Entropy Buffer: (cylinder numbers)
Entropy Quality: 28 (7*4)

Now the device would block completely because its at its max quality  
point

Now doing this isn't THAT hard (although figuring how to do it in a  
clean way that doesn't
use loads of memory will be a trick). I'm open to implementation  
ideas and tips.

> 2. The entropy pool then needs to be mixed, because the entropy is
> only an estimate and fluctuates wildly.  Mixing evens out the
> distribution.  Your current driver suggests a user-space mixing, but
> then the user space mixer needs to know the entropy estimate!  This
> could probably done by the control interface, but this starts to
> become unwildly.  Furthermore, it is not a good idea to drop entropy
> when the pool is full (you can't increase the entropy above the pool
> size, but you can improve the quality of the pool by mixing more
> entropy into it as a safety net, even when it is full).  Entropy is a
> scarce resource, and we have such poor entropy sources that pushing
> all data over to user space may be a performance issue in the current
> implementation (consider that all network traffic needs to be copied
> several times!).  It seems to make sense to me to mix in the kernel,
> and again in user space (user space then implements pools with
> different qualities, based on the high quality kernel entropy pool
> data).

Earlier versions of this driver did the mixing in kernel. After a few  
rounds on
the list, I took it out, and saved the code for implementation in the  
translator.
Readding it to the patch will be fairly easy, but I want to get  
everything else
figured out before I begin doing anything.

> Do you add timer randomness?
No, I found the timer really didn't add anything in terms of entropy -
it was too predictable :-)

(sorry for the late reply, the doctor put drops in my eye which  
blinded me from typing;
so I wasn't able to compose the email  :-/)

> Thanks,
> Marcus

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (Darwin)

iD8DBQFGmDnYV/FBeJ6jsZQRAtXcAJ9gJBcWEifpR+Beq6O+UtFcXnrxYACdGtqI
i5/rUe2sMrgP+M8ESwr4mr8=
=54Ez
-----END PGP SIGNATURE-----