Messages in this thread | | | Date | Mon, 2 Aug 2021 11:24:25 +0100 | From | Sudeep Holla <> | Subject | Re: [PATCH v6 06/17] firmware: arm_scmi: Introduce monotonically increasing tokens |
| |
On Wed, Jul 28, 2021 at 05:54:30PM +0100, Cristian Marussi wrote: > On Wed, Jul 28, 2021 at 03:17:46PM +0100, Sudeep Holla wrote: > > On Mon, Jul 12, 2021 at 03:18:22PM +0100, Cristian Marussi wrote:
[...]
> > > > > > +#define SCMI_PENDING_XFERS_HT_ORDER_SZ 9 > > > + > > > > Is there any particular reason to choose half the token size as hash bucket > > size ? IOW why not 1/3 or 1/4th of it ? I would appreciate a comment here. > > I see it is mentioned in the commit log. Also is it not better to associate > > or keep it close to MSG_TOKEN_ID_MASK and associated macros. > > > > I'll move this in the proper place where associated macros are defined. > > The reason for the size choice is tricky (and not sure about its value > still...so I have not commented yet :D); the ideal size of this hashtable would > be desc->max_msg so equal to the maximum number of inflight messages allowed on > the system in order to minimize (probably to zero) collisions on the hashtable: > unfortunately max_msg is only finally available at runtime time and the > kernel hashtable is statically sized by design.... > > I tried to play some tricks to define dynamically the size but everything falls > apart since a lot of stuff in linux/hashtable.h is based on ARRAY_SIZE() and > friends (to speedup all I suppose). Another non-fit (in my opinion) > alternative would be using relativistic hashtable (linux/rhashtable.h) but > those are definitely overkill in our case since they are hashtables that > can be resized completely at runtime while populated O_o. (with even > more overhead) > > At the end the size that fits all possible in-flight messages minimizing > collisions in any possible case that I can set at compile time would be 10, > which means really 2^10 1024 HT entries (equal to MAX_MSG_TOKEN) each of which > is a struct list_head (*prev,*next 16bytes) i.e. 16KB HT: Peter pointed out > that it would be a lot of wasted space on normal systems in which max in-flight > messages are far-less than 1024 AND would not even fit in one 4Kb page, so I > reduced it to 512 entries but the best would be 256 (8) if we want to > fit in one regular 4kb page. The drawback will be a bit of HT collisions on > system with more than 256 possible and effective in-flight messages. >
I agree, 256 should be fine for now. Just add a note that it is chosen to fit a page and can be updated if required.
> > > /** > > > * 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; > > > > Can we merge this and transfer_last_id ? Let this be free running like > > transfer_last_id and just use [0-9] from this ? I don't see any point > > having 2 different monotonically increasing tokens/id. > > > > Mmm I was tempted about that, but the reason I did not was that in some > rare limit condition as you can see in the ASCII art (:O) I can find a hole in > the next available token ids so I have to skip and update last_token itself, > not sure if this could cause confusion seeing transfer_ids with holes during > tracing if I unify them. >
That should be fine as it won't be used at all.
-- Regards, Sudeep
| |