Re: [PATCH v5 2/7] member: implement HT mode

["De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>]

Hi Yipeng,

> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Tuesday, October 3, 2017 5:32 AM
> To: dev@dpdk.org; De Lara Guarch, Pablo
> <pablo.de.lara.guarch@intel.com>
> Cc: thomas@monjalon.net; Tai, Charlie <charlie.tai@intel.com>; Gobriel,
> Sameh <sameh.gobriel@intel.com>; Mcnamara, John
> <john.mcnamara@intel.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>
> Subject: [PATCH v5 2/7] member: implement HT mode
> 
> One of the set-summary structures is hash-table based set-summary
> (HTSS). One example is cuckoo filter [1].
> 
> Comparing to a traditional hash table, HTSS has a much more compact
> structure. For each element, only one signature and its corresponding set ID
> is stored. No key comparison is required during lookup. For the table
> structure, there are multiple entries in each bucket, and the table is
> composed of many buckets.
> 
> Two modes are supported for HTSS, "cache" and "none-cache" modes.
> The non-cache mode is similar to the cuckoo filter [1].
> When a bucket is full, one entry will be evicted to its alternative bucket to
> make space for the new key. The table could be full and then no more keys
> could be inserted. This mode has false-positive rate but no false-negative.
> Multiple entries with same signature could stay in the same bucket.
> 
> The "cache" mode does not evict key to its alternative bucket when a
> bucket is full, an existing key will be evicted out of the table like a cache.
> Thus, the table will never reject keys when it is full. Another property is in
> each bucket, there cannot be multiple entries with same signature. The
> mode could have both false-positive and false-negative probability.
> 
> This patch adds the implementation of HTSS.
> 
> [1] B Fan, D G Andersen and M Kaminsky, “Cuckoo Filter: Practically Better
> Than Bloom,” in Conference on emerging Networking Experiments and
> Technologies, 2014.
> 
> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
...

Just a comment below. The rest looks fine to me (and thanks for the explanations
in the v4 patch, all clear), so keep my "Reviewed-by" in next version.

Reviewed-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>

> +++ b/lib/librte_member/rte_member_ht.c

...

> +/* Search bucket for entry with tmp_sig and update set_id */ static
> +inline int update_entry_search(uint32_t bucket_id, member_sig_t
> +tmp_sig,
> +		struct member_ht_bucket *buckets,
> +		member_set_t set_id)
> +{
> +	int32_t i;

"i" cannot take negative values, so use uint32_t
(same in "search_bucket_single" and "search_bucket_multi").

> +
> +	for (i = 0; i < RTE_MEMBER_BUCKET_ENTRIES; i++) {
> +		if (buckets[bucket_id].sigs[i] == tmp_sig) {
> +			buckets[bucket_id].sets[i] = set_id;
> +			return 1;
> +		}
> +	}
> +	return 0;
> +}
> +