From patchwork Tue Feb 4 08:28:46 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 13958777 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f175.google.com (mail-pl1-f175.google.com [209.85.214.175]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C345C2063CB; Tue, 4 Feb 2025 08:29:30 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.175 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657772; cv=none; b=nC1KmD70LYKVmqTw0oTXymayS8zIM4FAxpXeLDA3njWB1A8x8uHjwy7J1Ex8mxrdL6LTIMHVoCfS+gCbY1Nn4vGSS3xkU3PNymDbhKd8r/uErKg8yVzmplvzhTR59N/JY67Qh8JyYOZzx804hMS8EvyrY1dDF2gpVpNy2pg9SOI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657772; c=relaxed/simple; bh=cygbPsqm/+24ILyOqw6LUbAFmrpTSCgSL3gnpRYWYrM=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=kkx4vx7dlWw0mzJ9yOL80RRzYZDBYa6g5O/9Kwi6/o+yNUWvWxTirs7U0NHTM3TBvgs3BBotFEG2qM/jC3DQJko35sH/a48YuErF8aGVFwLKsRtgmqcg32LGiIBD7unvnksuWTYv557OI0t5RihGxSqor3QLnbervTwYUl96vWs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=kAoki27X; arc=none smtp.client-ip=209.85.214.175 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="kAoki27X" Received: by mail-pl1-f175.google.com with SMTP id d9443c01a7336-21ddab8800bso74098185ad.3; Tue, 04 Feb 2025 00:29:30 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1738657769; x=1739262569; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=vp62zAozdKsPL83mVTCVtEOMmQRcolpr5FVRl0Ln8/A=; b=kAoki27XrR9KFbjFNijUR3KaCPdWHbyzY9rs5joP0mzNeSeg4pbpP4XoL14FqGkATH 3iwCnbwh0Gcdi1GJsP6/dOWcefRmOi0bm1kI90MqeluOA5RZlePpfyU/dlWuXwsEa1qQ 4HVu6RpxO5gjB2lzpNKmVu+nR2lVdN20BjKdH+M1XvXcSR0imOuxHbtM47n5RVS3jQOT dkl/9YlhSjjM/lDehrf83wwqe4rJJUA4mMyzDVRo/FXMCjon7SNnZbSE1c2Zxk6DrGrl sl/UtZ5ECap3WTFThpwbx6NCEk5v2HY04Z5QoxpOmowgQOwfK9RfE1ALCz4NmIItDKOw ZVfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738657769; x=1739262569; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=vp62zAozdKsPL83mVTCVtEOMmQRcolpr5FVRl0Ln8/A=; b=SsmaGEHNCv30hBodv1iQKEIePeEH8lPy7qMKAwPP3eluMb6dACa5gQiz2szB5qPAJp P5XIhlEDpglEfIICeHzkS/yoOfIV2ZEyXFOOMl4TfQezJeJOLQ+dBUXqnFTovYg2TMBv mn2xxd4gQ7NlI+ieZLeCfobA8x6hxjyibKbQGkeFhn9G9LhCDffppQkCWAWwK07++iOX gIztZ2eKQi866+KodfzXoyjzwPdHOO9s0yZu0g+jNZ7pZuFAdghJfmCaBBIDqjoViJfe BLtFHdL1CbID/QtI93hqwmySeuewDyWgmvDjtMH7MA+Xyd6peVj47piOPgWr92Nb31U8 3G+g== X-Forwarded-Encrypted: i=1; AJvYcCU0lph55m8Om6hgogbOa0toAZyd6wHiPzhWpGAZ7mwrgEE7P0EHz/mIhKo+88tJpSgVTIM=@vger.kernel.org X-Gm-Message-State: AOJu0Yymj0T35iykmwIkktW6hA7N7mp5yvX+o0y2/xUcQLz/DD25fklh I8oWjEMCqixt96l5BCma8z7BpYXMC3ZZ6G/M6tNgGksqYAIjvb+wO5YcGp3DsxWs4Q== X-Gm-Gg: ASbGncvZHq2ateZH/36RQ6nNiUayzPTY4ZkMbdrRmG9pl/wM5xPXCt7Wn9ovx9Gac5C D2Eqr4SUx8nzc4HfcSNpxxQTNhchnOngjLLo+pWODAB0NCH+9aagqAAIU/lKACZEmtaCu6vFAR3 80RWKS81+v8A1mOHTQNSc6snUPvJAZlqxIrI07zzpZIjOkxqTsLxkYzxtusv69vJhRikyirS+E1 wWEJeQIRCAcldXoDnAXS2BOQvYjiwcNuDxzlisar4JAkjYGr36tZCOlRdtQZMWShPRmWT4JMKDj vCVxHmTaRr8o X-Google-Smtp-Source: AGHT+IFmcHRb38f9k/NtDEih1WWJkP1kNCt1xQdNvL6Sg8Gu8H/L9jP+++r5jcRFk0LIKTXLXYGKvA== X-Received: by 2002:a17:902:e552:b0:216:2bd7:1c2e with SMTP id d9443c01a7336-21dd7c664damr323784375ad.18.1738657769577; Tue, 04 Feb 2025 00:29:29 -0800 (PST) Received: from fedora.. ([183.156.115.252]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-21de32ea80csm90826685ad.140.2025.02.04.00.29.23 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Feb 2025 00:29:29 -0800 (PST) From: Hou Tao To: bpf@vger.kernel.org, rcu@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , Yonghong Song , John Fastabend , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , "Paul E . McKenney" , houtao1@huawei.com, hotforest@gmail.com Subject: [PATCH bpf-next 1/3] rculist: add hlist_nulls_replace_rcu() helper Date: Tue, 4 Feb 2025 16:28:46 +0800 Message-ID: <20250204082848.13471-2-hotforest@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250204082848.13471-1-hotforest@gmail.com> References: <20250204082848.13471-1-hotforest@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Add hlist_nulls_replace_rcu() to replace an existing element in the hash list. For the concurrent list traversal, the replace is atomic, it will find either the old element or the new element. Signed-off-by: Hou Tao --- include/linux/rculist_nulls.h | 42 +++++++++++++++++++++++++++++++++++ 1 file changed, 42 insertions(+) diff --git a/include/linux/rculist_nulls.h b/include/linux/rculist_nulls.h index 89186c499dd4..795071fda6ad 100644 --- a/include/linux/rculist_nulls.h +++ b/include/linux/rculist_nulls.h @@ -52,6 +52,14 @@ static inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n) #define hlist_nulls_next_rcu(node) \ (*((struct hlist_nulls_node __rcu __force **)&(node)->next)) + +/** + * hlist_nulls_pprev_rcu - returns the element of the list before @node. + * @node: element of the list. + */ +#define hlist_nulls_pprev_rcu(node) \ + (*((struct hlist_nulls_node __rcu __force **)(node)->pprev)) + /** * hlist_nulls_del_rcu - deletes entry from hash list without re-initialization * @n: the element to delete from the hash list. @@ -145,6 +153,40 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, } } +/** + * hlist_nulls_replace_rcu - replace an element in hash list + * @n: new element to add + * @o: old element to replace + * + * Description: + * Replace an existing element in a hash list with a new one, + * while permitting racing traversals. + * + * The caller must take whatever precautions are necessary + * (such as holding appropriate locks) to avoid racing + * with another list-mutation primitive, such as hlist_nulls_add_head_rcu() + * or hlist_nulls_del_rcu(), running on this same list. + * However, it is perfectly legal to run concurrently with + * the _rcu list-traversal primitives, such as + * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency + * problems on Alpha CPUs. Regardless of the type of CPU, the + * list-traversal primitive must be guarded by rcu_read_lock(). + */ +static inline void hlist_nulls_replace_rcu(struct hlist_nulls_node *n, + struct hlist_nulls_node *o) +{ + struct hlist_nulls_node *next = o->next; + struct hlist_nulls_node **pprev = o->pprev; + + WRITE_ONCE(n->next, next); + WRITE_ONCE(n->pprev, pprev); + rcu_assign_pointer(hlist_nulls_pprev_rcu(o), n); + + if (!is_a_nulls(next)) + WRITE_ONCE(next->pprev, &n->next); + WRITE_ONCE(o->pprev, LIST_POISON2); +} + /* after that hlist_nulls_del will work */ static inline void hlist_nulls_add_fake(struct hlist_nulls_node *n) { From patchwork Tue Feb 4 08:28:47 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 13958778 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pl1-f176.google.com (mail-pl1-f176.google.com [209.85.214.176]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 20125206F15; Tue, 4 Feb 2025 08:29:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.176 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657780; cv=none; b=BWZJMWZd1y35nu9Ubwpd6kYDlBhzODKMlgcINxOQcHatVi0F+OFXASKioSpYuE70AO4gDAzlVLo+wVTq0dGGGV/XQRt4tjnrIuER8T4DK4vhZW01EHRrsPnb+cDFKv2wI8KayFKf2pOP+AuGxjK/xNwUnIs89aTQ/F1CcNz7UxM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657780; c=relaxed/simple; bh=jXxRWf1PvMNCt9hiDjml0Obuom1TPrr9kqKoAouMtjI=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=tbfbdTi+qrf18NyhmKdNi4ozm2W1kj9vTUgn4fsO5pFRuAmomglJw9HZ2Rs15AWRzUd6KF3nHBPlA/1MZz+ZQXZJaV3E8+VvlJgvW5FWk8wV2KIXRD4iq2ZH28GFZoFmd4oSt+dbJYInyXM1dqCca2yks91iQv7jp0EWsBF2mLA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=C/8vuvAl; arc=none smtp.client-ip=209.85.214.176 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="C/8vuvAl" Received: by mail-pl1-f176.google.com with SMTP id d9443c01a7336-2163dc5155fso93179475ad.0; Tue, 04 Feb 2025 00:29:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1738657778; x=1739262578; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=Al2UwxdPrWH7ftc+zw3s2BSjj6h4sMz+uJ0myT5iwZ0=; b=C/8vuvAlZjGzH+pQQ7q4k9e+1JRUA0rU5D5x24nuCLYDn1UBXih/ywwL1bR6lmbCIk s8PBopV6Gp7O7S+C3jTooJ4SAFM8gnqdJnYIb/lnKSymMGn1NCc3pTWIbZ90+D8cesEK B4bChnj4AN3M0VnHJ5fzpEIsvmF4X9FI6Pmv+vm1uTP0G1WMopxGJNywM1+48yjUaYyr qySpb3bBOwPHM4Q1q/oEZvEBmXc90EroAuC2tweZqZw9DETrbZ51olOCFcbyGr+ClIKu sjcKYfMZnq6iNp8xhM/J8exIwtTbDEMaEZCw+WnFgdp33LFRjK1VlVilA4EZ8X2iIPmW sEbA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738657778; x=1739262578; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=Al2UwxdPrWH7ftc+zw3s2BSjj6h4sMz+uJ0myT5iwZ0=; b=O0KHWqc6wKGF282U+zDTo1s/GMW1aAOYwXPaSfZT8bCFRgop9BHU/vk6YWklExZC1p akwT36LCupyAALiWz94QyDkDc+xO9G92xPtxpQB1nJ9yWT9JE0ua2kEvdAoVOLsgcNhM XRKsTghmQLtfdCanaGTRbWLP1+H7KxFH2XXzJ1vX/WvrLcwAyr4zDPwJZTRMAVh1Qo4E ME1YthAcz6tAVlGgOKUcErAfmNnb0ffoOdn60SN4wsK6XcEfxASP5yJxVatjc8a4+d8E N2uBxywGgUv8VyOlteEoBgfurblA7boBxLlROMc9PLUeM9KXnF4jtlqj678OA7moqtip HCfA== X-Forwarded-Encrypted: i=1; AJvYcCUlMuTMpT7XSuOJI/6J+cMgrPX32qbuV0BBUOw0Rs3WJyJ0cQEqYQsMBvViQzS/rZ2Ehqk=@vger.kernel.org X-Gm-Message-State: AOJu0YyQpJtTPG2ySufiLaxQtDXH5/VFFHTm8DUnCbUd4swJAEJ8Ztqx 3409h1R+XPjHFh+VpbcacrJG8hufTTllTs1ueC+jEOALHf1fZZCOOgWg0sY0HjPSOw== X-Gm-Gg: ASbGncsfWzkM0aj0P8YQ7GZdyBZSJ2YH1hTnPZ5+ozPWqmUjeh/cyY4uLYgfCeibaH2 JJU9NAgasumwZsbBD0uV/I8z/90Alvd3NSxVOONey1Ga82I9kkVuQR7NvlrVDd0ApnQyyhJiJfN a4urVlQ+IcAqVO8IIp+nYxtlMuj0Kbgc/DgRF/qrDvqSS25bI3s/OMA4ULmZxaNxJPVsr1yq+eZ 60ucrK7j1wYEcdfMYFJQw8Dw1JuEnW4wYenVxojOCAwXNKw/B+7CgabsAqUSbMVnLhXj9Zt7ZkM F65DhjaX2bk3 X-Google-Smtp-Source: AGHT+IG9qpgFmb2lq3UNf7NazYCkUucb+7qrWn+jhvOdGlArOEToLfvGl3I8pTQ7gUmZymF33lhJBw== X-Received: by 2002:a17:902:d549:b0:215:8847:435c with SMTP id d9443c01a7336-21dd7c55d18mr408480055ad.12.1738657776369; Tue, 04 Feb 2025 00:29:36 -0800 (PST) Received: from fedora.. ([183.156.115.252]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-21de32ea80csm90826685ad.140.2025.02.04.00.29.31 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Feb 2025 00:29:35 -0800 (PST) From: Hou Tao To: bpf@vger.kernel.org, rcu@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , Yonghong Song , John Fastabend , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , "Paul E . McKenney" , houtao1@huawei.com, hotforest@gmail.com Subject: [PATCH bpf-next 2/3] bpf: Overwrite the element in hash map atomically Date: Tue, 4 Feb 2025 16:28:47 +0800 Message-ID: <20250204082848.13471-3-hotforest@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250204082848.13471-1-hotforest@gmail.com> References: <20250204082848.13471-1-hotforest@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Currently, the update of existing element in hash map involves two steps: 1) insert the new element at the head of the hash list 2) remove the old element It is possible that the concurrent lookup operation may fail to find either the old element or the new element if the lookup operation starts before the addition and continues after the removal. Therefore, replacing the two-step update with an atomic update. After the change, the update will be atomic in the perspective of the lookup operation: it will either find the old element or the new element. Signed-off-by: Hou Tao --- kernel/bpf/hashtab.c | 14 ++++++++------ 1 file changed, 8 insertions(+), 6 deletions(-) diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c index 4a9eeb7aef85..a28b11ce74c6 100644 --- a/kernel/bpf/hashtab.c +++ b/kernel/bpf/hashtab.c @@ -1179,12 +1179,14 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value, goto err; } - /* add new element to the head of the list, so that - * concurrent search will find it before old elem - */ - hlist_nulls_add_head_rcu(&l_new->hash_node, head); - if (l_old) { - hlist_nulls_del_rcu(&l_old->hash_node); + if (!l_old) { + hlist_nulls_add_head_rcu(&l_new->hash_node, head); + } else { + /* Replace the old element atomically, so that + * concurrent search will find either the new element or + * the old element. + */ + hlist_nulls_replace_rcu(&l_new->hash_node, &l_old->hash_node); /* l_old has already been stashed in htab->extra_elems, free * its special fields before it is available for reuse. Also From patchwork Tue Feb 4 08:28:48 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Hou Tao X-Patchwork-Id: 13958779 X-Patchwork-Delegate: bpf@iogearbox.net Received: from mail-pj1-f48.google.com (mail-pj1-f48.google.com [209.85.216.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 261AD206F15; Tue, 4 Feb 2025 08:29:43 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.216.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657785; cv=none; b=G0GULsXbDzpICEgTMTrKIq1JBCBq11d5dtHjk42e7wULzgB16sIgQ2DwnG0QjEUg2rGw3qf+TzSCKMYWPsTFiEf3KrJWTl6kkOqGzJ2SDO5CWlI1gn7IWs7Z3MRt3wzPZW5ELoOMVhL1ckIrCC3u9wn5GXnqJk6iJxPRe1iXAcM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1738657785; c=relaxed/simple; bh=grBlq7AtrDzJznDIIMWKhUXEENML1Ru70TG8QouqedA=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=mqNvAMFWmVXikmc0icMKywCXCOjMTk4YFWbRQ9zq9lhqhA/EjQnQB1/9lpbUahUXS3a7yhNGExFSMrJVD3Vv/Oijfa4KEMdmb7MBP/64V7gs+NmP0b50oWDqaT5u9UfKU7gOrB/UUgcrMO6amaPVShHspfn79EA1NJDInqJxzts= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=DiT9NoRt; arc=none smtp.client-ip=209.85.216.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="DiT9NoRt" Received: by mail-pj1-f48.google.com with SMTP id 98e67ed59e1d1-2efe25558ddso6702491a91.2; Tue, 04 Feb 2025 00:29:43 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1738657783; x=1739262583; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=8/rXpZZJDHG/iORGqfX0hjTAkoUOQszW7vZ0F9giU4M=; b=DiT9NoRt60TNAAmfpjYk7s21YIoCogrBQ4/J2Ng9vZwpX6t91FlQoOOBnY0KvYziDj dBjfxwhtb5BGs6O5eOo7Ve8yyZwd2FiDfmQPKlbIbtgjFvqlgbGN3JPRW8hCdIlLTDL+ inIJDQ86j/Huz5GQkeoQDAwcpHsBgGE8wiZNNwp/noD/ePbL5TQ79MKswqeclWtkOezu Dl07t1bSLPutkxxVcEXeBcpAfU8s7I2bd7gUN/cGnQ5wVXLgYSsooL5JvIWMl7Jn6Mtw nCxftWaepUEDMbaLHmGXUJr7eFkxV8ExgJ+IrEFp/XSJU6c6MjYhaj6Z1aq+LIg1CSw2 Lo5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1738657783; x=1739262583; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8/rXpZZJDHG/iORGqfX0hjTAkoUOQszW7vZ0F9giU4M=; b=f19XxGdU8skAqO0cV15nZzIsQY4nX8VQrxO21e7gVQFFNxbySB4GL5ANoARX6JWl4q UDfNhsTErPjoV622JMYVP+zafeaFGn4aOc1mFPPuxlvwChV8JvTHpN1hwvFFAAc5cmS+ ovC3TneS5SzAsBoX27UXDo9vrIIEKBxRixBSqN/VPCTuJ265wQ+JU6uE0oW2vp774oWq lIgKtAS/XHnUsjtzX7YvtFRzkccNnCxtEf5anrQBtNUVpEwUam6y8y9qfEbJsUMR6e9Z FCXtSi04BWFdxFyF/uUJKLz0t2FfsCVqhD9uLRB5pNuqjudvhjUfIXZcFdnjQPYUFFvl UY1g== X-Forwarded-Encrypted: i=1; AJvYcCXo61JcqT0pQV+/U3amwC8k+GodQ8ZxvZ9iwZnMeLX4zCxctUhkpF9bT7CaQEr+M43DL/E=@vger.kernel.org X-Gm-Message-State: AOJu0YyEX6ZAVIYrlMZGxLciR8/ltMkOHyPymNhZUibh1tL+cI4jlNc7 L9L/WCyIr1mL7nKwynrhuwf0IL3lzLkYA0U7XWRrn6Jbe/RjdpOMBpVtX26JLXvfIw== X-Gm-Gg: ASbGncuPL3O9AnFoqjImfhik8BhmvsUtKS4CtUReTX9iLUPzEUj5zajwM2kD/MFKmlQ ca8vPJr/mC2l2eiesfxoU2X78Olj6XMFTQfWATVZULY8jbKeGXKITyu9pu3hhS4/USTuXFMqCNr 1ob3nuhrfXxiVNdgBfxZ2wKpsWgrBZ3z4C94BicxkRuBuBsOqE9sySUqZI+UybB8M+iWlsi2lxb 9bQ/b9grDmUWYyBkney/bFXUuCBsek4+uVNVw5uZA5DQfDzec6lRfgjRJJwU3m9yZw3VGkp6Htk NiiiSxErnCSs X-Google-Smtp-Source: AGHT+IE7qoevV/2Nueo/bysoZM0pFqAonau//1OeJSs0qmWUP13x2qewRIwThpkyE4IkwtRkidfEYw== X-Received: by 2002:a17:90b:2585:b0:2f2:ab09:c256 with SMTP id 98e67ed59e1d1-2f83ac8bb24mr40935768a91.33.1738657782854; Tue, 04 Feb 2025 00:29:42 -0800 (PST) Received: from fedora.. ([183.156.115.252]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-21de32ea80csm90826685ad.140.2025.02.04.00.29.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Tue, 04 Feb 2025 00:29:42 -0800 (PST) From: Hou Tao To: bpf@vger.kernel.org, rcu@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Alexei Starovoitov , Daniel Borkmann , Andrii Nakryiko , Martin KaFai Lau , Eduard Zingerman , Song Liu , Yonghong Song , John Fastabend , KP Singh , Stanislav Fomichev , Hao Luo , Jiri Olsa , "Paul E . McKenney" , houtao1@huawei.com, hotforest@gmail.com Subject: [PATCH bpf-next 3/3] selftests/bpf: Add test case for atomic htab update Date: Tue, 4 Feb 2025 16:28:48 +0800 Message-ID: <20250204082848.13471-4-hotforest@gmail.com> X-Mailer: git-send-email 2.48.1 In-Reply-To: <20250204082848.13471-1-hotforest@gmail.com> References: <20250204082848.13471-1-hotforest@gmail.com> Precedence: bulk X-Mailing-List: bpf@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Patchwork-Delegate: bpf@iogearbox.net Add a test case to verify the atomic update of existing element in hash map. The test proceeds in three steps: 1) fill the map with keys in the range [0, 63] 2) create 8 threads to lookup these keys concurrently 3) create 2 threads to overwrite these keys concurrently Without atomic update support, the lookup operation may return -ENOENT error and the test will fail. After the atomic-update change, the lookup operation will always return 0 and the test will succeed. Signed-off-by: Hou Tao --- .../selftests/bpf/prog_tests/htab_lookup.c | 130 ++++++++++++++++++ .../testing/selftests/bpf/progs/htab_lookup.c | 13 ++ 2 files changed, 143 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/htab_lookup.c create mode 100644 tools/testing/selftests/bpf/progs/htab_lookup.c diff --git a/tools/testing/selftests/bpf/prog_tests/htab_lookup.c b/tools/testing/selftests/bpf/prog_tests/htab_lookup.c new file mode 100644 index 000000000000..ef9036827439 --- /dev/null +++ b/tools/testing/selftests/bpf/prog_tests/htab_lookup.c @@ -0,0 +1,130 @@ +// SPDX-License-Identifier: GPL-2.0 +#define _GNU_SOURCE +#include +#include +#include "htab_lookup.skel.h" + +struct htab_op_ctx { + int fd; + int loop; + unsigned int entries; + bool stop; +}; + +static void *htab_lookup_fn(void *arg) +{ + struct htab_op_ctx *ctx = arg; + int i = 0; + + while (i++ < ctx->loop && !ctx->stop) { + unsigned int j; + + for (j = 0; j < ctx->entries; j++) { + unsigned long key = j, value; + int err; + + err = bpf_map_lookup_elem(ctx->fd, &key, &value); + if (err) { + ctx->stop = true; + return (void *)(long)err; + } + } + } + + return NULL; +} + +static void *htab_update_fn(void *arg) +{ + struct htab_op_ctx *ctx = arg; + int i = 0; + + while (i++ < ctx->loop && !ctx->stop) { + unsigned int j; + + for (j = 0; j < ctx->entries; j++) { + unsigned long key = j, value = j; + int err; + + err = bpf_map_update_elem(ctx->fd, &key, &value, BPF_EXIST); + if (err) { + if (err == -ENOMEM) + continue; + ctx->stop = true; + return (void *)(long)err; + } + } + } + + return NULL; +} + +static int setup_htab(int fd, unsigned int entries) +{ + unsigned int i; + + for (i = 0; i < entries; i++) { + unsigned long key = i, value = i; + int err; + + err = bpf_map_update_elem(fd, &key, &value, 0); + if (!ASSERT_OK(err, "init update")) + return -1; + } + + return 0; +} + +void test_htab_lookup(void) +{ + unsigned int i, wr_nr = 2, rd_nr = 8; + pthread_t tids[wr_nr + rd_nr]; + struct htab_lookup *skel; + struct htab_op_ctx ctx; + int err; + + skel = htab_lookup__open_and_load(); + if (!ASSERT_OK_PTR(skel, "htab_lookup__open_and_load")) + return; + + ctx.fd = bpf_map__fd(skel->maps.htab); + ctx.loop = 50; + ctx.stop = false; + ctx.entries = 64; + + err = setup_htab(ctx.fd, ctx.entries); + if (err) + goto destroy; + + memset(tids, 0, sizeof(tids)); + for (i = 0; i < wr_nr; i++) { + err = pthread_create(&tids[i], NULL, htab_update_fn, &ctx); + if (!ASSERT_OK(err, "pthread_create")) { + ctx.stop = true; + goto reap; + } + } + for (i = 0; i < rd_nr; i++) { + err = pthread_create(&tids[i + wr_nr], NULL, htab_lookup_fn, &ctx); + if (!ASSERT_OK(err, "pthread_create")) { + ctx.stop = true; + goto reap; + } + } + +reap: + for (i = 0; i < wr_nr + rd_nr; i++) { + void *ret = NULL; + char desc[32]; + + if (!tids[i]) + continue; + + snprintf(desc, sizeof(desc), "thread %u", i + 1); + err = pthread_join(tids[i], &ret); + ASSERT_OK(err, desc); + ASSERT_EQ(ret, NULL, desc); + } +destroy: + htab_lookup__destroy(skel); +} diff --git a/tools/testing/selftests/bpf/progs/htab_lookup.c b/tools/testing/selftests/bpf/progs/htab_lookup.c new file mode 100644 index 000000000000..baa30fa5b84f --- /dev/null +++ b/tools/testing/selftests/bpf/progs/htab_lookup.c @@ -0,0 +1,13 @@ +// SPDX-License-Identifier: GPL-2.0 +#include +#include + +char _license[] SEC("license") = "GPL"; + +struct { + __uint(type, BPF_MAP_TYPE_HASH); + __uint(max_entries, 64); + __type(key, unsigned long); + __type(value, unsigned long); + __uint(map_flags, BPF_F_NO_PREALLOC); +} htab SEC(".maps");