[RFC] ->d_name accesses

[RFC] ->d_name accesses

[Al Viro]

	There are very few places that legitimitely can do stores to
dentry->d_name.  Basically, it's dentry creation and d_move() guts.
Unforutunately, there is a _lot_ of places where we access ->d_name -
every ->lookup(), ->create(), ->unlink(), etc. instances has to do
just that - that's how the directory entry name is passed to those.

	Verifying that nobody is playing silly buggers with ->d_name
contents take, IME, several hours of code audit.  And that has to
be repeated every cycle.  Compiler is no help there - it's grep over
the tree, exclude the irrelevant hits (struct dirent has a field
with that name, so does e.g. UFS directory entry, etc.) and looking
through the 900-odd places that remain after that.  Not fun, to
put it politely.

	One way to do that would be to replace d_name with
	union {
		const struct qstr d_name;
		struct qstr __d_name;
	};
and let the the places that want to modify it use __d_name.
Tempting, but the thing that makes me rather nervous about this
approach is that such games with unions are straying into
the nasal demon country (C99 6.7.3[5]), inviting the optimizers
to play.  Matt Wilcox pointed out that mainline already has
i_nlink/__i_nlink pair, but...  there are fewer users of those
and the damage from miscompiles would be less sensitive.
Patch along those lines would be pretty simple, though.

	There's an alternative way to get rid of that headache
that ought to be safer:

* add an inlined helper,
static inline const struct qstr *d_name(const struct dentry *d)
{
	return &d->d_name;
}

* gradually convert the accesses to ->d_name to calls of that helper -
e.g.
	ret = udf_fiiter_find_entry(dir, &dentry->d_name, &iter);
becoming
	ret = udf_fiiter_find_entry(dir, d_name(dentry), &iter);
while
        err = msdos_find(dir, dentry->d_name.name, dentry->d_name.len, &sinfo);
becomes either
        err = msdos_find(dir, d_name(dentry)->name, d_name(dentry)->len, &sinfo);
or, if msdos_find() gets converted to passing const struct qstr *
instead of passing name and length as separate arguments,
        err = msdos_find(dir, d_name(dentry), &sinfo);
I am *NOT* suggesting doing that step in a single conversion - that
would cause too many conflicts, wouldn't be easy to automate and there's
a considerable pile of places that would be better off with conversion
like above and those should be decided on case-by-case basis.  However,
it's not hard to do as a patch series, with very few dependencies other
than "need to have that helper in place".  And it's not hard to keep
track of unconverted instances.  Some of the existing functions would
need struct qstr * argument constified - 4 of those in current mainline
(the same functions would need that treatment with anon union approach
as well; again, there are very few of them and it's not hard to do).

* once everything is converted (with the exception of several places in
fs/dcache.c and this d_name() inline itself), we can declared the use
of d_name() mandatory and rename the field to e.g. __d_name.

At that point audits become as easy as grep for new name of the field
and for casts to struct qstr * - compiler will take care of the rest.

That variant is longer, but it's not too large either.  And it feels
safer wrt optimizer behaviour...

Preferences, comments?

Re: [RFC] ->d_name accesses

[Matthew Wilcox]

On Wed, Feb 07, 2024 at 10:22:48PM +0000, Al Viro wrote:
> 	One way to do that would be to replace d_name with
> 	union {
> 		const struct qstr d_name;
> 		struct qstr __d_name;
> 	};
> and let the the places that want to modify it use __d_name.
> Tempting, but the thing that makes me rather nervous about this
> approach is that such games with unions are straying into
> the nasal demon country (C99 6.7.3[5]), inviting the optimizers
> to play.  Matt Wilcox pointed out that mainline already has
> i_nlink/__i_nlink pair, but...  there are fewer users of those
> and the damage from miscompiles would be less sensitive.
> Patch along those lines would be pretty simple, though.

You're referring to this, I assume:

	If an attempt is made to modify an object defined with
	a const-qualified type through use of an lvalue with
	non-const-qualified type, the behavior is undefined

I'm not sure that's relevant.  As I see it, we're defining two objects,
one const-qualified and one not.  The union specifies that they share
the same storage ("a union is a type consisting of a sequence of members
whose storage overlap").

I see 6.7.3 as saying "even if you cast away the const from d_name,
modifyig d_name is undefined", but you're not modifying d_name,
you're modifying __d_name, which just happens to share storage with
d_name.

I think 6.7.2.1[14] is more likely to cause us problems:

	The value of at most one of the members can be stored in a union
	object at any time.

From that the compiler can assume that if it sees a store to __d_name
that accesses to d_name are undefined?  Perhaps?  My brain always starts
to hurt when people start spec-lawyering.

> * add an inlined helper,
> static inline const struct qstr *d_name(const struct dentry *d)
> {
> 	return &d->d_name;
> }

I'm in no way opposed to this solution.  I just thought that the i_nlink
solution might also work for you (and if the compiler people say the
i_nlink solution is actually not spec compliant, then I guess we can
adopt an i_nlink_read() function).

Re: [RFC] ->d_name accesses

[Nick Desaulniers]

On Wed, Feb 7, 2024 at 2:55 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Wed, Feb 07, 2024 at 10:22:48PM +0000, Al Viro wrote:
> >       One way to do that would be to replace d_name with
> >       union {
> >               const struct qstr d_name;
> >               struct qstr __d_name;
> >       };
> > and let the the places that want to modify it use __d_name.
> > Tempting, but the thing that makes me rather nervous about this
> > approach is that such games with unions are straying into
> > the nasal demon country (C99 6.7.3[5]), inviting the optimizers
> > to play.  Matt Wilcox pointed out that mainline already has
> > i_nlink/__i_nlink pair, but...  there are fewer users of those
> > and the damage from miscompiles would be less sensitive.
> > Patch along those lines would be pretty simple, though.
>
> You're referring to this, I assume:
>
>         If an attempt is made to modify an object defined with
>         a const-qualified type through use of an lvalue with
>         non-const-qualified type, the behavior is undefined

I have 100% observed llvm throw out writes to objects declared as
const where folks tried to write via "casting away the const" (since
that's UB) which resulted in boot failures in the Linux kernel
affecting android devices.  I can't find the commit in question at the
moment, but seemed to have made some kind of note in it in 2020.
https://android-review.git.corp.google.com/c/platform/prebuilts/clang/host/linux-x86/+/1201901/1/RELEASE_NOTES.md

That said, I just tried Al's union, and don't observe such optimizations.
https://godbolt.org/z/zrj71E8W5

This whole suggestion makes me laugh "in C++ private members."

>
> I'm not sure that's relevant.  As I see it, we're defining two objects,
> one const-qualified and one not.  The union specifies that they share
> the same storage ("a union is a type consisting of a sequence of members
> whose storage overlap").
>
> I see 6.7.3 as saying "even if you cast away the const from d_name,
> modifyig d_name is undefined", but you're not modifying d_name,
> you're modifying __d_name, which just happens to share storage with
> d_name.
>
> I think 6.7.2.1[14] is more likely to cause us problems:
>
>         The value of at most one of the members can be stored in a union
>         object at any time.
>
> From that the compiler can assume that if it sees a store to __d_name
> that accesses to d_name are undefined?  Perhaps?  My brain always starts
> to hurt when people start spec-lawyering.
>
> > * add an inlined helper,
> > static inline const struct qstr *d_name(const struct dentry *d)
> > {
> >       return &d->d_name;
> > }
>
> I'm in no way opposed to this solution.  I just thought that the i_nlink
> solution might also work for you (and if the compiler people say the
> i_nlink solution is actually not spec compliant, then I guess we can
> adopt an i_nlink_read() function).



-- 
Thanks,
~Nick Desaulniers

Re: [RFC] ->d_name accesses

[Linus Torvalds]

On Fri, 9 Feb 2024 at 11:10, Nick Desaulniers <ndesaulniers@google.com> wrote:
>
> I have 100% observed llvm throw out writes to objects declared as
> const where folks tried to write via "casting away the const" (since
> that's UB) which resulted in boot failures in the Linux kernel
> affecting android devices.

*PLEASE* fix compilers that silently generate bogus code just because it's UB.

That's pure and utter garbage.

We want a compiler flag that says "don't do that idiotic sh*t". There
are very good reasons why Linux uses flags like

  -fno-strict-overflow
  -fno-strict-aliasing
  -fno-delete-null-pointer-checks

and that reason is that the ANSI C standards committee has had its
head up its arse when it comes to these areas.

Optimizations based on undefined behavior are wrong. If you have to
resort to those kinds of optimizations, your compiler is bad.

*Silently* doing so is even worse.

If the compiler decides "I will throw away this write because it's
UB", I want a warning.

Better yet, I'd like to see compiler writers admit that undefined
behavior was not a good language feature in the first place, and that
any time the standard says "that's undefined behavior", you ignore
that bogus standards language, and you turn it into "implementation
defined", possibly with a warning.

                   Linus

Re: [RFC] ->d_name accesses

[Al Viro]

On Fri, Feb 09, 2024 at 11:10:10AM -0800, Nick Desaulniers wrote:
 
> I have 100% observed llvm throw out writes to objects declared as
> const where folks tried to write via "casting away the const" (since
> that's UB) which resulted in boot failures in the Linux kernel
> affecting android devices.  I can't find the commit in question at the
> moment, but seemed to have made some kind of note in it in 2020.
> https://android-review.git.corp.google.com/c/platform/prebuilts/clang/host/linux-x86/+/1201901/1/RELEASE_NOTES.md
> 
> That said, I just tried Al's union, and don't observe such optimizations.
> https://godbolt.org/z/zrj71E8W5

FWIW, see #work.qstr in git://git.kernel.org:/pub/scm/linux/kernel/git/viro/vfs.git

First 4 commits are constifying the arguments that get &dentry->d_inode
passed into, followed by the patch below.  __d_alloc(), swap_names(), copy_name()
and d_mark_tmpfile() - no other writers...

diff --git a/fs/dcache.c b/fs/dcache.c
index b813528fb147..d21df0fb967d 100644
--- a/fs/dcache.c
+++ b/fs/dcache.c
@@ -1651,13 +1651,13 @@ static struct dentry *__d_alloc(struct super_block *sb, const struct qstr *name)
 		dname = dentry->d_iname;
 	}	
 
-	dentry->d_name.len = name->len;
-	dentry->d_name.hash = name->hash;
+	dentry->__d_name.len = name->len;
+	dentry->__d_name.hash = name->hash;
 	memcpy(dname, name->name, name->len);
 	dname[name->len] = 0;
 
 	/* Make sure we always see the terminating NUL character */
-	smp_store_release(&dentry->d_name.name, dname); /* ^^^ */
+	smp_store_release(&dentry->__d_name.name, dname); /* ^^^ */
 
 	dentry->d_lockref.count = 1;
 	dentry->d_flags = 0;
@@ -2695,16 +2695,16 @@ static void swap_names(struct dentry *dentry, struct dentry *target)
 			/*
 			 * Both external: swap the pointers
 			 */
-			swap(target->d_name.name, dentry->d_name.name);
+			swap(target->__d_name.name, dentry->__d_name.name);
 		} else {
 			/*
 			 * dentry:internal, target:external.  Steal target's
 			 * storage and make target internal.
 			 */
-			memcpy(target->d_iname, dentry->d_name.name,
-					dentry->d_name.len + 1);
-			dentry->d_name.name = target->d_name.name;
-			target->d_name.name = target->d_iname;
+			memcpy(target->d_iname, dentry->__d_name.name,
+					dentry->__d_name.len + 1);
+			dentry->__d_name.name = target->__d_name.name;
+			target->__d_name.name = target->d_iname;
 		}
 	} else {
 		if (unlikely(dname_external(dentry))) {
@@ -2712,10 +2712,10 @@ static void swap_names(struct dentry *dentry, struct dentry *target)
 			 * dentry:external, target:internal.  Give dentry's
 			 * storage to target and make dentry internal
 			 */
-			memcpy(dentry->d_iname, target->d_name.name,
-					target->d_name.len + 1);
-			target->d_name.name = dentry->d_name.name;
-			dentry->d_name.name = dentry->d_iname;
+			memcpy(dentry->d_iname, target->__d_name.name,
+					target->__d_name.len + 1);
+			target->__d_name.name = dentry->__d_name.name;
+			dentry->__d_name.name = dentry->d_iname;
 		} else {
 			/*
 			 * Both are internal.
@@ -2728,7 +2728,7 @@ static void swap_names(struct dentry *dentry, struct dentry *target)
 			}
 		}
 	}
-	swap(dentry->d_name.hash_len, target->d_name.hash_len);
+	swap(dentry->__d_name.hash_len, target->__d_name.hash_len);
 }
 
 static void copy_name(struct dentry *dentry, struct dentry *target)
@@ -2738,12 +2738,12 @@ static void copy_name(struct dentry *dentry, struct dentry *target)
 		old_name = external_name(dentry);
 	if (unlikely(dname_external(target))) {
 		atomic_inc(&external_name(target)->u.count);
-		dentry->d_name = target->d_name;
+		dentry->__d_name = target->__d_name;
 	} else {
-		memcpy(dentry->d_iname, target->d_name.name,
-				target->d_name.len + 1);
-		dentry->d_name.name = dentry->d_iname;
-		dentry->d_name.hash_len = target->d_name.hash_len;
+		memcpy(dentry->d_iname, target->__d_name.name,
+				target->__d_name.len + 1);
+		dentry->__d_name.name = dentry->d_iname;
+		dentry->__d_name.hash_len = target->__d_name.hash_len;
 	}
 	if (old_name && likely(atomic_dec_and_test(&old_name->u.count)))
 		kfree_rcu(old_name, u.head);
@@ -3080,7 +3080,7 @@ void d_mark_tmpfile(struct file *file, struct inode *inode)
 		!d_unlinked(dentry));
 	spin_lock(&dentry->d_parent->d_lock);
 	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
-	dentry->d_name.len = sprintf(dentry->d_iname, "#%llu",
+	dentry->__d_name.len = sprintf(dentry->d_iname, "#%llu",
 				(unsigned long long)inode->i_ino);
 	spin_unlock(&dentry->d_lock);
 	spin_unlock(&dentry->d_parent->d_lock);
diff --git a/include/linux/dcache.h b/include/linux/dcache.h
index eb4ca8a1d948..a74370b1fe31 100644
--- a/include/linux/dcache.h
+++ b/include/linux/dcache.h
@@ -85,7 +85,10 @@ struct dentry {
 	seqcount_spinlock_t d_seq;	/* per dentry seqlock */
 	struct hlist_bl_node d_hash;	/* lookup hash list */
 	struct dentry *d_parent;	/* parent directory */
-	struct qstr d_name;
+	union {
+	struct qstr __d_name;
+	const struct qstr d_name;
+	};
 	struct inode *d_inode;		/* Where the name belongs to - NULL is
 					 * negative */
 	unsigned char d_iname[DNAME_INLINE_LEN];	/* small names */

Re: [RFC] ->d_name accesses

[Al Viro]

On Fri, Feb 09, 2024 at 11:10:10AM -0800, Nick Desaulniers wrote:

> I have 100% observed llvm throw out writes to objects declared as
> const where folks tried to write via "casting away the const" (since
> that's UB) which resulted in boot failures in the Linux kernel
> affecting android devices.  I can't find the commit in question at the
> moment, but seemed to have made some kind of note in it in 2020.
> https://android-review.git.corp.google.com/c/platform/prebuilts/clang/host/linux-x86/+/1201901/1/RELEASE_NOTES.md
> 
> That said, I just tried Al's union, and don't observe such optimizations.
> https://godbolt.org/z/zrj71E8W5

The really shitty part is not the missing stores; it's reordered loads.
If
	spin_lock(&dentry->d_lock);
	name = dentry->d_name.name;
	len = dentry->d_name.len;
	something(name, len);
	spin_unlock(&dentry->d_lock);
has the compiler go "->d_name is const, so I can bloody well move
the load before that spin_lock() call", we really have a problem.

Can it reorder the loads of const member wrt e.g. barrier()?  If
that's the case, this approach is no-go and accessor is the only
feasible alternative.

Re: [RFC] ->d_name accesses

[Linus Torvalds]

On Fri, 9 Feb 2024 at 20:23, Al Viro <viro@zeniv.linux.org.uk> wrote:
>
> Can it reorder the loads of const member wrt e.g. barrier()?

As far as I know, a C compiler can *not* in any situation think that
"const" means that something is immutable.

In C, a pointer to a "const' thing means that you are not allowed to
modify the object through *that* pointer, but it does not mean that
there might not be another non-const pointer that aliases the same
object.

Now, things are a bit different if the object definition itself is
"const", in that then there is generally no way for such an alias to
happen.

But anything that gets a pointer to a data structure that has a const
member cannot in the general case know whether there might be another
pointer somewhere else that could change said member.

IOW, 'const' - despite the name - does not mean "this field is
constant". It literally means "you can't write through this field".

And then as a very special case of that, if the compiler can show that
there are no possible aliases, the compiler can treat it as a constant
value.

The "no aliases" knowledge might be because the compiler itself
generates the object (eg an automatic variable), but it might also be
through things like "restrict" where the programmer has told the
compiler that no aliases exist.

But when it is a part of a union, by *definition* there are aliases to
the same field, and they may not be const.

End result: a compiler cannot validly hoist the load across the
spin_lock, because as far as the compiler knows, the spinlock could
change the value. 'const' in no way means 'the value cannot change'.

Of course, who knows what bugs can exist, but this is fairly
fundamental.  I don't believe a C compiler can possibly get this wrong
and call itself a C compiler.

                   Linus