Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation

John Ogness
2019-06-30T02:04:26Z

On 2019-06-29, Andrea Parri <andrea.parri@amarulasolutions.com> wrote:
>> /**
>> * 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);
>
> /* C */
>
>
>>
>> do {
>> newest_id = READ_ONCE(l->newest);
>
> /* A */
>
>
>> 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);
>
> /* 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?

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

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

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