From patchwork Fri Oct 27 02:45:21 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: bugzilla@dpdk.org X-Patchwork-Id: 133442 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from mails.dpdk.org (mails.dpdk.org [217.70.189.124]) by inbox.dpdk.org (Postfix) with ESMTP id 3BF1F4320F; Fri, 27 Oct 2023 04:45:22 +0200 (CEST) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id 0CE7E4025E; Fri, 27 Oct 2023 04:45:22 +0200 (CEST) Received: from inbox.dpdk.org (inbox.dpdk.org [95.142.172.178]) by mails.dpdk.org (Postfix) with ESMTP id 94F764003C for ; Fri, 27 Oct 2023 04:45:21 +0200 (CEST) Received: by inbox.dpdk.org (Postfix, from userid 33) id 8358A43210; Fri, 27 Oct 2023 04:45:21 +0200 (CEST) From: bugzilla@dpdk.org To: dev@dpdk.org Subject: [Bug 1306] hash: internal hash key pointer overflow Date: Fri, 27 Oct 2023 02:45:21 +0000 X-Bugzilla-Reason: AssignedTo X-Bugzilla-Type: new X-Bugzilla-Watch-Reason: None X-Bugzilla-Product: DPDK X-Bugzilla-Component: other X-Bugzilla-Version: 23.11 X-Bugzilla-Keywords: X-Bugzilla-Severity: normal X-Bugzilla-Who: sz.kim@navercorp.com X-Bugzilla-Status: UNCONFIRMED X-Bugzilla-Resolution: X-Bugzilla-Priority: Normal X-Bugzilla-Assigned-To: dev@dpdk.org X-Bugzilla-Target-Milestone: --- X-Bugzilla-Flags: X-Bugzilla-Changed-Fields: bug_id short_desc product version rep_platform op_sys bug_status bug_severity priority component assigned_to reporter target_milestone Message-ID: X-Bugzilla-URL: http://bugs.dpdk.org/ Auto-Submitted: auto-generated X-Auto-Response-Suppress: All MIME-Version: 1.0 X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org https://bugs.dpdk.org/show_bug.cgi?id=1306 Bug ID: 1306 Summary: hash: internal hash key pointer overflow Product: DPDK Version: 23.11 Hardware: All OS: All Status: UNCONFIRMED Severity: normal Priority: Normal Component: other Assignee: dev@dpdk.org Reporter: sz.kim@navercorp.com Target Milestone: --- Hello, I discovered that an overflow occurred in an internal variable used in the hash library. If the value of [slot_id * h->key_entry_size] is more than 32 bits, the pointer of [new_k] will be entered with the wrong value. Therefore, type casting to uint64_t is required for the calculation result. - free_slots = 1 to total entries - slot_id = total entries or less - key_entry_size = sizeof(rte_hash_key) + sizeof(user key) The above three variables are the internal values of the DPDK HASH. The free_slots is a ring structure, filled with 1 to total entries. The values of free_slots is used by slot_id. And the key_entry_size becomes the size of the key value set by the user. The following example shows a situation where the issue occurs. Example) - global variable : entries = 2^28 key_entry_size = 32 - no issue case : 2^26(slot_id) * 32(key_entry_size) = 0x80000000 (32bit) - issue case : 2^27(slot_id) * 32(key_entry_size) = 0x100000000 (33bit) 2^28(slot_id) * 32(key_entry_size) = 0x200000000 (34bit) I think it should be changed as follows diff code. Is that correct? Signed-off-by: SeongJoong Kim --- lib/hash/rte_cuckoo_hash.c | 38 +++++++++++++++++++------------------- 1 file changed, 19 insertions(+), 19 deletions(-) * should not leak after the store to pdata @@ -1071,7 +1071,7 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, return -ENOSPC; } - new_k = RTE_PTR_ADD(keys, slot_id * h->key_entry_size); + new_k = RTE_PTR_ADD(keys, (uint64_t) slot_id * h->key_entry_size); /* The store to application data (by the application) at *data should * not leak after the store of pdata in the key store. i.e. pdata is * the guard variable. Release the application data to the readers. @@ -1256,7 +1256,7 @@ search_one_bucket_l(const struct rte_hash *h, const void *key, if (bkt->sig_current[i] == sig && bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + (uint64_t) bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { if (data != NULL) @@ -1294,7 +1294,7 @@ search_one_bucket_lf(const struct rte_hash *h, const void *key, uint16_t sig, __ATOMIC_ACQUIRE); if (key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { if (data != NULL) { @@ -1492,7 +1492,7 @@ __hash_rcu_qsbr_free_resource(void *p, void *e, unsigned int n) keys = h->key_store; k = (struct rte_hash_key *) ((char *)keys + - rcu_dq_entry.key_idx * h->key_entry_size); + (uint64_t) rcu_dq_entry.key_idx * h->key_entry_size); key_data = k->pdata; if (h->hash_rcu_cfg->free_key_data_func) h->hash_rcu_cfg->free_key_data_func(h->hash_rcu_cfg->key_data_ptr, @@ -1654,7 +1654,7 @@ search_and_remove(const struct rte_hash *h, const void *key, __ATOMIC_ACQUIRE); if (bkt->sig_current[i] == sig && key_idx != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { bkt->sig_current[i] = NULL_SIGNATURE; /* Free the key store index if @@ -1806,8 +1806,8 @@ rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position, RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL); struct rte_hash_key *k, *keys = h->key_store; - k = (struct rte_hash_key *) ((char *) keys + (position + 1) * - h->key_entry_size); + k = (struct rte_hash_key *) ((char *) keys + + (uint64_t) (position + 1) * h->key_entry_size); *key = k->key; if (position != @@ -1934,7 +1934,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); rte_prefetch0(key_slot); continue; } @@ -1948,7 +1948,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); rte_prefetch0(key_slot); } } @@ -1965,7 +1965,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); /* * If key index is 0, do not compare key, @@ -1993,7 +1993,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); /* * If key index is 0, do not compare key, @@ -2091,7 +2091,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); rte_prefetch0(key_slot); continue; } @@ -2105,7 +2105,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); rte_prefetch0(key_slot); } } @@ -2123,7 +2123,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); /* * If key index is 0, do not compare key, @@ -2155,7 +2155,7 @@ __bulk_lookup_lf(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot = (const struct rte_hash_key *)( (const char *)h->key_store + - key_idx * h->key_entry_size); + (uint64_t) key_idx * h->key_entry_size); /* * If key index is 0, do not compare key, @@ -2506,7 +2506,7 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 __hash_rw_reader_lock(h); next_key = (struct rte_hash_key *) ((char *)h->key_store + - position * h->key_entry_size); + (uint64_t) position * h->key_entry_size); /* Return key and data */ *key = next_key->key; *data = next_key->pdata; @@ -2537,7 +2537,7 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32 } __hash_rw_reader_lock(h); next_key = (struct rte_hash_key *) ((char *)h->key_store + - position * h->key_entry_size); + (uint64_t) position * h->key_entry_size); /* Return key and data */ *key = next_key->key; *data = next_key->pdata; -- 2.31.1 diff --git a/lib/hash/rte_cuckoo_hash.c b/lib/hash/rte_cuckoo_hash.c index d92a903bb3..10ffa500d2 100644 --- a/lib/hash/rte_cuckoo_hash.c +++ b/lib/hash/rte_cuckoo_hash.c @@ -636,7 +636,7 @@ rte_hash_reset(struct rte_hash *h) } memset(h->buckets, 0, h->num_buckets * sizeof(struct rte_hash_bucket)); - memset(h->key_store, 0, h->key_entry_size * (h->entries + 1)); + memset(h->key_store, 0, (uint64_t) h->key_entry_size * (h->entries + 1)); *h->tbl_chng_cnt = 0; /* reset the free ring */ @@ -705,7 +705,7 @@ search_and_update(const struct rte_hash *h, void *data, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->sig_current[i] == sig) { k = (struct rte_hash_key *) ((char *)keys + - bkt->key_idx[i] * h->key_entry_size); + (uint64_t) bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { /* The store to application data at *data