random.c

讲述linux的初始化过程

	__asm__("roll %%cl,%0"
		:"=r" (word)
		:"0" (word),"c" (i));
	return word;
}
#endif

/*
 * More asm magic....
 * 
 * For entropy estimation, we need to do an integral base 2
 * logarithm.  
 *
 * Note the "12bits" suffix - this is used for numbers between
 * 0 and 4095 only.  This allows a few shortcuts.
 */
#if 0	/* Slow but clear version */
static inline __u32 int_ln_12bits(__u32 word)
{
	__u32 nbits = 0;
	
	while (word >>= 1)
		nbits++;
	return nbits;
}
#else	/* Faster (more clever) version, courtesy Colin Plumb */
static inline __u32 int_ln_12bits(__u32 word)
{
	/* Smear msbit right to make an n-bit mask */
	word |= word >> 8;
	word |= word >> 4;
	word |= word >> 2;
	word |= word >> 1;
	/* Remove one bit to make this a logarithm */
	word >>= 1;
	/* Count the bits set in the word */
	word -= (word >> 1) & 0x555;
	word = (word & 0x333) + ((word >> 2) & 0x333);
	word += (word >> 4);
	word += (word >> 8);
	return word & 15;
}
#endif

/**********************************************************************
 *
 * OS independent entropy store.   Here are the functions which handle
 * storing entropy in an entropy pool.
 * 
 **********************************************************************/

struct entropy_store {
	unsigned	add_ptr;
	int		entropy_count;
	int		input_rotate;
	int		extract_count;
	struct poolinfo poolinfo;
	__u32		*pool;
};

/*
 * Initialize the entropy store.  The input argument is the size of
 * the random pool.
 * 
 * Returns an negative error if there is a problem.
 */
static int create_entropy_store(int size, struct entropy_store **ret_bucket)
{
	struct	entropy_store	*r;
	struct	poolinfo	*p;
	int	poolwords;

	poolwords = (size + 3) / 4; /* Convert bytes->words */
	/* The pool size must be a multiple of 16 32-bit words */
	poolwords = ((poolwords + 15) / 16) * 16; 

	for (p = poolinfo_table; p->poolwords; p++) {
		if (poolwords == p->poolwords)
			break;
	}
	if (p->poolwords == 0)
		return -EINVAL;

	r = kmalloc(sizeof(struct entropy_store), GFP_KERNEL);
	if (!r)
		return -ENOMEM;

	memset (r, 0, sizeof(struct entropy_store));
	r->poolinfo = *p;

	r->pool = kmalloc(poolwords*4, GFP_KERNEL);
	if (!r->pool) {
		kfree(r);
		return -ENOMEM;
	}
	memset(r->pool, 0, poolwords*4);
	*ret_bucket = r;
	return 0;
}

/* Clear the entropy pool and associated counters. */
static void clear_entropy_store(struct entropy_store *r)
{
	r->add_ptr = 0;
	r->entropy_count = 0;
	r->input_rotate = 0;
	r->extract_count = 0;
	memset(r->pool, 0, r->poolinfo.poolwords*4);
}

static void free_entropy_store(struct entropy_store *r)
{
	if (r->pool)
		kfree(r->pool);
	kfree(r);
}

/*
 * This function adds a byte into the entropy "pool".  It does not
 * update the entropy estimate.  The caller should call
 * credit_entropy_store if this is appropriate.
 * 
 * The pool is stirred with a primitive polynomial of the appropriate
 * degree, and then twisted.  We twist by three bits at a time because
 * it's cheap to do so and helps slightly in the expected case where
 * the entropy is concentrated in the low-order bits.
 */
static void add_entropy_words(struct entropy_store *r, const __u32 *in,
			     int num)
{
	static __u32 const twist_table[8] = {
		         0, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
	unsigned i;
	int new_rotate;
	__u32 w;

	while (num--) {
		w = rotate_left(r->input_rotate, *in);
		i = r->add_ptr = (r->add_ptr - 1) & (r->poolinfo.poolwords-1);
		/*
		 * Normally, we add 7 bits of rotation to the pool.
		 * At the beginning of the pool, add an extra 7 bits
		 * rotation, so that successive passes spread the
		 * input bits across the pool evenly.
		 */
		new_rotate = r->input_rotate + 14;
		if (i)
			new_rotate = r->input_rotate + 7;
		r->input_rotate = new_rotate & 31;

		/* XOR in the various taps */
		w ^= r->pool[(i+r->poolinfo.tap1)&(r->poolinfo.poolwords-1)];
		w ^= r->pool[(i+r->poolinfo.tap2)&(r->poolinfo.poolwords-1)];
		w ^= r->pool[(i+r->poolinfo.tap3)&(r->poolinfo.poolwords-1)];
		w ^= r->pool[(i+r->poolinfo.tap4)&(r->poolinfo.poolwords-1)];
		w ^= r->pool[(i+r->poolinfo.tap5)&(r->poolinfo.poolwords-1)];
		w ^= r->pool[i];
		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
	}
}

/*
 * Credit (or debit) the entropy store with n bits of entropy
 */
static void credit_entropy_store(struct entropy_store *r, int num)
{
	int	max_entropy = r->poolinfo.poolwords*32;

	if (r->entropy_count + num < 0)
		r->entropy_count = 0;
	else if (r->entropy_count + num > max_entropy)
		r->entropy_count = max_entropy;
	else
		r->entropy_count = r->entropy_count + num;
}

/**********************************************************************
 *
 * Entropy batch input management
 *
 * We batch entropy to be added to avoid increasing interrupt latency
 *
 **********************************************************************/

static __u32	*batch_entropy_pool;
static int	*batch_entropy_credit;
static int	batch_max;
static int	batch_head, batch_tail;
static struct tq_struct	batch_tqueue;
static void batch_entropy_process(void *private_);

/* note: the size must be a power of 2 */
static int batch_entropy_init(int size, struct entropy_store *r)
{
	batch_entropy_pool = kmalloc(2*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_max = size;
	batch_tqueue.routine = batch_entropy_process;
	batch_tqueue.data = r;
	return 0;
}

void batch_entropy_store(u32 a, u32 b, int num)
{
	int	new;

	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 {
#if 0
		printk(KERN_NOTICE "random: batch entropy buffer full\n");
#endif
	}
}

static void batch_entropy_process(void *private_)
{
	int	num = 0;
	int	max_entropy;
	struct entropy_store *r	= (struct entropy_store *) private_, *p;
	
	if (!batch_max)
		return;

	max_entropy = r->poolinfo.poolwords*32;
	while (batch_head != batch_tail) {
		add_entropy_words(r, batch_entropy_pool + 2*batch_tail, 2);
		p = r;
		if (r->entropy_count > max_entropy && (num & 1))
			r = sec_random_state;
		credit_entropy_store(r, batch_entropy_credit[batch_tail]);
		batch_tail = (batch_tail+1) & (batch_max-1);
		num++;
	}
	if (r->entropy_count >= random_read_wakeup_thresh)
		wake_up_interruptible(&random_read_wait);
}

/*********************************************************************
 *
 * Entropy input management
 *
 *********************************************************************/

/* There is one of these per entropy source */
struct timer_rand_state {
	__u32		last_time;
	__s32		last_delta,last_delta2;
	int		dont_count_entropy:1;
};

static struct timer_rand_state keyboard_timer_state;
static struct timer_rand_state mouse_timer_state;
static struct timer_rand_state extract_timer_state;
static struct timer_rand_state *irq_timer_state[NR_IRQS];
static struct timer_rand_state *blkdev_timer_state[MAX_BLKDEV];

/*
 * This function adds entropy to the entropy "pool" by using timing
 * delays.  It uses the timer_rand_state structure to make an estimate
 * of how many bits of entropy this call has added to the pool.
 *
 * The number "num" is also added to the pool - it should somehow describe
 * the type of event which just happened.  This is currently 0-255 for
 * keyboard scan codes, and 256 upwards for interrupts.
 * On the i386, this is assumed to be at most 16 bits, and the high bits
 * are used for a high-resolution timer.
 *
 */
static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
{
	__u32		time;
	__s32		delta, delta2, delta3;
	int		entropy = 0;

#if defined (__i386__)
	if ( test_bit(X86_FEATURE_TSC, &boot_cpu_data.x86_capability) ) {
		__u32 high;
		__asm__(".byte 0x0f,0x31"
			:"=a" (time), "=d" (high));
		num ^= high;
	} else {
		time = jiffies;
	}
#else
	time = jiffies;
#endif

	/*
	 * Calculate number of bits of randomness we probably added.
	 * We take into account the first, second and third-order deltas
	 * in order to make our estimate.
	 */
	if (!state->dont_count_entropy) {
		delta = time - state->last_time;
		state->last_time = time;

		delta2 = delta - state->last_delta;
		state->last_delta = delta;

		delta3 = delta2 - state->last_delta2;
		state->last_delta2 = delta2;

		if (delta < 0)
			delta = -delta;
		if (delta2 < 0)
			delta2 = -delta2;
		if (delta3 < 0)
			delta3 = -delta3;
		if (delta > delta2)
			delta = delta2;
		if (delta > delta3)
			delta = delta3;

		/*
		 * delta is now minimum absolute delta.
		 * Round down by 1 bit on general principles,
		 * and limit entropy entimate to 12 bits.
		 */
		delta >>= 1;
		delta &= (1 << 12) - 1;

		entropy = int_ln_12bits(delta);
	}
	batch_entropy_store(num, time, entropy);
}

void add_keyboard_randomness(unsigned char scancode)
{
	static unsigned char last_scancode;
	/* ignore autorepeat (multiple key down w/o key up) */
	if (scancode != last_scancode) {
		last_scancode = scancode;
		add_timer_randomness(&keyboard_timer_state, scancode);
	}
}

void add_mouse_randomness(__u32 mouse_data)
{
	add_timer_randomness(&mouse_timer_state, mouse_data);
}

void add_interrupt_randomness(int irq)
{
	if (irq >= NR_IRQS || irq_timer_state[irq] == 0)
		return;

	add_timer_randomness(irq_timer_state[irq], 0x100+irq);
}

void add_blkdev_randomness(int major)
{
	if (major >= MAX_BLKDEV)
		return;

	if (blkdev_timer_state[major] == 0) {
		rand_initialize_blkdev(major, GFP_ATOMIC);
		if (blkdev_timer_state[major] == 0)
			return;
	}
		
	add_timer_randomness(blkdev_timer_state[major], 0x200+major);
}

/******************************************************************
 *
 * Hash function definition
 *
 *******************************************************************/

/*
 * This chunk of code defines a function
 * void HASH_TRANSFORM(__u32 digest[HASH_BUFFER_SIZE + HASH_EXTRA_SIZE],
 * 		__u32 const data[16])
 * 
 * The function hashes the input data to produce a digest in the first
 * HASH_BUFFER_SIZE words of the digest[] array, and uses HASH_EXTRA_SIZE
 * more words for internal purposes.  (This buffer is exported so the
 * caller can wipe it once rather than this code doing it each call,
 * and tacking it onto the end of the digest[] array is the quick and
 * dirty way of doing it.)
 *
 * It so happens that MD5 and SHA share most of the initial vector
 * used to initialize the digest[] array before the first call:
 * 1) 0x67452301
 * 2) 0xefcdab89
 * 3) 0x98badcfe
 * 4) 0x10325476
 * 5) 0xc3d2e1f0 (SHA only)
 * 
 * For /dev/random purposes, the length of the data being hashed is
 * fixed in length, so appending a bit count in the usual way is not
 * cryptographically necessary.
 */

#ifdef USE_SHA

#define HASH_BUFFER_SIZE 5
#define HASH_EXTRA_SIZE 80
#define HASH_TRANSFORM SHATransform

/* Various size/speed tradeoffs are available.  Choose 0..3. */