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;
Feedback-ID: ieff94742:Fastmail
User-Agent: Cyrus-JMAP/3.9.0-alpha0-496-g8c46984af0-fm-20230615.001-g8c46984a
Mime-Version: 1.0
Message-Id: <1d332a4f-3c45-4e6c-81ca-7f8e669b0366@app.fastmail.com>
In-Reply-To: <ZI3Sh6p8b4FcP0Y2@moria.home.lan>
References: <20230509165657.1735798-1-kent.overstreet@linux.dev>
 <20230509165657.1735798-8-kent.overstreet@linux.dev>
 <3508afc0-6f03-a971-e716-999a7373951f@wdc.com>
 <202305111525.67001E5C4@keescook> <ZF6Ibvi8U9B+mV1d@moria.home.lan>
 <202305161401.F1E3ACFAC@keescook> <ZGPzocRpSlg+4vgN@moria.home.lan>
 <1d249326-e3dd-9c9d-7b53-2fffeb39bfb4@kernel.org>
 <ZI3Sh6p8b4FcP0Y2@moria.home.lan>
Date:   Sat, 17 Jun 2023 12:19:41 -0700
From:   "Andy Lutomirski" <luto@kernel.org>
To:     "Kent Overstreet" <kent.overstreet@linux.dev>
Cc:     "Kees Cook" <keescook@chromium.org>,
        "Johannes Thumshirn" <Johannes.Thumshirn@wdc.com>,
        "Linux Kernel Mailing List" <linux-kernel@vger.kernel.org>,
        "linux-fsdevel@vger.kernel.org" <linux-fsdevel@vger.kernel.org>,
        "linux-bcachefs@vger.kernel.org" <linux-bcachefs@vger.kernel.org>,
        "Kent Overstreet" <kent.overstreet@gmail.com>,
        "Andrew Morton" <akpm@linux-foundation.org>,
        "Uladzislau Rezki" <urezki@gmail.com>,
        "hch@infradead.org" <hch@infradead.org>,
        "linux-mm@kvack.org" <linux-mm@kvack.org>,
        "linux-hardening@vger.kernel.org" <linux-hardening@vger.kernel.org>
Subject: Re: [PATCH 07/32] mm: Bring back vmalloc_exec
Content-Type: text/plain
Precedence: bulk

On Sat, Jun 17, 2023, at 8:34 AM, Kent Overstreet wrote:
> On Fri, Jun 16, 2023 at 09:13:22PM -0700, Andy Lutomirski wrote:
>> On 5/16/23 14:20, Kent Overstreet wrote:
>> > On Tue, May 16, 2023 at 02:02:11PM -0700, Kees Cook wrote:
>> > > For something that small, why not use the text_poke API?
>> > 
>> > This looks like it's meant for patching existing kernel text, which
>> > isn't what I want - I'm generating new functions on the fly, one per
>> > btree node.
>> 
>> Dynamically generating code is a giant can of worms.
>> 
>> Kees touched on a basic security thing: a linear address mapped W+X is a big
>> no-no.  And that's just scratching the surface -- ideally we would have a
>> strong protocol for generating code: the code is generated in some
>> extra-secure context, then it's made immutable and double-checked, then
>> it becomes live.
>
> "Double checking" arbitrary code is is fantasy. You can't "prove the
> security" of arbitrary code post compilation.
>
> Rice's theorem states that any nontrivial property of a program is
> either a direct consequence of the syntax, or is undecidable. It's why
> programs in statically typed languages are easier to reason about, and
> it's also why the borrow checker in Rust is a syntactic construct.

If you want security in some theoretical sense, sure, you're probably right.  But that doesn't stop people from double-checking executable code to quite good effect.  For example:

https://www.bitdefender.com/blog/businessinsights/bitdefender-releases-landmark-open-source-software-project-hypervisor-based-memory-introspection/

(I have no personal experience with this, but I know people who do.  It's obviously not perfect, but I think it provides meaningful benefits.)

I'm not saying Linux should do this internally, but it might not be a terrible idea some day.

>
> You just have to be able to trust the code that generates the code. Just
> like you have to be able to trust any other code that lives in kernel
> space.
>
> This is far safer and easier to reason about than what BPF is doing
> because we're not compiling arbitrary code, the actual codegen part is
> 200 loc and the input is just a single table.

Great, then propose a model where the codegen operates in an extra-safe protected context.  Or pre-generate the most common variants, have them pull their constants from memory instead of immediates, and use that.

>
>> 
>> (When x86 modifies itself at boot or for static keys, it changes out the
>> page tables temporarily.)
>> 
>> And even beyond security, we have correctness.  x86 is a fairly forgiving
>> architecture.  If you go back in time about 20 years, modify
>> some code *at the same linear address at which you intend to execute it*,
>> and jump to it, it works.  It may even work if you do it through
>> an alias (the manual is vague).  But it's not 20 years ago, and you have
>> multiple cores.  This does *not* work with multiple CPUs -- you need to
>> serialize on the CPU executing the modified code.  On all the but the very
>> newest CPUs, you need to kludge up the serialization, and that's
>> sloooooooooooooow.  Very new CPUs have the SERIALIZE instruction, which
>> is merely sloooooow.
>
> If what you were saying was true, it would be an issue any time we
> mapped in new executable code for userspace - minor page faults would be
> stupidly slow.

I literally mentioned this in the email.

I don't know _precisely_ what's going on, but I assume it's that it's impossible (assuming the kernel gets TLB invalidation right) for a CPU to have anything buffered for a linear address that is unmapped, so when it gets mapped, the CPU can't have anything stale in its buffers.  (By buffers, I mean any sort of instruction or decoded instruction cache.)

Having *this* conversation is what I was talking about in regard to possible fancy future optimization.

>
> This code has been running on thousands of machines for years, and the
> only issues that have come up have been due to the recent introduction
> of indirect branch tracking. x86 doesn't have such broken caches, and
> architectures that do have utterly broken caches (because that's what
> you're describing: you're describing caches that _are not coherent
> across cores_) are not high on my list of things I care about.

I care.  And a bunch of people who haven't gotten their filesystem corrupted because of a missed serialization.

>
> Also, SERIALIZE is a spectre thing. Not relevant here.

Nope, try again.  SERIALIZE "serializes" in the rather vague sense in the Intel SDM.  I don't think it's terribly useful for Spectre.

(Yes, I know what I'm talking about.)

>
>> Based on the above, I regret to inform you that jit_update() will either
>> need to sync all cores via IPI or all cores will need to check whether a
>> sync is needed and do it themselves.
>
> text_poke() doesn't even send IPIs.

text_poke() and the associated machinery is unbelievably complicated.  

Also, arch/x86/kernel/alternative.c contains:

void text_poke_sync(void)
{
	on_each_cpu(do_sync_core, NULL, 1);
}

The magic in text_poke() was developed over the course of years, and Intel architects were involved.

(And I think some text_poke() stuff uses RCU, which is another way to sync without IPI.  I doubt the performance characteristics are appropriate for bcachefs, but I could be wrong.)

>
> I think you've been misled about some things :)

I wish.


I like bcachefs.  I really don't want to have to put on my maintainer hat here, and I do indeed generally stay in the background.  (And I haven't had nearly as much time for this kind of the work in the last couple years as I'd like, sigh.) But I personally have a fairly strict opinion that, if someone (including myself!) wants to merge something that plays clever games that may cause x86 architecture code (especially mm code) to do things it shouldn't in corner cases, even if no one has directly observed that corner case or even knows how to get it to misbehave, then they had better have a very convincing argument that it's safe.  No one likes debugging bugs when something that should be coherent becomes incoherent.

So, if you really really want self-modifying code in bcachefs, its correctness needs to be very, very well argued, and it needs to be maintainable.  Otherwise I will NAK it.  Sorry.