Message-ID: <20210526144543.GP28060@e120937-lin>
Date:   Wed, 26 May 2021 15:45:43 +0100
From:   Cristian Marussi <cristian.marussi@....com>
To:     Jim Quinlan <james.quinlan@...adcom.com>
Cc:     open list <linux-kernel@...r.kernel.org>,
        "moderated list:BROADCOM BCM2711/BCM2835 ARM ARCHITECTURE" 
        <linux-arm-kernel@...ts.infradead.org>,
        Sudeep Holla <sudeep.holla@....com>,
        Jonathan Cameron <Jonathan.Cameron@...wei.com>,
        Florian Fainelli <f.fainelli@...il.com>,
        etienne.carriere@...aro.org, vincent.guittot@...aro.org,
        Souvik Chakravarty <souvik.chakravarty@....com>
Subject: Re: [PATCH 3/4] firmware: arm_scmi: Introduce monotonically
 increasing tokens

Hi Jim,

On Tue, May 25, 2021 at 09:47:41AM -0400, Jim Quinlan wrote:
> On Mon, May 24, 2021 at 7:15 PM Cristian Marussi <cristian.marussi@....com>
> wrote:
> 
> > Tokens are sequence numbers embedded in the each SCMI message header: they
> > are used to correlate commands with responses (and delayed responses), but
> > their usage and policy of selection is entirely up to the caller (usually
> > the OSPM agent), while they are completely opaque to the callee (SCMI
> > server platform) which merely copies them back from the command into the
> > response message header.
> > This also means that the platform does not, can not and should not enforce
> > any kind of policy on received messages depending on the contained sequence
> > number: platform can perfectly handle concurrent requests carrying the same
> > identifiying token if that should happen.
> >
> > Moreover the platform is not required to produce in-order responses to
> > agent requests, the only constraint in these regards is that in case of
> > an asynchronous message the delayed response must be sent after the
> > immediate response for the synchronous part of the command transaction.
> >
> > Currenly the SCMI stack of the OSPM agent selects as token for the
> > egressing commands the lowest possible number which is not already in use
> > by an existing in-flight transaction, which means, in other words, that
> > we immediately reuse any token after its transaction has completed or it
> > has timed out: this indeed simplifies token and associated xfer management
> > and lookup.
> >
> > Under the above assumptions and constraints, since there is really no state
> > shared between the agent and the platform to let the platform know when a
> > token and its associated message has timed out, the current policy of early
> > reuse of tokens can easily lead to the situation in which a spurios or late
> > received response (or delayed_response), related to an old stale and timed
> > out transaction, can be wrongly associated to a newer valid in-flight xfer
> > that just happens to have reused the same token.
> >
> > This misbehavior on such ghost responses is more easily exposed on those
> > transports that naturally have an higher level of parallelism in processing
> > multiple concurrent in-flight messages.
> >
> > This commit introduces a new policy of selection of tokens for the OSPM
> > agent: each new transfer now gets the next available and monotonically
> > increasing token, until tokens are exhausted and the counter rolls over.
> >
> > Such new policy mitigates the above issues with ghost responses since the
> > tokens are now reused as later as possible (when they roll back ideally)
> > and so it is much easier to identify ghost responses to stale timed out
> > transactions: this also helps in simplifying the specific transports
> > implementation since stale transport messages can be easily identified
> > and discarded early on in the rx path without the need to cross check
> > their actual sate with the core transport layer.
> > This mitigation is even more effective when, as is usual the case, the
> > maximum number of pending messages is capped by the platform to a much
> > lower value than whole possible range of tokens.(2^10)
> >
> > This internal policy change in the core SCMI transport layer is fully
> > transparent to the specific transports so it has not and should not have
> > any impact on the transports implementation.
> >
> > The empirically observed cost of such new procedure of token selection
> > amounts in the best case to ~10us out of an observed full transaction cost
> > of 3ms for the completion of a synchronous sensor reading command on a
> > platform supporting commmands completion interrupts.
> >
> > Signed-off-by: Cristian Marussi <cristian.marussi@....com>
> > ---
> >  drivers/firmware/arm_scmi/common.h |  23 +++
> >  drivers/firmware/arm_scmi/driver.c | 245 +++++++++++++++++++++++++----
> >  2 files changed, 234 insertions(+), 34 deletions(-)
> >
> > diff --git a/drivers/firmware/arm_scmi/common.h
> > b/drivers/firmware/arm_scmi/common.h
> > index 4bd43863c306..aba8f1efdd2b 100644
> > --- a/drivers/firmware/arm_scmi/common.h
> > +++ b/drivers/firmware/arm_scmi/common.h
> > @@ -14,7 +14,10 @@
> >  #include <linux/device.h>
> >  #include <linux/errno.h>
> >  #include <linux/kernel.h>
> > +#include <linux/hashtable.h>
> > +#include <linux/list.h>
> >  #include <linux/module.h>
> > +#include <linux/refcount.h>
> >  #include <linux/scmi_protocol.h>
> >  #include <linux/types.h>
> >
> > @@ -127,6 +130,21 @@ struct scmi_msg {
> >         size_t len;
> >  };
> >
> > +/**
> > + * An helper macro to lookup an xfer from the @pending_xfers hashtable
> > + * using the message sequence number token as a key.
> > + */
> > +#define XFER_FIND(__ht, __k)                                   \
> > +({                                                             \
> > +       typeof(__k) k_ = __k;                                   \
> > +       struct scmi_xfer *xfer_ = NULL;                         \
> > +                                                               \
> > +       hash_for_each_possible((__ht), xfer_, node, k_)         \
> > +               if (xfer_->hdr.seq == k_)                       \
> > +                       break;                                  \
> > +        xfer_;                                                 \
> > +})
> > +
> >  /**
> >   * struct scmi_xfer - Structure representing a message flow
> >   *
> > @@ -138,6 +156,9 @@ struct scmi_msg {
> >   *     buffer for the rx path as we use for the tx path.
> >   * @done: command message transmit completion event
> >   * @async_done: pointer to delayed response message received event
> > completion
> > + * @users: A refcount to track the active users for this xfer
> > + * @node: An hlist_node reference used to store this xfer, alternatively,
> > on
> > + *       the free list @free_xfers or in the @pending_xfers hashtable
> >   */
> >  struct scmi_xfer {
> >         int transfer_id;
> > @@ -146,6 +167,8 @@ struct scmi_xfer {
> >         struct scmi_msg rx;
> >         struct completion done;
> >         struct completion *async_done;
> > +       refcount_t users;
> > +       struct hlist_node node;
> >  };
> >
> >  struct scmi_xfer_ops;
> > diff --git a/drivers/firmware/arm_scmi/driver.c
> > b/drivers/firmware/arm_scmi/driver.c
> > index b4c69141eca1..ab975c74cab1 100644
> > --- a/drivers/firmware/arm_scmi/driver.c
> > +++ b/drivers/firmware/arm_scmi/driver.c
> > @@ -21,6 +21,7 @@
> >  #include <linux/io.h>
> >  #include <linux/kernel.h>
> >  #include <linux/ktime.h>
> > +#include <linux/hashtable.h>
> >  #include <linux/list.h>
> >  #include <linux/module.h>
> >  #include <linux/of_address.h>
> > @@ -65,19 +66,29 @@ struct scmi_requested_dev {
> >         struct list_head node;
> >  };
> >
> > +#define SCMI_PENDING_XFERS_HT_ORDER_SZ 9
> > +
> >  /**
> >   * struct scmi_xfers_info - Structure to manage transfer information
> >   *
> > - * @xfer_block: Preallocated Message array
> >   * @xfer_alloc_table: Bitmap table for allocated messages.
> >   *     Index of this bitmap table is also used for message
> >   *     sequence identifier.
> >   * @xfer_lock: Protection for message allocation
> > + * @last_token: A counter to use as base to generate for monotonically
> > + *             increasing tokens.
> > + * @free_xfers: A free list for available to use xfers. It is initialized
> > with
> > + *             a number of xfers equal to the maximum allowed in-flight
> > + *             messages.
> > + * @pending_xfers: An hashtable, indexed by msg_hdr.seq, used to keep all
> > the
> > + *                currently in-flight messages.
> >   */
> >  struct scmi_xfers_info {
> > -       struct scmi_xfer *xfer_block;
> >         unsigned long *xfer_alloc_table;
> >         spinlock_t xfer_lock;
> > +       atomic_t last_token;
> > +       struct hlist_head free_xfers;
> > +       DECLARE_HASHTABLE(pending_xfers, SCMI_PENDING_XFERS_HT_ORDER_SZ);
> >  };
> >
> >  /**
> > @@ -203,6 +214,117 @@ void *scmi_notification_instance_data_get(const
> > struct scmi_handle *handle)
> >         return info->notify_priv;
> >  }
> >
> > +/**
> > + * scmi_xfer_token_set  - Reserve and set new token for the xfer at hand
> > + *
> > + * @minfo: Pointer to Tx/Rx Message management info based on channel type
> > + * @xfer: The xfer to act upon
> > + *
> > + * Pick the next unused monotonically increasing token and set it into
> > + * xfer->hdr.seq: picking a monotonically increasing value avoids reusing
> > + * immediately tokens of just completed or timed-out xfers, mitigating
> > the risk
> > + * of wrongly associating a late received answer for an expired xfer to a
> > live
> > + * in-flight transaction which happened to have reused the same token.
> > + *
> > + * Since platform is NOT required to answer our request in-order we should
> > + * account for a few rare but possible scenarios:
> > + *
> > + *  - exactly 'next_token' may be NOT available so pick xfer_id >=
> > next_token
> > + *    using find_next_zero_bit() starting from candidate next_token bit
> > + *
> > + *  - all tokens ahead upto (MSG_TOKEN_ID_MASK - 1) are used in-flight
> > but we
> > + *    are plenty of free tokens at start, so try a second pass using
> > + *    find_next_zero_bit() and starting from 0.
> > + *
> > + *  X = used in-flight
> > + *
> > + * Normal
> > + * ------
> > + *
> > + *             |- xfer_id picked
> > + *
> >  -----------+----------------------------------------------------------
> > + *   | | |X|X|X| | | | | | ... ... ... ... ... ... ... ... ... ...
> > ...|X|X|
> > + *
> >  ----------------------------------------------------------------------
> > + *             ^
> > + *             |- next_token
> > + *
> > + * Out-of-order pending at start
> > + * -----------------------------
> > + *
> > + *       |- xfer_id picked, last_token fixed
> > + *
> >  -----+----------------------------------------------------------------
> > + *   |X|X| | | | |X|X| ... ... ... ... ... ... ... ... ... ... ... ...|X|
> > |
> > + *
> >  ----------------------------------------------------------------------
> > + *    ^
> > + *    |- next_token
> > + *
> > + *
> > + * Out-of-order pending at end
> > + * ---------------------------
> > + *
> > + *       |- xfer_id picked, last_token fixed
> > + *
> >  -----+----------------------------------------------------------------
> > + *   |X|X| | | | |X|X| ... ... ... ... ... ... ... ... ... ...
> > |X|X|X||X|X|
> > + *
> >  ----------------------------------------------------------------------
> > + *                                                             ^
> > + *                                                             |-
> > next_token
> > + *
> > + * Context: Assumes to be called with @xfer_lock already acquired.
> > + *
> > + * Return: 0 on Success or error
> > + */
> > +static int scmi_xfer_token_set(struct scmi_xfers_info *minfo,
> > +                              struct scmi_xfer *xfer)
> > +{
> > +       unsigned long xfer_id, next_token;
> > +
> > +       /* Pick a candidate monotonic token in range [0, MSG_TOKEN_MAX -
> > 1] */
> > +       next_token = (atomic_inc_return(&minfo->last_token) &
> > +                     (MSG_TOKEN_MAX - 1));
> > +
> > +       /* Pick the next available xfer_id >= next_token */
> > +       xfer_id = find_next_zero_bit(minfo->xfer_alloc_table,
> > +                                    MSG_TOKEN_MAX, next_token);
> > +       if (xfer_id == MSG_TOKEN_MAX) {
> > +               /*
> > +                * After heavily out-of-order responses, there are no free
> > +                * tokens ahead, but only at start of xfer_alloc_table so
> > +                * try again from the beginning.
> > +                */
> > +               xfer_id = find_next_zero_bit(minfo->xfer_alloc_table,
> > +                                            MSG_TOKEN_MAX, 0);
> > +               /*
> > +                * Something is wrong if we got here since there can be a
> > +                * maximum number of (MSG_TOKEN_MAX - 1) in-flight messages
> > +                * but we have not found any free token [0, MSG_TOKEN_MAX
> > - 1].
> > +                */
> > +               if (WARN_ON_ONCE(xfer_id == MSG_TOKEN_MAX))
> > +                       return -ENOMEM;
> > +       }
> > +
> > +       /* Update +/- last_token accordingly if we skept some hole */
> >
> s/skept/skipped/
> 
> This commit  is helpful.
> 

Thanks for the feeback.
Cristian

> Thanks,
> Jim Quinlan
> Broadcom STB
> 
> > +       if (xfer_id != next_token)
> > +               atomic_add((int)(xfer_id - next_token),
> > &minfo->last_token);
> > +
> > +       /* Set in-flight */
> > +       set_bit(xfer_id, minfo->xfer_alloc_table);
> > +       xfer->hdr.seq = (u16)xfer_id;
> > +
> > +       return 0;
> > +}
> > +
> > +/**
> > + * scmi_xfer_token_clear  - Release the token
> > + *
> > + * @minfo: Pointer to Tx/Rx Message management info based on channel type
> > + * @xfer: The xfer to act upon
> > + */
> > +static inline void scmi_xfer_token_clear(struct scmi_xfers_info *minfo,
> > +                                        struct scmi_xfer *xfer)
> > +{
> > +       clear_bit(xfer->hdr.seq, minfo->xfer_alloc_table);
> > +}
> > +
> >  /**
> >   * scmi_xfer_get() - Allocate one message
> >   *
> > @@ -212,37 +334,50 @@ void *scmi_notification_instance_data_get(const
> > struct scmi_handle *handle)
> >   * Helper function which is used by various message functions that are
> >   * exposed to clients of this driver for allocating a message traffic
> > event.
> >   *
> > - * This function can sleep depending on pending requests already in the
> > system
> > - * for the SCMI entity. Further, this also holds a spinlock to maintain
> > - * integrity of internal data structures.
> > + * Picks an xfer from the free list @free_xfers (if any available), sets a
> > + * monotonically increasing token and stores the inflight xfer into the
> > + * @pending_xfers hashtable for later retrieval.
> > + *
> > + * The successfully initialized xfer is refcounted.
> > + *
> > + * Context: Holds @xfer_lock while manipulating @xfer_alloc_table and
> > + *         @free_xfers.
> >   *
> >   * Return: 0 if all went fine, else corresponding error.
> >   */
> >  static struct scmi_xfer *scmi_xfer_get(const struct scmi_handle *handle,
> >                                        struct scmi_xfers_info *minfo)
> >  {
> > -       u16 xfer_id;
> > +       int ret;
> > +       unsigned long flags;
> >         struct scmi_xfer *xfer;
> > -       unsigned long flags, bit_pos;
> > -       struct scmi_info *info = handle_to_scmi_info(handle);
> >
> > -       /* Keep the locked section as small as possible */
> >         spin_lock_irqsave(&minfo->xfer_lock, flags);
> > -       bit_pos = find_first_zero_bit(minfo->xfer_alloc_table,
> > -                                     info->desc->max_msg);
> > -       if (bit_pos == info->desc->max_msg) {
> > +       if (hlist_empty(&minfo->free_xfers)) {
> >                 spin_unlock_irqrestore(&minfo->xfer_lock, flags);
> >                 return ERR_PTR(-ENOMEM);
> >         }
> > -       set_bit(bit_pos, minfo->xfer_alloc_table);
> > -       spin_unlock_irqrestore(&minfo->xfer_lock, flags);
> >
> > -       xfer_id = bit_pos;
> > +       /* grab an xfer from the free_list */
> > +       xfer = hlist_entry(minfo->free_xfers.first, struct scmi_xfer,
> > node);
> > +       hlist_del_init(&xfer->node);
> >
> > -       xfer = &minfo->xfer_block[xfer_id];
> > -       xfer->hdr.seq = xfer_id;
> > -       reinit_completion(&xfer->done);
> > -       xfer->transfer_id = atomic_inc_return(&transfer_last_id);
> > +       /* Pick and set monotonic token */
> > +       ret = scmi_xfer_token_set(minfo, xfer);
> > +       if (!ret) {
> > +               hash_add(minfo->pending_xfers, &xfer->node, xfer->hdr.seq);
> > +       } else {
> > +               dev_err(handle->dev, "Failed to get monotonic token %d\n",
> > ret);
> > +               hlist_add_head(&xfer->node, &minfo->free_xfers);
> > +               xfer = ERR_PTR(ret);
> > +       }
> > +       spin_unlock_irqrestore(&minfo->xfer_lock, flags);
> > +
> > +       if (!IS_ERR(xfer)) {
> > +               refcount_set(&xfer->users, 1);
> > +               reinit_completion(&xfer->done);
> > +               xfer->transfer_id = atomic_inc_return(&transfer_last_id);
> > +       }
> >
> >         return xfer;
> >  }
> > @@ -253,6 +388,9 @@ static struct scmi_xfer *scmi_xfer_get(const struct
> > scmi_handle *handle,
> >   * @minfo: Pointer to Tx/Rx Message management info based on channel type
> >   * @xfer: message that was reserved by scmi_xfer_get
> >   *
> > + * After refcount check, possibly release an xfer, clearing the token
> > slot,
> > + * removing xfer from @pending_xfers and putting it back into free_xfers.
> > + *
> >   * This holds a spinlock to maintain integrity of internal data
> > structures.
> >   */
> >  static void
> > @@ -260,16 +398,41 @@ __scmi_xfer_put(struct scmi_xfers_info *minfo,
> > struct scmi_xfer *xfer)
> >  {
> >         unsigned long flags;
> >
> > -       /*
> > -        * Keep the locked section as small as possible
> > -        * NOTE: we might escape with smp_mb and no lock here..
> > -        * but just be conservative and symmetric.
> > -        */
> >         spin_lock_irqsave(&minfo->xfer_lock, flags);
> > -       clear_bit(xfer->hdr.seq, minfo->xfer_alloc_table);
> > +       if (refcount_dec_and_test(&xfer->users)) {
> > +               scmi_xfer_token_clear(minfo, xfer);
> > +               hash_del(&xfer->node);
> > +               hlist_add_head(&xfer->node, &minfo->free_xfers);
> > +       }
> >         spin_unlock_irqrestore(&minfo->xfer_lock, flags);
> >  }
> >
> > +/**
> > + * scmi_xfer_lookup_unlocked  -  Helper to lookup an xfer_id
> > + *
> > + * @minfo: Pointer to Tx/Rx Message management info based on channel type
> > + * @xfer_id: Token ID to lookup in @pending_xfers
> > + *
> > + * Refcounting is untouched.
> > + *
> > + * Context: Assumes to be called with @xfer_lock already acquired.
> > + *
> > + * Return: A valid xfer on Success or error otherwise
> > + */
> > +static struct scmi_xfer *
> > +scmi_xfer_lookup_unlocked(struct scmi_xfers_info *minfo, u16 xfer_id)
> > +{
> > +       struct scmi_xfer *xfer = NULL;
> > +
> > +       if (xfer_id >= MSG_TOKEN_MAX)
> > +               return ERR_PTR(-EINVAL);
> > +
> > +       if (test_bit(xfer_id, minfo->xfer_alloc_table))
> > +               xfer = XFER_FIND(minfo->pending_xfers, xfer_id);
> > +
> > +       return xfer ?: ERR_PTR(-EINVAL);
> > +}
> > +
> >  static void scmi_handle_notification(struct scmi_chan_info *cinfo, u32
> > msg_hdr)
> >  {
> >         struct scmi_xfer *xfer;
> > @@ -306,19 +469,22 @@ static void scmi_handle_notification(struct
> > scmi_chan_info *cinfo, u32 msg_hdr)
> >  static void scmi_handle_response(struct scmi_chan_info *cinfo,
> >                                  u16 xfer_id, u8 msg_type)
> >  {
> > +       unsigned long flags;
> >         struct scmi_xfer *xfer;
> >         struct device *dev = cinfo->dev;
> >         struct scmi_info *info = handle_to_scmi_info(cinfo->handle);
> >         struct scmi_xfers_info *minfo = &info->tx_minfo;
> >
> >         /* Are we even expecting this? */
> > -       if (!test_bit(xfer_id, minfo->xfer_alloc_table)) {
> > +       spin_lock_irqsave(&minfo->xfer_lock, flags);
> > +       xfer = scmi_xfer_lookup_unlocked(minfo, xfer_id);
> > +       spin_unlock_irqrestore(&minfo->xfer_lock, flags);
> > +       if (IS_ERR(xfer)) {
> >                 dev_err(dev, "message for %d is not expected!\n", xfer_id);
> >                 info->desc->ops->clear_channel(cinfo);
> >                 return;
> >         }
> >
> > -       xfer = &minfo->xfer_block[xfer_id];
> >         /*
> >          * Even if a response was indeed expected on this slot at this
> > point,
> >          * a buggy platform could wrongly reply feeding us an unexpected
> > @@ -1036,18 +1202,25 @@ static int __scmi_xfer_info_init(struct scmi_info
> > *sinfo,
> >                 return -EINVAL;
> >         }
> >
> > -       info->xfer_block = devm_kcalloc(dev, desc->max_msg,
> > -                                       sizeof(*info->xfer_block),
> > GFP_KERNEL);
> > -       if (!info->xfer_block)
> > -               return -ENOMEM;
> > +       hash_init(info->pending_xfers);
> >
> > -       info->xfer_alloc_table = devm_kcalloc(dev,
> > BITS_TO_LONGS(desc->max_msg),
> > +       /* Allocate a bitmask sized to hold MSG_TOKEN_MAX tokens */
> > +       info->xfer_alloc_table = devm_kcalloc(dev,
> > BITS_TO_LONGS(MSG_TOKEN_MAX),
> >                                               sizeof(long), GFP_KERNEL);
> >         if (!info->xfer_alloc_table)
> >                 return -ENOMEM;
> >
> > -       /* Pre-initialize the buffer pointer to pre-allocated buffers */
> > -       for (i = 0, xfer = info->xfer_block; i < desc->max_msg; i++,
> > xfer++) {
> > +       /*
> > +        * Preallocate a number of xfers equal to max inflight messages,
> > +        * pre-initialize the buffer pointer to pre-allocated buffers and
> > +        * attach all of them to the free list
> > +        */
> > +       INIT_HLIST_HEAD(&info->free_xfers);
> > +       for (i = 0; i < desc->max_msg; i++) {
> > +               xfer = devm_kzalloc(dev, sizeof(*xfer), GFP_KERNEL);
> > +               if (!xfer)
> > +                       return -ENOMEM;
> > +
> >                 xfer->rx.buf = devm_kcalloc(dev, sizeof(u8),
> > desc->max_msg_size,
> >                                             GFP_KERNEL);
> >                 if (!xfer->rx.buf)
> > @@ -1055,8 +1228,12 @@ static int __scmi_xfer_info_init(struct scmi_info
> > *sinfo,
> >
> >                 xfer->tx.buf = xfer->rx.buf;
> >                 init_completion(&xfer->done);
> > +
> > +               /* Add initialized xfer to the free list */
> > +               hlist_add_head(&xfer->node, &info->free_xfers);
> >         }
> >
> > +       atomic_set(&info->last_token, -1);
> >         spin_lock_init(&info->xfer_lock);
> >
> >         return 0;
> > --
> > 2.17.1
> >
> >

Powered by blists - more mailing lists