From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from fhigh-a8-smtp.messagingengine.com (fhigh-a8-smtp.messagingengine.com [103.168.172.159]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C75BF20ADF8; Fri, 7 Mar 2025 11:14:22 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=103.168.172.159 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741346065; cv=none; b=XonKUcrxCg6irLTp6N0mF+8XTuo+dZ31CM6RDFMvJv4VhhoESHPXt46irNrzksv60c8idcoy0A6HxUz7PCJyrkS7ePDofdG4PcwJfI/blE+gxe9BoJpmFk5NltAMS5/WK5NnIm7wVPnBIn8Zri3e8iL14EiSio1zGXJet5KaqGQ= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1741346065; c=relaxed/simple; bh=qfwuaRi7jQfdY/tsJPohHR9MdAZm45tyyvJhRd0avUg=; h=Mime-Version:Content-Type:Date:Message-Id:Cc:Subject:From:To: References:In-Reply-To; b=u+dBB3meGAmonbxbZQkS5uc/Jjop5rjeCMVgIiCsXiaUSNdc2zfLhzSzlJgotOXaTRU6PW/zO4P7zNsqTiPaAyj2iUVBECPHvMIGXX0k8JQIzDI+yAKpu1SH+WxkKOH7Rc9RPHIlCsqyJ5sYb2ru0N2zByDxlP6v9IRFW6PEn30= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=arthurfabre.com; spf=pass smtp.mailfrom=arthurfabre.com; dkim=pass (2048-bit key) header.d=arthurfabre.com header.i=@arthurfabre.com header.b=GuRpm84s; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b=XT4LquRz; arc=none smtp.client-ip=103.168.172.159 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=arthurfabre.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=arthurfabre.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=arthurfabre.com header.i=@arthurfabre.com header.b="GuRpm84s"; dkim=pass (2048-bit key) header.d=messagingengine.com header.i=@messagingengine.com header.b="XT4LquRz" Received: from phl-compute-02.internal (phl-compute-02.phl.internal [10.202.2.42]) by mailfhigh.phl.internal (Postfix) with ESMTP id A53E31140151; Fri, 7 Mar 2025 06:14:21 -0500 (EST) Received: from phl-imap-13 ([10.202.2.103]) by phl-compute-02.internal (MEProxy); Fri, 07 Mar 2025 06:14:21 -0500 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=arthurfabre.com; h=cc:cc:content-transfer-encoding:content-type:content-type :date:date:from:from:in-reply-to:in-reply-to:message-id :mime-version:references:reply-to:subject:subject:to:to; s=fm3; t=1741346061; x=1741432461; bh=EfCYmpAv0890CPAQyase3pDIXfpfpyZd dxSR3YcnDrg=; b=GuRpm84svF4xfersuDdEpnketDmpHI37dVhrUHjL6IEnjG1U g8o/6qyjUInBTQkKNs9kVM8kPkdvyWHk/5mt5WXsKAAfuRKuMpjNmFTUJ8CfCgtp +8ItxDTPFUtxI3IZJtWi3gHpL1cRcOMV6+a05edrMnjdN94crAEjRzeYilmBQDGB ogqo1nfcNlONmHFj0pnFKPMmdzcq5ysxEw0T37re9ybEIfrjLOR/NbfejGxzvGz9 Sfn2Duj2u7I35Uf35ew1Fs6EabSh7kIMXtFnrL0dktezCbs47i8slvyhSKVnDX90 YDk8kJXW1ydGfCZc0uwxXvY6ZUEE9vDzq5UVeA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=cc:cc:content-transfer-encoding :content-type:content-type:date:date:feedback-id:feedback-id :from:from:in-reply-to:in-reply-to:message-id:mime-version :references:reply-to:subject:subject:to:to:x-me-proxy :x-me-sender:x-me-sender:x-sasl-enc; s=fm1; t=1741346061; x= 1741432461; bh=EfCYmpAv0890CPAQyase3pDIXfpfpyZddxSR3YcnDrg=; b=X T4LquRzsrsgZrxLe6WXGlDPJT3/MB7s23UumPIPxmad2JlCj6F4u+kNq2r3kNEUI 76mBPhZ7U6nMK0R644qpR2cmWsQXiGMvGZgeSTcLZqZz6foizUQ0bWUuizIRQ1za BZWECyCEwkX1XG7GIZVlUsALIenxEpAoAjuPQkEbxreNnQTR2aEIvN/g7DfbfLRh YsICyT/0S2XQPAO/ewTVnXaFuLHy5UlL6ntc7FtChBgxcR+qw6Su+s8qqvmc6hPo Iq5omdDEkriaSfUHiG8mHevRXdhRQHc8BGRsuzTa22BtoDFxlKg+mjfAKdbuUNEi o0y32GJwN04cVA4S2X/RA== X-ME-Sender: X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeefvddrtddtgdduuddtheduucetufdoteggodetrf dotffvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdggtfgfnhhsuhgsshgtrhhisggv pdfurfetoffkrfgpnffqhgenuceurghilhhouhhtmecufedttdenucesvcftvggtihhpih gvnhhtshculddquddttddmnecujfgurhepofgggfgtfffkvefuhffvofhfjgesthhqredt redtjeenucfhrhhomhepfdetrhhthhhurhcuhfgrsghrvgdfuceorghrthhhuhhrsegrrh hthhhurhhfrggsrhgvrdgtohhmqeenucggtffrrghtthgvrhhnpefhfeejgefhhffhveel teehhfffheffvdettdelgfeltefhteelveeuffetfffgjeenucevlhhushhtvghrufhiii gvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpegrrhhthhhurhesrghrthhhuhhrfhgr sghrvgdrtghomhdpnhgspghrtghpthhtohepuddtpdhmohguvgepshhmthhpohhuthdprh gtphhtthhopegrfhgrsghrvgestghlohhuughflhgrrhgvrdgtohhmpdhrtghpthhtohep jhgrkhhusgestghlohhuughflhgrrhgvrdgtohhmpdhrtghpthhtohepjhgsrhgrnhguvg gsuhhrghestghlohhuughflhgrrhgvrdgtohhmpdhrtghpthhtohephigrnhestghlohhu ughflhgrrhgvrdgtohhmpdhrtghpthhtoheprghlvgigvghirdhsthgrrhhovhhoihhtoh hvsehgmhgrihhlrdgtohhmpdhrtghpthhtohephhgrfihksehkvghrnhgvlhdrohhrghdp rhgtphhtthhopehlsghirghntghonhesrhgvughhrghtrdgtohhmpdhrtghpthhtohepth hhohhilhgrnhgusehrvgguhhgrthdrtghomhdprhgtphhtthhopegsphhfsehvghgvrhdr khgvrhhnvghlrdhorhhg X-ME-Proxy: Feedback-ID: i9179493c:Fastmail Received: by mailuser.phl.internal (Postfix, from userid 501) id 600431F00072; Fri, 7 Mar 2025 06:14:21 -0500 (EST) X-Mailer: MessagingEngine.com Webmail Interface Precedence: bulk X-Mailing-List: netdev@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=UTF-8 Date: Fri, 07 Mar 2025 12:14:20 +0100 Message-Id: Cc: "Network Development" , "bpf" , "Jakub Sitnicki" , "Jesper Dangaard Brouer" , "Yan Zhai" , , =?utf-8?q?Toke_H=C3=B8iland-J=C3=B8rgensen?= , , "Arthur Fabre" Subject: Re: [PATCH RFC bpf-next 01/20] trait: limited KV store for packet metadata From: "Arthur Fabre" To: "Alexei Starovoitov" X-Mailer: aerc 0.17.0 References: <20250305-afabre-traits-010-rfc2-v1-0-d0ecfb869797@cloudflare.com> <20250305-afabre-traits-010-rfc2-v1-1-d0ecfb869797@cloudflare.com> In-Reply-To: On Fri Mar 7, 2025 at 7:36 AM CET, Alexei Starovoitov wrote: > On Wed, Mar 5, 2025 at 6:33=E2=80=AFAM wrote: > > > > +struct __trait_hdr { > > + /* Values are stored ordered by key, immediately after the head= er. > > + * > > + * The size of each value set is stored in the header as two bi= ts: > > + * - 00: Not set. > > + * - 01: 2 bytes. > > + * - 10: 4 bytes. > > + * - 11: 8 bytes. > > ... > > > + * - hweight(low) + hweight(high)<<1 is offset. > > the comment doesn't match the code > > > + */ > > + u64 high; > > + u64 low; > > ... > > > +static __always_inline int __trait_total_length(struct __trait_hdr h) > > +{ > > + return (hweight64(h.low) << 1) + (hweight64(h.high) << 2) > > + // For size 8, we only get 4+2=3D6. Add another 2 in. > > + + (hweight64(h.high & h.low) << 1); > > +} > > This is really cool idea, but 2 byte size doesn't feel that useful. > How about: > - 00: Not set. > - 01: 4 bytes. > - 10: 8 bytes. > - 11: 16 bytes. > > 4 byte may be useful for ipv4, 16 for ipv6, and 8 is just a good number. > And compute the same way with 3 popcount with extra +1 to shifts. I chose the sizes arbitrarily, happy to change them. 16 is also useful for UUIDs, for tracing. Size 0 could store bools / flags. Keys could be set without a value,=20 and users could check if the key is set or not. That replaces single bits of the mark today, for example a "route locally" key. That only leaves one other size, maybe 4 for smaller values? If we want more sizes, we could also: - Add another u64 word to the header, so we have 3 bits per key. It uses more room, and we need more popcnts, but most modern x86 CPUs can do 3 popcnts in parallel so it could be ok. - Let users set consecutive keys to one big value. Instead of supporting size 16, we let them set two 8 byte KVs in one trait_set() call and provide a 16 byte value. Eg: trait_set_batch(u64 key_from, u64_key_to, size, ...); It's easy to implement, but it makes the API more complicated.