Incremental Global Array Initialization in C
| Author | Kevin Nygaard |
| Published | |
Custom memory sections enable incremental initialization of global arrays in C by exploiting the compiler's memory allocation behavior. This reduces boilerplate code, increasing the quality and maintainability of lightweight introspection, function registries, and other self-registration patterns.
Contents
1 Declarators, Initializers, and Expressions
In the C programming language, the top level of a file (ie translation unit) only allows declarations (with optional initializers). This limitation causes boilerplate code, creating unnecessary bugs and maintenance. For example, consider the following lightweight introspection code:
int Foo = 123;
int Bar = 456;
int Baz = 789;
typedef struct { int *Address; char *Name; } var;
var Vars[] = {
{&Foo, "Foo"},
{&Bar, "Bar"},
{&Baz, "Baz"},
}; Three integer variables (Foo, Bar, and Baz) are declared and initialized. var is defined as a structure containing the address of an integer variable (int *) and its name (char *). Then, an array of var structures called Vars is defined and initialized with the variable addresses and their names.
Due to this boilerplate, adding a new variable is an error-prone two step process: first, declare a new variable; second, add it to the array. Eliminating the second step removes the chance for errors and streamlines maintenance; however, a global array is initialized once, and the top level limitation prevents further modifications. For example, consider this proposed solution:
typedef struct { int *Address; char *Name; } var;
var Vars[10];
int VarCount;
#define DefVar(Name) \
int Name; \
Vars[VarCount++] = (var){&Name, #Name}; \
int Name
DefVar(Foo) = 123;
DefVar(Bar) = 456;
DefVar(Baz) = 789; The Vars array and VarCount are declared up front, then with each macro expansion: first, forward declare the Name parameter as an integer variable; second, construct a compound literal with that variable's address along with its string and append it to Vars; third, increment VarCount; fourth, begin the variable declaration of Name, which is completed by an (optional) initializer following the macro.
The resulting syntax – albeit imperfect – is clean and straightforward. However, the Vars[...] = ...; line is an expression, which is forbidden in the top level. The approach is sound, but the language is inadequate. Global arrays simply cannot be incrementally initialized… or can they?
2 Memory, the Compiler, and Implicit Arrays
For efficiency and security, program memory is divided into chunks called segments.1 The program's executable header defines the contents, sizes, and access permissions of these segments. Using this header, the operating system loads the program into memory. Example segments include a read-only segment for constants, a read/write segment for variables, and a read/execute segment for executable code.
Oblivious to the operating system, segments are further divided into chunks called sections. The compiler creates these to group similar objects together, improving locality and memory usage. Examples sections for a read-only segment include a section for strings and a section for all other constants.
During compilation, the compiler analyzes a variable, determines its usage, and appends it to a section; the variables are allocated in the order they are defined. Thus, defining multiple variables of the same type in succession results in a contiguous sequence of identical objects: an array. Therefore, the following explicit array initialization,
int Array[] = {
1,
2,
3,
}; is identical to the implicit array initialization,
int Foo = 1;
int Bar = 2;
int Baz = 3;
with &Foo being equivalent to Array.
However, variables forming an implicit array must meet three requirements: first, they must be initialized; second, they must be allocated to a custom section;2 third, they must be explicitly used.
2.1 Uninitialized Variables
Uninitialized variables – which are implicitly zero-initialized – are reordered to save space. The compiler groups them together, and knowing they are all zero, omits their initial values from the program image.3 Thus, all variables in an implicit array must be initialized to keep them contiguous:int Foo = 1;
int Bar = 0;
int Baz = 3;
Foo, Bar, and Baz are all contiguous, forming a three-element implicit array. Removing the initializer on the second line makes Foo and Baz contiguous, forming a two-element implicit array; Bar, although still initialized to zero, is allocated elsewhere.
2.2 Optimizations and Crowded Sections
The compiler is free to optimize variables into registers, constants, computations, or otherwise remove them from memory, destroying the contiguity of an implicit array. Additionally, global and static variables coexist in the same section, making accidental variable interposition easy to do, and hard to detect. Creating and using a custom section resolves both issues:/* For macOS */
__attribute__((section("info, info"))) int Foo = 3;
/* For Linux */
__attribute__((section("info"))) int Foo = 3;
/* For Windows */
#pragma section("info", read)
__declspec(allocate("info")) int Foo = 3; This places Foo into a custom section named info. macOS' Mach-O format requires both a segment and section name, and Windows requires an explicit section definition before use.
2.3 Unused Variables
The compiler is free to remove unused variables. It assumes they are isolated from one another, each existing in its own address space. Thus, a variable declared but never explicitly referenced is inessential to the program and simply wastes space. The compiler only sees accesses to the first variable of an implicit array; the others are considered unreachable and therefore removable. Adding a compiler directive prevents this optimization:/* For macOS and Linux */
__attribute__((used)) int Foo = 3;
Note, Windows does not perform this optimization on global variables.
Armed with this knowledge of memory and compilers, we return to our original problem with a solution.
3 The Solution
With implicit arrays – and a handful of caveats – we incrementally create a global array. Starting with the originally proposed solution, add a macro to the top, change an expression to a definition, and add some bookends:
/* For macOS */
#define info __attribute__((used, section("info, info")))
/* For Linux */
#define info __attribute__((used, section("info")))
/* For Windows */
#pragma section("info", read)
#define info __declspec(allocate("info"))
/* Shared */
typedef struct { int *Address; char *Name; } var;
#define DefVar(Name) \
int Name; \
info var Name ## Info = {&Name, #Name}; \
int Name
info var BeginVars = {0};
DefVar(Foo) = 123;
DefVar(Bar) = 456;
DefVar(Baz) = 789;
info var EndVars = {0}; The info macro aggregates the compiler directives discussed earlier; used in a variable declaration, it places the variable into a custom section named info. Then, using this macro, DefVar defines a variable and initializes it with metadata. Note, ## is the preprocessor's token paste operator, which combines the Name parameter and "Info" into a single entity (ie FooInfo, BarInfo, etc). Defining the variables with DefVar incrementally builds the Vars array inside the info section. The bookend variables, BeginVars and EndVars, provide consistent handles for array access and size calculation: they are independent of the array's contents.
Adding new variables is now a trivial process: just add the variable. This solution removes the boilerplate, making the code more reliable and maintainable.
4 Other Uses and Limitations
This article implements lightweight variable introspection, but the technique is equally powerful for function introspection. For example, adding commands to an interpreter, adding test cases to unit test suites, and registering setup/teardown routines. These tasks define a function, then register it with some database, coordinator, or registry. With implicit arrays, functions can auto-register themselves when defined:
DefCmd(Print) { printf("%s", Arg); }
DefTest(TestRng) { CheckEq(Random(), 42); }
DefInit(InitBuf) { Buf = malloc(256); }
DefFree(FreeBuf) { free(Buf); } Another use case is building heterogeneous arrays – arrays containing more than one type. Unlike an array of unions, each element only uses the spaces it needs; union elements are uniformly sized, wasting space.
While useful, implicit arrays rely on implementation-specific behavior:4 a compiler change in the future may break this technique (albeit unlikely). Similarly, a target system may not support sections, or may allocate variables non-linearly.
In terms of complexity, this technique can be pressed too hard into service, creating more problems than it solves. Beyond a certain point, a proper code generator or pre-pass step is more maintainable than wrangling macros and compiler quirks. As with many things, prudence is advised.
I hope this article has helped in understanding and seeing the potential of implicit arrays. Feedback and corrections are welcome via email. ✚
Footnotes
- ↑ Segments are few in number and large in size; each is a multiple of the page size (4 kB) and page aligned. mmap(2) allocates segments at runtime.
- ↑ This isn't a strict requirement, but a good rule of thumb. In dire situations, you can implement implicit arrays in the default section… if you are careful.
- ↑ For this reason, leave global variables uninitialized whenever possible for a smaller program image and a faster startup time. Initialized variables must be copied into memory before the program executes; uninitialized variables copy nothing because the kernel automatically zeros out program memory.
- ↑ By the C specification, its actually undefined behavior, giving the compiler license to kill – usually, it does something sensible. Technically, we are accessing an array of size 1 outside its bounds. From the C99 Standard, ISO/IEC 9899:1999, §6.5.6: "If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary
* operator that is evaluated."
See Also
Further Resources