From: "De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>
To: "Wang, Yipeng1" <yipeng1.wang@intel.com>, "dev@dpdk.org" <dev@dpdk.org>
Cc: "thomas@monjalon.net" <thomas@monjalon.net>,
"Tai, Charlie" <charlie.tai@intel.com>,
"Gobriel, Sameh" <sameh.gobriel@intel.com>,
"Mcnamara, John" <john.mcnamara@intel.com>
Subject: Re: [dpdk-dev] [PATCH v4 1/7] member: implement main API
Date: Mon, 2 Oct 2017 10:04:18 +0000 [thread overview]
Message-ID: <E115CCD9D858EF4F90C690B0DCB4D8976CC2890E@IRSMSX108.ger.corp.intel.com> (raw)
In-Reply-To: <1506534034-39433-2-git-send-email-yipeng1.wang@intel.com>
Hi Yipeng,
> -----Original Message-----
> From: Wang, Yipeng1
> Sent: Wednesday, September 27, 2017 6:40 PM
> To: dev@dpdk.org
> Cc: thomas@monjalon.net; Tai, Charlie <charlie.tai@intel.com>; Gobriel,
> Sameh <sameh.gobriel@intel.com>; De Lara Guarch, Pablo
> <pablo.de.lara.guarch@intel.com>; Mcnamara, John
> <john.mcnamara@intel.com>; Wang, Yipeng1 <yipeng1.wang@intel.com>
> Subject: [PATCH v4 1/7] member: implement main API
>
> Membership library is an extension and generalization of a traditional filter
> (for example Bloom Filter) structure. In general, the Membership library is a
> data structure that provides a "set-summary" and responds to set-
> membership queries of whether a certain element belongs to a set(s). A
> membership test for an element will return the set this element belongs to
> or not-found if the element is never inserted into the set-summary.
>
> The results of the membership test are not 100% accurate. Certain false
> positive or false negative probability could exist. However, comparing to a
> "full-blown" complete list of elements, a "set-summary"
> is memory efficient and fast on lookup.
>
> This patch adds the main API definition.
>
> Signed-off-by: Yipeng Wang <yipeng1.wang@intel.com>
A few comments on changes that you didn't make in the v4.
Thanks,
Pablo
...
> +
> +struct rte_member_setsum *
> +rte_member_create(const struct rte_member_parameters *params) {
> + struct rte_tailq_entry *te;
> + struct rte_member_list *member_list;
> + struct rte_member_setsum *setsum;
> + int ret;
> +
> + if (params == NULL) {
> + rte_errno = EINVAL;
> + return NULL;
> + }
> +
> + if (params->key_len == 0 ||
> + params->prim_hash_seed == params-
> >sec_hash_seed) {
> + rte_errno = EINVAL;
> + RTE_MEMBER_LOG(ERR, "Memship create with invalid
> parameters\n");
Do not use "Memship". Change to " rte_member_create has invalid parameters"?
Or something else that you want, but not Memship.
> + return NULL;
> + }
> +
...
> +struct rte_member_parameters {
> + const char *name; /**< Name of the hash. */
> +
> + /**
> + * User to specify the type of the setsummary from one of
> + * rte_member_setsum_type.
> + *
> + * HT based setsummary is implemented like a hash table. User
> should use
> + * this type when there are many sets.
> + *
> + * vBF setsummary is a vector of bloom filters. It is used when
> number
> + * of sets is not big (less than 32 for current implementation).
> + */
> + enum rte_member_setsum_type type;
> +
> + /**
> + * If it is HT based setsummary, user to specify the subtype or mode
> + * of the setsummary. It could be cache, or non-cache mode.
> + * Set iscache to be 1 if to use as cache mode.
Change to "is_cache".
> + *
> + * For cache mode, keys can be evicted out of the HT setsummary.
> Keys
> + * with the same signature and map to the same bucket
> + * will overwrite each other in the setsummary table.
> + * This mode is useful for the case that the set-summary only
> + * needs to keep record of the recently inserted keys. Both
> + * false-negative and false-positive could happen.
> + *
> + * For non-cache mode, keys cannot be evicted out of the cache. So
> for
> + * this mode the setsummary will become full eventually. Keys with
> the
> + * same signature but map to the same bucket will still occupy
> multiple
> + * entries. This mode does not give false-negative result.
> + */
> + uint8_t is_cache;
> +
> + /**
> + * For HT setsummary, num_keys equals to the number of entries
> of the
> + * table. When the number of keys that inserted in the HT
> setsummary
"number of keys inserted in the HT summary". Or "were inserted".
> + * approaches this number, eviction could happen. For cache mode,
> + * keys could be evicted out of the table. For non-cache mode, keys
> will
...
> + /**
> + * false_positive_rate is only relevant to vBF based setsummary.
> + * false_positive_rate is the user-defined false positive rate
> + * given expected number of inserted keys (num_keys). It is used to
> + * calculate the total number of bits for each BF, and the number of
> + * hash values used during lookup and insertion. For details please
> + * refer to vBF implementation and membership library
> documentation.
> + * Note that this parameter is not directly set by users for HT mode.
> + *
> + * HT setsummary's false positive rate is in the order of:
> + * false_pos = (1/bucket_count)*(1/2^16), since we use 16-bit
> signature.
> + * This is because two keys needs to map to same bucket and same
> + * signature to have a collision (false positive). bucket_count is
> equal
> + * to number of entries (num_keys) divided by entry count per
> bucket
> + * (RTE_MEMBER_BUCKET_ENTRIES). Thus, the false_positive_rate
> is not
> + * directly set by users.
Unless I understood it incorrectly, I think you should clarify that
this field is not set for HT mode, but it is for vBF, right?
> + */
> + float false_positive_rate;
> +
> + /**
> + * We use two seeds to calculate two independent hashes for each
> key.
> + *
> + * For HT type, one hash is used as signature, and the other is used
> + * for bucket location.
> + * For vBF type, these two hashes and their combinations are used
> as
> + * hash locations to index the bit array.
> + */
> + uint32_t prim_hash_seed;
> +
> + /**
> + * The secondary seed should be a different value from the primary
> seed.
> + */
> + uint32_t sec_hash_seed;
> +
> + int socket_id; /**< NUMA Socket ID for memory.
> */
> +};
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Find an existing set-summary and return a pointer to it.
> + *
> + * @param name
> + * Name of the set-summary.
> + * @return
> + * Pointer to the set-summary or NULL if object not found
> + * with rte_errno set appropriately. Possible rte_errno values include:
> + * - ENOENT - value not available for return
> + */
> +struct rte_member_setsum *
> +rte_member_find_existing(const char *name);
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Create set-summary (SS).
> + *
> + * @param params
> + * Parameters to initialize the setsummary.
> + * @return
> + * Return the pointer to the setsummary.
> + * Return value is NULL if the creation failed.
> + */
> +struct rte_member_setsum *
> +rte_member_create(const struct rte_member_parameters *params);
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * Lookup key in set-summary (SS).
> + * Single key lookup and return as soon as the first match found
> + *
> + * @param setsum
> + * Pointer of a setsummary.
> + * @param key
> + * Pointer of the key to be looked up.
> + * @param set_id
> + * Output the set id matches the key.
> + * @return
> + * Return 1 for found a match and 0 for not found a match.
> + */
> +int
> +rte_member_lookup(const struct rte_member_setsum *setsum, const
> void *key,
> + member_set_t *set_id);
> +
> +/**
> + * @warning
> + * @b EXPERIMENTAL: this API may change without prior notice
> + *
> + * lookup bulk of keys in set-summary (SS).
"Lookup bulk"
> + * Each key lookup returns as soon as the first match found
> + *
> + * @param setsum
> + * Pointer of a setsummary.
> + * @param keys
> + * Pointer of the bulk of keys to be looked up.
> + * @param num_keys
> + * Number of keys that will be lookup.
> + * @param set_ids
> + * Output set ids for all the keys to this array.
> + * User should preallocate array that can contain all results, which size is
> + * the num_keys.
> + * @return
next prev parent reply other threads:[~2017-10-02 10:04 UTC|newest]
Thread overview: 81+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-08-22 0:19 [dpdk-dev] [PATCH 0/7] Add Membership Library Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 1/7] member: implement main API Yipeng Wang
2017-08-22 3:59 ` Stephen Hemminger
2017-08-22 10:02 ` Luca Boccassi
2017-08-24 9:35 ` Ferruh Yigit
2017-08-24 9:55 ` Luca Boccassi
2017-08-24 10:32 ` Ferruh Yigit
2017-09-02 12:55 ` Luca Boccassi
2017-09-02 23:49 ` Luca Boccassi
2017-08-24 18:38 ` Wang, Yipeng1
2017-09-02 12:54 ` Luca Boccassi
2017-08-22 0:19 ` [dpdk-dev] [PATCH 2/7] member: implement HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 3/7] member: implement vBF mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 4/7] member: add AVX for HT mode Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 5/7] member: enable the library Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 6/7] test/member: add functional and perf tests Yipeng Wang
2017-08-22 0:19 ` [dpdk-dev] [PATCH 7/7] doc: add membership documentation Yipeng Wang
2017-08-22 4:01 ` [dpdk-dev] [PATCH 0/7] Add Membership Library Stephen Hemminger
2017-08-23 2:58 ` Wang, Yipeng1
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 " Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 1/7] member: implement main API Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 2/7] member: implement HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 3/7] member: implement vBF mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 5/7] member: enable the library Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-02 1:24 ` [dpdk-dev] [PATCH v2 7/7] doc: add membership documentation Yipeng Wang
2017-09-04 13:19 ` Mcnamara, John
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 0/7] Add Membership Library Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 1/7] member: implement main API Yipeng Wang
2017-09-22 10:47 ` Thomas Monjalon
2017-09-25 14:15 ` De Lara Guarch, Pablo
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 2/7] member: implement HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 3/7] member: implement vBF mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 5/7] member: enable the library Yipeng Wang
2017-09-22 10:48 ` Thomas Monjalon
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 6/7] test/member: add functional and perf tests Yipeng Wang
2017-09-05 23:59 ` [dpdk-dev] [PATCH v3 7/7] doc: add membership documentation Yipeng Wang
2017-09-18 18:42 ` Mcnamara, John
2017-09-25 12:30 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 0/7] Add Membership Library Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 1/7] member: implement main API Yipeng Wang
2017-10-02 10:04 ` De Lara Guarch, Pablo [this message]
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 2/7] member: implement HT mode Yipeng Wang
2017-10-02 13:30 ` De Lara Guarch, Pablo
2017-10-03 1:18 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 3/7] member: implement vBF mode Yipeng Wang
2017-10-02 15:44 ` De Lara Guarch, Pablo
2017-10-03 1:24 ` Wang, Yipeng1
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 4/7] member: add AVX for HT mode Yipeng Wang
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 5/7] member: enable the library Yipeng Wang
2017-10-02 15:47 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-02 16:20 ` De Lara Guarch, Pablo
2017-09-27 17:40 ` [dpdk-dev] [PATCH v4 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 0/7] Add Membership Library Yipeng Wang
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 1/7] member: implement main API Yipeng Wang
2017-10-03 8:42 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 2/7] member: implement HT mode Yipeng Wang
2017-10-03 8:47 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 3/7] member: implement vBF mode Yipeng Wang
2017-10-03 8:50 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-03 9:01 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 5/7] member: enable the library Yipeng Wang
2017-10-03 9:04 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-03 9:07 ` De Lara Guarch, Pablo
2017-10-03 4:31 ` [dpdk-dev] [PATCH v5 7/7] doc: add membership documentation Yipeng Wang
2017-10-03 9:08 ` De Lara Guarch, Pablo
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 1/7] member: implement main API Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 2/7] member: implement HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 3/7] member: implement vBF mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 4/7] member: add AVX for HT mode Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 5/7] member: enable the library Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 6/7] test/member: add functional and perf tests Yipeng Wang
2017-10-04 3:12 ` [dpdk-dev] [PATCH v6 7/7] doc: add membership documentation Yipeng Wang
2017-10-04 13:44 ` Mcnamara, John
2017-10-08 22:14 ` [dpdk-dev] [PATCH v6 0/7] Add Membership Library Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=E115CCD9D858EF4F90C690B0DCB4D8976CC2890E@IRSMSX108.ger.corp.intel.com \
--to=pablo.de.lara.guarch@intel.com \
--cc=charlie.tai@intel.com \
--cc=dev@dpdk.org \
--cc=john.mcnamara@intel.com \
--cc=sameh.gobriel@intel.com \
--cc=thomas@monjalon.net \
--cc=yipeng1.wang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).