Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Tue, 1 Feb 2022 13:43:17 -0800
From:   Martin KaFai Lau <kafai@fb.com>
To:     Maciej =?utf-8?Q?=C5=BBenczykowski?= <zenczykowski@gmail.com>
CC:     Maciej =?utf-8?Q?=C5=BBenczykowski?= <maze@google.com>,
        Brian Vazquez <brianvv@google.com>, Yonghong Song <yhs@fb.com>,
        Alexei Starovoitov <ast@kernel.org>,
        Daniel Borkmann <daniel@iogearbox.net>,
        Linux Network Development Mailing List 
        <netdev@vger.kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>,
        BPF Mailing List <bpf@vger.kernel.org>,
        "David S . Miller" <davem@davemloft.net>
Subject: Re: [PATCH bpf-next] RFC: bpf hashmap - improve iteration in the
 presence of concurrent delete operations
Message-ID: <20220201214317.fbqhpgewlhqvegob@kafai-mbp.dhcp.thefacebook.com>
References: <20220201183514.3235495-1-zenczykowski@gmail.com>
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <20220201183514.3235495-1-zenczykowski@gmail.com>
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?UURmUXhJZUFUUGZtL09MeTRlMXdVUWtiNnVzZ3c2WHNldkN3RTFocjd0R3Fr?=
 =?utf-8?B?SmQzaUtGcmJZMEFSdFZ4TEE3VmpzUG9mT2NGMDFtWXhQNUs4ZWZFNEJ0cVp0?=
 =?utf-8?B?aHlhaVYwS1pKYUZuTXlBazRZNFVtYy9ZSnYzRjY1MUtIVmJYVS9XNHVScm9t?=
 =?utf-8?B?a0xLc0pkVVpuTTdiNEQzcE1zbFBYcjNFQkpXS2oxK1F1c3dIQVFJUnFuK1FK?=
 =?utf-8?B?L293YnBhSThnYzBkeXVBNUhlQ3E0bm5DWVpsZnUzcjFXRHNjdCtvTjhnd25P?=
 =?utf-8?B?RThabk43UnlNUVpDUGhRellTU09KeW5GM2dWNnA0eEdOcXRZUHlHUDFjQU1J?=
 =?utf-8?B?bWs4eGVRR1h1L2ozUmdDZXJvRk5QQkZudURyRkMxMENyVFZVSHl1a0s0RUFD?=
 =?utf-8?B?QUdiMm5VODN6MDdiN25jd2Qwc3pZTHRZKzZIRWYyUmZyamdrd2VBUyttSjFz?=
 =?utf-8?B?VXNialBYT3FwdVlWMWdOK2dOdHVKMk1TeW9FbFY4bExDTG5lelhmTUVHTitN?=
 =?utf-8?B?cko1WndmRHo1dnpQTmJQREl6VmgxaWQvZXZ6dDE1djZEWi9mSmtRaTlRc1U3?=
 =?utf-8?B?dzY5UGc0RGVYNXhyUmNRU05lb1kramtTRkxSVStmYmFJNnBzRitWTkRsd2dY?=
 =?utf-8?B?WUJTckI4QlBTdWtQQ0lMOGU5SUVWQWhEYnlQQm1LSXZlL2s3Z2h6NUR3SGNu?=
 =?utf-8?B?cTNmVE1BNlZIa3pBT3c1K3lJVEd5cVlnbVFQYWFKSzJWZkxBRjRrKzd5c243?=
 =?utf-8?B?VnVyaTBHTkdCYXloSkVFWTR5WEo1T0FTWXVpVkVMc0QweCtmUkk3b2Rod1lz?=
 =?utf-8?B?ZzB3eHBsWlJFSlE4RFJ1Mmgrem1EaWVVMEZYbTZWSGl6Y1RYSGhnZEtHdnBL?=
 =?utf-8?B?VSs2aHRKOVRvQTZ1SDkvTEJoVC8yZXdDN1cvZU4zaGV6T241VUMyZWlGWWlj?=
 =?utf-8?B?NUNDVE1sQVliNFNwZlFtVWVGSHNnZzhvWDVsOXNYdkRZUDJhcHhJV1VGeXVp?=
 =?utf-8?B?eUxoeDl0RXhVNWZaby8vR3gwaUVubXFiYjZMTjdnQ1FTZmxqT3dScms2d3pI?=
 =?utf-8?B?aDBmQjVuR0VpVk11VWE1YnBMYWdRRWl2RGdKQkxJVkl0WE1DNDF0b0hzUHBG?=
 =?utf-8?B?UDdYaUZXN3B4dG13RnJjNENVN01qSDJYNUdKYWVNeGEzZ2VVYjZBcldqK1dh?=
 =?utf-8?B?eUFLc1hqUWJOTHpJR3M2c25iZFJSQlZWRHZOSFE5VVQwSDBKbnh6QzU2L0Jt?=
 =?utf-8?B?aUI1MFhnc1NDcm90M2FiZlFTcm9qazhtaVRVbzNObE9ud0w3K0xkZnY0Zk1k?=
 =?utf-8?B?MGNDdTMvWVkxZXJzc0lwUHEvYlUzYkNmVHB5U3JJVW81cGFnWjYyWUZiMlZ6?=
 =?utf-8?B?VCswNWFBQ1JOV1d0T0NGRUpBUUlSSWEyWFBSY2dpcWxjblRsZVYyTm5JeUI0?=
 =?utf-8?B?MXpXMFJJdER3c25nM3pNODFaaFkyeUtLa1B1b1hjbEpIZU9BejYxOGEwc2Rr?=
 =?utf-8?B?cGQ2bW5NY3pURllMc1BWOXlJbFQrNWxQcFBBckk4enFwS0FzdE1aTE1CazF0?=
 =?utf-8?B?WEtFcXJOeEFKUUhlRXRKeGdMVExKbWF6TzFEbzAwUlA2TjFtYzVZWkpoU2Qr?=
 =?utf-8?B?SnREN3o3WXpsalkwS0VLR3dweXUwMWFnUUQ4dnI4dUx5emtyWXY0L05Fci9D?=
 =?utf-8?B?d2pDMHlQc2ozV0lHRFRwWjVobXRkSDlQeW9tNWFYTE9xM0lHSkVrOG5TK3B2?=
 =?utf-8?B?NjcvSDljaTA4UHRiMHZtOFlPOW1JbzJtYkF4eElLLzJqM3RnbG5aY05ZclVl?=
 =?utf-8?B?QlJUVEVRck5YQkNCSGRvZ21Md0czLy82YTNEZDYxMWRvd2gyQVBZTXpEdUhm?=
 =?utf-8?B?K3RWcEthTXVRa3c4d3p4Ulllb1hVU3ZmTUsxRUoxMVkzWndSemxScHd1WnpC?=
 =?utf-8?B?N0ZNaEhSSldxUEVKeDhTaUxvdWJ2dDNDSkdzQTAwVzlkVVVpaGZnVksyUjBR?=
 =?utf-8?B?S2VCWjRzYTlHanBuR1RYL3YxU2dReklJSGEwZ1RRQ0JRMFRHRnh3NFRmNzVa?=
 =?utf-8?B?S3NLV0FpSTRCbHViUXRhcnc5RklEaHkrYlU5cmdiL1dBR2xTTnlmRUtLSGJD?=
 =?utf-8?Q?rpOkEU5Ti5VblCwdHBcWieurR?=
X-MS-Exchange-CrossTenant-Network-Message-Id: ce5c82b2-516b-4318-1b08-08d9e5cbdda3
X-MS-Exchange-CrossTenant-AuthSource: SA1PR15MB5016.namprd15.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Feb 2022 21:43:21.2023
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: PY9hPQImGlPHRnKCgglIgrK0SSE4XId1T8hWR7bPG9T8PBLyyrRa2MHf/MMuxOJX
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SJ0PR15MB4392
X-OriginatorOrg: fb.com
X-Proofpoint-GUID: _Yx5TP5UxOqHzHfv-XVFDxhAtkd8zmQE
X-Proofpoint-ORIG-GUID: _Yx5TP5UxOqHzHfv-XVFDxhAtkd8zmQE
Content-Transfer-Encoding: 8bit
X-Proofpoint-UnRewURL: 0 URL was un-rewritten
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=baseguard
 engine=ICAP:2.0.205,Aquarius:18.0.816,Hydra:6.0.425,FMLib:17.11.62.513
 definitions=2022-02-01_10,2022-02-01_01,2021-12-02_01
X-Proofpoint-Spam-Details: rule=fb_outbound_notspam policy=fb_outbound score=1 malwarescore=0
 phishscore=0 impostorscore=0 bulkscore=0 mlxlogscore=194 suspectscore=0
 priorityscore=1501 spamscore=1 adultscore=0 lowpriorityscore=0
 clxscore=1011 mlxscore=1 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2201110000 definitions=main-2202010119
X-FB-Internal: deliver
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Tue, Feb 01, 2022 at 10:35:14AM -0800, Maciej Żenczykowski wrote:
> From: Maciej Żenczykowski <maze@google.com>
> 
> by resuming from the bucket the key would be in if it still existed
> 
> Note: AFAICT this an API change that would require some sort of guard...
> 
> bpf map iteration was added all the way back in v3.18-rc4-939-g0f8e4bd8a1fc
> but behaviour of find first key with NULL was only done in v4.11-rc7-2042-g8fe45924387b
> (before that you'd get EFAULT)
> 
> this means previously find first key was done by calling with a non existing key
> (AFAICT this was hoping to get lucky, since if your non existing key actually existed,
> it wouldn't actually iterate right, since you couldn't guarantee your magic value was
> the first one)
> 
> ie. do we need a BPF_MAP_GET_NEXT_KEY2 or a sysctl? some other approach?
BPF_MAP_LOOKUP_BATCH has already been added to lookup in batches of buckets,
so the next bpf_map_lookup_batch will start from the beginning of
the next bucket.  Here is the details:

https://lore.kernel.org/bpf/20200115184308.162644-6-brianvv@google.com/#t