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

John Ogness
2019-08-21T05:41:34Z

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