[PATCH] (2/7) entropy batching

Oliver Xymoron (oxymoron@waste.org)
Fri, 23 Aug 2002 13:27:43 -0500


This smartens up and simplifies the batch entropy pool.

diff -ur a/drivers/char/random.c b/drivers/char/random.c
--- a/drivers/char/random.c 2002-08-23 12:43:20.000000000 -0500
+++ b/drivers/char/random.c 2002-08-23 12:43:22.000000000 -0500
@@ -526,7 +526,7 @@
}

/*
- * This function adds a byte into the entropy "pool". It does not
+ * This function adds a word into the entropy "pool". It does not
* update the entropy estimate. The caller should call
* credit_entropy_store if this is appropriate.
*
@@ -600,25 +600,19 @@
*
**********************************************************************/

-static __u32 *batch_entropy_pool;
-static int *batch_entropy_credit;
-static int batch_max;
-static int batch_head, batch_tail;
+static __u32 *batch_entropy_pool=0;
+static int batch_max, batch_pos, batch_credit, batch_samples;
static struct tq_struct batch_tqueue;
static void batch_entropy_process(void *private_);

/* note: the size must be a power of 2 */
static int __init batch_entropy_init(int size, struct entropy_store *r)
{
- batch_entropy_pool = kmalloc(2*size*sizeof(__u32), GFP_KERNEL);
+ batch_entropy_pool = kmalloc(size*sizeof(__u32), GFP_KERNEL);
if (!batch_entropy_pool)
return -1;
- batch_entropy_credit =kmalloc(size*sizeof(int), GFP_KERNEL);
- if (!batch_entropy_credit) {
- kfree(batch_entropy_pool);
- return -1;
- }
- batch_head = batch_tail = 0;
+
+ batch_pos = batch_credit = batch_samples = 0;
batch_max = size;
batch_tqueue.routine = batch_entropy_process;
batch_tqueue.data = r;
@@ -626,56 +620,61 @@
}

/*
- * Changes to the entropy data is put into a queue rather than being added to
- * the entropy counts directly. This is presumably to avoid doing heavy
- * hashing calculations during an interrupt in add_timer_randomness().
+ * Changes to the entropy data are put into a queue rather than being
+ * added to the entropy counts directly. This is to avoid doing heavy
+ * hashing calculations during an interrupt in add_timing_entropy().
* Instead, the entropy is only added to the pool once per timer tick.
+ *
+ * The batch pool intentionally allows wrap-around, to protect against
+ * flooding of untrusted data. Non-random data will not correlate with
+ * random data and can be safely XORed over existing data.
*/
-void batch_entropy_store(u32 a, u32 b, int num)
-{
- int new;

+void batch_entropy_store(u32 val, int bits)
+{
if (!batch_max)
return;

- batch_entropy_pool[2*batch_head] = a;
- batch_entropy_pool[(2*batch_head) + 1] = b;
- batch_entropy_credit[batch_head] = num;
-
- new = (batch_head+1) & (batch_max-1);
- if (new != batch_tail) {
- queue_task(&batch_tqueue, &tq_timer);
- batch_head = new;
- } else {
- DEBUG_ENT("batch entropy buffer full\n");
- }
+ batch_entropy_pool[batch_pos] ^= val;
+ batch_credit+=bits;
+ batch_samples++;
+ batch_pos = (batch_pos+1) & (batch_max-1);
+
+ queue_task(&batch_tqueue, &tq_timer);
}

/*
- * Flush out the accumulated entropy operations, adding entropy to the passed
- * store (normally random_state). If that store has enough entropy, alternate
- * between randomizing the data of the primary and secondary stores.
+ * Flush out the accumulated entropy operations, adding entropy to the
+ * passed store (normally random_state). Alternate between randomizing
+ * the data of the primary and secondary stores.
*/
static void batch_entropy_process(void *private_)
{
- struct entropy_store *r = (struct entropy_store *) private_, *p;
- int max_entropy = r->poolinfo.POOLBITS;
-
+ struct entropy_store *r = (struct entropy_store *) private_;
+ int samples, credit;
+
if (!batch_max)
return;

- p = r;
- while (batch_head != batch_tail) {
- if (r->entropy_count >= max_entropy) {
- r = (r == sec_random_state) ? random_state :
- sec_random_state;
- max_entropy = r->poolinfo.POOLBITS;
- }
- add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
- credit_entropy_store(r, batch_entropy_credit[batch_tail]);
- batch_tail = (batch_tail+1) & (batch_max-1);
+ /* switch pools if current full */
+ if (r->entropy_count >= r->poolinfo.POOLBITS) {
+ r = (r == sec_random_state) ?
+ random_state : sec_random_state;
}
- if (p->entropy_count >= random_read_wakeup_thresh)
+
+ credit=batch_credit;
+ samples=batch_samples;
+ batch_pos = batch_credit = batch_samples = 0;
+
+ /* Don't allow more credit BITS > pool WORDS */
+ if(credit > batch_max) credit=batch_max;
+ /* Check for pool wrap-around */
+ if(samples > batch_max) samples=batch_max;
+
+ add_entropy_words(r, batch_entropy_pool, samples);
+ credit_entropy_store(r, credit);
+
+ if (r->entropy_count >= random_read_wakeup_thresh)
wake_up_interruptible(&random_read_wait);
}

@@ -764,7 +763,7 @@

entropy = int_log2_16bits(delta);
}
- batch_entropy_store(num, time, entropy);
+ batch_entropy_store(num^time, entropy);
}

void add_keyboard_randomness(unsigned char scancode)
diff -ur a/include/linux/random.h b/include/linux/random.h
--- a/include/linux/random.h 2002-07-20 14:11:18.000000000 -0500
+++ b/include/linux/random.h 2002-08-23 12:43:22.000000000 -0500
@@ -46,7 +46,7 @@
extern void rand_initialize_irq(int irq);
extern void rand_initialize_blkdev(int irq, int mode);

-extern void batch_entropy_store(u32 a, u32 b, int num);
+extern void batch_entropy_store(u32 val, int bits);

extern void add_keyboard_randomness(unsigned char scancode);
extern void add_mouse_randomness(__u32 mouse_data);

-- 
 "Love the dolphins," she advised him. "Write by W.A.S.T.E.." 
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/