Merge spin-lock implementations.

[skalk]

There are at least two different implementations for spin-locks in the generic lock-implementation and in Fiasco.OC's kernel-capability slot allocator. In general, there are some rare issues where we need a more simple lock implementation than the Cancelable_lock class, introducing thread-queues, blocking, etc. It would be nice to remedy the current code-duplication. Moreover, the lock-library's spin-lock already benefits from a kernel-specific performance hook (thread_yield() function) that slightly limits the performance drawback of the spin-lock. So it's straight-forward to make the internally used spin-lock of the lock-library useable to the outside-world.

[nfeske]

I like your patch but I am not sure if it is a good idea to provide the spin lock to the "outside world", i.e., making it part of the official Genode API. I must confess that I am a bit hesitant.

As you stated, the main advantages would be the possibility to reduce code duplication. One example that comes in mind right now is the recently introduced dde_kit spinlock, which contains code duplicated from lock.cc (shame on me). On the other hand, the API you proposed doesn't seem to be suitable for replacing the dde_kit spinlock because it follows the lines of the lock API too closely. The dde_kit spinlock is expected to consist of a basic int type only, for which there exists an init function but no deinit function. See the following commit for the explanation: https://github.com/genodelabs/genode/commit/48ac5143a28ffbdbc3ff4161d74c765291b99740

If deciding to make a spinlock facility part of the Genode API, wouldn't it be sensible to tailor its interface to the low level of the spinlock semantics rather than following the lines of the lock interface?

Another consideration is, of course, the breath and orthogonality of the Genode API. By adding a feature to the API, we have to commit to retain it the future. Do we really want to advertise the use of spinlocks to users of the Genode framework by making it part of the API? Because of the functional overlap of both lock and spinlock, users may expect both to have a similar body of support (such as a lock guard facility).

Those concerns could be remedied quite easily by placing the spinlock API in a non-public header for now. Once, we are able to answer the questions raised above, we could decide to make it public. What do you think?

[skalk]

I've no objections with respect to your objections. So I've done so.

[nfeske]

Very nice! Thanks for addressing all my concerns. I merged the patch into genodelabs/staging.

[blitz]

Given proper locks, are there usecases for spinlocks in user code?

[nfeske]

I am not aware of any compelling example. Hence, me resistance against offering such a facility at Genode's API. However, DDE Kit needs to provide a spin-lock implementation because Linux drivers are using spinlocks. All further (application-level) needs for spinlocks and atomic operations (i.e., for building lock-free algorithms) lie outside the scope of Genode. For such needs, I'd refer to libraries - for example, boost atomic comes in mind.

[blitz]

Regarding DDE: Would a Linux driver break, because spinlocks don't actually spin, but block? I really can't think of a good example not to use proper locks, when you have them.

[nfeske]

Indeed, Linux drivers work as expected when using blocking locks instead spinlocks. DDE kit used to implement the Linux spinlock API using normal (blocking) Genode locks. The only problem here was that spinlocks are expected to be just a plain data word (some int value). The old implementation used to allocate a 'Lock' object when 'spin_lock_init' was called and stored the pointer to the 'Lock' object as data word in the spinlock data structure. This seemed to work fine until I discovered that there are drivers that call 'spin_lock_init' on each IRQ. Because a spinlock is expected to be just a data word, there is no 'spin_lock_deinit' function. So each repeated call of 'spin_lock_init' implied the leak of 'Lock' object.

This is why I decided to add dde_kit_spin_lock to DDE Kit: https://github.com/genodelabs/genode/commit/48ac5143a28ffbdbc3ff4161d74c765291b99740 But the reason for doing so had nothing to do with any semantic difference between blocking locks and spin locks.

[blitz]

Initializing a spinlock on each IRQ sounds broken to me. Do you have a concrete example of a driver that does this? I'd love to have a look at the actual driver code.

[nfeske]

Don't know if its broken but it was certainly not anticipated by DDE Kit :-) Well, it doesn't cause problems in the Linux kernel. So DDE Kit has to deal with it.

The driver in question is the USB driver that is included in our 'linux_drivers' repository (it is pretty dated; maybe more recent versions behave differently). The lock leak became a problem when I used the USB storage driver as block session to boot our live CD from. Tracing back the problem was anything but fun because the driver is quite complex.

If you like to dig deeper, you are welcome. In this case, I'd suggest to start by instrumenting DDE kit's 'dde_kit_spin_lock_init' by printing some message and watch the log output scroll by. .-) If you need some workload for the block-session interface, the 'libports/run/libc_ffat.run' script may be a good starting point. You may also take 'gems/run/d3m_boot.run' as reference.

[skalk]

@blitz: Apart from the DDE-kit's spin-lock usage, I just wanted to add some motivation. A spin-lock is part of the "proper lock" in the current user-level lock implementation of Genode anyway, to protect the wait-queue. Moreover, we need some simple lock, not using a lot of Genode abstractions (e.g.: Genode's thread-objects) in the low-level capability-slot allocator of Fiasco.OC and NOVA, because here you run into a chicken or egg dilemma when using the "proper lock". In NOVA we use kernel-semaphores for this issue, in Fiasco.OC a simple spin-lock implementation. My first and foremost intention was to merge this "proper lock"'s and cap-slot allocator's spin-lock code.

[nfeske]

I just want to add that in our case the "spinlock" is indeed a yielding spinlock - at least for the most of the platform (not sure about NOVA atm). So in the contention case, no CPU cycles are wasted if there is the chance to yield time to the spinlock-owning thread.

[blitz]

Ah, ok. I remember this switch_to being a sleep at some point in the past, wasn't it? . :-)