The joy of max()

[Posted March 28, 2018 by corbet]

LWN recently looked at the kernel's max() macro and the effort put into ensuring that it would evaluate to a "constant expression" as seen by the compiler. After a number of iterations, it would appear that the problem has been solved. For your reading pleasure, here is the new form of max(), extracted from the patch posted by Kees Cook:

    #define __typecheck(x, y) \
		(!!(sizeof((typeof(x)*)1 == (typeof(y)*)1)))

    #define __is_constant(x) \
	(sizeof(int) == sizeof(*(1 ? ((void*)((long)(x) * 0l)) : (int*)1)))

    #define __no_side_effects(x, y) \
		(__is_constant(x) && __is_constant(y))

    #define __safe_cmp(x, y) \
		(__typecheck(x, y) && __no_side_effects(x, y))

    #define __cmp(x, y, op)	((x) op (y) ? (x) : (y))

    #define __cmp_once(x, y, op) ({	\
		typeof(x) __x = (x);	\
		typeof(y) __y = (y);	\
		__cmp(__x, __y, op); })

    #define __careful_cmp(x, y, op)			\
		__builtin_choose_expr(__safe_cmp(x, y),	\
				      __cmp(x, y, op), __cmp_once(x, y, op))
 
    #define max(x, y)	__careful_cmp(x, y, >)

The above definitions should, of course, be immediately obvious to any LWN reader. For those who want an extra hint or two, though, the patch posting includes a few explanatory comments.

(Log in to post comments)

The joy of max()

Posted Mar 29, 2018 8:46 UTC (Thu) by flewellyn (subscriber, #5047) [Link]

For a patch that led the maintainer to say "Cthulhu fhtagn!", this is remarkably sane and readable. At least, by the standards of C macros.

The joy of max()

Posted Mar 30, 2018 22:26 UTC (Fri) by simcop2387 (subscriber, #101710) [Link]

Remarkably readable, but I could not begin to explain how it works fully, or why some things were chosen the way they were.

The joy of max()

Posted Mar 31, 2018 1:50 UTC (Sat) by lambda (subscriber, #40735) [Link]

If you follow the thread, you'll find that the "why some things were chosen the way they were" is a combination of some very careful reading of the C standard, some clever usage of some obscure rules of the difference in type between (int *) 0 and (int *) 1 (the first is actually of type void *), along with a lot of testing out what worked and what didn't with different versions of GCC on godbolt.org because a lot of it depended on exactly how clever the compiler constant expression evaluator was and how that interacted with type checking.

In other words, why some things were done the way they were is just that different closely related things were tried until a version could be found that did the right thing on a broad enough range of compiler versions. This isn't likely to be highly portable C code; but it works on enough versions of GCC that it can be built on the GCC included in the oldest supported versions of various major Linux distros.

The joy of max()

Posted Apr 5, 2018 14:35 UTC (Thu) by HelloWorld (guest, #56129) [Link]

That means it's _not_ readable.

The joy of max()

Posted Mar 29, 2018 14:14 UTC (Thu) by bfields (subscriber, #19510) [Link]

That does deserve some kind of prize. What exactly I'm not sure.

The joy of max()

Posted Mar 29, 2018 16:20 UTC (Thu) by smitty_one_each (subscriber, #28989) [Link]

A free Duff Device. https://en.wikipedia.org/wiki/Duff's_device

The joy of max()

Posted Mar 29, 2018 19:56 UTC (Thu) by jwilk (subscriber, #63328) [Link]

Fixed link: https://en.wikipedia.org/wiki/Duff%27s_device

Credits to: Martin Uecker

Posted Mar 29, 2018 20:52 UTC (Thu) by david.a.wheeler (guest, #72896) [Link]

The main approach appears to have been created by Martin Uecker.

I think Linus Torvalds said it best: "That is either genius, or a seriously diseased mind. I can't quite tell which." - https://lkml.org/lkml/2018/3/20/845

Credits to: Martin Uecker

Posted Mar 29, 2018 21:32 UTC (Thu) by gerdesj (subscriber, #5446) [Link]

I'm no expert but as an interested civilian, I can appreciate how most (OK some) of it hangs together, picking its way daintily around gotchas and builds up to a crescendo, drops the answer, takes a quick bow, saunters off stage left. The curtain drops to thunderous applause.

It is clearly a work of genius, with a touch of "bwou HA HA Ha ha haaaaa".

Credits to: Martin Uecker

Posted Mar 30, 2018 20:30 UTC (Fri) by nix (subscriber, #2304) [Link]

Exploiting that particular obscure aspect of the semantics of ternary conditionals is rare enough that I had to stare at the screen for five minutes to figure out what on earth that ternary was doing.

Credits to: Martin Uecker

Posted Mar 31, 2018 1:35 UTC (Sat) by gerdesj (subscriber, #5446) [Link]

"... is rare enough that I had to stare at the screen for five minutes to figure out what on earth that ternary was doing."

Now you now what it is like reading a paper of a mathematic or similar proof. It seems to me that IT is gradually growing up.

Credits to: Martin Uecker

Posted Apr 1, 2018 17:04 UTC (Sun) by nix (subscriber, #2304) [Link]

The feeling is more or less exactly the same, and has happened to me many times in the past with similar standard-subtlety. You can't really put language standards in the same bin as ineffable proof Truth though.

The joy of max()

Posted Mar 30, 2018 18:14 UTC (Fri) by flussence (subscriber, #85566) [Link]

It's not immediately obvious to me (because I'm not a C programmer), but it does kind of make sense after staring at it for a few minutes, and reading Linus' explanation of that one bit. It reads a bit like Haskell code, but with human-readable function names.

The joy of max()

Posted Mar 30, 2018 22:03 UTC (Fri) by tbodt (subscriber, #120821) [Link]

What I want to know is what's wrong with __builtin_constant_p.

The joy of max()

Posted Mar 30, 2018 23:17 UTC (Fri) by tux1968 (guest, #58956) [Link]

Looks like it caused problems with older compilers.

https://lwn.net/Articles/749064/

The joy of max()

Posted Mar 30, 2018 22:45 UTC (Fri) by adobriyan (subscriber, #30858) [Link]

And anecdote says: and these people tell me to stop picking nose.

The joy of max()

Posted Mar 30, 2018 23:38 UTC (Fri) by adobriyan (subscriber, #30858) [Link]

This horror probably kills my wet dream of deleting many "min_t" usages:

size_t a = min_t(size_t, PAGE_SIZE, count);

please remind me why C is so much better than C++?

Posted Apr 5, 2018 14:29 UTC (Thu) by HelloWorld (guest, #56129) [Link]

template< class T >
constexpr const T& max( const T& a, const T& b ) {
return a > b ? a : b;
}

Done.

please remind me why C is so much better than C++?

Posted Apr 7, 2018 21:19 UTC (Sat) by rleigh (guest, #14622) [Link]

I was going to write exactly this (maybe minus the references since we're dealing with integers). While some may criticise C++ for being "more complex" than C, there's a lot of stuff which becomes trivially simple when you don't have to work around all the weaknesses of C with horrible macros.

please remind me why C is so much better than C++?

Posted Apr 8, 2018 11:28 UTC (Sun) by HelloWorld (guest, #56129) [Link]

> I was going to write exactly this (maybe minus the references since we're dealing with integers).
That's the definition from the standard library (<algorithm> header), so you wouldn't really have to write it at all. It also makes sense, because this way the types don't need to be copy-constructible and the compiler will optimise the references away in most cases when dealing with simple types.