On 2019-08-20, Petr Mladek 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(>tail_id);
>> +
>> +for (;;) {
>> +/* cB */
>> +while (!numlist_read(nl, tail_id, NULL, _id)) {
>> +/*
>> + * @tail_id is invalid. Try again with an
>> + * updated value.
>> + */
>> +
>> +cpu_relax();
>> +
>> +/* cA: #2 */
>> +tail_id = atomic_long_read(>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(>tail_id);
>
> /*
>* Read might fail when the tail node has been removed
>* and reused in parallel.
>*/
> if (!numlist_read(nl, tail_id, NULL, _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(>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(>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
