Re: Yet another updated entropy patch

[Marcus Brinkmann]

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.

>      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?

> ! 

> + #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.  :)

> +         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.

> ! #ifdef MACH_KERNEL
> ! #ifdef MACH_ENTROPY

Maybe

#if defined (MACH_KERNEL) && defined (MACH_ENTROPY)

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));


> + #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.

> +     /***
> +      * 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.

> +     /* 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?

> + #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)"?

> + #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.

> + /* Variable Declrations */

Missing "a".

> + 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()?

> + 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.

> +
> + 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.

> +   // Sanity check!
> +   if (entropy_init_done == 1) {
> +     // should never happen
> +     return;
> +   }

Can't you use an assert()?

> +   /* 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 = 1;

> +   /* Lock so we don't get a race condition or something worse */

There is nothing worse ;)

> + /* 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;

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.

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).

Do you add timer randomness?

Thanks,
Marcus