TCP 源端口的选择有两个场景：
- 主机场景
- SNAT 场景
先看主机场景，其中又区分了两类互斥的场景：
- bind 时选端口：如果 bind 的端口被某条 established 连接使用，则无法 bind；
- connect 时选端口：如果端口已经被 bind，则无法在 connect 时被选中。
因此必须在 bind 和 connect 之间以及 bind，connect 彼此之间做互斥，遍历某端口的使用链表(bind 只涉及 2 元组，因此只涉及 port hash list)时需要 lock，由于一台主机可能有多个进程同时进行 bind 和 connect，为提高并发能力，Linux 整了个花活儿：
- bind 先遍历奇数端口，再遍历偶数端口；
- connect 先遍历偶数端口，再遍历奇数端口。
这样就巧妙地将 bind 和 connect 的遍历路径错开，沿着这个思路继续，还可以更花，比如在奇数或偶数的遍历空间内，根据进程 pid 再次区分奇偶跨度，比如奇数跨度按 1，5，9，13，… 顺序遍历，而偶数跨度按 3，7，11，… 顺序遍历，诸如此类。
本着 “及时停止优化” 的哲学，审视一下花活的代价是高尚的。
在奇数(或偶数)端口号都已经用尽情况下，花活儿不但发挥不了作用，还平添遍历一边奇数空间的开销，因为在遍历一遍之前，进程并不知道奇数空间已经用尽，虽然可以记录一个 anchor 来记录 “奇数空间已经用尽” 的事实，但本质上这个问题的原因是 16bit 的端口空间在 TCP 看来太少，但对实现时需要遍历时又太大，而之所以搞这些精致的花活儿，还是 16bit 空间太小。
所以不要觉得内核妹忒内儿提的任何派驰都是优化，相当大一部分是在恶心人，它们只是针对了场景，而在这些假设之外，性能反而劣化。这类似抛硬币猜正反，但凡做任何假设，总的成功率都会下降。
再看 SNAT 场景。先看一个没有花活儿的实现(约等于但不等于 Linux 内核 nf_conntrack SNAT 实现)：
uint16 tcp_get_port(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{
struct entry *ent;
int anchor = random16();
int begin = PORT_BASE;
retry:
// 4 元组 hash 而不是 3 元组，防止访问局部性导致 bucket 链表过长
hash = jhash(sip, sport, dip, dport, 2);
uniq = true;
list_for_each_from(ent, bucket[hash]) {
if (ent->sip == sip && ent->dip == dip && ent->sport == sport && ent->dport == dport) {
uniq = false;;
break;
}
}
if (uniq) {
ent = malloc(sizeof(*ent));
ent->sip = sip;
ent->dip = dip;
ent->sport = sport;
ent->dport = dport;
hash_insert(ent, hash);
return sport;
}
if (sport - begin < K && retried ++ > MAX_RETRIES) {
// 列维长跳
if (retried % (MAX_RETRIES/N) == 0)
anchor = random16(;
sport = anchor;
anchor ++;
goto retry;
}
return -1;
}
要整花活儿炫点技巧，一步一步来。
首先，递增 anchor 和列维长跳已够合理，人类文明的轨迹就是列维长跳的结果，典型的大杂居，小聚居对资源利用的合理分布非常有效，正因为此，中原文明才能在几千年时间同化掉整个东亚大陆。然而这太直观了，以至于不够 “厉害”。
如果不使用列维长跳来搜索可用端口，可以用时间戳(精确到 us)，进程 pid 一起组成候选 sport。使用时间戳可以自然跨过同时竞争同一端口的进程，从而减少互斥开销，但还有更好的。
如果系统中已经没有可用端口，在遍历一遍前，进程并不知晓这个事实，因此要引入 “快速失败” 机制。这并不难，只需要提供一些积累信息。于是有以下的算法：
uint16 get_port_new(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{
struct entry3 *ent3;
uint hash3;
hash3 = jhash(sip, dip, dport, 2);
list_for_each_from(ent3, bucket3[hash3]) {
if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {
if (ent3->free = ent3->end) // 已经满了，无空闲端口可用
return -1;
sport = ent3->free + 1;
ent3->free ++;
break;
}
}
if (ent3 == NULL) {
ent3 = malloc(sizeof(*ent3));
free_port_init(ent3);
sport = ent3->free + 1;
hash3_insert(ent3, hash3);
}
return sport;
}
魔鬼在细节，太复杂必然是错的，太简单也可能不对。
随机释放端口意味着端口分配并非连续可得，因此还是要一个一个尝试，于是代码又恢复成了冗杂，3 元组 hash 只是提高了运算复杂度降低的概率，所有的重试依然还要进行：
uint16 tcp_get_port_new(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{
struct entry3 *ent3;
struct entry4 *ent4;
int anchor = -1;
int begin = PORT_BASE;
int find = false;
hash3 = jhash(sip, dip, dport, 2);
list_for_each_from(ent3, bucket3[hash3]) {
if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {
find = true;
uniq = false;;
if (ent3->full)
return -1;
anchor = ent3->free;
break;
}
}
// 有了以上 3 元组 hash 辅助，下面的过程将省去遍历过程，几乎直接找到端口
if (anchor == -1)
anchor = 1;
retry:
// 4 元组 hash 而不是 3 元组，防止访问局部性导致 bucket 链表过长
hash4 = jhash(sip, sport, dip, dport, 2);
uniq = true;
list_for_each_from(ent4, bucket4[hash4]) {
if (ent4->sip == sip && ent4->dip == dip && ent4->sport == sport && ent4->dport == dport) {
uniq = false;;
break;
}
}
if (uniq) {
ent4 = malloc(sizeof(*ent4));
ent4->sip = sip;
ent4->dip = dip;
ent4->sport = sport;
ent4->dport = dport;
if (find == false) {
ent3 = malloc(sizeof(*ent3));
ent3->full = false;
ent3->end = 65535;
hash3_insert(ent3, hash3);
}
ent3->free = sport + 1;
hash4_insert(ent4, hash4);
return sport;
}
if (sport - begin < K && retried ++ > MAX_RETRIES) {
// 列维长跳
if (retried % (MAX_RETRIES/N) == 0)
anchor = random16(;
sport = anchor;
anchor ++;
goto retry;
}
return -1;
}
合适的数据结构上场比算法更能解决大部分问题，就像设置一个 anchor 的威力一样，如果用 stack 或 queue 组织空闲端口，事情就会高尚。
使用 stack 会倾向于使用最近被释放的 port，而使用 queue 则相反，使用最早被释放的 port，以 stack 为例，意思如下：
void free_port(uint16 port, uint32 sip, unit32 dip, uint16 dport)
{
hash3 = jhash(sip, dip, dport, 2);
list_for_each_from(ent3, bucket3[hash3]) {
if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {
sport = ent3->free.push(ent3.port);
break;
}
}
}
uint16 get_port(uint32 sip, unit32 dip, uint16 sport, uint16 dport)
{
struct entry3 *ent3;
struct port_entry *port;
uint hash3;
hash3 = jhash(sip, dip, dport, 2);
list_for_each_from(ent3, bucket3[hash3]) {
if (ent3->sip == sip && ent3->dip == dip && ent3->dport == dport) {
if (ent3->stack.num == 0) // 已经满了，无空闲端口可用
return -1;
port = ent3->free.pop();
break;
}
}
if (port == NULL) {
ent3 = malloc(sizeof(*ent3));
free_port_init(ent3);
hash3_insert(ent3, hash3);
port = ent3->free.pop();
}
return port.num;
}
只要 hash 足够好，源端口几乎可以在 O(1) 时间获得。值得注意的是，stack，queue 与 bitmap 相比具有优势，因为 bitmap 强依赖于实现，可以利用硬件高速实现，也可以使用 for-for 嵌套实现。
这些基本技巧已经谈不上是什么花活，malloc 库函数以及文件系统空闲块管理都会用类似机制管理空闲资源，没什么大不了，但 Linux 内核为什么没有使用这种技巧而遍历端口一个一个尝试呢？
首先是简单性，可维护性，这个不必多说，其次是资源占用，无论 bitmap，stack 还是 queue，动用的数据结构都对内存空间有不同需求，而通用操作系统不能假设空间需求的满足，但却可以用时间换空间。换句话说，内存不足就跑不起来了，而时间复杂度就算再高顶多就是慢，通用系统的可用性指标即程序可以完成。
想要程序运行快，除了算法分析外，局部性一定要利用：
- 时间局部性：针对目标，访问过的网站接下来还会被访问；
- 空间局部性：针对源，相邻 IP 地址会接连发起访问。
正如大约 10 年前我在 nf_conntrack 中加了一个不到 10 行代码的 recent cache 就获得 30%+ 的吞吐性能提升一样，局部性原理几乎控制着一切。
该总结一下了。
不管多么 trick 的算法，不管它多么高效，“及时停止优化” 永远是对的。沉迷于优美的算法将设计一个不优美的传输协议，因为你迫不及待希望用上这个算法，就很容易复制缺陷，在新协议里将 port(or channel，whatever) 继续设置为 16bit，因为只有这样你的算法才能表现出最优解。
但只要把 port(or channel，whatever) 设置成 32bit，一切问题将迎刃而解，但优美算法永远也用不上了。结构决定行为，而不是算法决定行为。
当审视本文描述的所有这一切，如果有人问你到底什么是正确的，他的目的并非要获取一个真正有价值的方案，而是要获得一个和他的想法一致的方案，因为人们总想听到自己想听到的，这是人们成功或失败的根源。
浙江温州皮鞋湿，下雨进水不会胖。
