From: Theo Buehler <tb@theobuehler.org>
Subject: Re: bgpd: better path_calc_hash() function
To: tech@openbsd.org
Date: Thu, 7 May 2026 12:33:57 +0200

On Thu, May 07, 2026 at 11:37:04AM +0200, Claudio Jeker wrote:
> The current path_calc_hash() has at least two issues and this tries to fix
> them.
> 
> 1. The others attributes are not included into the hash, so paths with
> same main attributes but different additional attributes hash into the
> same value.
> 
> 2. The hash calculation covers bits it should not. Especially the
> inclusion of aspa_generation is worrisome since path_equal() explicitly
> excludes it.
> 
> Since siphash really prefers to operate on 64bit values reshuffle the hash
> calculation to follow this as much as possible.

ok tb

> -- 
> :wq Claudio
> 
> Index: rde.h
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde.h,v
> diff -u -p -r1.346 rde.h
> --- rde.h	30 Apr 2026 15:51:07 -0000	1.346
> +++ rde.h	6 May 2026 19:22:59 -0000
> @@ -227,18 +227,17 @@ struct rde_aspath {
>  	struct rde_aspa_state		 aspa_state;
>  	int				 refcnt;
>  	uint32_t			 flags;		/* internally used */
> +#define	path_starthash	 med
>  	uint32_t			 med;		/* multi exit disc */
>  	uint32_t			 lpref;		/* local pref */
>  	uint32_t			 weight;	/* low prio lpref */
>  	uint16_t			 rtlabelid;	/* route label id */
>  	uint16_t			 pftableid;	/* pf table id */
>  	uint8_t				 origin;
> +#define	path_endhash	 others_len
>  	uint8_t				 others_len;
>  	uint8_t				 aspa_generation;
>  };
> -#define PATH_HASHOFF		offsetof(struct rde_aspath, med)
> -#define PATH_HASHSTART(x)	((const uint8_t *)x + PATH_HASHOFF)
> -#define PATH_HASHSIZE		(sizeof(struct rde_aspath) - PATH_HASHOFF)
>  
>  enum nexthop_state {
>  	NEXTHOP_LOOKUP,
> Index: rde_rib.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/bgpd/rde_rib.c,v
> diff -u -p -r1.291 rde_rib.c
> --- rde_rib.c	5 May 2026 08:26:50 -0000	1.291
> +++ rde_rib.c	7 May 2026 09:35:43 -0000
> @@ -610,11 +610,17 @@ static uint64_t
>  path_calc_hash(const struct rde_aspath *p)
>  {
>  	SIPHASH_CTX ctx;
> +	unsigned int l;
>  
>  	SipHash24_Init(&ctx, &pathkey);
> -	SipHash24_Update(&ctx, PATH_HASHSTART(p), PATH_HASHSIZE);
> +	for (l = 0; l < p->others_len && p->others[l] != NULL; l++)
> +		SipHash24_Update(&ctx, &p->others[l]->hash,
> +		    sizeof(p->others[l]->hash));
>  	SipHash24_Update(&ctx, aspath_dump(p->aspath),
>  	    aspath_length(p->aspath));
> +	SipHash24_Update(&ctx, &p->path_starthash,
> +	    (const char *)&p->path_endhash - (const char *)&p->path_starthash);
> +	
>  	return SipHash24_End(&ctx);
>  }
>  
>