Differential D22879 Diff 65848 head/sys/dev/random/fortuna.c

Changeset View

Standalone View

head/sys/dev/random/fortuna.c

Show First 20 Lines • Show All 119 Lines • ▼ Show 20 Lines	#ifdef _KERNEL
/* For use when 'pacing' the reseeds */		/* For use when 'pacing' the reseeds */
sbintime_t fs_lasttime;		sbintime_t fs_lasttime;
#endif		#endif
/* Reseed lock */		/* Reseed lock */
mtx_t fs_mtx;		mtx_t fs_mtx;
} fortuna_state;		} fortuna_state;

/*		/*
* This knob enables or disables Concurrent Reads. The plan is to turn it on		* This knob enables or disables the "Concurrent Reads" Fortuna feature.
* by default sometime before 13.0 branches.
*		*
* The benefit is improved concurrency in Fortuna. That is reflected in two		* The benefit of Concurrent Reads is improved concurrency in Fortuna. That is
* related aspects:		* reflected in two related aspects:
*		*
* 1. Concurrent devrandom readers can achieve similar throughput to a single		* 1. Concurrent full-rate devrandom readers can achieve similar throughput to
* reader thread.		* a single reader thread (at least up to a modest number of cores; the
		* non-concurrent design falls over at 2 readers).
*		*
* 2. The rand_harvestq process spends much less time spinning when one or more		* 2. The rand_harvestq process spends much less time spinning when one or more
* readers is processing a large request. Partially this is due to		* readers is processing a large request. Partially this is due to
* rand_harvestq / ra_event_processor design, which only passes one event at		* rand_harvestq / ra_event_processor design, which only passes one event at
* a time to the underlying algorithm. Each time, Fortuna must take its		* a time to the underlying algorithm. Each time, Fortuna must take its
* global state mutex, potentially blocking on a reader. Our adaptive		* global state mutex, potentially blocking on a reader. Our adaptive
* mutexes assume that a lock holder currently on CPU will release the lock		* mutexes assume that a lock holder currently on CPU will release the lock
* quickly, and spin if the owning thread is currently running.		* quickly, and spin if the owning thread is currently running.
*		*
		* (There is no reason rand_harvestq necessarily has to use the same lock as
		* the generator, or that it must necessarily drop and retake locks
		* repeatedly, but that is the current status quo.)
		*
* The concern is that the reduced lock scope might results in a less safe		* The concern is that the reduced lock scope might results in a less safe
* random(4) design. However, the reduced-lock scope design is still		* random(4) design. However, the reduced-lock scope design is still
* fundamentally Fortuna. This is discussed below.		* fundamentally Fortuna. This is discussed below.
*		*
* Fortuna Read() only needs mutual exclusion between readers to correctly		* Fortuna Read() only needs mutual exclusion between readers to correctly
* update the shared read-side state: just C, the 128-bit counter, and K, the		* update the shared read-side state: C, the 128-bit counter; and K, the
* current cipher key.		* current cipher/PRF key.
*		*
* In the Fortuna design, the global counter C should provide an independent		* In the Fortuna design, the global counter C should provide an independent
* range of values per generator (CTR-mode cipher or similar) invocation.		* range of values per request.
*		*
* Under lock, we can save a copy of C on the stack, and increment the global C		* Under lock, we can save a copy of C on the stack, and increment the global C
* by the number of blocks a Read request will require.		* by the number of blocks a Read request will require.
*		*
* Still under lock, we can save a copy of the key K on the stack, and then		* Still under lock, we can save a copy of the key K on the stack, and then
* perform the usual key erasure K' <- Keystream(C, K, ...). This does require		* perform the usual key erasure K' <- Keystream(C, K, ...). This does require
* generating 256 bits (32 bytes) of cryptographic keystream output with the		* generating 256 bits (32 bytes) of cryptographic keystream output with the
* global lock held, but that's all; none of the user keystream generation must		* global lock held, but that's all; none of the API keystream generation must
* be performed under lock.		* be performed under lock.
*		*
* At this point, we may unlock.		* At this point, we may unlock.
*		*
* Some example timelines below (to oversimplify, all requests are in units of		* Some example timelines below (to oversimplify, all requests are in units of
* native blocks, and the keysize happens to be equal or less to the native		* native blocks, and the keysize happens to be equal or less to the native
* blocksize of the underlying cipher, and the same sequence of two requests		* blocksize of the underlying cipher, and the same sequence of two requests
* arrive in the same order). The possibly expensive consumer keystream		* arrive in the same order). The possibly expensive consumer keystream
Show All 34 Lines
* 2: <- Keystream 2: <1 block generated>		* 2: <- Keystream 2: <1 block generated>
* 2: K'' := Keystream(C''', K', 1) 2: C'''' := C''' + 1		* 2: K'' := Keystream(C''', K', 1) 2: C'''' := C''' + 1
* 2: <1 block generated> 2: <- Keystream		* 2: <1 block generated> 2: <- Keystream
* 2: C'''' := C''' + 1 2:Unlock()		* 2: C'''' := C''' + 1 2:Unlock()
* 2: <- Keystream		* 2: <- Keystream
* 2: <- GenBytes()		* 2: <- GenBytes()
* 2:Unlock()		* 2:Unlock()
*		*
* Just prior to unlock, shared state is still identical:		* Just prior to unlock, global state is identical:
* ------------------------------------------------------		* ------------------------------------------------------
*		*
* C'''' == (C_0 + N + 1) + M + 1 C'''' == (C_0 + N + 1) + M + 1		* C'''' == (C_0 + N + 1) + M + 1 C'''' == (C_0 + N + 1) + M + 1
* K'' == keystream generated from K'' == keystream generated from		* K'' == keystream generated from K'' == keystream generated from
* C_0 + N + 1 + M, K'. C_0 + N + 1 + M, K'.		* C_0 + N + 1 + M, K'. C_0 + N + 1 + M, K'.
* K' has been erased. K' has been erased.		* K' has been erased. K' has been erased.
*		*
* Finally, in the new design, the two consumer threads can finish the		* Finally, in the new design, the two consumer threads can finish the
Show All 16 Lines
* The generated user keystream for both threads is identical between the two		* The generated user keystream for both threads is identical between the two
* implementations:		* implementations:
*		*
* 1: Keystream(C_0, K_0, N) 1: Keystream(stack_C, stack_K, N)		* 1: Keystream(C_0, K_0, N) 1: Keystream(stack_C, stack_K, N)
* 2: Keystream(C'', K', M) 2: Keystream(stack_C', stack_K', M)		* 2: Keystream(C'', K', M) 2: Keystream(stack_C', stack_K', M)
*		*
* (stack_C == C_0; stack_K == K_0; stack_C' == C''; stack_K' == K'.)		* (stack_C == C_0; stack_K == K_0; stack_C' == C''; stack_K' == K'.)
*/		*/
static bool fortuna_concurrent_read __read_frequently = false;		static bool fortuna_concurrent_read __read_frequently = true;

#ifdef _KERNEL		#ifdef _KERNEL
static struct sysctl_ctx_list random_clist;		static struct sysctl_ctx_list random_clist;
RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);		RANDOM_CHECK_UINT(fs_minpoolsize, RANDOM_FORTUNA_MINPOOLSIZE, RANDOM_FORTUNA_MAXPOOLSIZE);
#else		#else
static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];		static uint8_t zero_region[RANDOM_ZERO_BLOCKSIZE];
#endif		#endif

▲ Show 20 Lines • Show All 562 Lines • Show Last 20 Lines