Re: [B.A.T.M.A.N.] [PATCHv2 5/5] batman-adv: Allow to use different sized hash locks array

[Antonio Quartulli <ordex@autistici.org>]

[-- Attachment #1: Type: text/plain, Size: 3003 bytes --]

On Sat, Dec 01, 2012 at 05:58:22PM +0100, Sven Eckelmann wrote:
> On Saturday 01 December 2012 17:40:45 Antonio Quartulli wrote:
> > On Mon, Nov 26, 2012 at 12:58:32PM +0100, Sven Eckelmann wrote:
> > > The amount of locks of a hash directly affects the parallelity when all
> > > access independent parts of the hash. But this also affects the amount of
> > > memory used for each hash. Allowing to decouple the hash size and the
> > > lock size allows to reduce this memory consumption for hashes which don't
> > > allow this parallelism.
> > > 
> > > Signed-off-by: Sven Eckelmann <sven@narfation.org>
> > > ---
> > > 
> > >  bridge_loop_avoidance.c |   28 ++++++++++++++--------------
> > >  distributed-arp-table.c |   16 ++++++++--------
> > >  distributed-arp-table.h |    6 +++---
> > >  hash.h                  |   19 +++++++++----------
> > >  originator.c            |    6 ++++--
> > >  originator.h            |   13 +++++--------
> > >  translation-table.c     |   22 ++++++++++++++--------
> > >  vis.c                   |    8 ++++----
> > >  8 files changed, 61 insertions(+), 57 deletions(-)
> > > 
> > > diff --git a/bridge_loop_avoidance.c b/bridge_loop_avoidance.c
> > > index 1a78bac..781119f 100644
> > > --- a/bridge_loop_avoidance.c
> > > +++ b/bridge_loop_avoidance.c
> > > @@ -38,7 +38,7 @@ static void batadv_bla_send_announce(struct batadv_priv
> > > *bat_priv,> 
> > >  				     struct batadv_backbone_gw *backbone_gw);
> > >  
> > >  /* return the index of the claim */
> > > 
> > > -static inline uint32_t batadv_choose_claim(const void *data, uint32_t
> > > size) +static inline uint32_t batadv_choose_claim(const void *data)
> > > 
> > >  {
> > >  
> > >  	struct batadv_claim *claim = (struct batadv_claim *)data;
> > >  	uint32_t hash;
> > > 
> > > @@ -46,12 +46,11 @@ static inline uint32_t batadv_choose_claim(const void
> > > *data, uint32_t size)> 
> > >  	hash = jhash(&claim->addr, sizeof(claim->addr), 0);
> > >  	hash = jhash(&claim->vid, sizeof(claim->vid), hash);
> > > 
> > > -	return hash % size;
> > > +	return hash;
> > 
> > I do not fully understand how having the mod operation inside the function
> > would prevent the decoupling. Why you need to move it out?
> 
> Because following calculations can create different results:
> 
> * (i % hashsize) % locksize
> * (i % locksize)
> 
> Example:
> * (21 % 4) % 3 == 1
> * 21 % 3 == 0
> 
> And of course, we could use only the first calculation. But then we would end 
> up in having more hash buckets mapped in the first part of the locks when 
> hashsize > locksize.

Yeah this is what I had in mind, but I didn't think to the distribution effect.
Well, even doing your way I think the distribution is not uniform at all. But
the effect is minimized with respect of the first case.

I think it is worth leaving it as you posted.

Cheers,



-- 
Antonio Quartulli

..each of us alone is worth nothing..
Ernesto "Che" Guevara

[-- Attachment #2: Type: application/pgp-signature, Size: 836 bytes --]