GCC *is* wonderful: a better ARRAY_SIZE macro

One of the best patch submissions I’ve ever seen is Rusty Russell’s change to Linux’s ARRAY_SIZE macro. For those that haven’t programmed much in C, I’ll briefly explain that the language provides no built-in construct for determining the number of elements in an array. However, it does allow one to determine the size of an array in bytes (well, chars, actually) and also the size of the array’s elements (also in chars) and you can then find the number of array elements by dividing the former by the latter.

This works reasonably well — well enough that to this day, C still does not include a language construct for determining array element counts. However, there’s disagreement as to what to call the macro for doing this, with Unix programmers typically preferring ARRAY_SIZE, Windows programmers sometimes preferring DIM, and some programmers preferring NELEMS or something else entirely. What’s worse, sometimes a macro isn't used at all, leaving the calculation open-coded. Occasionally, when an open-coded calculation is used, the element size is written as a literal value instead of using C’s sizeof keyword, or the element type is explicitly specified instead of letting the compiler work that out itself.

Okay, so maybe that sounds a little cumbersome but not especially bad, right? Actually, yes — the ARRAY_SIZE macro as conventionally defined does not provide good type-safety and the open-coded approach is more fragile, more verbose and provides no improvement in type-safety.

Type-safety of the conventional ARRAY_SIZE macro

The macro is usually defined as follows:

#define ARRAY_SIZE(array) \
    (sizeof(array) / sizeof(*array))

or:

#define ARRAY_SIZE(array) \
    (sizeof(array) / sizeof(array[0]))

As C uses the same syntax for pointer dereferencing and the indexing of arrays, these are equivalent. The macro would be used as follows:

int i;
int a[100];

for (i = 0; i < ARRAY_SIZE(a); i++) {
    a[i] = i;
}

Some C programmers presumably feel that the version of the definition that uses ‘[0]’ better conveys that the parameter to the macro is to be an array. On the contrary, I feel that ‘*’ better conveys that the parameter could be a pointer. Of course, if the parameter is a pointer, the calculation is unlikely to produce the desired value. For example:

int i;
int a[100];
int *p = a;

for (i = 0; i < ARRAY_SIZE(p); i++) { /* WRONG */
    a[i] = i;
}

ARRAY_SIZE(p) expands to sizeof(p) / sizeof(*p). Although sizeof(*p) provides the expected value, sizeof(p) is equivalent to sizeof(int *), and not sizeof(int[10]) as intended. On most general-purpose platforms in use today, the size of any pointer type will be either four chars (for 32-bit systems) or eight chars (for 64-bit systems). Depending on the array’s element size, the result of the integer division will be either 8, 4, 2, 1 or 0, regardless of the number of elements. In the above example, the vast majority of the elements in the array will be left uninitialised.

Competent C programmers are therefore somewhat careful to ensure that they never use ARRAY_SIZE directly with a pointer variable, and are also careful in cases where they might legitimately use the ARRAY_SIZE macro to get the size of an array that is the member of a structure that is referenced through a pointer, as shown:

int i;
struct foo {
    int a[100];
} bar;
struct foo *p = &bar;

for (i = 0; i < ARRAY_SIZE(p->a); i++) {
    p->a[i] = i;
}

It’s also worth considering the fragility of the open-coded approach, but only because it’s still frightfully common. Here, if the array were to change from an array of int to an array of long int, we would need to update the open-coded calculation to suit:

int i;
int a[100];

for (i = 0; i < sizeof(a) / sizeof(int); i++) { /* UGH */
    a[i] = i;
}

There’s simply no reason to burden the programmer with this task, especially when once every so often a failure to do this will result in a severe bug.

One danger of the example above, where the array member of p->a is used, is that if the struct were to be changed to include a pointer, instead of an array, the code would still compile without modification. Note that open-coding of the calculation does nothing to prevent this.

Rusty Russell’s patch to Linux’s ARRAY_SIZE macro

There are at least three awesome things about Rusty’s patch. These are:

1. The functionality. With this version of ARRAY_SIZE, one never needs to worry about accidentally taking the array size of a pointer, as any code doing this would quite simply fail to compile when using a sufficiently recent version of GCC (such as GCC 3.1, released on 27th July 2002) or Clang. The error message is somewhat opaque but it’s better than the bug that would otherwise result.
2. The subject: ‘[PATCH] Use more gcc extensions in the Linux headers’. It’s brilliantly attention-getting, but also conveys quite well that the submission was more of a request for comment than anything else, at that early stage. There’s a sense of humour about this which is wonderfully disarming, and what followed was a short discussion and a far tidier patch which was accepted soon afterwards. The follow-up patch addressing the lack of documentation is worth a quick mention, too: it simply added the comment /* GCC is awesome. */ — of course, this too was only intended a bit of light humour, and the eventual change provides a far better explanation.
3. The directness of the original submission. Rather than to attempt to explain it, Rusty simply leaves it as a challenge to the reader! I wouldn’t suggest accepting code in this form, but I found it interesting to read his original patch and to make sense of the change. Oddly, it was probably easier than it would have been to make sense of anybody else’s explanation, or to look at the eventual implementation of the __must_be_array macro.

Rusty’s version of the ARRAY_SIZE macro, with the added ‘documentation’ (and with some whitespace changes), is as follows:

/* GCC is awesome. */
#define ARRAY_SIZE(arr) \
    (sizeof(arr) / sizeof((arr)[0]) \
     + sizeof(typeof(int[1 - 2 * \
           !!__builtin_types_compatible_p(typeof(arr), \
                 typeof(&arr[0]))])) * 0)

I won’t explain this in full, so as to provide some of the same challenge to you, except to say:

• The initial division is the same as before, the addend must equal zero to leave this behaviour unchanged.
• The type of the addend must be size_t (as provided by sizeof) for all expansions of the macro to retain the type of size_t.
• typeof(int[-1]) is an invalid expression under GCC (as is ‘sizeof(struct { int : -1; })’, upon which current kernels rely).
• typeof and __builtin_types_compatible_p are both GCC extensions, as you may have guessed!

Usable ARRAY_SIZE macro with type-safety under GCC

My only question: why should we have to go to so much trouble? Well, I’m not sure how far fair-use extends (as these macros are QEMU and Linux, which are distributed under the GPLv2) and IANAL, but this may help:

#if defined(__GNUC__) && defined(__GNUC_MINOR__)
 #define GNUC_VERSION \
     (__GNUC__ << 16) + __GNUC_MINOR__
 #define GNUC_PREREQ(maj, min) \
     (GNUC_VERSION >= ((maj) << 16) + (min))
#else
 #define GNUC_PREREQ(maj, min) 0
#endif

#define BUILD_BUG_ON_ZERO(e) \
    (sizeof(struct { int:-!!(e)*1234; }))

#if GNUC_PREREQ(3, 1)
 #define SAME_TYPE(a, b) \
     __builtin_types_compatible_p(typeof(a), typeof(b))
 #define MUST_BE_ARRAY(a) \
     BUILD_BUG_ON_ZERO(SAME_TYPE((a), &(*a)))
#else
 #define MUST_BE_ARRAY(a) \
     BUILD_BUG_ON_ZERO(sizeof(a) % sizeof(*a))
#endif

#ifdef __cplusplus
 template <typename T, size_t N>
 char ( &ARRAY_SIZE_HELPER( T (&array)[N] ))[N];
 #define ARRAY_SIZE( array ) \
      (sizeof( ARRAY_SIZE_HELPER( array ) ))
#else
 #define ARRAY_SIZE(a) ( \
     (sizeof(a) / sizeof(*a)) \
     + MUST_BE_ARRAY(a))
#endif

With this version, if you take the ARRAY_SIZE of a pointer, GCC 4.9 will give you the error message:

error: negative width in bit-field ‘<anonymous>’

This will also work for Clang (as it curiously defines __GNUC__ and __GNUC_MINOR__):

error: anonymous bit-field has negative width (-1234)

The magic value of −1234 is intended as something of a give-away as to the cause of the error, should it occur, assuming that some poor soul will be shown this line on its own without the subsequent lines of output that backtrack through successive layers of macro expansion. At least this way, you would have something to grep for!

I’ve added the nice hack from Chromium’s version of the macro that will provide somewhat patchy checking for compilers without __builtin_types_compatible_p or typeof. It may be worth noting here that the approach Chromium takes is to use ‘0[a]’ instead of ‘*a’, exploiting the equivalence between pointer dereferencing and array indexing in C (a[i] is equivalent to *(a+i)and therefore i[a]) but catching operator overloading (using an operator[] method to handle subscripting for a class) as well.

Instead of adopting Chromium’s trick, I’ve also included a portable version for C++ in the above, although this has the disadvantage that it cannot be used with types defined within a function.

What would actually make sense would be for C and C++ (and Objective C, assuming that’s also affected... and let’s just pretend Objective C++ doesn’t exist) to be extended to include a keyword or some syntax for this. In lieu of any provision for this in the standards, I feel that it would make good sense for compilers to add this as an extension. In GCC and Clang, I imagine a __builtin_arraysize function would probably make a whole lot of sense. Yes, I know things are a lot better in C++, but there may still be times when you can’t escape from its C roots, such as when writing language bindings, or when using a library written in C.

Really, this should have been fixed thirty years ago!