From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-8.6 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI, SPF_PASS,USER_IN_DEF_DKIM_WL autolearn=unavailable autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 4AA40C43381 for ; Mon, 1 Apr 2019 21:38:17 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 1544C2146E for ; Mon, 1 Apr 2019 21:38:17 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="GuoOo1Jt" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726843AbfDAViM (ORCPT ); Mon, 1 Apr 2019 17:38:12 -0400 Received: from mail-yb1-f195.google.com ([209.85.219.195]:43920 "EHLO mail-yb1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726399AbfDAViL (ORCPT ); Mon, 1 Apr 2019 17:38:11 -0400 Received: by mail-yb1-f195.google.com with SMTP id a123so2380702ybg.10 for ; Mon, 01 Apr 2019 14:38:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=FHNIq0DAsiO68PBdakjAEu2fVLC527LLikbsrJoLlzw=; b=GuoOo1Jtsv8fOQjSU/DMg/+OeDJo25ir04J2M6CQzfya8Aft4/BhJ+g3al2eV213gt B1hP9eiO/rrCOQB08YjA8O59LoU7MJxAYJpd411bxNKw4fNfTL+yrgJemihGxl/rofQz sXXi6YrU2wDiR/0gV5iNzKECTfbRY4wYhzbvMikja8QmcBpjKVlcTxSG4ofOS/SqnVDG jQZJhWFS5Q8twQTipMBVzM7JErAXf35f5ORR60XFumwAZkRDfS9rInxT8VpG3lUtGb9V PqqDjtqvgnFgFXTSyDGT5yPjDqgZtWc2R6GIAyd2QKM2tIWakZ/x+VIuU1APvk2WngMu uvaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=FHNIq0DAsiO68PBdakjAEu2fVLC527LLikbsrJoLlzw=; b=iDl2jedb0lcwMYQ0PZCOzyf+msnQM3znXRQppFT0CoPVTz+6s6Qu1bL6MHhmOGZLd+ 2THqU/j2DS41QKdaHfw+u/3auXxEod8OsuuxEJWAZL6A/EtOwnsVeA7f3mzhDnbKt+vB 8bAIxlJ7VqVlEy6zKQ4SWtDFDDnNpgjA8WS3d28vB0NZ4dDyxRIaijLKlnkyJO6D1nAz Bb8uRs8XjO/0JUMb1/XweQOT+fQBMe+q8P9GaOfxAcYLDfHdbAwRhJrx/m3xgxOaZlQJ fTe4/luJ4iM9h4sSGrNJFFlQq65b/ZAVugwsNcSuSS/v+891RBmrt1O6D8sTglvyNsiO Vb3g== X-Gm-Message-State: APjAAAWToFQdMqt8pwuk4hNdgVxikGUqnZ/G80xQu4QX0TSVX+RG8Wwn VNu3ks7FGw0lKhmDQVANODH4MK02qwDoR+4YIu4kPQ== X-Google-Smtp-Source: APXvYqwv1DAqeJDxj1BR/mVOls+XWht4DhUm2eGk3cbzkXumNXi4kiC1qjGlDH+tPPXvPCfEsv5lGHYnp8KEgnRaHF8= X-Received: by 2002:a25:5755:: with SMTP id l82mr54855357ybb.25.1554154690145; Mon, 01 Apr 2019 14:38:10 -0700 (PDT) MIME-Version: 1.0 References: <20190331064129.31702-1-brianvv.kernel@gmail.com> <74e3024f-6fde-a04d-4000-89c6e61acc26@iogearbox.net> In-Reply-To: <74e3024f-6fde-a04d-4000-89c6e61acc26@iogearbox.net> From: =?UTF-8?Q?Maciej_=C5=BBenczykowski?= Date: Mon, 1 Apr 2019 14:37:59 -0700 Message-ID: Subject: Re: [PATCH] bpf: do not start from first bucket if elem is not found on a htab To: Daniel Borkmann Cc: Brian Vazquez , Brian Vazquez , Alexei Starovoitov , "David S . Miller" , Kernel hackers , Linux NetDev Content-Type: text/plain; charset="UTF-8" Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org > This breaks BPF selftest suite unfortunately: > > # ./test_maps > test_maps: test_maps.c:114: test_hashmap: Assertion `bpf_map_get_next_key(fd, &key, &next_key) == 0 && (next_key == first_key)' failed. > Aborted > > Some more background, situation is a bit tricky: pre 8fe45924387b ("bpf: > map_get_next_key to return first key on NULL") there was no reliable way > of getting to the start of a hash table, meaning it needed an 'invalid' > key to return the first element for starting traversal which commit fixed > by being able to pass in NULL. So some applications might still just rely > on e.g. key of zero bytes (if guaranteed to not be used otherwise) to do > just that. With this patch, we'd start out from anywhere in the hash table. sdf@ just mentioned this internally as well... I think we simply will need to add a flags field with at least two options/flags: - return error if key not found - resume from bucket instead of beginning if key not found and while we're at it: - return concatenated key+value instead of just key to save an immediate lookup on the returned key