lkml.org 
[lkml]   [2019]   [Jun]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    SubjectRe: [RFC PATCH v2 1/2] printk-rb: add a new printk ringbuffer implementation
    Date
    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

    \
     
     \ /
      Last update: 2019-06-30 04:05    [W:4.402 / U:0.592 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site