Yesterday we released VPOP3 6.1 (build 2648) and had to remove it from our website a few hours later. This was because we discovered an incompatibility with Windows XP/2003. This version works fine on Windows Vista and later, but we inadvertently added something which required Windows Vista.
LevelDB
The ‘culprit’ was LevelDB. This is a very fast database system developed by Google (and used in Google Chrome and others). LevelDB is a very fast ‘key/data pair’ database system. It doesn’t support SQL or anything like that, but it is very useful if you just need to store and retrieve data.
We have been looking for an alternative for the spam filter’s Bayesian data store for a while, because an SQL database such as SQLite (in VPOP3 v2.x) or PostgreSQL (in VPOP3 v3 and later) is too heavyweight for this, and it appears to be causing heavier than expected disk load in some busy systems. This is because each message which is processed by the VPOP3 spam filter causes updates to the Bayesian data store. VPOP3 batches these up to try to reduce disk load, but still, each update will cause several files to be updated (the data table files, indexes and also the PostgreSQL WAL (write-ahead log) – the data table and indexes are updated in a ‘random access’ way, so this is slow in itself on low-end disk systems). In fact, the durability of PostgreSQL is not needed. If the PC crashes and we lose the last few messages worth of Bayesian data it is no great loss.
While looking for an alternative, LevelDB came on our radar. It is a key/data database, so all you can do with it is read/set a single ‘data’ value given a ‘key’ value. This is actually ideal for a Bayesian data store, as the ‘key’ is the word being analysed, and the ‘data’ is a structure containing the statistics for that word.
The performance advantage of LevelDB is that every time a word’s data is added/updated, only a single log disk file is appended to, which is a sequential write, so very quick. Occasionally, the LevelDB system will merge this log file into other data files, but this amortised cost is much less than the regular multi-file updates of PostgreSQL.
For durability and ease of backup, we use PostgreSQL as the ‘main’ data store, and overnight will synchronise the LevelDB database with the PostgreSQL data table. On a restore, the LevelDB database is automatically rebuilt from the PostgreSQL backup. This means that the backup/restore procedure is no more complicated than in VPOP3 v5 & 6.0, but normal operation places less load on the disk system of the VPOP3 PC.
The Problem
While the LevelDB solution works great on Windows 7/2008 etc, this version of VPOP3 will not even load on Windows XP/2003. Obviously this is a problem because XP/2003 installations still comprise a large portion of the userbase.
The cause of the problem is that the Windows port of LevelDB which we are using uses the InitOnceExecuteOnce Windows API function. This is a useful function which will cause a specified ‘initializer’ function to be run only once, however many times it is called. In multi-threaded programs this is a solution to a common problem with initialisation of global variables. Unfortunately InitOnceExecuteOnce is only supported in Windows Vista and later.
We had made the mistake of assuming that, since LevelDB is used in Google Chrome, and Chrome works on Windows XP, then there would be no issue with using LevelDB on Windows XP. However, Google Chrome uses a different Windows port of LevelDB which requires other libraries (Boost) which we did not want to have to integrate into VPOP3, so we had not used the same Windows port as Chrome uses – thus the problem.
As LevelDB requires an InitOnceExecuteOnce type of function we had to produce our own implementation of something like that, but which will work on Windows XP/2003.
Our implementation is below:
ldb_port_win.h
#if WINVER <= 0x0600 typedef volatile __int64 OnceType; #else typedef void* OnceType; #endif
#define LEVELDB_ONCE_INIT 0 extern void InitOnce(port::OnceType*, void (*initializer)());
ldb_port_win.c
#if WINVER <= 0x600
void InitOnce(OnceType* once, void (*initializer)()) {
LARGE_INTEGER *once_ = (LARGE_INTEGER *)once;
if (once_->LowPart == 1)
{
return;
}
if (InterlockedExchange(&once_->HighPart, 1) == 0)
{
((void (*)())initializer)();
once_->LowPart = 1;
}
else
{
while(once_->LowPart == 0)
{
Sleep(10);
}
}
}
#else
BOOL CALLBACK InitHandleFunction (PINIT_ONCE InitOnce, PVOID func, PVOID *lpContext) {
((void (*)())func)();
return true;
}
void InitOnce(OnceType* once, void (*initializer)()) {
InitOnceExecuteOnce((PINIT_ONCE)once, InitHandleFunction, initializer, NULL);
}
#endif
We use a 64 bit integer as the ‘OnceType’. This type needs to be set by the compiler from a single value (LEVELDB_ONCE_INIT) for it to be compatible with LevelDB. It cannot be a structure or have an initialisation function. We use a 64 bit integer because we need to have two 32 bit values contained within a single variable. (Potentially there may be a way of doing it with a single 32 bit value, but as this way works, and is straightforward, we decided to do it this way). Even though we are only storing a 0 or 1 in each value, at least one has to be a 32 bit value because we need to use the InterlockedExchange function to modify it, and the 16 bit InterlockedExchange function was only added in Windows Vista, so we cannot use that.
So, we use the 64 bit value as two 32 bit values. The low 32 bits are 0 at initialisation and 1 when the initializer function has been called. The high 32 bits are 0 at initialisation and 1 when a thread has the responsibility of calling the initializer function.
Thus, once initialisation has finished, the if (once_->LowPart == 1) condition allows a quick return from the function. (This conditional return is not strictly necessary – if it wasn’t there, then the function would still work correctly – but it allows for a quick drop-out from the function in the most common case).
If two or more threads call the InitOnce function at the same time before the initializer function has been called, then when they both call the InterlockedExchange function and set the HighPart to 1, one of them (and only one) will be told that the previous value of HighPart was 0, the other threads will see that the previous value was 1. This is what the InterlockedExchange function gives us.
If we had to do this without the InterlockedExchange function we would have difficulty because of race conditions, eg
if (HighPart == 0)
{
HighPart = 1;
initializer();
}
would give us a race condition where two or more threads could see that HighPart was 0 so both could go through to call the initializer. We could potentially use mutexs or critical sections to avoid this – except that the mutex or critical section would need initialising – and that’s the whole point of this function, so we couldn’t create this function without this function already existing. Thus, we can’t use critical sections or mutexes, and an InterlockedExchange function is the best way we can see of doing it.
Back to the InitOnce function. When a second thread has arrived at the InitOnce function before initializer has finished, but after another thread has taken responsibility, it will pass through to the busy wait loop, idling until the LowPart has been set to 1.