[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Yet another updated entropy patch

From: Michael Casadevall
Subject: Re: Yet another updated entropy patch
Date: Fri, 13 Jul 2007 22:50:00 -0400

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:


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?


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


#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

                return ((*romgetc)(1));

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

+ #define entropyname           "entropy"
+ extern int    entropyopen(), entropyclose(), entropyread(),

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!

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


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

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

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  :-/)


Version: GnuPG v1.4.6 (Darwin)


reply via email to

[Prev in Thread] Current Thread [Next in Thread]