水一篇。

念念不忘，必有回响。

这真是对我一直想去美国看看的真实写照。
本来Gopher Contributor Summit并没有邀请我，但是Ben不去参加，把名额转给我了。
我想着我的贡献度远比他低，只是10个左右的CL而已，没想到询问了主办方后2周后，突然就收到了同意参加的邮件。
6月22号填完查户口般的DS160后发现，我应该去的广州领事馆面签预约时间竟然到了一个月以后，可是这个会就在7月23号开了啊。这样肯定是不行的，
四处找啊找，上海、北京也是1个多月，最后在预约栏里发现了“沈阳”这个选项。点进去一看，只要7天！！
最快就是7月1号办！！赶紧买了机票。

以前都是看文章，说什么东三省衰落，落后啥的，没想到飞到沈阳以后发现，压根不是这么回事！
要啥有啥！地铁还比南宁还多！
真是应验了主席的“没有调查就没有发言权”。
坐了出租车到订的“公寓式酒店”，发现真是公寓改的酒店……因为这酒店就在一栋40多层高的高档居民楼里。
不过到的时候凌晨1点了，所以也没看清城市啥样，虽然确实不能和深圳的灯火通明比，但也不算差了。

因为看网上攻略美签不能带手机啥的，只能拿个透明资料袋，又懒得取现金来打车，所以订的酒店就隔了20分钟走路时间。第二天醒了之后时间还早，所以走着去看了看，9点就已经好多人呆在领事馆外头等叫号了。
不过领事馆安保太严了，不让拍照，我前面有个人拍了一张，就被保安追过去，站在身后要求他删掉。

走回酒店的路上发现有个饺子馆，想着午饭就吃个正宗东北酸菜饺子好了。
早饭就匆匆吃了个面包，然后等到时间去做面签。

到了以后，坐在领事馆对面的椅子上，边上的一个妈妈跟我攀谈了起来，问我为啥去，我说开个会，我礼貌性地反问她，她很自豪地说是送女儿上普渡大学。听着很野鸡，但回头一查……常青藤呵呵
就在尴尬的时候，幸好边上一对夫妇听见她也是送小孩上学，就跟她聊了起来，自曝一年要花60万学杂费，好可怕。

轮到我了，跟着前面的人做，拿资料，录指纹。
真的面签了，一个白人大叔，中文问我为啥去美国，我答开会。
然后跟网上攻略一样，他直接英语问工作在哪里，多久了，bla bla，特意问了我是不是做AI相关的开发，还没问我要全家福和资产证明时，就把我的护照收走了，丢了张通过的红纸出来……果然是大厂牌子响么。

离晚上的飞机时间还早，我就吃了个酸菜饺子做午饭，嗯……跟我们家楼下的东北人夫妇开的店里卖的是一个味道，就是皮得多，吃起来有嚼劲。

然后在浑河边上转了转，名不副实，这河清着呢，沈阳还有个比深圳好的一个地方就是，特别凉快～
最后水几张沈阳的照片

沈阳电视塔

好像是图书馆

电车

项目地址

github.com/mengzhuo/nabhash

什么是NABHash？

NABHash 是一种 超级快的 基于AES的非密码学安全哈希算法（Hash Algorithm)

有以下特点：

• 速度快，Intel i7 处理器上（2.6GHz 支持AES硬件）可达到40GB/s处理速度
• 128 位哈希值，不像其他为了快速的哈希算法，产生的哈希值长度过短，NABHash与sha1长度相当。
• 通过所有了SmHasher的测试，雪崩性和分布性良好。
• 针对大数据，大于1024字节时就有优良性能。
• 支持X86、ARMv8平台

性能对比图


可以看到，在65536字节时，NABHash的速度是xxhash、murmur3这些常见快速哈希算法的10倍左右。

为啥可以这么快？

因为“简约”。

一般哈希算法是使用加法、异或、移位完成的（Shift Add XOR）
而哈希算法为了满足雪崩性和分布性，会多计算几轮，导致就算使用SIMD技术，也无可避免性能下降。

这就是NABHash优化的地方，NABHash对于一个16字节数据块，在Intel平台上仅仅使用了1个指令：

AESENC

即AES加密。而选择AES的主要原因是，现在主流的CPU都支持了AES硬件加速（ARM、PPC），而SHA系列虽然有硬件支持，但指令复杂，往往一个数据块还需要多个指令才能完成计算。

主要流程可见下图：

相当于用数据不停地加密初始向量值（0x5A827999 0x6ED9EBA1），最终得到一个哈希值。

可能有些小朋友就会问了，为啥初始向量是这个值，是随机生成的么？不，这是sha1的初始key值。

最后，为啥叫NABHash

因为这是Non-Crypto-Safe AES Based Hash，简写NABHash，基于AES的非密码学安全哈希算法。

Linux的bind REUSEPORT选项是为了充分利用多核CPU，允许不同进程绑定同一个地址+端口号，避免出现仅仅有一个核在处理数据包，其他核闲着的问题。

启用前后的对比图（借用nginx的

不过这么好的特性，Go默认是不开启的，需要自己手动调用net.ListenConfig(Go1.11以上)

一看API就懵了，咋是一个interface……

type ListenConfig struct {
// If Control is not nil, it is called after creating the network
// connection but before binding it to the operating system.
//
// Network and address parameters passed to Control method are not
// necessarily the ones passed to Listen. For example, passing "tcp" to
// Listen will cause the Control function to be called with "tcp4" or "tcp6".
Control func(network, address string, c syscall.RawConn) error
}

这是因为Go有近乎强迫症的向下兼容|backward compatible，不会在已有的接口上添加选项，所以肯定是新开一个API了。但是这个API跟常见POSIX API差太远了，仔细阅读了文档才摸索出下面这个例子:

import (
"net"
"syscall"
"golang.org/x/sys/unix"
)
func newUDPListener(address string) (conn *net.UDPConn, err error) {
// 构造Control闭包
cfgFn := func(network, address string, conn syscall.RawConn) (err error) {
// 构造fd控制函数
fn := func(fd uintptr) {
// 设置REUSEPORT
err = syscall.SetsockoptInt(int(fd),
syscall.SOL_SOCKET,
unix.SO_REUSEPORT, 1)
if err != nil {
return
}
}
if err = conn.Control(fn); err != nil {
return
}
return
}
lc := net.ListenConfig{Control: cfgFn}
lp, err := lc.ListenPacket(context.Background(), "udp", address)
if err != nil {
return
}
conn = lp.(*net.UDPConn)
return
}

效果方面，我的GoNTPD项目一到高峰期就没办法响应太多的请求，导致UDP recv buf 过高，图中的绿线是网卡吞吐量，红线就是UDP recv buf的使用量，越高就说明无法立即处理的请求越多，可以看到更新后，就没有出现UDP recv buf堆积的情况了。

Goost库终于发布了，最开始只有base64和adler32（其实就是捡Go官方废弃的汇编加速代码来）
这次我添加了base64 arm64加速的优化，性能提升不高，也就2x，arm处理器羸弱的流水线这锅是跑不了了。
代码如下：

goost.org/encoding/base64

本文记录一下这两天的思路和总结

base64编码基础

base64很简单，数据按6bit（2^6=64)分隔并转换成可见ASCII编码内的字符就可以了，不是我们常见的8bit分隔。具体可以看Wikipedia，这里就不赘述了。

如何加速？

其实早就人研究好了Base64 encoding with SIMD instructions，只不过没有arm64版本的文章。
这里就大致翻译下上面文章的思路，一些解释和背景讲解：

• 中括号[] 代表一个字节
• aaaaaa代表一个base64字符

在内存里，3个字节数据是这样排布的。

[aaaaaabb][bbbbcccc][ccdddddd]

而我们的目标是：

[__aaaaaa][__bbbbbb][__cccccc][__dddddd]

接下来大致分三步：首先借助的是arm64 的ld3指令将上面的3个连续字符载入至三个不同的向量寄存器v0, v1, v2

v0: [aaaaaabb]....
v1: [bbbbcccc]....
v2: [ccdddddd]....

通过VSHL，VSHR指令，转到四个对应的向量寄存器，以bbbbbb为例：

aaaaaabb << 4 = aabb____
bbbbcccc >> 4 = ____bbbb

接下来用or，mask将bbbbbb保留

最后这步最好玩。arm64支持VTBL（向量查表操作），恰好最多支持4个128bit的表查询（正好64个字节），所以只需要把base64的码表塞进查询向量寄存器中即可

最后st4保存四个向量寄存器到目的地址即可。

总结一下

写的时候还是碰到了一个坑，因为对VSRI和VSHR区别不熟悉，加上Go编译器只支持VSRI（vector shift right and insert)，这个insert会保留原有向量寄存器的数据，导致总是在3/27/53这三个位置的数据不对。浪费了不少时间，下次有不熟悉的指令还是多读读手册。不过误打误撞倒是比原来的作者少了2个指令哈哈。

看原文的时候总是沉不下心，看不懂，下次还是要带着问题读。

解码感觉有些复杂，而且原文的实现不太方便，回头再研究一下。

背景

Go怎么获取当前时间？问一个会Go的程序员，他随手就能写这个出来给你。

import time
time.Now()

这背后是一个系统调用，X86上调用SYSCALL来完成，ARM64上是SVC。

// func walltime() (sec int64, nsec int32)
TEXT runtime·walltime(SB),NOSPLIT,$24-12
MOVW $0, R0 // CLOCK_REALTIME
MOVD RSP, R1
MOVD $SYS_clock_gettime, R8
SVC
MOVD 0(RSP), R3 // sec
MOVD 8(RSP), R5 // nsec
MOVD R3, sec+0(FP)
MOVW R5, nsec+8(FP)
RET

• R0 分别是调用的时钟类型
• R1 是对应的Stack Pointer
• R8 系统调用的ID

很简单吧？但是这里有一个优化点，就是SVC涉及到了内核态和用户态的切换，
其实就是把所有的用户态的寄存器存储在内核的栈上，执行完内核函数之后，再恢复回来。
这一来一回，速度就降下来了……

而时间又是很常见的系统调用，且是只读数据，能不能不切换内核/用户态呢？
Linux内核的开发者们提出了vDSO方案。
通过给每个用户态进程添加一个共享对象（virtual dynamic shared object)来提供一些常见的内核函数
这样就不用切换用户态了。

寻找vDSO

Go对于linux_amd64 vDSO已经优化得很到位了
包括ELF库的解析和使用。比较关键的代码是下面这段。
runtime/vdso_linux_amd64.go

var sym_keys = []symbol_key{
// ...
{"__vdso_clock_gettime", 0xd35ec75, 0x6e43a318, &__vdso_clock_gettime_sym},
}
// initialize with vsyscall fallbacks
var (
// ...
__vdso_clock_gettime_sym uintptr = 0
)

ARM64位也填上一样的值就可以了吧？
然而，现实是，照抄的不行，跟x86的名字和版本都不一样（摔！

man 7 vdso

aarch64 functions
The table below lists the symbols exported by the vDSO.
symbol version
──────────────────────────────────────
__kernel_rt_sigreturn LINUX_2.6.39
__kernel_gettimeofday LINUX_2.6.39
__kernel_clock_gettime LINUX_2.6.39
__kernel_clock_getres LINUX_2.6.39

好好好，我调整一下代码
注意这个后面的0x75fcb89，vDSO代码需要校验，我通过gdb跟踪才最终查到的。

vdso_linux_arm64.go

var vdsoLinuxVersion = vdsoVersionKey{"LINUX_2.6.39", 0x75fcb89}
var vdsoSymbolKeys = []vdsoSymbolKey{
{"__kernel_clock_gettime", 0xd35ec75, 0x6e43a318, &vdsoClockgettimeSym},
}
// initialize to fall back to syscall
var vdsoClockgettimeSym uintptr = 0

发起vDSO call

其实vDSO跟系统调用使用了同样的参数，都是R0 类型，R1 SP, 理论上直接BL 到vDSO函数地址即可。
但不一致的地方是，vDSO需要更大的栈空间。
因此需要切换SP地址到M的第一个g上，即g0，调度器g0栈32K，一般只有2K，如果不是，就查找g0的SP地址并切换，在函数结束时切换回当前的g。

MOVD m_curg(R21), R0 // m_curg 其实是个宏，展开后是取当前m的g0
CMP g, R0
BNE noswitch
MOVD m_g0(R21), R3 // m_g0 也是个宏，展开后就是读取m的g0地址
MOVD (g_sched+gobuf_sp)(R3), R1 // Set RSP to g0 stack
noswitch:
SUB $16, R1
BIC $15, R1 // Align for C code
MOVD R1, RSP

pprof的需求

在完成这部分代码后，我发现Ian加了一个追踪vdso调用的pprof
都是照猫画虎，所以就不提了。

最后的提交

runtime: use vDSO for clock_gettime on linux/arm64

效果能快个66%

name old time/op new time/op delta
TimeNow 442ns ± 0% 163ns ± 0% -63.16% (p=0.000 n=10+10)

不过……内核得支持才行，如果内核没办法使用特定时钟源，还是会进行系统调用。
比如我这块破NanoPC，就不支持

cat /sys/devices/system/clocksource/clocksource0/current_clocksource
source timer

哎……啥时候可以买块Hikey960或者ThunderX2 🙁

2018-04-01 Updates

为什么ARM64下有些内核vDSO比原来还慢呢？
买了块Hikey960试了试，发现还是不能加速vDSO……奇怪了……

我试着在内核里找了找原因。
发现，可能是CPU的bug。

以Linux 4.15 Hikey960为例子。

在/arch/arm64/kernel/vdso/gettimeofday.S
有个宏，每次调用vDSO的vsyscall时，都会检查，而有问题的芯片总是跳到fail上。

 .macro syscall_check fail
ldr w_tmp, [vdso_data, #VDSO_USE_SYSCALL]
cbnz w_tmp, \fail
.endm

这个vdso_data就是指针，#VDSO_USE_SYSCALL对应的是use_syscall

use_syscall在/arch/arm64/kernel/vdso.c)初始化时，会调用时钟驱动里的vdso_direct值。

void update_vsyscall(struct timekeeper *tk)
{
u32 use_syscall = !tk->tkr_mono.clock->archdata.vdso_direct;

而我们的Hikey960用的是arch_sys_counter

~ # cat /sys/devices/system/clocksource/clocksource0/current_clocksource
arch_sys_counter

搜了一下，发现在/drivers/clocksource/arm_arch_timer.c

static struct clocksource clocksource_counter = {
.name = "arch_sys_counter",
.rating = 400,
.read = arch_counter_read,
.mask = CLOCKSOURCE_MASK(56),
.flags = CLOCK_SOURCE_IS_CONTINUOUS,
};

精彩的部分来了！
默认情况下，vdso_default是true的，也就是不用vdso
这个时钟源驱动怎么初始化这个vdso_direct改成false的呢？

 if (wa->read_cntvct_el0) {
clocksource_counter.archdata.vdso_direct = false;
vdso_default = false;
}

继续追下去，发现是

#ifdef CONFIG_HISILICON_ERRATUM_161010101
/*
* Verify whether the value of the second read is larger than the first by
* less than 32 is the only way to confirm the value is correct, so clear the
* lower 5 bits to check whether the difference is greater than 32 or not.
* Theoretically the erratum should not occur more than twice in succession
* when reading the system counter, but it is possible that some interrupts
* may lead to more than twice read errors, triggering the warning, so setting
* the number of retries far beyond the number of iterations the loop has been
* observed to take.
*/
#define __hisi_161010101_read_reg(reg) ({ \
u64 _old, _new; \
int _retries = 50; \
\
do { \
_old = read_sysreg(reg); \
_new = read_sysreg(reg); \
_retries--; \
} while (unlikely((_new - _old) >> 5) && _retries); \
\
WARN_ON_ONCE(!_retries); \
_new; \
})

按理说，这个_new值应该就是>1的，实际上就是bool 的true。这样，vdso_direct就应该是false，即启用vdso了。
但是……我们的CPU 没有通过这个，应该就是CPU的bug了 🙁