From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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: Content-Type: multipart/alternative; boundary=16983747210.4EC6.441228 Content-Transfer-Encoding: 7bit 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 --16983747210.4EC6.441228 Date: Fri, 27 Oct 2023 04:45:21 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://bugs.dpdk.org/ Auto-Submitted: auto-generated X-Auto-Response-Suppress: All https://bugs.dpdk.org/show_bug.cgi?id=3D1306 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 =3D 1 to total entries - slot_id =3D total entries or less - key_entry_size =3D 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 =3D 2^28 key_entry_size =3D 32 - no issue case : 2^26(slot_id) * 32(key_entry_size) =3D 0x80000000 (32bit) - issue case : 2^27(slot_id) * 32(key_entry_size) =3D 0x100000000 (33bit) 2^28(slot_id) * 32(key_entry_size) =3D 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(-) 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 =3D 0; /* reset the free ring */ @@ -705,7 +705,7 @@ search_and_update(const struct rte_hash *h, void *data, const void *key, for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { if (bkt->sig_current[i] =3D=3D sig) { k =3D (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) =3D=3D 0) { /* The store to application data at *data * 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 =3D RTE_PTR_ADD(keys, slot_id * h->key_entry_size); + new_k =3D 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 v= oid *key, if (bkt->sig_current[i] =3D=3D sig && bkt->key_idx[i] !=3D EMPTY_SLOT) { k =3D (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) =3D=3D 0) { if (data !=3D 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 !=3D EMPTY_SLOT) { k =3D (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) =3D=3D 0) { if (data !=3D NULL) { @@ -1492,7 +1492,7 @@ __hash_rcu_qsbr_free_resource(void *p, void *e, unsig= ned int n) keys =3D h->key_store; k =3D (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 =3D 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] =3D=3D sig && key_idx !=3D EMPTY_SLOT) { k =3D (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) =3D=3D 0) { bkt->sig_current[i] =3D 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 =3D=3D NULL) || (key =3D=3D NULL)), -EINVAL); struct rte_hash_key *k, *keys =3D h->key_store; - k =3D (struct rte_hash_key *) ((char *) keys + (position + 1) * - h->key_entry_size); + k =3D (struct rte_hash_key *) ((char *) keys + + (uint64_t) (position + 1) * h->key_entry_size); *key =3D k->key; if (position !=3D @@ -1934,7 +1934,7 @@ __bulk_lookup_l(const struct rte_hash *h, const void **keys, const struct rte_hash_key *key_slot =3D (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 =3D (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 =3D (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 =3D (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 =3D (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 =3D (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 =3D (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 =3D (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 =3D (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 =3D next_key->key; *data =3D 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 =3D (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 =3D next_key->key; *data =3D next_key->pdata; -- 2.31.1 --=20 You are receiving this mail because: You are the assignee for the bug.= --16983747210.4EC6.441228 Date: Fri, 27 Oct 2023 04:45:21 +0200 MIME-Version: 1.0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Bugzilla-URL: http://bugs.dpdk.org/ Auto-Submitted: auto-generated X-Auto-Response-Suppress: All
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 =3D 1 to total entries
- slot_id =3D total entries or less
- key_entry_size =3D 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 =3D 2^28
   key_entry_size =3D 32

- no issue case :
   2^26(slot_id) * 32(key_entry_size) =3D 0x80000000  (32bit)

- issue case :
   2^27(slot_id) * 32(key_entry_size) =3D 0x100000000 (33bit)
   2^28(slot_id) * 32(key_entry_size) =3D 0x200000000 (34bit)


I think it should be changed as follows diff code. Is that correct?


Signed-off-by: SeongJoong Kim <sz.kim@navercorp.com>
---
lib/hash/rte_cuckoo_hash.c | 38 +++++++++++++++++++-------------------
1 file changed, 19 insertions(+), 19 deletions(-)

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_buc=
ket));
-    memset(h->key_store, 0, h->key_entry_size * (h->entries + 1));
+    memset(h->key_store, 0, (uint64_t) h->key_entry_size * (h->en=
tries + 1));
    *h->tbl_chng_cnt =3D 0;

    /* reset the free ring */
@@ -705,7 +705,7 @@ search_and_update(const struct rte_hash=
 *h, void *data,
const void *key,
    for (i =3D 0; i < RTE_HASH_BUCKET_ENTRIES; i++) {
        if (bkt->sig_current[i] =3D=3D sig) {
            k =3D (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) =3D=3D 0) {
                /* The store to application data at *data
                 * should not leak after the store to pdata
@@ -1071,7 +1071,7 @@ __rte_hash_add_key_with_hash(const st=
ruct rte_hash *h,
const void *key,
            return -ENOSPC;
    }

-    new_k =3D RTE_PTR_ADD(keys, slot_id * h->key_entry_size);
+    new_k =3D 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] =3D=3D sig &&
                bkt->key_idx[i] !=3D EMPTY_SLOT) {
            k =3D (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) =3D=3D 0) {
                if (data !=3D 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 !=3D EMPTY_SLOT) {
                k =3D (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) =3D=3D 0) {
                    if (data !=3D NULL) {
@@ -1492,7 +1492,7 @@ __hash_rcu_qsbr_free_resource(void *p=
, void *e, unsigned
int n)
    keys =3D h->key_store;

    k =3D (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 =3D k->pdata;
    if (h->hash_rcu_cfg->free_key_data_func)
        h->hash_rcu_cfg->free_key_data_func(h->hash_rcu_cfg->ke=
y_data_ptr,
@@ -1654,7 +1654,7 @@ search_and_remove(const struct rte_ha=
sh *h, const void
*key,
                      __ATOMIC_ACQUIRE);
        if (bkt->sig_current[i] =3D=3D sig && key_idx !=3D EMPTY=
_SLOT) {
            k =3D (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) =3D=3D 0) {
                bkt->sig_current[i] =3D 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 =3D=3D NULL) || (key =3D=3D NULL)), -EINVAL);

    struct rte_hash_key *k, *keys =3D h->key_store;
-    k =3D (struct rte_hash_key *) ((char *) keys + (position + 1) *
-                     h->key_entry_size);
+    k =3D (struct rte_hash_key *) ((char *) keys +
+                     (uint64_t) (position + 1) * h->key_entry_size);
    *key =3D k->key;

    if (position !=3D
@@ -1934,7 +1934,7 @@ __bulk_lookup_l(const struct rte_hash=
 *h, const void
**keys,
            const struct rte_hash_key *key_slot =3D
                (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 =3D
                (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 =3D
                (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 =3D
                (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_has=
h *h, const void
**keys,
                const struct rte_hash_key *key_slot =3D
                    (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_has=
h *h, const void
**keys,
                const struct rte_hash_key *key_slot =3D
                    (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_has=
h *h, const void
**keys,
                const struct rte_hash_key *key_slot =3D
                    (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_has=
h *h, const void
**keys,
                const struct rte_hash_key *key_slot =3D
                    (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_has=
h *h, const void
**key, void **data, uint32

    __hash_rw_reader_lock(h);
    next_key =3D (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 =3D next_key->key;
    *data =3D next_key->pdata;
@@ -2537,7 +2537,7 @@ rte_hash_iterate(const struct rte_has=
h *h, const void
**key, void **data, uint32
    }
    __hash_rw_reader_lock(h);
    next_key =3D (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 =3D next_key->key;
    *data =3D next_key->pdata;
--
2.31.1

You are receiving this mail because:
  • You are the assignee for the bug.
=20=20=20=20=20=20=20=20=20=20
= --16983747210.4EC6.441228--