Skip to contentSkip to conversation

printk: replace ringbuffer

PATCH Superseded John Ogness 5 participants 31 messages May 1, 2020 – Jun 11, 2020

Subsystems (4)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

John Ogness

author maintainer
#0 lore raw

v2 cover printk: replace ringbuffer

Hello,

Here is a v2 for the first series to rework the printk subsystem. The v1 and history are here [0]. This first series only replaces the existing ringbuffer implementation. No locking is removed. No semantics/behavior of printk are changed.

The VMCOREINFO is updated. RFC patches for the external tools crash(8) [1] and makedumpfile(8) [2] have been submitted that allow the new ringbuffer to be correctly read.

This series is in line with the agreements [3] made at the meeting during LPC2019 in Lisbon, with 1 exception: support for dictionaries will not be discontinued [4]. Dictionaries are stored in a separate buffer so that they cannot interfere with the human-readable buffer.

The list of changes since v1:

printk_ringbuffer
=================
- documentation formatting/wording cleanup
- main memory barrier comments moved from memory accesses to memory barriers
- remove all symbol exporting of printk_ringbuffer functions
- add prb_count_lines() for line counting so printk.c can also use this functionality
- add prb_read_valid_info() to just read record meta-data
- remove @line_count out of printk_record (there is now an interface for line counting)
- to_block(): remove intermediate (char *) typecast
- data_alloc(): use WRITE_ONCE for writing block ID
- data_push_tail(): fix test condition for tail LPOS already pushed
- data_push_tail(): continue loop rather than try cmpxchg() if tail LPOS was pushed
- data_push_tail(): add memory barrier before pushing tail LPOS so readers can recognize if data has expired while reading the descriptor
- data_make_reusable(): added memory barrier and logic to protect against invalid read of block ID
- data_alloc(): add memory barrier to guarantee the tail ID is stored before updating the block ID
- desc_reserve(): add memory barrier before checking ID to make sure the head ID is read before the tail ID
- desc_reserve(): move memory barrier to before the head ID is pushed to guarantee the tail ID is stored before the head ID

printk.c
========
- remove static syslog_record/console_record (use dynamic allocation and in-place buffer manipulation instead)
- reduce expected average message size from 64 to 32
- add printk_record initializers to simplify reader and writer code
- fix wrong return value when log_store() truncates
- add full VMCOREINFO needed by makedumpfile(8)
- change record_print_text() to add prefix data to the buffer in-place instead of requiring a 2nd buffer
- add helper to calculate text size when prefix added:
get_record_text_size() (used together with prb_count_lines() or prb_read_valid_info() to get full text size, rather than abusing record_print_text() for this purpose)
- syslog_print_all(): fix missing break if copy_to_user() failed
- moved "messages dropped" printing to call_console_drivers()

John Ogness

[0] https://lkml.kernel.org/r/[email protected]
[1] https://www.redhat.com/archives/crash-utility/2020-April/msg00080.html
[2] https://lists.infradead.org/pipermail/kexec/2020-April/024906.html
[3] https://lkml.kernel.org/r/[email protected]
[4] https://lkml.kernel.org/r/[email protected]

John Ogness (3):
crash: add VMCOREINFO macro for anonymous structs
printk: add lockless buffer
printk: use the lockless ringbuffer

 include/linux/crash_core.h        |    3 +
 include/linux/kmsg_dump.h         |    2 -
 kernel/printk/Makefile            |    1 +
 kernel/printk/printk.c            |  938 +++++++++--------
 kernel/printk/printk_ringbuffer.c | 1626 +++++++++++++++++++++++++++++
 kernel/printk/printk_ringbuffer.h |  369 +++++++
 6 files changed, 2491 insertions(+), 448 deletions(-)
 create mode 100644 kernel/printk/printk_ringbuffer.c
 create mode 100644 kernel/printk/printk_ringbuffer.h
Signature · 7 lines
2.20.1


_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec
author maintainer
#1 lore raw

PATCH v2 1/3 crash: add VMCOREINFO macro for anonymous structs

Some structs are not named and are only available via their typedef. Add a VMCOREINFO macro to export field offsets for such structs.

---
 include/linux/crash_core.h | 3 +++
 1 file changed, 3 insertions(+)
include/linux/crash_core.h +3 -0
index 525510a9f965..43b51c9df571 100644
@@ -53,6 +53,9 @@ phys_addr_t paddr_vmcoreinfo_note(void);
 #define VMCOREINFO_OFFSET(name, field) \
 	vmcoreinfo_append_str("OFFSET(%s.%s)=%lu\n", #name, #field, \
 			      (unsigned long)offsetof(struct name, field))
+#define VMCOREINFO_TYPE_OFFSET(name, field) \
+	vmcoreinfo_append_str("OFFSET(%s.%s)=%lu\n", #name, #field, \
+			      (unsigned long)offsetof(name, field))
 #define VMCOREINFO_LENGTH(name, value) \
 	vmcoreinfo_append_str("LENGTH(%s)=%lu\n", #name, (unsigned long)value)
 #define VMCOREINFO_NUMBER(name) \
Signature · 7 lines
2.20.1


_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec
maintainer
#2 lore raw

Re: [PATCH v2 1/3] crash: add VMCOREINFO macro for anonymous structs

Quoted 2 lines · John Ogness

Some structs are not named and are only available via their typedef. Add a VMCOREINFO macro to export field offsets for such structs.

Honestly, I did not get the meaning until I looked at the sample usage added by the 2nd patch.

The term "anonymous structures" has another meaning in C++. It is used for structures without any name that are defined inside a named structure.

Something like this might be better:

"crash: Add VMCOREINFO macro to define offset in a struct declared by typedef

The existing macro VMCOREINFO_OFFSET() can't be used for structures declared via typedef because "struct" is not part of type definition.

Create another macro for this purpose."

Anyway, thanks a lot for the prototype of crash implementation. I am happy that it is possible.

Best Regards,
Petr

PS: It might take few more days until I send some feedback for the other patches. They are a bit more complex ;-)

author maintainer
#3 lore raw

PATCH v2 2/3 printk: add lockless buffer

In reply to John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

The printk_ringbuffer is made up of 3 internal ringbuffers:

desc_ring:
A ring of descriptors. A descriptor contains all record meta data (sequence number, timestamp, loglevel, etc.) as well as internal state information about the record and logical positions specifying where in the other ringbuffers the text and dictionary strings are located.

text_data_ring:
A ring of data blocks. A data block consists of an unsigned long integer (ID) that maps to a desc_ring index followed by the text string of the record.

dict_data_ring:
A ring of data blocks. A data block consists of an unsigned long integer (ID) that maps to a desc_ring index followed by the dictionary string of the record.

The internal state information of a descriptor is the key element to allow readers and writers to locklessly synchronize access to the data.

---
 kernel/printk/Makefile            |    1 +
 kernel/printk/printk_ringbuffer.c | 1626 +++++++++++++++++++++++++++++
 kernel/printk/printk_ringbuffer.h |  369 +++++++
 3 files changed, 1996 insertions(+)
 create mode 100644 kernel/printk/printk_ringbuffer.c
 create mode 100644 kernel/printk/printk_ringbuffer.h
kernel/printk/Makefile +1 -0
index 4d052fc6bcde..eee3dc9b60a9 100644
@@ -2,3 +2,4 @@
 obj-y	= printk.o
 obj-$(CONFIG_PRINTK)	+= printk_safe.o
 obj-$(CONFIG_A11Y_BRAILLE_CONSOLE)	+= braille.o
+obj-$(CONFIG_PRINTK)	+= printk_ringbuffer.o
kernel/printk/printk_ringbuffer.c new file +1626 -0

1,626 lines not on this page · raw message

kernel/printk/printk_ringbuffer.h new file +369 -0

369 lines not on this page · raw message

Signature · 7 lines
2.20.1


_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec
author maintainer
#4 lore raw

Re: [PATCH v2 2/3] printk: add lockless buffer

Hi,

For the v2 I was supposed to have fixed a bug in v1. The cover letter stated:

- data_push_tail(): continue loop rather than try cmpxchg() if tail LPOS was pushed

Unfortunately, the fix was incorrect and actually made it worse. The explanation and patch are below.

Quoted 5 lines · John Ogness
kernel/printk/printk_ringbuffer.c new file +0 -0
new file mode 100644
index 000000000000..e0a66468d4f3

...

Quoted 53 lines
kernel/printk/printk_ringbuffer.c new file +53 -0
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */

kernel/printk/printk_ringbuffer.c

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */
+			if (next_lpos == tail_lpos)
+				return false;
+
+			/* Another task pushed the tail. Try again. */
+			tail_lpos = next_lpos;
+			continue;

The purpose of the continue is to try again _without_ attempting a cmpxchg(). However, since the cmpxchg() is in the while condition, it _is_ called. This is a major problem because if the cmpxchg() succeeds (highly likely at this point) then the smp_mb() is not called and success is returned even though the tail may not have been pushed far enough.

The cmpxchg() needs to be moved out of the while condition so that a continue can be used as intended. Patch below.

Quoted 5 lines
kernel/printk/printk_ringbuffer.c new file +5 -0
+		}
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This

kernel/printk/printk_ringbuffer.c

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		 * allows readers to identify if data has expired while
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */
+
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+
+	return true;
+}

John Ogness

kernel/printk/printk_ringbuffer.c +8 -7
index e0a66468d4f3..ac542bdb8deb 100644
@@ -546,11 +546,8 @@ static bool data_push_tail(struct printk_ringbuffer *rb,
 
 	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
 
-	do {
-		/* Done, if the tail lpos is already at or beyond @lpos. */
-		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
-			break;
-
+	/* Done, if the tail lpos is already at or beyond @lpos. */
+	while ((lpos - tail_lpos) - 1 < DATA_SIZE(data_ring)) {
 		/*
 		 * Make all descriptors reusable that are associated with
 		 * data blocks before @lpos.
@@ -601,8 +598,12 @@ static bool data_push_tail(struct printk_ringbuffer *rb,
 		 */
 		smp_mb(); /* LMM(data_push_tail:C) */
 
-	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
-			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+		if (atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+				&tail_lpos,
+				next_lpos)) { /* LMM(data_push_tail:D) */
+			break;
+		}
+	}
 
 	return true;
 }

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

#5 lore raw

Re: [PATCH v2 2/3] printk: add lockless buffer

Quoted 3 lines · John Ogness

The cmpxchg() needs to be moved out of the while condition so that a continue can be used as intended. Patch below.

This seems pointless and wrong (patch edited to remove the '-' lines so that you see the end result):

kernel/printk/printk_ringbuffer.c static bool data_push_tail(struct printk_ringbuffer *rb, · line 605

Quoted 7 lines
                smp_mb(); /* LMM(data_push_tail:C) */
kernel/printk/printk_ringbuffer.c +5 -0
+               if (atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+                               &tail_lpos,
+                               next_lpos)) { /* LMM(data_push_tail:D) */
+                       break;
+               }

Doing an "smp_mb()" followed by a "cmpxchg_relaxed" seems all kinds of odd and pointless, and is very much non-optimal on x86 for example.,

Just remove the smp_mb(), and use the non-relaxed form of cmpxchg. It's defined to be fully ordered if it succeeds (and if the cmpxchg doesn't succeed, it's a no-op and the memory barrier shouldn't make any difference).

Otherwise you'll do two memory ordering operations on x86 (and probably some other architectures), since the cmpxchg is always ordered on x86 and there exists no "relaxed" form of it.

Linus

author maintainer
#6 lore raw

Re: [PATCH v2 2/3] printk: add lockless buffer

Quoted 11 lines · Linus Torvalds

kernel/printk/printk_ringbuffer.c static bool data_push_tail(struct printk_ringbuffer *rb, · line 605

Quoted 7 lines
                smp_mb(); /* LMM(data_push_tail:C) */
kernel/printk/printk_ringbuffer.c +5 -0
+               if (atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+                               &tail_lpos,
+                               next_lpos)) { /* LMM(data_push_tail:D) */
+                       break;
+               }

Doing an "smp_mb()" followed by a "cmpxchg_relaxed" seems all kinds of odd and pointless, and is very much non-optimal on x86 for example.,

Quoted 8 lines

Just remove the smp_mb(), and use the non-relaxed form of cmpxchg. It's defined to be fully ordered if it succeeds (and if the cmpxchg doesn't succeed, it's a no-op and the memory barrier shouldn't make any difference).

Otherwise you'll do two memory ordering operations on x86 (and probably some other architectures), since the cmpxchg is always ordered on x86 and there exists no "relaxed" form of it.

ACK.

All three smp_mb()'s and both smp_wmb()'s sit directly next to cmpxchg_relaxed() calls. Having explicit memory barriers was helpful for identifying, proving, and testing a minimal set of pairs (on arm64), but all will be folded into full cmpxchg()'s for the next version.

John Ogness

maintainer
#7 lore raw

blk->id read race: was: [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 36 lines · John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

kernel/printk/printk_ringbuffer.c new file +26 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.

kernel/printk/printk_ringbuffer.c line 457

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */

This would deserve some comment:

1. Compiler could not optimize out the read because there is a data dependency on lpos_begin.

2. Compiler could not postpone the read because it is followed by smp_rmb().

So, is READ_ONCE() realy needed?

Well, blk->id clearly can be modified in parallel so we need to be careful. There is smp_rmb() right below. Do we needed smp_rmb() also before?

What about the following scenario?:

CPU0 CPU1

						data_alloc()
						  data_push_tail()

						blk = to_block(data_ring, begin_lpos)
						WRITE_ONCE(blk->id, id); /* LMM(data_alloc:B) */

desc_push_tail()
data_push_tail()

    tail_lpos = data_ring->tail_lpos;
    // see data_ring->tail_lpos already updated by CPU1

    data_make_reusable()

      // lpos_begin = tail_lpos via parameter
      blk = to_block(data_ring, lpos_begin);
      id = blk->id

Now: CPU0 might see outdated blk->id before CPU1 wrote new value
because there is no read barrier betwen reading tail_lpos and blk->id here.

The outdated id would cause desc_miss. CPU0 would return back to data_push_tail(). It will try to re-read data_ring->tail_lpos. But it will be the same as before because it already read the updated value.

As a result, data_alloc() would fail.

IMHO, we need smp_rmb() between data_ring->tail_lpos read and the related blk->id read. It should be either in data_push_tail() or in data_make_reusable().

Best Regards,
Petr

PS: I am still in the middle of the review. I think that it is better to discuss each race separately.

Quoted 141 lines
kernel/printk/printk_ringbuffer.c new file +141 -0
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}
+
+		d_state = desc_read(desc_ring, id,
+				    &desc); /* LMM(data_make_reusable:D) */
+
+		switch (d_state) {
+		case desc_miss:
+			return false;
+		case desc_reserved:
+			return false;
+		case desc_committed:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			desc_make_reusable(desc_ring, id);
+			break;
+		case desc_reusable:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			break;
+		}
+
+		/* Advance @lpos_begin to the next data block. */
+		lpos_begin = blk_lpos->next;
+	}
+
+	*lpos_out = lpos_begin;
+	return true;
+}
+
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */
+			if (next_lpos == tail_lpos)
+				return false;
+
+			/* Another task pushed the tail. Try again. */
+			tail_lpos = next_lpos;
+			continue;
+		}
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This
+		 * allows readers to identify if data has expired while

kernel/printk/printk_ringbuffer.c line 609

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */
+
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+
+	return true;
+}
+

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#8 lore raw

Re: blk->id read race: was: [PATCH v2 2/3] printk: add lockless buffer

Quoted 41 lines · Petr Mladek
Quoted 28 lines
kernel/printk/printk_ringbuffer.c new file +26 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.

kernel/printk/printk_ringbuffer.c line 457

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */

This would deserve some comment:

Quoted 7 lines

1. Compiler could not optimize out the read because there is a data dependency on lpos_begin.

2. Compiler could not postpone the read because it is followed by smp_rmb().

So, is READ_ONCE() realy needed?

I agree that it is not needed. Both the READ_ONCE() and its countering WRITE_ONCE() (data_alloc:B) only document the lockless shared access. I will remove both for the next version.

Do we still need a comment? Is it not obvious that there is a data dependency on @lpos_begin?

        blk = to_block(data_ring, lpos_begin);
        id = blk->id;
Quoted 27 lines

Well, blk->id clearly can be modified in parallel so we need to be careful. There is smp_rmb() right below. Do we needed smp_rmb() also before?

What about the following scenario?:

CPU0 CPU1

						data_alloc()
						  data_push_tail()

						blk = to_block(data_ring, begin_lpos)
						WRITE_ONCE(blk->id, id); /* LMM(data_alloc:B) */

desc_push_tail()
data_push_tail()

    tail_lpos = data_ring->tail_lpos;
    // see data_ring->tail_lpos already updated by CPU1

    data_make_reusable()

      // lpos_begin = tail_lpos via parameter
      blk = to_block(data_ring, lpos_begin);
      id = blk->id
Quoted 3 lines

Now: CPU0 might see outdated blk->id before CPU1 wrote new value
because there is no read barrier betwen reading tail_lpos and blk->id here.

In your example, CPU1 is pushing the tail and then setting the block ID for the _newly_ allocated block, that is located is _before_ the new tail. If CPU0 sees the new tail already, it is still reading a valid block ID, which is _not_ from the block that CPU1 is in the process of writing.

John Ogness

maintainer
#9 lore raw

Re: blk->id read race: was: [PATCH v2 2/3] printk: add lockless buffer

Quoted 45 lines · John Ogness
Quoted 44 lines · Petr Mladek
Quoted 28 lines
kernel/printk/printk_ringbuffer.c new file +26 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.

kernel/printk/printk_ringbuffer.c line 457

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */

This would deserve some comment:

1. Compiler could not optimize out the read because there is a data dependency on lpos_begin.

Quoted 8 lines
Quoted 4 lines

2. Compiler could not postpone the read because it is followed by smp_rmb().

So, is READ_ONCE() realy needed?

I agree that it is not needed. Both the READ_ONCE() and its countering WRITE_ONCE() (data_alloc:B) only document the lockless shared access. I will remove both for the next version.

Sounds good.

Quoted 2 lines

Do we still need a comment? Is it not obvious that there is a data dependency on @lpos_begin?

Sigh, I just wonder why I am always confusedby this. See below.

Quoted 34 lines
        blk = to_block(data_ring, lpos_begin);
        id = blk->id;
Quoted 27 lines

Well, blk->id clearly can be modified in parallel so we need to be careful. There is smp_rmb() right below. Do we needed smp_rmb() also before?

What about the following scenario?:

CPU0 CPU1

						data_alloc()
						  data_push_tail()

						blk = to_block(data_ring, begin_lpos)
						WRITE_ONCE(blk->id, id); /* LMM(data_alloc:B) */

desc_push_tail()
data_push_tail()

    tail_lpos = data_ring->tail_lpos;
    // see data_ring->tail_lpos already updated by CPU1

    data_make_reusable()

      // lpos_begin = tail_lpos via parameter
      blk = to_block(data_ring, lpos_begin);
      id = blk->id
Quoted 3 lines

Now: CPU0 might see outdated blk->id before CPU1 wrote new value
because there is no read barrier betwen reading tail_lpos and blk->id here.

Quoted 5 lines

In your example, CPU1 is pushing the tail and then setting the block ID for the _newly_ allocated block, that is located is _before_ the new tail. If CPU0 sees the new tail already, it is still reading a valid block ID, which is _not_ from the block that CPU1 is in the process of writing.

Ah, I see. I wrongly assumed that both CPO0 and CPU1 are working with the same block address. But if CPU0 sees the new tail_lpos, it is already looking at another block. And it is the classic fight against yet another potential CPUs that try to push the tail as well.

I wonder if the comment might look like:

/*
* No barrier is needed between reading tail_lpos and the related
* blk->id. Only CPU that modifies tail_lpos via cmpxchg is allowed
* to modify the related blk->id. CPUs that see the moved tail_lpos
* are looking at another block related to the new tail_lpos.
* It does not mater when the previous winner modifies the previous
* block.
*/

I am not sure how many people are confused like me. It is possible that it is not worth it. I just know that I did this mistake repeatedly ;-)

Best Regards,
Petr

author maintainer
#10 lore raw

Re: blk->id read race: was: [PATCH v2 2/3] printk: add lockless buffer

Quoted 43 lines · Petr Mladek
Quoted 32 lines
Quoted 32 lines
Quoted 32 lines
kernel/printk/printk_ringbuffer.c new file +30 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
Quoted 8 lines
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 457

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */

This would deserve some comment:

I wonder if the comment might look like:

Quoted 8 lines

/*
* No barrier is needed between reading tail_lpos and the related
* blk->id. Only CPU that modifies tail_lpos via cmpxchg is allowed
* to modify the related blk->id. CPUs that see the moved tail_lpos
* are looking at another block related to the new tail_lpos.
* It does not mater when the previous winner modifies the previous
* block.
*/

Sorry, but this comment does not make sense for me. The tail is pushed _before_ the block ID is modified. So any kind of barrier here (where we read the tail, then the block ID, i.e. the same order) would be inappropriate anyway.

Also, this comment only talks about when a new value is seen, but not about when the old value is seen. IMO it is seeing the old value that is worthy of a comment since that is the only case with a data race.

In preparation for my next version I have added the following comment:

blk = to_block(data_ring, lpos_begin);

/*
* When going from lpos to block pointer, the wrap around
* feature of the lpos value is lost. Since another CPU could
* invalidate this data area at any time, the data tail must
* be re-checked after the block ID has been read. */

id = blk->id; /* LMM(data_make_reusable:A) */

I think this comment also helps to further clarify "why" the following data tail check occurs.

John Ogness

maintainer
#11 lore raw

redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 76 lines · John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

kernel/printk/printk_ringbuffer.c new file +63 -0
new file mode 100644
index 000000000000..e0a66468d4f3
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */

kernel/printk/printk_ringbuffer.c line 494

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past. Well, it would just prove that it really needs a comment why this check is necessary. I looks redundant or just an optimization to me.

IMHO, the following check of the descriptor state should be enough:

1. This function returns "false" when the descriptor is in desc_misc or desc_reusable state or when it does not point back to the data.

In this case, data_push_tail() does similar check. It loads data_ring->tail_lpos as well. It returns false when the tail did not move. Otherwise, it calls data_make_reusable() again and has the same effect as the continue here.

2. This function returns true only when the descriptor is in committed or reusable state and points back to the same data block. In this, case it really contains consistent data.

OK, it is possible that the block is already reused when the descriptor is in reusable state. But it is possible only when data_ring->tail_lpos moved. In this case, cmpxchg in data_push_tail() would fail and we would go back as well.

Do I miss anything, please?

See also a nit below.

Quoted 83 lines
kernel/printk/printk_ringbuffer.c new file +83 -0
+
+		d_state = desc_read(desc_ring, id,
+				    &desc); /* LMM(data_make_reusable:D) */
+
+		switch (d_state) {
+		case desc_miss:
+			return false;
+		case desc_reserved:
+			return false;
+		case desc_committed:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			desc_make_reusable(desc_ring, id);
+			break;
+		case desc_reusable:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			break;
+		}
+
+		/* Advance @lpos_begin to the next data block. */
+		lpos_begin = blk_lpos->next;
+	}
+
+	*lpos_out = lpos_begin;
+	return true;
+}
+
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B

kernel/printk/printk_ringbuffer.c line 587

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */

I have been a bit confused whether next_lpos variable is used correctly everywhere. The primary purpose is to use a value provided by data_make_reusable() in the cmpxchg below.

But it is (mis)used here to temporary store the current tail_lpos value. Could we please use another variable here? IMHO, the following code would be more clear:

	tail_lpos_old = tail_lpos;
	tail_lpos = atomic_long_read(&data_ring->tail_lpos); /* LMM(data_push_tail:B) */

	if (tail_lpos == tail_lpos_old)
		return false;
Quoted 11 lines
kernel/printk/printk_ringbuffer.c new file +11 -0
+			if (next_lpos == tail_lpos)
+				return false;
+
+			/* Another task pushed the tail. Try again. */
+			tail_lpos = next_lpos;
+			continue;
+		}
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This

kernel/printk/printk_ringbuffer.c line 608

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		 * allows readers to identify if data has expired while
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */
+
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+
+	return true;
+}

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#12 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 69 lines · Petr Mladek
Quoted 69 lines
kernel/printk/printk_ringbuffer.c new file +67 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 494

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past.

We have [0]. (Search for "Ouch.")

Quoted 2 lines

Well, it would just prove that it really needs a comment why this check is necessary.

The comment says why it is necessary. The previous read of the block ID cannot be trusted if the the tail has been pushed beyond it.

Quoted 11 lines

IMHO, the following check of the descriptor state should be enough:

1. This function returns "false" when the descriptor is in desc_misc or desc_reusable state or when it does not point back to the data.

In this case, data_push_tail() does similar check. It loads data_ring->tail_lpos as well. It returns false when the tail did not move. Otherwise, it calls data_make_reusable() again and has the same effect as the continue here.

Quoted 8 lines

2. This function returns true only when the descriptor is in committed or reusable state and points back to the same data block. In this, case it really contains consistent data.

OK, it is possible that the block is already reused when the descriptor is in reusable state. But it is possible only when data_ring->tail_lpos moved. In this case, cmpxchg in data_push_tail() would fail and we would go back as well.

In your email from our previous discussion, you pointed out that two writers could race to allocate a block and the loser would start freeing the winner's data because it gets a valid block ID to a descriptor in the committed state that points back to the block lpos.

Quoted 3 lines · You

=> We should add a check into data_make_reusable() that
we are invalidating really the descriptor pointing to the given lpos and not a freshly reused one!

That is what this check is doing. If the tail has been pushed beyond the block, we cannot trust the block ID read because that area may have been recycled already.

Quoted 66 lines
Quoted 47 lines
kernel/printk/printk_ringbuffer.c new file +47 -0
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B

kernel/printk/printk_ringbuffer.c line 587

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */

I have been a bit confused whether next_lpos variable is used correctly everywhere. The primary purpose is to use a value provided by data_make_reusable() in the cmpxchg below.

But it is (mis)used here to temporary store the current tail_lpos value. Could we please use another variable here? IMHO, the following code would be more clear:

Quoted 5 lines
	tail_lpos_old = tail_lpos;
	tail_lpos = atomic_long_read(&data_ring->tail_lpos); /* LMM(data_push_tail:B) */

	if (tail_lpos == tail_lpos_old)
		return false;

You are correct. I am ashamed about this misuse. I will add the variable and rely on the compiler to appropriately merge/recycle stack variables.

John Ogness

[0] https://lkml.kernel.org/r/[email protected]

maintainer
#13 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 79 lines · John Ogness
Quoted 69 lines · Petr Mladek
Quoted 69 lines
kernel/printk/printk_ringbuffer.c new file +67 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 494

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past.

Quoted 1 line

We have [0]. (Search for "Ouch.")

I see. Thanks a lot for the pointer.

Quoted 5 lines
Quoted 2 lines

Well, it would just prove that it really needs a comment why this check is necessary.

The comment says why it is necessary. The previous read of the block ID cannot be trusted if the the tail has been pushed beyond it.

Not really. The comment describes what the check does. But it does not explain why it is needed. The reason might be described be something like:

* Make sure that the id read from tail_lpos is really
* pointing to this lpos. The block might have been
* reused in the meantime. Make sure to do not make
* the new owner reusable.

But wait! This situation should get caught by the two existing descriptor checks:

Quoted 9 lines
		case desc_committed:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			desc_make_reusable(desc_ring, id);
			break;
Quoted 8 lines
		case desc_reusable:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			break;

Here again the comments describe what the check does but not why. I would write something like:

/*
* The block might have already been
* reused. Make sure that the descriptor really
* points back to the checked lpos. It covers
* both situations. Random data might point to
* a valid descriptor just by chance. Or the block
* has been already reused by another descriptor. */

BTW: In theory, it might happen that the ringbuffer is reused many times in the meantime and (blk_lpos->begin == lpos_begin) again. But then lpos_begin would be valid lpos again and even the range check would not catch this as well.

So, I think that the lpos range check is still redundant. We might describe it as an extra paranoid check but I am not sure if it is worth it.

But I would remove it and keep the code "simple" and design "clear". Well, I do not resist on it.

Best Regards,
Petr

author maintainer
#14 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 88 lines · Petr Mladek
Quoted 78 lines
Quoted 69 lines
Quoted 69 lines
kernel/printk/printk_ringbuffer.c new file +67 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 494

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past.

Quoted 1 line

We have [0]. (Search for "Ouch.")

I see. Thanks a lot for the pointer.

Quoted 5 lines
Quoted 2 lines

Well, it would just prove that it really needs a comment why this check is necessary.

The comment says why it is necessary. The previous read of the block ID cannot be trusted if the the tail has been pushed beyond it.

Quoted 7 lines

Not really. The comment describes what the check does. But it does not explain why it is needed. The reason might be described be something like:

* Make sure that the id read from tail_lpos is really
* pointing to this lpos. The block might have been
* reused in the meantime. Make sure to do not make
* the new owner reusable.

That is _not_ what this check is doing. I recommend looking closely at the example you posted. This is not about whether or not a descriptor is pointing to this lpos. In your example you showed that ID, state, and lpos values could all look good, but it is for the _new_ record and we should _not_ invalidate that one.

We can detect the scenario you pointed out by verifying the tail has not moved beyond the data block that the ID was read from. The comment for this check says:

If @lpos_begin has fallen behind the tail lpos, the read block ID cannot be trusted.

This is exactly the why. It is only about whether we can trust that a non-garbage block ID was read. Or do you want me to add:

... because data read that is behind the tail lpos must be considered garbage.

Quoted 20 lines

But wait! This situation should get caught by the two existing descriptor checks:

Quoted 17 lines
		case desc_committed:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			desc_make_reusable(desc_ring, id);
			break;
		case desc_reusable:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			break;

No. Your example showed that it is not caught here.

Quoted 11 lines

Here again the comments describe what the check does but not why. I would write something like:

/*
* The block might have already been
* reused. Make sure that the descriptor really
* points back to the checked lpos. It covers
* both situations. Random data might point to
* a valid descriptor just by chance. Or the block
* has been already reused by another descriptor. */

OK. I will expand the comments to something similar to this.

Quoted 6 lines

So, I think that the lpos range check is still redundant. We might describe it as an extra paranoid check but I am not sure if it is worth it.

But I would remove it and keep the code "simple" and design "clear". Well, I do not resist on it.

If we remove it, we end up back at your bug report. ;-)

John Ogness

[0] https://lkml.kernel.org/r/[email protected]

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#15 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 82 lines · Petr Mladek
Quoted 68 lines
kernel/printk/printk_ringbuffer.c new file +68 -0
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}
+
+		d_state = desc_read(desc_ring, id,
+				    &desc); /* LMM(data_make_reusable:D) */
+

kernel/printk/printk_ringbuffer.c line 508

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		switch (d_state) {
+		case desc_miss:
+			return false;
+		case desc_reserved:
+			return false;
+		case desc_committed:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */

Here again the comments describe what the check does but not why. I would write something like:

Quoted 8 lines

/*
* The block might have already been
* reused. Make sure that the descriptor really
* points back to the checked lpos. It covers
* both situations. Random data might point to
* a valid descriptor just by chance. Or the block
* has been already reused by another descriptor. */

Originally this check was needed because the descriptor would be read even if there was a data race reading the ID from the data block. Validating the lpos value was a kind of protection against reading random data that by chance yielded an ID of a committed/reusable descriptor.

However, after you pointed out that this check was not enough, the code now re-checks the data tail to make sure that no data race happened. So actually it is not possible that a descriptor in the committed/reusable state will point anywhere else. We know the ID is not random garbage or recycled, so the state can be trusted.

I recommend to either remove this sanity check (for committed and reusable) or at least change it to:

			WARN_ON_ONCE(blk_lpos->begin != lpos_begin);

Or can you see any possibility of this case?

Quoted 9 lines
Quoted 9 lines
kernel/printk/printk_ringbuffer.c new file +9 -0
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			desc_make_reusable(desc_ring, id);
+			break;
+		case desc_reusable:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 525

Quoted 8 lines
kernel/printk/printk_ringbuffer.c new file +8 -0
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			break;
+		}
+
+		/* Advance @lpos_begin to the next data block. */
+		lpos_begin = blk_lpos->next;
+	}

John Ogness

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#16 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 103 lines · John Ogness
Quoted 82 lines
Quoted 68 lines
kernel/printk/printk_ringbuffer.c new file +68 -0
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}
+
+		d_state = desc_read(desc_ring, id,
+				    &desc); /* LMM(data_make_reusable:D) */
+

kernel/printk/printk_ringbuffer.c line 508

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		switch (d_state) {
+		case desc_miss:
+			return false;
+		case desc_reserved:
+			return false;
+		case desc_committed:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */

Here again the comments describe what the check does but not why. I would write something like:

Quoted 8 lines

/*
* The block might have already been
* reused. Make sure that the descriptor really
* points back to the checked lpos. It covers
* both situations. Random data might point to
* a valid descriptor just by chance. Or the block
* has been already reused by another descriptor. */

Originally this check was needed because the descriptor would be read even if there was a data race reading the ID from the data block. Validating the lpos value was a kind of protection against reading random data that by chance yielded an ID of a committed/reusable descriptor.

However, after you pointed out that this check was not enough, the code now re-checks the data tail to make sure that no data race happened. So actually it is not possible that a descriptor in the committed/reusable state will point anywhere else. We know the ID is not random garbage or recycled, so the state can be trusted.

Quoted 4 lines

I recommend to either remove this sanity check (for committed and reusable) or at least change it to:

			WARN_ON_ONCE(blk_lpos->begin != lpos_begin);

Sorry, I wasn't thinking things out correctly which this suggestion. We need the checks. The explanation is as follows...

With regard to the block ID read (data_make_reusable:A):

Failing the following tail check is a guarantee that we read garbage. Data behind the data tail must never be trusted. It is correct to try again with the new tail value.

Passing the following tail check could still be a garbage read. The descriptor owning that data block may be in the reserved state and has not yet written the new block ID. In that case we read whatever random data was there even though the tail check passes. And that random data could yield a valid descriptor ID, resulting in some state value that does not apply.

The "descriptor pointing back to data block" checks are playing the critical role of protecting against data_make_reusable:A reading garbage. And indeed, I can reproduce this situation fairly easily on ppc64le+kvm tests.

So please disregard this suggestion. And yes, the comments for these checks need to be expanded to make clear just how critical they are and explain how the situation can occur.

John Ogness

Quoted 17 lines
Quoted 17 lines
Quoted 17 lines
kernel/printk/printk_ringbuffer.c new file +17 -0
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			desc_make_reusable(desc_ring, id);
+			break;
+		case desc_reusable:
+			/*
+			 * This data block is invalid if the descriptor
+			 * does not point back to it.
+			 */
+			if (blk_lpos->begin != lpos_begin)
+				return false;
+			break;
+		}
+
+		/* Advance @lpos_begin to the next data block. */
+		lpos_begin = blk_lpos->next;
+	}
maintainer
#17 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 97 lines · John Ogness
Quoted 88 lines · Petr Mladek
Quoted 78 lines
Quoted 69 lines
Quoted 69 lines
kernel/printk/printk_ringbuffer.c new file +67 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 494

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past.

Quoted 1 line

We have [0]. (Search for "Ouch.")

I see. Thanks a lot for the pointer.

Quoted 5 lines
Quoted 2 lines

Well, it would just prove that it really needs a comment why this check is necessary.

The comment says why it is necessary. The previous read of the block ID cannot be trusted if the the tail has been pushed beyond it.

Quoted 7 lines

Not really. The comment describes what the check does. But it does not explain why it is needed. The reason might be described be something like:

* Make sure that the id read from tail_lpos is really
* pointing to this lpos. The block might have been
* reused in the meantime. Make sure to do not make
* the new owner reusable.

Quoted 5 lines

That is _not_ what this check is doing. I recommend looking closely at the example you posted. This is not about whether or not a descriptor is pointing to this lpos. In your example you showed that ID, state, and lpos values could all look good, but it is for the _new_ record and we should _not_ invalidate that one.

OK, let's make sure that we are talking about the same example. I was talking about this one from
https://lore.kernel.org/lkml/[email protected]/

% [*] Another problem would be when data_make_reusable() see the new
% data already in the committed state. It would make fresh new
% data reusable.
%
% I mean the following:
%
% CPU0 CPU1
%
% data_alloc()
% begin_lpos = dr->head_lpos
% data_push_tail()
% lpos = dr->tail_lpos
% prb_reserve()
% # reserve the location of current
% # dr->tail_lpos
% prb_commit()
%

%     id = blk->id
%     # read id for the freshly written data on CPU1
%     # and happily make them reusable
%     data_make_reusable()

Sigh, sigh, sigh, there is a hugely misleading comment in the example:

% # reserve the location of current
% # dr->tail_lpos

It is true that it reserves part of this location. But it will use data_ring->head_lpos for the related desc->text_blk_lpos.begin !!!

See below:

Quoted 34 lines

We can detect the scenario you pointed out by verifying the tail has not moved beyond the data block that the ID was read from. The comment for this check says:

If @lpos_begin has fallen behind the tail lpos, the read block ID cannot be trusted.

This is exactly the why. It is only about whether we can trust that a non-garbage block ID was read. Or do you want me to add:

... because data read that is behind the tail lpos must be considered garbage.

Quoted 20 lines

But wait! This situation should get caught by the two existing descriptor checks:

Quoted 17 lines
		case desc_committed:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			desc_make_reusable(desc_ring, id);
			break;
		case desc_reusable:
			/*
			 * This data block is invalid if the descriptor
			 * does not point back to it.
			 */
			if (blk_lpos->begin != lpos_begin)
				return false;
			break;
Quoted 1 line

No. Your example showed that it is not caught here.

I am afraid that my example was wrong:

If blk->id comes from the new descriptor written by CPU1 then blk_lpos->begin is based on the old data_ring->head_lpos. Then it is different from lpos_begin.

Let's put it another way. The state of the descriptor defines validity of the data. Descriptor in committed state _must not_ point to invalid data block!!!

If a descriptor in committed state point to lpos that was in invalid range before reading the descriptor then we have a huge hole in the design.

This is why I believe that the check of the descriptor must be enough.

Best Regards,
Petr

PS: I am sorry if I create too much confusion. It is easy to get lost :-(

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#18 lore raw

Re: redundant check in make_data_reusable(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 128 lines · Petr Mladek
Quoted 96 lines
Quoted 88 lines
Quoted 78 lines
Quoted 69 lines
Quoted 69 lines
kernel/printk/printk_ringbuffer.c new file +67 -0
+/*
+ * Given a data ring (text or dict), put the associated descriptor of each
+ * data block from @lpos_begin until @lpos_end into the reusable state.
+ *
+ * If there is any problem making the associated descriptor reusable, either
+ * the descriptor has not yet been committed or another writer task has
+ * already pushed the tail lpos past the problematic data block. Regardless,
+ * on error the caller can re-load the tail lpos to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+			       struct prb_data_ring *data_ring,
+			       unsigned long lpos_begin,
+			       unsigned long lpos_end,
+			       unsigned long *lpos_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	struct prb_data_blk_lpos *blk_lpos;
+	struct prb_data_block *blk;
+	unsigned long tail_lpos;
+	enum desc_state d_state;
+	struct prb_desc desc;
+	unsigned long id;
+
+	/*
+	 * Using the provided @data_ring, point @blk_lpos to the correct
+	 * blk_lpos within the local copy of the descriptor.
+	 */
+	if (data_ring == &rb->text_data_ring)
+		blk_lpos = &desc.text_blk_lpos;
+	else
+		blk_lpos = &desc.dict_blk_lpos;
+
+	/* Loop until @lpos_begin has advanced to or beyond @lpos_end. */
+	while ((lpos_end - lpos_begin) - 1 < DATA_SIZE(data_ring)) {
+		blk = to_block(data_ring, lpos_begin);
+		id = READ_ONCE(blk->id); /* LMM(data_make_reusable:A) */
+
+		/*
+		 * Guarantee the block ID is loaded before checking the tail
+		 * lpos. The loaded block ID can only be considered valid if
+		 * the tail lpos has not overtaken @lpos_begin. This pairs
+		 * with data_alloc:A.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If data_make_reusable:A reads from data_alloc:B, then
+		 * data_make_reusable:C reads from data_push_tail:D.
+		 *
+		 * Relies on:
+		 *
+		 * MB from data_push_tail:D to data_alloc:B
+		 *    matching
+		 * RMB from data_make_reusable:A to data_make_reusable:C
+		 *
+		 * Note: data_push_tail:D and data_alloc:B can be different
+		 *       CPUs. However, the data_alloc:B CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       data_push_tail:D.
+		 */
+		smp_rmb(); /* LMM(data_make_reusable:B) */
+
+		tail_lpos = atomic_long_read(&data_ring->tail_lpos
+					); /* LMM(data_make_reusable:C) */
+
+		/*
+		 * If @lpos_begin has fallen behind the tail lpos, the read
+		 * block ID cannot be trusted. Fast forward @lpos_begin to the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 494

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+		 * tail lpos and try again.
+		 */
+		if (lpos_begin - tail_lpos >= DATA_SIZE(data_ring)) {
+			lpos_begin = tail_lpos;
+			continue;
+		}

I am sorry if we have had this discussion already in past.

Quoted 1 line

We have [0]. (Search for "Ouch.")

I see. Thanks a lot for the pointer.

Quoted 5 lines
Quoted 2 lines

Well, it would just prove that it really needs a comment why this check is necessary.

The comment says why it is necessary. The previous read of the block ID cannot be trusted if the the tail has been pushed beyond it.

Quoted 7 lines

Not really. The comment describes what the check does. But it does not explain why it is needed. The reason might be described be something like:

* Make sure that the id read from tail_lpos is really
* pointing to this lpos. The block might have been
* reused in the meantime. Make sure to do not make
* the new owner reusable.

Quoted 5 lines

That is _not_ what this check is doing. I recommend looking closely at the example you posted. This is not about whether or not a descriptor is pointing to this lpos. In your example you showed that ID, state, and lpos values could all look good, but it is for the _new_ record and we should _not_ invalidate that one.

OK, let's make sure that we are talking about the same example. I was talking about this one from
https://lore.kernel.org/lkml/[email protected]/

% [*] Another problem would be when data_make_reusable() see the new
% data already in the committed state. It would make fresh new
% data reusable.
%
% I mean the following:
%
% CPU0 CPU1
%
% data_alloc()
% begin_lpos = dr->head_lpos
% data_push_tail()
% lpos = dr->tail_lpos
% prb_reserve()
% # reserve the location of current
% # dr->tail_lpos
% prb_commit()
%

%     id = blk->id
%     # read id for the freshly written data on CPU1
%     # and happily make them reusable
%     data_make_reusable()
Quoted 7 lines

Sigh, sigh, sigh, there is a hugely misleading comment in the example:

% # reserve the location of current
% # dr->tail_lpos

It is true that it reserves part of this location. But it will use data_ring->head_lpos for the related desc->text_blk_lpos.begin !!!

Aaargh! You are right!

Quoted 8 lines

If blk->id comes from the new descriptor written by CPU1 then blk_lpos->begin is based on the old data_ring->head_lpos. Then it is different from lpos_begin.

Let's put it another way. The state of the descriptor defines validity of the data. Descriptor in committed state _must not_ point to invalid data block!!!

Quoted 5 lines

If a descriptor in committed state point to lpos that was in invalid range before reading the descriptor then we have a huge hole in the design.

This is why I believe that the check of the descriptor must be enough.

You are right. The smp_rmb (data_make_reusable:B) and its following tail check are not needed. Since data_make_reusable:A can read garbage even if we pass the tail check, we might as well always allow garbage and rely on the descriptor/lpos checks to catch it. (Actually, that was the design!)

However, the pairing smp_mb (data_alloc:A) is still needed, but it will then pair with data_push_tail:A. If data_make_reusable() reads garbage (maybe newly written garbage), it is important that a new data tail is visible.

The comment for data_alloc:A would change to something like:

/*
* Guarantee any updated tail lpos is stored before modifying
* the newly allocated data area. Another context may be in
* data_make_reusable() and is reading a block ID from this
* area. data_make_reusable() can handle reading a garbage block
* ID value, but then it must be able to load a new tail lpos.
* This pairs with data_push_tail:A.
*/
smp_mb(); /* LMM(data_alloc:A) */

John Ogness

maintainer
#19 lore raw

Full barrier in data_push_tail(): was [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 75 lines · John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

kernel/printk/printk_ringbuffer.c new file +62 -0
new file mode 100644
index 000000000000..e0a66468d4f3
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */
+			if (next_lpos == tail_lpos)
+				return false;
+
+			/* Another task pushed the tail. Try again. */
+			tail_lpos = next_lpos;

kernel/printk/printk_ringbuffer.c line 602

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			continue;
+		}
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This
+		 * allows readers to identify if data has expired while
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */

The comment does not explain why we need a full barrier here. It talks about writing descriptor states. It suggests that write barrier should be enough.

I guess that this is related to the discussion that we had last time, and the litmus test mentioned in
see https://lore.kernel.org/r/[email protected]

I would add something like:

* Full barrier is necessary because the descriptors
* might have been made reusable also by other CPUs.

For people like me, it would be great to add also link to a more detailed explanation, for example, the litmus tests, or something even more human readable ;-) I think that it is a "rather" common problem. I wonder whether it is already documented somewhere.

kernel/printk/printk_ringbuffer.c line 609

Quoted 6 lines
kernel/printk/printk_ringbuffer.c new file +6 -0
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+
+	return true;
+}
+

Best Regards,
Petr

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#20 lore raw

Re: Full barrier in data_push_tail(): was [PATCH v2 2/3] printk: add lockless buffer

Quoted 18 lines · Petr Mladek
Quoted 5 lines
kernel/printk/printk_ringbuffer.c new file +3 -0
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,
+			   unsigned long lpos)

kernel/printk/printk_ringbuffer.c line 602

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +9 -0
+{
...
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This
+		 * allows readers to identify if data has expired while
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */

The comment does not explain why we need a full barrier here.

Quoted 4 lines

I would add something like:

* Full barrier is necessary because the descriptors
* might have been made reusable also by other CPUs.

Agreed. Somehow I missed that explanation for this comment.

Quoted 4 lines

For people like me, it would be great to add also link to a more detailed explanation, for example, the litmus tests, or something even more human readable ;-) I think that it is a "rather" common problem. I wonder whether it is already documented somewhere.

I believe that memory barriers need to be formally documented. Perhaps in such a way that litmus tests can be easily generated. Tools could greatly assist with this. It is my hope that my memory barrier documentation can spark some ideas about how we could do this. (Doing all this manually really sucks!)

John Ogness

maintainer
#21 lore raw

Barrier before pushing desc_ring tail: was [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 74 lines · John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

kernel/printk/printk_ringbuffer.c new file +64 -0
+/*
+ * Advance the desc ring tail. This function advances the tail by one
+ * descriptor, thus invalidating the oldest descriptor. Before advancing
+ * the tail, the tail descriptor is made reusable and all data blocks up to
+ * and including the descriptor's data block are invalidated (i.e. the data
+ * ring tail is pushed past the data block of the descriptor being made
+ * reusable).
+ */
+static bool desc_push_tail(struct printk_ringbuffer *rb,
+			   unsigned long tail_id)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	enum desc_state d_state;
+	struct prb_desc desc;
+
+	d_state = desc_read(desc_ring, tail_id, &desc);
+
+	switch (d_state) {
+	case desc_miss:
+		/*
+		 * If the ID is exactly 1 wrap behind the expected, it is
+		 * in the process of being reserved by another writer and
+		 * must be considered reserved.
+		 */
+		if (DESC_ID(atomic_long_read(&desc.state_var)) ==
+		    DESC_ID_PREV_WRAP(desc_ring, tail_id)) {
+			return false;
+		}
+
+		/*
+		 * The ID has changed. Another writer must have pushed the
+		 * tail and recycled the descriptor already. Success is
+		 * returned because the caller is only interested in the
+		 * specified tail being pushed, which it was.
+		 */
+		return true;
+	case desc_reserved:
+		return false;
+	case desc_committed:
+		desc_make_reusable(desc_ring, tail_id);
+		break;
+	case desc_reusable:
+		break;
+	}
+
+	/*
+	 * Data blocks must be invalidated before their associated
+	 * descriptor can be made available for recycling. Invalidating
+	 * them later is not possible because there is no way to trust
+	 * data blocks once their associated descriptor is gone.
+	 */
+
+	if (!data_push_tail(rb, &rb->text_data_ring, desc.text_blk_lpos.next))
+		return false;
+	if (!data_push_tail(rb, &rb->dict_data_ring, desc.dict_blk_lpos.next))
+		return false;
+
+	/*
+	 * Check the next descriptor after @tail_id before pushing the tail
+	 * to it because the tail must always be in a committed or reusable
+	 * state. The implementation of prb_first_seq() relies on this.
+	 *
+	 * A successful read implies that the next descriptor is less than or
+	 * equal to @head_id so there is no risk of pushing the tail past the

kernel/printk/printk_ringbuffer.c line 683

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+	 * head.
+	 */
+	d_state = desc_read(desc_ring, DESC_ID(tail_id + 1),
+			    &desc); /* LMM(desc_push_tail:A) */
+	if (d_state == desc_committed || d_state == desc_reusable) {
+		/*
+		 * Any CPU that loads the new tail ID, must see that the
+		 * descriptor at @tail_id is in the reusable state. See the
+		 * read memory barrier part of desc_reserve:D for details.
+		 */

I was quite confused by the above comment. Does it mean that we need a barrier here? Or does it explain why the cmpxchg has its own LMM marker?

I think that we actually need a full barrier here to make sure that all CPUs see the changes made by data_push_tail() before we allow to rewrite the descriptor. The changes in data_push_tail() might be done on different CPUs.

It is similar like the full barrier in data_push_tail() before changing data_ring->tail_lpos.

Best Regards,
Petr

Quoted 162 lines
kernel/printk/printk_ringbuffer.c new file +162 -0
+		atomic_long_cmpxchg_relaxed(&desc_ring->tail_id, tail_id,
+			DESC_ID(tail_id + 1)); /* LMM(desc_push_tail:B) */
+	} else {
+		/*
+		 * Guarantee the last state load from desc_read() is before
+		 * reloading @tail_id in order to see a new tail ID in the
+		 * case that the descriptor has been recycled. This pairs
+		 * with desc_reserve:D.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If desc_push_tail:A reads from desc_reserve:G, then
+		 * desc_push_tail:D reads from desc_push_tail:B.
+		 *
+		 * Relies on:
+		 *
+		 * MB from desc_push_tail:B to desc_reserve:G
+		 *    matching
+		 * RMB from desc_push_tail:A to desc_push_tail:D
+		 *
+		 * Note: desc_push_tail:B and desc_reserve:G can be different
+		 *       CPUs. However, the desc_reserve:G CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       desc_push_tail:B.
+		 */
+		smp_rmb(); /* LMM(desc_push_tail:C) */
+
+		/*
+		 * Re-check the tail ID. The descriptor following @tail_id is
+		 * not in an allowed tail state. But if the tail has since
+		 * been moved by another task, then it does not matter.
+		 */
+		if (atomic_long_read(&desc_ring->tail_id) ==
+					tail_id) { /* LMM(desc_push_tail:D) */
+			return false;
+		}
+	}
+
+	return true;
+}
+
+/* Reserve a new descriptor, invalidating the oldest if necessary. */
+static bool desc_reserve(struct printk_ringbuffer *rb, unsigned long *id_out)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	unsigned long prev_state_val;
+	unsigned long id_prev_wrap;
+	struct prb_desc *desc;
+	unsigned long head_id;
+	unsigned long id;
+
+	head_id = atomic_long_read(&desc_ring->head_id
+						); /* LMM(desc_reserve:A) */
+
+	do {
+		desc = to_desc(desc_ring, head_id);
+
+		id = DESC_ID(head_id + 1);
+		id_prev_wrap = DESC_ID_PREV_WRAP(desc_ring, id);
+
+		/*
+		 * Guarantee the head ID is read before reading the tail ID.
+		 * Since the tail ID is updated before the head ID, this
+		 * guarantees that @id_prev_wrap is never ahead of the tail
+		 * ID. This pairs with desc_reserve:D.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If desc_reserve:A reads from desc_reserve:E, then
+		 * desc_reserve:C reads from desc_push_tail:B.
+		 *
+		 * Relies on:
+		 *
+		 * MB from desc_push_tail:B to desc_reserve:E
+		 *    matching
+		 * RMB from desc_reserve:A to desc_reserve:C
+		 *
+		 * Note: desc_push_tail:B and desc_reserve:E can be different
+		 *       CPUs. However, the desc_reserve:E CPU (which performs
+		 *       the full memory barrier) must have previously seen
+		 *       desc_push_tail:B.
+		 */
+		smp_rmb(); /* LMM(desc_reserve:B) */
+
+		if (id_prev_wrap == atomic_long_read(&desc_ring->tail_id
+						)) { /* LMM(desc_reserve:C) */
+			/*
+			 * Make space for the new descriptor by
+			 * advancing the tail.
+			 */
+			if (!desc_push_tail(rb, id_prev_wrap))
+				return false;
+		}
+
+		/*
+		 * Guarantee the tail ID is read before validating the
+		 * recycled descriptor state. A read memory barrier is
+		 * sufficient for this. This pairs with data_push_tail:C.
+		 *
+		 * Memory barrier involvement:
+		 *
+		 * If desc_reserve:C reads from desc_push_tail:B, then
+		 * desc_reserve:F reads from desc_make_reusable:A.
+		 *
+		 * Relies on:
+		 *
+		 * MB from desc_make_reusable:A to desc_push_tail:B
+		 *    matching
+		 * RMB from desc_reserve:C to desc_reserve:F
+		 *
+		 * Note: desc_make_reusable:A, desc_push_tail:B, and
+		 *       data_push_tail:C can all be different CPUs. However,
+		 *       the desc_push_tail:B CPU must have previously seen
+		 *       data_push_tail:D and the data_push_tail:D CPU (which
+		 *       performs the full memory barrier) must have
+		 *       previously seen desc_make_reusable:A.
+		 *
+		 * Guarantee any data ring tail changes are stored before
+		 * recycling the descriptor. Data ring tail changes can happen
+		 * via desc_push_tail()->data_push_tail(). A full memory
+		 * barrier is needed since another task may have pushed the
+		 * data ring tails. This pairs with data_push_tail:A.
+		 *
+		 * Guarantee a new tail ID is stored before recycling the
+		 * descriptor. A full memory barrier is needed since another
+		 * task may have pushed the tail ID. This pairs with
+		 * desc_push_tail:C and prb_first_seq:C.
+		 *
+		 * Guarantee the tail ID is stored before storing the head ID.
+		 * This pairs with desc_reserve:B.
+		 */
+		smp_mb(); /* LMM(desc_reserve:D) */
+
+	} while (!atomic_long_try_cmpxchg_relaxed(&desc_ring->head_id,
+				&head_id, id)); /* LMM(desc_reserve:E) */
+
+	desc = to_desc(desc_ring, id);
+
+	/*
+	 * If the descriptor has been recycled, verify the old state val.
+	 * See "ABA Issues" about why this verification is performed.
+	 */
+	prev_state_val = atomic_long_read(&desc->state_var
+						); /* LMM(desc_reserve:F) */
+	if (prev_state_val && prev_state_val != (id_prev_wrap |
+						 DESC_COMMITTED_MASK |
+						 DESC_REUSE_MASK)) {
+		WARN_ON_ONCE(1);
+		return false;
+	}
+
+	/*
+	 * Assign the descriptor a new ID and set its state to reserved.
+	 * See "ABA Issues" about why cmpxchg() instead of set() is used.
+	 */
+	if (!atomic_long_try_cmpxchg_relaxed(&desc->state_var,
+			&prev_state_val, id | 0)) { /* LMM(desc_reserve:G) */
+		WARN_ON_ONCE(1);
+		return false;
+	}
+
+	/*

kernel/printk/printk_ringbuffer.c line 855

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+	 * Guarantee the new descriptor ID and state is stored before making
+	 * any other changes. This pairs with desc_read:D.
+	 */
+	smp_wmb(); /* LMM(desc_reserve:H) */
+
+	/* Now data in @desc can be modified: LMM(desc_reserve:I) */
+
+	*id_out = id;
+	return true;
+}

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#22 lore raw

Re: Barrier before pushing desc_ring tail: was [PATCH v2 2/3] printk: add lockless buffer

Quoted 74 lines · Petr Mladek
Quoted 74 lines
kernel/printk/printk_ringbuffer.c new file +72 -0
+/*
+ * Advance the desc ring tail. This function advances the tail by one
+ * descriptor, thus invalidating the oldest descriptor. Before advancing
+ * the tail, the tail descriptor is made reusable and all data blocks up to
+ * and including the descriptor's data block are invalidated (i.e. the data
+ * ring tail is pushed past the data block of the descriptor being made
+ * reusable).
+ */
+static bool desc_push_tail(struct printk_ringbuffer *rb,
+			   unsigned long tail_id)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	enum desc_state d_state;
+	struct prb_desc desc;
+
+	d_state = desc_read(desc_ring, tail_id, &desc);
+
+	switch (d_state) {
+	case desc_miss:
+		/*
+		 * If the ID is exactly 1 wrap behind the expected, it is
+		 * in the process of being reserved by another writer and
+		 * must be considered reserved.
+		 */
+		if (DESC_ID(atomic_long_read(&desc.state_var)) ==
+		    DESC_ID_PREV_WRAP(desc_ring, tail_id)) {
+			return false;
+		}
+
+		/*
+		 * The ID has changed. Another writer must have pushed the
+		 * tail and recycled the descriptor already. Success is
+		 * returned because the caller is only interested in the
+		 * specified tail being pushed, which it was.
+		 */
+		return true;
+	case desc_reserved:
+		return false;
+	case desc_committed:
+		desc_make_reusable(desc_ring, tail_id);
+		break;
+	case desc_reusable:
+		break;
+	}
+
+	/*
+	 * Data blocks must be invalidated before their associated
+	 * descriptor can be made available for recycling. Invalidating
+	 * them later is not possible because there is no way to trust
+	 * data blocks once their associated descriptor is gone.
+	 */
+
+	if (!data_push_tail(rb, &rb->text_data_ring, desc.text_blk_lpos.next))
+		return false;
+	if (!data_push_tail(rb, &rb->dict_data_ring, desc.dict_blk_lpos.next))
+		return false;
+
+	/*
+	 * Check the next descriptor after @tail_id before pushing the tail
+	 * to it because the tail must always be in a committed or reusable
+	 * state. The implementation of prb_first_seq() relies on this.
+	 *
+	 * A successful read implies that the next descriptor is less than or
+	 * equal to @head_id so there is no risk of pushing the tail past the
+	 * head.
+	 */
+	d_state = desc_read(desc_ring, DESC_ID(tail_id + 1),
+			    &desc); /* LMM(desc_push_tail:A) */
+	if (d_state == desc_committed || d_state == desc_reusable) {
+		/*
+		 * Any CPU that loads the new tail ID, must see that the
+		 * descriptor at @tail_id is in the reusable state. See the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 685

Quoted 4 lines
kernel/printk/printk_ringbuffer.c new file +4 -0
+		 * read memory barrier part of desc_reserve:D for details.
+		 */
+		atomic_long_cmpxchg_relaxed(&desc_ring->tail_id, tail_id,
+			DESC_ID(tail_id + 1)); /* LMM(desc_push_tail:B) */

I was quite confused by the above comment. Does it mean that we need a barrier here? Or does it explain why the cmpxchg has its own LMM marker?

This LMM marker is referenced quite often, but since it is a relaxed cmpxchg(), its significance is not immediately clear. I was hoping to add some hints as to why it is significant. The comment that it is referring to is:

/*
* Guarantee the tail ID is read before validating the
* recycled descriptor state. A read memory barrier is
* sufficient for this. This pairs with data_push_tail:C. *
* Memory barrier involvement:
*
* If desc_reserve:C reads from desc_push_tail:B, then
* desc_reserve:F reads from desc_make_reusable:A. *
* Relies on:
*
* MB from desc_make_reusable:A to desc_push_tail:B
* matching
* RMB from desc_reserve:C to desc_reserve:F
*
* Note: desc_make_reusable:A, desc_push_tail:B, and
* data_push_tail:C can all be different CPUs. However,
* the desc_push_tail:B CPU must have previously seen
* data_push_tail:D and the data_push_tail:D CPU (which
* performs the full memory barrier) must have
* previously seen desc_make_reusable:A.
*/

English translation:

In order to push the data tail, a CPU must first see that the associated descriptor is in the reusable state. Since a full memory barrier is performed after that sighting and before doing the data tail push, _any_ CPU that sees the pushed data tail will be able to see that the associated descriptor is in the reusable state.

In order to push the descriptor tail, a CPU must first see that the associated data tail has been pushed. Therefore, that CPU would also see that the associated descriptor is in the reusable state.

Quoted 4 lines

I think that we actually need a full barrier here to make sure that all CPUs see the changes made by data_push_tail() before we allow to rewrite the descriptor. The changes in data_push_tail() might be done on different CPUs.

There needs to be a reason why the ordering of data tail pushing and descriptor tail pushing is important.

Quoted 2 lines

It is similar like the full barrier in data_push_tail() before changing data_ring->tail_lpos.

How so? That memory barrier exists to make sure the reusable descriptor state is stored before pushing the data tail. This is important for readers (which start from the data tail) so they can notice if the descriptor has since been invalidated (reusable state).

But where is it important that the data tail change is seen before the descriptor tail change? How are the data tail and descriptor tail significantly related to each other?

John Ogness

maintainer
#23 lore raw

Re: Barrier before pushing desc_ring tail: was [PATCH v2 2/3] printk: add lockless buffer

Quoted 121 lines · John Ogness
Quoted 74 lines · Petr Mladek
Quoted 74 lines
kernel/printk/printk_ringbuffer.c new file +72 -0
+/*
+ * Advance the desc ring tail. This function advances the tail by one
+ * descriptor, thus invalidating the oldest descriptor. Before advancing
+ * the tail, the tail descriptor is made reusable and all data blocks up to
+ * and including the descriptor's data block are invalidated (i.e. the data
+ * ring tail is pushed past the data block of the descriptor being made
+ * reusable).
+ */
+static bool desc_push_tail(struct printk_ringbuffer *rb,
+			   unsigned long tail_id)
+{
+	struct prb_desc_ring *desc_ring = &rb->desc_ring;
+	enum desc_state d_state;
+	struct prb_desc desc;
+
+	d_state = desc_read(desc_ring, tail_id, &desc);
+
+	switch (d_state) {
+	case desc_miss:
+		/*
+		 * If the ID is exactly 1 wrap behind the expected, it is
+		 * in the process of being reserved by another writer and
+		 * must be considered reserved.
+		 */
+		if (DESC_ID(atomic_long_read(&desc.state_var)) ==
+		    DESC_ID_PREV_WRAP(desc_ring, tail_id)) {
+			return false;
+		}
+
+		/*
+		 * The ID has changed. Another writer must have pushed the
+		 * tail and recycled the descriptor already. Success is
+		 * returned because the caller is only interested in the
+		 * specified tail being pushed, which it was.
+		 */
+		return true;
+	case desc_reserved:
+		return false;
+	case desc_committed:
+		desc_make_reusable(desc_ring, tail_id);
+		break;
+	case desc_reusable:
+		break;
+	}
+
+	/*
+	 * Data blocks must be invalidated before their associated
+	 * descriptor can be made available for recycling. Invalidating
+	 * them later is not possible because there is no way to trust
+	 * data blocks once their associated descriptor is gone.
+	 */
+
+	if (!data_push_tail(rb, &rb->text_data_ring, desc.text_blk_lpos.next))
+		return false;
+	if (!data_push_tail(rb, &rb->dict_data_ring, desc.dict_blk_lpos.next))
+		return false;
+
+	/*
+	 * Check the next descriptor after @tail_id before pushing the tail
+	 * to it because the tail must always be in a committed or reusable
+	 * state. The implementation of prb_first_seq() relies on this.
+	 *
+	 * A successful read implies that the next descriptor is less than or
+	 * equal to @head_id so there is no risk of pushing the tail past the
+	 * head.
+	 */
+	d_state = desc_read(desc_ring, DESC_ID(tail_id + 1),
+			    &desc); /* LMM(desc_push_tail:A) */
+	if (d_state == desc_committed || d_state == desc_reusable) {
+		/*
+		 * Any CPU that loads the new tail ID, must see that the
+		 * descriptor at @tail_id is in the reusable state. See the
Quoted 8 lines

kernel/printk/printk_ringbuffer.c line 685

Quoted 4 lines
kernel/printk/printk_ringbuffer.c new file +4 -0
+		 * read memory barrier part of desc_reserve:D for details.
+		 */
+		atomic_long_cmpxchg_relaxed(&desc_ring->tail_id, tail_id,
+			DESC_ID(tail_id + 1)); /* LMM(desc_push_tail:B) */

I was quite confused by the above comment. Does it mean that we need a barrier here? Or does it explain why the cmpxchg has its own LMM marker?

This LMM marker is referenced quite often, but since it is a relaxed cmpxchg(), its significance is not immediately clear. I was hoping to add some hints as to why it is significant. The comment that it is referring to is:

/*
* Guarantee the tail ID is read before validating the
* recycled descriptor state. A read memory barrier is
* sufficient for this. This pairs with data_push_tail:C. *
* Memory barrier involvement:
*
* If desc_reserve:C reads from desc_push_tail:B, then
* desc_reserve:F reads from desc_make_reusable:A. *
* Relies on:
*
* MB from desc_make_reusable:A to desc_push_tail:B
* matching
* RMB from desc_reserve:C to desc_reserve:F
*
* Note: desc_make_reusable:A, desc_push_tail:B, and
* data_push_tail:C can all be different CPUs. However,
* the desc_push_tail:B CPU must have previously seen
* data_push_tail:D and the data_push_tail:D CPU (which
* performs the full memory barrier) must have
* previously seen desc_make_reusable:A.
*/

English translation:

In order to push the data tail, a CPU must first see that the associated descriptor is in the reusable state. Since a full memory barrier is performed after that sighting and before doing the data tail push, _any_ CPU that sees the pushed data tail will be able to see that the associated descriptor is in the reusable state.

Quoted 3 lines

In order to push the descriptor tail, a CPU must first see that the associated data tail has been pushed. Therefore, that CPU would also see that the associated descriptor is in the reusable state.

Thanks a lot for this detailed description. It helped a lot.

Let me try another description from slightly different angle:

All this relies on the fact the the full barrier is called in data_push_tail() and data_push_tail() is called right above. But there are two situations where the barrier is not called. It is when:

1. desc.text_blk_lpos.next already is behind data_ring->tail_lpos.

This is safe.

It might happen when there was a race in the past. CPU1 reserved a descriptor before CPU2 and CPU2 was able to allocate data block before CPU1.

As a result, both descriptors and both data blocks were moved into reusable state when the earlier descriptor was reused. It is because it pointed to newer data block and the older data block must have been invalidated together with the newer descriptor.

Now, the full barrier was called before tail_lpos was moved. Both descriptors must have been in the reusable state already.

2. desc.text_blk_lpos == INVALID_LPOS.

It seems that this is not synchronized and other CPUs might see the old state.

It happens for data blocks that do not have any data. So it probably does not cause real problems but ...

Quoted 5 lines
Quoted 4 lines

I think that we actually need a full barrier here to make sure that all CPUs see the changes made by data_push_tail() before we allow to rewrite the descriptor. The changes in data_push_tail() might be done on different CPUs.

Quoted 8 lines

How so? That memory barrier exists to make sure the reusable descriptor state is stored before pushing the data tail. This is important for readers (which start from the data tail) so they can notice if the descriptor has since been invalidated (reusable state).

But where is it important that the data tail change is seen before the descriptor tail change? How are the data tail and descriptor tail significantly related to each other?

I have to admit that I did not think about it deeply enough. It was more about feeling and seeing similar pattern.

You have a point. The state value of the descriptor is the central point. It is used to synchronize operations with both desc_ring and data_ring.

The state is modified only once. So one (full) memory barrier should be enough to synchronize all CPUs.

The state has to be modified before the data block could be reused. Therefore the full barrier has to be already in the data_ring code.

The question is what to do with the empty data case. I see three possibilities:

1. Ignore the case with empty block because it (probably) does not cause real problems.

2. Call the full barrier in data_push_tail() even when the data block is empty.

3. Call the full barrier also in desc_push_tail() as I suggested.

My opinion:

I prefer 3rd solution. The barrier would be superfluous in the most common situation. But it would create more error-proof code. We could always optimize it when it causes problems.

Anyway, I would feel very uneasy about the the 1st solution. And the 2nd solution is weird. It would be hard to explain.

Best Regards,
Petr

PS: I start feeling more confident about the code. The more barriers the less possible races ;-)

author maintainer
#24 lore raw

Re: Barrier before pushing desc_ring tail: was [PATCH v2 2/3] printk: add lockless buffer

Quoted 8 lines · Petr Mladek

All this relies on the fact the the full barrier is called in data_push_tail() and data_push_tail() is called right above. But there are two situations where the barrier is not called. It is when:

1. desc.text_blk_lpos.next already is behind data_ring->tail_lpos.

This is safe.

Yes, and I have since expanded the comment above the data_push_tail() while loop to mention that:

/*
* Loop until the tail lpos is at or beyond @lpos. This condition
* may already be satisfied, resulting in no full memory barrier
* from data_push_tail:C being performed. However, since this CPU
* sees the new tail lpos, any descriptor states that transitioned to
* the reusable state must already be visible.
*/

Quoted 4 lines

2. desc.text_blk_lpos == INVALID_LPOS.

It seems that this is not synchronized and other CPUs might see the old state.

Great catch! This could trigger the WARN_ON at desc_reserve:F and lead to prb_reserve() unnecessarily failing.

Quoted 5 lines

The question is what to do with the empty data case. I see three possibilities:

1. Ignore the case with empty block because it (probably) does not cause real problems.

It could cause dropped messages.

Quoted 2 lines

2. Call the full barrier in data_push_tail() even when the data block is empty.

This is the common case, since most records will not have dictionary data.

Quoted 5 lines

3. Call the full barrier also in desc_push_tail() as I suggested.

My opinion:

I prefer 3rd solution.

Agreed. For my next version I am folding all smp_mb() and smp_wmb() calls into their neighboring cmpxchg_relaxed(). This would apply here as well, changing desc_push_tail:B to a full cmpxchg().

We still need the full memory barrier at data_push_tail:C. Readers rely on it to be able to verify if their copied data is still valid:

CPU0 (writer0) CPU1 (writer1) CPU2 (reader)

                                           desc_read->committed

desc_make_reusable
smp_mb
data_push_tail
read new data tail data_push_head
smp_mb
write new data
read garbage new data desc_read->reusable

John Ogness

maintainer
#25 lore raw

data_ring head_lpos and tail_lpos synchronization: was [PATCH v2 2/3] printk: add lockless buffer

In reply to John Ogness
Quoted 17 lines · John Ogness

Introduce a multi-reader multi-writer lockless ringbuffer for storing the kernel log messages. Readers and writers may use their API from any context (including scheduler and NMI). This ringbuffer will make it possible to decouple printk() callers from any context, locking, or console constraints. It also makes it possible for readers to have full access to the ringbuffer contents at any time and context (for example from any panic situation).

kernel/printk/printk_ringbuffer.c new file +7 -0
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,

kernel/printk/printk_ringbuffer.c line 547

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);

Hmm, I wonder whether data_ring->tail_lpos and data_ring->head_lpos are synchronized enough between each other.

I feel that there should be read barrier here. But it seems that more barriers are missing. For example, let's have:

CPU0 CPU1

data_alloc()
begin_lpos = atomic_read(data_ring->head_lpos);

				data_alloc()
				  data_push_tail()
				    cmpxchg(data_ring->tail_lpos);
				    // A: no barrier
				  cmpxchg(data_ring->head_lpos);
  data_push_tail()
    // B: no barrier
    tail_lpos = atomic_read(data_ring->tail_lpos);

Problem 1:

CPU0 might see random ordering of data_ring->tail_lpos and head_lpos values modified by CPU1. There are missing both write and read barriers.

Problem 2:

There might be still a chance because CPU0 does:

     if (!data_make_reusable())
       smp_rmb()
       tail_lpos = atomic_read(data_ring->tail_lpos);

But CPU0 might still see old data_ring->tail because CPU1 did not do write barrier.

My proposal:

1. There should be full memory barrier on the location A before updating data_ring->head_lpos. It will be the same as the full barriers needed before updating data_ring->tail_lpos.

data_ring->tail_lpos might have been pushed by another CPU. We need to make sure that all CPUs see all needed changes before we data_alloc() pushes head_lpos.

2. There should be read memory barrier in the location B.

It is not strictly necessary because data_push_tail() tries to re-read data_ring->tail_lpos after a read barrier. But the re-read is just a fallback.

The read barrier before the first read should be there to keep "clean" design ;-) Or there should be at least some comment about why the barrier is not there.

Best Regards,
Petr

Quoted 117 lines
kernel/printk/printk_ringbuffer.c new file +117 -0
+
+	do {
+		/* Done, if the tail lpos is already at or beyond @lpos. */
+		if ((lpos - tail_lpos) - 1 >= DATA_SIZE(data_ring))
+			break;
+
+		/*
+		 * Make all descriptors reusable that are associated with
+		 * data blocks before @lpos.
+		 */
+		if (!data_make_reusable(rb, data_ring, tail_lpos, lpos,
+					&next_lpos)) {
+			/*
+			 * Guarantee the descriptor state loaded in
+			 * data_make_reusable() is performed before reloading
+			 * the tail lpos. The failed data_make_reusable() may
+			 * be due to a newly recycled descriptor causing
+			 * the tail lpos to have been previously pushed. This
+			 * pairs with desc_reserve:D.
+			 *
+			 * Memory barrier involvement:
+			 *
+			 * If data_make_reusable:D reads from desc_reserve:G,
+			 * then data_push_tail:B reads from data_push_tail:D.
+			 *
+			 * Relies on:
+			 *
+			 * MB from data_push_tail:D to desc_reserve:G
+			 *    matching
+			 * RMB from data_make_reusable:D to data_push_tail:B
+			 *
+			 * Note: data_push_tail:D and desc_reserve:G can be
+			 *       different CPUs. However, the desc_reserve:G
+			 *       CPU (which performs the full memory barrier)
+			 *       must have previously seen data_push_tail:D.
+			 */
+			smp_rmb(); /* LMM(data_push_tail:A) */
+
+			next_lpos = atomic_long_read(&data_ring->tail_lpos
+						); /* LMM(data_push_tail:B) */
+			if (next_lpos == tail_lpos)
+				return false;
+
+			/* Another task pushed the tail. Try again. */
+			tail_lpos = next_lpos;
+			continue;
+		}
+
+		/*
+		 * Guarantee any descriptor states that have transitioned to
+		 * reusable are stored before pushing the tail lpos. This
+		 * allows readers to identify if data has expired while
+		 * reading the descriptor. This pairs with desc_read:D.
+		 */
+		smp_mb(); /* LMM(data_push_tail:C) */
+
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->tail_lpos,
+			&tail_lpos, next_lpos)); /* LMM(data_push_tail:D) */
+
+	return true;
+}
+
+/*
+ * Allocate a new data block, invalidating the oldest data block(s)
+ * if necessary. This function also associates the data block with
+ * a specified descriptor.
+ */
+static char *data_alloc(struct printk_ringbuffer *rb,
+			struct prb_data_ring *data_ring, unsigned long size,
+			struct prb_data_blk_lpos *blk_lpos, unsigned long id)
+{
+	struct prb_data_block *blk;
+	unsigned long begin_lpos;
+	unsigned long next_lpos;
+
+	if (!data_ring->data || size == 0) {
+		/* Specify a data-less block. */
+		blk_lpos->begin = INVALID_LPOS;
+		blk_lpos->next = INVALID_LPOS;
+		return NULL;
+	}
+
+	size = to_blk_size(size);
+
+	begin_lpos = atomic_long_read(&data_ring->head_lpos);
+
+	do {
+		next_lpos = get_next_lpos(data_ring, begin_lpos, size);
+
+		if (!data_push_tail(rb, data_ring,
+				    next_lpos - DATA_SIZE(data_ring))) {
+			/* Failed to allocate, specify a data-less block. */
+			blk_lpos->begin = INVALID_LPOS;
+			blk_lpos->next = INVALID_LPOS;
+			return NULL;
+		}
+	} while (!atomic_long_try_cmpxchg_relaxed(&data_ring->head_lpos,
+						  &begin_lpos, next_lpos));
+
+	/*
+	 * Guarantee any updated tail lpos is stored before setting the new
+	 * block ID. This allows block IDs to be trusted based on the tail
+	 * lpos. A full memory barrier is needed since another task may
+	 * have updated the tail lpos. This pairs with data_make_reusable:B.
+	 */
+	smp_mb(); /* LMM(data_alloc:A) */
+
+	blk = to_block(data_ring, begin_lpos);
+	WRITE_ONCE(blk->id, id); /* LMM(data_alloc:B) */
+
+	if (DATA_WRAPS(data_ring, begin_lpos) !=
+	    DATA_WRAPS(data_ring, next_lpos)) {
+		/* Wrapping data blocks store their data at the beginning. */
+		blk = to_block(data_ring, 0);
+
+		/*
+		 * Store the ID on the wrapped block for consistency.

kernel/printk/printk_ringbuffer.c line 855

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+		 * The printk_ringbuffer does not actually use it.
+		 */
+		blk->id = id;
+	}
+
+	blk_lpos->begin = begin_lpos;
+	blk_lpos->next = next_lpos;
+
+	return &blk->data[0];
+}

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#26 lore raw

Re: data_ring head_lpos and tail_lpos synchronization: was [PATCH v2 2/3] printk: add lockless buffer

Quoted 42 lines · Petr Mladek
Quoted 9 lines
kernel/printk/printk_ringbuffer.c new file +7 -0
+/*
+ * Advance the data ring tail to at least @lpos. This function puts
+ * descriptors into the reusable state if the tail is pushed beyond
+ * their associated data block.
+ */
+static bool data_push_tail(struct printk_ringbuffer *rb,
+			   struct prb_data_ring *data_ring,

kernel/printk/printk_ringbuffer.c line 547

Quoted 10 lines
kernel/printk/printk_ringbuffer.c new file +10 -0
+			   unsigned long lpos)
+{
+	unsigned long tail_lpos;
+	unsigned long next_lpos;
+
+	/* If @lpos is not valid, there is nothing to do. */
+	if (lpos == INVALID_LPOS)
+		return true;
+
+	tail_lpos = atomic_long_read(&data_ring->tail_lpos);

Hmm, I wonder whether data_ring->tail_lpos and data_ring->head_lpos are synchronized enough between each other.

I feel that there should be read barrier here. But it seems that more barriers are missing. For example, let's have:

CPU0 CPU1

data_alloc()
begin_lpos = atomic_read(data_ring->head_lpos);

				data_alloc()
				  data_push_tail()
				    cmpxchg(data_ring->tail_lpos);
				    // A: no barrier
				  cmpxchg(data_ring->head_lpos);
  data_push_tail()
    // B: no barrier
    tail_lpos = atomic_read(data_ring->tail_lpos);
Quoted 5 lines

Problem 1:

CPU0 might see random ordering of data_ring->tail_lpos and head_lpos values modified by CPU1. There are missing both write and read barriers.

You need to explain why this is a problem. CPU0 saw some head and some tail. Both values are at least the current values (i.e. there is no danger that it sees a tail that is further than the tail really is).

CPU0 then uses the head/tail values to determine how far to advance the tail and how far to advance the head. Both of these advances use cmpxchg_relaxed(). So there is no danger of random head/tail modifications. Upon cmpxchg_relaxed() failure, the new current values are loaded and it retries based on the new values.

The only issue is if data_push_tail()/data_make_reusable() are able to recognize that a data area is already recycled. And both functions have memory barriers in place for that.

Quoted 10 lines

Problem 2:

There might be still a chance because CPU0 does:

     if (!data_make_reusable())
       smp_rmb()
       tail_lpos = atomic_read(data_ring->tail_lpos);

But CPU0 might still see old data_ring->tail because CPU1 did not do write barrier.

I claim that it does not matter. The smp_rmb() here pairs with the full memory barrier LMM(desc_reserve:D). The reasoning:

* Guarantee any data ring tail changes are stored before
* recycling the descriptor. Data ring tail changes can happen
* via desc_push_tail()->data_push_tail(). A full memory
* barrier is needed since another task may have pushed the
* data ring tails. This pairs with data_push_tail:A.

So if data_make_reusable() failed due to a descriptor already being recycled, we know CPU0 will be able to read an updated tail value (and try again with the new value).

John Ogness

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec

author maintainer
#27 lore raw

PATCH v2 3/3 printk: use the lockless ringbuffer

In reply to John Ogness

Replace the existing ringbuffer usage and implementation with lockless ringbuffer usage. Even though the new ringbuffer does not require locking, all existing locking is left in place. Therefore, this change is purely replacing the underlining ringbuffer.

Changes that exist due to the ringbuffer replacement:

- The VMCOREINFO has been updated for the new structures.

- Dictionary data is now stored in a separate data buffer from the human-readable messages. The dictionary data buffer is set to the same size as the message buffer. Therefore, the total required memory for both dictionary and message data is
2 * (2 ^ CONFIG_LOG_BUF_SHIFT) for the initial static buffers and 2 * log_buf_len (the kernel parameter) for the dynamic buffers.

- Record meta-data is now stored in a separate array of descriptors. This is an additional 72 * (2 ^ (CONFIG_LOG_BUF_SHIFT - 5)) bytes for the static array and 72 * (log_buf_len >> 5) bytes for the dynamic array.

---
 include/linux/kmsg_dump.h |   2 -
 kernel/printk/printk.c    | 938 ++++++++++++++++++++------------------
 2 files changed, 492 insertions(+), 448 deletions(-)
include/linux/kmsg_dump.h +0 -2
index 2e7a1e032c71..ae6265033e31 100644
@@ -46,8 +46,6 @@ struct kmsg_dumper {
 	bool registered;
 
 	/* private state of the kmsg iterator */
-	u32 cur_idx;
-	u32 next_idx;
 	u64 cur_seq;
 	u64 next_seq;
 };
kernel/printk/printk.c +492 -446

1,458 lines not on this page · raw message

Signature · 7 lines
2.20.1


_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec
author maintainer
#28 lore raw

Re: [PATCH v2 3/3] printk: use the lockless ringbuffer

Hi,

I discovered a bug while preparing my next series, which also made me realize I had never tested the extended mode feature of netconsole. :-/ The only other user of extended output is /dev/kmsg, and it is doing it correctly.

Explanation and patch below.

Quoted 9 lines · John Ogness
kernel/printk/printk.c +1 -0
index 9a9b6156270b..0d74ca748b82 100644
@@ -2395,12 +2443,17 @@ void console_unlock(void)
 	static char text[LOG_LINE_MAX + PREFIX_MAX];
 	unsigned long flags;
 	bool do_cond_resched, retry;
+	struct printk_info info;

kernel/printk/printk.c void console_unlock(void) · line 2456

Quoted 10 lines
kernel/printk/printk.c +4 -0
+	struct printk_record r;
 
 	if (console_suspended) {
 		up_console_sem();
 		return;
 	}
 
+	prb_rec_init_rd(&r, &info, text, sizeof(text), ext_text,
+			sizeof(ext_text));
+

Using @ext_text for the dictionary buffer. But extended mode will need that buffer for generating extended output!

Quoted 16 lines
kernel/printk/printk.c +3 -3
 	/*
 	 * Console drivers are called with interrupts disabled, so
 	 * @console_may_schedule should be cleared before; however, we may
@@ -2470,19 +2514,20 @@ void console_unlock(void)
 			exclusive_console = NULL;
 		}
 
-		len += msg_print_text(msg,
+		len = record_print_text(&r,
 				console_msg_format & MSG_FORMAT_SYSLOG,
-				printk_time, text + len, sizeof(text) - len);
+				printk_time);
 		if (nr_ext_console_drivers) {
-			ext_len = msg_print_ext_header(ext_text,
+			ext_len = info_print_ext_header(ext_text,
 						sizeof(ext_text),

kernel/printk/printk.c void console_unlock(void) · line 2529

Quoted 10 lines
kernel/printk/printk.c +5 -3
-						msg, console_seq);
+						r.info);
 			ext_len += msg_print_ext_body(ext_text + ext_len,
 						sizeof(ext_text) - ext_len,
-						log_dict(msg), msg->dict_len,
-						log_text(msg), msg->text_len);
+						&r.dict_buf[0],
+						r.info->dict_len,
+						&r.text_buf[0],
+						r.info->text_len);

2 problems here:

First, record_print_text() works by modifying the record text buffer "in-place". So when msg_print_ext_body() creates the extended output, it will be using a modified text buffer (i.e. one with prefix added).

Second, info_print_ext_header() and msg_print_ext_body() are clobbering the dictionary buffer because @ext_text _is_ @r.dict_buf.

This can be resolved by giving the record a separate dictionary buffer and calling record_print_text() after preparing any extended console text. Patch below...

John Ogness

kernel/printk/printk.c +9 -5
index 0d74ca748b82..cc79ad67e6e3 100644
@@ -2441,6 +2441,7 @@ void console_unlock(void)
 {
 	static char ext_text[CONSOLE_EXT_LOG_MAX];
 	static char text[LOG_LINE_MAX + PREFIX_MAX];
+	static char dict[LOG_LINE_MAX];
 	unsigned long flags;
 	bool do_cond_resched, retry;
 	struct printk_info info;
@@ -2451,8 +2452,7 @@ void console_unlock(void)
 		return;
 	}
 
-	prb_rec_init_rd(&r, &info, text, sizeof(text), ext_text,
-			sizeof(ext_text));
+	prb_rec_init_rd(&r, &info, text, sizeof(text), dict, sizeof(dict));
 
 	/*
 	 * Console drivers are called with interrupts disabled, so
@@ -2514,9 +2514,10 @@ void console_unlock(void)
 			exclusive_console = NULL;
 		}
 
-		len = record_print_text(&r,
-				console_msg_format & MSG_FORMAT_SYSLOG,
-				printk_time);
+		/*
+		 * Handle extended console text first because later
+		 * record_print_text() will modify the record buffer in-place.
+		 */
 		if (nr_ext_console_drivers) {
 			ext_len = info_print_ext_header(ext_text,
 						sizeof(ext_text),
@@ -2528,6 +2529,9 @@ void console_unlock(void)
 						&r.text_buf[0],
 						r.info->text_len);
 		}
+		len = record_print_text(&r,
+				console_msg_format & MSG_FORMAT_SYSLOG,
+				printk_time);
 		console_seq++;
 		raw_spin_unlock(&logbuf_lock);
 
Signature · 1 line
2.20.1
#29 lore raw
In reply to John Ogness
Quoted 7 lines · John Ogness

Hello,

Here is a v2 for the first series to rework the printk subsystem. The v1 and history are here [0]. This first series only replaces the existing ringbuffer implementation. No locking is removed. No semantics/behavior of printk are changed.

Quoted 9 lines

The VMCOREINFO is updated. RFC patches for the external tools crash(8) [1] and makedumpfile(8) [2] have been submitted that allow the new ringbuffer to be correctly read.

This series is in line with the agreements [3] made at the meeting during LPC2019 in Lisbon, with 1 exception: support for dictionaries will not be discontinued [4]. Dictionaries are stored in a separate buffer so that they cannot interfere with the human-readable buffer.

Hey John,

I tested this on two 128-cpu ppc64le power8 boxes, and a 64 core x86_64 box using your prb-test testsuite with the latest upstream kernel. The tests ran successfully for ~16 hours without any problems.

P.

Acked-by on the v2 series
#30 lore raw
In reply to John Ogness
Quoted 7 lines · John Ogness

Hello,

Here is a v2 for the first series to rework the printk subsystem. The v1 and history are here [0]. This first series only replaces the existing ringbuffer implementation. No locking is removed. No semantics/behavior of printk are changed.

Quoted 8 lines

The VMCOREINFO is updated. RFC patches for the external tools crash(8) [1] and makedumpfile(8) [2] have been submitted that allow the new ringbuffer to be correctly read.

This series is in line with the agreements [3] made at the meeting during LPC2019 in Lisbon, with 1 exception: support for dictionaries will not be discontinued [4]. Dictionaries are stored in a separate buffer so that they cannot interfere with the human-readable buffer.

I'm willing to bless this. The code looks good to me, nice job guys.

	-ss

_______________________________________________
kexec mailing list
[email protected]
http://lists.infradead.org/mailman/listinfo/kexec