cgra's

What follows, should be considered EXPERIMENTAL, because:

1. I could be wrong,
2. brain fart this thick is difficult to breathe,
3. nobody else looked yet, and
4. it's not been extensively tested.

Let us proceed. We will first analyze the current situation, then have a look at the proposed solution.

The reader may first want to have a careful look at the patch contents below this article, then resume here to read the whole description.

Current situation

TRB has a bunch of (here, here, and here) out-of-memory DoS issues. This article will attempt to address one specific issue in that group, which is the vNodesDisconnected dumpster, where every disconnected CNode is put on hold for 15 minutes, after being disconnected, and before actually deallocated.

The dumpster mechanism is bad, because:

• It's not necessary (elaborated later), and
• It enables an attacker to waste the target node's RAM just by repeatedly connecting and disconnecting.

Brain Farts of Satoshi, episode ∞ - Ref Counting

Tied to the dumpster mechanism are¹: CNode's AddRef(), Release(), GetRefCount(), nRefCount, and nReleaseTime.

AddRef() and Release() calls should go in pairs, otherwise nRefCount could remain positive, indefinitely. In such cases, the node wouldn't ever get removed from vNodesDisconnected, and deallocated.

These refs are adjusted as follows:

• Increment and decrement for each peer, when beginning and ending a message processing loop in ThreadMessageHandler2() thread.
• Increment and decrement for each peer, when beginning and ending a send()/recv() handling loop in ThreadSocketHandler2() thread.
• Increment on peer's connect-time, when peer gets added to vNodes. Both, inbound and outbound.
• Decrement when disconnected node is moved from vNodes to vNodesDisconnected.
• Increment in a corner case where simultaneously connecting inbound, and outbound, to the same peer, resulting in sharing a CNode object without separate inbound/outbound connections. See next.

In ConnectNode(), an unbalanced AddRef() is theoretically possible: If new inbound peer was connected after the FindNode() call in OpenNetworkConnection(), and before the FindNode() call in ConnectNode(), and also happened to be the same peer our node was about to connect to (ie. ConnectNode()'s parameter addrConnect). Here, the inbound and outbound connection attempts would end up peculiarly sharing the same CNode object.

Otherwise, starting from the last FindNode() call, nothing prevents a peer from creating multiple connections to our node, and if we had an outbound connection already to the peer, we could end up with separate inbound and outbound connections to the same (unlike above, not a shared CNode object).

In the dumpster filling section is an expression that never triggers. The ref count increments for new connections (inbound, outbound) are only balanced with their equivalent decrements after triggering the expression, which is impossible!

Therefore, ref counts are only ever productively read by the check: whether to already delete a disconnected node, or not.

Ref counting is mostly pointless

Because the ref count reading happens in the ThreadSocketHandler2() thread, it's entirely pointless to adjust ref counts in the send()/recv handler (increment, decrement). The ref count reading will never happen at the same time -- both are in different positions of the same thread.

Adjusting the ref count, when peer is being added to, or removed from vNodes (new inbound, new outbound; dumpster load), is similarly pointless, but serves one distinct purpose: Prevent a theoretical risk of a dangling pointer dereference on two rows:

• Patch line 57, a redundant timestamp assignment, and
• patch line 177, an outbound-node-flag assignment, which could easily reside in a thread-safe position.

The last remaining, and within the scope of this patch, fundamentally the only, useful place to adjust the ref count is the ThreadMessageHandler2()'s loop. It signals the deletion code in ThreadSocketHandler2() thread that whether the message handler thread is still actively handling the peer data, or not.

The 15 min dumpster cooldown of disconnected nodes doesn't add to the ref counting anything else, but a loose, extra protection against the marginal dangling pointer dereference risk in OpenNetworkConnection(), at patch line 177: The second FindNode() call could find an existing peer, which the ThreadSocketHandler2() could delete immediately after - now we have a dangling pnode pointer.

Proposed changes

Removals: redundant outbound validation, unbalanced ref count increment, redundant assignment

Repeatedly validating outbound connections (patch lines 164, 165, 28, and 32) is useless, and for the FindNode() check especially, because the acceptance of inbound connections from a single peer IP address is not limited to one only.

The AddRef() by the second FindNode() position is not balanced anywhere, and could cause a stale peer to stick till node restart.

Also, assignment at patch line 57 is already done in CNode constructor, so is redundant. And besides, it marginally risks a dangling pointer dereference, as previously noted.

For these reasons we may remove lines from ConnectNode(), marked by patch lines from 28 to 41, and line 57.

Simplified outbound connection init

We may simplify the OpenNetworkConnection() function to return void, instead of bool, because the return value isn't used anywhere, and it further helps cleaning up the whole function.

The outbound-node-flag assignment from OpenNetworkConnection() should be moved to happen before the new peer gets added to vNodes in ConnectNode(), to avoid one of the marginal risks of a dangling pointer dereference noted earlier.

ConnectNode() would convey it's meaning more accurately, if it didn't return a CNode pointer. Specifically, we don't want to do anything with a node object, when outside of cs_vNodes/ref count guard, to avoid further dangling pointers. So we change the return type to void.

ConnectNode() parameter nTimeout is always 0, so we bolt the value down.

These changes are highlighted by patch lines: 16, 17, 25, 26, 53, 56-62, 155-180, 218 and 219.

Reduce the ref counting to required minimum

Because the AddRef() / Release() / GetRefCount() only make sense in coordinating the stale peer deletion moment, between ThreadMessageHandler2() and ThreadSocketHandler2(), we remove all the other uses:

• From ConnectNode() outbound connection initialization,
• From ThreadSocketHandler2() send()/recv() loop (before loop, after loop), and
• From ThreadSocketHandler2() inbound connection initialization
• From ThreadSocketHandler2() dumpster-loading connection ref count decrement

AddRef()'s nTimeout parameter is never used, we may remove it.

The nReleaseTime will not be used, and must go (patch lines 90, 227, 235 and 250-255). We previously fixed the corner case it was loosely originally protecting -- nReleaseTime won't bed missed.

Because ref count is never 0 at deletion check time, we may remove the expression that never triggers.

Tow away the dumpster

The vNodesDisconnected can go entirely. We will keep the stale nodes in vNodes instead, and they won't stay there for long.

None of the TRY_CRITICAL_BLOCK's were necessary, because:

• The whole dumpster-loading and dumpster-unloading section is surrounded by the cs_vNodes lock
• Either an outer cs_vNodes has us covered, where the other threads may hold these locks (ThreadRCPServer() and ThreadBitcoinMiner(), which only are concerned with relaying either user's transactions, or freshly self-mined blocks), or
• ThreadMessageHandler2() is either sleeping, waiting for cs_vNodes, or signalling own use with an increased ref count

We keep the zero ref count condition, under which the final deallocation may happen, like before.

The outbound/inbound flag check is pointless, because no node may show up here that has both flags false. The only three places where CNode constructor is called, are:

• New inbound peer connection, where fInbound will become true,
• new outbound peer connection, where fNetworkNode will become true, and
• a global pnodeLocalHost object allocation in StartNode()², which is a redundant object, doing nothing of importance.

The 1) removal from vNodes, and 2) CNode deallocation, will happen together, under required conditions. Closing the TCP socket and other cleanup should happen without delay, even if the final deletion had to wait until ThreadMessageHandler2() is done with it's current iteration.

This whole dumpster hauling change is highlighted by the patch lines 70, and 78-118.

Finally, ThreadMessageHandler2() and ThreadSocketHandler2() threads could remain off-sync for a while so that the deletion section didn't immediately coincide with the message handler's sleeping period. For this reason, we're probably better off not letting already disconnected nodes to unnecessarily get locked down by the ref count guard (patch lines 188-198).

In conclusion

Simple as that! Right?

The patch

The patch file and my corresponding signature.

1. See bitcoin/src/net.h, declaration of class CNode [↩]
2. See: bitcoin/src/net.cpp [↩]

I was in a process of writing an explanation for a TRB patch. The changes in question touched TRB's concurrency mechanics, which I thought I had properly already taken into account, but then realized this might've not really been the case. So it was time for some TRB homework: The Threads.

The summary of my study below, is based mostly on these sources:

• A C/C++ threads intro
• An article about memory reordering
• A follow-up article about memory reordering
• Cooperating sequential processes, by E. W. Dijkstra
• GCC manual

I also found Ada's approach to concurrency¹ an interesting, and contrasting read.

Anyway...

The next time I see multi-threaded code, I will remember these four things:

I. Compiler and CPU do not always follow the programmer-specified execution order

The compiler may optimize/reorder code, making it vastly different from what the programmer specified.

The CPU may also reorder code, again, making it different from what the programmer (and compiler!) specified.

The only guiding principle is, that the reorganized program's effect must be exactly the same as the programmer-specified variant would result in. But only in a single-threaded case!

II. Nothing must be assumed of individual thread's relative execution speed

Concurrently running threads' instructions interleave, but there's roughly no guarantee at all, how exactly. If point I above didn't exist, the only guarantee would be that each thread's instructions execute in the specified order, for that thread only.

III. Compiler and CPU memory barriers required for thread synchronization

Compilers and CPU's provide² memory "barriers" or "fences" for the programmer to control the said reordering mechanisms. These are markers, or machine instructions, that are placed in code, where no reordering across that point should happen, if it were to change the running program's current memory state -- compared to what it would've been without any reordering.

In practice, certain implicit compiler barriers also exist, like an external call. Compiler cannot reliably predict the external function's side effects, so it must sync up with the memory state of the programmer-specified program once, before resuming its improv-reordering solo, after the external call has returned.

IV. Usually, simple reads or writes of primitive data types are atomic

From multi-threaded programming's point of view, neither C++ nor GCC, AFAIK, guarantee atomic handling³ for any piece of data, not even for a bool.

CPU manufacturers, on the other hand, specify⁴ which of their CPUs' memory operations are atomic. In x86_64 CPUs, for example, reads and writes up to 64-bit are atomic, if properly aligned.

In practice, handling of the "usual primitive" C++-variables⁵ just happen to be atomic for each individual read or write. And only for that. For example, incrementing a variable, is likely not atomic, because it's not a simple assignment, or a value read.

A couple of practical experiments

A C++ piece, compiled with -O2 optimization:

...and it could result in the following machine code, like in my case:

Notice that there's no loop at all! Here the compiler is not merely reordering, but entirely omitting -- the point I's compiler in full swing.

I also tried out a CPU reordering demonstration, which I copied with some changes, below:

On my machine, it behaved exactly as advertised. I also removed the randomization⁶, and it still behaved the same. So, again, the point I's CPU in full swing.

TRB locks

Underneath the TRB's critical section construct is found the Linux libc pthread library. When a critical section starts, pthread_mutex_lock() is executed. Equally, when a critical section ends, pthread_mutex_unlock() is called. Also, a pthread_mutex_trylock() variation exists.

I dug into TRB's musl libc, looking for clues do pthread_mutex_lock(), or pthread_mutex_unlock() include a CPU memory barrier, or not, and what would such a barrier look like. I found a Linux kernel "futex" syscall, which I further dug into, but could only find suggestive material, and not properly verify the case. The closest I got was that the futex syscall, for x86_64, may contain CPU instructions like:

• LOCK XCHGL
• LOCK XADDL
• LOCK ORL
• LOCK ANDL
• LOCK XORL

Because the pthread lock calls are external calls, likely that alone makes them implicit compiler memory barriers.

Finally

An other type of a concurrency issue...

1. See "Tasks and Synchronization" [↩]
2. Or at least, should provide [↩]
3. Atomicity matters in that sense, that, for example, you only want to read either: 1) an old value of an integer, or 2) a new value, but not 3) a whatever-bit-mixture of both, because the new value's write was in-progress at the moment of the read. [↩]
4. Again, AFAIK. [↩]
5. bool, char, int, long: signed/unsigned; float, double [↩]
6. Shown in the original version [↩]