The “both open and closed” trick for connected spaces

Here is a basic result concerning connected topological spaces.

The only subsets of a connected space \(X\) that are both open and closed are \(\emptyset\) and \(X\) itself.

Clearly, if \(A\) is a nonempty subset of \(X\) that is both open and closed then \(A=X\). We can derive a useful theorem as a consequence of this principle.

Theorem. Let \(X\) be a connected space and let \(\sim\) be an equivalence relation on \(X\). If every \(x \in X\) has a neighborhood \(U\) such that \(p \sim q\) for every \(p,q \in U\), then \(p \sim q \) for every \(p,q \in X\).

Proof. The result clearly holds if \(X\) is empty, so assume otherwise. Let \(p \in X\) and let \(S=\{q \in X : p \sim q\}\). Note that \(S\) is nonempty. If \(q \in S\) then there is a neighborhood \(U\) of \(q\) such that \(q_1 \sim q_2\) for every \(q_1,q_2 \in U\). In particular, for every \(r \in U\) we have \(p \sim q\) and \(q \sim r\) which implies that \(p \sim r\). Then \(U \subseteq S\), which shows that \(S\) is open. If \(q \in X \setminus S\) we can again find a neighborhood \(U\) of \(q\) such that \(q_1 \sim q_2\) for every \(q_1,q_2 \in U\). If \(p \sim r\) for some \(r \in U\) then \(p \sim q\) since \(q \sim r\), which contradicts the fact that \(q \in X \setminus S\). Therefore \(U \subseteq X \setminus S\), which shows that \(S\) is closed. Since \(X\) is connected, \(S=X\). \(\square\)

We can restate this as follows: if \(X\) is connected and \(\sim\) is an equivalence relation on \(X\) such that every equivalence class is open, then there is exactly one equivalence class. This theorem can be used to derive global properties from local ones. Here are some simple applications of this “local-to-global” theorem.

Theorem. A space that is both connected and locally path-connected is path-connected. A space that is both connected and locally piecewise-smooth-path-connected is piecewise-smooth-path-connected.

Proof. Obvious. \(\square\)

A graph is a CW complex of dimension 0 or 1; the 0-cells are the vertices and the 1-cells are the edges.

Theorem. A graph \(G\) is connected in the graph-theoretic sense if and only if it is connected in the topological sense.

Proof. The \(\Rightarrow\) direction is clear. Suppose that \(G\) is topologically connected. Define an equivalence relation \(\sim\) on \(G\) by “\(p \sim q\) if and only if there exists a graph-theoretic path containing the points \(p\) and \(q\)”, and apply the “local-to-global” theorem. \(\square\)

We say that a topological space \(X\) is homogeneous if for any two points \(p,q \in X\) there is a homeomorphism \(\varphi : X \to X\) such that \(\varphi(p)=q\).

Theorem. Every connected topological manifold is homogeneous.

Proof. Let \(X\) be such a manifold. Write \(\mathbb{B}^n\) for the open unit ball in \(\mathbb{R}^n\). It is not too hard to show that for any two points \(p,q \in \mathbb{B}^n\) there is a homeomorphism \(\varphi:\overline{\mathbb{B}^n}\to\overline{\mathbb{B}^n}\) such that \(\varphi(p)=q\) and \(\varphi|_{\partial\mathbb{B}^n}\) is the identity. From this we can use the gluing lemma to show that every point of \(X\) has a neighborhood \(U\) with the property that for any \(p,q \in U\), there is a homeomorphism from \(X\) to itself taking \(p\) to \(q\). (Here we choose \(U\) to be a certain coordinate ball around the point.) Finally, notice that the relation \(\sim\) on \(X\) defined by “\(p \sim q\) if and only if there exists a homeomorphism from \(X\) to itself taking \(p\) to \(q\)” is indeed an equivalence relation, since we can compose two homeomorphisms to get another homeomorphism. Applying the “local-to-global” theorem finishes off the proof. \(\square\)

Theorem. If \(q : C \to X\) is a covering map and \(X\) is connected then the cardinality of \(q^{-1}(\{x\})\) is the same for all \(x \in X\).

Proof. Define an equivalence relation \(\sim\) on \(X\) by declaring that \(x \sim y\) if and only if \(q^{-1}(\{x\})\) and \(q^{-1}(\{y\})\) have the same cardinality. Every point \(x \in X\) has some evenly covered neighborhood \(U\), and obviously \(p \sim q\) for every \(p,q \in U\). Now apply the “local-to-global” theorem. \(\square\)

Of course, there are many more applications of the “open and closed” principle that do not use the equivalence relation theorem stated above. Here are two of them.

Theorem. Every continuous map \(f:X \to Y\) from a nonempty connected space to a discrete space is constant.

Proof. Choose some \(x \in X\). Since \(\{f(x)\}\) is both open and closed in \(Y\), the set \(f^{-1}(\{f(x)\})\) is both open and closed in \(X\). Therefore \(f^{-1}(\{f(x)\})=X\), i.e. \(f\) is constant. \(\square\)

Lemma. Let \(f(X)=\sum a_n X^n\) be a complex power series convergent in a non-discrete set \(E\subseteq\mathbb{C}\). If \(f(z)=0\) for all \(z \in E\) then \(a_n=0\) for all \(n\).

Theorem (The identity theorem). Let \(U\) be a connected open subset of \(\mathbb{C}\) and let \(f:U\to\mathbb{C}\) be an analytic function. If \(f\) is zero on a non-discrete set then \(f=0\) on \(U\).

Proof. Let \(S\) be the set of points \(z \in U\) such that \(f=0\) in a neighborhood of \(z\); then \(S\) is open by definition. Now let \(z \in U\) be a limit point of \(S\). The preceding lemma shows that there exists a neighborhood of \(z\) on which \(f=0\), and therefore \(z \in S\). This shows that \(S\) is closed in \(U\). Finally, our assumption that \(f\) is zero on a non-discrete set implies that \(f=0\) on some open set (by the preceding lemma), so \(S\) is non-empty. Since \(U\) is connected and \(S\) is both open and closed, \(S=U\). \(\square\)

Asus UX31E – setting up the Elantech touchpad driver for Windows 8

I recently upgraded my Asus Zenbook UX31E laptop to Windows 8. Here I’ll show you what I did to update my Elantech drivers to get gestures (swipe from left, top, right, bottom) working. As a bonus, I’ll also show you how to get three finger tap = middle click so you can open new browser tabs easily.

  1. Download the latest Elantech driver for Windows 8 from here: http://support.asus.com/download.aspx?SLanguage=en&m=Touchpad&p=3&s=110. The file name should look like this: Touchpad_Elanteh_Pega_Win7_Win8_….
  2. Install the driver and reboot.
  3. Try out the gestures and test scrolling. If you’re happy with the driver, stop reading here.
  4. Download Process Hacker and run it with administrator privileges.
  5. Press Ctrl+F and search for “elantech”. You should get some results that have Type = Key and Name = HKU\S-1-5-21-<many digits>\Software\Elantech\….
  6. Double-click on one of the results and click Properties. The registry editor should pop up at that registry key.
  7. On the left, make sure you’re at SmartPad: Elantech Registry
  8. To disable annoying behavior where the touchpad freezes up when you’re typing: set the values of DisableWhenType_DelayTime_Gesture, DisableWhenType_DelayTime_Move, DisableWhenType_DelayTime_Tap all to 0.
  9. To disable scrolling inertia: set EGS_InertialScroll_Enable and SC_InertialScroll_Enable both to 0. (I can’t remember which one it is, so you might as well set both.)
  10. To enable three finger tap = middle click: set Tap_Three_Finger to 2 (left click = 0, right click = 1, middle click = 2) and set Tap_Three_Finger_Enable to 1.
  11. Reboot.

Please post a comment if you have any questions.

AdSense on Process Hacker’s website

Today I finally enabled AdSense on processhacker.sourceforge.net with the following (somewhat aggressive) layout:

Home page:

ph_ads_1

Downloads page:

ph_ads_2

Mini FAQ

Why ads? (1) I want to get some money, and (2) Curiosity. This change should not affect loyal users of Process Hacker at all, because most people come to the website to see what Process Hacker is about and download it – that’s pretty much it. Our average pages/visit is around 1.71.

Are ads going to show up on the forums? Probably not.

What about those “Fix EXE and DLL and registry error” ads? Yes, this is somewhat ironic.

When is the next version of Process Hacker going to be released? Very soon.

Thanks for reading. If you have any strong opinions about this, please post a comment here.

How to backup files in C++ using the volume shadow copy service (VSS)

If you’re writing a backup program, you need to be able to read and access files that are in use by other programs. The proper way to do this is to use the Volume Shadow Copy Service. The MSDN pages cover a lot of material that is unnecessary for a simple backup program, so here are some simple steps to get you started.

Before you start: important notes

  • This article assumes that you are using Windows Vista or later. For Windows XP, you may need to make some modifications to this code.
  • You cannot use VSS from a 32-bit program running under a 64-bit version of Windows. On 64-bit Windows, you need to compile a 64-bit version of your program.
  • Usually, your program needs to run under an administrator account. If UAC is enabled, your program needs to be elevated.

Step 1. Initialize backup components

You need to have access to these two functions: CreateVssBackupComponents, VssFreeSnapshotProperties. If you want, you can link to VssApi.lib. Here I will be using GetProcAddress instead. Start with some basic imports and definitions:

#include <vss.h>
#include <vswriter.h>
#include <vsbackup.h>

typedef HRESULT (STDAPICALLTYPE *_CreateVssBackupComponentsInternal)(
    __out IVssBackupComponents **ppBackup
    );

typedef void (APIENTRY *_VssFreeSnapshotPropertiesInternal)(
    __in VSS_SNAPSHOT_PROP *pProp
    );

static _CreateVssBackupComponentsInternal CreateVssBackupComponentsInternal_I;
static _VssFreeSnapshotPropertiesInternal VssFreeSnapshotPropertiesInternal_I;

Note that the functions have “Internal” at the end. Now get the functions and create your IVssBackupComponents object:

HRESULT result;
HMODULE vssapiBase;
IVssBackupComponents *backupComponents;

vssapiBase = LoadLibrary(L"vssapi.dll");

if (vssapiBase)
{
    CreateVssBackupComponentsInternal_I = (_CreateVssBackupComponentsInternal)GetProcAddress(vssapiBase, "CreateVssBackupComponentsInternal");
    VssFreeSnapshotPropertiesInternal_I = (_VssFreeSnapshotPropertiesInternal)GetProcAddress(vssapiBase, "VssFreeSnapshotPropertiesInternal");
}

if (!CreateVssBackupComponentsInternal_I || !VssFreeSnapshotPropertiesInternal_I)
    abort(); // Handle error

result = CreateVssBackupComponentsInternal_I(&backupComponents);

if (!SUCCEEDED(result))
    abort(); // Handle error

Step 2. Connect to VSS

Nothing interesting here.

VSS_ID snapshotSetId;

result = backupComponents->InitializeForBackup();

if (!SUCCEEDED(result))
    abort(); // If you don't have admin privileges or your program is running under WOW64, it will fail here

result = backupComponents->SetBackupState(FALSE, FALSE, VSS_BT_INCREMENTAL);

if (!SUCCEEDED(result))
    abort(); // Handle error

result = backupComponents->SetContext(VSS_CTX_FILE_SHARE_BACKUP);

if (!SUCCEEDED(result))
    abort(); // Handle error

return backupComponents->StartSnapshotSet(&snapshotSetId);

Step 3. Add the volumes

Now you need to add the volumes that you’re interested in by calling AddToSnapshotSet. This will give you a snapshot ID that you need to save. Make sure your volume name has a trailing backslash. In this article we’ll assume that you only have one volume that you’re interested in, but you can add as many as you want.

VSS_ID snapshotId;

result = backupComponents->AddToSnapshotSet(L"D:\\", GUID_NULL, &snapshotId);

if (!SUCCEEDED(result))
    abort(); // Handle error

Step 4. Perform the snapshot

Once you have added your volumes, you need to perform the snapshot using DoSnapshotSet:

IVssAsync *async;

result = backupComponents->DoSnapshotSet(&async);

if (!SUCCEEDED(result))
    abort(); // Handle error

result = async->Wait();
async->Release();

if (!SUCCEEDED(result))
    abort(); // Handle error

Step 5. Use the snapshot(s)

Your snapshot(s) are now ready. For each of the volumes, call GetSnapshotProperties to get a VSS_SNAPSHOT_PROP structure. Use the m_pwszSnapshotDeviceObject field to get the device name (e.g. “\Device\HarddiskVolumeShadowCopy1”) for your snapshot. If you created a snapshot for D:\ and you want to access D:\somefile.txt, open \Device\HarddiskVolumeShadowCopy1\somefile.txt.

VSS_SNAPSHOT_PROP prop;

result = backupComponents->GetSnapshotProperties(snapshotId, &prop);

if (!SUCCEEDED(result))
    abort(); // Handle error

// Use prop.m_pwszSnapshotDeviceObject to access your files.

VssFreeSnapshotPropertiesInternal_I(&prop);

Step 6. Cleaning up

You just need one line:

backupComponents->Release();

For more information:

Please leave a comment if you have any questions.

NiceVS makes Visual Studio 2012 usable again

OK, Visual Studio 2012’s new user interface isn’t that bad. But you need to get some serious work done, and you don’t want to be forced to hover your cursor over each monochrome icon to get a tooltip explaining what it’s for. NOR DO YOU WANT THE MAIN MENUS SHOUTING AT YOU ALL THE TIME. That’s why you need to get NiceVS, which restores the old colorful icons and sensible menu labels.

Choose TOOLS > Extensions and Updates…, click Online, and search for NiceVS. Once installed, you will see the following (hilarious) screen:

NiceVS screenshot

Click Yes, and Visual Studio will be back to normal:

NiceVS 2


Links:

EnumWindows no longer finds Metro/Modern UI windows: a workaround

In the final release of Windows 8, the EnumWindows function no longer lists Metro/Modern UI windows:

Note For Windows 8 and later, EnumWindows enumerates only top-level windows of desktop apps.

This change was made some time around the consumer preview release. I’m not sure why Microsoft did this, but there is a simple workaround. Instead of calling EnumWindows, call this function:

VOID EnumWindowsWithMetro(
    __in WNDENUMPROC lpEnumFunc,
    __in LPARAM lParam
    )
{
    HWND childWindow = NULL;
    ULONG i = 0;

    while (i < 1000 && (childWindow = FindWindowEx(NULL, childWindow, NULL, NULL)))
    {
        if (!lpEnumFunc(childWindow, lParam))
            return;

        i++;
    }
}

The reason this works is that FindWindowEx, unlike EnumWindows, does not ignore Metro windows. We just call FindWindowEx in a loop to keep retrieving the next window in the list until there are no more. Note the i < 1000 condition, which is there to prevent infinite loops (highly unlikely but possible, to my knowledge).

ObQueryTypeInfo and NtQueryObject buffer overrun in Windows 8

**** Update: **** Microsoft is now aware of this bug.

Here’s some output from WinDbg on Windows 8 while I was debugging a driver:

Spot the difference

These two UNICODE_STRINGs are from the OBJECT_TYPE structures of the Section and TmTx (transaction) object types. Can you spot the difference between these two strings? The Section string’s MaximumLength includes two extra bytes for a null terminator, while the TmTx string’s MaximumLength doesn’t.

Now take a look at the code for ObQueryTypeInfo, which is called from NtQueryObject when you pass in the ObjectTypeInformation information class. Look out for the buffer overrun at the end. Also notice that the string “TmTx” happens to be 8 bytes long (when using WCHARs).

#define ALIGN_UP(Length, Type) (((Length) + sizeof(Type) - 1) & ~(sizeof(Type) - 1))

NTSTATUS ObQueryTypeInfo(
__in POBJECT_TYPE ObjectType,
__out_bcount(Length) POBJECT_TYPE_INFORMATION ObjectTypeInfo,
__in ULONG Length,
__out PULONG ReturnLength
)
{
    NTSTATUS status;

    __try
    {
        *ReturnLength += sizeof(OBJECT_TYPE_INFORMATION) + ALIGN_UP(ObjectType->Name.MaximumLength, ULONG_PTR);

        if (Length < *ReturnLength)
        {
            status = STATUS_INFO_LENGTH_MISMATCH;
        }
        else
        {
            ObjectTypeInfo->TotalNumberOfObjects = ObjectType->TotalNumberOfObjects;
            // ...
            ObjectTypeInfo->DefaultNonPagedPoolCharge = ObjectType->TypeInfo.DefaultNonPagedPoolCharge;

            ObjectTypeInfo->TypeName.Buffer = (PWSTR)(ObjectTypeInfo + 1);
            ObjectTypeInfo->TypeName.Length = ObjectType->Name.Length;
            ObjectTypeInfo->TypeName.MaximumLength = ObjectType->Name.MaximumLength;

            memcpy(ObjectTypeInfo + 1, ObjectType->Name.Buffer, ObjectType->Name.Length);
            ((PWSTR)(ObjectTypeInfo + 1))[ObjectType->Name.Length / sizeof(WCHAR)] = 0; // **** Oops! ****

            status = STATUS_SUCCESS;
        }
    }
    __except (EXCEPTION_EXECUTE_HANDLER)
    {
        status = GetExceptionCode();
    }

    return status;
}

The solution is pretty simple. Until Microsoft fixes this bug, if you’re calling NtQueryObject with some ObjectInformationLength, make sure you have ObjectInformationLength + 2 bytes allocated in the buffer that you are passing in.