Considering uninitialized function parameters UB

[ramosian-glider]

I've learned recently that Clang may mark certain function parameters as noundef, and passing uninitialized data in such parameters will be considered an UB (see https://llvm.org/docs/LangRef.html for the definition of noundef).

Moreover, Clang is quite aggressive in assigning noundef and can do that even for parameters that aren't always used: https://godbolt.org/z/s1oPve6d4

I couldn't find any relevant bit in the C standard, so I am unsure whether or not this is the expected compiler behavior.
What I know for sure is that there are places in kernel where uninitialized arguments are being passed to functions, but thrown away afterwards:

BUG: KMSAN: uninit-value in walk_component+0x643/0x730 fs/namei.c:2026
 walk_component+0x643/0x730 fs/namei.c:2026
 lookup_last fs/namei.c:2475
 path_lookupat+0x281/0x6f0 fs/namei.c:2499
 filename_lookup+0x250/0x800 fs/namei.c:2528
 kern_path+0x7d/0x3a0 fs/namei.c:2618
 init_stat+0x76/0x143 fs/init.c:132
 clean_path+0x78/0x250 init/initramfs.c:313
 do_name+0x131/0xc02 init/initramfs.c:345
 write_buffer init/initramfs.c:432
 unpack_to_rootfs+0xa79/0xe17 init/initramfs.c:485
 do_populate_rootfs+0x5b/0x40e init/initramfs.c:674
 async_run_entry_fn+0x93/0x400 kernel/async.c:127
 process_one_work+0xb2b/0x13f0 kernel/workqueue.c:2289
 worker_thread+0x1086/0x1d80 kernel/workqueue.c:2436
 kthread+0x31f/0x430 kernel/kthread.c:376
 ret_from_fork+0x1f/0x30 ??:?

Local variable inode created at: 
 walk_component+0x4a/0x730 fs/namei.c:2005
 lookup_last fs/namei.c:2475
 path_lookupat+0x281/0x6f0 fs/namei.c:2499

(this is a report from a more conservative KMSAN version that reports uninits as they are passed to functions)

Apparently such code can be miscompiled by Clang, so the question is whether or not it is legitimate to pass uninitialized data to functions in the kernel? If it is, we probably need to build the kernel without enable_noundef_analysis?

[nathanchance]

I've learned recently that Clang may mark certain function parameters as noundef, and passing uninitialized data in such parameters will be considered an UB (see https://llvm.org/docs/LangRef.html for the definition of noundef).

Moreover, Clang is quite aggressive in assigning noundef and can do that even for parameters that aren't always used: https://godbolt.org/z/s1oPve6d4

Right, this is a result of llvm/llvm-project@1b1c8d8, which also causes a bunch of objtool warnings when at least UBSAN is enabled from what I can tell: #1480.

I couldn't find any relevant bit in the C standard, so I am unsure whether or not this is the expected compiler behavior. What I know for sure is that there are places in kernel where uninitialized arguments are being passed to functions, but thrown away afterwards:

BUG: KMSAN: uninit-value in walk_component+0x643/0x730 fs/namei.c:2026
 walk_component+0x643/0x730 fs/namei.c:2026
 lookup_last fs/namei.c:2475
 path_lookupat+0x281/0x6f0 fs/namei.c:2499
 filename_lookup+0x250/0x800 fs/namei.c:2528
 kern_path+0x7d/0x3a0 fs/namei.c:2618
 init_stat+0x76/0x143 fs/init.c:132
 clean_path+0x78/0x250 init/initramfs.c:313
 do_name+0x131/0xc02 init/initramfs.c:345
 write_buffer init/initramfs.c:432
 unpack_to_rootfs+0xa79/0xe17 init/initramfs.c:485
 do_populate_rootfs+0x5b/0x40e init/initramfs.c:674
 async_run_entry_fn+0x93/0x400 kernel/async.c:127
 process_one_work+0xb2b/0x13f0 kernel/workqueue.c:2289
 worker_thread+0x1086/0x1d80 kernel/workqueue.c:2436
 kthread+0x31f/0x430 kernel/kthread.c:376
 ret_from_fork+0x1f/0x30 ??:?

Local variable inode created at: 
 walk_component+0x4a/0x730 fs/namei.c:2005
 lookup_last fs/namei.c:2475
 path_lookupat+0x281/0x6f0 fs/namei.c:2499

(this is a report from a more conservative KMSAN version that reports uninits as they are passed to functions)

Apparently such code can be miscompiled by Clang, so the question is whether or not it is legitimate to pass uninitialized data to functions in the kernel? If it is, we probably need to build the kernel without enable_noundef_analysis?

I suspect it is a common pattern to pass in an uninitialized variable to a function and have that function initialize it? If not, I would say the kernel should just be fixed but if it is, I guess we should build the kernel with -Xclang -disable-noundef-analysis in that case if there are going to be miscompiles without it.

[eugenis]

We actually implemented this for MSan (the "conservative KMSAN mode" that Alex mentions) initially, and then it turned out that it is useful for optimization, too :)

I suspect it is a common pattern to pass in an uninitialized variable to a function and have that function initialize it?

If that's by-reference, it would be entirely legal and neither optimizer not MSan would have an issue with it.

I guess there is this other pattern where, depending on the value of other arguments or some global state, one of the function arguments is unused. Then folks think its ok to pass undefined bits through that argument. This it not true according to the language standard, and LLVM may miscompile such code, and ("conservative") MSan will scream at you, too.

[ramosian-glider]

This it not true according to the language standard, and LLVM may miscompile such code, and ("conservative") MSan will scream at you, too.

I couldn't find any mentions of this in the C99 or C11 standards. If this is a new requirement that is silently applied to older standards, then the compiler might be misbehaving.

[nathanchance]

I guess there is this other pattern where, depending on the value of other arguments or some global state, one of the function arguments is unused.

Right, I suspect that is the case for the initial report above but I didn't look too closely.

[ramosian-glider]

Right, I suspect that is the case for the initial report above but I didn't look too closely.

Yes, this is the case. Another one is in the Godbolt snippet cited above: https://godbolt.org/z/s1oPve6d4

As far as I understand, neither of the calls to kmalloc_or_not() there can be considered valid if we prohibit passing uninitialized arguments to functions.

[nickdesaulniers]

A common pattern in C code is to have constructor-like init functions.

void init (int *z);

int foo (void) {
  int x;
  init(&x);
  return x;
}

A commonly recurring problematic pattern in the kernel is when init conditionally initializes z; this requires inter-procedural analysis via clang-analyzer; clang's -Wuninitialized machinery is based on intra-procedural control flow.

Pretty sure any use of an unitialized value (such as passing it by value to a function) is UB; we can go dig out the relevant citation if needed. But it sounds to me like the kernel code needs to be fixed. @ramosian-glider do you have a specific line of code we can look at?

[ramosian-glider]

Yes, I have at least the one mentioned above.
If you look at walk_component() in fs/namei.c:

static const char *walk_component(struct nameidata *nd, int flags)
{
	struct dentry *dentry;
	struct inode *inode;
	unsigned seq;
	/*
	 * "." and ".." are special - ".." especially so because it has
	 * to be able to know about the current root directory and
	 * parent relationships.
	 */
	if (unlikely(nd->last_type != LAST_NORM)) {
...
	}
	dentry = lookup_fast(nd, &inode, &seq);
	if (IS_ERR(dentry))
		return ERR_CAST(dentry);
	if (unlikely(!dentry)) {
...
	}
	if (!(flags & WALK_MORE) && nd->depth)
		put_link(nd);
	return step_into(nd, flags, dentry, inode, seq);
}

, we can see that if lookup_fast() fails to initialize inode and seq, then undefined values are passed into step_into().

Looking at lookup_fast() implementation we can see this is quite possible:

static struct dentry *lookup_fast(struct nameidata *nd,
				  struct inode **inode,
			          unsigned *seqp)
{
	struct dentry *dentry, *parent = nd->path.dentry;
	int status = 1;

	/*
	 * Rename seqlock is not required here because in the off chance
	 * of a false negative due to a concurrent rename, the caller is
	 * going to fall back to non-racy lookup.
	 */
	if (nd->flags & LOOKUP_RCU) {
		unsigned seq;
		dentry = __d_lookup_rcu(parent, &nd->last, &seq);
...
		*seqp = seq;
...
	} else {
		dentry = __d_lookup(parent, &nd->last);
		if (unlikely(!dentry))
			return NULL;
		status = d_revalidate(dentry, nd->flags);
	}
	if (unlikely(status <= 0)) {
		if (!status)
			d_invalidate(dentry);
		dput(dentry);
		return ERR_PTR(status);
	}
	return dentry;
}

so there exists at least one path where *seqp and *inode are left intact. The mentioned KMSAN report indicates that path was reached in a working kernel. On the other hand, the same bug is never reported without -fsanitize-memory-param-retval, which means the uninit values are probably never used in practice.

Before starting to chase and fix such issues in the whole kernel, I'd love to better understand whether they are just poor coding practices or cases where the behavior is really undefined.

[nickdesaulniers]

This concrete instance you've found is exactly the abstract problem in the kernel I was referring to.

To me, it's analogous to the problem -fno-delete-null-pointer-checks seeks to solve; if you deref a ptr before a NULL check, then the compiler will drop the NULL check.

I suspect that if you ran make LLVM=1 clang-analyzer, you would get a warning along the lines of garbage values being passed to step_into in the event that lookup_fast failed to initialize it's parameters. That said...

, we can see that if lookup_fast() fails to initialize inode and seq, then undefined values are passed into step_into().

Well, no, looking closer at the context there in the code snippets you pasted, we can see that...

2002 static const char *walk_component(struct nameidata *nd, int flags)              
2003 {                                                                               
...                                                   
2005   struct inode *inode;                                                          
2006   unsigned seq;
...
2017   dentry = lookup_fast(nd, &inode, &seq);                                       
2018   if (IS_ERR(dentry))                                                           
2019     return ERR_CAST(dentry); 
...
2027   return step_into(nd, flags, dentry, inode, seq);                              
2028 }                                                                               
...

while lookup_fast can conditionally assign to its second and third parameter, it will also return ERR_PTR or NULL in the cases where those are uninitialized. So by the time we get to passing them to step_into, they MUST be defined (or noundef in LLVM IR parlance). I suspect we build this code without optimizations enabled, then LLVM will not infer noundef.

Or was there another control flow path that I missed that led to unintialized values being used?

[ramosian-glider]

What I am seeing is that lookup_fast() returns NULL here:

1616 static struct dentry *lookup_fast(struct nameidata *nd,
1617                                   struct inode **inode,
1618                                   unsigned *seqp)
1619 {
1620         struct dentry *dentry, *parent = nd->path.dentry;
1621         int status = 1;
1622 
1623         /*
1624          * Rename seqlock is not required here because in the off chance
1625          * of a false negative due to a concurrent rename, the caller is
1626          * going to fall back to non-racy lookup.
1627          */
1628         if (nd->flags & LOOKUP_RCU) {
1629                 unsigned seq;
1630                 dentry = __d_lookup_rcu(parent, &nd->last, &seq);
1631                 if (unlikely(!dentry)) {
1632                         if (!try_to_unlazy(nd)) 
1633                                 return ERR_PTR(-ECHILD);
1634                         return NULL;
1635                 }

without initializing inode and seq.

As a result, IS_ERR(dentry) is false, so we get into the !dentry branch in walk_component():

2019         if (unlikely(!dentry)) {
2020                 dentry = lookup_slow(&nd->last, nd->path.dentry, nd->flags);
2021                 if (IS_ERR(dentry))
2022                         return ERR_CAST(dentry);
2023         }

, but then lookup_slow() returns some valid non-NULL dentry, so we manage to reach the call of step_into() with inode and seq still being uninitialized.

Pretty sure any use of an unitialized value (such as passing it by value to a function) is UB; we can go dig out the relevant citation if needed.

I would be very interested in seeing such a citation, because I've spent quite a bit of time digging it out with no success.

My understanding is that, despite static analysis may fail to prove that certain value is always initialized within a function, it is still fine to pass it to another function as long as that other function never uses the uninitialized values.

[nickdesaulniers]

Forked off #1653 .

I would be very interested in seeing such a citation, because I've spent quite a bit of time digging it out with no success.

I think we're in agreement; I was referring to use of unconditionally uninitialized memory, you are referring to use of conditionally uninitialized memory.

My understanding is that, despite static analysis may fail to prove that certain value is always initialized within a function, it is still fine to pass it to another function as long as that other function never uses the uninitialized values.

Right, that's what I just asked on https://lore.kernel.org/linux-toolchains/CAKwvOd=C1GC09zobqLK0higE3xPpghWBbB4xujyC8-QDyd_DTQ@mail.gmail.com/:

One thing I'm curious about; if you have an aggregate in C (struct or
array) and don't fully initialize the whole object, just
members/sub-objects, but only use those I assume that's not UB? (Which
is what my maybe_init example does). I think that's fine.

[ramosian-glider]

I think we're in agreement; I was referring to use of unconditionally uninitialized memory, you are referring to use of conditionally uninitialized memory.

But you consider passing uninitialized value to a function a "use", while I don't. Or am I missing something?

I think the list of possible "uses" of uninitialized values in C is more or less limited to branches, array indexing and pointer dereferencing. Passing (even unconditionally) uninitialized values to functions is fine as long as they are not used inside those functions.

[ramosian-glider]

To close the loop, these are the relevant excerpts from the standard cited by Segher Boessenkool:

Since C11, lvalue conversion of an automatic variable that does not have
its address taken is explicitly undefined behaviour (6.3.2.1/2). So in
function "p", both where "c" and where "size" are passed causes UB (so
that executing "p" always causes UB btw).

and Richard Smith:

6.2.4/6: "If an initialization is specified for the object, it is performed each time the declaration or compound literal is reached in the execution of the block; otherwise, the value becomes indeterminate each time the declaration is reached."
3.19.2/1: "indeterminate value: either an unspecified value or a trap representation"
6.2.6.1/5: "Certain object representations need not represent a value of the object type. If the stored value of an object has such a representation and is read by an lvalue expression that does not have character type, the behavior is undefined. If such a representation is produced by a side effect that modifies all or any part of the object by an lvalue expression that does not have character type, the behavior is undefined. [Footnote: Thus, an automatic variable can be initialized to a trap representation without causing undefined behavior, but the value of the variable cannot be used until a proper value is stored in it.] Such a representation is called a trap representation."