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 AC09645F93; Wed, 1 Jan 2025 10:37:49 +0100 (CET) Received: from mails.dpdk.org (localhost [127.0.0.1]) by mails.dpdk.org (Postfix) with ESMTP id AA67B4021E; Wed, 1 Jan 2025 10:37:47 +0100 (CET) Received: from mail-pl1-f178.google.com (mail-pl1-f178.google.com [209.85.214.178]) by mails.dpdk.org (Postfix) with ESMTP id 143BA40151 for ; Wed, 1 Jan 2025 10:37:46 +0100 (CET) Received: by mail-pl1-f178.google.com with SMTP id d9443c01a7336-21631789fcdso106155775ad.1 for ; Wed, 01 Jan 2025 01:37:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1735724265; x=1736329065; darn=dpdk.org; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:from:to:cc:subject:date:message-id:reply-to; bh=2zz6RwYXhMiFJMmNlHtqnYz2tQJUR3EH0frnEjjCzXQ=; b=RX7fj8Bm73QVWi1opMEn6omkcjNEjYsZ5WySPkcqfZlAGZyHvB+ID5Uud25el3aN5r yqdXq+O+Hq8MesDiX4EocaP7wf4vHUa5FEhsksqrNeNjTZKvLDnCzQ9SZUR0mAD+ruNF IGms2toJMS4HhFtMSimwDUo/eUKtHrbEvmT8bJ6Qk05sb7NJBRqvaWGaYRj17D8DDEeH PFKWtakUgBIrYdsR4P+7/TgVSM/giIGarPTwzKfZV6tRVMtzDKsdV1Yn4mfn1ehydls5 tK+7a/nE2Y0gf3B2HlxHVDoBFVjccXikVJvw9ZdftJXXZg7Ud4VAB4fVJPDKsDuBpRth 4aaw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1735724265; x=1736329065; h=content-transfer-encoding:mime-version:message-id:date:subject:cc :to:from:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=2zz6RwYXhMiFJMmNlHtqnYz2tQJUR3EH0frnEjjCzXQ=; b=IMUl6qJKY1pMyJyBy+mRgH5IrkFJ9BspzT5nbQnCYfzBEcnEFOD59KziJcOItKcHCm jRxPPsGwSnxF/qmTYoSajNh1JnkyeJ4ld6c5cY6DV8nJUFFdGfoOxA4ZASErbyA4e882 J2kzElWBvDR34epjZ4LmuDpusF3SM+IfuByKWIeK0IgagooMYsPEQmEvgGXO2Qj5eC/w Jf30KArrO7TKF+tIABBGxwpl4xcicOkdpTCDmSpg9LLxrwHDKuiwilDDKVaPr3twgwid Szj5WLfy/o8g8xtVUumVmpnvFrgn1hCFQrNd88FFucUVJWk7igNMztAZFF/WOxPHBLW4 8PeA== X-Gm-Message-State: AOJu0Yw0GJ8NUM0HoIRbWv58ldzuHno0vX7H2+FUoazOoF5XjMm9C8Lm /io1FOF2KPuaYgziQj6oGjelGVg4q3KNg8MYbirK0IU2siz17PS4 X-Gm-Gg: ASbGnctIE10BjsSDV3b/inc/9Nh03inhJd50Dz+K5AW4Xy+naMe/Ct3ABoxK9aLPmqT VvOGtOA45SwdaRRT4yUgziF6UAjFMc7k0pQA708WSG+tt6+IepIW/IHsP5nGqDRoly4WFcNrBrQ KmOWABKR2cJXAxAqOAR4pFHar7nsa3ond8rUV2GQLKBJ9gFN3nJIzis5bQeeEY+0VD9EbKH66Xh FXXypzUnkZxwF7wgECeGU1ndU2mUMlfJA5EdjdX1Yynz0yAS6sawHiMoSZuh1pNBRGggSr2vyli 55uztTmXCCt4d+ZkiG72pPYt9eg= X-Google-Smtp-Source: AGHT+IFm6dDFecyWcDTB0Jhq4WL2yxgP72UyVQBtj7mkLztjnFtiFJi9AV+K1IEKYegK91g9V6wPWA== X-Received: by 2002:a05:6a21:32a8:b0:1e0:d5be:bf75 with SMTP id adf61e73a8af0-1e5e1f56862mr46222400637.17.1735724264881; Wed, 01 Jan 2025 01:37:44 -0800 (PST) Received: from IDCREDBOX918.fareast.corp.microsoft.com ([167.220.238.66]) by smtp.gmail.com with ESMTPSA id d2e1a72fcca58-72aad8dbae4sm22149000b3a.96.2025.01.01.01.37.42 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Wed, 01 Jan 2025 01:37:44 -0800 (PST) From: Kumara Parameshwaran To: hujiayu.hu@foxmail.com Cc: dev@dpdk.org, Kumara Parameshwaran Subject: [PATCH] lib/gro: use hash function for flow lookup Date: Wed, 1 Jan 2025 15:07:35 +0530 Message-ID: <20250101093735.95271-1-kumaraparamesh92@gmail.com> X-Mailer: git-send-email 2.47.1 MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 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 optimize the GRO lookup using hash based implementation Signed-off-by: Kumara Parameshwaran --- The patch helps improving the CPU cycles during flow lookup in the GRO library. The current approach iterates over all the flows in the GRO table to find a matching flow for every incoming packet. The proposed patch uses Hash if the incoming packet contains the RTE_MBUF_F_RX_RSS_HASH field in the rte_mbuf, if not hash is computed based on the source and destination addresses and port. The current implementation is simple XOR. lib/gro/gro_tcp4.c | 131 ++++++++++++++++++++++++++------------------- lib/gro/gro_tcp4.h | 4 ++ 2 files changed, 79 insertions(+), 56 deletions(-) diff --git a/lib/gro/gro_tcp4.c b/lib/gro/gro_tcp4.c index 855cc7a71d..d2f0ecd931 100644 --- a/lib/gro/gro_tcp4.c +++ b/lib/gro/gro_tcp4.c @@ -57,6 +57,9 @@ gro_tcp4_tbl_create(uint16_t socket_id, tbl->flows[i].start_index = INVALID_ARRAY_INDEX; tbl->max_flow_num = entries_num; + for (i = 0; i < GRO_TCP4_HASH_BUCKET_SIZE; i++) + STAILQ_INIT(&tbl->collision_list[i]); + return tbl; } @@ -84,17 +87,18 @@ find_an_empty_flow(struct gro_tcp4_tbl *tbl) return INVALID_ARRAY_INDEX; } -static inline uint32_t +static inline int insert_new_flow(struct gro_tcp4_tbl *tbl, struct tcp4_flow_key *src, - uint32_t item_idx) + uint32_t item_idx, + uint32_t flow_hash) { struct tcp4_flow_key *dst; uint32_t flow_idx; flow_idx = find_an_empty_flow(tbl); if (unlikely(flow_idx == INVALID_ARRAY_INDEX)) - return INVALID_ARRAY_INDEX; + return -1; dst = &(tbl->flows[flow_idx].key); @@ -106,7 +110,28 @@ insert_new_flow(struct gro_tcp4_tbl *tbl, tbl->flows[flow_idx].start_index = item_idx; tbl->flow_num++; - return flow_idx; + if (STAILQ_EMPTY(&tbl->collision_list[flow_hash])) + STAILQ_INSERT_HEAD(&tbl->collision_list[flow_hash], + &(tbl->flows[flow_idx]), next); + else + STAILQ_INSERT_TAIL(&tbl->collision_list[flow_hash], + &(tbl->flows[flow_idx]), next); + return 0; +} + +static inline struct gro_tcp4_flow* +gro_tcp4_flow_search(struct gro_tcp4_tbl *tbl, + struct tcp4_flow_key *key, + uint32_t flow_hash) +{ + struct gro_tcp4_flow *flow; + + STAILQ_FOREACH(flow, &tbl->collision_list[flow_hash], next) { + if (memcmp(&(flow->key), key, sizeof(struct tcp4_flow_key)) == 0) + return flow; + } + + return NULL; } int32_t @@ -124,9 +149,8 @@ gro_tcp4_reassemble(struct rte_mbuf *pkt, struct tcp4_flow_key key; uint32_t item_idx; - uint32_t i, max_flow_num, remaining_flow_num; - uint8_t find; - uint32_t item_start_idx; + uint32_t flow_hash; + struct gro_tcp4_flow *flow; /* * Don't process the packet whose TCP header length is greater @@ -173,22 +197,15 @@ gro_tcp4_reassemble(struct rte_mbuf *pkt, is_atomic = (frag_off & RTE_IPV4_HDR_DF_FLAG) == RTE_IPV4_HDR_DF_FLAG; ip_id = is_atomic ? 0 : rte_be_to_cpu_16(ipv4_hdr->packet_id); - /* Search for a matched flow. */ - max_flow_num = tbl->max_flow_num; - remaining_flow_num = tbl->flow_num; - find = 0; - for (i = 0; i < max_flow_num && remaining_flow_num; i++) { - if (tbl->flows[i].start_index != INVALID_ARRAY_INDEX) { - if (is_same_tcp4_flow(tbl->flows[i].key, key)) { - find = 1; - item_start_idx = tbl->flows[i].start_index; - break; - } - remaining_flow_num--; - } + if (pkt->ol_flags & RTE_MBUF_F_RX_RSS_HASH) { + flow_hash = pkt->hash.rss % GRO_TCP4_HASH_BUCKET_SIZE; + } else { + flow_hash = ipv4_hdr->src_addr ^ ipv4_hdr->dst_addr ^ + tcp_hdr->src_port ^ tcp_hdr->dst_port; + flow_hash = flow_hash % GRO_TCP4_HASH_BUCKET_SIZE; } - - if (find == 1) { + flow = gro_tcp4_flow_search(tbl, &key, flow_hash); + if (flow != NULL) { /* * Any packet with additional flags like PSH,FIN should be processed * and flushed immediately. @@ -197,9 +214,9 @@ gro_tcp4_reassemble(struct rte_mbuf *pkt, */ if (tcp_hdr->tcp_flags & (RTE_TCP_ACK_FLAG | RTE_TCP_PSH_FLAG | RTE_TCP_FIN_FLAG)) { if (tcp_hdr->tcp_flags != RTE_TCP_ACK_FLAG) - tbl->items[item_start_idx].start_time = 0; + tbl->items[flow->start_index].start_time = 0; return process_tcp_item(pkt, tcp_hdr, tcp_dl, tbl->items, - tbl->flows[i].start_index, &tbl->item_num, + flow->start_index, &tbl->item_num, tbl->max_item_num, ip_id, is_atomic, start_time); } else { return -1; @@ -217,8 +234,7 @@ gro_tcp4_reassemble(struct rte_mbuf *pkt, is_atomic); if (item_idx == INVALID_ARRAY_INDEX) return -1; - if (insert_new_flow(tbl, &key, item_idx) == - INVALID_ARRAY_INDEX) { + if (insert_new_flow(tbl, &key, item_idx, flow_hash) != 0) { /* * Fail to insert a new flow, so delete the * stored packet. @@ -255,36 +271,39 @@ gro_tcp4_tbl_timeout_flush(struct gro_tcp4_tbl *tbl, { uint16_t k = 0; uint32_t i, j; - uint32_t max_flow_num = tbl->max_flow_num; - - for (i = 0; i < max_flow_num; i++) { - if (unlikely(tbl->flow_num == 0)) - return k; - - j = tbl->flows[i].start_index; - while (j != INVALID_ARRAY_INDEX) { - if (tbl->items[j].start_time <= flush_timestamp) { - out[k++] = tbl->items[j].firstseg; - if (tbl->items[j].nb_merged > 1) - update_header(&(tbl->items[j])); - /* - * Delete the packet and get the next - * packet in the flow. - */ - j = delete_tcp_item(tbl->items, j, - &tbl->item_num, INVALID_ARRAY_INDEX); - tbl->flows[i].start_index = j; - if (j == INVALID_ARRAY_INDEX) - tbl->flow_num--; - - if (unlikely(k == nb_out)) - return k; - } else - /* - * The left packets in this flow won't be - * timeout. Go to check other flows. - */ - break; + struct gro_tcp4_flow *flow; + + for (i = 0; i < GRO_TCP4_HASH_BUCKET_SIZE; i++) { + STAILQ_FOREACH(flow, &tbl->collision_list[i], next) { + j = flow->start_index; + while (j != INVALID_ARRAY_INDEX) { + if (tbl->items[j].start_time <= flush_timestamp) { + out[k++] = tbl->items[j].firstseg; + if (tbl->items[j].nb_merged > 1) + update_header(&(tbl->items[j])); + /* + * Delete the packet and get the next + * packet in the flow. + */ + j = delete_tcp_item(tbl->items, j, + &tbl->item_num, + INVALID_ARRAY_INDEX); + flow->start_index = j; + if (j == INVALID_ARRAY_INDEX) { + tbl->flow_num--; + STAILQ_REMOVE(&tbl->collision_list[i], + flow, gro_tcp4_flow, next); + } + + if (unlikely(k == nb_out)) + return k; + } else + /* + * The left packets in this flow won't be + * timeout. Go to check other flows. + */ + break; + } } } return k; diff --git a/lib/gro/gro_tcp4.h b/lib/gro/gro_tcp4.h index 245e5da486..077fe08e41 100644 --- a/lib/gro/gro_tcp4.h +++ b/lib/gro/gro_tcp4.h @@ -8,6 +8,7 @@ #include "gro_tcp.h" #define GRO_TCP4_TBL_MAX_ITEM_NUM (1024UL * 1024UL) +#define GRO_TCP4_HASH_BUCKET_SIZE 32 /* Header fields representing common fields in TCP flow */ struct tcp4_flow_key { @@ -23,6 +24,7 @@ struct gro_tcp4_flow { * INVALID_ARRAY_INDEX indicates an empty flow. */ uint32_t start_index; + STAILQ_ENTRY(gro_tcp4_flow) next; }; /* @@ -33,6 +35,8 @@ struct gro_tcp4_tbl { struct gro_tcp_item *items; /* flow array */ struct gro_tcp4_flow *flows; + /* Collision list for the flows following the same hash */ + STAILQ_HEAD(, gro_tcp4_flow) collision_list[GRO_TCP4_HASH_BUCKET_SIZE]; /* current item number */ uint32_t item_num; /* current flow num */ -- 2.45.1