The other day, someone in the qt-interest mailing list posted the link to an article entitled: How to make fewer errors at the stage of code writing, the third part in a series of articles about writing better code. In this particular article, the author ran a static code-checker tool on the Qt source code and found some mistakes.
One of his suggestions to avoid mistakes was to use table-driven methods as a way to avoid mistakes, like the following:
struct {
QSysInfo::WinVersion; m_ver;
const char *m_str;
} Table_WinVersionToString[] = {
{ WV_Me, "WinMe" },
{ WV_95, "Win95" },
{ WV_98, "Win98" },
{ WV_NT, "WinNT" },
{ WV_2000, "Win2000" },
{ WV_2003, "Win2003" },
{ WV_XP, "WinXP" },
{ WV_VISTA,"WinVista" }
};
Unfortunately, I see two problems with that solution. The first is that it does not prevent the mistake that the author found anymore than the original solution did (the mistake was to test QSysInfo::WV_2000 twice, trying to return “Win2003″ for the second test). A better solution, making this fool-proof, would not use a table, but an array. However, this would require that the values in the QSysInfo::WinVersion were sequential. I’d instead write the code as:
static const char *DOS_based_names[] =
{ 0, "Win32s", "Win95", "Win98", "WinMe" };
static const char *NT_based_names[] =
{ 0, "WinNT", "Win2000", "WinXP", "Win2003", "WinVista", "Win7" };
if (ver & QSysInfo::WV_DOS_based)
ret = QLatin1String(DOS_based_names[ver]);
else if (ver & QSysInfo::WV_NT_based)
ret = QLatin1String(NT_based_names[ver >> 4]);
This code above also uses a table-driven method and is more secure against typing mistakes. It could use some extra checks to see if the versions IDs are in the table, if that’s possible to happen by construction. However, it doesn’t solve the second problem: relocations.
Whenever you have an array like the ones above (mine and the article’s author’s) which contain pointers, the array must be initialised in memory before the code is run. Since on libraries on Unix operating systems are Position-independent code, the actual pointer addresses aren’t known at library link time. They are only known once the library is loaded into memory, which means the dynamic linker must “patch up” the memory — that’s a relocation. For more information into what they are, I suggest reading my previous two blogs on relocation and position-independence: Moving code around and Moving code around more easily.
What I want to do here is to avoid having relocations at all. Having no relocations in my table means it can be stored in a read-only, sharable section of memory. With that, we have a faster load time of the library and we use less memory per application loading the library. So how can we have a table containing strings without relocations?
Back in 2006, when I wrote QtDBus, I faced a similar problem for the QDBusError class: I needed a way to map the enum containing the error codes to the error names. Inspired by the output from moc, the solution I found was to write a small Perl script that generated one very long string containing NULs (“\0″) and an array of indices into that table.
So instead of having a table like:
static const char *DOS_based_names[] =
{ 0, "Win32s", "Win95", "Win98", "WinMe" };
We’d instead have:
static const char DOS_based_names_string[] =
"\0"
"Win32s\0"
"Win95\0"
"Win98\0"
"WinMe\0"
"\0";
static const int DOS_based_names_indices[] = {
0, 1, 8, 14, 20, -1
};
ret = QLatin1String(DOS_based_names_string + DOS_based_names_indices[ver]);
The code above generates no relocations in the shared library and both the string and the integers can be safely stored in the .rodata section. Depending on the architecture, the amount of extra code can be trivial or not (see the end of the post for some assembly listings).
I found this technique so useful I applied it in many places in KDE. I even added a script to kdesdk called generate_string_table.pl that generate string tables. In fact, I generated the table above by running:
perl generate_string_table.pl DOS_based_names <<<'
Win32s
Win95
Win98
WinMe'
The script works fine for arrays, but the principle is the same for an associative table. Instead of creating an array of ints, you’d create an array of structs mapping the original type to the offset in the string. Writing such a script is left as an exercise for the reader.
Read the rest of this entry »
