Introducing WJ’s Backup

Recently I became frustrated with Cobian Backup. It was the only free software I could find that:

1. supported incremental backups,
2. supported Volume Shadow Copy,
3. and didn’t install a bunch of extra, useless startup entries and services.

However, two things sucked:

1. Incremental backups only seemed to work properly when it used the “archive” attribute. This meant that it couldn’t recover from interrupted backups properly.
2. It didn’t provide any way of restoring files, so you had to go through the different .7z files and find the file you want to restore.

So, I decided to create my own backup program: “WJ’s Backup”. The possessive in the title is not to indicate some obsessive sense of ownership, but to emphasize the fact that the program was not developed with any other user’s perspective in mind.

Unlike most other backup programs I could find, WJ’s Backup maintains a database with file/directory metadata for each revision. It keeps file versions in a SVN-like way, but without diffs for file content (each new version is stored in full). 7-Zip compression is mandatory.

Project page at SourceForge

Power series of tan(x), cot(x), csc(x)

Here’s a little how-to on figuring out the power series of tan(x), cot(x) and csc(x).

Start with the generating function for the Bernoulli numbers:

Take only the even powers of t on the LHS:

Put :

Recall that and :

That was pretty easy. How about tan and csc?

Consider

And finally,

Thread-safe one-time initialization

Not thread-safe

BOOLEAN initialized = FALSE;
OBJECT object = NULL;

DoSomething()
{
    if (!initialized)
    {
        object = Create();
        initialized = TRUE;
    }
    
    // Use object.
}

Disadvantages:

• Not thread-safe

Thread-safe (locking, double-checked)

BOOLEAN initialized = FALSE;
OBJECT object = NULL;
LOCK lock = LOCK_INIT;

DoSomething()
{
    if (!initialized)
    {
        AcquireLock(&lock);
        
        if (!initialized)
        {
            object = Create();
            MemoryBarrier();
            initialized = TRUE;
        }
        
        ReleaseLock(&lock);
    }
    
    // Use object.
}

Advantages:

• Thread-safe

Disadvantages:

• Lock overhead
• More code

Thread-safe (custom)

OBJECT object = NULL;

DoSomething()
{
    OBJECT localObject;
    OBJECT newObject;
    
    localObject = object;
    
    if (!localObject)
    {
        newObject = Create();
        
        // Try to store the created object.
        localObject = InterlockedCompareExchangePointer(
            &object,
            newObject,
            NULL
            );
        
        if (!localObject)
        {
            // Success.
            localObject = newObject;
        }
        else
        {
            // Some other thread already stored the object.
            Destroy(newObject);
        }
    }
    
    return localObject;
}

Advantages:

• Thread-safe
• Less overhead

Disadvantages:

• More code
• Created object may need to be destroyed

PAE patch updated for Windows 7 SP1

This patch allows you to use more than 3/4GB of RAM on an x86 Windows system. Works on Vista and 7, has been tested on Windows Vista SP2, Windows 7 SP0 and Windows 7 SP1. Instructions and source code included.

Download: http://www.mediafire.com/?01x25z8sqvbbzfz

Note: I do not offer any support for this. If this did not work for you, either:

• You cannot follow instructions correctly, or
• You cannot use more than 4GB of physical memory on 32-bit Windows due to hardware/software conflicts.

Fast CRC32 in Assembly

Timings on 768 bytes, 1,000,000 times:

Assembly: 1722ms
C (same algorithm, MSVC, -O2): 2099ms
RtlComputeCrc32: 2033ms

Timings on 2,097,152 bytes, 1,000 times:

Assembly: 5375ms
C: 5892ms
RtlComputeCrc32: 5608ms

It’s pretty fast, but nowhere as fast as an implementation that processes the data in 16-bit quantities.

Note: Crc32Table not included.

__declspec(naked) unsigned long __cdecl crc32(unsigned long crc, char *buf, size_t len)
{
    __asm
    {
        push    esi

        mov     eax, [esp+0x8+0x0] // crc
        mov     ecx, [esp+0x8+0x8] // len
        mov     esi, [esp+0x8+0x4] // buf

        xor     edx, edx // all bits but lowest 8 are kept clear for use as the index
        jecxz   done
        not     eax

        // while (len--)
        //     crc = (crc >> 8 ) ^ table[(crc ^ *buf++) & 0xff]
loop_start:
        mov     dl, [esi] // 1
        inc     esi // 1
        xor     dl, al // 2 (dl)
        shr     eax, 8 // 2
        xor     eax, [Crc32Table+edx*4] // 3 (eax, edx)

        sub     ecx, 1 // 4
        jnz     loop_start // 4

        not     eax
done:
        pop     esi
        ret
    }
}

The NT “reserve object”

Windows 7 introduced two new object types: UserApcReserve and IoCompletionReserve. What do these object types have in common? They’re both created using NtAllocateReserveObject. If we look inside this system call we can see that the third argument is an index into two arrays, PspMemoryReserveObjectSizes and PspMemoryReserveObjectTypes. Notice that PspInitPhase0 creates a set number (currently two) of object types, drawing the names from another array: PspMemoryReserveObjectNames. Here’s my reversed definition of NtAllocateReserveObject:

#define USER_APC_RESERVE_TYPE 0
#define IO_COMPLETION_RESERVE_TYPE 1

NTSYSCALLAPI
NTSTATUS
NTAPI
NtAllocateReserveObject(
    __out PHANDLE MemoryReserveHandle,
    __in_opt POBJECT_ATTRIBUTES ObjectAttributes,
    __in ULONG Type
    );

Two new system calls take advantage of the UserApcReserve object and IoCompletionReserve object: NtQueueApcThreadEx and NtSetIoCompletionEx, respectively. In NtQueueApcThreadEx we can see that if a user APC reserve handle/object is supplied, the function uses the space allocated for that object to store the APC, instead of allocating from the pool. Similarly NtSetIoCompletionEx uses the I/O completion reserve object’s already allocated space to store the I/O completion mini-packet, instead of allocating from the pool. It is now clear what the purpose of these reserve objects are: to allow processes to reserve memory before performing certain system calls in order to avoid out-of-memory problems occurring at bad spots (or critical code). Here’s my reversed definitions for the two system calls:

NTSYSCALLAPI
NTSTATUS
NTAPI
NtQueueApcThreadEx(
    __in HANDLE ThreadHandle,
    __in_opt HANDLE UserApcReserveHandle,
    __in PPS_APC_ROUTINE ApcRoutine,
    __in_opt PVOID ApcArgument1,
    __in_opt PVOID ApcArgument2,
    __in_opt PVOID ApcArgument3
    );

NTSYSCALLAPI
NTSTATUS
NTAPI
NtSetIoCompletionEx(
    __in HANDLE IoCompletionHandle,
    __in HANDLE IoCompletionReserveHandle,
    __in PVOID KeyContext,
    __in_opt PVOID ApcContext,
    __in NTSTATUS IoStatus,
    __in ULONG_PTR IoStatusInformation
    );

Note that NtQueueApcThread now calls NtQueueApcThreadEx, which is why the reserve object is optional.

PAE patch updated for Windows 7

Note: An updated version for Windows 7 SP1 is available.

This patch allows you to use more than 3/4GB of RAM on an x86 Windows system. Works on Vista and 7, has been tested on Windows Vista SP2 and Windows 7. Instructions and source code included.

Download: http://www.mediafire.com/file/tgjjmhnnm2c/PatchPae.zip

HOWTO: Use I_QueryTagInformation

Process Explorer 12 includes a new feature whereby you can view service names associated with threads. To find out how this works, read this article by Alex Ionescu. You won’t be completely satisfied, though. You still don’t know how to use I_QueryTagInformation.

First step: Getting the service tag for a thread
This is simple; use NtQueryInformationThread to get the thread’s TEB address, then read the SubProcessTag from the TEB:

THREAD_BASIC_INFORMATION basicInfo;
PVOID subProcessTag;

NtQueryInformationThread(your_thread_handle, ThreadBasicInformation, &basicInfo, sizeof(basicInfo), NULL);
NtReadVirtualMemory(handle_to_the_process_containing_the_thread, (PVOID)((ULONG_PTR)basicInfo.TebBaseAddress + FIELD_OFFSET(TEB, SubProcessTag)), &subProcessTag, sizeof(PVOID), NULL);

// If you don't have the full TEB definition, here are the offsets (replace the FIELD_OFFSET invocation with these):
// x86: 0xf60
// x64: 0x1720

// You now have the service tag in subProcessTag.

Second step: Using I_QueryTagInformation
I_QueryTagInformation is located in advapi32.dll. Here’s what I’ve reverse-engineered from looking at advapi32.dll and services.exe:

typedef enum _SC_SERVICE_TAG_QUERY_TYPE
{
    ServiceNameFromTagInformation = 1,
    ServiceNamesReferencingModuleInformation,
    ServiceNameTagMappingInformation
} SC_SERVICE_TAG_QUERY_TYPE, *PSC_SERVICE_TAG_QUERY_TYPE;

typedef struct _SC_SERVICE_TAG_QUERY
{
    ULONG ProcessId;
    ULONG ServiceTag;
    ULONG Unknown;
    PVOID Buffer;
} SC_SERVICE_TAG_QUERY, *PSC_SERVICE_TAG_QUERY;

typedef ULONG (NTAPI *_I_QueryTagInformation)(
    __in PVOID Unknown,
    __in SC_SERVICE_TAG_QUERY_TYPE QueryType,
    __inout PSC_SERVICE_TAG_QUERY Query
    );

The usage is fairly obvious: you want the service name for the service tag (ServiceNameFromTagInformation), you fill in the SC_SERVICE_TAG_QUERY structure, and you call I_QueryTagInformation:

_I_QueryTagInformation I_QueryTagInformation;
SC_SERVICE_TAG_QUERY query;

I_QueryTagInformation = GetProcAddress(GetModuleHandle(L"advapi32.dll"), "I_QueryTagInformation");

if (I_QueryTagInformation)
{
    query.ProcessId = (ULONG)your_process_ID;
    query.ServiceTag = (ULONG)subProcessTag;
    query.Unknown = 0;
    query.Buffer = NULL;
    
    I_QueryTagInformation(NULL, ServiceNameFromTagInformation, &query);
    
    wprintf(L"Service name: %s\n", query.Buffer);
    LocalFree(query.Buffer);
}

Get the image file name of any process from any user on Vista and above

On Vista and above there is an information class for NtQuerySystemInformation which I call SystemProcessImageNameInformation (88). (Note that I reverse-engineered this, so it is probably not the correct name for the information class.) The structure definition is below:

typedef struct _SYSTEM_PROCESS_IMAGE_NAME_INFORMATION
{
    HANDLE ProcessId;
    UNICODE_STRING ImageName;
} SYSTEM_PROCESS_IMAGE_NAME_INFORMATION, *PSYSTEM_PROCESS_IMAGE_NAME_INFORMATION;

This information class allows you to get the image file name of any process, regardless of your user, privileges, or access to the process. Usage:

NTSTATUS status;
PVOID buffer;
SYSTEM_PROCESS_IMAGE_NAME_INFORMATION info;

buffer = malloc(0x100);
info.ProcessId = WhateverTheProcessIdIs;
info.ImageName.Length = 0;
info.ImageName.MaximumLength = (USHORT)0x100;
info.ImageName.Buffer = buffer;

status = NtQuerySystemInformation(88, &info, sizeof(info), NULL);

if (status == STATUS_INFO_LENGTH_MISMATCH)
{
    // Our buffer was too small. The required buffer length is stored in MaximumLength.
    free(buffer);
    buffer = malloc(info.ImageName.MaximumLength);
    info.ImageName.Buffer = buffer;
    status = NtQuerySystemInformation(88, &info, sizeof(info), NULL);
}

if (NT_SUCCESS(status))
{
    wprintf(L"File name: %.*s\n", info.ImageName.Length / 2, info.ImageName.Buffer);
}

free(buffer);

Fast reader-writer lock in C

I ported my fast reader-writer lock from C# to C for Process Hacker 2. Here it is.

#include <windows.h>
#include <intrin.h>

// Put this in a header file.
typedef struct _PH_FAST_LOCK
{
    ULONG Value;
    HANDLE ExclusiveWakeEvent;
    HANDLE SharedWakeEvent;
} PH_FAST_LOCK, *PPH_FAST_LOCK;

#define PH_LOCK_OWNED 0x1
#define PH_LOCK_EXCLUSIVE_WAKING 0x2

#define PH_LOCK_SHARED_OWNERS_SHIFT 2
#define PH_LOCK_SHARED_OWNERS_MASK 0x3ff
#define PH_LOCK_SHARED_OWNERS_INC 0x4

#define PH_LOCK_SHARED_WAITERS_SHIFT 12
#define PH_LOCK_SHARED_WAITERS_MASK 0x3ff
#define PH_LOCK_SHARED_WAITERS_INC 0x1000

#define PH_LOCK_EXCLUSIVE_WAITERS_SHIFT 22
#define PH_LOCK_EXCLUSIVE_WAITERS_MASK 0x3ff
#define PH_LOCK_EXCLUSIVE_WAITERS_INC 0x400000

#define PH_LOCK_EXCLUSIVE_MASK \
    (PH_LOCK_EXCLUSIVE_WAKING | \
    (PH_LOCK_EXCLUSIVE_WAITERS_MASK << PH_LOCK_EXCLUSIVE_WAITERS_SHIFT))

static ULONG PhLockSpinCount;

// Call this method BEFORE using any of the other functions.
VOID PhFastLockInitialization()
{
    SYSTEM_INFO systemInfo;

    GetSystemInfo(&systemInfo);

    if (systemInfo.dwNumberOfProcessors > 1)
        PhLockSpinCount = 4000;
    else
        PhLockSpinCount = 0;
}

VOID PhInitializeFastLock(
    __out PPH_FAST_LOCK FastLock
    )
{
    FastLock->Value = 0;
    FastLock->ExclusiveWakeEvent = NULL;
    FastLock->SharedWakeEvent = NULL;
}

VOID PhDeleteFastLock(
    __inout PPH_FAST_LOCK FastLock
    )
{
    if (FastLock->ExclusiveWakeEvent)
    {
        CloseHandle(FastLock->ExclusiveWakeEvent);
        FastLock->ExclusiveWakeEvent = NULL;
    }

    if (FastLock->SharedWakeEvent)
    {
        CloseHandle(FastLock->SharedWakeEvent);
        FastLock->SharedWakeEvent = NULL;
    }
}

#ifdef _M_IX86

FORCEINLINE PVOID _InterlockedCompareExchangePointer(
    __inout PVOID volatile *Destination,
    __in PVOID Exchange,
    __in PVOID Comparand
    )
{
    return (PVOID)_InterlockedCompareExchange(
        (PLONG_PTR)Destination,
        (LONG_PTR)Exchange,
        (LONG_PTR)Comparand
        );
}

FORCEINLINE PVOID _InterlockedExchangePointer(
    __inout PVOID volatile *Destination,
    __in PVOID Exchange
    )
{
    return (PVOID)_InterlockedExchange(
        (PLONG_PTR)Destination,
        (LONG_PTR)Exchange
        );
}

#endif

FORCEINLINE VOID PhpEnsureEventCreated(
    __inout PHANDLE Handle
    )
{
    HANDLE handle;

    if (*Handle != NULL)
        return;

    handle = CreateSemaphore(NULL, 0, MAXLONG, NULL);

    if (_InterlockedCompareExchangePointer(
        Handle,
        handle,
        NULL
        ) != NULL)
    {
        CloseHandle(handle);
    }
}

VOID PhAcquireFastLockExclusive(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;
    ULONG i = 0;

    while (TRUE)
    {
        value = FastLock->Value;

        if (!(value & (PH_LOCK_OWNED | PH_LOCK_EXCLUSIVE_WAKING)))
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value + PH_LOCK_OWNED,
                value
                ) == value)
                break;
        }
        else if (i >= PhLockSpinCount)
        {
            PhpEnsureEventCreated(&FastLock->ExclusiveWakeEvent);

            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value + PH_LOCK_EXCLUSIVE_WAITERS_INC,
                value
                ) == value)
            {
                if (WaitForSingleObject(
                    FastLock->ExclusiveWakeEvent,
                    INFINITE
                    ) != WAIT_OBJECT_0)
                {
                    // You might want to raise an exception here.
                }

                do
                {
                    value = FastLock->Value;
                } while (_InterlockedCompareExchange(
                    &FastLock->Value,
                    value + PH_LOCK_OWNED - PH_LOCK_EXCLUSIVE_WAKING,
                    value
                    ) != value);

                break;
            }
        }

        i++;
        YieldProcessor();
    }
}

VOID PhAcquireFastLockShared(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;
    ULONG i = 0;

    while (TRUE)
    {
        value = FastLock->Value;

        if (!(value & (
            PH_LOCK_OWNED |
            (PH_LOCK_SHARED_OWNERS_MASK << PH_LOCK_SHARED_OWNERS_SHIFT) |
            PH_LOCK_EXCLUSIVE_MASK
            )))
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value + PH_LOCK_OWNED + PH_LOCK_SHARED_OWNERS_INC,
                value
                ) == value)
                break;
        }
        else if (
            (value & PH_LOCK_OWNED) &&
            ((value >> PH_LOCK_SHARED_OWNERS_SHIFT) & PH_LOCK_SHARED_OWNERS_MASK) > 0 &&
            !(value & PH_LOCK_EXCLUSIVE_MASK)
            )
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value + PH_LOCK_SHARED_OWNERS_INC,
                value
                ) == value)
                break;
        }
        else if (i >= PhLockSpinCount)
        {
            PhpEnsureEventCreated(&FastLock->SharedWakeEvent);

            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value + PH_LOCK_SHARED_WAITERS_INC,
                value
                ) == value)
            {
                if (WaitForSingleObject(
                    FastLock->SharedWakeEvent,
                    INFINITE
                    ) != WAIT_OBJECT_0)
                {
                    // You might want to raise an exception here.
                }

                continue;
            }
        }

        i++;
        YieldProcessor();
    }
}

VOID PhReleaseFastLockExclusive(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;

    while (TRUE)
    {
        value = FastLock->Value;

        if ((value >> PH_LOCK_EXCLUSIVE_WAITERS_SHIFT) & PH_LOCK_EXCLUSIVE_WAITERS_MASK)
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value - PH_LOCK_OWNED + PH_LOCK_EXCLUSIVE_WAKING - PH_LOCK_EXCLUSIVE_WAITERS_INC,
                value
                ) == value)
            {
                ReleaseSemaphore(FastLock->ExclusiveWakeEvent, 1, NULL);

                break;
            }
        }
        else
        {
            ULONG sharedWaiters;

            sharedWaiters = (value >> PH_LOCK_SHARED_WAITERS_SHIFT) & PH_LOCK_SHARED_WAITERS_MASK;

            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value & ~(PH_LOCK_OWNED | (PH_LOCK_SHARED_WAITERS_MASK << PH_LOCK_SHARED_WAITERS_SHIFT)),
                value
                ) == value)
            {
                if (sharedWaiters)
                    ReleaseSemaphore(FastLock->SharedWakeEvent, sharedWaiters, 0);

                break;
            }
        }

        YieldProcessor();
    }
}

VOID PhReleaseFastLockShared(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;

    while (TRUE)
    {
        value = FastLock->Value;

        if (((value >> PH_LOCK_SHARED_OWNERS_SHIFT) & PH_LOCK_SHARED_OWNERS_MASK) > 1)
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value - PH_LOCK_SHARED_OWNERS_INC,
                value
                ) == value)
                break;
        }
        else if ((value >> PH_LOCK_EXCLUSIVE_WAITERS_SHIFT) & PH_LOCK_EXCLUSIVE_WAITERS_MASK)
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value - PH_LOCK_OWNED + PH_LOCK_EXCLUSIVE_WAKING -
                PH_LOCK_SHARED_OWNERS_INC - PH_LOCK_EXCLUSIVE_WAITERS_INC,
                value
                ) == value)
            {
                ReleaseSemaphore(FastLock->ExclusiveWakeEvent, 1, NULL);

                break;
            }
        }
        else
        {
            if (_InterlockedCompareExchange(
                &FastLock->Value,
                value - PH_LOCK_OWNED - PH_LOCK_SHARED_OWNERS_INC,
                value
                ) == value)
                break;
        }

        YieldProcessor();
    }
}

BOOLEAN PhTryAcquireFastLockExclusive(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;

    value = FastLock->Value;

    if (value & (PH_LOCK_OWNED | PH_LOCK_EXCLUSIVE_WAKING))
        return FALSE;

    return _InterlockedCompareExchange(
        &FastLock->Value,
        value + PH_LOCK_OWNED,
        value
        ) == value;
}

BOOLEAN PhTryAcquireFastLockShared(
    __inout PPH_FAST_LOCK FastLock
    )
{
    ULONG value;

    value = FastLock->Value;

    if (value & PH_LOCK_EXCLUSIVE_MASK)
        return FALSE;

    if (!(value & PH_LOCK_OWNED))
    {
        return _InterlockedCompareExchange(
            &FastLock->Value,
            value + PH_LOCK_OWNED + PH_LOCK_SHARED_OWNERS_INC,
            value
            ) == value;
    }
    else if ((value >> PH_LOCK_SHARED_OWNERS_SHIFT) & PH_LOCK_SHARED_OWNERS_MASK)
    {
        return _InterlockedCompareExchange(
            &FastLock->Value,
            value + PH_LOCK_SHARED_OWNERS_INC,
            value
            ) == value;
    }
    else
    {
        return FALSE;
    }
}