From nobody Thu Oct 10 22:23:53 2024
X-Original-To: freebsd-hackers@mlmmj.nyi.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1])
	by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4XPknG0ndDz5Yksc
	for <freebsd-hackers@mlmmj.nyi.freebsd.org>; Thu, 10 Oct 2024 22:24:02 +0000 (UTC)
	(envelope-from vadimnuclight@gmail.com)
Received: from mail-lj1-x234.google.com (mail-lj1-x234.google.com [IPv6:2a00:1450:4864:20::234])
	(using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits)
	 key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256
	 client-signature RSA-PSS (2048 bits) client-digest SHA256)
	(Client CN "smtp.gmail.com", Issuer "WR4" (verified OK))
	by mx1.freebsd.org (Postfix) with ESMTPS id 4XPknF0Y6Bz4lhQ
	for <freebsd-hackers@freebsd.org>; Thu, 10 Oct 2024 22:24:01 +0000 (UTC)
	(envelope-from vadimnuclight@gmail.com)
Authentication-Results: mx1.freebsd.org;
	dkim=pass header.d=gmail.com header.s=20230601 header.b=O4sp7Zrk;
	spf=pass (mx1.freebsd.org: domain of vadimnuclight@gmail.com designates 2a00:1450:4864:20::234 as permitted sender) smtp.mailfrom=vadimnuclight@gmail.com;
	dmarc=pass (policy=none) header.from=gmail.com
Received: by mail-lj1-x234.google.com with SMTP id 38308e7fff4ca-2fb2e21b631so3891781fa.0
        for <freebsd-hackers@freebsd.org>; Thu, 10 Oct 2024 15:24:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1728599038; x=1729203838; darn=freebsd.org;
        h=content-transfer-encoding:mime-version:references:in-reply-to
         :message-id:subject:cc:to:from:date:from:to:cc:subject:date
         :message-id:reply-to;
        bh=HO5UFR7Av1lM/tHrEgFid5gJGAKLwVGttB0YlxJXSTg=;
        b=O4sp7ZrkHHtu0I5kfjs/vcpCSZ/iaYWBrPv31xrItmVbS4M7g2wmtWurwEMbNR+bJi
         nW2jWN3jrhCXu8nBoseHDOMTY7kF1THil7ZjWTjKhJKNBgkFL+a/NOuXoJM5LfLfppxJ
         k8Oi9DvLBWKS1MbHfzJWTq2BGPQlBcuyjh2dicmZiTEUIxnldDHRFNXn2C8TzXTHC7Nj
         XLAoR7neORukFkjSN4DStPnynxPTdBRaWSOg5fXBWaeDmCUUdw0jvRzP3qXDaQda3I3C
         jXsxAoEh/s+oKukh2cydbfZjCMcIhEwMMtsLcCX+rfOpte+TCizIfnv/UPMbdFxNpeIG
         7x0Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1728599038; x=1729203838;
        h=content-transfer-encoding:mime-version:references:in-reply-to
         :message-id:subject:cc:to:from:date:x-gm-message-state:from:to:cc
         :subject:date:message-id:reply-to;
        bh=HO5UFR7Av1lM/tHrEgFid5gJGAKLwVGttB0YlxJXSTg=;
        b=ofYzWW/O6y6lqCgeplpCtS2+PhNaorfwyT96qaqEZe9IB+/hJCLynktEdEGCBPHvsI
         70DFXjMzINp9/8sORCx3OiMRg6szgTa/t/x2fF5w7RHk80txN7f01tjFhKfR/1vktX6Z
         GwkqeU1uPh7g7pe7yaH3kDzN+5jx+RKa5lpCUc/Dd/8ixCDuqjdOtBZklIVHH3g2uu4i
         34pyrQ90YMuzuPaSjK5SnF0YC2iu2B1RE/bXcp3nkepPuUII7xtlHeT99qGU2nz5Dkg8
         jNyu4h02ga4iFSPWpFiZP5TAWScJbYqMjD3IegbX3j2/I+F5SphRvALLtIJlinRirEOz
         1vpw==
X-Gm-Message-State: AOJu0YwVPWJHfnazFMz29qunwtHn6gbtKEa1MIcsPM2A41lDs+bFETAN
	ZzX9pcPZribTvrtdcX0Hr7klF+xJ32X2GWac+Q1uE1jGxCQ0LWddLhFvM7Xp
X-Google-Smtp-Source: AGHT+IF4sITiOShFK+7FjuGBKlL8HLvYW7TF8/0P9LfTSBcKDHinbhP2eppXDvOIamLVfzDbHuvD+w==
X-Received: by 2002:a2e:6119:0:b0:2fa:faed:e86b with SMTP id 38308e7fff4ca-2fb30dfab1bmr1482871fa.13.1728599037794;
        Thu, 10 Oct 2024 15:23:57 -0700 (PDT)
Received: from nuclight.lan ([37.204.254.214])
        by smtp.gmail.com with ESMTPSA id 38308e7fff4ca-2fb24706343sm3402321fa.77.2024.10.10.15.23.56
        (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
        Thu, 10 Oct 2024 15:23:57 -0700 (PDT)
Date: Fri, 11 Oct 2024 01:23:53 +0300
From: Vadim Goncharov <vadimnuclight@gmail.com>
To: "Gavin D. Howard" <gavin@gavinhoward.com>
Cc: "freebsd-hackers@FreeBSD.org" <freebsd-hackers@FreeBSD.org>
Subject: Re: BPF64: proposal of platform-independent hardware-friendly
 backwards-compatible eBPF alternative
Message-ID: <20241011012353.59784a96@nuclight.lan>
In-Reply-To: <f9KxenmdwQZ8oQrcH6ePy30goR2nOPYCULfkQnFaugR0mFpoL_THbqWwt4Jkt4FKpe03xXULUwRCSc8rUdIsnCSeG2X03iSpfNczBy-vks8=@gavinhoward.com>
References: <20240910040544.125245ad@nuclight.lan>
	<wLzD36W8VSXSlBByVmK745ezszNVGM-hfWOobdrCb1vmx9snihwW_gBgeAlvtKWL55fnAZgr9G5ztIO3UjD3Wou3-YPxmLkMp9AFuGHwXsA=@gavinhoward.com>
	<20240910181711.5d324ac5@nuclight.lan>
	<f9KxenmdwQZ8oQrcH6ePy30goR2nOPYCULfkQnFaugR0mFpoL_THbqWwt4Jkt4FKpe03xXULUwRCSc8rUdIsnCSeG2X03iSpfNczBy-vks8=@gavinhoward.com>
X-Mailer: Claws Mail 3.19.1 (GTK+ 2.24.33; amd64-portbld-freebsd12.4)
List-Id: Technical discussions relating to FreeBSD <freebsd-hackers.freebsd.org>
List-Archive: https://lists.freebsd.org/archives/freebsd-hackers
List-Help: <mailto:freebsd-hackers+help@freebsd.org>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Subscribe: <mailto:freebsd-hackers+subscribe@freebsd.org>
List-Unsubscribe: <mailto:freebsd-hackers+unsubscribe@freebsd.org>
Sender: owner-freebsd-hackers@FreeBSD.org
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-Spamd-Result: default: False [-3.99 / 15.00];
	NEURAL_HAM_MEDIUM(-1.00)[-1.000];
	NEURAL_HAM_LONG(-1.00)[-1.000];
	NEURAL_HAM_SHORT(-0.99)[-0.988];
	DMARC_POLICY_ALLOW(-0.50)[gmail.com,none];
	R_SPF_ALLOW(-0.20)[+ip6:2a00:1450:4000::/36];
	R_DKIM_ALLOW(-0.20)[gmail.com:s=20230601];
	MIME_GOOD(-0.10)[text/plain];
	RCPT_COUNT_TWO(0.00)[2];
	ARC_NA(0.00)[];
	FREEMAIL_FROM(0.00)[gmail.com];
	TO_DN_SOME(0.00)[];
	RCVD_TLS_LAST(0.00)[];
	FREEMAIL_ENVFROM(0.00)[gmail.com];
	MIME_TRACE(0.00)[0:+];
	TO_DN_EQ_ADDR_SOME(0.00)[];
	FROM_HAS_DN(0.00)[];
	DWL_DNSWL_NONE(0.00)[gmail.com:dkim];
	TO_MATCH_ENVRCPT_SOME(0.00)[];
	RCVD_COUNT_TWO(0.00)[2];
	FROM_EQ_ENVFROM(0.00)[];
	DKIM_TRACE(0.00)[gmail.com:+];
	PREVIOUSLY_DELIVERED(0.00)[freebsd-hackers@freebsd.org];
	RCVD_VIA_SMTP_AUTH(0.00)[];
	MLMMJ_DEST(0.00)[freebsd-hackers@freebsd.org];
	ASN(0.00)[asn:15169, ipnet:2a00:1450::/32, country:US];
	RCVD_IN_DNSWL_NONE(0.00)[2a00:1450:4864:20::234:from]
X-Rspamd-Queue-Id: 4XPknF0Y6Bz4lhQ
X-Spamd-Bar: ---

On Thu, 12 Sep 2024 06:29:38 +0000
"Gavin D. Howard" <gavin@gavinhoward.com> wrote:

> > > If I understand Turing-completeness correctly, the "no backward
> > > jumps but allow recursion and quit on stack overflow" is exactly
> > > equivalent to having non-infinite loops.  
> >
> > Sure, but then look at practical usefulness: suppose you have stack
> > of 32 frames (current limit of eBPF and BPF64). Then you can have
> > only 31 iterations on a loop, loosing ability to call more
> > functions from loop body.  
> 
> That is true.
> 
> However, I wonder if everyone is going at this the wrong way. More
> specifically, I wonder if we are targeting the entirely wrong level.
> Maybe verifying bytecode or some other low-level code form is just too
> hard. What if it were easier just to provide a higher level language
> that had enough restrictions to be just barely not Turing-complete.

The problem is, then you need compiler of this language in target
environment, e.g. kernel, because you cannot trust that compiler's
output was not modified in a circumventing way.
 
> To test that idea, I did a quick experiment.
> 
> I have been working on a language called Yao for the past three years.
> One feature I planned for the future was the ability to restrict what
> packages and keywords are available at compile time. I had already
> put in the plumbing, but I just hadn't implemented it.
> 
> But I decided to quickly implement it as an experiment.
> 
> First, I needed a stack limit:
> 
> https://git.yzena.com/Yzena/Yc/commit/99c822bf7b
> 
> Now, you can run this:
> 
> ```
> $ ./release/yc yao --max-stack-depth=32 <script>
> ```
> 
> and you get the same max stack depth as eBPF.
> 
> Next, restricting keywords. One unique thing about Yao is that *every*
> keyword is imported like you would import functions, even standard
> ones like `if` and `while`. This means that if a keyword is not
> allowed, I can just skip importing it, and it's like it doesn't even
> exist.
> 
> So I built a way to skip importing the `while` keyword and any other
> keyword that would make the language Turing-complete. Crucially,
> though, it still includes a `foreach` loop, so backwards jumps are
> still possible.

This reminds me of Tcl which has very little syntax, and everything in
"common syntax", like "if" and "while", is in standard library (and
thus defining new syntax constructs is possible to some extent).

However, Tcl, while attractive for task, suffers from problems:
1) "Everything is a string" is incompatible with high performance
2) like Lua, it is too general-pupose - not designed for such security
3) again like Lua and Rust, is maintained outside of *BSD src tree.

> A script with a `while` loop is `tools/rig_slam.yao` in the same repo.
> If you run:
> 
> ```
> $ make # This bootstraps the repo.
> $ ./release/yc yao tools/rig_slam.yao
> ```
> 
> you will get a panic when it tries to parse the `while` loop because I
> haven't implemented the parsing:
> 
> ```
> Panic: Unimplemented
>     Source:
> /home/gavin/Yzena/Code/yc-git/yc/src/yao/keywords.c:2310 Function:
> yao_parse_while() ```
> 
> But if you run this:
> 
> ```
> $ ./release/yc yao --max-stack-depth=32 --lang-mode=iterative \
>   tools/rig_slam.yao
> ```
> 
> you get a compile error, and it doesn't even try to parse the `while`:
> 
> ```
> yc: tools/rig_slam.yao[145:2]
>     Parse error: Incomplete variable declaration for name: while
> 
> yc: tools/rig_slam.yao[145:8]
>     Invalid token: Expected semicolon (';')
> ```
> 
> (You also get a different panic after that because Yao has bugs.)
> 
> Anyway, essentially, the "iterative" language mode with a max stack
> depth makes Yao non-Turing-complete, but with a way to loop.
> 
> You can try that with `tools/format.yao`, which has a `foreach` loop:
> 
> ```
> $ ./release/yc yao --max-stack-depth=32 --lang-mode=iterative \
>   tools/format.yao
> ```
> 
> and it still works.
> 
> I'm not saying Yao as an eBPF replacement is a good idea; it's not.
> But I think this demonstrates that a simple high-level language with a
> simple compiler and a simple VM might be a viable method of
> implementing an eBPF-like thing without a complex verifier.

Probably interesting ideas to borrow, but I've tried to lurk in your
repository for 28 minutes and did not find any tutorial, introduction
or commented example of program longer than helloworld or fizzbuzz. For
BPF64, I've put relatively long example in both C and commented
translation to new language - as with learning new human languages,
first something in language already known to reader.

> Yes, the compiler and VM would need to be in the kernel, but that
> might already be the case with the JIT in Linux.

No, they keep compiler outside of kernel. And JIT is relatively dumb to
translate prepared bytecode.

In fact, having only VM in kernel is consistent with using for
non-kernel environments, like network interface card hardware or
passing to remote server for remote procedure call - yes, these are
also as important targets as BSD kernel. And no hardware engineer in
sane mind will not design a CPU for a human-readable high-level
language, only bytecode VM - maximum that ever was in industry was for
still relatively low level languages, like Forth CPUs (even Lisp
machines did not run Lisp directly).

> Anyway, my point is that before FreeBSD accepts BPF64, it might be a
> good idea to sit down and consider all of the options, brainstorm
> ideas together, and make an excellent design.

So what are other options to consider&

> And it could very well be that BPF64 *is* the best design! I don't
> know; I'm not a kernel guy, nor am I an expert compiler guy.
> 
> > > * But the analysis pass(es) must still live in the kernel.
> > > * There would need to be tutorials or some docs on how to write
> > > whatever language so that backwards jumps are avoided.  
> >
> > So BPF64 took simplicity pass: while you have tutorials etc. it's
> > still very hard to write (non-toy) code that passes verifier. I
> > think a language where you do not need backward jumps but have
> > usable constructs (so you just can't write bad code), even BAW, is
> > a better way to go than try to train people to fight with
> > unnecessary Cerber.  
> 
> Yes, I think you are right on this, which IMO just points to a
> high-level language. Such a language can have whatever constructs are
> safe, but by its very nature, it will be restricted such that
> dangerous code is impossible.
> 
> It would also be easier to write code that passes the "verifier" if
> the verifier is actually the compiler.

This restricts to only one high-level language. Of course, it may look
like

INSERT INTO conntrack FROM current_packet(), time_now() + 60;
DELETE FROM conntrack WHERE expire < time_now();

but I'd better think about .NET-like to allow for different languages
better suited for different areas, not only network.

> judge BPF64. Plus, I can tell you put in a lot of work.

Thanks, you are first one who noticed this.

-- 
WBR, @nuclight