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

[Petr Mladek]

On Thu 2019-08-08 00:32:26, John Ogness 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);


> +		/* 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.

Best Regards,
Petr

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