Here is a real-world example on how one could begin to implement this.
Note: This is not application-ready code. I wrote this from scratch, and as such, should only be considered as a proof-of-concept; something one would use as a basis for a discussion in a development team. This version does not use a proper C parser, but assumes certain conventions used in the C source.
All of the files included in this post are licensed under CC0, i.e. dedicated to public domain. Remember, however, that there are no guarantees: if it breaks or breaks something else, don't blame me.
Essentially, we use a Bash+Awk script to generate a C program, that when compiled and run, generates a hash table with precalculated data, and a member_offset() function one can use to find member offsets of structure types, with structure type and member name given as strings.
For illustration, this is a complete working example, including a Makefile.
File mytypes.h contains the types we are interested in:
#include <stdlib.h>
struct type1 {
char one, two[2];
float three;
int (*callback)(const char *, void *, size_t);
} __attribute__((__packed__));
struct type2 {
char four;
struct type1 five;
int six, seven[3];
};
You don't need to stuff the types into a single header file; you only need to edit the Makefile if you have them in different files. One requirement, however, is that all types are included in header files, that can be #include'd in the intermediate C generator file, compiled and run at build time only.
For illustration, we have a main.c that lets user specify struct type and member name on the command line, with the offset printed to standard output:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
extern size_t member_offset(const char *type, const char *name, const size_t not_found);
int main(int argc, char *argv[])
{
int arg;
size_t offset;
if (argc < 3 || !(argc & 1) || !strcmp(argv[1], "-h") || !strcmp(argv[1], "--help")) {
fprintf(stderr, "\n");
fprintf(stderr, "Usage: %s [ -h | --help ]\n", argv[0]);
fprintf(stderr, " %s TYPE NAME [ TYPE NAME ... ]\n", argv[0]);
fprintf(stderr, "\n");
return EXIT_SUCCESS;
}
for (arg = 1; arg < argc - 1; arg += 2) {
offset = member_offset(argv[arg], argv[arg + 1], ~(size_t)0);
if (errno) {
fprintf(stderr, "struct %s unknown, or has no member %s.\n", argv[arg], argv[arg + 1]);
return EXIT_FAILURE;
}
printf("struct %s has member %s at offset %zu.\n", argv[arg], argv[arg + 1], offset);
fflush(stdout);
}
return EXIT_SUCCESS;
}
To build the project, we use a Makefile. Note that the indents are Tabs, not spaces; make is picky that way.
CC := gcc
CFLAGS := -Wall -O2
LDFLAGS :=
.PHONY: all clean
all: clean example
clean:
rm -f *.o example member-offset.c member-offset-generator.c member-offset-generator
member-offset.c: mytypes.h
rm -f $@ member-offset-generator member-offset-generator.c
./member-offset-generator.bash mytypes.h:type1 mytypes.h:type2 > member-offset-generator.c
$(CC) $(CFLAGS) member-offset-generator.c $(LDFLAGS) -o member-offset-generator
./member-offset-generator > $@
rm -f member-offset-generator member-offset-generator.c
%.o: %.c
$(CC) $(CFLAGS) -c $^
example: member-offset.o main.c
$(CC) $(CFLAGS) $^ $(LDFLAGS) -o $@
Note the member-offset.c rule above. It refers to the autogenerated C source file, that will contain the member_offset() function. It is recompiled if it does not exist yet, and also whenever mytypes.h is modified.
The command ./member-offset-generator.bash mytypes.h:type1 mytypes.h:type2 > member-offset-generator.c uses the fourth file not shown yet (see further below), to examine mytypes.h, and include struct type1 and struct type2 in the type database hash tables. The output is member-offset-generator.c, a C program that when compiled and run, generates the C code we actually want. It might be better to split this rule into separate rules, but for now, I made it automatically compile and run member-offset-generator.c, and delete it (as it is only needed to output member-offset.c once).
The shell script that generates that intermediate C program, member-offset-generator.bash, is pretty complicated:
#!/bin/bash
export LANG=C LC_ALL=C
[ -n "$CC" ] || export CC="gcc"
[ -n "$CFLAGS" ] || export CFLAGS="-Wall -O2"
if [ $# -lt 1 ] || [ "$1" = "-h" ] || [ "$1" = "--help" ]; then
exec >&2
printf '\n'
printf 'Usage: %s [ -h | --help ]\n' "$0"
printf ' %s HEADER[:TYPE] ...\n' "$0"
printf '\n'
printf 'This script autogenerates a C program, that when run,\n'
printf 'emits a C implementation of function member_offset()\n'
printf 'which returns the offset of "member" within type "struct type".\n'
printf '\n'
printf 'The generated C program includes all HEADER files,\n'
printf 'but each one only once. Only the specified struct types\n'
printf 'will be supported by the final function.\n'
printf '\n'
exit 1
fi
function hash_of_function() {
sed -e 's| ||' << END
/* DJB2 xor hash, http://www.cse.yorku.ca/~oz/hash.html */
size_t hash_of(const void *data, const size_t size)
{
const unsigned char *p = (const unsigned char *)data;
const unsigned char *const q = (const unsigned char *)data + size;
size_t h = 5381;
while (p < q)
h = ((h << 5) + h) ^ (*(p++));
return h;
}
END
}
# Emit all headers as includes, but each one only once.
printf '%s\n' "$@" | awk \
'BEGIN {
RS="\n"
FS=":"
split("", seen)
printf "#include <stdlib.h>\n"
printf "#include <stddef.h>\n"
printf "#include <string.h>\n"
printf "#include <stdio.h>\n"
seen["stdlib.h"] = 1
seen["stddef.h"] = 1
seen["string.h"] = 1
seen["stdio.h"] = 1
}
{
header = $1
sub(/^[<"]/, "", header)
sub(/[>"]$/, "", header)
if (length(header) > 0 && !(header in seen)) {
seen[header] = 1
if (substr($1, 1, 1) == "<")
printf "#include <%s>\n", header
else
printf "#include \"%s\"\n", header
}
}'
# emit the hash function as a string.
printf '\nstatic const char hash_of_def[] =\n'
hash_of_function | sed -e 's|\\|\\\\|g; s|"|\\"|g; s|^| "|g; s|[\t\v\f ]*$|\\n"|g'
printf ' ;\n\n'
# and the hash function itself.
hash_of_function
# emit structures and code used by the generator itself.
sed -e 's|^ ||' <<END
struct type_member_list {
struct type_member_list *next;
size_t offset;
size_t hash;
size_t namelen;
char name[];
};
struct type_list {
struct type_list *next;
struct type_member_list *members;
size_t hash;
size_t slots;
size_t typelen;
char type[];
};
static size_t type_list_size(const struct type_list *list)
{
size_t result = 0;
while (list) {
++result;
list = list->next;
}
return result;
}
static size_t type_member_list_size(const struct type_member_list *list)
{
size_t result = 0;
while (list) {
++result;
list = list->next;
}
return result;
}
static struct type_list *types = NULL;
static void add_type_member(const char *type, const char *name, const size_t offset)
{
const size_t typelen = (type) ? strlen(type) : 0;
const size_t namelen = (name) ? strlen(name) : 0;
struct type_list *list = NULL, *temp;
struct type_member_list *member;
if (!typelen || !namelen) {
if (!typelen)
fprintf(stderr, "Error: add_type_member() called with empty type.\n");
if (!namelen)
fprintf(stderr, "Error: add_type_member() called with empty name.\n");
exit(EXIT_FAILURE);
}
/* Find the list for the specified type. */
for (temp = types; temp != NULL; temp = temp->next)
if (temp->typelen == typelen && !strcmp(temp->type, type)) {
list = temp;
break;
}
/* If this is a new type, create a new list. */
if (!list) {
list = malloc(sizeof (struct type_list) + typelen + 1);
if (!list) {
fprintf(stderr, "Error: Out of memory.\n");
exit(EXIT_FAILURE);
}
memcpy(list->type, type, typelen);
list->type[typelen] = '\0';
list->typelen = typelen;
list->hash = hash_of(type, typelen);
list->slots = 0;
list->members = NULL;
/* Prepend to global types list. */
list->next = types;
types = list;
}
/* Create a new member. */
member = malloc(sizeof (struct type_member_list) + namelen + 1);
if (!member) {
fprintf(stderr, "Error: Out of memory.\n");
exit(EXIT_FAILURE);
}
memcpy(member->name, name, namelen);
member->name[namelen] = '\0';
member->namelen = namelen;
member->hash = hash_of(name, namelen);
member->offset = offset;
/* Prepend to member list. */
member->next = list->members;
list->members = member;
}
void add_types_and_members(void)
{
END
ignorefirst=$'<"'
ignorelast=$'>"'
# Extract the member names from each structure.
for pair in "$@"; do
name="${pair#*:}"
[ ":$name" = ":$pair" ] && continue
[ -n "$name" ] || continue
file="${pair%%:*}"
file="${file#[$ignorefirst]}"
file="${file%[$ignorelast]}"
$CC $CFLAGS -P -E "$file" | \
sed -e '/#/ d' | tr -s '\t\n\v\f\r ' ' ' | \
sed -e 's|\(struct [^ ]*\) {|\n\1 {\n|g; s|}|\n}\n|g; s| *;|\n|g; s|)([^)]*)||g' | \
awk -v name="$name" \
'BEGIN {
RS = " *\n"
FS = " *,"
split("", members)
}
$0 == ("struct " name " {") {
inside = 1
next
}
$0 == "}" {
inside = 0
next
}
inside {
for (i = 1; i <= NF; i++) {
member = $i
sub(/\[[^\[\]]*\]/, "", member)
sub(/^.*[ \*(]/, "", member)
if (!(member in members))
members[member] = member
}
}
END {
for (member in members)
printf " add_type_member(\"%s\", \"%s\", offsetof(struct %s, %s));\n", name, member, name, member
}' || exit 1
done
# emit the rest of the generator code.
sed -e 's|^ ||' <<END
}
size_t type_slots(struct type_list *list)
{
const size_t size = type_list_size(list);
const size_t max_slots = 4 * size + 1;
size_t slots = size;
size_t *used, i, n;
struct type_list *item;
used = malloc(max_slots * sizeof used[0]);
if (!used) {
fprintf(stderr, "Error: Out of memory.\n");
exit(EXIT_FAILURE);
}
while (1) {
if (slots >= max_slots) {
fprintf(stderr, "Error: Weak hash function; hash table grows too large.\n");
fprintf(stderr, " (Need more than %zu slots for %zu data entries.)\n", max_slots, size);
exit(EXIT_FAILURE);
}
for (i = 0; i < slots; i++)
used[i] = 0;
for (item = list; item != NULL; item = item->next)
++used[item->hash % slots];
n = used[0];
for (i = 1; i < slots; i++)
if (used[i] > n)
n = used[i];
if (n <= 1) {
free(used);
return slots;
}
slots++;
}
}
size_t generate_type(const char *type, struct type_member_list *list, const size_t size)
{
/* Maximum size for current hash table. */
const size_t max_slots = 4*size + 1;
size_t slots = size;
size_t *used, i, n;
struct type_member_list *item;
if (size < 1)
return 0;
used = malloc(max_slots * sizeof used[0]);
if (!used) {
fprintf(stderr, "Error: Out of memory.\n");
exit(EXIT_FAILURE);
}
while (1) {
if (slots >= max_slots) {
fprintf(stderr, "Error: Weak hash function; hash table grows too large.\n");
fprintf(stderr, " (Need more than %zu slots for %zu data entries.)\n", max_slots, size);
exit(EXIT_FAILURE);
}
/* Clear slot use counts. */
for (i = 0; i < slots; i++)
used[i] = 0;
/* Count slot occupancies. */
for (item = list; item != NULL; item = item->next)
++used[item->hash % slots];
/* Find the maximum slot occupancy. */
n = used[0];
for (i = 1; i < slots; i++)
if (used[i] > n)
n = used[i];
/* Suitable size? */
if (n <= 1)
break;
/* Try a larger hash table, then. */
slots++;
}
free(used);
/* Print out the contents of this hash table. */
printf("static const struct member struct_%s_members[%zu] = {\n", type, slots);
for (i = 0; i < slots; i++) {
for (item = list; item != NULL; item = item->next)
if (item->hash % slots == i)
break;
if (item) {
printf(" { .offset = %zu,\n", item->offset);
printf(" .hash = %zu,\n", item->hash);
printf(" .namelen = %zu,\n", item->namelen);
printf(" .name = \"%s\" },\n", item->name);
} else {
printf(" { .offset = 0,\n");
printf(" .hash = 0,\n");
printf(" .namelen = 0,\n");
printf(" .name = NULL },\n");
}
}
printf("};\n\n");
return slots;
}
int main(void)
{
struct type_list *list;
size_t main_slots, i;
add_types_and_members();
printf("#include <stdlib.h>\n");
printf("#include <string.h>\n");
printf("#include <errno.h>\n");
printf("\n");
printf("struct member {\n");
printf(" const size_t offset;\n");
printf(" const size_t hash;\n");
printf(" const size_t namelen;\n");
printf(" const char *const name;\n");
printf("};\n");
printf("\n");
printf("struct type {\n");
printf(" const size_t hash;\n");
printf(" const size_t namelen;\n");
printf(" const size_t members;\n");
printf(" const struct member *const member;\n");
printf(" const char *const name;\n");
printf("};\n");
printf("\n");
printf("%s\n", hash_of_def);
printf("\n");
for (list = types; list != NULL; list = list->next)
list->slots = generate_type(list->type, list->members, type_member_list_size(list->members));
main_slots = type_slots(types);
printf("static const size_t num_types = %zu;\n", main_slots);
printf("static const struct type types[%zu] = {\n", main_slots);
for (i = 0; i < main_slots; i++) {
for (list = types; list != NULL; list = list->next)
if (list->hash % main_slots == i)
break;
if (list) {
printf(" { .hash = %zuUL,\n", list->hash);
printf(" .namelen = %zu,\n", list->typelen);
printf(" .members = %zu,\n", list->slots);
printf(" .member = struct_%s_members,\n", list->type);
printf(" .name = \"%s\" },\n", list->type);
} else {
printf(" { .hash = 0,\n");
printf(" .namelen = 0,\n");
printf(" .members = 0,\n");
printf(" .member = NULL,\n");
printf(" .name = NULL },\n");
}
}
printf("};\n");
printf("\n");
printf("size_t member_offset(const char *type, const char *name, const size_t not_found)\n");
printf("{\n");
printf(" const size_t typelen = (type) ? strlen(type) : 0;\n");
printf(" const size_t namelen = (name) ? strlen(name) : 0;\n");
printf("\n");
printf(" if (typelen > 0 && namelen > 0) {\n");
printf(" const size_t typehash = hash_of(type, typelen);\n");
printf(" const size_t t = typehash %% num_types;\n");
printf(" if (types[t].hash == typehash &&\n");
printf(" types[t].namelen == typelen &&\n");
printf(" !strcmp(types[t].name, type)) {\n");
printf(" const size_t namehash = hash_of(name, namelen);\n");
printf(" const struct member *const member = types[t].member + (namehash %% types[t].members);\n");
printf(" if (member->hash == namehash &&\n");
printf(" member->namelen == namelen &&\n");
printf(" !strcmp(member->name, name)) {\n");
printf(" errno = 0;\n");
printf(" return member->offset;\n");
printf(" }\n");
printf(" }\n");
printf(" }\n");
printf(" errno = ENOENT;\n");
printf(" return not_found;\n");
printf("}\n\n");
return EXIT_SUCCESS;
}
END
This version uses djb2 xor hash function. If you use some other one, write it in C after the sed ... <<END line, ending with END at the start of the line, in the hash_of_function Bash function. (The sed is there just to remove eight spaces of indentation, making the script slightly easier to read.) It is fast, and simple. Whether it suffices for any real world use cases, I don't know; for some test header files I threw at it, it worked just fine.
Both the known structure types, and the members of each known structure type, are stored in hash tables. Since the entries are small, and this is done for performance gains, the hash tables have at most one entry per hash table slot, with some empty slots. This means at most two probes (one probe per tble) per lookup. The intermediate C program searches for the smallest size (number of slots) that puts at most one type or member per entry, so that simple arrays can be used. This yields constant time ($O(1)$) complexity for the hash table search. Because we do need to calculate the hashes from the two supplied strings, technically the time complexity depends on their lengths. Which means, you do need to use a fast hash function; the hash function does not need to be perfect or cryptographically secure.
The one probe to each hash table first compares the hash, then the string length, and finally the string itself, to ensure no false matches. This means that when a match is found, exactly two strcmp()s are made.
If you know the function will never be called to find the offset of a non-existent member, or with a non-existent type, you can safely omit the strcmp() checks.
You can examine the generated intermediate program by running
./member-offset-generator.bash mytypes.h:type1 mytypes.h:type2 | less
As you probably have noticed at this point, writing a C program that generates C code is .. complicated; and that writing a script that generates a C program that generates C code is .. typically not worth the maintenance effort. However, it is definitely doable, although there is a high risk that maintaining the script requires more effort than the generated code is worth. Be aware of this risk.
The default action in the Makefile (when you run make) is the same as make clean example. If you save all the above to their respective files, and then run
make
you should see something like
rm -f *.o example member-offset.c member-offset-generator.c member-offset-generator
rm -f member-offset.c member-offset-generator member-offset-generator.c
./member-offset-generator.bash mytypes.h:type1 mytypes.h:type2 > member-offset-generator.c
gcc -Wall -O2 member-offset-generator.c -o member-offset-generator
./member-offset-generator > member-offset.c
rm -f member-offset-generator member-offset-generator.c
gcc -Wall -O2 -c member-offset.c
gcc member-offset.o main.c -o example
because make outputs the commands it runs, and I didn't hide any of them (by prepending the corresponding command with @).
Then, if you run
./example type1 one type1 two type1 three type1 callback
the example program should output
struct type1 has member one at offset 0.
struct type1 has member two at offset 1.
struct type1 has member three at offset 3.
struct type1 has member callback at offset 7.
On x86-64, which is an LP64 architecture (int being 32-bit, and long and pointers 64-bit), running
./example type2 four type2 five type2 six type2 seven
outputs
struct type2 has member four at offset 0.
struct type2 has member five at offset 1.
struct type2 has member six at offset 16.
struct type2 has member seven at offset 20.
On x86-64, one can compile 32-bit code by using the -m32 GCC option. So, running
make CFLAGS="-Wall -O2 -m32" clean all
and then
./example type2 four type2 five type2 six type2 seven
outputs
struct type2 has member four at offset 0.
struct type2 has member five at offset 1.
struct type2 has member six at offset 12.
struct type2 has member seven at offset 16.
This can be extended to allow for some kind of introspection, if we add support for the types of the structure members in the hash table entries.
However, I cannot stress enough how important it is to consider the maintenance efforts needed to keep this working. If the codebase has a strict set of coding standards, and someone knows this code-generator-generator well enough to regularly check it parses the structures correctly, and more than one developer can maintain it long-term, then sure; I don't see why not use something like this. Otherwise, it may become a heavy burden, that may pull down the rest of the project with it. Especially if there is just one developer who has sufficient knowledge to maintain the code-generator-generator, and they happen to leave. No project should be dependent on a specific person, in my opinion.
If you have any specific questions, feel free to ask them in comments, and I'll try to explain. However, I will not explain the entire member-offset-generator.bash script line-by-line (as I have occasionally done in the past for other examples I've written), because at 435 lines, with its inherent inception-like (C code output by a C program created by the script) complexity, it is not worth the effort to anyone.
