Re: numlist_push() barriers Re: [RFC PATCH v4 1/9] printk-rb: add a new printk ringbuffer implementation

[Petr Mladek]

On Tue 2019-08-27 16:28:55, John Ogness wrote:
> On 2019-08-27, Petr Mladek <pmladek@xxxxxxxx> wrote:
> >> On 2019-08-23, Petr Mladek <pmladek@xxxxxxxx> wrote:
> >>>> --- /dev/null
> >>>> +++ b/kernel/printk/numlist.c
> >>>> +void numlist_push(struct numlist *nl, struct nl_node *n, unsigned long id)
> >>>> +{
> > [...]
> >>>> +
> >>>> +	/* bB: #1 */
> >>>> +	head_id = atomic_long_read(&nl->head_id);
> >>>> +
> >>>> +	for (;;) {
> >>>> +		/* bC: */
> >>>> +		while (!numlist_read(nl, head_id, &seq, NULL)) {
> >>>> +			/*
> >>>> +			 * @head_id is invalid. Try again with an
> >>>> +			 * updated value.
> >>>> +			 */
> >>>> +
> >>>> +			cpu_relax();
> >>>
> >>> I have got very confused by this. cpu_relax() suggests that this
> >>> cycle is busy waiting until a particular node becomes valid.
> >>> My first though was that it must cause deadlock in NMI when
> >>> the interrupted code is supposed to make the node valid.
> >>>
> >>> But it is the other way. The head is always valid when it is
> >>> added to the list. It might become invalid when another CPU
> >>> moves the head and the old one gets reused.
> >>>
> >>> Anyway, I do not see any reason for cpu_relax() here.
> >> 
> >> You are correct. The cpu_relax() should not be there. But there is
> >> still an issue that this could spin hard if the head was recycled and
> >> this CPU does not yet see the new head value.
> >
> > I do not understand this. The head could get reused only after
> > head_id was replaced with the following valid node.
> > The next cycle is done with a new id that should be valid.
> >
> > Of course, the new ID might get reused as well. But then we just
> > repeat the cycle. We have to be able to find a valid head after
> > few cycles. The last valid ID could not get reused because nodes
> > can be removed only if was not the last valid node.
> 
> Sorry, I was not very precise with my language. I will try again...
> 
> nl->head_id is read using a relaxed read.

I wonder if the "relaxed read" causes the confusion. Could it read
the old id even when numlist_read() for this id failed?

If this is true then it should not be relaxed read.


> A second CPU may have added new nodes and removed/recycled
> the node with the ID that the first CPU read as the head.

This sounds like ABA problem. My understanding is that we
use ID to prevent these problems and could ignore them.


> As a result, the first CPU's numlist_read() will (correctly) fail. If
> numlist_read() failed in the first node() callback within numlist_read()
> (i.e. it sees that the node already has a new ID), there is no guarantee
> that rereading the head ID will provide a new ID. At some point the
> memory system would make the new head ID visible, but there could be
> some heavy spinning until that happens.
>
> Here is a litmus test showing the problem (using comments and verbose
> variable names):
> 
> C numlist_push_loop
> 
> {
> 	int node1 = 1;
> 	int node2 = 2;
> 	int *numlist_head = &node1;
> }
> 
> P0(int **numlist_head)
> {
> 	int *head;
> 	int id;
> 
> 	// read head ID
> 	head = READ_ONCE(*numlist_head);
> 
> 	// read head node ID
> 	id = READ_ONCE(*head);
> 
> 	// re-read head ID when node ID is unexpected
> 	head = READ_ONCE(*numlist_head);
> }
> 
> P1(int **numlist_head, int *node1, int *node2)
> {
> 	int *r0;
> 
> 	// push node2
> 	r0 = cmpxchg_release(numlist_head, node1, node2);
> 
> 	// pop node1, reassigning a new ID
> 	smp_store_release(node1, 3);
> }

I think that the Litmus test does not describe the code.
If it does then we need to fix the algorithm or barriers.

> The results show that P0 sees the head is node1 but also sees that
> node1's ID has changed. (And if node1's ID changed, it means P1 had
> previously replaced the head.) If P0 ran in a while-loop, at some point
> it _would_ see that node2 is now the head. But that is wasteful spinning
> and may possibly have negative influence on the memory system.

My undestanding is that only valid nodes are added to the list.

If a node read via head_id is not valid then head_id already
points to another valid node. Am I wrong, please?

Best Regards,
Petr