HOME BLOG ARCHIVE TAGS

Another case for indirection: programming handles/descriptors

February 16, 2015

A famous aphorism attributed to David Wheeler states that any problem in computer science can be solved by another indirection. This is an interesting idea (that deserves a post for itself).

The power of indirections can’t be overstated. In his book “Writing Solid Code” (ISBN 1556155514), Steve Maguire presented an interesting indirection idiom, applied to single linked lists (iteration through pointer to pointer; no special code needed, branch prediction and management problems avoided):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
//
// traversing single linked lists through ptr to ptrs avoids
// some pitfalls;
//
typedef struct node_
{
    // (...)
    struct node_ *next;

} node_t;

// (...)

while ( *ppnode != NULL ) {
    ppnode = &(*ppnode)->next;
}

// additions/deletions simplified;

A nice case for indirection happens when we need to implement descriptors (handles and descriptors will be used interchangeably from now on).

Programmers are very familiar with the concept of handles as abstractions for resources (e.g., files, network connections, devices, etc). In fact, Unix-like enthusiasts know by heart that IO descriptors are nothing more than indexes for entries in kernel tables.

By their own nature, handles are usually implemented in terms of opaque ptrs, that provide nice encapsulation and O(1) access to data. The problem with this line of reasoning - where descriptors should always point directly to internal structures - is that a great deal of control can be left out along the way. Using a second indirection level (i.e., ptr to ptrs) buy us a whole deal of flexibility.

This can be seen in Win32 programming all the time (last time I checked, HANDLE declaration was here, but Microsoft keeps breaking MSDN for no apparent reason):

1
typedef void *HANDLE;

After using Win32 HANDLEs, less experienced programmers assume that direct ptrs will always do the job (which isn’t always the case). Declaring HANDLEs like this is just a way to encode the possibility of having enough memory to store any kind of ptr (that can naturally point to anything, including other ptrs). This was not a rule of thumb, saying to developers: “always make your descriptors direct ptrs to dynamic memory.

Recently, I had the displeasure of helping a friend at work fix a legacy MS CryptoAPI project. Unfortunately, every type of handle was implemented as a direct ptr in the codebase. HCRYPTPROV descriptors were malloc’ed ptrs to internal state, making the management of sessions a living hell.

Here is how everything starts when using some CSP:

1
2
3
4
5
BOOL CPAcquireContext(HCRYPTPROV* phProv,
                        WCHAR* pszContainer,
                        DWORD dwFlags,
                        PVTableProvStruc pVTable 
                        );

The moment programmers made CPAcquireContext() return ptr based descriptors - instead of using an additional level of indirection - they deprived themselves of nice control over sessions. One special multithreaded process called the CSP in question with cached HCRYPTPROVs, and it was impossible to manage underlying session context in a “shallow” way.

Making a handle point to a further ptr may put a burden on the side of the implementer. This happens because two dynamic allocations must be made: one for underlying state, and another for the value returned (if you make your descriptor an integer/index - like in Unix - the second allocation comes free, but corresponding table management may get into the way).

In any case, don’t blindly employ one-level direct ptrs. Or assume it’s the only possible alternative. Sometimes, extra levels of indirection are very useful.