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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Tue, 20 Aug 2019 10:15:18 +0200
From:   Petr Mladek <pmladek@...e.com>
To:     John Ogness <john.ogness@...utronix.de>
Cc:     linux-kernel@...r.kernel.org,
        Andrea Parri <andrea.parri@...rulasolutions.com>,
        Sergey Senozhatsky <sergey.senozhatsky@...il.com>,
        Sergey Senozhatsky <sergey.senozhatsky.work@...il.com>,
        Steven Rostedt <rostedt@...dmis.org>,
        Brendan Higgins <brendanhiggins@...gle.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Thomas Gleixner <tglx@...utronix.de>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Subject: numlist_pop(): Re: [RFC PATCH v4 1/9] printk-rb: add a new printk
 ringbuffer implementation

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.