Re: more barriers: Re: [PATCH 1/2] printk: add lockless buffer
Hi,
This is quite a long response. I can summarize here:
- Several new memory barrier pairs were identified.
- The placement of a memory barrier was incorrect.
There are now quite a few changes queued up for v2. I will try to get
this posted soon. Also, I believe we've now identified the cmpxchg's
that really need the full memory barriers. So I will be folding all the
memory barriers into cmpxchg() calls where applicable and include the
appropriate memory barrier documentation.
And now my response...
On 2020-03-04, Petr Mladek wrote:
diff --git a/kernel/printk/printk_ringbuffer.c
b/kernel/printk/printk_ringbuffer.c
new file mode 100644
index ..796257f226ee
--- /dev/null
+++ b/kernel/printk/printk_ringbuffer.c
+/*
+ * Take a given descriptor out of the committed state by attempting
+ * the transition from committed to reusable. Either this task or some
+ * other task will have been successful.
+ */
+static void desc_make_reusable(struct prb_desc_ring *desc_ring,
+ unsigned long id)
+{
+ struct prb_desc *desc = to_desc(desc_ring, id);
+ atomic_long_t *state_var = >state_var;
+ unsigned long val_committed = id | DESC_COMMITTED_MASK;
+ unsigned long val_reusable = val_committed | DESC_REUSE_MASK;
+
+ atomic_long_cmpxchg_relaxed(state_var, val_committed,
val_reusable);
>>>
>>> IMHO, we should add smp_wmb() here to make sure that the reusable
>>> state is written before we shuffle the desc_ring->tail_id/head_id.
>>>
>>> It would pair with the read part of smp_mb() in desc_reserve()
>>> before the extra check if the descriptor is really in reusable state.
>>
>> Yes. Now that we added the extra state checking in desc_reserve(),
>> this ordering has become important.
>>
>> However, for this case I would prefer to instead place a full memory
>> barrier immediately before @tail_id is incremented (in
>> desc_push_tail()). The tail-incrementing-task must have seen the
>> reusable state (even if it is not the one that set it) and an
>> incremented @tail_id must be visible to the task recycling a
>> descriptor.
>
> I agree that this is exactly the place when the full barrier will be
> needed. This write can happen on any CPU and the write depending on
> this value might be done on another CPU.
>
> Also I agree that desc_push_tail() looks like the right place
> for the full barrier because some actions there are done only
> when the descriptor is invalidated.
>
> I just wonder if it should be even before data_push_tail()
> calls. It will make sure that everyone sees the reusable state
> before we move the data_ring borders.
You are correct. The reader is only ordering data reads against the
state of the _descriptor that is being read_. The reader may not yet see
that its descriptor has transitioned to reusable while a writer may have
already recycled the data block (associated with a _different_
descriptor) and started writing something new.
The problem is a missing ordering between setting the descriptor to
reusable and any possibilty of data block recycling (e.g. the data tail
is pushed). Inserting a full memory barrier after setting the state to
reusable and before pushing the data tail will fix that. Then if the
reader reads newer data, it must see that its descriptor state is no
longer committed.
Changing the cmpxchg_relaxed() in data_push_tail() to cmpxchg() will add
the needed full memory barrier. I felt uneasy about making that
cmpxchg() relaxed but couldn't prove why. Thanks for seeing it!
+}
+
+/*
+ * For a given data ring (text or dict) and its current tail lpos:
+ * for each data block up until @lpos, make the associated descriptor
+ * reusable.
+ *
+ * If there is any problem making the associated descriptor reusable,
+ * either the descriptor has not yet been committed or another writer
+ * task has already pushed the tail lpos past the problematic data
+ * block. Regardless, on error the caller can re-load the tail lpos
+ * to determine the situation.
+ */
+static bool data_make_reusable(struct printk_ringbuffer *rb,
+ struct prb_data_ring *data_ring,
+ unsigned long tail_lpos, unsigned long lpos,
+ unsigned long *lpos_out)
+{
+ struct prb_desc_ring *desc_ring = >desc_ring;
+ struct prb_data_blk_lpos *blk_lpos;
+ struct prb_data_block *blk;
+ enum desc_state d_state;
+ struct prb_desc desc;
+ unsigned long id;
+
+ /*
+ * Using the provided @data_ring, point @blk_lpos to the correct
+ * blk_lpos within the local copy of the descriptor.
+ */
+ if (data_ring == >text_data_ring)
+ blk_lpos = _blk_lpos;
+ else
+ blk_lpos = _blk_lpos;
+
+ /* Loop until @tail_lpos has advanced to
Re: more barriers: Re: [PATCH 1/2] printk: add lockless buffer
On Thu 2020-02-27 13:04:09, John Ogness wrote:
> On 2020-02-21, Petr Mladek wrote:
> > If I get it correctly, the used cmpxchg_relaxed() variants does not
> > provide full barriers. They are just able to prevent parallel
> > manipulation of the modified variable.
>
> Correct.
>
> I purposely avoided the full barriers of a successful cmpxchg() so that
> we could clearly specify what we needed and why. As Andrea pointed out
> [0], we need to understand if/when we require those memory barriers.
>
> Once we've identified these, we may want to fold some of those barriers
> back in, going from cmpxchg_relaxed() back to cmpxchg(). In particular
> when we see patterns like:
>
> do {
>
> } while (!try_cmpxchg_relaxed());
> smp_mb();
>
> or possibly:
>
> smp_mb();
> cmpxchg_relaxed(); /* no return value check */
It seems that we need more barriers than I expected. If we are able to
get rid of them by using cmpxchg() instead of cmpxchg_relaxed() then
it might be quite some simplification.
I have to admit that my understanding of barriers is more incomplete
than I have hooped for. I am less and less convinced that my ack is
enough to merge this patch. It would be great when PeterZ or another
expert on barriers might give it a cycle (or maybe wait for the next
version of this patch?).
Alternative solution is to do quite some testing and push it into
linux-next to give it even more testing. It seems that the main
danger is that some messages might get lost. But it should
not crash. Well, I would feel much more comfortable if I wasn't
the only reviewer.
> > On Tue 2020-01-28 17:25:47, John Ogness wrote:
> >> diff --git a/kernel/printk/printk_ringbuffer.c
> >> b/kernel/printk/printk_ringbuffer.c
> >> new file mode 100644
> >> index ..796257f226ee
> >> --- /dev/null
> >> +++ b/kernel/printk/printk_ringbuffer.c
> >> +/*
> >> + * Take a given descriptor out of the committed state by attempting
> >> + * the transition from committed to reusable. Either this task or some
> >> + * other task will have been successful.
> >> + */
> >> +static void desc_make_reusable(struct prb_desc_ring *desc_ring,
> >> + unsigned long id)
> >> +{
> >> + struct prb_desc *desc = to_desc(desc_ring, id);
> >> + atomic_long_t *state_var = >state_var;
> >> + unsigned long val_committed = id | DESC_COMMITTED_MASK;
> >> + unsigned long val_reusable = val_committed | DESC_REUSE_MASK;
> >> +
> >> + atomic_long_cmpxchg_relaxed(state_var, val_committed,
> >> val_reusable);
> >
> > IMHO, we should add smp_wmb() here to make sure that the reusable
> > state is written before we shuffle the desc_ring->tail_id/head_id.
> >
> > It would pair with the read part of smp_mb() in desc_reserve()
> > before the extra check if the descriptor is really in reusable state.
>
> Yes. Now that we added the extra state checking in desc_reserve(), this
> ordering has become important.
>
> However, for this case I would prefer to instead place a full memory
> barrier immediately before @tail_id is incremented (in
> desc_push_tail()). The tail-incrementing-task must have seen the
> reusable state (even if it is not the one that set it) and an
> incremented @tail_id must be visible to the task recycling a descriptor.
Ah, the below mentioned litmus tests for the full barrier in
desc_reserve() opened my eyes to see why full barrier is sometimes
needed instead of the write barrier.
I agree that this is exactly the place when the full barrier will be
needed. This write can happen on any CPU and the write
depending on this value might be done on another CPU.
Also I agree that desc_push_tail() looks like the right place
for the full barrier because some actions there are done only
when the descriptor is invalidated.
I just wonder if it should be even before data_push_tail()
calls. It will make sure that everyone sees the reusable state
before we move the data_ring borders.
Also I wonder whether we need even more full barriers in the code.
There are many more dependent actions that can be done on different
CPUs in parallel.
> >> +}
> >> +
> >> +/*
> >> + * For a given data ring (text or dict) and its current tail lpos:
> >> + * for each data block up until @lpos, make the associated descriptor
> >> + * reusable.
> >> + *
> >> + * If there is any problem making the associated descriptor reusable,
> >> + * either the descriptor has not yet been committed or another writer
> >> + * task has already pushed the tail lpos past the problematic data
> >> + * block. Regardless, on error the caller can re-load the tail lpos
> >> + * to determine the situation.
> >> + */
> >> +static bool data_make_reusable(struct printk_ringbuffer *rb,
> >> + struct prb_data_ring *data_ring,
> >> + unsigned long tail_lpos, unsigned long lpos,
> >> + unsigned long *lpos_out)
> >> +{
> >> + struct prb_desc_ring *desc_ring = >desc_ring;
> >> + struct
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On Tue 2020-03-03 16:42:07, John Ogness wrote:
> On 2020-03-03, Petr Mladek wrote:
> >> diff --git a/kernel/printk/printk_ringbuffer.c
> >> b/kernel/printk/printk_ringbuffer.c
> >> new file mode 100644
> >> index ..796257f226ee
> >> --- /dev/null
> >> +++ b/kernel/printk/printk_ringbuffer.c
> >> +/*
> >> + * Read the record @id and verify that it is committed and has the
> >> sequence
> >> + * number @seq. On success, 0 is returned.
> >> + *
> >> + * Error return values:
> >> + * -EINVAL: A committed record @seq does not exist.
> >> + * -ENOENT: The record @seq exists, but its data is not available.
> >> This is a
> >> + * valid record, so readers should continue with the next
> >> seq.
> >> + */
> >> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
> >> + unsigned long id, u64 seq,
> >> + struct prb_desc *desc)
> >> +{
> >>>
> @id _is_ very important because that is how descriptors are
> read. desc_read() takes @id as an argument and it is @id that identifies
> the descriptor. @seq is only meta-data within a descriptor. The only
> reason @seq is even checked is because of possible ABA issues with @id
> on 32-bit systems.
I think that the different view is because I look at this API
from the reader API side. It is called the following way:
prb_read_valid(, seq, )
_prb_read_valid( , , )
prb_read( , *seq, )
# id is read from address defined by seq
rdesc = dr->descs[seq & MASK];
id = rdesc->state_var && MASK_ID;
desc_read_commited( , id, seq, )
desc_read( , id, )
# desc is the same as rdesc above because
# seq & MASK == id & MASK
desc = dr->descs[id & MASK];
Note that prb_read_valid() and prb_read() are addressed by seq.
It would be perfectly fine to pass only seq to desc_read_committed()
and read id from inside.
The name desc_read_committed() suggests that the important condition
is that the descriptor is in the committed state. It is not obvious
that seq is important as well.
>From my POV, it will be more clear to pass only seq and rename the
function to desc_read_by_seq() or so:
+ seq is enough for addressing
+ function returns true only when the stored seq matches
+ the stored seq is valid only when the state is committed
or reusable
Please, do not reply to this mail. Either take the idea or keep
the code as is. I could live with it. And it is not important
enough to spend more time on it. I just wanted to explain my view.
But it is obviously just a personal preference.
Best Regards,
Petr
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On Mon 2020-03-02 14:43:41, John Ogness wrote:
> On 2020-03-02, Petr Mladek wrote:
> diff --git a/kernel/printk/printk_ringbuffer.c
> b/kernel/printk/printk_ringbuffer.c
> new file mode 100644
> index ..796257f226ee
> --- /dev/null
> +++ b/kernel/printk/printk_ringbuffer.c
> +/*
> + * Read the record @id and verify that it is committed and has the
> sequence
> + * number @seq. On success, 0 is returned.
> + *
> + * Error return values:
> + * -EINVAL: A committed record @seq does not exist.
> + * -ENOENT: The record @seq exists, but its data is not available. This
> is a
> + * valid record, so readers should continue with the next seq.
> + */
> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
> + unsigned long id, u64 seq,
> + struct prb_desc *desc)
> +{
> >
> > static enum desc_state
> > desc_read_by_seq(struct prb_desc_ring *desc_ring,
> > u64 seq, struct prb_desc *desc)
> > {
> > struct prb_desc *rdesc = to_desc(desc_ring, seq);
> > atomic_long_t *state_var = >state_var;
> > id = DESC_ID(atomic_long_read(state_var));
>
> I think it is error-prone to re-read @state_var here. It is lockless
> shared data. desc_read_committed() is called twice in prb_read() and it
> is expected that both calls are using the same @id.
>
> > enum desc_state d_state;
> >
> > d_state = desc_read(desc_ring, id, desc);
> > if (d_state == desc_miss ||
> > d_state == desc_reserved ||
> > desc->info.seq != seq)
> > return -EINVAL;
> >
> > if (d_state == desc_reusable)
> > return -ENOENT;
>
> I can use this refactoring.
>
> >
> > if (d_state != desc_committed)
> > return -EINVAL;
>
> I suppose you meant to remove this check and leave in the @blk_lpos
> check instead. If we're trying to minimize lines of code, the @blk_lpos
> check could be combined with the "== desc_reusable" check as well.
I am an idiot. I missed that the check "d_state != desc_committed"
will return -EINVAL also when desc_miss or desc_reserved.
I was too concentrated by the fact that desc->info.seq was checked
first even though it might contain garbage.
Also it did not help me much the note about blk_lpos. I did not
see how it was related to this code.
To sum up. The original code worked fine. But I would prefer my variant
that has more lines but it is somehow cleaner.
Best Regards,
Petr
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On 2020-03-03, Petr Mladek wrote:
>> diff --git a/kernel/printk/printk_ringbuffer.c
>> b/kernel/printk/printk_ringbuffer.c
>> new file mode 100644
>> index ..796257f226ee
>> --- /dev/null
>> +++ b/kernel/printk/printk_ringbuffer.c
>> +/*
>> + * Read the record @id and verify that it is committed and has the
>> sequence
>> + * number @seq. On success, 0 is returned.
>> + *
>> + * Error return values:
>> + * -EINVAL: A committed record @seq does not exist.
>> + * -ENOENT: The record @seq exists, but its data is not available. This
>> is a
>> + * valid record, so readers should continue with the next seq.
>> + */
>> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
>> + unsigned long id, u64 seq,
>> + struct prb_desc *desc)
>> +{
>>>
>>> OK, what about having desc_read_by_seq() instead?
>>
>> Well, it isn't actually "reading by seq". @seq is there for
>> additional verification. Yes, prb_read() is deriving @id from
>> @seq. But it only does this once and uses that value for both calls.
>
> I do not want to nitpick about words. If I get it properly,
> the "id" is not important here. Any "id" is fine as long as
> "seq" matches. Reading "id" once is just an optimization.
Your statement is incorrect. We are not nitpicking about words. I am
trying to clarify what you are misunderstanding.
@id _is_ very important because that is how descriptors are
read. desc_read() takes @id as an argument and it is @id that identifies
the descriptor. @seq is only meta-data within a descriptor. The only
reason @seq is even checked is because of possible ABA issues with @id
on 32-bit systems.
> I do not resist on the change. It was just an idea how to
> avoid confusion. I was confused more than once. But I might
> be the only one. The more strightforward code looked more
> important to me than the optimization.
I am sorry for the confusion. In preparation for v2 I have changed the
function description to:
/*
* Get a copy of a specified descriptor and verify that the record is
* committed and has the sequence number @seq. @seq is checked because
* of possible ABA issues with @id on 32-bit systems. On success, 0 is
* returned.
*
* Error return values:
* -EINVAL: A committed record @seq does not exist.
* -ENOENT: The record @seq exists, but its data is not available. This is a
* valid record, so readers should continue with the next seq.
*/
This is using the same language as the description of desc_read() so
that is it is hopefully clear that desc_read_committed() is an extended
version of desc_read().
>>> Also there is a bug in current desc_read_commited().
>>> desc->info.seq might contain a garbage when d_state is desc_miss
>>> or desc_reserved.
>>
>> It is not a bug. In both of those cases, -EINVAL is the correct return
>> value.
>
> No, it is a bug. If info is not read and contains garbage then the
> following check may pass by chance:
>
> if (desc->info.seq != seq)
> return -EINVAL;
>
> Then the function would return 0 even when desc_read() returned
> desc_miss or desc_reserved.
0 cannot be returned. The state is checked. Please let us stop this
bug/non-bug discussion. It is distracting us from clarifying this
function and refactoring it to simplify understanding.
>>> I would change it to:
>>>
>>> static enum desc_state
>>> desc_read_by_seq(struct prb_desc_ring *desc_ring,
>>> u64 seq, struct prb_desc *desc)
>>> {
>>> struct prb_desc *rdesc = to_desc(desc_ring, seq);
>>> atomic_long_t *state_var = >state_var;
>>> id = DESC_ID(atomic_long_read(state_var));
>>
>> I think it is error-prone to re-read @state_var here. It is lockless
>> shared data. desc_read_committed() is called twice in prb_read() and
>> it is expected that both calls are using the same @id.
>
> It is not error prone. If "id" changes then "seq" will not match.
@id is set during prb_reserve(). @seq (being mere meta-data) is set
_afterwards_. Your proposed multiple-deriving of @id from @seq would
work because the _state checks_ would catch it, not because @seq would
necessarily change.
But that logic is backwards. @seq is not what is important here. It is
only meta-data. On 64-bit systems the @seq checks could be safely
removed.
You may want to refer back to your private email [0] from last November
where you asked me to move this code out of prb_read() and into a helper
function. That may clarify what we are talking about (although I hope
the new function description is clear enough).
John Ogness
[0] private: 20191122122724.n6wlummg3ap56...@pathway.suse.cz
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On Mon 2020-03-02 14:43:41, John Ogness wrote:
> On 2020-03-02, Petr Mladek wrote:
> diff --git a/kernel/printk/printk_ringbuffer.c
> b/kernel/printk/printk_ringbuffer.c
> new file mode 100644
> index ..796257f226ee
> --- /dev/null
> +++ b/kernel/printk/printk_ringbuffer.c
> +/*
> + * Read the record @id and verify that it is committed and has the
> sequence
> + * number @seq. On success, 0 is returned.
> + *
> + * Error return values:
> + * -EINVAL: A committed record @seq does not exist.
> + * -ENOENT: The record @seq exists, but its data is not available. This
> is a
> + * valid record, so readers should continue with the next seq.
> + */
> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
> + unsigned long id, u64 seq,
> + struct prb_desc *desc)
> +{
> >
> > OK, what about having desc_read_by_seq() instead?
>
> Well, it isn't actually "reading by seq". @seq is there for additional
> verification. Yes, prb_read() is deriving @id from @seq. But it only
> does this once and uses that value for both calls.
I do not want to nitpick about words. If I get it properly,
the "id" is not important here. Any "id" is fine as long as
"seq" matches. Reading "id" once is just an optimization.
I do not resist on the change. It was just an idea how to
avoid confusion. I was confused more than once. But I might
be the only one. The more strightforward code looked more
important to me than the optimization.
> > Also there is a bug in current desc_read_commited().
> > desc->info.seq might contain a garbage when d_state is desc_miss
> > or desc_reserved.
>
> It is not a bug. In both of those cases, -EINVAL is the correct return
> value.
No, it is a bug. If info is not read and contains garbage then the
following check may pass by chance:
if (desc->info.seq != seq)
return -EINVAL;
Then the function would return 0 even when desc_read() returned
desc_miss or desc_reserved.
> > I would change it to:
> >
> > static enum desc_state
> > desc_read_by_seq(struct prb_desc_ring *desc_ring,
> > u64 seq, struct prb_desc *desc)
> > {
> > struct prb_desc *rdesc = to_desc(desc_ring, seq);
> > atomic_long_t *state_var = >state_var;
> > id = DESC_ID(atomic_long_read(state_var));
>
> I think it is error-prone to re-read @state_var here. It is lockless
> shared data. desc_read_committed() is called twice in prb_read() and it
> is expected that both calls are using the same @id.
It is not error prone. If "id" changes then "seq" will not match.
> > enum desc_state d_state;
> >
> > d_state = desc_read(desc_ring, id, desc);
> > if (d_state == desc_miss ||
> > d_state == desc_reserved ||
> > desc->info.seq != seq)
> > return -EINVAL;
> >
> > if (d_state == desc_reusable)
> > return -ENOENT;
>
> I can use this refactoring.
Yes please, "else" is not needed.
> >
> > if (d_state != desc_committed)
> > return -EINVAL;
>
> I suppose you meant to remove this check and leave in the @blk_lpos
> check instead.
Good catch, this check is superfluous.
> If we're trying to minimize lines of code, the @blk_lpos
> check could be combined with the "== desc_reusable" check as well.
Minimizing the lines of code was not my primary goal. I was just
confused by the function name. Also the fact that "seq" was the
important thing was well hidden.
Best Regards,
Petr
PS: I dived into the barriers and got lost. I hope that I will
be able to send something sensible in the end ;-)
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On 2020-03-02, Petr Mladek wrote:
diff --git a/kernel/printk/printk_ringbuffer.c
b/kernel/printk/printk_ringbuffer.c
new file mode 100644
index ..796257f226ee
--- /dev/null
+++ b/kernel/printk/printk_ringbuffer.c
+/*
+ * Read the record @id and verify that it is committed and has the
sequence
+ * number @seq. On success, 0 is returned.
+ *
+ * Error return values:
+ * -EINVAL: A committed record @seq does not exist.
+ * -ENOENT: The record @seq exists, but its data is not available. This
is a
+ * valid record, so readers should continue with the next seq.
+ */
+static int desc_read_committed(struct prb_desc_ring *desc_ring,
+ unsigned long id, u64 seq,
+ struct prb_desc *desc)
+{
>
> OK, what about having desc_read_by_seq() instead?
Well, it isn't actually "reading by seq". @seq is there for additional
verification. Yes, prb_read() is deriving @id from @seq. But it only
does this once and uses that value for both calls.
> Also there is a bug in current desc_read_commited().
> desc->info.seq might contain a garbage when d_state is desc_miss
> or desc_reserved.
It is not a bug. In both of those cases, -EINVAL is the correct return
value.
> I would change it to:
>
> static enum desc_state
> desc_read_by_seq(struct prb_desc_ring *desc_ring,
>u64 seq, struct prb_desc *desc)
> {
> struct prb_desc *rdesc = to_desc(desc_ring, seq);
> atomic_long_t *state_var = >state_var;
> id = DESC_ID(atomic_long_read(state_var));
I think it is error-prone to re-read @state_var here. It is lockless
shared data. desc_read_committed() is called twice in prb_read() and it
is expected that both calls are using the same @id.
> enum desc_state d_state;
>
> d_state = desc_read(desc_ring, id, desc);
> if (d_state == desc_miss ||
> d_state == desc_reserved ||
> desc->info.seq != seq)
> return -EINVAL;
>
> if (d_state == desc_reusable)
> return -ENOENT;
I can use this refactoring.
>
> if (d_state != desc_committed)
> return -EINVAL;
I suppose you meant to remove this check and leave in the @blk_lpos
check instead. If we're trying to minimize lines of code, the @blk_lpos
check could be combined with the "== desc_reusable" check as well.
>
> return 0;
> }
Thanks.
John Ogness
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On Mon 2020-03-02 11:38:42, John Ogness wrote:
> On 2020-02-21, Petr Mladek wrote:
> >> diff --git a/kernel/printk/printk_ringbuffer.c
> >> b/kernel/printk/printk_ringbuffer.c
> >> new file mode 100644
> >> index ..796257f226ee
> >> --- /dev/null
> >> +++ b/kernel/printk/printk_ringbuffer.c
> >> +/*
> >> + * Read the record @id and verify that it is committed and has the
> >> sequence
> >> + * number @seq. On success, 0 is returned.
> >> + *
> >> + * Error return values:
> >> + * -EINVAL: A committed record @seq does not exist.
> >> + * -ENOENT: The record @seq exists, but its data is not available. This
> >> is a
> >> + * valid record, so readers should continue with the next seq.
> >> + */
> >> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
> >> + unsigned long id, u64 seq,
> >> + struct prb_desc *desc)
> >> +{
> >
> > I was few times confused whether this function reads the descriptor
> > a safe way or not.
> >
> > Please, rename it to make it clear that does only a check.
> > For example, check_state_commited().
>
> This function _does_ read. It is a helper function of prb_read() to
> _read_ the descriptor. It is an extended version of desc_read() that
> also performs various checks that the descriptor is committed.
I see.
> I will update the function description to be more similar to desc_read()
> so that it is obvious that it is "getting a copy of a specified
> descriptor".
OK, what about having desc_read_by_seq() instead?
Also there is a bug in current desc_read_commited().
desc->info.seq might contain a garbage when d_state is desc_miss
or desc_reserved.
I would change it to:
static enum desc_state
desc_read_by_seq(struct prb_desc_ring *desc_ring,
u64 seq, struct prb_desc *desc)
{
struct prb_desc *rdesc = to_desc(desc_ring, seq);
atomic_long_t *state_var = >state_var;
id = DESC_ID(atomic_long_read(state_var));
enum desc_state d_state;
d_state = desc_read(desc_ring, id, desc);
if (d_state == desc_miss ||
d_state == desc_reserved ||
desc->info.seq != seq)
return -EINVAL;
if (d_state == desc_reusable)
return -ENOENT;
if (d_state != desc_committed)
return -EINVAL;
return 0;
}
Best Regards,
Petr
PS: I am going to dive into the barriers again to answer the last
letter about them.
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On Mon, 2020-03-02 at 11:38 +0100, John Ogness wrote:
> On 2020-02-21, Petr Mladek wrote:
> > > diff --git a/kernel/printk/printk_ringbuffer.c
> > > b/kernel/printk/printk_ringbuffer.c
[]
> > > +static struct prb_data_block *to_block(struct prb_data_ring *data_ring,
> > > +unsigned long begin_lpos)
> > > +{
> > > + char *data = _ring->data[DATA_INDEX(data_ring, begin_lpos)];
> > > +
> > > + return (struct prb_data_block *)data;
> >
> > Nit: Please, use "blk" instead of "data". I was slightly confused
> > because "data" is also one member of struct prb_data_block.
>
> OK.
trivia:
Perhaps use void * instead of char * and a direct return
and avoid the naming altogether.
static struct prb_data_block *to_block(struct prb_data_ring *data_ring,
unsigned long begin_lpos)
{
return (void *)_ring->data[DATA_INDEX(data_ring, begin_lpos)];
}
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: misc nits Re: [PATCH 1/2] printk: add lockless buffer
On 2020-02-21, Petr Mladek wrote:
>> diff --git a/kernel/printk/printk_ringbuffer.c
>> b/kernel/printk/printk_ringbuffer.c
>> new file mode 100644
>> index ..796257f226ee
>> --- /dev/null
>> +++ b/kernel/printk/printk_ringbuffer.c
>> +static struct prb_data_block *to_block(struct prb_data_ring *data_ring,
>> + unsigned long begin_lpos)
>> +{
>> +char *data = _ring->data[DATA_INDEX(data_ring, begin_lpos)];
>> +
>> +return (struct prb_data_block *)data;
>
> Nit: Please, use "blk" instead of "data". I was slightly confused
> because "data" is also one member of struct prb_data_block.
OK.
>> +/* The possible responses of a descriptor state-query. */
>> +enum desc_state {
>> +desc_miss, /* ID mismatch */
>> +desc_reserved, /* reserved, but still in use by writer */
>> +desc_committed, /* committed, writer is done */
>> +desc_reusable, /* free, not used by any writer */
>
> s/not used/not yet used/
OK.
>> +EXPORT_SYMBOL(prb_reserve);
>
> Please, do not export symbols if there are no plans to actually
> use them from modules. It will be easier to rework the code
> in the future. Nobody would need to worry about external
> users.
>
> Please, do so everywhere in the patchset.
You are correct.
The reason I exported them is that I could run my test module. But since
the test module will not be part of the kernel source, I'll just hack
the exports in when doing my testing.
>> +static char *get_data(struct prb_data_ring *data_ring,
>> + struct prb_data_blk_lpos *blk_lpos,
>> + unsigned long *data_size)
>> +{
>> +struct prb_data_block *db;
>> +
>> +/* Data-less data block description. */
>> +if (blk_lpos->begin == INVALID_LPOS &&
>> +blk_lpos->next == INVALID_LPOS) {
>> +return NULL;
>
> Nit: There is no need for "else" after return. checkpatch.pl usually
> complains about it ;-)
OK.
>> +/*
>> + * Read the record @id and verify that it is committed and has the sequence
>> + * number @seq. On success, 0 is returned.
>> + *
>> + * Error return values:
>> + * -EINVAL: A committed record @seq does not exist.
>> + * -ENOENT: The record @seq exists, but its data is not available. This is a
>> + * valid record, so readers should continue with the next seq.
>> + */
>> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
>> + unsigned long id, u64 seq,
>> + struct prb_desc *desc)
>> +{
>
> I was few times confused whether this function reads the descriptor
> a safe way or not.
>
> Please, rename it to make it clear that does only a check.
> For example, check_state_commited().
This function _does_ read. It is a helper function of prb_read() to
_read_ the descriptor. It is an extended version of desc_read() that
also performs various checks that the descriptor is committed.
I will update the function description to be more similar to desc_read()
so that it is obvious that it is "getting a copy of a specified
descriptor".
John Ogness
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
Re: more barriers: Re: [PATCH 1/2] printk: add lockless buffer
On 2020-02-21, Petr Mladek wrote:
> If I get it correctly, the used cmpxchg_relaxed() variants does not
> provide full barriers. They are just able to prevent parallel
> manipulation of the modified variable.
Correct.
I purposely avoided the full barriers of a successful cmpxchg() so that
we could clearly specify what we needed and why. As Andrea pointed out
[0], we need to understand if/when we require those memory barriers.
Once we've identified these, we may want to fold some of those barriers
back in, going from cmpxchg_relaxed() back to cmpxchg(). In particular
when we see patterns like:
do {
} while (!try_cmpxchg_relaxed());
smp_mb();
or possibly:
smp_mb();
cmpxchg_relaxed(); /* no return value check */
> On Tue 2020-01-28 17:25:47, John Ogness wrote:
>> diff --git a/kernel/printk/printk_ringbuffer.c
>> b/kernel/printk/printk_ringbuffer.c
>> new file mode 100644
>> index ..796257f226ee
>> --- /dev/null
>> +++ b/kernel/printk/printk_ringbuffer.c
>> +/*
>> + * Take a given descriptor out of the committed state by attempting
>> + * the transition from committed to reusable. Either this task or some
>> + * other task will have been successful.
>> + */
>> +static void desc_make_reusable(struct prb_desc_ring *desc_ring,
>> + unsigned long id)
>> +{
>> +struct prb_desc *desc = to_desc(desc_ring, id);
>> +atomic_long_t *state_var = >state_var;
>> +unsigned long val_committed = id | DESC_COMMITTED_MASK;
>> +unsigned long val_reusable = val_committed | DESC_REUSE_MASK;
>> +
>> +atomic_long_cmpxchg_relaxed(state_var, val_committed,
>> val_reusable);
>
> IMHO, we should add smp_wmb() here to make sure that the reusable
> state is written before we shuffle the desc_ring->tail_id/head_id.
>
> It would pair with the read part of smp_mb() in desc_reserve()
> before the extra check if the descriptor is really in reusable state.
Yes. Now that we added the extra state checking in desc_reserve(), this
ordering has become important.
However, for this case I would prefer to instead place a full memory
barrier immediately before @tail_id is incremented (in
desc_push_tail()). The tail-incrementing-task must have seen the
reusable state (even if it is not the one that set it) and an
incremented @tail_id must be visible to the task recycling a descriptor.
>> +}
>> +
>> +/*
>> + * For a given data ring (text or dict) and its current tail lpos:
>> + * for each data block up until @lpos, make the associated descriptor
>> + * reusable.
>> + *
>> + * If there is any problem making the associated descriptor reusable,
>> + * either the descriptor has not yet been committed or another writer
>> + * task has already pushed the tail lpos past the problematic data
>> + * block. Regardless, on error the caller can re-load the tail lpos
>> + * to determine the situation.
>> + */
>> +static bool data_make_reusable(struct printk_ringbuffer *rb,
>> + struct prb_data_ring *data_ring,
>> + unsigned long tail_lpos, unsigned long lpos,
>> + unsigned long *lpos_out)
>> +{
>> +struct prb_desc_ring *desc_ring = >desc_ring;
>> +struct prb_data_blk_lpos *blk_lpos;
>> +struct prb_data_block *blk;
>> +enum desc_state d_state;
>> +struct prb_desc desc;
>> +unsigned long id;
>> +
>> +/*
>> + * Using the provided @data_ring, point @blk_lpos to the correct
>> + * blk_lpos within the local copy of the descriptor.
>> + */
>> +if (data_ring == >text_data_ring)
>> +blk_lpos = _blk_lpos;
>> +else
>> +blk_lpos = _blk_lpos;
>> +
>> +/* Loop until @tail_lpos has advanced to or beyond @lpos. */
>> +while ((lpos - tail_lpos) - 1 < DATA_SIZE(data_ring)) {
>> +blk = to_block(data_ring, tail_lpos);
>
> IMHO, we need smp_rmb() here to make sure that we read blk->id
> that we written after pushing the tail_lpos.
>
> It would pair with the write barrier in data_alloc() before
> before writing blk->id. It is there after updating head_lpos.
> But head_lpos could be updated only after updating tail_lpos.
> See the comment in data_alloc() below.
I do not understand. @blk->id has a data dependency on the provided
@tail_lpos. A random @tail_lpos value could be passed to this function
and it will only make a descriptor state change if the associated
descriptor is in the committed state and points back to that @tail_lpos
value. That is always legal.
If the old @blk->id value is read (just before data_alloc() writes it),
then the following desc_read() will return with desc_miss. That is
correct. If the new @blk->id value is read (just after data_alloc()
writes it), desc_read() will return with desc_reserved. This is also
correct. Why would this code care about @head_lpos or @tail_lpos
ordering to @blk->id? Please explain.
>> +id = READ_ONCE(blk->id);
>> +
>> +d_state =
misc nits Re: [PATCH 1/2] printk: add lockless buffer
Hi,
there are few more small things that catched my eyes during review.
They are from the nits deparment.
On Tue 2020-01-28 17:25:47, John Ogness wrote:
> Introduce a multi-reader multi-writer lockless ringbuffer for storing
> the kernel log messages. Readers and writers may use their API from
> any context (including scheduler and NMI). This ringbuffer will make
> it possible to decouple printk() callers from any context, locking,
> or console constraints. It also makes it possible for readers to have
> full access to the ringbuffer contents at any time and context (for
> example from any panic situation).
>
> diff --git a/kernel/printk/printk_ringbuffer.c
> b/kernel/printk/printk_ringbuffer.c
> new file mode 100644
> index ..796257f226ee
> --- /dev/null
> +++ b/kernel/printk/printk_ringbuffer.c
> +/**
> + * DOC: printk_ringbuffer overview
I really like the overview.
> +/* A data block: maps to the raw data within the data ring. */
> +struct prb_data_block {
> + unsigned long id;
> + chardata[0];
> +};
> +
> +
> +static struct prb_data_block *to_block(struct prb_data_ring *data_ring,
> +unsigned long begin_lpos)
> +{
> + char *data = _ring->data[DATA_INDEX(data_ring, begin_lpos)];
> +
> + return (struct prb_data_block *)data;
Nit: Please, use "blk" instead of "data". I was slightly confused
because "data" is also one member of struct prb_data_block.
> +/* The possible responses of a descriptor state-query. */
> +enum desc_state {
> + desc_miss, /* ID mismatch */
> + desc_reserved, /* reserved, but still in use by writer */
> + desc_committed, /* committed, writer is done */
> + desc_reusable, /* free, not used by any writer */
s/not used/not yet used/
> +};
[...]
> +EXPORT_SYMBOL(prb_reserve);
Please, do not export symbols if there are no plans to actually
use them from modules. It will be easier to rework the code
in the future. Nobody would need to worry about external
users.
Please, do so everywhere in the patchset.
> +/*
> + * Given @blk_lpos, return a pointer to the raw data from the data block
> + * and calculate the size of the data part. A NULL pointer is returned
> + * if @blk_lpos specifies values that could never be legal.
> + *
> + * This function (used by readers) performs strict validation on the lpos
> + * values to possibly detect bugs in the writer code. A WARN_ON_ONCE() is
> + * triggered if an internal error is detected.
> + */
> +static char *get_data(struct prb_data_ring *data_ring,
> + struct prb_data_blk_lpos *blk_lpos,
> + unsigned long *data_size)
> +{
> + struct prb_data_block *db;
> +
> + /* Data-less data block description. */
> + if (blk_lpos->begin == INVALID_LPOS &&
> + blk_lpos->next == INVALID_LPOS) {
> + return NULL;
Nit: There is no need for "else" after return. checkpatch.pl usually
complains about it ;-)
> +
> + /* Regular data block: @begin less than @next and in same wrap. */
> + } else if (DATA_WRAPS(data_ring, blk_lpos->begin) ==
> +DATA_WRAPS(data_ring, blk_lpos->next) &&
> +blk_lpos->begin < blk_lpos->next) {
> + db = to_block(data_ring, blk_lpos->begin);
> + *data_size = blk_lpos->next - blk_lpos->begin;
> +
> + /* Wrapping data block: @begin is one wrap behind @next. */
> + } else if (DATA_WRAPS(data_ring,
> + blk_lpos->begin + DATA_SIZE(data_ring)) ==
> +DATA_WRAPS(data_ring, blk_lpos->next)) {
> + db = to_block(data_ring, 0);
> + *data_size = DATA_INDEX(data_ring, blk_lpos->next);
> +
> + /* Illegal block description. */
> + } else {
> + WARN_ON_ONCE(1);
> + return NULL;
> + }
> +
> + /* A valid data block will always be aligned to the ID size. */
> + if (WARN_ON_ONCE(blk_lpos->begin !=
> + ALIGN(blk_lpos->begin, sizeof(db->id))) ||
> + WARN_ON_ONCE(blk_lpos->next !=
> + ALIGN(blk_lpos->next, sizeof(db->id {
> + return NULL;
> + }
> +
> + /* A valid data block will always have at least an ID. */
> + if (WARN_ON_ONCE(*data_size < sizeof(db->id)))
> + return NULL;
> +
> + /* Subtract descriptor ID space from size to reflect data size. */
> + *data_size -= sizeof(db->id);
> +
> + return >data[0];
> +}
> +
> +/*
> + * Read the record @id and verify that it is committed and has the sequence
> + * number @seq. On success, 0 is returned.
> + *
> + * Error return values:
> + * -EINVAL: A committed record @seq does not exist.
> + * -ENOENT: The record @seq exists, but its data is not available. This is a
> + * valid record, so readers should continue with the next seq.
> + */
> +static int desc_read_committed(struct prb_desc_ring *desc_ring,
> +unsigned long id, u64
more barriers: Re: [PATCH 1/2] printk: add lockless buffer
Hi,
the new full barrier in desc_reserve() made me to think more about
the existing ones.
If I get it correctly, the used cmpxchg_relaxed() variants does
not provide full barriers. They are just able to prevent parallel
manipulation of the modified variable.
Because of this, I think that we need some more barriers to synchronize
reads and writes of the tail/head values of the three ring buffers.
See below for more details.
It is possible that some of the barriers are superfluous because
some read barriers are hidden in desc_read(). But I think that
barriers are sometimes needed even before the first read or
after the last read in desc_read().
On Tue 2020-01-28 17:25:47, John Ogness wrote:
> Introduce a multi-reader multi-writer lockless ringbuffer for storing
> the kernel log messages. Readers and writers may use their API from
> any context (including scheduler and NMI). This ringbuffer will make
> it possible to decouple printk() callers from any context, locking,
> or console constraints. It also makes it possible for readers to have
> full access to the ringbuffer contents at any time and context (for
> example from any panic situation).
>
> diff --git a/kernel/printk/printk_ringbuffer.c
> b/kernel/printk/printk_ringbuffer.c
> new file mode 100644
> index ..796257f226ee
> --- /dev/null
> +++ b/kernel/printk/printk_ringbuffer.c
> +/*
> + * Take a given descriptor out of the committed state by attempting
> + * the transition from committed to reusable. Either this task or some
> + * other task will have been successful.
> + */
> +static void desc_make_reusable(struct prb_desc_ring *desc_ring,
> +unsigned long id)
> +{
> + struct prb_desc *desc = to_desc(desc_ring, id);
> + atomic_long_t *state_var = >state_var;
> + unsigned long val_committed = id | DESC_COMMITTED_MASK;
> + unsigned long val_reusable = val_committed | DESC_REUSE_MASK;
> +
> + atomic_long_cmpxchg_relaxed(state_var, val_committed,
> val_reusable);
IMHO, we should add smp_wmb() here to make sure that the reusable
state is written before we shuffle the desc_ring->tail_id/head_id.
It would pair with the read part of smp_mb() in desc_reserve()
before the extra check if the descriptor is really in reusable state.
> +}
> +
> +/*
> + * For a given data ring (text or dict) and its current tail lpos:
> + * for each data block up until @lpos, make the associated descriptor
> + * reusable.
> + *
> + * If there is any problem making the associated descriptor reusable,
> + * either the descriptor has not yet been committed or another writer
> + * task has already pushed the tail lpos past the problematic data
> + * block. Regardless, on error the caller can re-load the tail lpos
> + * to determine the situation.
> + */
> +static bool data_make_reusable(struct printk_ringbuffer *rb,
> +struct prb_data_ring *data_ring,
> +unsigned long tail_lpos, unsigned long lpos,
> +unsigned long *lpos_out)
> +{
> + struct prb_desc_ring *desc_ring = >desc_ring;
> + struct prb_data_blk_lpos *blk_lpos;
> + struct prb_data_block *blk;
> + enum desc_state d_state;
> + struct prb_desc desc;
> + unsigned long id;
> +
> + /*
> + * Using the provided @data_ring, point @blk_lpos to the correct
> + * blk_lpos within the local copy of the descriptor.
> + */
> + if (data_ring == >text_data_ring)
> + blk_lpos = _blk_lpos;
> + else
> + blk_lpos = _blk_lpos;
> +
> + /* Loop until @tail_lpos has advanced to or beyond @lpos. */
> + while ((lpos - tail_lpos) - 1 < DATA_SIZE(data_ring)) {
> + blk = to_block(data_ring, tail_lpos);
IMHO, we need smp_rmb() here to make sure that we read blk->id
that we written after pushing the tail_lpos.
It would pair with the write barrier in data_alloc() before
before writing blk->id. It is there after updating head_lpos.
But head_lpos could be updated only after updating tail_lpos.
See the comment in data_alloc() below.
> + id = READ_ONCE(blk->id);
> +
> + d_state = desc_read(desc_ring, id,
> + ); /* LMM(data_make_reusable:A) */
> +
> + switch (d_state) {
> + case desc_miss:
> + return false;
> + case desc_reserved:
> + return false;
> + case desc_committed:
> + /*
> + * This data block is invalid if the descriptor
> + * does not point back to it.
> + */
> + if (blk_lpos->begin != tail_lpos)
> + return false;
> + desc_make_reusable(desc_ring, id);
> + break;
> + case desc_reusable:
> + /*
> + * This data block is invalid if the descriptor
Re: [PATCH 1/2] printk: add lockless buffer
On Tue, 28 Jan 2020 17:25:47 +0106
John Ogness wrote:
> diff --git a/kernel/printk/printk_ringbuffer.c
> b/kernel/printk/printk_ringbuffer.c
> new file mode 100644
> index ..796257f226ee
> --- /dev/null
> +++ b/kernel/printk/printk_ringbuffer.c
> @@ -0,0 +1,1370 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include
> +#include
> +#include
> +#include
> +#include
> +#include "printk_ringbuffer.h"
> +
> +/**
> + * DOC: printk_ringbuffer overview
> + *
> + * Data Structure
> + * --
> + * The printk_ringbuffer is made up of 3 internal ringbuffers::
> + *
> + * * desc_ring: A ring of descriptors. A descriptor contains all
> record
> + * meta data (sequence number, timestamp, loglevel, etc.)
> + * as well as internal state information about the record
> + * and logical positions specifying where in the other
> + * ringbuffers the text and dictionary strings are
> + * located.
> + *
> + * * text_data_ring: A ring of data blocks. A data block consists of an
> + * unsigned long integer (ID) that maps to a desc_ring
> + * index followed by the text string of the record.
> + *
> + * * dict_data_ring: A ring of data blocks. A data block consists of an
> + * unsigned long integer (ID) that maps to a desc_ring
> + * index followed by the dictionary string of the record.
> + *
> + * Implementation
> + * --
> + *
> + * ABA Issues
> + * ~~
> + * To help avoid ABA issues, descriptors are referenced by IDs (index values
> + * with tagged states) and data blocks are referenced by logical positions
> + * (index values with tagged states). However, on 32-bit systems the number
> + * of tagged states is relatively small such that an ABA incident is (at
> + * least theoretically) possible. For example, if 4 million maximally sized
4 million? I'm guessing that maximally sized printk messages are 1k?
Perhaps say that, otherwise one might think this is a mistake. "4
million maximally sized (1k) printk messages"
> + * printk messages were to occur in NMI context on a 32-bit system, the
> + * interrupted task would not be able to recognize that the 32-bit integer
> + * wrapped and thus represents a different data block than the one the
> + * interrupted task expects.
> + *
> + * To help combat this possibility, additional state checking is performed
> + * (such as using cmpxchg() even though set() would suffice). These extra
> + * checks will hopefully catch any ABA issue that a 32-bit system might
> + * experience.
> + *
[..]
> + * Usage
> + * -
> + * Here are some simple examples demonstrating writers and readers. For the
> + * examples a global ringbuffer (test_rb) is available (which is not the
> + * actual ringbuffer used by printk)::
> + *
> + * DECLARE_PRINTKRB(test_rb, 15, 5, 3);
> + *
> + * This ringbuffer allows up to 32768 records (2 ^ 15) and has a size of
> + * 1 MiB (2 ^ 20) for text data and 256 KiB (2 ^ 18) for dictionary data.
(2 ^ (15 + 5)) ... (2 ^ (15 + 3)) ?
I'll play around more with this this week. But so far it looks good.
-- Steve
> + *
> + * Sample writer code::
> + *
> + * struct prb_reserved_entry e;
> + * struct printk_record r;
> + *
> + * // specify how much to allocate
> + * r.text_buf_size = strlen(textstr) + 1;
> + * r.dict_buf_size = strlen(dictstr) + 1;
> + *
> + * if (prb_reserve(, _rb, )) {
> + * snprintf(r.text_buf, r.text_buf_size, "%s", textstr);
> + *
> + * // dictionary allocation may have failed
> + * if (r.dict_buf)
> + * snprintf(r.dict_buf, r.dict_buf_size, "%s", dictstr);
> + *
> + * r.info->ts_nsec = local_clock();
> + *
> + * prb_commit();
> + * }
> + *
___
kexec mailing list
kexec@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/kexec
