random(4): Make entropy source deregistration safe

[cem]

Summary

Allow loadable modules that provide random entropy source(s) to safely
unload. Prior to this change, no driver could ensure that their
random_source structure was not being used by random_harvestq.c for any
period of time after invoking random_source_deregister().

This change converts the source_list LIST to a ConcurrencyKit CK_LIST and
uses an epoch(9) to protect typical read accesses of the list. The existing
HARVEST_LOCK spin mutex is used to safely add and remove list entries.
random_source_deregister() uses epoch_wait() to ensure no concurrent
source_list readers are accessing a random_source before freeing the list
item and returning to the caller.

Callers can safely unload immediately after random_source_deregister()
returns.

[cem]

I would like to get more eyeballs from anyone more familiar with CK and epoch(9) to sanity check the idea. If you know of anyone who would be a good reviewer, please let me know or add them directly. Thanks.

sys/dev/random/random_harvestq.c

221

We should probably turn SI_SUB_TASKQ + 1's myriad copies into an SI_SUB_EPOCH eventually.

[markm]

sys/dev/random/random_harvestq.c

221

That SI_SUB_EPOCH is looking really important now.

[markj]

sys/dev/random/random_harvestq.c

267

This function may acquire an sx lock if RANDOM_LOADABLE is configured, and that's not permitted in an epoch section.

Hmm. We acquire that lock earlier in this function though, so I guess we're recursing.

[cem]

sys/dev/random/random_harvestq.c

221

I’ll chase that up in a separate revision.

267

Yeah. The recursion should be permissible, if ugly? It may also be possible to convert the (random(4)) loadable module system into an epoch system, I think. One step at a time.

(RANDOM_LOADABLE gets periodically broken for months and we don’t get emails about it. Maybe someone (juniper?) would care if we shipped a release with it broken. But: not hugely popular and I’d love to not have it.)

Does this approach seem sane otherwise?

[jhb]

sys/dev/random/random_harvestq.c

267

I wonder if this epoch can actually replace the sx lock directly? You will still need a separate lock for the exclusive access, but perhaps the exclusive one wouldn't have to be an sx anymore.

On a cursory glance, it looks like this would work. I think you would need an epoch_wait() after clearing the function pointers during unload. I'm not sure you even need an xlock at all. You really just need a barrier between clearing the function pointers on unload and the epoch_wait(), but epoch_wait() probably has a sufficient barrier in its implementation already. This would remove the recursion altogether.

[cem]

sys/dev/random/random_harvestq.c

267

Yeah, that's what I had in mind. Do you think it makes sense to do all of that as part of this revision, or separately?

[cem]

sys/dev/random/random_harvestq.c

267

Hm, in investigating further, I don't believe a non-preemtible epoch can replace the CONFIG sx lock, because the random_reader_context calls it wraps may block. So maybe it makes sense to use a separate, preemptible epoch for that? Either way, I'd like to leave it for a future revision.

[jhb]

Probably ok to do as a followup. I think though that in the followup what yo would have to do is use a single epoch and just have it be preemptive in the RANDOM_LOADABLE case, maybe you can just do that in this commit as well to appease any assertions that might fire?

[cem]

In D22489#492132, @jhb wrote:

Probably ok to do as a followup. I think though that in the followup what yo would have to do is use a single epoch and just have it be preemptive in the RANDOM_LOADABLE case,

Hm, I'll give it a shot.

maybe you can just do that in this commit as well to appease any assertions that might fire?

Well, I won't commit this as-is if it trips WITNESS :-).

sys/dev/random/random_harvestq.c

221

https://reviews.freebsd.org/D22503

[cem]

sys/dev/random/random_harvestq.c

221

Correction: D22504

[cem]

The epoch API currently does not support sleeping in epoch_preempt
sections.

Is that bit still true? It seems to be the case:

_epoch_enter_preempt(epoch_t epoch, epoch_tracker_t et EPOCH_FILE_LINE)
{
...
    THREAD_NO_SLEEPING();

So I guess EPOCH_PREEMPT allows you to take ordinary (contested) mutexes and rwlocks and things like that, but not sxlocks or sleep(9). It looks like the sxlock recurse path shouldn't attempt to sleep, so long as there are no exclusive waiters. I guess we can't guarantee that, so there isn't a clear path forward here (for either proposal).

Maybe it would be useful to have a 3rd tier of epoch that allows sleeping, distinct from the preemptible class? This means the wait() and call() delays are potentially unbounded, but that's not a regression for an API already using sleepable locks. Much like we have a hierarchy today of sleepable -> "blockable" -> spin locks, maybe it makes sense to have a similar one in epoch(9)?

[cem]

Pending D22512.

[cem]

D22512 has landed and random_loadable no longer uses SX locks.

My current plan is to make the minor adjustment: SYSINIT(rs_epoch_init, SI_SUB_TASKQ + 1, => SI_SUB_EPOCH.

I am not sure if we need a pre-emptible epoch. random_harvest_direct acquires an ordinary (non-spin) mutex (Fortuna's global lock, which protects concurrent access to the entropy pools as well as the generator). Does that mean the epoch needs to be preemptible? (It is probably not suitable to use a spin mutex for Fortuna's global lock.)

[cem]

Switch to preemptible epoch for algorithm locks (e.g., Fortuna's pool mutex).

[markm]

I can't find anything to object to - but my epoch-fu is a bit lacking, so I'm trusting the other reviewers here.

[cem]

Thanks Mark! Epoch(9) is new to me too.

@markj , @jhb , does this revision make sense now? Hopefully the previous concerns about the config SX lock have been resolved externally by rS356096.

Fortuna's global mutex is a MTX_DEF, not a spin mutex, so I believe that means we need a PREEMPT epoch. I might be mistaken.

We can require that any Fortuna-alternative random(4) algorithm implementation (i.e., D22837) use only non-sleeping primitives.

I ran the current patch with EPOCH_TRACE enabled and did not see any warnings related to it. Quite a lot of Net epoch warnings, though.