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=-4.0 required=3.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_PASS,URIBL_BLOCKED autolearn=ham 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 C60EBC43381 for ; Fri, 22 Feb 2019 21:30:35 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 886D4206BB for ; Fri, 22 Feb 2019 21:30:35 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=pass (2048-bit key) header.d=netronome-com.20150623.gappssmtp.com header.i=@netronome-com.20150623.gappssmtp.com header.b="SBTfbnq8" Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1725863AbfBVVae (ORCPT ); Fri, 22 Feb 2019 16:30:34 -0500 Received: from mail-qk1-f195.google.com ([209.85.222.195]:36098 "EHLO mail-qk1-f195.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1725774AbfBVVae (ORCPT ); Fri, 22 Feb 2019 16:30:34 -0500 Received: by mail-qk1-f195.google.com with SMTP id c2so1318284qkb.3 for ; Fri, 22 Feb 2019 13:30:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=netronome-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:in-reply-to:references :organization:mime-version:content-transfer-encoding; bh=kNnuvzQRGiyE512xAiggEsl+0qbJLIPwn2lLqLq5rWU=; b=SBTfbnq8VQBdtgFIzFnOml3faAICXLL4q1rM+1v97uyHYZ6EwxHMaCWz/I3xTnj8uw vCFHc3fk9ttwL1GmnIcappzX77Gn94K7maxQGgCh/etOphX/ZkJ7B0dT6Z63GYbJApSn E6F/uon6k1U6tsBqsN3ubWolwgvZ31EuRMmkqgcp6k827o7U/j//WOsQsams3RInd80W VjfA5fPJ6eugwmCxVEJXsMPLUOegMuETCmC9AGtHGBBJBSYCOPh5dNSkwO8rbxfk3Jfb TPZ7IOt6yOZsdguzJyohjpGbSdudB0GzS8Jw28djHbQth7R/27cS1le3TpxCRiEZrVUA JB5g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:cc:subject:message-id:in-reply-to :references:organization:mime-version:content-transfer-encoding; bh=kNnuvzQRGiyE512xAiggEsl+0qbJLIPwn2lLqLq5rWU=; b=GNOLsIMPrEkNGwsCSaymLcZae+QbEMTHvrPiInkHA+s8US8aFRODkEXKgqGteo8+Qy /zDhCRCtP6MmAZTSYmCHN8H2extpmhxkDZDvAFWVYqdg7m+8HwpyVdXnXi53SchQE+y9 TBk2GfZwllfISMN3+DxNQ4B0ErQbYX3MGtvx5B3fqXhbpDAJKBiCxaKgekYc7/NwDkob Ses3sr/y3LQdpH/fVUNXC4H7gwKROYCttM4RHvwK1s5wDuVB3vxiu3piNg1DTZy31iY/ wPPdy9bVHRes1LzQjd6tfHYFn4pb9duEIuKhoULuvEne2hj53demaIZ2HtZLqMjtFmhJ GaJw== X-Gm-Message-State: AHQUAubrdpMWZMAlO55zcHOap8y1IM+cz0D0D0cfe2SeqnemOinMr6qd DGpaNavv6Kn6DyQc/gRewv+F7nGP5ws= X-Google-Smtp-Source: AHgI3IZNfnUvswdSnKP2PDyGFQxDRqi3t8I3UFCCe95pAQhW3DT5SqT7g9jG6ja4jXH4318tka3Spw== X-Received: by 2002:a37:6115:: with SMTP id v21mr3017644qkb.185.1550871032597; Fri, 22 Feb 2019 13:30:32 -0800 (PST) Received: from cakuba.netronome.com ([66.60.152.14]) by smtp.gmail.com with ESMTPSA id 46sm1503919qty.59.2019.02.22.13.30.31 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Fri, 22 Feb 2019 13:30:32 -0800 (PST) Date: Fri, 22 Feb 2019 13:30:29 -0800 From: Jakub Kicinski To: Toke =?UTF-8?B?SMO4aWxhbmQtSsO4cmdlbnNlbg==?= Cc: David Miller , netdev@vger.kernel.org, Jesper Dangaard Brouer , Daniel Borkmann , Alexei Starovoitov Subject: Re: [PATCH net-next 2/2] xdp: Add devmap_idx map type for looking up devices by ifindex Message-ID: <20190222133029.131d066d@cakuba.netronome.com> In-Reply-To: <87y368gnoh.fsf@toke.dk> References: <155075021399.13610.12521373406832889226.stgit@alrua-x1> <155075021407.13610.6656977312753058829.stgit@alrua-x1> <20190221134923.53c40b11@cakuba.netronome.com> <874l8wiw3k.fsf@toke.dk> <20190221163218.72905325@cakuba.netronome.com> <87y368gnoh.fsf@toke.dk> Organization: Netronome Systems, Ltd. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Sender: netdev-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: netdev@vger.kernel.org On Fri, 22 Feb 2019 10:47:10 +0100, Toke H=C3=B8iland-J=C3=B8rgensen wrote: > Jakub Kicinski writes: >=20 > > On Fri, 22 Feb 2019 00:02:23 +0100, Toke H=C3=B8iland-J=C3=B8rgensen wr= ote: =20 > >> Jakub Kicinski writes: > >> =20 > >> > On Thu, 21 Feb 2019 12:56:54 +0100, Toke H=C3=B8iland-J=C3=B8rgensen= wrote: =20 > >> >> A common pattern when using xdp_redirect_map() is to create a devic= e map > >> >> where the lookup key is simply ifindex. Because device maps are arr= ays, > >> >> this leaves holes in the map, and the map has to be sized to fit the > >> >> largest ifindex, regardless of how many devices actually are actual= ly > >> >> needed in the map. > >> >>=20 > >> >> This patch adds a second type of device map where the key is interp= reted as > >> >> an ifindex and looked up using a hashmap, instead of being used as = an array > >> >> index. This leads to maps being densely packed, so they can be smal= ler. > >> >>=20 > >> >> The default maps used by xdp_redirect() are changed to use the new = map > >> >> type, which means that xdp_redirect() is no longer limited to ifind= ex < 64, > >> >> but instead to 64 total simultaneous interfaces per network namespa= ce. This > >> >> also provides an easy way to compare the performance of devmap and > >> >> devmap_idx: > >> >>=20 > >> >> xdp_redirect_map (devmap): 8394560 pkt/s > >> >> xdp_redirect (devmap_idx): 8179480 pkt/s > >> >>=20 > >> >> Difference: 215080 pkt/s or 3.1 nanoseconds per packet. =20 > >> > > >> > Could you share what the ifindex mix was here, to arrive at these > >> > numbers? How does it compare to using an array but not keying with > >> > ifindex? =20 > >>=20 > >> Just the standard set on my test machine; ifindex 1 through 9, except 8 > >> in this case. So certainly no more than 1 ifindex in each hash bucket > >> for those numbers. =20 > > > > Oh, I clearly misread your numbers, it's still slower than array, you > > just don't need the size limit. =20 >=20 > Yeah, this is not about speeding up devmap, it's about lifting the size > restriction. >=20 > >> >> Signed-off-by: Toke H=C3=B8iland-J=C3=B8rgensen = =20 > >> > =20 > >> >> +static int dev_map_idx_update_elem(struct bpf_map *map, void *key,= void *value, > >> >> + u64 map_flags) > >> >> +{ > >> >> + struct bpf_dtab *dtab =3D container_of(map, struct bpf_dtab, map); > >> >> + struct bpf_dtab_netdev *dev, *old_dev; > >> >> + u32 idx =3D *(u32 *)key; > >> >> + u32 val =3D *(u32 *)value; > >> >> + u32 bit; > >> >> + > >> >> + if (unlikely(map_flags > BPF_EXIST)) > >> >> + return -EINVAL; > >> >> + if (unlikely(map_flags =3D=3D BPF_NOEXIST)) > >> >> + return -EEXIST; > >> >> + > >> >> + old_dev =3D __dev_map_idx_lookup_elem(map, idx); > >> >> + if (!val) { > >> >> + if (!old_dev) > >> >> + return 0; =20 > >> > > >> > IMHO this is a fairly strange mix of array and hashmap semantics. I > >> > think you should stick to hashmap behaviour AFA flags and > >> > update/delete goes. =20 > >>=20 > >> Yeah, the double book-keeping is a bit strange, but it allows the actu= al > >> forwarding and flush code to be reused between both types of maps. I > >> think this is worth the slight semantic confusion :) =20 > > > > I'm not sure I was clear, let me try again :) Your get_next_key only > > reports existing indexes if I read the code right, so that's not an > > array - in an array indexes always exist. What follows inserting 0 > > should not be equivalent to delete and BPF_NOEXIST should be handled > > appropriately. =20 >=20 > Ah, I see what you mean. Yeah, sure, I guess I can restrict deletion to > only working through explicit delete. >=20 > I could also add a fail on NOEXIST, but since each index is tied to a > particular value, you can't actually change the contents of each index, > only insert and remove. So why would you ever set that flag? The reason user would have for setting the flag is not clear :) But=20 if you want to reject it because it's unsupported/makes no sense, you should do EINVAL, not EEXIST ;) > > Different maps behave differently, I think it's worth trying to limit > > the divergence in how things behave to the basic array and a hashmap > > models when possible. =20 >=20 > So I don't actually think of this as a hashmap in the general sense; > after all, you can only store ifindexes in it, and key and value are > tied to one another. So it's an ifindex'ed devmap (which is also why I > named it devmap_idx and not devmap_hash); the fact that it's implemented > as a hashmap is just incidental. >=20 > So I guess it's a choice between being consistent with the other devmap > type, or with a general hashmap. I'm not actually sure that the latter > is less surprising? :) The distinction is that if entry is not in the map get_next won't return its key. As you say the construct is not really a hash map (probably a set is the closest) but it most definitely is not an array, so no hard EEXIST on NOEXIST flag :)