Messages in this thread | | | From | John Ogness <> | Subject | Re: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation | Date | Sun, 30 Jun 2019 04:03:34 +0200 |
| |
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
| |