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

[John Ogness <john.ogness@linutronix.de>]

On 2019-08-20, Petr Mladek <pmladek@suse.com> wrote:
>> --- /dev/null
>> +++ b/kernel/printk/numlist.c
>> +/**
>> + * numlist_pop() - Remove the oldest node from the list.
>> + *
>> + * @nl: The numbered list from which to remove the tail node.
>> + *
>> + * The tail node can only be removed if two conditions are satisfied:
>> + *
>> + * * The node is not the only node on the list.
>> + * * The node is not busy.
>> + *
>> + * If, during this function, another task removes the tail, this function
>> + * will try again with the new tail.
>> + *
>> + * Return: The removed node or NULL if the tail node cannot be removed.
>> + */
>> +struct nl_node *numlist_pop(struct numlist *nl)
>> +{
>> +	unsigned long tail_id;
>> +	unsigned long next_id;
>> +	unsigned long r;
>> +
>> +	/* cA: #1 */
>> +	tail_id = atomic_long_read(&nl->tail_id);
>> +
>> +	for (;;) {
>> +		/* cB */
>> +		while (!numlist_read(nl, tail_id, NULL, &next_id)) {
>> +			/*
>> +			 * @tail_id is invalid. Try again with an
>> +			 * updated value.
>> +			 */
>> +
>> +			cpu_relax();
>> +
>> +			/* cA: #2 */
>> +			tail_id = atomic_long_read(&nl->tail_id);
>> +		}
>
> The above while-cycle basically does the same as the upper for-cycle.
> It tries again with freshly loaded nl->tail_id. The following code
> looks easier to follow:
>
> 	do {
> 		tail_id = atomic_long_read(&nl->tail_id);
>
> 		/*
> 		 * Read might fail when the tail node has been removed
> 		 * and reused in parallel.
> 		 */
> 		if (!numlist_read(nl, tail_id, NULL, &next_id))
> 			continue;
>
> 		/* Make sure the node is not the only node on the list. */
> 		if (next_id == tail_id)
> 			return NULL;
>
> 		/* cC: Make sure the node is not busy. */
> 		if (nl->busy(tail_id, nl->busy_arg))
> 			return NULL;
>
> 	while (atomic_long_cmpxchg_relaxed(&nl->tail_id, tail_id, next_id) !=
> 			tail_id);
>
> 	/* This should never fail. The node is ours. */
> 	return nl->node(tail_id, nl->node_arg);

You will see that pattern in several cmpxchg() loops. The reason I chose
to do it that way was so that I could make use of the return value of
the failed cmpcxhg(). This avoids an unnecessary LOAD and establishes a
data dependency between the failed cmpxchg() and the following
numlist_read(). I suppose none of that matters since we only care about
the case where cmpxchg() is successful.

I agree that your variation is easier to read.

>> +		/* Make sure the node is not the only node on the list. */
>> +		if (next_id == tail_id)
>> +			return NULL;
>> +
>> +		/*
>> +		 * cC:
>> +		 *
>> +		 * Make sure the node is not busy.
>> +		 */
>> +		if (nl->busy(tail_id, nl->busy_arg))
>> +			return NULL;
>> +
>> +		r = atomic_long_cmpxchg_relaxed(&nl->tail_id,
>> +						tail_id, next_id);
>> +		if (r == tail_id)
>> +			break;
>> +
>> +		/* cA: #3 */
>> +		tail_id = r;
>> +	}
>> +
>> +	return nl->node(tail_id, nl->node_arg);
>
> If I get it correctly, the above nl->node() call should never fail.
> The node has been removed from the list and nobody else could
> touch it. It is pretty useful information and it might be worth
> mention it in a comment.

You are correct and I will add a comment.

> PS: I am scratching my head around the patchset. I'll try Peter's
> approach and comment independent things is separate mails.

I think it is an excellent approach. Especially when discussing the
memory barriers.

John Ogness