printk: new ringbuffer implementation
Subsystems (3)
John Ogness
maintainerv2 cover printk: new ringbuffer implementation
Hello,
This is a follow-up RFC on the work to reimplement much of the core of printk. The original thread can be seen here[0].
One of the results of that thread was that the work needs to be broken up into several pieces. A roadmap was laid out[1] and this RFC is for the base component of the first piece:
a new ringbuffer implementation for printk.
This series does not touch any existing printk code. It is only the ringbuffer implementation. I am particularly interested in feedback relating to the design of the ringbuffer and the use of memory barriers.
The series also includes a test module that performs some heavy writer stress testing. I have successfully run these tests on a 16-core ARM64 platform.
John Ogness
[0] https://lkml.kernel.org/r/[email protected]
[1] https://lkml.kernel.org/r/[email protected]
John Ogness (2):
printk-rb: add a new printk ringbuffer implementation
printk-rb: add test module
Documentation/core-api/index.rst | 1 + Documentation/core-api/printk-ringbuffer.rst | 104 +++ include/linux/printk_ringbuffer.h | 238 +++++++ lib/Makefile | 2 + lib/printk_ringbuffer.c | 924 +++++++++++++++++++++++++++ lib/test_prb.c | 237 +++++++ 6 files changed, 1506 insertions(+) create mode 100644 Documentation/core-api/printk-ringbuffer.rst create mode 100644 include/linux/printk_ringbuffer.h create mode 100644 lib/printk_ringbuffer.c create mode 100644 lib/test_prb.c
Signature · 1 line
2.11.0
John Ogness
maintainerRFC PATCH v2 1/2 printk-rb: add a new printk ringbuffer implementation
See documentation for details.
--- Documentation/core-api/index.rst | 1 + Documentation/core-api/printk-ringbuffer.rst | 104 +++ include/linux/printk_ringbuffer.h | 238 +++++++ lib/printk_ringbuffer.c | 924 +++++++++++++++++++++++++++ 4 files changed, 1267 insertions(+) create mode 100644 Documentation/core-api/printk-ringbuffer.rst create mode 100644 include/linux/printk_ringbuffer.h create mode 100644 lib/printk_ringbuffer.c
Documentation/core-api/index.rst +1 -0
@@ -27,6 +27,7 @@ Core utilities errseq printk-formats circular-buffers + printk-ringbuffer generic-radix-tree memory-allocation mm-api
Documentation/core-api/printk-ringbuffer.rst new file +104 -0
104 lines not on this page · raw message
include/linux/printk_ringbuffer.h new file +238 -0
238 lines not on this page · raw message
lib/printk_ringbuffer.c new file +924 -0
924 lines not on this page · raw message
Signature · 1 line
2.11.0
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Hello John,
On (06/07/19 18:29), John Ogness wrote:
[..]
Documentation/core-api/printk-ringbuffer.rst line 67
Quoted 8 lines
Documentation/core-api/printk-ringbuffer.rst new file +8
-0+ struct prb_reserved_entry e; + char *s; + + s = prb_reserve(&e, &rb, 32); + if (s) { + sprintf(s, "Hello, world!"); + prb_commit(&e); + }
A nit: snprintf().
sprintf() is tricky, it may write "slightly more than was anticipated" bytes - all those string_nocheck(" disabled"), error_string("pK-error"), etc.
[..]
Quoted 10 lines
Documentation/core-api/printk-ringbuffer.rst new file +10
-0+Sample reader code:: + + DECLARE_PRINTKRB_ENTRY(entry, 128); + DECLARE_PRINTKRB_ITER(iter, &test_rb, &entry); + u64 last_seq = 0; + int len; + char *s; + + prb_for_each_entry(&iter, len) { + if (entry.seq - last_seq != 1) {
Documentation/core-api/printk-ringbuffer.rst line 92
Quoted 10 lines
Documentation/core-api/printk-ringbuffer.rst new file +10
-0+ printf("LOST %llu ENTRIES\n", + entry.seq - (last_seq + 1)); + } + last_seq = entry.seq; + + s = (char *)&entry.buffer[0]; + if (len >= 128) + s[128 - 1] = 0; + printf("data: %s\n", s); + }
How are we going to handle pr_cont() loops?
print_modules()
preempt_disable(); list_for_each_entry_rcu(mod, &modules, list) {
pr_cont(" %s%s", mod->name, module_flags(mod, buf));
}
preempt_enable();
-ss
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 11 lines · Sergey Senozhatsky
Documentation/core-api/printk-ringbuffer.rst line 67
Quoted 8 lines
Documentation/core-api/printk-ringbuffer.rst new file +8
-0+ struct prb_reserved_entry e; + char *s; + + s = prb_reserve(&e, &rb, 32); + if (s) { + sprintf(s, "Hello, world!"); + prb_commit(&e); + }A nit:
snprintf().
Quoted 3 lines
sprintf()is tricky, it may write "slightly more than was anticipated" bytes - all thosestring_nocheck(" disabled"),error_string("pK-error"), etc.
Agreed. Documentation should show good examples.
Quoted 23 lines
Quoted 10 lines
Documentation/core-api/printk-ringbuffer.rst new file +10
-0+Sample reader code:: + + DECLARE_PRINTKRB_ENTRY(entry, 128); + DECLARE_PRINTKRB_ITER(iter, &test_rb, &entry); + u64 last_seq = 0; + int len; + char *s; + + prb_for_each_entry(&iter, len) { + if (entry.seq - last_seq != 1) {Documentation/core-api/printk-ringbuffer.rst line 92
Quoted 10 lines
Documentation/core-api/printk-ringbuffer.rst new file +10
-0+ printf("LOST %llu ENTRIES\n", + entry.seq - (last_seq + 1)); + } + last_seq = entry.seq; + + s = (char *)&entry.buffer[0]; + if (len >= 128) + s[128 - 1] = 0; + printf("data: %s\n", s); + }How are we going to handle
pr_cont()loops?
Quoted 6 lines
print_modules()
preempt_disable();list_for_each_entry_rcu(mod, &modules, list){
pr_cont(" %s%s", mod->name, module_flags(mod, buf));
}
preempt_enable();
pr_cont() (in its current form) is not related to the printk buffer because cont messages use their own separate struct cont buffer. And for the initial integration of the new ringbuffer I would leave that as it is. Which means initially, pr_cont() would still sit behind a raw spinlock and pr_cont() from NMI context would be stored as individual messages.
However, to remove the spinlock of the cont buffer and allow pr_cont() to work from NMI context, I would like to introduce a separate lockless ringbuffer instance for cont that contains all the cont pieces (including the caller_id). As soon as the caller_id changes from the oldest record in the cont ringbuffer, that caller would assemble the full cont message, popping all the pieces from the ringbuffer (with a single cmpxchg) and insert the message to the printk ringbuffer.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 12 lines · John Ogness
Quoted 11 lines · Sergey Senozhatsky
Documentation/core-api/printk-ringbuffer.rst line 67
Quoted 8 lines
Documentation/core-api/printk-ringbuffer.rst new file +8
-0+ struct prb_reserved_entry e; + char *s; + + s = prb_reserve(&e, &rb, 32); + if (s) { + sprintf(s, "Hello, world!"); + prb_commit(&e); + }A nit:
snprintf().
Quoted 5 lines
Quoted 3 lines
sprintf()is tricky, it may write "slightly more than was anticipated" bytes - all thosestring_nocheck(" disabled"),error_string("pK-error"), etc.Agreed. Documentation should show good examples.
In vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.
printk("%pS %s\n", regs->ip, current->name)
prb_reserve(&e, &rb, ????);or are we going to run vscnprintf() on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) -> prb_commit(&e)?
-ss
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 22 lines · Sergey Senozhatsky
Quoted 12 lines · John Ogness
Quoted 11 lines · Sergey Senozhatsky
Documentation/core-api/printk-ringbuffer.rst line 67
Quoted 8 lines
Documentation/core-api/printk-ringbuffer.rst new file +8
-0+ struct prb_reserved_entry e; + char *s; + + s = prb_reserve(&e, &rb, 32); + if (s) { + sprintf(s, "Hello, world!"); + prb_commit(&e); + }A nit:
snprintf().Quoted 5 lines
Quoted 3 lines
sprintf()is tricky, it may write "slightly more than was anticipated" bytes - all thosestring_nocheck(" disabled"),error_string("pK-error"), etc.Agreed. Documentation should show good examples.
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.
Quoted 6 lines
printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?
I'm asking this because, well, if the most common usage pattern (printk->prb_reserve) will always reserve fixed size records (aka data blocks), then you _probably_ (??) can drop the 'variable size records' requirement from prb design and start looking at records (aka data blocks) as fixed sized chunks of bytes, which are always located at fixed offsets.
-ss
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 20 lines · Sergey Senozhatsky
Quoted 11 lines
Quoted 11 lines
Documentation/core-api/printk-ringbuffer.rst line 67
Quoted 8 lines
Documentation/core-api/printk-ringbuffer.rst new file +8
-0+ struct prb_reserved_entry e; + char *s; + + s = prb_reserve(&e, &rb, 32); + if (s) { + sprintf(s, "Hello, world!"); + prb_commit(&e); + }A nit:
snprintf().Quoted 5 lines
Quoted 3 lines
sprintf()is tricky, it may write "slightly more than was anticipated" bytes - all thosestring_nocheck(" disabled"),error_string("pK-error"), etc.Agreed. Documentation should show good examples.
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.
Quoted 6 lines
printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?
(As suggested by Petr) I want to use vscnprintf() on a NULL buffer. However, a NULL buffer is not sufficient because things like the loglevel are sometimes added via %s (for example, in /dev/kmsg). So rather than a NULL buffer, I would use a small buffer on the stack (large enough to store loglevel/cont information). This way we can use vscnprintf() to get the exact size _and_ printk_get_level() will see enough of the formatted string to parse what it needs.
Quoted 7 lines
I'm asking this because, well, if the most common usage pattern (
printk->prb_reserve) will always reserve fixed size records (aka data blocks), then you _probably_ (??) can drop the 'variable size records' requirement from prb design and start looking at records (aka data blocks) as fixed sized chunks of bytes, which are always located at fixed offsets.
The average printk message size is well under 128 bytes. It would be quite wasteful to always reserve 1K blocks.
John Ogness
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 11 lines · John Ogness
Quoted 9 lines · Sergey Senozhatsky
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?
Quoted 7 lines
(As suggested by Petr) I want to use
vscnprintf()on a NULL buffer. However, a NULL buffer is not sufficient because things like the loglevel are sometimes added via %s (for example, in/dev/kmsg). So rather than a NULL buffer, I would use a small buffer on the stack (large enough to store loglevel/cont information). This way we can usevscnprintf()to get the exact size _and_printk_get_level()will see enough of the formatted string to parse what it needs.
vscnprintf() with NULL pointer is perfectly fine. Only the formatted string has variable size.
Log level, timestamp, and other information can be stored as metadata with a fixed size, see struct printk_log. They are formatted as text later, see msg_print_text() and msg_print_ext_header().
Quoted 10 lines
Quoted 7 lines
I'm asking this because, well, if the most common usage pattern (
printk->prb_reserve) will always reserve fixed size records (aka data blocks), then you _probably_ (??) can drop the 'variable size records' requirement from prb design and start looking at records (aka data blocks) as fixed sized chunks of bytes, which are always located at fixed offsets.The average printk message size is well under 128 bytes. It would be quite wasteful to always reserve 1K blocks.
Yes, I think that we need to store the strings in variable sized chunks.
Best Regards,
Petr
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 20 lines · Petr Mladek
Quoted 11 lines · John Ogness
Quoted 9 lines · Sergey Senozhatsky
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?Quoted 7 lines
(As suggested by Petr) I want to use
vscnprintf()on a NULL buffer. However, a NULL buffer is not sufficient because things like the loglevel are sometimes added via %s (for example, in/dev/kmsg). So rather than a NULL buffer, I would use a small buffer on the stack (large enough to store loglevel/cont information). This way we can usevscnprintf()to get the exact size _and_printk_get_level()will see enough of the formatted string to parse what it needs.
Quoted 2 lines
vscnprintf()with NULL pointer is perfectly fine. Only the formatted string has variable size.
Yeah, that should work. Probably. Can't think of any issues, except for increased CPU usage. Some sprintf() format specifiers are heavier than the rest (pS/pF on ia64/ppc/hppa).
OK, very theoretically.
There is a difference.
Doing "sz = vscprintf(NULL, msg); vscnprintf(buf, sz, msg)" for msg_print_text() and msg_print_ext_header() was safe, because the data - msg - would not change under us, we would work with logbuf records, IOW with data which is owned by printk() and printk only.
But doing
sz = vcsprintf(NULL, "xxx", random_pointer);
if ((buf = prb_reserve(... sz))) {
vscnprintf(buf, sz, "xxx", random_pointer);
prb_commit(...);
}might have different outcome sometimes. We probably (!!!) can have some race conditions. The problem is that, unlike msg_print_text() and msg_print_ext_header(), printk() works with pointers which it does not own nor control. IOW within single printk() we will access some random kernel pointers, then do prb stuff, then access those same pointers, expecting that none of them will ever change their state. A very simple example
printk("Comm %s\n", current->comm)Suppose printk on CPU0 and ia64_mca_modify_comm on CPU1
CPU0 CPU1
printk(...)
sz = vscprintf(NULL, "Comm %s\n", current->comm); ia64_mca_modify_comm() snprintf(comm, sizeof(comm), "%s %d", current->comm, previous_current->pid); memcpy(current->comm, comm, sizeof(current->comm));
if ((buf = prb_reserve(... sz))) {
vscnprintf(buf, "Comm %s\n", current->comm);
^^^^^^^^^^^^^^ ->comm has changed.
Nothing critical, we should not corrupt anything, but we will truncate ->comm if its new size is larger than what it used to be when we did vscprintf(NULL).
prb_commit(...);
}
Probably there can be other examples.
-ss
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 72 lines · Sergey Senozhatsky
Quoted 18 lines
Quoted 10 lines
Quoted 9 lines
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?Quoted 7 lines
(As suggested by Petr) I want to use
vscnprintf()on a NULL buffer. However, a NULL buffer is not sufficient because things like the loglevel are sometimes added via %s (for example, in/dev/kmsg). So rather than a NULL buffer, I would use a small buffer on the stack (large enough to store loglevel/cont information). This way we can usevscnprintf()to get the exact size _and_printk_get_level()will see enough of the formatted string to parse what it needs.Quoted 2 lines
vscnprintf()with NULL pointer is perfectly fine. Only the formatted string has variable size.Yeah, that should work. Probably. Can't think of any issues, except for increased CPU usage. Some
sprintf()format specifiers are heavier than the rest (pS/pF on ia64/ppc/hppa).OK, very theoretically.
There is a difference.
Doing "sz =
vscprintf(NULL, msg);vscnprintf(buf, sz, msg)" formsg_print_text()andmsg_print_ext_header()was safe, because the data - msg - would not change under us, we would work with logbuf records, IOW with data which is owned byprintk()and printk only.But doing
sz = vcsprintf(NULL, "xxx", random_pointer); if ((buf = prb_reserve(... sz))) { vscnprintf(buf, sz, "xxx", random_pointer); prb_commit(...); }might have different outcome sometimes. We probably (!!!) can have some race conditions. The problem is that, unlike
msg_print_text()andmsg_print_ext_header(),printk()works with pointers which it does not own nor control. IOW within singleprintk()we will access some random kernel pointers, then do prb stuff, then access those same pointers, expecting that none of them will ever change their state. A very simple exampleprintk("Comm %s\n", current->comm)Suppose printk on CPU0 and
ia64_mca_modify_common CPU1CPU0 CPU1
printk(...)sz = vscprintf(NULL, "Comm %s\n", current->comm); ia64_mca_modify_comm() snprintf(comm, sizeof(comm), "%s %d", current->comm, previous_current->pid); memcpy(current->comm, comm, sizeof(current->comm));if ((buf = prb_reserve(... sz))) {
vscnprintf(buf, "Comm %s\n", current->comm);
^^^^^^^^^^^^^^ ->comm has changed.
Nothing critical, we should not corrupt anything, but we will truncate ->comm if its new size is larger than what it used to be when we did vscprintf(NULL).
prb_commit(...);
}
Quoted 1 line
Probably there can be other examples.
This is a very good point, and quite important. It is not acceptable if some crash output is cut off because of this effect.
In my v1 rfc series, I avoided this issue by having a separate dedicated ringbuffer (rb_sprintf) that was used to allocate a temporary max-size (2KB) buffer for sprinting to. Then _that_ was used for the real ringbuffer input (strlen, prb_reserve, memcpy, prb_commit). That would still be the approach of my choice.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
On (06/25/19 14:03), John Ogness wrote:
[..]
Quoted 18 lines
Quoted 18 lines
CPU0 CPU1
printk(...)sz = vscprintf(NULL, "Comm %s\n", current->comm); ia64_mca_modify_comm() snprintf(comm, sizeof(comm), "%s %d", current->comm, previous_current->pid); memcpy(current->comm, comm, sizeof(current->comm));if ((buf = prb_reserve(... sz))) {
vscnprintf(buf, "Comm %s\n", current->comm);
^^^^^^^^^^^^^^ ->comm has changed.
Nothing critical, we should not corrupt anything, but we will truncate ->comm if its new size is larger than what it used to be when we did vscprintf(NULL).
prb_commit(...);
}
[..]
Quoted 5 lines
In my v1 rfc series, I avoided this issue by having a separate dedicated ringbuffer (
rb_sprintf) that was used to allocate a temporary max-size (2KB) buffer for sprinting to. Then _that_ was used for the real ringbuffer input (strlen,prb_reserve, memcpy,prb_commit). That would still be the approach of my choice.
In other words per-CPU buffering, AKA printk_safe ;)
-ss
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 20 lines · Sergey Senozhatsky
[..]
Quoted 10 lines
Quoted 10 lines
CPU0 CPU1
printk(...)sz = vscprintf(NULL, "Comm %s\n", current->comm); ia64_mca_modify_comm() snprintf(comm, sizeof(comm), "%s %d", current->comm, previous_current->pid); memcpy(current->comm, comm, sizeof(current->comm)); if ((buf = prb_reserve(... sz))) { vscnprintf(buf, "Comm %s\n", current->comm); ^^^^^^^^^^^^^^ ->comm has changed. Nothing critical, weQuoted 8 lines
Quoted 8 lines
should not corrupt anything, but we will truncate ->comm if its new size is larger than what it used to be when we did vscprintf(NULL).
prb_commit(...);
}
Quoted 8 lines
[..]
Quoted 5 lines
In my v1 rfc series, I avoided this issue by having a separate dedicated ringbuffer (
rb_sprintf) that was used to allocate a temporary max-size (2KB) buffer for sprinting to. Then _that_ was used for the real ringbuffer input (strlen,prb_reserve, memcpy,prb_commit). That would still be the approach of my choice.In other words per-CPU buffering, AKA
printk_safe;)
Actually, no. I made use of a printk_ringbuffer (which is global). It was used for temporary memory allocation for sprintf, but the result was immediately written into the printk buffer from the same context. In contrast, printk_safe triggers a different context to handle the insertion.
It is still my intention to eliminate the buffering component of printk_safe.
After we get a lockless ringbuffer that we are happy with, my next series to integrate the buffer into printk will again use the sprint_rb solution to avoid the issue discussed in this thread. Perhaps it would be best to continue this discussion after I've posted that series.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 8 lines · John Ogness
Quoted 7 lines · Sergey Senozhatsky
[..]
Quoted 5 lines
In my v1 rfc series, I avoided this issue by having a separate dedicated ringbuffer (
rb_sprintf) that was used to allocate a temporary max-size (2KB) buffer for sprinting to. Then _that_ was used for the real ringbuffer input (strlen,prb_reserve, memcpy,prb_commit). That would still be the approach of my choice.
Quoted 7 lines
Quoted 1 line
In other words per-CPU buffering, AKA
printk_safe;)Actually, no. I made use of a
printk_ringbuffer(which is global). It was used for temporary memory allocation for sprintf, but the result was immediately written into the printk buffer from the same context. In contrast,printk_safetriggers a different context to handle the insertion.
I agree that's not relevant to your patch. But let me explain what I meant. printk_safe has many faces. The NMI part of printk_safe has the PRINTK_NMI_DIRECT_CONTEXT_MASK bufferring bypass - when we know that we are in NMI and printk logbuf is unlocked then we can do the normal logbuf_store() from NMI, avoiding irq flush because the data is already in the main log buffer. We also can do the same buffering bypass for non-NMI part of printk_safe, but just sometimes. PRINTK_SAFE_CONTEXT_MASK most of the times indicates that logbuf is locked, but not always - e.g. we call console_drivers under PRINTK_SAFE_CONTEXT_MASK.
But like I said, not relevant to your patch. The relevant part is the possibility of race conditions.
Quoted 2 lines
It is still my intention to eliminate the buffering component of
printk_safe.
That's understandable.
Quoted 3 lines
After we get a lockless ringbuffer that we are happy with, my next series to integrate the buffer into printk will again use the
sprint_rbsolution to avoid the issue discussed in this thread.
Yes, I agree that either sprint_rb or just 2 LOG_LINE_MAX per-CPU buffers looks safer. This basically means that printk cannot use printk_ringbuffer as is and needs some sort of extra layer next to (or atop of) printk_ringbuffer, but we have the same thing in printk right now, basically. static char textbuf[LOG_LINE_MAX] -> logbuf.
-ss
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 12 lines · John Ogness
Quoted 11 lines · Sergey Senozhatsky
[..]
Quoted 10 lines
Quoted 10 lines
CPU0 CPU1
printk(...)sz = vscprintf(NULL, "Comm %s\n", current->comm); ia64_mca_modify_comm() snprintf(comm, sizeof(comm), "%s %d", current->comm, previous_current->pid); memcpy(current->comm, comm, sizeof(current->comm)); if ((buf = prb_reserve(... sz))) { vscnprintf(buf, "Comm %s\n", current->comm); ^^^^^^^^^^^^^^ ->comm has changed. Nothing critical, we
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
should not corrupt anything, but we will truncate ->comm if its new size is larger than what it used to be when we did vscprintf(NULL).
prb_commit(...);
}
Great catch.
Quoted 4 lines
After we get a lockless ringbuffer that we are happy with, my next series to integrate the buffer into printk will again use the
sprint_rbsolution to avoid the issue discussed in this thread. Perhaps it would be best to continue this discussion after I've posted that series.
We should keep it in head. But I fully agree with postponing the discussion.
I personally think that this is a corner case. I would start with a simple vscprintf(NULL, ...) and vscprintf(reserved_buf, ...) approach. We could always make it more complex when it causes real life problems.
If the data might change under the hood then we have bigger problems. For example, there might be a race when the trailing "\0" has not been written yet.
Best Regards,
Petr
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
On (06/26/19 09:47), Petr Mladek wrote:
[..]
Quoted 3 lines
If the data might change under the hood then we have bigger problems. For example, there might be a race when the trailing "\0" has not been written yet.
Current printk would not handle such cases. I'm only talking about transition from one consistent state to another, when
sprintf(NULL, ptr) == A && sprintf(buf, ptr) != A
Wether it's a corner case or not is entirely unclear to me but I probably would not call it "an impossible scenario".
-ss
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 10 lines · John Ogness
Quoted 9 lines
In
vprintk_emit(), are we going to always reserve 1024-byte records, since we don't know the size in advance, e.g.printk("%pS %s\n", regs->ip, current->name) prb_reserve(&e, &rb, ????);or are we going to run
vscnprintf()on a NULL buffer first, then reserve the exactly required number of bytes and afterwards vscnprintf(s) ->prb_commit(&e)?
Quoted 7 lines
(As suggested by Petr) I want to use
vscnprintf()on a NULL buffer. However, a NULL buffer is not sufficient because things like the loglevel are sometimes added via %s (for example, in/dev/kmsg). So rather than a NULL buffer, I would use a small buffer on the stack (large enough to store loglevel/cont information). This way we can usevscnprintf()to get the exact size _and_printk_get_level()will see enough of the formatted string to parse what it needs.
OK. I guess this should work except for the cases when we want to printk that we are running out of stack :)
More seriously, tho, sometimes messages come with dictionaries of key/value pairs. I don't think we impose any strict limits on the number of key/value pair or on the overall size of the dictionary each record can have (up to a single PAGE, I'd guess. I really need to check printk code). Finding a sufficiently large buffer size might be a bit of a task.
Quoted 9 lines
Quoted 7 lines
I'm asking this because, well, if the most common usage pattern (
printk->prb_reserve) will always reserve fixed size records (aka data blocks), then you _probably_ (??) can drop the 'variable size records' requirement from prb design and start looking at records (aka data blocks) as fixed sized chunks of bytes, which are always located at fixed offsets.The average printk message size is well under 128 bytes.
Do you also count in dictionary of properties (key/value pairs) which records can carry?
For printks from core kernel 128 bytes would be a good estimation, for dev_printk() and so on - I'm not exactly sure.
cat /dev/kmsg
This one, for instance, is a single logbuf record
6,560,2470340,-;hid-generic 0003:093A:2510.0001: input,hidraw0: USB HID v1.11 Mouse [PixArt USB Optical Mouse] on usb-0000:00:14.0-3/input0
SUBSYSTEM=hid
DEVICE=+hid:0003:093A:2510.0001
I suspect that it's larger than 128 bytes.
Quoted 1 line
It would be quite wasteful to always reserve 1K blocks.
Agreed.
-ss
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 7 lines · John Ogness
+/**
+ * structprb_descr- A descriptor representing an entry in the ringbuffer.
+ * @seq: The sequence number of the entry.
+ * @id: The descriptor id.
+ * The location of the descriptor within the descriptor array can be
+ * determined from this value.
+ * @data: The logical position of the data for this entry.
Quoted 8 lines
+ * The location of the beginning of the data within the data array
+ * can be determined from this value.
+ * @data_next: The logical position of the data next to this entry.
+ * This is used to determine the length of the data as well as
+ * identify where the next data begins.
+ * @next: The id of the next (newer) descriptor in the linked list.
+ * A value of EOL means it is the last descriptor in the list.
+ *
For the entire patch; can you please vertically align those descriptions? This is unreadable. Also, add some whitespace, to aid with reading, something like do:
* struct prb_descr - A descriptor representing an entry in the ringbuffer. *
* @seq: The sequence number of the entry.
*
* @id: The descriptor id. * The location of the descriptor within the descriptor * array can be determined from this value. * * @data: The logical position of the data for this entry. The * location of the beginning of the data within the data * array can be determined from this value. * * @data_next: The logical position of the data next to this entry. * This is used to determine the length of the data as well as * identify where the next data begins. * * @next: The id of the next (newer) descriptor in the linked list. * A value of EOL means it is the last descriptor in the * list.
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 24 lines · Peter Zijlstra
Quoted 7 lines
+/**
+ * structprb_descr- A descriptor representing an entry in the ringbuffer.
+ * @seq: The sequence number of the entry.
+ * @id: The descriptor id.
+ * The location of the descriptor within the descriptor array can be
+ * determined from this value.
+ * @data: The logical position of the data for this entry.Quoted 8 lines
+ * The location of the beginning of the data within the data array
+ * can be determined from this value.
+ * @data_next: The logical position of the data next to this entry.
+ * This is used to determine the length of the data as well as
+ * identify where the next data begins.
+ * @next: The id of the next (newer) descriptor in the linked list.
+ * A value of EOL means it is the last descriptor in the list.
+ *For the entire patch; can you please vertically align those descriptions? This is unreadable. Also, add some whitespace, to aid with reading, something like do:
* struct
prb_descr- A descriptor representing an entry in the ringbuffer. *
* @seq: The sequence number of the entry.
*
Quoted 15 lines
* @id: The descriptor id. * The location of the descriptor within the descriptor * array can be determined from this value. * * @data: The logical position of the data for this entry. The * location of the beginning of the data within the data * array can be determined from this value. * * @data_next: The logical position of the data next to this entry. * This is used to determine the length of the data as well as * identify where the next data begins. * * @next: The id of the next (newer) descriptor in the linked list. * A value of EOL means it is the last descriptor in the * list.
OK. Thanks for taking the time to format an example.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 2 lines · John Ogness
+/**
+ * DOC: memory barriers
What's up with that 'DOC' crap?
Quoted 28 lines
+ *
+ * Writers
+ * -------
+ * The main issue with writers is expiring/invalidating old data blocks in
+ * order to create new data blocks. This is performed in 6 steps that must
+ * be observed in order by all writers to allow cooperation. Here is a list
+ * of the 6 steps and the named acquire/release memory barrier pairs that
+ * are used to synchronized them:
+ *
+ * * old data invalidation (MB1): Pushing rb.data_list.oldest forward.
+ * Necessary for identifying if data has been expired.
+ *
+ * * new data reservation (MB2): Pushing rb.data_list.newest forward.
+ * Necessary for validating data.
+ *
+ * * assign the data block to a descriptor (MB3): Setting data block id to
+ * descriptor id. Necessary for finding the descriptor associated with th
+ * data block.
+ *
+ * * commit data (MB4): Setting data blockdata_next. (Now data block is
+ * valid). Necessary for validating data.
+ *
+ * * make descriptor newest (MB5): Setting rb.descr_list.newest to descriptor.
+ * (Now following new descriptors will be linked to this one.) Necessary for
+ * ensuring the descriptor's next is set to EOL before adding to the list.
+ *
+ * * link descriprtor to previous newest (MB6): Setting the next of the
+ * previous descriptor to this one. Necessary for correctly identifying if
Quoted 8 lines
+ * a descriptor is the only descriptor on the list.
+ *
+ * Readers
+ * -------
+ * Readers only make ofsmb_rmb()to ensure that certain critical load
+ * operations are performed in an order that allows readers to evaluate if
+ * the data they read is really valid.
+ */
This isn't really helping much I feel. It doesn't begin to describe the ordering. But maybe the code makes more sense.
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 4 lines · Peter Zijlstra
Quoted 2 lines
+/**
+ * DOC: memory barriersWhat's up with that 'DOC' crap?
The separate documentation in Documentation/core-api/printk-ringbuffer.rst references this so it automatically shows up in the kernel docs. An external reference requires the DOC keyword.
Maybe the memory barrier descriptions do not belong in the kernel docs?
Quoted 37 lines
Quoted 28 lines
+ *
+ * Writers
+ * -------
+ * The main issue with writers is expiring/invalidating old data blocks in
+ * order to create new data blocks. This is performed in 6 steps that must
+ * be observed in order by all writers to allow cooperation. Here is a list
+ * of the 6 steps and the named acquire/release memory barrier pairs that
+ * are used to synchronized them:
+ *
+ * * old data invalidation (MB1): Pushing rb.data_list.oldest forward.
+ * Necessary for identifying if data has been expired.
+ *
+ * * new data reservation (MB2): Pushing rb.data_list.newest forward.
+ * Necessary for validating data.
+ *
+ * * assign the data block to a descriptor (MB3): Setting data block id to
+ * descriptor id. Necessary for finding the descriptor associated with th
+ * data block.
+ *
+ * * commit data (MB4): Setting data blockdata_next. (Now data block is
+ * valid). Necessary for validating data.
+ *
+ * * make descriptor newest (MB5): Setting rb.descr_list.newest to descriptor.
+ * (Now following new descriptors will be linked to this one.) Necessary for
+ * ensuring the descriptor's next is set to EOL before adding to the list.
+ *
+ * * link descriprtor to previous newest (MB6): Setting the next of the
+ * previous descriptor to this one. Necessary for correctly identifying ifQuoted 8 lines
+ * a descriptor is the only descriptor on the list.
+ *
+ * Readers
+ * -------
+ * Readers only make ofsmb_rmb()to ensure that certain critical load
+ * operations are performed in an order that allows readers to evaluate if
+ * the data they read is really valid.
+ */
Quoted 2 lines
This isn't really helping much I feel. It doesn't begin to describe the ordering. But maybe the code makes more sense.
Sorry. I really have no feel about what (or how) exactly I should document the memory barriers. I think the above comments make sense when someone understands the details of the implementation. But perhaps it should describe things such that someone without knowledge of the implementation would understand what the memory barriers are for? That would significantly increase the amount of text as I would have to basically explain the implementation.
I would appreciate it if you could point out a source file that documents its memory barriers the way you would like to see these memory barriers documented.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 3 lines
I would appreciate it if you could point out a source file that documents its memory barriers the way you would like to see these memory barriers documented.
IMO, you could find some inspiration by looking at the memory barriers comments from:
kernel/sched/core.c:try_to_wake_up()
include/linux/wait.h:waitqueue_active()
kernel/futex.c [header _and inline annotations]
I'll detail a single example here, and then conclude with some general guidelines:
---
[from kernel/sched/rt.c]
static inline void rt_set_overload(struct rq *rq)
{
if (!rq->online)
return;
cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
/*
* Make sure the mask is visible before we set
* the overload count. That is checked to determine
* if we should look at the mask. It would be a shame
* if we looked at the mask, but the mask was not
* updated yet.
*
* Matched by the barrier in pull_rt_task().
*/
smp_wmb();
atomic_inc(&rq->rd->rto_count);
}static void pull_rt_task(struct rq *this_rq)
{
int this_cpu = this_rq->cpu, cpu;
bool resched = false;
struct task_struct *p;
struct rq *src_rq;
int rt_overload_count = rt_overloaded(this_rq);
if (likely(!rt_overload_count))
return;
/*
* Match the barrier from rt_set_overloaded; this guarantees that if we
* see overloaded we must also see the rto_mask bit.
*/
smp_rmb();
/* If we are the only overloaded CPU do nothing */
if (rt_overload_count == 1 &&
cpumask_test_cpu(this_rq->cpu, this_rq->rd->rto_mask))
return;
[...]}
---
Notice that the comments provide the following information: for _each_ memory barrier primitive,
1) the _memory accesses_ being ordered
the store to ->rto_mask and the store to ->rto_count for the smp_wmb()
the load from ->rto_count and the from ->rto_mask for the smp_rmb() 2) the _matching barrier_ (and its location)
3) an informal description of the _underlying guarantee(s)_ (c.f., "if we see overloaded we must also see the rto_mask bit").
One can provide this information by embedding some snippet/pseudo-code in its comments as illustrated in the examples pointed out above.
I'd suggest to _not be stingy with memory barriers explanations: this eases/makes it possible the review itself as well as future changes or fixes to the implementation.
FWIW (and as anticipated time ago in a private email), when I see code like this I tend to look elsewhere... ;-/
Thanks,
Andrea
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 76 lines · Andrea Parri
Quoted 3 lines
I would appreciate it if you could point out a source file that documents its memory barriers the way you would like to see these memory barriers documented.
IMO, you could find some inspiration by looking at the memory barriers comments from:
kernel/sched/core.c:try_to_wake_up()
include/linux/wait.h:waitqueue_active()
kernel/futex.c[header_andinline annotations]I'll detail a single example here, and then conclude with some general guidelines:
---
[fromkernel/sched/rt.c]static inline void
rt_set_overload(struct rq *rq){ if (!rq->online) return; cpumask_set_cpu(rq->cpu, rq->rd->rto_mask); /* * Make sure the mask is visible before we set * the overload count. That is checked to determine * if we should look at the mask. It would be a shame * if we looked at the mask, but the mask was not * updated yet. * * Matched by the barrier in pull_rt_task(). */ smp_wmb(); atomic_inc(&rq->rd->rto_count); }static void
pull_rt_task(struct rq *this_rq){ int this_cpu = this_rq->cpu, cpu; bool resched = false; struct task_struct *p; struct rq *src_rq; int rt_overload_count = rt_overloaded(this_rq); if (likely(!rt_overload_count)) return; /* * Match the barrier from rt_set_overloaded; this guarantees that if we * see overloaded we must also see the rto_mask bit. */ smp_rmb(); /* If we are the only overloaded CPU do nothing */ if (rt_overload_count == 1 && cpumask_test_cpu(this_rq->cpu, this_rq->rd->rto_mask)) return; [...]}
---Notice that the comments provide the following information: for _each_ memory barrier primitive,
1) the
_memoryaccesses_being orderedthe store to ->rto_mask and the store to ->rto_count for the smp_wmb() the load from ->rto_count and the from ->rto_mask for the smp_rmb()2) the
_matchingbarrier_(and its location)3) an informal description of the
_underlyingguarantee(s)_ (c.f., "if we see overloaded we must also see therto_maskbit").
Quoted 6 lines
One can provide this information by embedding some snippet/pseudo-code in its comments as illustrated in the examples pointed out above.
I'd suggest to
_notbe stingy with memory barriers explanations: this eases/makes it possible the review itself as well as future changes or fixes to the implementation.
Thank you for the specific examples and explanations. I need to frame your email and hang it next to my monitor for reference.
Quoted 2 lines
FWIW (and as anticipated time ago in a private email), when I see code like this I tend to look elsewhere... ;-/
Do you really mean "code" or are you just referring to "code comments"? If you really mean code, then I'd appreciate some feedback about what should change.
Your private email helped me a great deal. The memory barrier work in v2 is vastly superior to v1, even if it still crap in your eyes. I appreciate you continuing to support me on this.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 6 lines
Quoted 2 lines
FWIW (and as anticipated time ago in a private email), when I see code like this I tend to look elsewhere... ;-/
Do you really mean "code" or are you just referring to "code comments"? If you really mean code, then I'd appreciate some feedback about what should change.
I really just meant "uncommented code". ;-) I do plan to read your:
https://lkml.kernel.org/r/[email protected]
(and the code it's referring to) with due calm in the following days. Thank you in advance for these remarks.
[Trying to address your question about herd7,]
A list of supported primitives is available from:
tools/memory-model/linux-kernel.def (left column)
This includes cmpxchg() (and its variants: _relaxed(), _acquire() and _release()), however, herd7 can currently only parse statements like:
loc_var = cmpxchg(addr, old, new);
(and it will complain loudly without that "loc_var = " part...); this is something that could be improved, or at least it seems this way...
A similar consideration holds for all the value-returning primitives.
Thanks,
Andrea
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 4 lines · John Ogness
Quoted 3 lines · Peter Zijlstra
Quoted 2 lines
+/**
+ * DOC: memory barriers
Quoted 8 lines
Quoted 1 line
What's up with that 'DOC' crap?
The separate documentation in
Documentation/core-api/printk-ringbuffer.rstreferences this so it automatically shows up in the kernel docs. An external reference requires the DOC keyword.Maybe the memory barrier descriptions do not belong in the kernel docs?
So i'm biased; I don't much care for Documentation/ -- code should be readable and have sufficient comments; I hate rst and I think that anything that detracts from reading code comments in an editor is pure evil.
Personally, I've stopped using /** comments, live is better now.
YMMV
Quoted 11 lines
Sorry. I really have no feel about what (or how) exactly I should document the memory barriers. I think the above comments make sense when someone understands the details of the implementation. But perhaps it should describe things such that someone without knowledge of the implementation would understand what the memory barriers are for? That would significantly increase the amount of text as I would have to basically explain the implementation.
I would appreciate it if you could point out a source file that documents its memory barriers the way you would like to see these memory barriers documented.
Yeah, I was going to read the implementation and make suggestions; just haven't gotten there yet.
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John Ognesslib/printk_ringbuffer.c line 200
Quoted 2 lines · John Ogness
lib/printk_ringbuffer.c new file +2
-0+#define DATAARRAY_SIZE (rb) (1 << rb->data_array_size_bits) +#define DATAARRAY_SIZE_BITMASK (rb) (DATAARRAY_SIZE(rb) - 1)
*phew* no comments on those..
I think the kernel typically uses _MASK instead of _BITMASK for this though.
Quoted 19 lines
lib/printk_ringbuffer.c new file +19
-0+/** +* DATA_INDEX() - Determine the data array index from logical position. +* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +*/ +#define DATA_INDEX (rb, lpos) (lpos & DATAARRAY_SIZE_BITMASK(rb)) + +/** +* DATA_WRAPS() - Determine how many times the data array has wrapped. +* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +* +* The number of wraps is useful when determining if one logical position +* is overtaking the data array index another logical position. +*/ +#define DATA_WRAPS (rb, lpos) (lpos >> rb->data_array_size_bits) + +/** +* DATA_THIS_WRAP_START_LPOS() - Get the position at the start of the wrap.
lib/printk_ringbuffer.c line 230
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +* +* Given a logical position, return the logical position if backed up to the +* beginning (data array index 0) of the current wrap. This is used when a +* data block wraps and therefore needs to begin at the beginning of the data +* array (for the next wrap). +*/ +#define DATA_THIS_WRAP_START_LPOS (rb, lpos) \ + (DATA_WRAPS(rb, lpos) << rb->data_array_size_bits)
That's more easily written as: ((lpos) & ~MASK(rb))
lib/printk_ringbuffer.c line 234
Quoted 4 lines
lib/printk_ringbuffer.c new file +4
-0+ +#define DATA_ALIGN sizeof(long) +#define DATA_ALIGN_SIZE (sz) \ + ((sz + (DATA_ALIGN - 1)) & ~(DATA_ALIGN - 1))
We have ALIGN() for that
lib/printk_ringbuffer.c line 236
Quoted 2 lines
lib/printk_ringbuffer.c new file +2
-0+ +#define DESCR_COUNT_BITMASK (rb) (rb->descr_max_count - 1)
I think the kernel typically uses 'DESC' as shorthand for Descriptor. Idem on the MASK vs BITMASK thing.
lib/printk_ringbuffer.c line 246
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+ +/** +* DESCR_INDEX() - Determine the descriptor array index from the id. +* @rb: The associated ringbuffer. +* @id: The descriptor id. +*/ +#define DESCR_INDEX (rb, id) (id & DESCR_COUNT_BITMASK(rb)) + +#define TO_DATABLOCK (rb, lpos) \ + ((struct prb_datablock *)&rb->data_array[DATA_INDEX(rb, lpos)])
If I were paranoid, I'd point out that this evaluates @rb twice, and doesn't have the macro arguments in parens.
Quoted 20 lines
lib/printk_ringbuffer.c new file +20
-0+#define TO_DESCR (rb, id) \ + (&rb->descr_array[DESCR_INDEX(rb, id)]) + +/** +* data_valid() - Check if a data block is valid. +* @rb: The ringbuffer containing the data. +* @oldest_data: The oldest data logical position. +* @newest_data: The newest data logical position. +* @data: The logical position for the data block to check. +* @data_next: The logical position for the data block next to this one. +* This value is used to identify the end of the data block. +* +* A data block is considered valid if it satisfies the two conditions: +* +* * oldest_data <= data < data_next <= newest_data +* * oldest_data is at most exactly 1 wrap behind newest_data +* +* Return: true if the specified data block is valid. +*/ +static inline bool data_valid(struct printk_ringbuffer *rb,
lib/printk_ringbuffer.c line 276
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+unsigned long oldest_data, + unsigned long newest_data, + unsigned long data, unsigned long data_next) + +{ + return ((data - oldest_data) < DATAARRAY_SIZE(rb) && + data_next != data && + (data_next - data) < DATAARRAY_SIZE(rb) && + (newest_data - data_next) < DATAARRAY_SIZE(rb) && + (newest_data - oldest_data) <= DATAARRAY_SIZE(rb));
unsigned long size = DATA_SIZE(rb); /* oldest_data <= data */ if (data - oldest_data >= size); return false; /* data_next < data */ if (data_next == data) return false /* data_next <= newest_data */ if (newest_data - data_next >= size) return false; /* 1 wrap */ if (newest_data - oldest_data >= size) return false; return true;
Quoted 28 lines
lib/printk_ringbuffer.c new file +28
-0+} + +/** +* add_descr_list() - Add a descriptor to the descriptor list. +* @e: An entry that has already reserved data. +* +* The provided entry contains a pointer to a descriptor that has already +* been reserved for this entry. However, the reserved descriptor is not +* yet on the list. Add this descriptor as the newest item. +* +* A descriptor is added in two steps. The first step is to make this +* descriptor the newest. The second step is to update the "next" field of +* the former newest item to point to this item. +*/ +static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ + do { + /* MB5: synchronize add descr */ + newest_id = smp_load_acquire(&l->newest); + newest_d = TO_DESCR(rb, newest_id); +
lib/printk_ringbuffer.c line 314
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+if (newest_id ==EOL ) +WRITE_ONCE (d->seq,1 ); +else +WRITE_ONCE (d->seq,READ_ONCE (newest_d->seq) +1 ); +/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id);
What does this pair with? I find ->newest usage in:
- later this function with an MB6 comment
- remove_oldest_descr() with no comment
- expire_oldest_data() with an MB2 comment
- get_new_lpos() with no comment
- data_reserve() with an MB2 comment
- prb_iter_next_valid_entry() with no comment (and the smp_rmb()s have no clear comments either).
In short; I've no frigging clue and I might as well just delete all these comments and reverse engineer :-(
lib/printk_ringbuffer.c line 320
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+ +if (unlikely (newest_id ==EOL )) { +/* no previous newest means we *are* the list, set oldest */ + +/* +* MB UNPAIRED
That's a bug, MB must always be paired.
lib/printk_ringbuffer.c line 331
Quoted 11 lines
lib/printk_ringbuffer.c new file +11
-0+* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&l->oldest,EOL , e->id) !=EOL ); + }else { +/* link to previous chain */ + +/* +* MB6: synchronize link descr +* +* In particular: Force cmpxchg _after_ cmpxchg on newest.
But why... and who cares.
Quoted 5 lines
lib/printk_ringbuffer.c new file +5
-0+*/ +WARN_ON_ONCE (cmpxchg_release (&newest_d->next, +EOL , e->id) !=EOL ); + } +}
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Hi Peter,
This is a long response, but we are getting into some fine details about the memory barriers (as well as battling my communication skill level).
Quoted 7 lines · Peter Zijlstra
lib/printk_ringbuffer.c line 200
Quoted 2 lines
lib/printk_ringbuffer.c new file +2
-0+#define DATAARRAY_SIZE (rb) (1 << rb->data_array_size_bits) +#define DATAARRAY_SIZE_BITMASK (rb) (DATAARRAY_SIZE(rb) - 1)*phew* no comments on those..
I think the kernel typically uses
_MASKinstead of_BITMASKfor this though.
Yes, you are right.
Quoted 23 lines
Quoted 23 lines
lib/printk_ringbuffer.c new file +23
-0+/** +* DATA_INDEX() - Determine the data array index from logical position. +* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +*/ +#define DATA_INDEX (rb, lpos) (lpos & DATAARRAY_SIZE_BITMASK(rb)) + +/** +* DATA_WRAPS() - Determine how many times the data array has wrapped. +* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +* +* The number of wraps is useful when determining if one logical position +* is overtaking the data array index another logical position. +*/ +#define DATA_WRAPS (rb, lpos) (lpos >> rb->data_array_size_bits) + +/** +* DATA_THIS_WRAP_START_LPOS() - Get the position at the start of the wrap. +* @rb: The associated ringbuffer. +* @lpos: The logical position (data/data_next). +* +* Given a logical position, return the logical position if backed up to the
Quoted 8 lines
lib/printk_ringbuffer.c line 230
Quoted 6 lines
+ * beginning (data array index 0) of the current wrap. This is used when a
+ * data block wraps and therefore needs to begin at the beginning of the data
+ * array (for the next wrap).
+ */lib/printk_ringbuffer.c new file +2
-0+#define DATA_THIS_WRAP_START_LPOS (rb, lpos) \ + (DATA_WRAPS(rb, lpos) << rb->data_array_size_bits)That's more easily written as: ((lpos) & ~MASK(rb))
Agreed.
Quoted 6 lines
lib/printk_ringbuffer.c line 234
Quoted 4 lines
lib/printk_ringbuffer.c new file +4
-0+ +#define DATA_ALIGN sizeof(long) +#define DATA_ALIGN_SIZE (sz) \ + ((sz + (DATA_ALIGN - 1)) & ~(DATA_ALIGN - 1))We have
ALIGN()for that
OK.
Quoted 5 lines
lib/printk_ringbuffer.c line 236
Quoted 2 lines
lib/printk_ringbuffer.c new file +2
-0+ +#define DESCR_COUNT_BITMASK (rb) (rb->descr_max_count - 1)I think the kernel typically uses 'DESC' as shorthand for Descriptor. Idem on the MASK vs BITMASK thing.
Yes, you are correct.
Quoted 5 lines
Quoted 5 lines
lib/printk_ringbuffer.c new file +5
-0+ +/** +* DESCR_INDEX() - Determine the descriptor array index from the id. +* @rb: The associated ringbuffer. +* @id: The descriptor id.
Quoted 8 lines
lib/printk_ringbuffer.c line 246
Quoted 5 lines
+ */
lib/printk_ringbuffer.c new file +4
-0+#define DESCR_INDEX (rb, id) (id & DESCR_COUNT_BITMASK(rb)) + +#define TO_DATABLOCK (rb, lpos) \ + ((struct prb_datablock *)&rb->data_array[DATA_INDEX(rb, lpos)])If I were paranoid, I'd point out that this evaluates @rb twice, and doesn't have the macro arguments in parens.
There are several other macros that also should have some parens for the arguments. Thanks for pointing that out.
As for the double evaluation, I'm not sure what should be done instead. It is a convenience macro. I could split it into 2 macros and have the caller always call the 2 macros. Is that desirable?
Quoted 42 lines
Quoted 20 lines
lib/printk_ringbuffer.c new file +20
-0+#define TO_DESCR (rb, id) \ + (&rb->descr_array[DESCR_INDEX(rb, id)]) + +/** +* data_valid() - Check if a data block is valid. +* @rb: The ringbuffer containing the data. +* @oldest_data: The oldest data logical position. +* @newest_data: The newest data logical position. +* @data: The logical position for the data block to check. +* @data_next: The logical position for the data block next to this one. +* This value is used to identify the end of the data block. +* +* A data block is considered valid if it satisfies the two conditions: +* +* * oldest_data <= data < data_next <= newest_data +* * oldest_data is at most exactly 1 wrap behind newest_data +* +* Return: true if the specified data block is valid. +*/ +static inline bool data_valid(struct printk_ringbuffer *rb,lib/printk_ringbuffer.c line 276
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+unsigned long oldest_data, + unsigned long newest_data, + unsigned long data, unsigned long data_next) + +{ + return ((data - oldest_data) < DATAARRAY_SIZE(rb) && + data_next != data && + (data_next - data) < DATAARRAY_SIZE(rb) && + (newest_data - data_next) < DATAARRAY_SIZE(rb) && + (newest_data - oldest_data) <= DATAARRAY_SIZE(rb));unsigned long size = DATA_SIZE(rb); /* oldest_data <= data */ if (data - oldest_data >= size); return false; /* data_next < data */ if (data_next == data) return false /* data_next <= newest_data */
Quoted 8 lines
if (newest_data - data_next >= size) return false; /* 1 wrap */ if (newest_data - oldest_data >= size) return false; return true;
Ha! That was my original implementation, but I changed it because I figured there would be feedback telling me to put everything into a single expression for compiler optimization. I am happy to use your suggestion instead.
Quoted 32 lines
Quoted 32 lines
lib/printk_ringbuffer.c new file +32
-0+} + +/** +* add_descr_list() - Add a descriptor to the descriptor list. +* @e: An entry that has already reserved data. +* +* The provided entry contains a pointer to a descriptor that has already +* been reserved for this entry. However, the reserved descriptor is not +* yet on the list. Add this descriptor as the newest item. +* +* A descriptor is added in two steps. The first step is to make this +* descriptor the newest. The second step is to update the "next" field of +* the former newest item to point to this item. +*/ +static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ + do { + /* MB5: synchronize add descr */ + newest_id = smp_load_acquire(&l->newest); + newest_d = TO_DESCR(rb, newest_id); + + if (newest_id == EOL) + WRITE_ONCE(d->seq, 1); + else + WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);
Quoted 8 lines
lib/printk_ringbuffer.c line 314
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id);What does this pair with? I find ->newest usage in:
It is pairing with the smp_load_acquire() at the beginning of this loop (also labeled MB5) that is running simultaneously on another CPU. I am avoiding a possible situation that a new descriptor is added but the store of "next" from the previous descriptor is not yet visible and thus the cmpxchg following will fail, which is not allowed. (Note that "next" is set to EOL shortly before this function is called.)
The litmus test for this is:
P0(int *newest, int *d_next)
{
// set descr->next to EOL (terminates list)
WRITE_ONCE(*d_next, 1);
// set descr as newest
smp_store_release(*newest, 1);
}P1(int *newest, int *d_next)
{
int local_newest;
int local_next;
// get newest descriptor
local_newest = smp_load_acquire(*newest);
// a new descriptor is set as the newest
// (not relevant here)
// read descr->next of previous newest
// (must be EOL!)
local_next = READ_ONCE(*d_next);
}exists (1:local_newest=1 /\ 1:local_next=0)
Quoted 10 lines
- later this function with an MB6 comment
-remove_oldest_descr()with no comment
-expire_oldest_data()with an MB2 comment
-get_new_lpos()with no comment
-data_reserve()with an MB2 comment
-prb_iter_next_valid_entry()with no comment (and the smp_rmb()s have no clear comments either).In short; I've no frigging clue and I might as well just delete all these comments and reverse engineer :-(
OK. I understand that I haved failed horribly at commenting the barriers. Perhaps I should submit a v3 with only new memory barrier comments so that you can better understand and (hopefully) Andrea would also be able to take a look?
Quoted 8 lines
lib/printk_ringbuffer.c line 320
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+ +if (unlikely (newest_id ==EOL )) { +/* no previous newest means we *are* the list, set oldest */ + +/* +* MB UNPAIRED That's a bug, MB must always be paired.
Well, it "pairs" with the smp_rmb() of the readers, but I didn't think that counts as a pair. That's why I wrote unpaired. The litmus test is:
P0(int *x, int *y)
{
WRITE_ONCE(*x, 1);
smp_store_release(y, 1);
}P1(int *x, int *y)
{
int rx;
int ry;
ry = READ_ONCE(*y);
smp_rmb();
rx = READ_ONCE(*x);
}exists (1:rx=0 /\ 1:ry=1)
The readers rely on the store_releases "pairing" with the smp_rmb() so that the readers see things in a sane order.
For this particular case, I could change the READ_ONCE(rb->descr_list.oldest) in iter_peek_next_id() and prb_iter_next_valid_entry() to smp_load_acquires and then there would be an official (and correct) pairing. But since the smp_rmb's are needed anyway (for other fields), it really isn't necessary.
Quoted 5 lines
Quoted 5 lines
lib/printk_ringbuffer.c new file +5
-0+* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&l->oldest,EOL , e->id) !=EOL ); + }else {
Quoted 8 lines
lib/printk_ringbuffer.c line 331
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+/* link to previous chain */ + +/* +* MB6: synchronize link descr +* +* In particular: Force cmpxchg _after_ cmpxchg on newest. But why... and who cares.
The comments on the matching MB6 and in the MB6 documentation are more precise about this. But I guess they aren't clear enough either. :-/
It is important to understand that once the ringbuffer is full (which is quite common for the printk buffer) then old data starts to be expired and descriptors recycled. This is really where memory barriers become critical.
In this situation, it becomes normal that a writer adding a new record must first expire/recycle and old record. The writer moving the oldest descriptor pointer forward is also the one that is re-initializing the oldest descriptor and re-adding it to end of the reader-visible list.
As described in the documentation, a descriptor can not be removed from the list if it is the only one on the list. This is verified by checking if it's "next" is EOL and it is the "oldest". However, because descriptors are recycled (and thus the next set to EOL) and oldest can be moving (by writers on other CPUs), the check for this case must be taken into careful consideration, which is where MB6 comes in.
If a writer changes "next" then that writer previously changed "oldest". And when another writer checks "next" it needs to be guaranteed that it also sees the updated "oldest".
The litmus test for this is:
P0(int *oldest, int *prev_newest_next)
{
// remove the oldest descriptor
WRITE_ONCE(*oldest, 1);
// set the previous newest next to this descriptor
smp_store_release(*prev_newest_next, 1);
}P1(int *oldest, int *prev_newest_next)
{
int local_oldest;
int local_next;
// get next of oldest descriptor
// (assuming prev_newest_next is now the oldest)
local_next = smp_load_acquire(*prev_newest_next);
// read the oldest
local_oldest = READ_ONCE(*oldest);
}exists (1:local_next=1 /\ 1:local_oldest=0)
Quoted 5 lines
lib/printk_ringbuffer.c line 336
Quoted 5 lines
lib/printk_ringbuffer.c new file +5
-0+*/ +WARN_ON_ONCE (cmpxchg_release (&newest_d->next, +EOL , e->id) !=EOL ); + } +}
So this email has a lot of explanations. My first question is: do my explanations make any sense to you? If yes, then I need to figure out how to massively condense them to something that is appropriate for a memory barrier comment. If no... I guess I need to find someone to translate my madness into something that is understandable to the rest of the world.
John Ogness
P.S. Is it correct that git HEAD herd7 does not support cmpxchg? For my litmus tests I use stores and loads instead, which works and is correct, but makes it more difficult for someone to match the test to the actual code.
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 4 lines · John Ogness
Hi Peter,
This is a long response, but we are getting into some fine details about the memory barriers (as well as battling my communication skill level).
So I'm going to reply piecewise to this... so not such long emails, but more of them.
Quoted 62 lines · Peter Zijlstra
Quoted 18 lines
Quoted 18 lines
lib/printk_ringbuffer.c new file +18
-0+static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ + do { + /* MB5: synchronize add descr */ + newest_id = smp_load_acquire(&l->newest); + newest_d = TO_DESCR(rb, newest_id); + + if (newest_id == EOL) + WRITE_ONCE(d->seq, 1); + else + WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);Quoted 8 lines
lib/printk_ringbuffer.c line 314
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id);What does this pair with? I find ->newest usage in:
It is pairing with the
smp_load_acquire()at the beginning of this loop (also labeled MB5) that is running simultaneously on another CPU. I am avoiding a possible situation that a new descriptor is added but the store of "next" from the previous descriptor is not yet visible and thus the cmpxchg following will fail, which is not allowed. (Note that "next" is set to EOL shortly before this function is called.)The litmus test for this is:
P0(int *newest, int *d_next){ // set descr->next to EOL (terminates list) WRITE_ONCE(*d_next, 1); // set descr as newest smp_store_release(*newest, 1); }
P1(int *newest, int *d_next){ int local_newest; int local_next; // get newest descriptor local_newest = smp_load_acquire(*newest); // a new descriptor is set as the newest // (not relevant here) // read descr->next of previous newest // (must be EOL!) local_next = READ_ONCE(*d_next); }
Quoted 1 line
exists (1:local_newest=1 /\ 1:local_next=0)
I'm having trouble connecting your P1's READ_ONCE() to the actual code.
You say that is in the same function, but I cannot find a LOAD there that would care about the ACQUIRE.
Afaict prb_list is a list head not a list node (calling it just _list is confusing at best).
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
struct lqueue_head {
struct lqueue_node *head, *tail;
};
struct lqueue_node {
struct lqueue_node *next;
};
void lqueue_push(struct lqueue_head *h, struct lqueue_node *n)
{
struct lqueue_node *prev;
n->next = NULL;
/*
* xchg() implies RELEASE; and thereby ensures @n is
* complete before getting published.
*/
prev = xchg(&h->head, n);
/*
* xchg() implies ACQUIRE; and thereby ensures @tail is
* written after @head, see lqueue_pop()'s smp_rmb().
*/
if (prev)
WRITE_ONCE(prev->next, n);
else
WRITE_ONCE(h->tail, n);
}
struct lqueue_node *lqueue_pop(struct lqueue_head *h)
{
struct lqueue_node *head, *tail, *next;
do {
tail = READ_ONCE(h->tail);
/* If the list is empty, nothing to remove. */
if (!tail)
return NULL;
/*
* If we see @tail, we must then also see @head.
* Pairs with the xchg() in lqueue_push(),
* ensure no false positive on the singleton
* test below.
*/
smp_rmb();
head = READ_ONCE(h->head);
/* If there is but one item; fail to remove. */
if (head == tail)
return NULL;
next = smp_cond_load_relaxed(&tail->next, VAL);
} while (cmpxchg(h->tail, tail, next) != tail);
return tail;
}Now, you appear to be using desc_ids instead of pointers, but since you're not using the actual wrap value; I don't see the benefit of using those IDs over straight pointers.
That is, unless I've overlooked some subtle ABA issue, but then, your code doesn't seem to mention that, and I think we're good because if we re-use an entry, it can never get back in the same location, since we never allow an empty list (might also be fixable, haven't tought too hard on this).
That said, the above has cmpxchg() vs WRITE_ONCE() and is therefore not safe on a number of our architectures. We can either not care about performance and use xchg() for the ->tail store, or use atomic_long_t and suffer ugly casting.
But the above is, IMO, a more useful and readable abstraction. Let me continue in another email (probably tomorrow).
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 39 lines · Peter Zijlstra
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
struct lqueue_head { struct lqueue_node *head, *tail; }; struct lqueue_node { struct lqueue_node *next; }; void lqueue_push(struct lqueue_head *h, struct lqueue_node *n) { struct lqueue_node *prev; n->next = NULL; /* * xchg() implies RELEASE; and thereby ensures @n is * complete before getting published. */ prev = xchg(&h->head, n); /* * xchg() implies ACQUIRE; and thereby ensures @tail is * written after @head, see lqueue_pop()'s smp_rmb(). */ if (prev) WRITE_ONCE(prev->next, n); else WRITE_ONCE(h->tail, n); } struct lqueue_node *lqueue_pop(struct lqueue_head *h) { struct lqueue_node *head, *tail, *next; do { tail = READ_ONCE(h->tail); /* If the list is empty, nothing to remove. */
Quoted 8 lines
if (!tail) return NULL; /* * If we see @tail, we must then also see @head. * Pairs with the xchg() in lqueue_push(), * ensure no false positive on the singleton * test below.
or is it false negative?, I'm too tired to think staight. What can happen without the rmb is that the head load can get hoisted over the tail load and then observe a NULL head and a !NULL tail and thus head != tail and we think there's multiple entries on the list and stuff goes wobbly.
Quoted 14 lines
*/ smp_rmb(); head = READ_ONCE(h->head); /* If there is but one item; fail to remove. */ if (head == tail) return NULL; next = smp_cond_load_relaxed(&tail->next, VAL); } while (cmpxchg(h->tail, tail, next) != tail); return tail; }
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
Quoted 3 lines
This is a long response, but we are getting into some fine details about the memory barriers (as well as battling my communication skill level).
So I'm going to reply piecewise to this... so not such long emails, but more of them.
I am not sure if I should wait to respond until you've finished going through the full patch. I will respond to this email and if you would like me to wait on further responses, just let me know. Thanks.
Quoted 62 lines
Quoted 62 lines
Quoted 18 lines
Quoted 18 lines
lib/printk_ringbuffer.c new file +18
-0+static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ + do { + /* MB5: synchronize add descr */ + newest_id = smp_load_acquire(&l->newest); + newest_d = TO_DESCR(rb, newest_id); + + if (newest_id == EOL) + WRITE_ONCE(d->seq, 1); + else + WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);Quoted 8 lines
lib/printk_ringbuffer.c line 314
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id);What does this pair with? I find ->newest usage in:
It is pairing with the
smp_load_acquire()at the beginning of this loop (also labeled MB5) that is running simultaneously on another CPU. I am avoiding a possible situation that a new descriptor is added but the store of "next" from the previous descriptor is not yet visible and thus the cmpxchg following will fail, which is not allowed. (Note that "next" is set to EOL shortly before this function is called.)The litmus test for this is:
P0(int *newest, int *d_next){ // set descr->next to EOL (terminates list) WRITE_ONCE(*d_next, 1); // set descr as newest smp_store_release(*newest, 1); }
P1(int *newest, int *d_next){ int local_newest; int local_next; // get newest descriptor local_newest = smp_load_acquire(*newest); // a new descriptor is set as the newest // (not relevant here) // read descr->next of previous newest // (must be EOL!) local_next = READ_ONCE(*d_next); }
Quoted 5 lines
Quoted 1 line
exists (1:local_newest=1 /\ 1:local_next=0)
I'm having trouble connecting your P1's
READ_ONCE()to the actual code. You say that is in the same function, but I cannot find a LOAD there that would care about the ACQUIRE.
P1's READ_ONCE() is the READ part of the cmpxchg a few lines below:
WARN_ON_ONCE(cmpxchg_release(&newest_d->next,
EOL, e->id) != EOL);Note that the cmpxchg is a _release because of MB6 (a different memory barrier pair). But only the READ part of that cmpxchg synchronizes with MB5.
Also note that cmpxchg is used only because of bug checking. If instead it becomes a blind store (such as you suggest below), then it changes to smp_store_release().
While investigating this (and the lack of a LOAD), I realized that the smp_load_acquire() is not needed because @seq is dependent on the load of @newest. I have implemented and tested these changes. I also added setting the list terminator to this function, since all callers would have to do it anyway. Also, I spent a lot of time trying to put in comments that I think are _understandable_ and _acceptable_.
@Peter: I expect they are way too long for you.
@Andrea: Is this starting to become something that you would like to see?
/**
* add_descr_list() - Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
static void add_descr_list(struct prb_reserved_entry *e)
{
struct printk_ringbuffer *rb = e->rb;
struct prb_list *l = &rb->descr_list;
struct prb_descr *d = e->descr;
struct prb_descr *newest_d;
unsigned long newest_id;
WRITE_ONCE(d->next, EOL);
do {
newest_id = READ_ONCE(l->newest); newest_d = TO_DESC(rb, newest_id);
if (newest_id == EOL) {
WRITE_ONCE(d->seq, 1);
} else {
/*
* MB5-read: synchronize setting newest descr *
* context-pair: 2 writers adding a descriptor via
* add_descr_list().
*
* @newest will load before @seq due to a data
* dependency, therefore, the stores of @seq
* and @next from the pairing MB5-write context
* will be visible.
*
* Although @next is not loaded by this context,
* this context must overwrite the stored @next
* value of the pairing MB5-write context. */
WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);
}
/*
* MB5-write: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
* add_descr_list().
*
* Ensure that @next and @seq are stored before @d is
* visible via @newest. The pairing MB5-read context
* must load this @seq value and must overwrite this
* @next value.
*/
} while (cmpxchg_release(&l->newest, newest_id, e->id) != newest_id);
if (unlikely(newest_id == EOL)) {
/*
* MB0-write: synchronize adding first descr *
* context-pair: 1 writer adding the first descriptor via
* add_descr_list(), 1 reader getting the beginning of
* the list via iter_peek_next_id().
*
* This context recently assigned new values for @id,
* @next, @seq. Ensure these are stored before the first
* store to @oldest so that the new values are visible
* to the reader in the pairing MB0-read context. *
* Note: Before this store, the value of @oldest is EOL. */
smp_store_release(&l->oldest, e->id);
} else {
/*
* MB6-write: synchronize linking new descr
*
* context-pair-1: 1 writer adding a descriptor via
* add_descr_list(), 1 writer removing a descriptor via
* remove_oldest_descr().
*
* If this is a recycled descriptor, this context
* recently stored a new @oldest value. Ensure that
* @oldest is stored before storing @next so that
* if the pairing MB6-read context sees a non-EOL
* @next value, it is ensured that it will also see
* an updated @oldest value.
*
* context-pair-2: 1 writer adding a descriptor via
* add_descr_list(), 1 reader iterating the list via
* prb_iter_next_valid_entry().
*
* This context recently assigned new values for @id,
* @next, @seq, @data, @data_next. Ensure these are
* stored before storing @next of the previously
* newest descriptor so that the new values are
* visible to the iterating reader in the pairing
* MB6-read context.
*
* Note: Before this store, the value of @next of the
* previously newest descriptor is EOL.
*/
smp_store_release(&newest_d->next, e->id);
}
}
The smp_rmb() calls in the reader functions are then commented and marked with the appropriate MB0-read and MB6-read labels.
Quoted 2 lines
Afaict
prb_listis a list head not a list node (calling it just_listis confusing at best).
OK.
Quoted 3 lines
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
Yes, but with one important feature: the nodes in the FIFO queue are labeled with ordered sequence numbers. This is important for printk. I talk more about this below.
Quoted 5 lines
struct lqueue_head {
struct lqueue_node *head, *tail;
};
struct lqueue_node {Quoted 8 lines
struct lqueue_node *next;
};
void lqueue_push(struct lqueue_head *h, struct lqueue_node *n)
{
struct lqueue_node *prev;
n->next = NULL;Is this safe? Do all compilers understand that @next must be stored before the xchg() of @head? I would have chosen WRITE_ONCE().
Quoted 5 lines
/* * xchg() implies RELEASE; and thereby ensures @n is * complete before getting published. */ prev = xchg(&h->head, n);
Unfortunately it is not that simple because of sequence numbers. A node must be assigned a sequence number that is +1 of the previous node. This must be done before exchanging the head because immediately after the xchg() on the head, another CPU could then add on to us and expects our sequence number to already be set.
This is why I need cmpxchg() here.
Quoted 6 lines
/* * xchg() implies ACQUIRE; and thereby ensures @tail is * written after @head, see lqueue_pop()'s smp_rmb(). */ if (prev) WRITE_ONCE(prev->next, n);
This needs to be a store_release() so that a reader cannot read @n but the store to @next is not yet visible. The memory barriers of the above xchg() do not apply here because readers never read @head.
Quoted 2 lines
else WRITE_ONCE(h->tail, n);
Ditto, but for the tail node in particular.
Quoted 18 lines
}
struct lqueue_node *lqueue_pop(struct lqueue_head *h)
{
struct lqueue_node *head, *tail, *next;
do {
tail = READ_ONCE(h->tail);
/* If the list is empty, nothing to remove. */
if (!tail)
return NULL;
/*
* If we see @tail, we must then also see @head.
* Pairs with the xchg() in lqueue_push(),
* ensure no false positive on the singleton
* test below.
*/Quoted 8 lines
smp_rmb(); head = READ_ONCE(h->head); /* If there is but one item; fail to remove. */ if (head == tail) return NULL; next = smp_cond_load_relaxed(&tail->next, VAL);
What if a writer is adding a 2nd node to the queue and is interrupted by an NMI directly after the xchg() in lqueue_push()? Then we have:
* head != tail
* tail->next == NULL
If that interrupting NMI calls lqueue_pop(), the NMI will spin forever. The following cmpxchg() is not allowed to happen as long as tail->next is NULL.
This is why I synchronize on @next instead, using (tail && !tail->next) for the singleton test.
Quoted 8 lines
} while (cmpxchg(h->tail, tail, next) != tail); return tail; }Now, you appear to be using
desc_idsinstead of pointers, but since you're not using the actual wrap value; I don't see the benefit of using those IDs over straight pointers.
The documentation mentions that descriptor ids are used to identify pointers to invalid descriptors. This is used by the readers, see iter_peek_next_id() and prb_iter_next_valid_entry().
IDs are used for:
- @next of descriptors on the list
- @id, @id_next in the reader iterator
- @id in the data blocks
If changed to pointers, iterators would need to additionally store @seq values to be able to identifiy if the entry they are pointing to is the entry they expect.
The only advantage I see with pointers is that the ringbuffer could be more useful generally, independent of whether the data is separate or within the nodes or if the nodes are statically or dynamically allocated. That is something worth having, even if it is not printk related.
Are you implicitly requesting me to split the prb_ringbuffer and instead base it on a new "lockless multi-writer multi-reader sequenced FIFO queue" data structure?
Quoted 4 lines
That is, unless I've overlooked some subtle ABA issue, but then, your code doesn't seem to mention that, and I think we're good because if we re-use an entry, it can never get back in the same location, since we never allow an empty list
I do not understand what you mean here. If a reader has a pointer to an entry, the entry behind that pointer can certainly change. But that isn't a problem. The reader will recognize that.
Quoted 1 line
(might also be fixable, haven't tought too hard on this).
:-)
Quoted 4 lines
That said, the above has
cmpxchg()vsWRITE_ONCE()and is therefore not safe on a number of our architectures. We can either not care about performance and usexchg()for the ->tail store, or useatomic_long_tand suffer ugly casting.
cmpxchg_release() vs WRITE_ONCE() is not safe?! Can you point me to documentation about this?
Quoted 2 lines
But the above is, IMO, a more useful and readable abstraction. Let me continue in another email (probably tomorrow).
Thank you for taking the time for this.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 79 lines · John Ogness
Quoted 62 lines · Peter Zijlstra
Quoted 62 lines
Quoted 18 lines
Quoted 18 lines
lib/printk_ringbuffer.c new file +18
-0+static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ + do { + /* MB5: synchronize add descr */ + newest_id = smp_load_acquire(&l->newest); + newest_d = TO_DESCR(rb, newest_id); + + if (newest_id == EOL) + WRITE_ONCE(d->seq, 1); + else + WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);Quoted 8 lines
lib/printk_ringbuffer.c line 314
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id);What does this pair with? I find ->newest usage in:
It is pairing with the
smp_load_acquire()at the beginning of this loop (also labeled MB5) that is running simultaneously on another CPU. I am avoiding a possible situation that a new descriptor is added but the store of "next" from the previous descriptor is not yet visible and thus the cmpxchg following will fail, which is not allowed. (Note that "next" is set to EOL shortly before this function is called.)The litmus test for this is:
P0(int *newest, int *d_next){ // set descr->next to EOL (terminates list) WRITE_ONCE(*d_next, 1); // set descr as newest smp_store_release(*newest, 1); }
P1(int *newest, int *d_next){ int local_newest; int local_next; // get newest descriptor local_newest = smp_load_acquire(*newest); // a new descriptor is set as the newest // (not relevant here) // read descr->next of previous newest // (must be EOL!) local_next = READ_ONCE(*d_next); }Quoted 5 lines
Quoted 1 line
exists (1:local_newest=1 /\ 1:local_next=0)
I'm having trouble connecting your P1's
READ_ONCE()to the actual code. You say that is in the same function, but I cannot find a LOAD there that would care about the ACQUIRE.P1's
READ_ONCE()is the READ part of the cmpxchg a few lines below:WARN_ON_ONCE(cmpxchg_release(&newest_d->next, EOL, e->id) != EOL);Note that the cmpxchg is a
_releasebecause of MB6 (a different memory barrier pair). But only the READ part of that cmpxchg synchronizes with MB5.
Quoted 7 lines
Also note that cmpxchg is used only because of bug checking. If instead it becomes a blind store (such as you suggest below), then it changes to
smp_store_release().While investigating this (and the lack of a LOAD), I realized that the
smp_load_acquire()is not needed because @seq is dependent on the load of @newest.
That!
Quoted 10 lines
I have implemented and tested these changes. I also added setting the list terminator to this function, since all callers would have to do it anyway. Also, I spent a lot of time trying to put in comments that I think are _understandable_ and _acceptable_.
@Peter: I expect they are way too long for you.
@Andrea: Is this starting to become something that you would like to see?
Quoted 14 lines
/**
*add_descr_list()- Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
I still think it might be useful to explicitly call out the data structure more. Even if you cannot use a fully abtracted queue.
Also, newest/oldest just looks weird to me; I'm expecting head/tail.
Quoted 105 lines
static void
add_descr_list(struct prb_reserved_entry *e){
structprintk_ringbuffer*rb =e->rb; structprb_list*l =&rb->descr_list; structprb_descr*d =e->descr;
structprb_descr*newest_d;
unsigned longnewest_id;
WRITE_ONCE(d->next, EOL);do {
newest_id=READ_ONCE(l->newest);newest_d=TO_DESC(rb, newest_id);if (
newest_id== EOL) {
WRITE_ONCE(d->seq, 1);
} else {
/*
* MB5-read: synchronize setting newest descr *
* context-pair: 2 writers adding a descriptor via
*add_descr_list().
*
* @newest will load before @seq due to a data
* dependency, therefore, the stores of @seq
* and @next from the pairing MB5-write context
* will be visible.
*
* Although @next is not loaded by this context,
* this context must overwrite the stored @next
* value of the pairing MB5-write context. */
WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);
}/*
* MB5-write: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
*add_descr_list().
*
* Ensure that @next and @seq are stored before @d is
* visible via @newest. The pairing MB5-read context
* must load this @seq value and must overwrite this
* @next value.
*/
} while (cmpxchg_release(&l->newest, newest_id, e->id)!=newest_id);if (
unlikely(newest_id == EOL)) {
/*
* MB0-write: synchronize adding first descr *
* context-pair: 1 writer adding the first descriptor via
*add_descr_list(), 1 reader getting the beginning of
* the list viaiter_peek_next_id().
*
* This context recently assigned new values for @id,
* @next, @seq. Ensure these are stored before the first
* store to @oldest so that the new values are visible
* to the reader in the pairing MB0-read context. *
* Note: Before this store, the value of @oldest is EOL. */
smp_store_release(&l->oldest, e->id);
} else {
/*
* MB6-write: synchronize linking new descr
*
* context-pair-1: 1 writer adding a descriptor via
*add_descr_list(), 1 writer removing a descriptor via
*remove_oldest_descr().
*
* If this is a recycled descriptor, this context
* recently stored a new @oldest value. Ensure that
* @oldest is stored before storing @next so that
* if the pairing MB6-read context sees a non-EOL
* @next value, it is ensured that it will also see
* an updated @oldest value.
*
* context-pair-2: 1 writer adding a descriptor via
*add_descr_list(), 1 reader iterating the list via
*prb_iter_next_valid_entry().
*
* This context recently assigned new values for @id,
* @next, @seq, @data, @data_next. Ensure these are
* stored before storing @next of the previously
* newest descriptor so that the new values are
* visible to the iterating reader in the pairing
* MB6-read context.
*
* Note: Before this store, the value of @next of the
* previously newest descriptor is EOL.
*/
smp_store_release(&newest_d->next, e->id);
}
}The
smp_rmb()calls in the reader functions are then commented and marked with the appropriate MB0-read and MB6-read labels.Quoted 2 lines
Afaict
prb_listis a list head not a list node (calling it just_listis confusing at best).OK.
Quoted 7 lines
Quoted 3 lines
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
Yes, but with one important feature: the nodes in the FIFO queue are labeled with ordered sequence numbers. This is important for printk. I talk more about this below.
But nowhere did/do you say what the actual data structure is, with what modification for which reason.
Quoted 8 lines
Quoted 8 lines
struct lqueue_head { struct lqueue_node *head, *tail; }; struct lqueue_node { struct lqueue_node *next; };
Quoted 8 lines
Quoted 5 lines
void lqueue_push(struct lqueue_head *h, struct lqueue_node *n) { struct lqueue_node *prev; n->next = NULL;Is this safe? Do all compilers understand that @next must be stored before the
xchg()of @head? I would have chosenWRITE_ONCE().
Yep, xchg() implies an smp_mb() before and after, smp_mb() in turn implies a compiler barrier. Even if there is compiler induced brain damage (store-tearing) all that must be done before the actual RmW.
Same with xchg_release(), the RELEASE is sufficient to have all previous stores complete before the RmW.
Quoted 6 lines
Quoted 5 lines
/* * xchg() implies RELEASE; and thereby ensures @n is * complete before getting published. */ prev = xchg(&h->head, n);
Quoted 7 lines
Unfortunately it is not that simple because of sequence numbers. A node must be assigned a sequence number that is +1 of the previous node. This must be done before exchanging the head because immediately after the
xchg()on the head, another CPU could then add on to us and expects our sequence number to already be set.This is why I need
cmpxchg()here.
So far that doens't make sense yet, +1 is implicit in the list order surely. But yes, if you need the seq like that, then cmpxchg it is.
Quoted 10 lines
Quoted 6 lines
/* * xchg() implies ACQUIRE; and thereby ensures @tail is * written after @head, see lqueue_pop()'s smp_rmb(). */ if (prev) WRITE_ONCE(prev->next, n);This needs to be a
store_release()so that a reader cannot read @n but the store to @next is not yet visible. The memory barriers of the abovexchg()do not apply here because readers never read @head.
Confused, all stores to @n are before the xchg() so the barrier from xchg() also order those stores and this store.
Quoted 35 lines
Quoted 2 lines
else WRITE_ONCE(h->tail, n);Ditto, but for the tail node in particular.
Quoted 18 lines
} struct lqueue_node *lqueue_pop(struct lqueue_head *h) { struct lqueue_node *head, *tail, *next; do { tail = READ_ONCE(h->tail); /* If the list is empty, nothing to remove. */ if (!tail) return NULL; /* * If we see @tail, we must then also see @head. * Pairs with the xchg() in lqueue_push(), * ensure no false positive on the singleton * test below. */Quoted 8 lines
smp_rmb(); head = READ_ONCE(h->head); /* If there is but one item; fail to remove. */ if (head == tail) return NULL; next = smp_cond_load_relaxed(&tail->next, VAL);What if a writer is adding a 2nd node to the queue and is interrupted by an NMI directly after the
xchg()inlqueue_push()? Then we have:
Quoted 6 lines
* head != tail
*tail->next== NULLIf that interrupting NMI calls
lqueue_pop(), the NMI will spin forever. The followingcmpxchg()is not allowed to happen as long astail->nextis NULL.
Indeed. I forgot that you actually use pop on the producer side.
(Note that the qspinlock has a queue not unlike this, but that again doesn't have to bother with NMIs)
Quoted 2 lines
This is why I synchronize on @next instead, using (tail && !tail->next) for the singleton test.
OK.
Quoted 29 lines
Quoted 8 lines
} while (cmpxchg(h->tail, tail, next) != tail); return tail; }Now, you appear to be using
desc_idsinstead of pointers, but since you're not using the actual wrap value; I don't see the benefit of using those IDs over straight pointers.The documentation mentions that descriptor ids are used to identify pointers to invalid descriptors. This is used by the readers, see
iter_peek_next_id()andprb_iter_next_valid_entry().IDs are used for:
- @next of descriptors on the list
- @id, @id_next in the reader iterator
- @id in the data blocksIf changed to pointers, iterators would need to additionally store @seq values to be able to identifiy if the entry they are pointing to is the entry they expect.
The only advantage I see with pointers is that the ringbuffer could be more useful generally, independent of whether the data is separate or within the nodes or if the nodes are statically or dynamically allocated. That is something worth having, even if it is not printk related.
Quoted 3 lines
Are you implicitly requesting me to split the
prb_ringbufferand instead base it on a new "lockless multi-writer multi-reader sequenced FIFO queue" data structure?
Not specifically; I was just trying to untangle the code and found a queue. I still (sorry!) haven't gotten through the lot of it to see how all the parts fit together.
Quoted 8 lines
Quoted 4 lines
That is, unless I've overlooked some subtle ABA issue, but then, your code doesn't seem to mention that, and I think we're good because if we re-use an entry, it can never get back in the same location, since we never allow an empty list
I do not understand what you mean here. If a reader has a pointer to an entry, the entry behind that pointer can certainly change. But that isn't a problem. The reader will recognize that.
ABA is where a cmpxchg has a false positive due to values matching but not the structure.
For example, in the above pop, if h->tail would (again) be @tail, but @next would not be the correct value. Something like that could happen if before the cmpxchg a concurrent pop takes the element off and then sticks it back on, but with a different ->next.
Then our cmpxchg wil succeed and corrupt.
Quoted 11 lines
Quoted 1 line
(might also be fixable, haven't tought too hard on this).
:-)
Quoted 4 lines
That said, the above has
cmpxchg()vsWRITE_ONCE()and is therefore not safe on a number of our architectures. We can either not care about performance and usexchg()for the ->tail store, or useatomic_long_tand suffer ugly casting.
cmpxchg_release()vsWRITE_ONCE()is not safe?! Can you point me to documentation about this?
Documentation/atomic_t.txt has this, see the SEMANTICS section on atomic-set.
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 7 lines · Peter Zijlstra
Quoted 2 lines · John Ogness
cmpxchg_release()vsWRITE_ONCE()is not safe?! Can you point me to documentation about this?
Documentation/atomic_t.txthas this, see the SEMANTICS section on atomic-set.
Also see: arch/parisc/lib/bitops.c for one such case.
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to Peter ZijlstraQuoted 25 lines · Peter Zijlstra
Quoted 10 lines
I have implemented and tested these changes. I also added setting the list terminator to this function, since all callers would have to do it anyway. Also, I spent a lot of time trying to put in comments that I think are _understandable_ and _acceptable_.
@Peter: I expect they are way too long for you.
@Andrea: Is this starting to become something that you would like to see?
Quoted 14 lines
/**
*add_descr_list()- Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
Quoted 2 lines
I still think it might be useful to explicitly call out the data structure more. Even if you cannot use a fully abtracted queue.
Agreed. It needs to be clear that the queue management is separate from the data management.
Quoted 1 line
Also, newest/oldest just looks weird to me; I'm expecting head/tail.
I will rename it to head/tail.
Quoted 10 lines
Quoted 7 lines
Quoted 3 lines
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
Yes, but with one important feature: the nodes in the FIFO queue are labeled with ordered sequence numbers. This is important for printk. I talk more about this below.
But nowhere did/do you say what the actual data structure is, with what modification for which reason.
When you dive into the reader code you will see that the sequence numbers are necessary for readers to recognize that they have missed records. This means that the sequence numbers must be ordered, and AFAICT that is only possible if the queue management code is assigning it.
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
/* * xchg() implies ACQUIRE; and thereby ensures @tail is * written after @head, see lqueue_pop()'s smp_rmb(). */ if (prev) WRITE_ONCE(prev->next, n);
Quoted 6 lines
Quoted 3 lines
This needs to be a
store_release()so that a reader cannot read @n but the store to @next is not yet visible. The memory barriers of the abovexchg()do not apply here because readers never read @head.Confused, all stores to @n are before the
xchg()so the barrier fromxchg()also order those stores and this store.
Sorry. Yes, you are correct. I was confusing your suggested implementation with mine. I'm starting to overthink things and confuse myself about memory barriers. I need to be more careful.
Quoted 2 lines
(Note that the qspinlock has a queue not unlike this, but that again doesn't have to bother with NMIs)
Thank you for pointing this out! I will look to qspinlock for some naming guidelines.
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
Now, you appear to be using
desc_idsinstead of pointers, but since you're not using the actual wrap value; I don't see the benefit of using those IDs over straight pointers. That is, unless I've overlooked some subtle ABA issue, but then, your code doesn't seem to mention that, and I think we're good because if we re-use an entry, it can never get back in the same location, since we never allow an empty list
Quoted 6 lines
Quoted 3 lines
I do not understand what you mean here. If a reader has a pointer to an entry, the entry behind that pointer can certainly change. But that isn't a problem. The reader will recognize that.
ABA is where a cmpxchg has a false positive due to values matching but not the structure.
Thanks for the clarification. And it reminds me why I chose to use desc_ids. If we are using pointers instead of desc_ids, assuming we have a queue with currently only 1 node, the following should cause the ABA problem. CPU0 is perfoming an lqueue_push() to add a 2nd node to the queue.
CPU0 CPU1
---- ----
head = READ_ONCE(h->head);
seq = READ_ONCE(head->seq);
WRITE_ONCE(n->seq, seq + 1);
WRITE_ONCE(n->next, NULL);
lqueue_push();
lqueue_pop();
lqueue_push();
cmpxchg_release(&h->head, head, n);
WRITE_ONCE(head->next, n);The queue itself will still be intact, but the sequence numbers are now wrong. For this to happen using desc_ids, the above set of calls from CPU1 would need to occur "LONG_MAX/desc_max_count" times in that window. Basically I am using tagged state references with probably >40 bits for the tag (on 64-bit systems).
The effect for readers is that they will see a sequence number that is less or equal to the previous seen sequence number. Worthy of a warn message.
My code needs to mention all this.
Quoted 10 lines
Quoted 7 lines
Quoted 4 lines
That said, the above has
cmpxchg()vsWRITE_ONCE()and is therefore not safe on a number of our architectures. We can either not care about performance and usexchg()for the ->tail store, or useatomic_long_tand suffer ugly casting.
cmpxchg_release()vsWRITE_ONCE()is not safe?! Can you point me to documentation about this?
Documentation/atomic_t.txthas this, see the SEMANTICS section on atomic-set.
Thanks. I overlooked that subtle detail. Can I assume NMIs do not exist on architectures that need to implement locking for cmpxchg()? Or did I just hit a major obstacle?
I would prefer to replace the affected WRITE_ONCE() with xchg_relaxed() (like qspinlock is doing). Or are there some other subtle advantages of atomic_long_t?
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 3 lines · John Ogness
Thanks. I overlooked that subtle detail. Can I assume NMIs do not exist on architectures that need to implement locking for
cmpxchg()? Or did I just hit a major obstacle?
I think that is a fair assumption, I'm not aware of anybody having NMIs _and_ 'broken' atomics.
Then again, we also have ARCH_HAVE_NMI_SAFE_CMPXCHG.
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 6 lines · John Ogness
Quoted 2 lines · Peter Zijlstra
(Note that the qspinlock has a queue not unlike this, but that again doesn't have to bother with NMIs)
Thank you for pointing this out! I will look to qspinlock for some naming guidelines.
Fair warning: qspinlock might hurt your brain; but if you do look and are unsure; let me know and I'll try and improve its comments.
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 15 lines
/**
*add_descr_list()- Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
static voidadd_descr_list(struct prb_reserved_entry *e)
Quoted 8 lines
{
struct printk_ringbuffer *rb = e->rb;
struct prb_list *l = &rb->descr_list;
struct prb_descr *d = e->descr;
struct prb_descr *newest_d;
unsigned long newest_id;
WRITE_ONCE(d->next, EOL);/* C */
Quoted 3 lines
do {
newest_id = READ_ONCE(l->newest);/* A */
Quoted 13 lines
newest_d = TO_DESC(rb, newest_id);
if (newest_id == EOL) {
WRITE_ONCE(d->seq, 1);
} else {
/*
* MB5-read: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
* add_descr_list().
*
* @newest will load before @seq due to a data
* dependency, therefore, the stores of @seqQuoted 8 lines
* and @next from the pairing MB5-write context * will be visible. * * Although @next is not loaded by this context, * this context must overwrite the stored @next * value of the pairing MB5-write context. */ WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);
/* B: this READ_ONCE() */
Hence you're claiming a data dependency from A to B. (FWIW, the LKMM would call "A ->dep B" an "address dependency.)
This comment also claims that the "pairing MB5-write" orders "stores of @seq and @next" (which are to different memory locations w.r.t. A and B): I do not get why this access to @next (C above?, that's also "unordered" w.r.t. A) can be relevant; can you elaborate?
Quoted 15 lines
}
/*
* MB5-write: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
*add_descr_list().
*
* Ensure that @next and @seq are stored before @d is
* visible via @newest. The pairing MB5-read context
* must load this @seq value and must overwrite this
* @next value.
*/
} while (cmpxchg_release(&l->newest, newest_id, e->id)!=newest_id);
Quoted 15 lines
if (
unlikely(newest_id == EOL)) {
/*
* MB0-write: synchronize adding first descr *
* context-pair: 1 writer adding the first descriptor via
*add_descr_list(), 1 reader getting the beginning of
* the list viaiter_peek_next_id().
*
* This context recently assigned new values for @id,
* @next, @seq. Ensure these are stored before the first
* store to @oldest so that the new values are visible
* to the reader in the pairing MB0-read context. *
* Note: Before this store, the value of @oldest is EOL. */
My gmail-search foo is unable to locate MB0-read: what am I missing? Also, can you maybe annotate the memory accesses to @id, @next, @seq and @oldest (as I did above)? I find myself guessing their location.
Quoted 22 lines
smp_store_release(&l->oldest, e->id);
} else {
/*
* MB6-write: synchronize linking new descr *
* context-pair-1: 1 writer adding a descriptor via
*add_descr_list(), 1 writer removing a descriptor via
*remove_oldest_descr().
*
* If this is a recycled descriptor, this context
* recently stored a new @oldest value. Ensure that
* @oldest is stored before storing @next so that
* if the pairing MB6-read context sees a non-EOL
* @next value, it is ensured that it will also see
* an updated @oldest value.
*
* context-pair-2: 1 writer adding a descriptor via
*add_descr_list(), 1 reader iterating the list via
*prb_iter_next_valid_entry().
*
* This context recently assigned new values for @id,
* @next, @seq, @data, @data_next. Ensure these are
Quoted 8 lines
* stored before storing @next of the previously
* newest descriptor so that the new values are
* visible to the iterating reader in the pairing
* MB6-read context.
*
* Note: Before this store, the value of @next of the
* previously newest descriptor is EOL.
*/
Same as above but for MB6-read and the accesses to @id, @next, @seq, @data, @data_next.
In conclusion, I have been unable to produce litmus tests by reading your comments (meaning I'm lost).
Thanks,
Andrea
Quoted 167 lines
smp_store_release(&newest_d->next, e->id); } }The
smp_rmb()calls in the reader functions are then commented and marked with the appropriate MB0-read and MB6-read labels.Quoted 2 lines
Afaict
prb_listis a list head not a list node (calling it just_listis confusing at best).OK.
Quoted 3 lines
You have a single linked list going from the tail to the head, while adding to the head and removing from the tail. And that sounds like a FIFO queue:
Yes, but with one important feature: the nodes in the FIFO queue are labeled with ordered sequence numbers. This is important for printk. I talk more about this below.
Quoted 5 lines
struct lqueue_head { struct lqueue_node *head, *tail; }; struct lqueue_node {Quoted 8 lines
struct lqueue_node *next; }; void lqueue_push(struct lqueue_head *h, struct lqueue_node *n) { struct lqueue_node *prev; n->next = NULL;Is this safe? Do all compilers understand that @next must be stored before the
xchg()of @head? I would have chosenWRITE_ONCE().Quoted 5 lines
/* * xchg() implies RELEASE; and thereby ensures @n is * complete before getting published. */ prev = xchg(&h->head, n);Unfortunately it is not that simple because of sequence numbers. A node must be assigned a sequence number that is +1 of the previous node. This must be done before exchanging the head because immediately after the
xchg()on the head, another CPU could then add on to us and expects our sequence number to already be set.This is why I need
cmpxchg()here.Quoted 6 lines
/* * xchg() implies ACQUIRE; and thereby ensures @tail is * written after @head, see lqueue_pop()'s smp_rmb(). */ if (prev) WRITE_ONCE(prev->next, n);This needs to be a
store_release()so that a reader cannot read @n but the store to @next is not yet visible. The memory barriers of the abovexchg()do not apply here because readers never read @head.Quoted 2 lines
else WRITE_ONCE(h->tail, n);Ditto, but for the tail node in particular.
Quoted 18 lines
} struct lqueue_node *lqueue_pop(struct lqueue_head *h) { struct lqueue_node *head, *tail, *next; do { tail = READ_ONCE(h->tail); /* If the list is empty, nothing to remove. */ if (!tail) return NULL; /* * If we see @tail, we must then also see @head. * Pairs with the xchg() in lqueue_push(), * ensure no false positive on the singleton * test below. */Quoted 8 lines
smp_rmb(); head = READ_ONCE(h->head); /* If there is but one item; fail to remove. */ if (head == tail) return NULL; next = smp_cond_load_relaxed(&tail->next, VAL);What if a writer is adding a 2nd node to the queue and is interrupted by an NMI directly after the
xchg()inlqueue_push()? Then we have:* head != tail
*tail->next== NULLIf that interrupting NMI calls
lqueue_pop(), the NMI will spin forever. The followingcmpxchg()is not allowed to happen as long astail->nextis NULL.This is why I synchronize on @next instead, using (tail && !tail->next) for the singleton test.
Quoted 8 lines
} while (cmpxchg(h->tail, tail, next) != tail); return tail; }Now, you appear to be using
desc_idsinstead of pointers, but since you're not using the actual wrap value; I don't see the benefit of using those IDs over straight pointers.The documentation mentions that descriptor ids are used to identify pointers to invalid descriptors. This is used by the readers, see
iter_peek_next_id()andprb_iter_next_valid_entry().IDs are used for:
- @next of descriptors on the list
- @id, @id_next in the reader iterator
- @id in the data blocksIf changed to pointers, iterators would need to additionally store @seq values to be able to identifiy if the entry they are pointing to is the entry they expect.
The only advantage I see with pointers is that the ringbuffer could be more useful generally, independent of whether the data is separate or within the nodes or if the nodes are statically or dynamically allocated. That is something worth having, even if it is not printk related.
Are you implicitly requesting me to split the
prb_ringbufferand instead base it on a new "lockless multi-writer multi-reader sequenced FIFO queue" data structure?Quoted 4 lines
That is, unless I've overlooked some subtle ABA issue, but then, your code doesn't seem to mention that, and I think we're good because if we re-use an entry, it can never get back in the same location, since we never allow an empty list
I do not understand what you mean here. If a reader has a pointer to an entry, the entry behind that pointer can certainly change. But that isn't a problem. The reader will recognize that.
Quoted 1 line
(might also be fixable, haven't tought too hard on this).
:-)
Quoted 4 lines
That said, the above has
cmpxchg()vsWRITE_ONCE()and is therefore not safe on a number of our architectures. We can either not care about performance and usexchg()for the ->tail store, or useatomic_long_tand suffer ugly casting.
cmpxchg_release()vsWRITE_ONCE()is not safe?! Can you point me to documentation about this?Quoted 2 lines
But the above is, IMO, a more useful and readable abstraction. Let me continue in another email (probably tomorrow).
Thank you for taking the time for this.
John Ogness
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 58 lines · Andrea Parri
Quoted 15 lines
/**
*add_descr_list()- Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
static voidadd_descr_list(struct prb_reserved_entry *e)Quoted 8 lines
{ struct printk_ringbuffer *rb = e->rb; struct prb_list *l = &rb->descr_list; struct prb_descr *d = e->descr; struct prb_descr *newest_d; unsigned long newest_id; WRITE_ONCE(d->next, EOL);/* C */
Quoted 3 lines
do { newest_id = READ_ONCE(l->newest);/* A */
Quoted 13 lines
newest_d = TO_DESC(rb, newest_id); if (newest_id == EOL) { WRITE_ONCE(d->seq, 1); } else { /* * MB5-read: synchronize setting newest descr * * context-pair: 2 writers adding a descriptor via * add_descr_list(). * * @newest will load before @seq due to a data * dependency, therefore, the stores of @seqQuoted 8 lines
* and @next from the pairing MB5-write context * will be visible. * * Although @next is not loaded by this context, * this context must overwrite the stored @next * value of the pairing MB5-write context. */ WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);/* B: this
READ_ONCE()*/
Quoted 7 lines
Hence you're claiming a data dependency from A to B. (FWIW, the LKMM would call "A ->dep B" an "address dependency.)
This comment also claims that the "pairing MB5-write" orders "stores of @seq and @next" (which are to different memory locations w.r.t. A and B): I do not get why this access to @next (C above?, that's also "unordered" w.r.t. A) can be relevant; can you elaborate?
I will add some more labels to complete the picture. All these events are within this function:
D: the WRITE_ONCE() to @seq
E: the STORE of a successful cmpxchg() for @newest (the MB5-write cmpxchg())
F: the STORE of a new @next (the last smp_store_release() of this function, note that the _release() is not relevant for this pair)
The significant events for 2 contexts that are accessing the same addresses of a descriptor are:
P0(struct desc *d0)
{
// adding a new descriptor d0
WRITE_ONCE(d0->next, EOL); // C
WRITE_ONCE(d0->seq, X); // D
cmpxchg_release(newest, Y, indexof(d0)); // E
}P1(struct desc *d1)
{
// adding a new descriptor d1 that comes after d0
struct desc *d0;
int r0, r1;
r0 = READ_ONCE(newest); // A
d0 = &array[r0];
r1 = READ_ONCE(d0->seq); // B
WRITE_ONCE(d0->next, Z); // F
}d0 is the same address for P0 and P1. (The values of EOL, X, Y, Z are unrelated and irrelevant.)
I am claiming that:
- B comes after D
- F comes after C
Quoted 31 lines
Quoted 15 lines
}
/*
* MB5-write: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
*add_descr_list().
*
* Ensure that @next and @seq are stored before @d is
* visible via @newest. The pairing MB5-read context
* must load this @seq value and must overwrite this
* @next value.
*/
} while (cmpxchg_release(&l->newest, newest_id, e->id)!=newest_id);Quoted 15 lines
if (
unlikely(newest_id == EOL)) {
/*
* MB0-write: synchronize adding first descr *
* context-pair: 1 writer adding the first descriptor via
*add_descr_list(), 1 reader getting the beginning of
* the list viaiter_peek_next_id().
*
* This context recently assigned new values for @id,
* @next, @seq. Ensure these are stored before the first
* store to @oldest so that the new values are visible
* to the reader in the pairing MB0-read context. *
* Note: Before this store, the value of @oldest is EOL. */
Quoted 3 lines
My gmail-search foo is unable to locate MB0-read: what am I missing? Also, can you maybe annotate the memory accesses to @id, @next, @seq and @oldest (as I did above)? I find myself guessing their location.
Sorry. The MB0-read is a _new_ comment that would be added to the smp_rmb() of the reader functions. I didn't repost everything because I just wanted to get a feel if the comments for _this_ function are improving. Really all I care about right now is properly documenting MB5. It is a good example because MB5 is completely within this function. If I can satisfactorily document MB5, then I can post a new version with updated comments for everything.
Quoted 31 lines
Quoted 22 lines
smp_store_release(&l->oldest, e->id);
} else {
/*
* MB6-write: synchronize linking new descr *
* context-pair-1: 1 writer adding a descriptor via
*add_descr_list(), 1 writer removing a descriptor via
*remove_oldest_descr().
*
* If this is a recycled descriptor, this context
* recently stored a new @oldest value. Ensure that
* @oldest is stored before storing @next so that
* if the pairing MB6-read context sees a non-EOL
* @next value, it is ensured that it will also see
* an updated @oldest value.
*
* context-pair-2: 1 writer adding a descriptor via
*add_descr_list(), 1 reader iterating the list via
*prb_iter_next_valid_entry().
*
* This context recently assigned new values for @id,
* @next, @seq, @data, @data_next. Ensure these areQuoted 8 lines
* stored before storing @next of the previously
* newest descriptor so that the new values are
* visible to the iterating reader in the pairing
* MB6-read context.
*
* Note: Before this store, the value of @next of the
* previously newest descriptor is EOL.
*/
Quoted 5 lines
Same as above but for MB6-read and the accesses to @id, @next, @seq, @data, @data_next.
In conclusion, I have been unable to produce litmus tests by reading your comments (meaning I'm lost).
I feel like I'm stating all the information, but nobody understands it. If you can help me to correctly document MB5, I can submit a new version with all the memory barriers correctly documented.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 103 lines · John Ogness
Quoted 58 lines · Andrea Parri
Quoted 15 lines
/**
*add_descr_list()- Add a descriptor to the descriptor list. *
* @e: An entry that has already reserved data.
*
* The provided entry contains a pointer to a descriptor that has already
* been reserved for this entry. However, the reserved descriptor is not
* yet on the list. Add this descriptor as the newest item.
*
* A descriptor is added in two steps. The first step is to make this
* descriptor the newest. The second step is to update @next of the former
* newest descriptor to point to this one (or set @oldest to this one if
* this will be the first descriptor on the list).
*/
static voidadd_descr_list(struct prb_reserved_entry *e)Quoted 8 lines
{ struct printk_ringbuffer *rb = e->rb; struct prb_list *l = &rb->descr_list; struct prb_descr *d = e->descr; struct prb_descr *newest_d; unsigned long newest_id; WRITE_ONCE(d->next, EOL);/* C */
Quoted 3 lines
do { newest_id = READ_ONCE(l->newest);/* A */
Quoted 13 lines
newest_d = TO_DESC(rb, newest_id); if (newest_id == EOL) { WRITE_ONCE(d->seq, 1); } else { /* * MB5-read: synchronize setting newest descr * * context-pair: 2 writers adding a descriptor via * add_descr_list(). * * @newest will load before @seq due to a data * dependency, therefore, the stores of @seqQuoted 8 lines
* and @next from the pairing MB5-write context * will be visible. * * Although @next is not loaded by this context, * this context must overwrite the stored @next * value of the pairing MB5-write context. */ WRITE_ONCE(d->seq, READ_ONCE(newest_d->seq) + 1);/* B: this
READ_ONCE()*/Quoted 7 lines
Hence you're claiming a data dependency from A to B. (FWIW, the LKMM would call "A ->dep B" an "address dependency.)
This comment also claims that the "pairing MB5-write" orders "stores of @seq and @next" (which are to different memory locations w.r.t. A and B): I do not get why this access to @next (C above?, that's also "unordered" w.r.t. A) can be relevant; can you elaborate?
I will add some more labels to complete the picture. All these events are within this function:
D: the
WRITE_ONCE()to @seqE: the STORE of a successful
cmpxchg()for @newest (the MB5-writecmpxchg())F: the STORE of a new @next (the last
smp_store_release()of this function, note that the_release()is not relevant for this pair)The significant events for 2 contexts that are accessing the same addresses of a descriptor are:
P0(struct desc *d0){ // adding a new descriptor d0 WRITE_ONCE(d0->next, EOL); // C WRITE_ONCE(d0->seq, X); // D cmpxchg_release(newest, Y, indexof(d0)); // E }
P1(struct desc *d1){ // adding a new descriptor d1 that comes after d0 struct desc *d0; int r0, r1; r0 = READ_ONCE(newest); // A d0 = &array[r0]; r1 = READ_ONCE(d0->seq); // B WRITE_ONCE(d0->next, Z); // F }
Quoted 7 lines
d0 is the same address for P0 and P1. (The values of EOL, X, Y, Z are unrelated and irrelevant.)
I am claiming that:
- B comes after D
- F comes after C
I think these are both assuming that A is reading the value stored by E (shortly, "A reads from E")? If so, then the two claims become/are:
- If A reads from E, then B comes after D
- If A reads from E, then F comes after C
I think you could avoid the (ambiguous) "comes after" and say something like:
(1) If A reads from E, then B reads from D (or from another store
to ->seq, not reported in the snippet, which overwrites D)
(2) If A reads from E, then F overwrites C
This, IIUC, for the informal descriptions of the (intended) guarantees. Back to the pairings in question: AFAICT,
(a) For (1), we rely on the pairing:
RELEASE from D to E (matching) ADDRESS DEP. from A to B
(b) For (2), we rely on the pairing:
RELEASE from C to E (matching) ADDRESS DEP. from A to F
Does this make sense?
Quoted 36 lines
Quoted 32 lines
Quoted 16 lines
}
/*
* MB5-write: synchronize setting newest descr
*
* context-pair: 2 writers adding a descriptor via
*add_descr_list().
*
* Ensure that @next and @seq are stored before @d is
* visible via @newest. The pairing MB5-read context
* must load this @seq value and must overwrite this
* @next value.
*/
} while (cmpxchg_release(&l->newest, newest_id, e->id)!=newest_id);Quoted 15 lines
if (
unlikely(newest_id == EOL)) {
/*
* MB0-write: synchronize adding first descr *
* context-pair: 1 writer adding the first descriptor via
*add_descr_list(), 1 reader getting the beginning of
* the list viaiter_peek_next_id().
*
* This context recently assigned new values for @id,
* @next, @seq. Ensure these are stored before the first
* store to @oldest so that the new values are visible
* to the reader in the pairing MB0-read context. *
* Note: Before this store, the value of @oldest is EOL. */Quoted 3 lines
My gmail-search foo is unable to locate MB0-read: what am I missing? Also, can you maybe annotate the memory accesses to @id, @next, @seq and @oldest (as I did above)? I find myself guessing their location.
Quoted 7 lines
Sorry. The MB0-read is a _new_ comment that would be added to the
smp_rmb()of the reader functions. I didn't repost everything because I just wanted to get a feel if the comments for _this_ function are improving. Really all I care about right now is properly documenting MB5. It is a good example because MB5 is completely within this function. If I can satisfactorily document MB5, then I can post a new version with updated comments for everything.
Oh, I see, thanks for this clarification.
Quoted 35 lines
Quoted 35 lines
Quoted 23 lines
smp_store_release(&l->oldest, e->id);
} else {
/*
* MB6-write: synchronize linking new descr *
* context-pair-1: 1 writer adding a descriptor via
*add_descr_list(), 1 writer removing a descriptor via
*remove_oldest_descr().
*
* If this is a recycled descriptor, this context
* recently stored a new @oldest value. Ensure that
* @oldest is stored before storing @next so that
* if the pairing MB6-read context sees a non-EOL
* @next value, it is ensured that it will also see
* an updated @oldest value.
*
* context-pair-2: 1 writer adding a descriptor via
*add_descr_list(), 1 reader iterating the list via
*prb_iter_next_valid_entry().
*
* This context recently assigned new values for @id,
* @next, @seq, @data, @data_next. Ensure these areQuoted 8 lines
* stored before storing @next of the previously
* newest descriptor so that the new values are
* visible to the iterating reader in the pairing
* MB6-read context.
*
* Note: Before this store, the value of @next of the
* previously newest descriptor is EOL.
*/Same as above but for MB6-read and the accesses to @id, @next, @seq, @data, @data_next.
Quoted 6 lines
Quoted 2 lines
In conclusion, I have been unable to produce litmus tests by reading your comments (meaning I'm lost).
I feel like I'm stating all the information, but nobody understands it. If you can help me to correctly document MB5, I can submit a new version with all the memory barriers correctly documented.
IMO (and assuming that what I wrote above makes some sense), (a-b) and (1-2) above, together with the associated annotations of the code/ops, provide all the desired and necessary information to document MB5.
For readability purposes, it could be nice to also keep the snippet you provided above (but let me stress, again, that such a snippet should be integrated with additional information as suggested above).
As to "where to insert the memory barrier documentation", I really have no suggestion ATM. I guess someone would split it (say, before A and E) while others could prefer to keep it within a same inline comment.
Thanks for this information (and for your patience!),
Andrea
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 38 lines · Andrea Parri
Quoted 25 lines
The significant events for 2 contexts that are accessing the same addresses of a descriptor are:
P0(struct desc *d0){ // adding a new descriptor d0 WRITE_ONCE(d0->next, EOL); // C WRITE_ONCE(d0->seq, X); // D cmpxchg_release(newest, Y, indexof(d0)); // E }
P1(struct desc *d1){ // adding a new descriptor d1 that comes after d0 struct desc *d0; int r0, r1; r0 = READ_ONCE(newest); // A d0 = &array[r0]; r1 = READ_ONCE(d0->seq); // B WRITE_ONCE(d0->next, Z); // F }Quoted 2 lines
d0 is the same address for P0 and P1. (The values of EOL, X, Y, Z are unrelated and irrelevant.)
(1) If A reads from E, then B reads from D (or from another store
to ->seq, not reported in the snippet, which overwrites D)(2) If A reads from E, then F overwrites C
This, IIUC, for the informal descriptions of the (intended) guarantees. Back to the pairings in question: AFAICT,
(a) For (1), we rely on the pairing:
Quoted 7 lines
RELEASE from D to E (matching) ADDRESS DEP. from A to B
(b) For (2), we rely on the pairing:
RELEASE from C to E (matching) ADDRESS DEP. from A to F
Does this make sense?
Yes. This is what I needed to see.
Quoted 11 lines
IMO (and assuming that what I wrote above makes some sense), (a-b) and (1-2) above, together with the associated annotations of the code/ops, provide all the desired and necessary information to document MB5.
For readability purposes, it could be nice to also keep the snippet you provided above (but let me stress, again, that such a snippet should be integrated with additional information as suggested above).
As to "where to insert the memory barrier documentation", I really have no suggestion ATM. I guess someone would split it (say, before A and E) while others could prefer to keep it within a same inline comment.
Thank you. This is the level of formalization I've been looking for. I will rework the comments (and naming) and post a v3. It is probably best for you to wait until then to look at this again. (And after going through such formal processes, even _I_ am having difficulties understanding what some of my memory barriers are supposed to be synchronizing.)
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 29 lines · John Ogness
Quoted 8 lines · Peter Zijlstra
lib/printk_ringbuffer.c line 320
Quoted 6 lines
lib/printk_ringbuffer.c new file +6
-0+ +if (unlikely (newest_id ==EOL )) { +/* no previous newest means we *are* the list, set oldest */ + +/* +* MB UNPAIRED That's a bug, MB must always be paired.
Well, it "pairs" with the
smp_rmb()of the readers, but I didn't think that counts as a pair. That's why I wrote unpaired. The litmus test is:
P0(int *x, int *y){ WRITE_ONCE(*x, 1); smp_store_release(y, 1); }
P1(int *x, int *y){ int rx; int ry; ry = READ_ONCE(*y); smp_rmb(); rx = READ_ONCE(*x); }
Quoted 4 lines
exists (1:rx=0 /\ 1:ry=1)
The readers rely on the
store_releases"pairing" with thesmp_rmb()so that the readers see things in a sane order.
That is certainly a valid pairing, see also the 'SMP BARRIER PAIRING' section in memory-barriers.txt (I thought we had a table in there, but apparently that never quite made it in).
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessHi John,
I am still scratching head around this. Anyway, I wanted to write something. I am sorry that the answer is really long. I do not know how to write it more effectively.
First, the documentation helped a lot. Also I found several ideas that were important to make it working a lockless way. Especially:
+ separate buffer with descriptors of data entries
+ descriptor can be reused only when the related data have already been discarded
There are few comments about the naming and code at the end of the mail. But I primary want to write about the design, namely:
+ Linked list of descriptors
+ Code structure, consistency, barriers
+ Ideas
1. Linked list of descriptors
-----------------------------
The list of descriptors makes the code more complicated and I do not see much gain. It is possible that I just missed something.
If I get it correctly then the list could only grow by adding never used members. The already added members are newer removed neither shuffled.
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
It would allow to remove:
+ desc->id because it will be the same as desc->seq
+ desc->next because the address of the next member can be easily counted
2. Consistency, barriers, and code structure
--------------------------------------------
I haven't got the whole picture about the code logic so far. Maybe I haven't tried hard enough. I actually spent quite some time with playing with some alternatives.
In each case, the code is very complicated (of course, the problem is complicated):
+ 6 steps (barriers) are needed to synchronize writers. This means a lot of variants of possible races.
+ The six barriers are somehow related to 6 variables. But there are several other variables that are being modified. It is needed to check that they can be safely modified/read on the given locations.
OK, the structures have a livecycle:
+ descriptor:
+ free
+ taken
+ data block:
+ reserved
+ committed
+ correctly read
+ freed
And there are few basic questions about each state:
+ where and how the state is set
+ where and how it is invalidated
+ where and how the state is checked in other code
+ how is it achieved that the state is the same as long as needed
Some of the answers are easier to find than the others. So far I found one suspicious thing in expire_oldest_data().
To be honest, I am not sure how to describe this effectively. It might help to better describe the barriers (what they synchronize (a after b) and where is the counterpart, and why it is needed from some top level point of view).
Of course, the best solution is an easy to follow code. This brings me to the next section.
3. Ideas
--------
I started reading your code and I though that it must have been possible to write it a more straightforward way. I tried it and reached many dead ends so far ;-) But it helped me to better understand your code.
I have not given up yet and would like to give it some more time. Unfortunately, I will not have much time the next week.
Anyway, I am trying to:
+ use the array of descriptors as a ring buffer (no list, no id, only the sequence number)
+ distinguish the state of the data by some flags in struct prb_desc to avoid complicated and tricky checks
It seems that the ring buffer of descriptors really makes things easier.
Regarding the flags. I have something like:
struct prb_desc
{
unsigned long seq;
bool committed;
bool freed;
}The basic idea with the flags is that they are valid only when the seq number in the structure is valid. The newly reserved struct prb_desc is written the following way:
static void prb_init_desc(struct prb_desc *desc)
{
desc->committed = false;
desc->freed = false;
/*
* Flags must be cleared before we tell others that they
* are for this sequence number.
*/
smp_wmb();
desc->seq = seq;
}Then we could have checks like:
/*
* Used by readers to check if the data are valid.
* It has to be called twice (before and after)
* to make sure that the read data are valid. */
static bool prb_data_valid(struct printk_ringbuffer *rb,
unsigned long seq)
{
static prb_desc *desc = TO_DESC(rb, seq);
if (READ_ONCE(desc->seq) != seq)
false;
/* Do not read outdated flags, see prb_init_desc()
smp_rmb();
return READ_ONCE(desc->committed) && !READ_ONCE(desc->freed);
}I am not sure if these extra flags are really needed and useful. This is why I play with it myself. I do not want to ask you to spend a lot of time with my crazy ideas.
Anyway, the above approach looked promising until I tried to to free data from the data array. The problem is how to prove that the sequence number read from the data array is not a garbage. BTW: I think that your expire_oldest_data() is buggy from this point of view, see below.
I think that it might be much more safe when we mask the two highest bits of seq number and use them for the flags. Then we could track the state of the given sequence number a very safe and straightforward way.
Finally, here are some comments about the original patch:
Quoted 1 line · John Ogness
See documentation for details.
Please, mention here some basics. It might be enough to copy the following sections from the documentation:
Overview
Features
Behavior
Note that the documentation is written via .rst file. You need to build html or pdf to get all the pieces together.
Quoted 6 lines
include/linux/printk_ringbuffer.h new file +0
-0
include/linux/printk_ringbuffer.h line 10
Quoted 10 lines
include/linux/printk_ringbuffer.h new file +10
-0@@ -0,0 +1,238 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_PRINTK_RINGBUFFER_H +#define _LINUX_PRINTK_RINGBUFFER_H + +#include <linux/atomic.h> + +/** +* struct prb_list - An abstract linked list of items. +* @oldest: The oldest item on the list. +* @newest: The newest item on the list.
I admit that I got confused by this. I wonder if there is another location in kernel where lists are handled this way.
I have always seen in kernel only lists handled via the struct list_head trick. Where the same structure is bundled in all linked members.
I can't find a good name. I would personally remove the structure and add the members into the relates structures directly.
Also I would personally use "first" and "last" because they are shorter and easier to visually distinguish. I know that "oldest" and "newest" are more clear but...
include/linux/printk_ringbuffer.h line 12
Quoted 2 lines
include/linux/printk_ringbuffer.h new file +2
-0+/** +* struct prb_descr - A descriptor representing an entry in the ringbuffer.
I agree with Peter that "desc" is a better shortcut.
include/linux/printk_ringbuffer.h line 35
Quoted 7 lines
include/linux/printk_ringbuffer.h new file +7
-0+* @seq: The sequence number of the entry. +* @id: The descriptor id. +* The location of the descriptor within the descriptor array can be +* determined from this value. +* @data: The logical position of the data for this entry. +* The location of the beginning of the data within the data array +* can be determined from this value.
I was quite confused by this name. Please, use "lpos". It will make clear that it is the logical position. Also it will be clear that desc->data is the same as lpos used on other location in the code.
include/linux/printk_ringbuffer.h line 38
Quoted 3 lines
include/linux/printk_ringbuffer.h new file +3
-0+* @data_next: The logical position of the data next to this entry. +* This is used to determine the length of the data as well as +* identify where the next data begins.
next_lpos
Quoted 9 lines
include/linux/printk_ringbuffer.h new file +9
-0+* @next: The id of the next (newer) descriptor in the linked list. +* A value of EOL means it is the last descriptor in the list. +* +* Descriptors are used to identify where the data for each entry is and +* also provide an ordering for readers. Entry ordering is based on the +* descriptor linked list (not the ordering of data in the data array). +*/ +struct prb_descr { +/* private */
include/linux/printk_ringbuffer.h line 57
Quoted 10 lines
include/linux/printk_ringbuffer.h new file +10
-0+u64 seq; +unsigned long id; +unsigned long data; +unsigned long data_next; +unsigned long next; +}; + +/** +* struct printk_ringbuffer - The ringbuffer structure. +* @data_array_size_bits: The size of the data array as a power-of-2.
I would use "data_size_bits"
include/linux/printk_ringbuffer.h line 58
Quoted 1 line
include/linux/printk_ringbuffer.h new file +1
-0+* @data_array: A pointer to the data array.
and "data"
include/linux/printk_ringbuffer.h line 63
Quoted 5 lines
include/linux/printk_ringbuffer.h new file +5
-0+* @data_list: A list of entry data. +* Since the data list is not traversed, this list is only used to +* mark the contiguous section of the data array that is in use. +* @descr_max_count: The maximum amount of descriptors allowed. +* @descr_array: A pointer to the descriptor array.
descs?
include/linux/printk_ringbuffer.h line 233
Quoted 11 lines
include/linux/printk_ringbuffer.h new file +11
-0+/** +* prb_for_each_entry() - Iterate through all the entries of a ringbuffer. +* @i: A pointer to an iterator. +* @l: An integer used to identify when the last entry is traversed. +* +* This macro expects the iterator to be initialized. It also does not reset +* the iterator. So if the iterator has already been used for some traversal, +* this macro will continue where the iterator left off. +*/ +#define prb_for_each_entry (i, l) \ + for (; (l = prb_iter_next_valid_entry(i)) != 0;)
This is very unusual semantic. Please, define two iterators:
prb_for_each_entry() - iterate over all entries prb_for_each_entry_continue() - iterate from the gived entry
Quoted 29 lines
include/linux/printk_ringbuffer.h new file +29
-0+/** +* expire_oldest_data() - Invalidate the oldest data block. +* @rb: The ringbuffer containing the data block. +* @oldest_lpos: The logical position of the oldest data block. +* +* This function expects to "push" the pointer to the oldest data block +* forward, thus invalidating the oldest data block. However, before pushing, +* it is verified if the data block is valid. (For example, if the data block +* was reserved but not yet committed, it is not permitted to invalidate the +* "in use by a writer" data.) +* +* If the data is valid, it will be associated with a descriptor, which will +* then provide the necessary information to validate the data. +* +* Return: true if the oldest data was invalidated (regardless if this +* task was the one that did it or not), otherwise false. +*/ +static bool expire_oldest_data (struct printk_ringbuffer *rb, +unsigned long oldest_lpos) +{ +unsigned long newest_lpos; +struct prb_datablock *b; +unsigned long data_next; +struct prb_descr *d; +unsigned long data; + +/* MB2: synchronize data reservation */ + newest_lpos =smp_load_acquire (&rb->data_list.newest); +
include/linux/printk_ringbuffer.h line 97
Quoted 10 lines
include/linux/printk_ringbuffer.h new file +10
-0+ b =TO_DATABLOCK (rb, oldest_lpos); + +/* MB3: synchronize descr setup */ + d =TO_DESCR (rb,smp_load_acquire (&b->id)); + + data =READ_ONCE (d->data); + +/* sanity check to check to see if b->id was correct */ +if (oldest_lpos != data) + goto out;
Is this cross check really enough?
How is it ensured that the data are committed?
How is it ensured that the descriptor is not an outdated one?
IMHO, there might be a garbage in the data array. It might be chance point to an outdated descriptor that by chance pointed to this data range in the past. I agree that it is very unlikely. But we could not afford such a risk.
Quoted 4 lines
include/linux/printk_ringbuffer.h new file +4
-0+/* MB4: synchronize commit */ + data_next =smp_load_acquire (&d->data_next); + +if (!data_valid (rb, oldest_lpos, newest_lpos, data, data_next))
include/linux/printk_ringbuffer.h line 111
Quoted 10 lines
include/linux/printk_ringbuffer.h new file +10
-0+ goto out; + +/* MB1: synchronize data invalidation */ +cmpxchg_release (&rb->data_list.oldest, data, data_next); + +/* Some task (maybe this one) successfully expired the oldest data. */ +return true; +out: +return (oldest_lpos !=READ_ONCE (rb->data_list.oldest)); +}
Best Regards,
Petr
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Hi Petr,
Quoted 3 lines · Petr Mladek
I am still scratching head around this. Anyway, I wanted to write something. I am sorry that the answer is really long. I do not know how to write it more effectively.
No need to apologize (to me) for long answers.
Quoted 7 lines
1. Linked list of descriptors
-----------------------------The list of descriptors makes the code more complicated and I do not see much gain. It is possible that I just missed something.
Quoted 7 lines
If I get it correctly then the list could only grow by adding never used members. The already added members are newer removed neither shuffled.
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
So you are suggesting using a multi-reader multi-writer lockless ringbuffer to implement a multi-reader multi-writer lockless ringbuffer. ;-)
The descriptor ringbuffer has fixed-size items, which simplifies the task. But I expect you will run into a chicken-egg scenario.
Quoted 5 lines
It would allow to remove:
+
desc->idbecause it will be the same asdesc->seq
+desc->nextbecause the address of the next member can be easily counted
Yes, you will remove these and then replace them with new variables to track array-element state.
Quoted 7 lines
2. Consistency, barriers, and code structure
--------------------------------------------I haven't got the whole picture about the code logic so far. Maybe I haven't tried hard enough. I actually spent quite some time with playing with some alternatives.
Quoted 5 lines
In each case, the code is very complicated (of course, the problem is complicated):
+ 6 steps (barriers) are needed to synchronize writers. This means a lot of variants of possible races.
Agreed. The writer documentation explains those 6 steps, which are 6 atomic operations. I am not sure if you would be able to reduce the 6 steps by using a descriptor ringbuffer. Instead of cmpxchg'ing list pointers you will be cmpxchg'ing state variables.
Using litmus tests and lots of testing on SMP arm64, I have been able hit and address these races (i.e. removing one of the barriers causes the test module to fail on SMP arm64). But if we can simplify the design, that would certainly help to deal with races.
Quoted 4 lines
+ The six barriers are somehow related to 6 variables. But there are several other variables that are being modified. It is needed to check that they can be safely modified/read on the given locations.
Here are the writer-relevant memory barriers and their associated variables:
MB1: data_list.oldest
MB2: data_list.newest
MB3: data_block.id
MB4: descr.data_next
MB5: descr_list.newest
MB6: descr.next
The only other variables that I see as relevant are:
descr.id: This variable is used often and is quite important (the basis for linked lists and descriptor validation). I will go through all its uses again. My memory barrier comments should definitely include this variable in their explanations.
descr.data: This is set when the descriptor is not part of the list and is indirectly synchronized by MB3 (written before store_release of data_block.id and loaded as data dependent on the load_acquire of data_block.id).
descr.seq: This is set when the descriptor is not part of the list and is indirectly synchronized by MB5 (written before store_release of descr_list.newest and loaded as data dependent on the load_acquire of descr_list.newest).
descr_list.oldest: As I explained[0] to Peter, this variable is indirectly synchronized by MB6 when there is only 1 descriptor on the list (which is not the normal case). Otherwise it has no synchronization. This could lead to a writer unnecessarily trying multiple times to remove the oldest descriptor because of failed cmpxchg() calls. But that isn't really an issue. (And now revisiting remove_oldest_descr() I see I can pull the READ_ONCE(l->oldest) out of the loop and use the cmpxchg() return value for the next iteration.)
Are there any other variables that you are referring to?
Quoted 11 lines
OK, the structures have a livecycle:
+ descriptor:
+ free
+ taken+ data block:
+ reserved
+ committed
+ correctly read
+ freed
IMO, it is:
+ descriptor:
+ free
+ taken
+ valid (i.e. data/data_next have been set by the writer)
+ data block:
+ reserved
+ committed
+ invalid/garbage
Quoted 91 lines
And there are few basic questions about each state:
+ where and how the state is set
+ where and how it is invalidated
+ where and how the state is checked in other code
+ how is it achieved that the state is the same as long as neededSome of the answers are easier to find than the others. So far I found one suspicious thing in
expire_oldest_data().To be honest, I am not sure how to describe this effectively. It might help to better describe the barriers (what they synchronize (a after b) and where is the counterpart, and why it is needed from some top level point of view).
Of course, the best solution is an easy to follow code. This brings me to the next section.
3. Ideas
--------I started reading your code and I though that it must have been possible to write it a more straightforward way. I tried it and reached many dead ends so far ;-) But it helped me to better understand your code.
I have not given up yet and would like to give it some more time. Unfortunately, I will not have much time the next week.
Anyway, I am trying to:
+ use the array of descriptors as a ring buffer (no list, no id, only the sequence number)
+ distinguish the state of the data by some flags in struct
prb_descto avoid complicated and tricky checksIt seems that the ring buffer of descriptors really makes things easier.
Regarding the flags. I have something like:
struct
prb_desc{ unsigned long seq; bool committed; bool freed; }The basic idea with the flags is that they are valid only when the seq number in the structure is valid. The newly reserved struct
prb_descis written the following way:static void
prb_init_desc(struct prb_desc *desc){ desc->committed = false; desc->freed = false; /* * Flags must be cleared before we tell others that they * are for this sequence number. */ smp_wmb(); desc->seq = seq; }Then we could have checks like:
/*
* Used by readers to check if the data are valid.
* It has to be called twice (before and after)
* to make sure that the read data are valid. */
static bool prb_data_valid(structprintk_ringbuffer*rb,
unsigned long seq){ static prb_desc *desc = TO_DESC(rb, seq); if (READ_ONCE(desc->seq) != seq) false; /* Do not read outdated flags, see prb_init_desc() smp_rmb(); return READ_ONCE(desc->committed) && !READ_ONCE(desc->freed); }
Quoted 3 lines
I am not sure if these extra flags are really needed and useful. This is why I play with it myself. I do not want to ask you to spend a lot of time with my crazy ideas.
But thank you for sharing them. I always welcome new ideas.
Quoted 5 lines
Anyway, the above approach looked promising until I tried to to free data from the data array. The problem is how to prove that the sequence number read from the data array is not a garbage. BTW: I think that your
expire_oldest_data()is buggy from this point of view, see below.
You do point out an issue for 32-bit systems. Below I include an explanation and patch.
Quoted 4 lines
I think that it might be much more safe when we mask the two highest bits of seq number and use them for the flags. Then we could track the state of the given sequence number a very safe and straightforward way.
When I first started to design/code this, I implemented something quite
similar: using a single variable to represent state and id. This works nicely for cmpxchg operations (lockless synchronization) and reader validation. The problem I ran into was a chicken-egg problem (which I suspect you will also run into).
I solved this problem by changing the design to use a linked list for the descriptors. At first I had kept state information for each descriptor. But later I realized that state information was not necessary because the linked list itself was providing implicit state information.
I do not claim that using linked lists for the descriptors is absolutely necessary. But it was the only way that I could figure out how to make everything work. Now that I have something that works (and the experience of getting it there), maybe I could make it work without a linked list. I will let the idea simmer on my brain in the background and I am following your experimentation/ideas with great curiosity.
Quoted 11 lines
Finally, here are some comments about the original patch:
Quoted 1 line · John Ogness
See documentation for details.
Please, mention here some basics. It might be enough to copy the following sections from the documentation:
Overview
Features
Behavior
Ugh. Do we really want all that in a commit message?
Quoted 2 lines
Note that the documentation is written via .rst file. You need to build html or pdf to get all the pieces together.
Yes, but isn't that how all the kernel docs are supposed to be for the future?
Quoted 20 lines
Quoted 6 lines
include/linux/printk_ringbuffer.h new file +0
-0include/linux/printk_ringbuffer.h line 10
Quoted 10 lines
include/linux/printk_ringbuffer.h new file +10
-0@@ -0,0 +1,238 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _LINUX_PRINTK_RINGBUFFER_H +#define _LINUX_PRINTK_RINGBUFFER_H + +#include <linux/atomic.h> + +/** +* struct prb_list - An abstract linked list of items. +* @oldest: The oldest item on the list. +* @newest: The newest item on the list. I admit that I got confused by this. I wonder if there is another location in kernel where lists are handled this way.
Quoted 6 lines
I have always seen in kernel only lists handled via the struct
list_headtrick. Where the same structure is bundled in all linked members.I can't find a good name. I would personally remove the structure and add the members into the relates structures directly.
The only reason I made it a struct is so that I could just write l->oldest instead of rb->descr_list_oldest. But it is an otherwise useless struct that I can remove.
Quoted 3 lines
Also I would personally use "first" and "last" because they are shorter and easier to visually distinguish. I know that "oldest" and "newest" are more clear but...
I don't like "oldest" and "newest" either, but it is immediately clear. How about:
rb->data_lpos_oldest (formerly rb->data_list.oldest) rb->data_lpos_newest (formerly rb->data_list.newest) rb->desc_id_oldest (formerly rb->descr_list.oldest) rb->desc_id_newest (formerly rb->descr_list.newest)
If using the strings "oldest" and "newest" are too ugly for people, I have no problems using first/last or head/tail, even if IMHO they add unnecessary confusion.
Quoted 4 lines
include/linux/printk_ringbuffer.h line 12
Quoted 2 lines
include/linux/printk_ringbuffer.h new file +2
-0+/** +* struct prb_descr - A descriptor representing an entry in the ringbuffer. I agree with Peter that "desc" is a better shortcut.
OK.
Quoted 8 lines
include/linux/printk_ringbuffer.h line 19
Quoted 7 lines
include/linux/printk_ringbuffer.h new file +7
-0+* @seq: The sequence number of the entry. +* @id: The descriptor id. +* The location of the descriptor within the descriptor array can be +* determined from this value. +* @data: The logical position of the data for this entry. +* The location of the beginning of the data within the data array +* can be determined from this value.
Quoted 4 lines
I was quite confused by this name. Please, use "lpos". It will make clear that it is the logical position. Also it will be clear that
desc->datais the same as lpos used on other location in the code.
Agreed.
Quoted 5 lines
include/linux/printk_ringbuffer.h line 22
Quoted 3 lines
include/linux/printk_ringbuffer.h new file +3
-0+* @data_next: The logical position of the data next to this entry. +* This is used to determine the length of the data as well as +* identify where the next data begins.
next_lpos
How about lpos_next?
Quoted 13 lines
Quoted 13 lines
include/linux/printk_ringbuffer.h new file +13
-0+* @next: The id of the next (newer) descriptor in the linked list. +* A value of EOL means it is the last descriptor in the list. +* +* Descriptors are used to identify where the data for each entry is and +* also provide an ordering for readers. Entry ordering is based on the +* descriptor linked list (not the ordering of data in the data array). +*/ +struct prb_descr { +/* private */ +u64 seq; +unsigned long id; +unsigned long data; +unsigned long data_next;
Quoted 8 lines
include/linux/printk_ringbuffer.h line 41
Quoted 6 lines
include/linux/printk_ringbuffer.h new file +6
-0+unsigned long next; +}; + +/** +* struct printk_ringbuffer - The ringbuffer structure. +* @data_array_size_bits: The size of the data array as a power-of-2. I would use "
data_size_bits"
OK.
Quoted 3 lines
include/linux/printk_ringbuffer.h line 42
Quoted 1 line
include/linux/printk_ringbuffer.h new file +1
-0+* @data_array: A pointer to the data array. and "data"
OK.
Quoted 7 lines
include/linux/printk_ringbuffer.h line 47
Quoted 5 lines
include/linux/printk_ringbuffer.h new file +5
-0+* @data_list: A list of entry data. +* Since the data list is not traversed, this list is only used to +* mark the contiguous section of the data array that is in use. +* @descr_max_count: The maximum amount of descriptors allowed. +* @descr_array: A pointer to the descriptor array. descs?
OK.
Quoted 14 lines
include/linux/printk_ringbuffer.h line 58
Quoted 11 lines
include/linux/printk_ringbuffer.h new file +11
-0+/** +* prb_for_each_entry() - Iterate through all the entries of a ringbuffer. +* @i: A pointer to an iterator. +* @l: An integer used to identify when the last entry is traversed. +* +* This macro expects the iterator to be initialized. It also does not reset +* the iterator. So if the iterator has already been used for some traversal, +* this macro will continue where the iterator left off. +*/ +#define prb_for_each_entry (i, l) \ + for (; (l = prb_iter_next_valid_entry(i)) != 0;)This is very unusual semantic. Please, define two iterators:
Quoted 2 lines
prb_for_each_entry()- iterate over all entriesprb_for_each_entry_continue()- iterate from the gived entry
OK.
Quoted 33 lines
Quoted 33 lines
include/linux/printk_ringbuffer.h new file +33
-0+/** +* expire_oldest_data() - Invalidate the oldest data block. +* @rb: The ringbuffer containing the data block. +* @oldest_lpos: The logical position of the oldest data block. +* +* This function expects to "push" the pointer to the oldest data block +* forward, thus invalidating the oldest data block. However, before pushing, +* it is verified if the data block is valid. (For example, if the data block +* was reserved but not yet committed, it is not permitted to invalidate the +* "in use by a writer" data.) +* +* If the data is valid, it will be associated with a descriptor, which will +* then provide the necessary information to validate the data. +* +* Return: true if the oldest data was invalidated (regardless if this +* task was the one that did it or not), otherwise false. +*/ +static bool expire_oldest_data (struct printk_ringbuffer *rb, +unsigned long oldest_lpos) +{ +unsigned long newest_lpos; +struct prb_datablock *b; +unsigned long data_next; +struct prb_descr *d; +unsigned long data; + +/* MB2: synchronize data reservation */ + newest_lpos =smp_load_acquire (&rb->data_list.newest); + + b =TO_DATABLOCK (rb, oldest_lpos); + +/* MB3: synchronize descr setup */ + d =TO_DESCR (rb,smp_load_acquire (&b->id));
Quoted 8 lines
include/linux/printk_ringbuffer.h line 97
Quoted 6 lines
include/linux/printk_ringbuffer.h new file +6
-0+ + data =READ_ONCE (d->data); + +/* sanity check to check to see if b->id was correct */ +if (oldest_lpos != data) + goto out;Is this cross check really enough?
This is only a cheap sanity check to filter out most garbage. However, it still is not a guarantee that b is valid. At this point d could be some random descriptor that by chance is pointing to the loaded oldest value.
Quoted 1 line
How is it ensured that the data are committed?
The following data_valid() call checks this. If it is valid, it is committed.
Quoted 6 lines
How is it ensured that the descriptor is not an outdated one?
IMHO, there might be a garbage in the data array. It might be chance point to an outdated descriptor that by chance pointed to this data range in the past. I agree that it is very unlikely. But we could not afford such a risk.
An outdated descriptor that has a data value (lpos) matching the oldest (lpos) would mean that the lpos has completely wrapped (4GB of data on a 32-bit system) without the descriptor having been recycled. It should be possible to force such a situation on a 32-bit system, so this issue does need to be addressed. Thanks.
Quoted 6 lines
Quoted 6 lines
include/linux/printk_ringbuffer.h new file +6
-0+/* MB4: synchronize commit */ + data_next =smp_load_acquire (&d->data_next); + +if (!data_valid (rb, oldest_lpos, newest_lpos, data, data_next)) + goto out; +
Quoted 8 lines
include/linux/printk_ringbuffer.h line 111
Quoted 8 lines
include/linux/printk_ringbuffer.h new file +8
-0+/* MB1: synchronize data invalidation */ +cmpxchg_release (&rb->data_list.oldest, data, data_next); + +/* Some task (maybe this one) successfully expired the oldest data. */ +return true; +out: +return (oldest_lpos !=READ_ONCE (rb->data_list.oldest)); +}
Currently the descriptor's data/data_next values are left "as is" until they are used again. This creates the risk (really only on 32-bit systems) that in the case of a complete unsigned long wrap around while never reusing that descriptor, random (or specially crafted) data during a writer race to expire the oldest data could be read that point to that unused descriptor where its data (lpos) is the same as oldest (lpos) but data_next is not valid. This would corrupt the data array.
To avoid this, explicitly make the descriptor invalid (independent of any future oldest/newest values) after expiring the data.
lib/printk_ringbuffer.c +10 -1
@@ -451,7 +451,16 @@ static bool expire_oldest_data(struct printk_ringbuffer *rb, goto out;/* MB1: synchronize data invalidation */ -cmpxchg_release (&rb->data_list.oldest, data, data_next); +if (cmpxchg_release (&rb->data_list.oldest, data, data_next) == data) { +/* +* Set data_next to match data so the descriptor is invalid. +* This avoids the possibility of mistaking it as valid in +* case of a full lpos value wrap around. +* +* If this fails, the descriptor has already been recycled. +*/ +cmpxchg (&d->data_next, data_next, data); + }/* Some task (maybe this one) successfully expired the oldest data. */ return true;
John Ogness
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 10 lines · John Ogness
Quoted 10 lines
1. Linked list of descriptors
-----------------------------The list of descriptors makes the code more complicated and I do not see much gain. It is possible that I just missed something.
If I get it correctly then the list could only grow by adding never used members. The already added members are newer removed neither shuffled.
Is the above paragraph correct, please?
Quoted 10 lines
Quoted 3 lines
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
So you are suggesting using a multi-reader multi-writer lockless ringbuffer to implement a multi-reader multi-writer lockless ringbuffer. ;-)
The descriptor ringbuffer has fixed-size items, which simplifies the task. But I expect you will run into a chicken-egg scenario.
AFAIK, the main obstacle with the fully lockless solution was that the entries did not have a fixed size.
If I understand it correctly, the list works exactly as a ring buffer once all available descriptors are used.
Quoted 8 lines
Quoted 5 lines
It would allow to remove:
+
desc->idbecause it will be the same asdesc->seq
+desc->nextbecause the address of the next member can be easily countedYes, you will remove these and then replace them with new variables to track array-element state.
Yes, it should easier to understand that, for example, a descriptor is free by a flag named "free" than by some magic check of links.
It is not must to have. But the code is complicated. Anything that might make it easier to understand is much appreciated.
Quoted 10 lines
Quoted 4 lines
I think that it might be much more safe when we mask the two highest bits of seq number and use them for the flags. Then we could track the state of the given sequence number a very safe and straightforward way.
When I first started to design/code this, I implemented something quite
similar: using a single variable to represent state and id. This works nicely for cmpxchg operations (lockless synchronization) and reader validation. The problem I ran into was a chicken-egg problem (which I suspect you will also run into).
Do you remember more details about the chicken-egg problem, please? I believe that there might be one. Any hint just could save me quite some time.
I have hit two big dead ends so far:
1. I was not able to free data when there was no free descriptor and free descriptor when the data have already been freed. I was not able to make both operations race-free.
I got inspiration from remove_oldest_descr() and solved this by failing to get descriptor when there was no free one.
But it is possible that I just did not try hard enough. I see that your code is actually able to free the data and descriptor from assign_descriptor().
2. I was not able to free the oldest data. I did not know how to make sure that the seq read from the data buffer was valid.
My plan was to solve this by changing seq and state flags in the descriptor atomically. Then I would just check whether the seq was in valid bounds (I would ignore overflow) and that the flag "committed" was set. Then I would just set the flag "freed". The descriptor itself would be freed from prb_get_desc().
But I might actually use similar approach like you are using in expire_oldest_data(). We could assume that as long as the desc->seq is within valid bounds (rb->first_seq <= seq <= rb->last_seq) then it is the right descriptor.
Quoted 5 lines
I solved this problem by changing the design to use a linked list for the descriptors. At first I had kept state information for each descriptor. But later I realized that state information was not necessary because the linked list itself was providing implicit state information.
And this is my problem. I do not see how the list itself provides the state information. Especially I do not see how it distinguishes reserved and commited state, for example, from expire_oldest_data() point of view.
Quoted 5 lines
Quoted 5 lines
Finally, here are some comments about the original patch:
Quoted 1 line · John Ogness
See documentation for details.
Quoted 8 lines
Quoted 6 lines
Please, mention here some basics. It might be enough to copy the following sections from the documentation:
Overview
Features
BehaviorUgh. Do we really want all that in a commit message?
2-3 pages of text for such a complicated commit is perfectly fine. You could not build html/pdf variant easily when reading "git log -p".
Quoted 5 lines
Quoted 2 lines
Note that the documentation is written via .rst file. You need to build html or pdf to get all the pieces together.
Yes, but isn't that how all the kernel docs are supposed to be for the future?
I could not talk for others. I have personally built the html version for the first time just few weeks ago. And it was only because I reviewed conversion of livepatch related documentation into rst.
I normally search for information using "cscope in emacs", "git blame", "git log -p", "git grep", and "google in web browser". I much prefer to find the information in the code sources or in the related commit message.
Quoted 12 lines
Quoted 12 lines
Quoted 4 lines
+/**
+ * structprb_list- An abstract linked list of items.
+ * @oldest: The oldest item on the list.
+ * @newest: The newest item on the list.I admit that I got confused by this. I wonder if there is another location in kernel where lists are handled this way.
I have always seen in kernel only lists handled via the struct
list_headtrick. Where the same structure is bundled in all linked members.
Quoted 6 lines
Quoted 2 lines
I can't find a good name. I would personally remove the structure and add the members into the relates structures directly.
The only reason I made it a struct is so that I could just write
l->oldestinstead ofrb->descr_list_oldest. But it is an otherwise useless struct that I can remove.
rb->last_lpos and rb->last_seq are short enough. And it is clear what exactly is being compared.
Quoted 7 lines
Quoted 3 lines
Also I would personally use "first" and "last" because they are shorter and easier to visually distinguish. I know that "oldest" and "newest" are more clear but...
I don't like "oldest" and "newest" either, but it is immediately clear. How about:
Quoted 8 lines
rb->data_lpos_oldest(formerlyrb->data_list.oldest)rb->data_lpos_newest(formerlyrb->data_list.newest)rb->desc_id_oldest(formerlyrb->descr_list.oldest)rb->desc_id_newest(formerlyrb->descr_list.newest)If using the strings "oldest" and "newest" are too ugly for people, I have no problems using first/last or head/tail, even if IMHO they add unnecessary confusion.
I do not have strong opinion. I am slightly biased because I am used to "first"/"next" from the current code.
In each case when I compare:
rb->data_lpos_oldest (formerly rb->data_list.oldest) rb->data_lpos_newest (formerly rb->data_list.newest) rb->desc_id_oldest (formerly rb->descr_list.oldest) rb->desc_id_newest (formerly rb->descr_list.newest)
rb->data_lpos_first (formerly rb->data_list.first) rb->data_lpos_last (formerly rb->data_list.last) rb->desc_id_first (formerly rb->descr_list.first) rb->desc_id_last (formerly rb->descr_list.last)
then the 2nd variant helps me to spot the difference and find the valuable information.
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
+ * @data_next: The logical position of the data next to this entry.
+ * This is used to determine the length of the data as well as
+ * identify where the next data begins.
next_lposHow about
lpos_next?
next_lpos looks gramatically more correct. Well, I do not mind as long as the style is consistent all over the code.
Quoted 22 lines
Quoted 22 lines
Quoted 10 lines
(quoted diff) +10
-0+/** + * expire_oldest_data() - Invalidate the oldest data block. + * @rb: The ringbuffer containing the data block. + * @oldest_lpos: The logical position of the oldest data block. + * + * This function expects to "push" the pointer to the oldest data block + * forward, thus invalidating the oldest data block. However, before pushing, + * it is verified if the data block is valid. (For example, if the data block + * was reserved but not yet committed, it is not permitted to invalidate the + * "in use by a writer" data.)Review
Quoted 10 lines
(quoted diff) +10
-0+ * + * If the data is valid, it will be associated with a descriptor, which will + * then provide the necessary information to validate the data. + * + * Return: true if the oldest data was invalidated (regardless if this + * task was the one that did it or not), otherwise false. + */ +static bool expire_oldest_data(struct printk_ringbuffer *rb, + unsigned long oldest_lpos) +{How is it ensured that the descriptor is not an outdated one?
Quoted 8 lines
Quoted 4 lines
IMHO, there might be a garbage in the data array. It might be chance point to an outdated descriptor that by chance pointed to this data range in the past. I agree that it is very unlikely. But we could not afford such a risk.
An outdated descriptor that has a data value (lpos) matching the oldest (lpos) would mean that the lpos has completely wrapped (4GB of data on a 32-bit system) without the descriptor having been recycled.
Ah, I missed that it takes long time until the positions are reused (overflow). It would probably helped me when all the compared variables were called lpos instead of data ;-)
Quoted 3 lines
It should be
possible to force such a situation on a 32-bit system, so this issue does need to be addressed. Thanks.
We might even be able to ignore this because both descriptors and data arrays are reused. It should be impossible to wrap around lpos without wrapping seq and vice versa.
Best Regards,
Petr
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 7 lines · Petr Mladek
Quoted 7 lines
Quoted 7 lines
1. Linked list of descriptors
-----------------------------The list of descriptors makes the code more complicated and I do not see much gain. It is possible that I just missed something.
Quoted 5 lines
Quoted 3 lines
Quoted 3 lines
If I get it correctly then the list could only grow by adding never used members. The already added members are newer removed neither shuffled.
Is the above paragraph correct, please?
Sorry for not addressing this remark. I am trying to be careful and not steer you to a certain implementation. I failed to achieve what you are attempting. You are already doing things slightly different, so my experiences regarding this may falsely discourage you from figuring out how to do it.
To address your question: For the linked list implementation, if you are looking at it from the linked list perspective, the number of descriptors on the list is constantly fluctuating (increasing and decreasing) and the ordering of the descriptors is constantly changing. They are ordered according to the writer commit order (not the writer reserve order) and the only descriptors on the list are the ones that are not within a reserve/commit window.
Quoted 8 lines
Quoted 8 lines
Quoted 3 lines
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
So you are suggesting using a multi-reader multi-writer lockless ringbuffer to implement a multi-reader multi-writer lockless ringbuffer. ;-)
Quoted 5 lines
Quoted 2 lines
The descriptor ringbuffer has fixed-size items, which simplifies the task. But I expect you will run into a chicken-egg scenario.
AFAIK, the main obstacle with the fully lockless solution was that the entries did not have a fixed size.
No. The variable size of the records was the reason I used descriptors. That has nothing to do with how I chose to connect those descriptors.
Quoted 2 lines
If I understand it correctly, the list works exactly as a ring buffer once all available descriptors are used.
There are a lot of details hiding in the words "exactly as a ring buffer". We are talking about a (truly) lockless ringbuffer that supports concurrent writers. (IMO my v1 rfc ringbuffer was not truly lockless because of the prb_lock.) AFAIK there is no such ringbuffer implementation in existence, otherwise I would have used that instead of writing my own.
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
It would allow to remove:
+
desc->idbecause it will be the same asdesc->seq
+desc->nextbecause the address of the next member can be easily counted
Quoted 8 lines
Quoted 2 lines
Yes, you will remove these and then replace them with new variables to track array-element state.
Yes, it should easier to understand that, for example, a descriptor is free by a flag named "free" than by some magic check of links.
It is not must to have. But the code is complicated. Anything that might make it easier to understand is much appreciated.
I think it is not as simple as you think it is and I expect you will end up with a solution that is more complex (although I could be wrong). IMHO the linked list solution is quite elegant. Perhaps the real problem is my coding style, poor naming, and horrible comments.
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
I think that it might be much more safe when we mask the two highest bits of seq number and use them for the flags. Then we could track the state of the given sequence number a very safe and straightforward way.
Quoted 7 lines
Quoted 5 lines
When I first started to design/code this, I implemented something quite similar: using a single variable to represent state and id. This works nicely for cmpxchg operations (lockless synchronization) and reader validation. The problem I ran into was a chicken-egg problem (which I suspect you will also run into).
Do you remember more details about the chicken-egg problem, please?
You really already answered your own question when you stated:
"we could achieve similar result when using the array
as a circular buffer"
That circular buffer must have the same features as the circular buffer we are trying to implement. My choice to use a linked list was not due to variable sized records, but rather that is the only way I could figure out how to implement a lockless multi-writer multi-reader ringbuffer.
Again, that doesn't mean it isn't possible. But _I_ could not get it to work. I had all kinds of state tracking and crazy cmpxchg loops and wacky races. Switching to linked lists made everything so much simpler and straight forward. (Many thanks my colleague Benedikt Spranger for coming up with the idea!)
Quoted 8 lines
I believe that there might be one. Any hint just could save me quite some time.
I have hit two big dead ends so far:
1. I was not able to free data when there was no free descriptor and free descriptor when the data have already been freed. I was not able to make both operations race-free.
This is why I reserve the descriptor before reserving the data, so that this situation can never occur.
Note that invalid descriptors in the linked list do not act as terminators for readers. The readers simply traverse over the invalid descriptors until they hit an EOL.
Quoted 19 lines
I got inspiration from
remove_oldest_descr()and solved this by failing to get descriptor when there was no free one.But it is possible that I just did not try hard enough. I see that your code is actually able to free the data and descriptor from
assign_descriptor().2. I was not able to free the oldest data. I did not know how to make sure that the seq read from the data buffer was valid.
My plan was to solve this by changing seq and state flags in the descriptor atomically. Then I would just check whether the seq was in valid bounds (I would ignore overflow) and that the flag "committed" was set. Then I would just set the flag "freed". The descriptor itself would be freed from
prb_get_desc().
Quoted 5 lines
But I might actually use similar approach like you are using in
expire_oldest_data(). We could assume that as long as thedesc->seqis within valid bounds (rb->first_seq<= seq <=rb->last_seq) then it is the right descriptor.
desc->seq is not some random data. If it is >= rb->first_seq (and points back to the same data block!), it is what you are looking for.
Quoted 10 lines
Quoted 5 lines
I solved this problem by changing the design to use a linked list for the descriptors. At first I had kept state information for each descriptor. But later I realized that state information was not necessary because the linked list itself was providing implicit state information.
And this is my problem. I do not see how the list itself provides the state information. Especially I do not see how it distinguishes reserved and commited state, for example, from
expire_oldest_data()point of view.
_All_ descriptors on the linked list are not within the reserve/commit window and no writers have pointers to them. (The only exception is the newest descriptor, whose next will be modified by a writer that is adding a new descriptor. That is the reason that if there is only 1 descriptor on the list, it must not be removed. A writer might be modifying its next.)
When a writer wants to reserve data (i.e. enter the reserve/commit window), the first thing it must do is pull a descriptor off the list. With the descriptor off the list, the writer is free to do whatever it needs to do to prepare the data and the descriptor. And when it is done committing (i.e. exiting the reserve/commit window), the last thing it does is add the ready descriptor to the list.
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Finally, here are some comments about the original patch:
Quoted 1 line · John Ogness
See documentation for details.
Please, mention here some basics. It might be enough to copy the following sections from the documentation:
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
Overview
Features
BehaviorUgh. Do we really want all that in a commit message?
2-3 pages of text for such a complicated commit is perfectly fine. You could not build html/pdf variant easily when reading "git log -p".
OK.
Quoted 9 lines
Quoted 5 lines
Quoted 2 lines
Note that the documentation is written via .rst file. You need to build html or pdf to get all the pieces together.
Yes, but isn't that how all the kernel docs are supposed to be for the future?
I could not talk for others. I have personally built the html version for the first time just few weeks ago. And it was only because I reviewed conversion of livepatch related documentation into rst.
I also built it for the first time so that I could document this series.
Quoted 4 lines
I normally search for information using "cscope in emacs", "git blame", "git log -p", "git grep", and "google in web browser". I much prefer to find the information in the code sources or in the related commit message.
There is an obvious push to get the kernel docs unified under RST, even if it is not how I usually do things either. However, now that I've done the work, looking back it seems to be a good idea in order to automate documentation.
Quoted 6 lines
Quoted 3 lines
If using the strings "oldest" and "newest" are too ugly for people, I have no problems using first/last or head/tail, even if IMHO they add unnecessary confusion.
I do not have strong opinion. I am slightly biased because I am used to "first"/"next" from the current code.
But are you used to starting with last and traversing next to first? The descriptors and data blocks are linked from oldest to newest. IMHO that is why it tends to be confusing.
In circular buffer speak, writers write to the head and readers read from the tail. As a writer this feels natural, but for a reader that reads the tail and follows next pointers to the head, it feels backwards.
I explicitly wanted to get away from any preconceptions. By specifying we have data linked from oldest to newest, I find it feels more natural, regardless if I am a writer writing new records to the newest or a reader reading all records from oldest to newest.
John Ogness
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 7 lines · John Ogness
To address your question: For the linked list implementation, if you are looking at it from the linked list perspective, the number of descriptors on the list is constantly fluctuating (increasing and decreasing) and the ordering of the descriptors is constantly changing. They are ordered according to the writer commit order (not the writer reserve order) and the only descriptors on the list are the ones that are not within a reserve/commit window.
This and few other comments below are really valuable explanation. I misunderstood how the list worked. I have to revisit it and rethink my view on the patchset.
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines
Quoted 3 lines
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
So you are suggesting using a multi-reader multi-writer lockless ringbuffer to implement a multi-reader multi-writer lockless ringbuffer. ;-)
The descriptor ringbuffer has fixed-size items, which simplifies the task. But I expect you will run into a chicken-egg scenario.
Quoted 6 lines
Quoted 2 lines
AFAIK, the main obstacle with the fully lockless solution was that the entries did not have a fixed size.
No. The variable size of the records was the reason I used descriptors. That has nothing to do with how I chose to connect those descriptors.
I think that we are talking about the same. If I remember correctly, the main problem is that cmpxchg() is not reliable when the same address might be used by the metadata and data.
For example, the code never know if it compared previous seq number of it another CPU/NMI wrote there data (string) in the meantime.
Quoted 3 lines
I think it is not as simple as you think it is and I expect you will end up with a solution that is more complex (although I could be wrong). IMHO the linked list solution is quite elegant.
It is quite likely.
Quoted 4 lines
There is an obvious push to get the kernel docs unified under RST, even if it is not how I usually do things either. However, now that I've done the work, looking back it seems to be a good idea in order to automate documentation.
I personally like /** */ description of public API functions. Also html/pdf version looks nice even though I do not use them.
The thing is that both /** */ and .rst formats can be well readable even in the source code. I guess that most existing developers read only the source code.
Well, this discussion probably belongs to another thread. My wish was just to make the commit message more verbose, please.
Quoted 4 lines
I explicitly wanted to get away from any preconceptions. By specifying we have data linked from oldest to newest, I find it feels more natural, regardless if I am a writer writing new records to the newest or a reader reading all records from oldest to newest.
As I said, I do not have strong opinion. I could live with oldest, newest.
Best Regards,
Petr
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 10 lines · Petr Mladek
Quoted 7 lines
To address your question: For the linked list implementation, if you are looking at it from the linked list perspective, the number of descriptors on the list is constantly fluctuating (increasing and decreasing) and the ordering of the descriptors is constantly changing. They are ordered according to the writer commit order (not the writer reserve order) and the only descriptors on the list are the ones that are not within a reserve/commit window.
This and few other comments below are really valuable explanation. I misunderstood how the list worked.
I will add a documentation section about why a linked list was used.
Quoted 14 lines
Quoted 14 lines
Quoted 13 lines
Quoted 10 lines
Quoted 3 lines
If the above is true then we could achieve similar result when using the array as a circular buffer. It would be the same like when all members are linked from the beginning.
So you are suggesting using a multi-reader multi-writer lockless ringbuffer to implement a multi-reader multi-writer lockless ringbuffer. ;-)
The descriptor ringbuffer has fixed-size items, which simplifies the task. But I expect you will run into a chicken-egg scenario.
AFAIK, the main obstacle with the fully lockless solution was that the entries did not have a fixed size.
Quoted 7 lines
Quoted 3 lines
No. The variable size of the records was the reason I used descriptors. That has nothing to do with how I chose to connect those descriptors.
I think that we are talking about the same. If I remember correctly, the main problem is that
cmpxchg()is not reliable when the same address might be used by the metadata and data.
The cmpxchg() issue you mention is why I needed descriptors. But even if I were to implement a fixed-record-size ringbuffer where the cmpxchg() issue does not exist, I _still_ would have used a linked list to connect the records.
It is misleading to think the linked list is because of variable size records.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessQuoted 9 lines · John Ogness
Here are the writer-relevant memory barriers and their associated variables:
MB1: data_list.oldest
MB2: data_list.newest
MB3: data_block.id
MB4: descr.data_next
MB5: descr_list.newest
MB6: descr.next
I think this is the fundamental divergence in parlance.
You seem to associate a barrier with a (single) variable, where normally a barrier is between two (or more) variables.
As you wrote in that other email (I'm stlil going through all that); your MB5 isn't desc_list.newest, but rather between desc_list.newest and descr.next.
Remember, the topic is called 'memory ordering', and you cannot order singles.
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 10 lines · Peter Zijlstra
Quoted 9 lines
Here are the writer-relevant memory barriers and their associated variables:
MB1: data_list.oldest
MB2: data_list.newest
MB3: data_block.id
MB4: descr.data_next
MB5: descr_list.newest
MB6: descr.next
Quoted 4 lines
I think this is the fundamental divergence in parlance.
You seem to associate a barrier with a (single) variable, where normally a barrier is between two (or more) variables.
The litmus tests I posted to answer your previous questions should (hopefully) show that I already understand this. The above list shows the _key_ loads/stores that are used to guarantee ordering (for these and other memory operations). And yes, I now understand that my comments need to list all the operations that are being ordered based on these key loads/stores.
Quoted 3 lines
As you wrote in that other email (I'm stlil going through all that); your MB5 isn't desc_list.newest, but rather between desc_list.newest and descr.next.
Here is where I have massive problems communicating. I don't understand why you say the barrier is _between_ newest and next. I would say the barrier is _on_ newest to _synchronize_ with next (or something). I am struggling with terminology. (To be honest, I'd much rather just post litmus tests.)
For example, if we have:
WRITE_ONCE(&a, 1);WRITE_ONCE(&b, 1);WRITE_ONCE(&c, 1);smp_store_release(&d, 1);
and:
local_d = smp_load_acquire(&d);local_a = READ_ONCE(&a);local_b = READ_ONCE(&b);local_c = READ_ONCE(&c);
How do you describe that? Do you say the memory barrier is between a and d? Or between a, b, c, d? (a, b, c aren't ordered, but they are one-way synchronized with d).
I would say there is a barrier on d to synchronize a, b, c.
John Ogness
Petr Mladek
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 20 lines · John Ogness
Here is where I have massive problems communicating. I don't understand why you say the barrier is _between_ newest and next. I would say the barrier is _on_ newest to _synchronize_ with next (or something). I am struggling with terminology. (To be honest, I'd much rather just post litmus tests.)
For example, if we have:
WRITE_ONCE(&a, 1);WRITE_ONCE(&b, 1);WRITE_ONCE(&c, 1);smp_store_release(&d, 1);and:
local_d=smp_load_acquire(&d);local_a=READ_ONCE(&a);local_b=READ_ONCE(&b);local_c=READ_ONCE(&c);
Quoted 5 lines
How do you describe that? Do you say the memory barrier is between a and d? Or between a, b, c, d? (a, b, c aren't ordered, but they are one-way synchronized with d).
I would say there is a barrier on d to synchronize a, b, c.
Barriers are always paired. We need to know what variables are synchonized against each other, what is the reason and where is the counter part.
I think that it might be done many ways. I am familiar with bariers in kernel/livepatch/ code. They use rather long description. But I find it pretty useful especially when the problem is complicated and more bariers are involved in a single transition.
Best Regards,
Petr
Petr Mladek
maintainerPATCH 1/1 printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
In reply to Petr MladekThis is POC that implements the lockless printk ringbuffer slightly different way. I believe that it is worth considering because it looks much easier to deal with. The reasons are:
+ The state of each entry is always clear.
+ The write access rights and validity of the data are clear from the state of the entry.
+ It seems that three barriers are enough to synchronize readers vs. writers. The rest is done implicitely using atomic operations.
Of course, I might have missed some critical race that can't get solved by the new design easily. But I do not see it at the moment.
The code compiles but it is not really tested. I wanted to send it ASAP in a good enough state before we spend more time on cleaning up either of the proposals.
How it works:
It uses two buffers (data, descriptors) like in John's variant. The main difference is how the state is handled.
The trick is in the descriptor state "dst" variable included in struct prb_desc. It consists of 3 values that are manipulated atomically:
+ sequence number
+ committed flag
+ reuse flag
All the operations rely on the fact that we know what sequence number we are looking for. From this point of view the descriptor can be in the following states, see also enum prb_desc_state and prb_desc_state() function:
+ miss: sequence number is not the expected one
+ reserved: sequence matches, both flags cleared
+ committed: sequence matches, committed flag set
+ reusable: sequence matches, both flags set
Next, the descriptor and data array are crosslinked:
+ descriptor contains: lpos, lpos_next
+ data array contains: seq
The main trickery is in prb_read_desc(). It reads descriptor for the given sequence number into a buffer. It returns enum prb_desc_state that says how much the values are valid. The meaning is the following, by descriptor state:
+ miss: nothing is valid
+ reserved: nothing is valid
+ committed: everything is valid (descriptor, data)
+ reusable: descriptor has valid lpos, lpos_next but data are not longer valid
The validity is guaranteed by double checking the descriptor state before and after reading the other values. It might be less efficient than Jonh's approach. But I find it much easier to make sure that the consistency more is correct.
Consistency:
1. Writer become owner of the descriptor by pushing rb->seq_newest forward. From this point, it has exclusive write access to the descriptor until the committed flag is set.
The descriptor that is being replaced has to be in reusable state and the related data are not longer in valid lpos_oldest, lpos_latest range. By other words, nobody need the data from the old descriptor any longer.
The descriptor can be moved into reusable state only when it was in the committed state before (atomic operation).
2. Writer reserve data by pushing rb->lpos_newest. From this point, it has exclusive access to the data until committed flag is set.
Writers have to make enough space for the data before they change lpos_newest by pushing rb->lpos_oldest. They use the crosslinked "seq" to find the right descriptors and set them reusable.
Again, only committed descriptors can be marked reusable.
3. Writers set committed flag when everything is set correctly. It means that crosslink and data are set correctly.
From this point, they must not modify the descriptor or the data any longer. They might get moved into the reusable state at any time.
4. Readers have a simple life. They just try to access descriptors in the seq_oldest, seq_newest range. They try to read data only when the descriptor is in the committed state. They double check the state after the data read (copied).
5. Finally, I believe that we do not need to be concerned about overflows of seq or lpos numbers. All operations are done with interrupts disabled. Therefore they can be interrupted only by NMI. And NMI could not reserve and already reserved descriptor before it gets committed.
By other words, I do not see a way how any CPU could rotate lpos or seq numbers over the entire range while while another CPU is still looking for a reusable descriptor/data.
TODO when there is interest in this variant:
+ add printk_ringbuffer.h and Makefile
+ solve bootstrap (first added message)
+ add iterators
+ fix bugs (one-off and other ungly mistakes)
Heavily-based-on: John Ogness <[email protected]>
--- lib/Makefile | 1 + lib/printk_ringbuffer.c | 715 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 716 insertions(+) create mode 100644 lib/printk_ringbuffer.c
lib/Makefile +1 -0
@@ -37,6 +37,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \ earlycpio.o seq_buf.o siphash.o dec_and_lock.o \ nmi_backtrace.o nodemask.o win_minmax.o memcat_p.o +lib-$(CONFIG_PRINTK) += printk_ringbuffer.o lib-$(CONFIG_PRINTK) += dump_stack.o lib-$(CONFIG_MMU) += ioremap.o lib-$(CONFIG_SMP) += cpumask.o
lib/printk_ringbuffer.c new file +715 -0
715 lines not on this page · raw message
Signature · 1 line
2.16.4
John Ogness
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Hi Petr,
Quoted 9 lines · Petr Mladek
This is POC that implements the lockless printk ringbuffer slightly different way. I believe that it is worth considering because it looks much easier to deal with. The reasons are:
+ The state of each entry is always clear.
+ The write access rights and validity of the data are clear from the state of the entry.
Quoted 6 lines
+ It seems that three barriers are enough to synchronize readers vs. writers. The rest is done implicitely using atomic operations.
Of course, I might have missed some critical race that can't get solved by the new design easily. But I do not see it at the moment.
Two things jump out at me when looking at the implementation:
1. The code claims that the cmpxchg(seq_newest) in prb_reserve_desc() guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that wind seq_newest wraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.
This was one of the reasons I chose to use a linked list. When the descriptor is atomically removed from the linked list, it can _never_ be used (or even seen) by any other writer until the owning writer is done with it.
I'm not yet sure how that could be fixed with this implementation. The state information is in a separate variable than the head pointer for the descriptor array (seq_newest). This means you cannot atomically reserve descriptors.
2. Another issue is when prb_reserve() fails and sets the descriptor as unused. As it is now, no reader can read beyond that descriptor until it is recycled. Readers need to know that the descriptor is bad and can be skipped over. It might be better to handle this the way I did: go ahead and set the state to committed, but have invalid lpos/lpos_next values (for example: lpos_next=lpos) so the reader knows it can skip over the descriptor.
Quoted 3 lines
The code compiles but it is not really tested. I wanted to send it ASAP in a good enough state before we spend more time on cleaning up either of the proposals.
I am glad to see you put together your implementation. If anything, it shows you understand the design! If after seeing my next version (v3) you are still convinced that using a linked list for the descriptors is too complex, then I can help support your idea to move to an array.
Thank you for taking so much time for this!
John Ogness
Petr Mladek
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Quoted 19 lines · John Ogness
Hi Petr,
Quoted 9 lines · Petr Mladek
This is POC that implements the lockless printk ringbuffer slightly different way. I believe that it is worth considering because it looks much easier to deal with. The reasons are:
+ The state of each entry is always clear.
+ The write access rights and validity of the data are clear from the state of the entry.
Quoted 6 lines
+ It seems that three barriers are enough to synchronize readers vs. writers. The rest is done implicitely using atomic operations.
Of course, I might have missed some critical race that can't get solved by the new design easily. But I do not see it at the moment.
Quoted 8 lines
Two things jump out at me when looking at the implementation:
1. The code claims that the
cmpxchg(seq_newest)inprb_reserve_desc()guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that windseq_newestwraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.
I am not sure that I fully understand the problem. seq_newest wraps at 2^30 (32-bit) and at 2^62 (64-bit). It takes a while to reuse an existing one. And it does not depend on the size of the array.
In addition, new sequence number can get assigned only when the descriptor with the conflicting (sharing the same struct prb_desc) sequence number is in reusable state. It means that it has to be committed before.
Quoted 9 lines
This was one of the reasons I chose to use a linked list. When the descriptor is atomically removed from the linked list, it can _never_ be used (or even seen) by any other writer until the owning writer is done with it.
I'm not yet sure how that could be fixed with this implementation. The state information is in a separate variable than the head pointer for the descriptor array (
seq_newest). This means you cannot atomically reserve descriptors.
In my implementation, the sequence numbers are atomically reserved in prb_reserve_desc() by
} while (cmpxchg(&rb->seq_newest, seq_newest, seq) != newest_seqs);
where seq is always seq_newest + 1. We are here only when the conflicting seq from the previous wrap is in reusable state and the related datablock is moved outside valid lpos range. This is ensured by prb_remove_desc_oldest(rb, seq_prev_wrap).
Now, the CPU that succeeded with cmpxchg() becomes
the exclusive owner of the respective descriptor. The sequence number is written into this descriptor _after_ cmpxchg() succeeded.
It is safe because:
+ previous values are not longer used (descriptor has been marked as reusable, lpos from the related datablock were moved outside valid range (lpos_oldest, lpos_newest).
+ new values are ignored by readers and other writers until the right sequence number and the committed flag is set in the descriptor.
Quoted 7 lines
2. Another issue is when
prb_reserve()fails and sets the descriptor as unused. As it is now, no reader can read beyond that descriptor until it is recycled. Readers need to know that the descriptor is bad and can be skipped over. It might be better to handle this the way I did: go ahead and set the state to committed, but have invalid lpos/lpos_next values (for example: lpos_next=lpos) so the reader knows it can skip over the descriptor.
This is exactly what the code does, see prb_make_desc_unused(). It marks the descriptor as committed so that it can get reused. And it sets lpos and lpos_next to the same value so that the situation can get eventually detected by readers.
Quoted 8 lines
Quoted 3 lines
The code compiles but it is not really tested. I wanted to send it ASAP in a good enough state before we spend more time on cleaning up either of the proposals.
I am glad to see you put together your implementation. If anything, it shows you understand the design! If after seeing my next version (v3) you are still convinced that using a linked list for the descriptors is too complex, then I can help support your idea to move to an array.
I am definitely interested into seeing v3 of your approach. I believe that it will be much easier to understand. Then it will be easier to compare.
BTW: There is one potential problem with my alternative approach.
The descriptors and the related data blocks might get reserved in different order. Now, the descriptor might get reused only when the related datablock is moved outside the valid range. This operation might move also other data blocks outside the range and invalidate descriptors that were reserved later. As a result we might need to invalidate more messages in the log buffer then would be really necessary.
If I get it properly, this problem does not exist with the implementation using links. It is because the descriptors are linked in the same order as the reserved data blocks.
I am not sure how big the problem, with more invalidated messages, would be in reality. I am not sure if it would be worth a more complicated implementation.
Alternative solution would be to somehow mix tricks from both approaches and get something that is easier to deal with and has less drawbacks. I am not sure it is possible. Anyway, I still need to fully understand the linked approach first.
Best Regards,
Petr
John Ogness
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Quoted 25 lines · Petr Mladek
Quoted 16 lines
Quoted 9 lines
This is POC that implements the lockless printk ringbuffer slightly different way. I believe that it is worth considering because it looks much easier to deal with. The reasons are:
+ The state of each entry is always clear.
+ The write access rights and validity of the data are clear from the state of the entry.
Quoted 6 lines
+ It seems that three barriers are enough to synchronize readers vs. writers. The rest is done implicitely using atomic operations.
Of course, I might have missed some critical race that can't get solved by the new design easily. But I do not see it at the moment.
Quoted 8 lines
Two things jump out at me when looking at the implementation:
1. The code claims that the
cmpxchg(seq_newest)inprb_reserve_desc()guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that windseq_newestwraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.
Quoted 4 lines
I am not sure that I fully understand the problem.
seq_newestwraps at 2^30 (32-bit) and at 2^62 (64-bit). It takes a while to reuse an existing one. And it does not depend on the size of the array.
I am not referring to unsigned long overflowing. I am referring to array index wrapping. This _does_ depend on the size of the array.
Quoted 4 lines
In addition, new sequence number can get assigned only when the descriptor with the conflicting (sharing the same struct
prb_desc) sequence number is in reusable state. It means that it has to be committed before.
Correct. But taking it _out_ of the reusable state is not atomic, which opens the window I am referring to.
Quoted 26 lines
Quoted 9 lines
This was one of the reasons I chose to use a linked list. When the descriptor is atomically removed from the linked list, it can _never_ be used (or even seen) by any other writer until the owning writer is done with it.
I'm not yet sure how that could be fixed with this implementation. The state information is in a separate variable than the head pointer for the descriptor array (
seq_newest). This means you cannot atomically reserve descriptors.In my implementation, the sequence numbers are atomically reserved in
prb_reserve_desc()by} while (cmpxchg(&rb->seq_newest, seq_newest, seq) != newest_seqs);where seq is always
seq_newest+ 1. We are here only when the conflicting seq from the previous wrap is in reusable state and the related datablock is moved outside valid lpos range. This is ensured byprb_remove_desc_oldest(rb, seq_prev_wrap).Now, the CPU that succeeded with
cmpxchg()becomes
the exclusive owner of the respective descriptor. The sequence number is written into this descriptor _after_cmpxchg()succeeded.It is safe because:
Quoted 7 lines
+ previous values are not longer used (descriptor has been marked as reusable, lpos from the related datablock were moved outside valid range (
lpos_oldest,lpos_newest).+ new values are ignored by readers and other writers until the right sequence number and the committed flag is set in the descriptor.
Let me inline the function are talking about and add commentary to illustrate what I am saying:
static int prb_reserve_desc(struct prb_reserved_entry *entry)
{
unsigned long seq, seq_newest, seq_prev_wrap;
struct printk_ringbuffer *rb = entry->rb;
struct prb_desc *desc;
int err;
/* Get descriptor for the next sequence number. */
do {
seq_newest = READ_ONCE(rb->seq_newest);
seq = (seq_newest + 1) & PRB_SEQ_MASK;
seq_prev_wrap = (seq - PRB_DESC_SIZE(rb)) & PRB_SEQ_MASK;
/*
* Remove conflicting descriptor from the previous wrap
* if ever used. It might fail when the related data
* have not been committed yet.
*/
if (seq_prev_wrap == READ_ONCE(rb->seq_oldest)) {
err = prb_remove_desc_oldest(rb, seq_prev_wrap);
if (err)
return err;
}
} while (cmpxchg(&rb->seq_newest, seq_newest, seq) != seq_newest);I am referring to this point in the code, after the cmpxchg(). seq_newest has been incremented but the descriptor is still in the unused state and seq is still 1 wrap behind. If an NMI occurs here and the NMI (or some other CPU) inserts enough entries to wrap the descriptor array, this descriptor will be reserved again, even though it has already been reserved.
/* * The descriptor is ours until the COMMITTED bit is set. * Set its sequence number with all flags cleared. */ desc = SEQ_TO_DESC(rb, seq); WRITE_ONCE(desc->dst, seq); /* * Make sure that anyone sees the new dst/seq before * lpos values and data are manipulated. It is related * to the read berrier in prb_read_desc(). */ smp_wmb();
*Now* the descriptor is ours. Not before. And it is only exclusively ours if the above mentioned situation doesn't occur.
This window doesn't exist with the list approach because reserving a descriptor simply involves removing the tail (oldest) of the committed list, which is an atomic operation.
entry->seq = seq; return 0; }
Quoted 8 lines
Quoted 7 lines
2. Another issue is when
prb_reserve()fails and sets the descriptor as unused. As it is now, no reader can read beyond that descriptor until it is recycled. Readers need to know that the descriptor is bad and can be skipped over. It might be better to handle this the way I
did: go ahead and set the state to committed, but have invalid lpos/lpos_next values (for example: lpos_next=lpos) so the reader knows it can skip over the descriptor.
Quoted 4 lines
This is exactly what the code does, see
prb_make_desc_unused(). It marks the descriptor as committed so that it can get reused. And it sets lpos andlpos_nextto the same value so that the situation can get eventually detected by readers.
Indeed. Sorry for the noise.
Quoted 10 lines
BTW: There is one potential problem with my alternative approach.
The descriptors and the related data blocks might get reserved in different order. Now, the descriptor might get reused only when the related datablock is moved outside the valid range. This operation might move also other data blocks outside the range and invalidate descriptors that were reserved later. As a result we might need to invalidate more messages in the log buffer then would be really necessary.
Quoted 3 lines
If I get it properly, this problem does not exist with the implementation using links. It is because the descriptors are linked in the same order as the reserved data blocks.
Descriptors in the committed list are ordered in commit order (not the reserve order). However, if there are not enough descriptors (i.e. avgdatabits is higher than the true average) this problem exists with the list approach as well.
Quoted 3 lines
I am not sure how big the problem, with more invalidated messages, would be in reality. I am not sure if it would be worth a more complicated implementation.
I am also not sure how big the problem is in a practical sense. However to help avoid this issue, I will increase the descbits:avgdatabits ratio for v3.
Quoted 2 lines
Anyway, I still need to fully understand the linked approach first.
You may want to wait for v3. I've now split the ringbuffer into multiple generic data structures (as unintentionally suggested[0] by PeterZ), which helps to clarify the role of each data structure and also isolates the memory barriers so that it is clear which data structure requires which memory barriers.
John Ogness
Petr Mladek
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Quoted 36 lines · John Ogness
Quoted 7 lines · Petr Mladek
Quoted 6 lines
1. The code claims that the
cmpxchg(seq_newest)inprb_reserve_desc()guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that windseq_newestwraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.Let me inline the function are talking about and add commentary to illustrate what I am saying:
static int
prb_reserve_desc(struct prb_reserved_entry *entry){ unsigned long seq, seq_newest, seq_prev_wrap; struct printk_ringbuffer *rb = entry->rb; struct prb_desc *desc; int err; /* Get descriptor for the next sequence number. */ do { seq_newest = READ_ONCE(rb->seq_newest); seq = (seq_newest + 1) & PRB_SEQ_MASK; seq_prev_wrap = (seq - PRB_DESC_SIZE(rb)) & PRB_SEQ_MASK; /* * Remove conflicting descriptor from the previous wrap * if ever used. It might fail when the related data * have not been committed yet. */ if (seq_prev_wrap == READ_ONCE(rb->seq_oldest)) { err = prb_remove_desc_oldest(rb, seq_prev_wrap); if (err) return err; } } while (cmpxchg(&rb->seq_newest, seq_newest, seq) != seq_newest);
Quoted 6 lines
I am referring to this point in the code, after the
cmpxchg().seq_newesthas been incremented but the descriptor is still in the unused state and seq is still 1 wrap behind. If an NMI occurs here and the NMI (or some other CPU) inserts enough entries to wrap the descriptor array, this descriptor will be reserved again, even though it has already been reserved.
Not really, the NMI will not reach the cmpxchg() in this case. prb_remove_desc_oldest() will return error. It will not be able to remove the conflicting descriptor because it will still be occupied by a two-wraps-old descriptor.
BTW: I did meet these problems in some early variatns. But everything started working at some point. I always looked how you solved a particular situation in the link-based approach. Then I somehow translated it into the pure-array variant.
Quoted 10 lines
Quoted 10 lines
BTW: There is one potential problem with my alternative approach.
The descriptors and the related data blocks might get reserved in different order. Now, the descriptor might get reused only when the related datablock is moved outside the valid range. This operation might move also other data blocks outside the range and invalidate descriptors that were reserved later. As a result we might need to invalidate more messages in the log buffer then would be really necessary.
Quoted 8 lines
Quoted 3 lines
If I get it properly, this problem does not exist with the implementation using links. It is because the descriptors are linked in the same order as the reserved data blocks.
Descriptors in the committed list are ordered in commit order (not the reserve order). However, if there are not enough descriptors (i.e. avgdatabits is higher than the true average) this problem exists with the list approach as well.
Thanks for the explanation.
Quoted 7 lines
Quoted 3 lines
I am not sure how big the problem, with more invalidated messages, would be in reality. I am not sure if it would be worth a more complicated implementation.
I am also not sure how big the problem is in a practical sense. However to help avoid this issue, I will increase the descbits:avgdatabits ratio for v3.
Yup, it sounds reasonable. The number of reserved but not committed descriptors is basically limited by the number of CPUs.
The only unknown variable is the length of the messages. Which brings another problem. We might need a solution for continuous lines. People would want it. Also storing one line in many entries would be quite inefficient. But let's discuss this later when printk() gets converted into the lockless ring buffer.
Quoted 8 lines
Quoted 2 lines
Anyway, I still need to fully understand the linked approach first.
You may want to wait for v3. I've now split the ringbuffer into multiple generic data structures (as unintentionally suggested[0] by PeterZ), which helps to clarify the role of each data structure and also isolates the memory barriers so that it is clear which data structure requires which memory barriers.
Sure, I am interested to see v3.
Best Regards,
Petr
John Ogness
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Quoted 42 lines · Petr Mladek
Quoted 35 lines
Quoted 7 lines
Quoted 6 lines
1. The code claims that the
cmpxchg(seq_newest)inprb_reserve_desc()guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that windseq_newestwraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.Let me inline the function are talking about and add commentary to illustrate what I am saying:
static int
prb_reserve_desc(struct prb_reserved_entry *entry){ unsigned long seq, seq_newest, seq_prev_wrap; struct printk_ringbuffer *rb = entry->rb; struct prb_desc *desc; int err; /* Get descriptor for the next sequence number. */ do { seq_newest = READ_ONCE(rb->seq_newest); seq = (seq_newest + 1) & PRB_SEQ_MASK; seq_prev_wrap = (seq - PRB_DESC_SIZE(rb)) & PRB_SEQ_MASK; /* * Remove conflicting descriptor from the previous wrap * if ever used. It might fail when the related data * have not been committed yet. */ if (seq_prev_wrap == READ_ONCE(rb->seq_oldest)) { err = prb_remove_desc_oldest(rb, seq_prev_wrap); if (err) return err; } } while (cmpxchg(&rb->seq_newest, seq_newest, seq) != seq_newest);Quoted 6 lines
I am referring to this point in the code, after the
cmpxchg().seq_newesthas been incremented but the descriptor is still in the unused state and seq is still 1 wrap behind. If an NMI occurs here and the NMI (or some other CPU) inserts enough entries to wrap the descriptor array, this descriptor will be reserved again, even though it has already been reserved.
Quoted 2 lines
Not really, the NMI will not reach the
cmpxchg()in this case.prb_remove_desc_oldest()will return error.
Why will prb_remove_desc_oldest() fail? IIUC, it will return success because the descriptor is in the desc_miss state.
Quoted 2 lines
It will not be able to remove the conflicting descriptor because it will still be occupied by a two-wraps-old descriptor.
Please explain why with more details. Perhaps providing a function call chain? Sorry if I'm missing the obvious here.
This is really the critical point that drove me to use lists: multiple writers expiring and reserving the same descriptors.
John Ogness
Petr Mladek
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Quoted 43 lines · John Ogness
Quoted 42 lines · Petr Mladek
Quoted 41 lines
Quoted 7 lines
Quoted 6 lines
1. The code claims that the
cmpxchg(seq_newest)inprb_reserve_desc()guarantees that "The descriptor is ours until the COMMITTED bit is set." This is not true if in that windseq_newestwraps, allowing another writer to gain ownership of the same descriptor. For small descriptor arrays (such as in my test module), this situation is quite easy to reproduce.Let me inline the function are talking about and add commentary to illustrate what I am saying:
static int
prb_reserve_desc(struct prb_reserved_entry *entry){ unsigned long seq, seq_newest, seq_prev_wrap; struct printk_ringbuffer *rb = entry->rb; struct prb_desc *desc; int err; /* Get descriptor for the next sequence number. */ do { seq_newest = READ_ONCE(rb->seq_newest); seq = (seq_newest + 1) & PRB_SEQ_MASK; seq_prev_wrap = (seq - PRB_DESC_SIZE(rb)) & PRB_SEQ_MASK; /* * Remove conflicting descriptor from the previous wrap * if ever used. It might fail when the related data * have not been committed yet. */ if (seq_prev_wrap == READ_ONCE(rb->seq_oldest)) { err = prb_remove_desc_oldest(rb, seq_prev_wrap); if (err) return err; } } while (cmpxchg(&rb->seq_newest, seq_newest, seq) != seq_newest);I am referring to this point in the code, after the
cmpxchg().seq_newesthas been incremented but the descriptor is still in the unused state and seq is still 1 wrap behind. If an NMI occurs here and the NMI (or some other CPU) inserts enough entries to wrap the descriptor array, this descriptor will be reserved again, even though it has already been reserved.
Quoted 8 lines
Quoted 2 lines
Not really, the NMI will not reach the
cmpxchg()in this case.prb_remove_desc_oldest()will return error.Why will
prb_remove_desc_oldest()fail? IIUC, it will return success because the descriptor is in thedesc_missstate.Quoted 2 lines
It will not be able to remove the conflicting descriptor because it will still be occupied by a two-wraps-old descriptor.
Ah, I see that this situation was not handled correctly. But it can get fixed pretty easily, see an updated prb_remove_desc_oldest() at the end of the mail.
Quoted 2 lines
Please explain why with more details. Perhaps providing a function call chain? Sorry if I'm missing the obvious here.
To be on the safe side, let's try it with real numbers.
Let's have array with 8 descriptors filled with the following sequence numbers pointing to commited messages:
desc[10]: 16 17 18 19 20 21 22 23 rb->seq_oldest = 16; rb->seq_newest = 23;
then prb_reserve_desc() would do:
seq_newest = 23; seq = 24; seq_prew_wrap = 16; prb_remove_desc_oldest(rb, 16); // let's say that it succeeds and // rb->seq_oldest == 17; cmpxchg(&rb->seq_newest, 23, 24) == 23) // let's say that it succeds and it is immediately // interrupted by NMI before desc[0]->dst is set to 24. // So, we still have: desc[10]: 16 17 18 19 20 21 22 23 rb->seq_oldest = 17; rb->seq_newest = 24;
Let's say that NMI tries to print 8 messages. After 7 successfully reserved and commited messages we could have:
desc[10]: 16 25 26 27 28 29 30 31 rb->seq_oldest = 24; rb->seq_newest = 31;
desc[0] still has the outdated information. Now, we try to reserve the 8th message, then prb_reserve_desc() would do:
seq_newest = 31;
seq = 32;
seq_prew_wrap = 24;
prb_remove_desc_oldest(rb, 24);
desc_state = prb_read_desc(rb, 24, &desc);
// desc_state == desc_miss because the
// descriptor still points to the outdated
// seq = 16.
// prb_remove_desc_oldest(rb, 24) would continue with:
switch (desc_state) {
/*
* Another seq means that the oldest desciptor has already been
* removed and reused. Return success in this case.
*/
case desc_miss:
return 0;
BUG: This is obviously wrong!But this is a special case that can get detected. desc->seq is exactly 1 wrap back than requested. The proper code would be:
static int prb_remove_desc_oldest(struct printk_ringbuffer *rb,
unsigned long seq_oldest)
{
struct prb_desc desc;
enum prb_desc_state desc_state;
int err;
desc_state = prb_read_desc(rb, seq_oldest, &desc);
switch (desc_state) {
case desc_miss:
unsigned long seq_prev_wrap =
(seq_oldest - PRB_DESC_SIZE(rb)) &
PRB_SEQ_MASK;
if (desc->dst ==
(seq_prev_wrap |
PRB_COMMITED_MASK |
PRB_REUSABLE_MASK)) {
/*
* Special case: Reusable descriptor from the
* previous wrap means that the current
* oldest descriptor is reserved but the dst
* has not been updated yet.
*/
return -ENOMEM;
/*
* Any other desc_misc means that the oldest
* has been already removed and reused by a newer
* sequence number. Return success in this case.
* The attempt to update rb->seq_oldest will fail.
*/
return 0;At this point, any prb_reserve() would fail exactly this way until NMI returns and the message with seq == 24 gets commited.
Best Regards,
Petr
John Ogness
maintainerRe: [PATCH POC] printk_ringbuffer: Alternative implementation of lockless printk ringbuffer
Hi Petr,
FWIW, I hacked a patch against my RFCv4[0] series to implement your POC. Some parts of the patch are not particularly pretty, as I had to "mold" it to fit numlist usage. And I was extreme with heavy memory barrier usage to save time. But it boots, runs, and passes all my printk interface tests. It is all behind a PETRM_POC macro, so toggling between the two implementations is quite simple.
I varied from your POC by having the sequence number be separate from the id. We need 64-bit sequence numbers for all architectures, but since there are cmpxchg() calls on the id, the id probably should remain an unsigned long. That wasn't a problem to implement because my ringbuffer implementation has them separate as well. It also has the benefit that no sequence bits are sacrified for the state bits.
I would like to say that I am glad to see that this works. I was not convinced that an array-based approach would work. And although I still think it is too complex, it is not as bad as I expected.
Particularly interesting to note by the implementation is the use of states. numlist.c:expire_oldest_node() provides the main piece of state logic to handle the critical point of descriptor recycling. But also note that readers (numlist.c:numlist_read()) need to watch for two states (committed and reusable) as well as validating the data itself.
As for performance, my test_prb test module does not provide very good results. On a 16-core ARM64 I usually only see about 10,000 to 1,000,000 records before a writer fails to reserve. The problem seems to be that a writer has reserved but not yet committed a record and the descriptor array has wrapped. With the array implementation this means no further descriptors can be assigned until that writer has committed. So a new writer has no choice but to fail.
With the linked list approach this problem is avoided because writers simply remove a descriptor from the committed list. With it removed, it is less critical how long that writer takes to commit because it is not preventing other writers from removing descriptors from the committed list.
To compare, with the linked list implementation, the test_prb test module ran 14 days on a 16-core ARM64 machine before I manually stopped the test. In that time the 15 writers wrote a total of 936,341,256,222 records (average of 735,408 per second). The single reader never lost more than 29 consecutive records (having lost a total of 0.02% of the records). Keep in mind all of this is using a 4KB ringbuffer.
It could be argued that the test_prb module (with its massive writing and small ringbuffer) is unrealistic. However, I would still argue that using a linked list to manage the committed records is a simpler, more straight forward, more robust approach that is easier to understand and maintain. I hope with the splitting of the linked list (numlist) into separate source files, you will also see that it is not so complicated.
John Ogness
[0] https://lkml.kernel.org/r/[email protected]
------ BEGIN PATCH -----
kernel/printk/numlist.h +22 -0
@@ -2,6 +2,7 @@#ifndef _KERNEL_PRINTK_NUMLIST_H#define _KERNEL_PRINTK_NUMLIST_H +#define PETRM_POC #include <linux/atomic.h>
@@ -69,4 +70,25 @@ unsigned long numlist_read_tail(struct numlist *nl, u64 *seq,bool numlist_read (struct numlist *nl,unsigned long id,u64 *seq,unsigned long *next_id); +#ifdef PETRM_POC +unsigned long prb_descs_count (struct numlist *nl); + +enum desc_state { + desc_miss, + desc_reserved, + desc_committed, + desc_reusable, +}; + +#define DESC_DST_BITS (sizeof(long) * 8) +#define DESC_COMMITTED_MASK (1UL << (DESC_DST_BITS - 1)) +#define DESC_REUSE_MASK (1UL << (DESC_DST_BITS - 2)) +#define DESC_FLAGS_MASK (DESC_COMMITTED_MASK | DESC_REUSE_MASK) +#define DESC_ID_MASK (~DESC_FLAGS_MASK) + +#define DESC_ID (id) ((id) & DESC_ID_MASK) +#define DESC_ID_PREV_WRAP (nl, id) \ + DESC_ID(DESC_ID(id) - prb_descs_count(nl)) +#endif +#endif /* _KERNEL_PRINTK_NUMLIST_H */
kernel/printk/numlist.c +125 -0
164 lines not on this page · raw message
kernel/printk/ringbuffer.h +12 -2
@@ -218,13 +218,23 @@ struct dr_desc *prb_getdesc(unsigned long id, void *arg);* immediately available and initialized. It is an alternative to * manually initializing a ringbuffer with prb_init(). */ +#ifdef PETRM_POC +#define ID0_INITIALIZER \ + ATOMIC_LONG_INIT(DESC_COMMITTED_MASK|DESC_REUSE_MASK) +#define NODE0_INITIALIZER { .seq = 0, .next_id = 1, } +#else +#define ID0_INITIALIZER ATOMIC_LONG_INIT(0) +#define NODE0_INITIALIZER { .seq = 0, .next_id = 0 } +#endif +#define DECLARE_PRINTKRB (name, avgdatabits, descbits, waitq) \ char _##name##_data[1 << ((avgdatabits) + (descbits))] \ __aligned(__alignof__(long)); \ struct prb_desc _##name##_descs[1 << (descbits)] = { \ { \ - .id = ATOMIC_LONG_INIT(0), \ + .id = ID0_INITIALIZER, \ .desc = __DR_DESC_INITIALIZER, \ + .list = NODE0_INITIALIZER, \ }, \ }; \ struct printk_ringbuffer name = { \
@@ -281,7 +291,7 @@ struct prb_entry name = { \* * @name: The name for the entry structure variable. * -* This macro is declares and initializes an entry structure without any +* This macro declares and initializes an entry structure without any * buffer. This is useful if an iterator is only interested in sequence * numbers and so does not need to read the entry data. Also, because of * its small size, it is safe to put on the stack.
kernel/printk/ringbuffer.c +63 -1
134 lines not on this page · raw message
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessHi,
I would like to point out an important typo related to memory barriers...
Quoted 5 lines · John Ogness
lib/printk_ringbuffer.c new file +0
-0
[...]
Quoted 36 lines
lib/printk_ringbuffer.c new file +36
-0+static struct prb_descr *remove_oldest_descr (struct printk_ringbuffer *rb) +{ +struct prb_list *l = &rb->descr_list; +unsigned long oldest_id; +struct prb_descr *d; +unsigned long next; + +for (;;) { + oldest_id =READ_ONCE (l->oldest); + +/* list empty */ +if (oldest_id ==EOL ) +return NULL ; + + d =TO_DESCR (rb, oldest_id); + +/* only descriptors with _invalid_ data can be removed */ +if (data_valid (rb,READ_ONCE (rb->data_list.oldest), +READ_ONCE (rb->data_list.newest), +READ_ONCE (d->data), +READ_ONCE (d->data_next))) { +return NULL ; + } + +/* +* MB6: synchronize link descr +* +* In particular: l->oldest is loaded as a data dependency so +* d->next and the following l->oldest will load afterwards, +* respectively. +*/ + next =smp_load_acquire (&d->next); + +if (next ==EOL &&READ_ONCE (l->oldest) == oldest_id) { +/* +* The oldest has no next, so this is a list of one
lib/printk_ringbuffer.c line 399
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+* descriptor. Lists must always have at least one +* descriptor. +*/ +return NULL ; + } + +if (cmpxchg (&l->oldest, oldest_id, next) == oldest_id) { +/* removed successfully */ +break ; + }
This is supposed to be cmpxchg_relaxed(), not cmpxchg(). I did not intend to include the general mb() memory barriers around the RMW operation. (For some reason I thought _relaxed was the default.) Sorry.
John Ogness
Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
In reply to John OgnessOn (06/07/19 18:29), John Ogness wrote:
[..]
Quoted 46 lines
lib/printk_ringbuffer.c new file +46
-0+static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ +do { +/* MB5: synchronize add descr */ + newest_id =smp_load_acquire (&l->newest); + newest_d =TO_DESCR (rb, newest_id); + +if (newest_id ==EOL ) +WRITE_ONCE (d->seq,1 ); +else +WRITE_ONCE (d->seq,READ_ONCE (newest_d->seq) +1 ); +/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id); + +if (unlikely (newest_id ==EOL )) { +/* no previous newest means we *are* the list, set oldest */ + +/* +* MB UNPAIRED +* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&l->oldest,EOL , e->id) !=EOL ); + }else { +/* link to previous chain */ + +/* +* MB6: synchronize link descr +* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&newest_d->next, +EOL , e->id) !=EOL ); + } +}
[..]
Quoted 21 lines
lib/printk_ringbuffer.c new file +21
-0+char *prb_reserve (struct prb_reserved_entry *e,struct printk_ringbuffer *rb, +unsigned int size) +{ +struct prb_datablock *b; +struct prb_descr *d; +char *buf; + +if (size ==0 ) +return NULL ; + + size +=sizeof (struct prb_datablock ); + size =DATA_ALIGN_SIZE (size); +if (size >DATAARRAY_SIZE (rb)) +return NULL ; + + e->rb = rb; + +local_irq_save (e->irqflags); + +if (!assign_descr (e)) + goto err_out;
lib/printk_ringbuffer.c line 656
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+ + d = e->descr; +WRITE_ONCE (d->id, e->id); + +if (!data_reserve (e, size)) { +/* put invalid descriptor on list, can still be traversed */ +WRITE_ONCE (d->next,EOL ); +add_descr_list (e); + goto err_out; + }
I'm wondering if prb can always report about its problems. Including the cases when things "go rather bad".
Suppose we have
printk() prb_reserve() !data_reserve() add_descr_list() WARN_ON_ONCE() printk() prb_reserve() !assign_descr(e) << lost WARN_ON's "printk" or "printks"?
In general, assuming that there might be more error printk-s either called directly directly from prb->printk on indirectly, from prb->ABC->printk.
Also note,
Lost printk-s are not going to be accounted as 'lost' automatically. It seems that for printk() there is no way to find out that it has recursed from printk->prb_commit but hasn't succeeded in storing recursive messages. I'd say that prb_reserve() err_out should probably &rb->lost++.
-ss
John Ogness
maintainerRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
Quoted 27 lines · Sergey Senozhatsky
[..]
Quoted 26 lines
lib/printk_ringbuffer.c new file +26
-0+static void add_descr_list (struct prb_reserved_entry *e) +{ +struct printk_ringbuffer *rb = e->rb; +struct prb_list *l = &rb->descr_list; +struct prb_descr *d = e->descr; +struct prb_descr *newest_d; +unsigned long newest_id; + +/* set as newest */ +do { +/* MB5: synchronize add descr */ + newest_id =smp_load_acquire (&l->newest); + newest_d =TO_DESCR (rb, newest_id); + +if (newest_id ==EOL ) +WRITE_ONCE (d->seq,1 ); +else +WRITE_ONCE (d->seq,READ_ONCE (newest_d->seq) +1 ); +/* +* MB5: synchronize add descr +* +* In particular: next written before cmpxchg +*/ + }while (cmpxchg_release (&l->newest, newest_id, e->id) != newest_id); + +if (unlikely (newest_id ==EOL )) {
Quoted 8 lines
lib/printk_ringbuffer.c line 324
Quoted 8 lines
lib/printk_ringbuffer.c new file +8
-0+/* no previous newest means we *are* the list, set oldest */ + +/* +* MB UNPAIRED +* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&l->oldest,EOL , e->id) !=EOL );
This WARN_ON_ONCE...
Quoted 10 lines
lib/printk_ringbuffer.c line 334
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+ }else { +/* link to previous chain */ + +/* +* MB6: synchronize link descr +* +* In particular: Force cmpxchg _after_ cmpxchg on newest. +*/ +WARN_ON_ONCE (cmpxchg_release (&newest_d->next, +EOL , e->id) !=EOL );
... and this WARN_ON_ONCE should both really be BUG_ON. These situations will not happen. Actually, they should both be xchg_release(). But until everyone is happy with the memory barriers, I wanted to leave this bug checking in place.
Quoted 55 lines
Quoted 2 lines
(quoted diff) +2
-0+ } +}[..]
Quoted 21 lines
lib/printk_ringbuffer.c new file +21
-0+char *prb_reserve (struct prb_reserved_entry *e,struct printk_ringbuffer *rb, +unsigned int size) +{ +struct prb_datablock *b; +struct prb_descr *d; +char *buf; + +if (size ==0 ) +return NULL ; + + size +=sizeof (struct prb_datablock ); + size =DATA_ALIGN_SIZE (size); +if (size >DATAARRAY_SIZE (rb)) +return NULL ; + + e->rb = rb; + +local_irq_save (e->irqflags); + +if (!assign_descr (e)) + goto err_out;lib/printk_ringbuffer.c line 656
Quoted 10 lines
lib/printk_ringbuffer.c new file +10
-0+ + d = e->descr; +WRITE_ONCE (d->id, e->id); + +if (!data_reserve (e, size)) { +/* put invalid descriptor on list, can still be traversed */ +WRITE_ONCE (d->next,EOL ); +add_descr_list (e); + goto err_out; + }I'm wondering if prb can always report about its problems. Including the cases when things "go rather bad".
Suppose we have
printk() prb_reserve() !data_reserve() add_descr_list() WARN_ON_ONCE() printk() prb_reserve() !assign_descr(e) << lost WARN_ON's "printk" or "printks"?In general, assuming that there might be more error printk-s either called directly directly from
prb->printkon indirectly, fromprb->ABC->printk.
Quoted 6 lines
Also note,
Lost printk-s are not going to be accounted as 'lost' automatically. It seems that forprintk()there is no way to find out that it has recursed fromprintk->prb_commitbut hasn't succeeded in storing recursive messages. I'd say thatprb_reserve()err_outshould probably &rb->lost++.
This is a good point. I have no problems with that. In that case, it should probably be called "fail" instead of "lost".
John Ogness
John Ogness
maintainerRFC PATCH v2 2/2 printk-rb: add test module
In reply to John OgnessThis module does some heavy write stress testing on the ringbuffer with a reader that is checking for integrity.
--- lib/Makefile | 2 + lib/test_prb.c | 237 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 239 insertions(+) create mode 100644 lib/test_prb.c
lib/Makefile +2 -0
@@ -292,3 +292,5 @@ obj-$(CONFIG_GENERIC_LIB_MULDI3) += muldi3.o obj-$(CONFIG_GENERIC_LIB_CMPDI2) += cmpdi2.o obj-$(CONFIG_GENERIC_LIB_UCMPDI2) += ucmpdi2.o obj-$(CONFIG_OBJAGG) += objagg.o + +obj-m += test_prb.o
lib/test_prb.c new file +237 -0
237 lines not on this page · raw message
Signature · 1 line
2.11.0
On Fri, 7 Jun 2019, John Ogness wrote:
Polite ping ....
Quoted 42 lines
This is a follow-up RFC on the work to reimplement much of the core of printk. The original thread can be seen here[0].
One of the results of that thread was that the work needs to be broken up into several pieces. A roadmap was laid out[1] and this RFC is for the base component of the first piece:
a new ringbuffer implementation for printk.This series does not touch any existing printk code. It is only the ringbuffer implementation. I am particularly interested in feedback relating to the design of the ringbuffer and the use of memory barriers.
The series also includes a test module that performs some heavy writer stress testing. I have successfully run these tests on a 16-core ARM64 platform.
John Ogness
[0] https://lkml.kernel.org/r/[email protected]
[1] https://lkml.kernel.org/r/[email protected]John Ogness (2):
printk-rb: add a new printk ringbuffer implementation
printk-rb: add test moduleDocumentation/core-api/index.rst | 1 + Documentation/core-api/printk-ringbuffer.rst | 104 +++ include/linux/printk_ringbuffer.h | 238 +++++++ lib/Makefile | 2 + lib/printk_ringbuffer.c | 924 +++++++++++++++++++++++++++ lib/test_prb.c | 237 +++++++ 6 files changed, 1506 insertions(+) create mode 100644 Documentation/core-api/printk-ringbuffer.rst create mode 100644 include/linux/printk_ringbuffer.h create mode 100644 lib/printk_ringbuffer.c create mode 100644 lib/test_prb.cSignature · 1 line
2.11.0
Petr Mladek
maintainerQuoted 3 lines · Thomas Gleixner
On Fri, 7 Jun 2019, John Ogness wrote:
Polite ping ....
I have started looking at the patchset yesterday. I informed John that I was busy last week via a personal mail.
My first impression is very good. But I still have to dive much more into the code.
Best Regards,
Petr