gsliepen/tinc — pull request #5 by dechamps (2013-07-20 14:47:56+00:00)
Title: Fixes to the UDP address cache hash table

`hash_function()` is broken. Because of a small mistake in the inner loop, the function will only ever use the first 4 bytes of data, and will never look at the remaining bytes.

Incidentally, the node UDP address cache uses this function with a key of type `sockaddr_in`. This structure contains the IP protocol and port in the first 4 bytes, and the IP address in the remaining bytes. With the broken hash function, this means that all addresses that have the same IP protocol and port will return the same hash.

This is demonstrated by the following test code: https://github.com/dechamps/tinc/compare/1828908...hashtest

Which outputs the following:

Hash test: 10.172.1.1:656 (10.172.1.1 port 656) -> 144
Hash test: 10.172.1.5:656 (10.172.1.5 port 656) -> 144
Hash test: 94.23.24.223:656 (94.23.24.223 port 656) -> 144
Hash test: 127.0.0.1:656 (127.0.0.1 port 656) -> 144
Hash test: 1.2.3.4:656 (1.2.3.4 port 656) -> 144
Hash test: 10.172.1.1:655 (10.172.1.1 port 655) -> 104
Hash test: 10.172.1.5:655 (10.172.1.5 port 655) -> 104
Hash test: 94.23.24.223:655 (94.23.24.223 port 655) -> 104
Hash test: 127.0.0.1:655 (127.0.0.1 port 655) -> 104
Hash test: 1.2.3.4:655 (1.2.3.4 port 655) -> 104
Hash test: 10.172.1.1:42 (10.172.1.1 port 42) -> 80
Hash test: 10.172.1.5:42 (10.172.1.5 port 42) -> 80
Hash test: 94.23.24.223:42 (94.23.24.223 port 42) -> 80
Hash test: 127.0.0.1:42 (127.0.0.1 port 42) -> 80
Hash test: 1.2.3.4:42 (1.2.3.4 port 42) -> 80

To make things worse, tinc's hash table doesn't care about collisions, meaning, two keys with the same hash value will override each other. This means that if two nodes happen to use the same port number, they can't appear in the node UDP address cache at the same time.

Unfortunately, that matches the situation that I put myself in:
- Node "kobol" sits somewhere on the Internet, IP address 94.23.24.223
- Node "zyklos" is on my LAN, local IP address 10.172.1.1
- Node "firefly" is on my LAN, local IP address 10.172.1.5

All these nodes use port 656. Now, here's what happens when LocalDiscovery comes into play:

1. LocalDiscovery succeeds, zyklos and firefly are speaking locally, and their UDP address cache contains each other's local addresses: `[144 (2148532224 % 256 = 144)] 10.172.1.5 port 656 -> firefly`

2. At some point, kobol will attempt to communicate with one of the two nodes. This could happen because they need to negotiate PMTU again, which happens every PingInterval seconds.

3. If communication succeeds over UDP, kobol's address will override the existing contents of the node's UDP address cache: `[144 (2148532224 % 256 = 144)] 94.23.24.223 port 656 -> kobol`

4. As a result, when the node receives data from the other local node, it will not find its address in the UDP address cache and will have to fall back to `try_harder()` to find out from which node it just received data.

5. If one of the nodes starts talking simultaneously with kobol and the other local node (e.g. in my test, the two local nodes are pinging each other while kobol is renegociating PMTU at the same time), then they will constantly override each other in the cache, and `try_harder()` will be called several times per second.

6. Unfortunately, there is what seems to be a "safety" (I'm guessing oracle attack protection) measure in try_harder() that will make it refuse to "try harder" more than one time per second, dropping packets instead.

In summary: when a node is communicating with more than one other node simultaneously, the UDP address cache is constantly being overridden, `try_harder()` is called lots of time per second, and as a result, throughput is limited to at most one packet per second, which is of course completely impractical.