zhuo/blog

项目地址

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了 :(

背景

Go内置了map类型，而其中重要的哈希算法是一个cityhash的变种。

同时，为了避免哈希冲突攻击（collision attack）和加速哈希计算速度，Keith Randall于Go1.0中就添加了x86_64支持的有硬件加速的AESHASH算法。 我搜遍了互联网，惊讶地发现，这个算法仅仅在Go里面有实现，这思路真是绝了。

这就被我这个四处搜索ARM64 Go runtime待优化点的人找到了：ARM64也支持AESHASH的硬件加速指令，但是Go并没有用上。

我嘴角又微微地一笑，满心欢喜准备加代码。可我并不知道，这看似平静的海面下不知道藏着什么妖怪……

开工

打蛇打七寸，看代码实现自然要先看头。 初始化代码在runtime/alg.go

if (GOARCH == "386" || GOARCH == "amd64") &&
	GOOS != "nacl" &&
	support_aes && // AESENC
	support_ssse3 && // PSHUFB
	support_sse41 { // PINSR{D,Q}
	useAeshash = true
	algarray[alg_MEM32].hash = aeshash32
	algarray[alg_MEM64].hash = aeshash64
	algarray[alg_STRING].hash = aeshashstr
	// Initialize with random data so hash collisions will be hard to engineer.
	getRandomData(aeskeysched[:])
	return
}

可以看到，通过替换algarrary中的hash函数成aeshash，就完成了这个加速替换， 充分考虑了未来其他平台的跟进，赞叹同时感到这个简直就是盛情邀请我来完成接下来的工作。

先看看最简单的aeshash64的具体实现

//func aeshash64(p unsafe.Pointer, h uintptr) uintptr
TEXT runtime·aeshash64(SB),NOSPLIT,$0-24
	MOVQ	p+0(FP), AX	// ptr to data
	MOVQ	h+8(FP), X0	// seed
	PINSRQ	$1, (AX), X0	// data
	AESENC	runtime·aeskeysched+0(SB), X0
	AESENC	runtime·aeskeysched+16(SB), X0
	AESENC	runtime·aeskeysched+32(SB), X0
	MOVQ	X0, ret+16(FP)
	RET

注释也很清晰，AX载入了数据的指针，然后，把map的种子和数据载入X0中等待计算。 这里要说明一下，每个hashmap在初始化的时候都会随机分配一个种子，防止黑客找到系统的种子而发起哈希冲突攻击。 在接下来的几步中，使用程序初始化时生成的随机种子 runtime·aeskeysched 对数据进行加密，最后把结果返回。

更复杂的aeshash也只是加载各种长度进行计算而已。

到这，我只能感叹，这太简单了，便花了两个周末就写完了大体的代码，还碰到了以下问题:

1. 平台差异
2. Smhasher
3. 冲突（Collision）
4. Go编译器bug

平台差异

首先发现的问题是，ARM64并没有X86的AESENC，而是分成两个指令，AESE和AESMC。

先看了看AES的介绍 标准AES加密分成了4步：

1. AddRoundKey
2. SubBytes
3. ShiftRows
4. MixColumns

X86的AESENC指令等价于：

1. SubBytes
2. ShiftRows
3. MixColumns
4. data XOR Key

但是……ARM64的AESE指令等价于：

1. AddRoundKey
2. SubBytes
3. ShiftRows

所以，要是单纯模仿X86的AESENC X0,X0写法时……数据就会被清空掉……（摔。 无奈，只好另寻出路，用系统随机种子加密数据，代码思路如下：

// 把系统种子载入 V1
// 再将种子和数据载入 V2
AESE	V1.B16, V2.B16

SMhasher&Collision

解决了上个问题，开始进行测试。 Go使用的是Smhasher，一个Hash函数是否达标需要通过以下测试：

1. Sanity，必须处理整个key
2. AppendedZeros，填零，长度不同
3. SmallKeys，所有小key（< 3字节）组合
4. Cyclic，循环，例如：11211->11121
5. Sparse，稀疏，例如：0b00001和 0b00100
6. Permutation，组合，每个block排列组合顺序不同
7. Avalanche，翻转每个位
8. Windowed，例如产生的hash值是32位的，那么就20位相同，结果也需要不同
9. Seed，种子变化会影响结果

每一次Smhasher报错，我都开始看代码哪里出了问题，一般都是放错寄存器这些低级错误…… Go还会对map中bucket分配情况进行测试，如果某个bucket放了过多的数据，一样也会出错。 不过，这部分还是比较顺利的。

Go编译器bug

搞定了这个，我又发现另一个坑。 为了减少指令，我希望直接把寄存器中的数据直接载入到ARM64 Vector Lane

但是Go的编译器没办法正确编译不同的lane index。 例如下面两条指令，最终产生的指令码是一样……

VMOV R1, V2.D[0]
VMOV R1, V2.D[1]

只好先报个bug。

cmd/asm: wrong implement vmov/vld on arm64

然后用原生字节码先顶着了，想知道如何做到可以直接拉到Tips

妖怪

终于，所有runtime的Smhasher和Hash测试都通过了，我开始试着运行src/all.bash来构建Go。

这时我拉到了海底的那只妖怪……

构建日志

$ ./all.bash
Building Go cmd/dist using /usr/lib/go-1.6.
Building Go toolchain1 using /usr/lib/go-1.6.
Building Go bootstrap cmd/go (go_bootstrap) using Go toolchain1.
Building Go toolchain2 using go_bootstrap and Go toolchain1.
Building Go toolchain3 using go_bootstrap and Go toolchain2.
# runtime
duplicate type..hashfunc.struct { "".full "".lfstack; "".empty "".lfstack; "".pad0 [64]uint8; "".wbufSpans struct { "".lock "".mutex; "".free "".mSpanList; "".busy "".mSpanList }; _ uint32; "".bytesMarked uint64; "".markrootNext uint32; "".markrootJobs uint32; "".nproc uint32; "".tstart int64; "".nwait uint32; "".ndone uint32; "".alldone "".note; "".helperDrainBlock bool; "".nFlushCacheRoots int; "".nDataRoots int; "".nBSSRoots int; "".nSpanRoots int; "".nStackRoots int; "".markrootDone bool; "".startSema uint32; "".markDoneSema uint32; "".bgMarkReady "".note; "".bgMarkDone uint32; "".mode "".gcMode; "".userForced bool; "".totaltime int64; "".initialHeapLive uint64; "".assistQueue struct { "".lock "".mutex; "".head "".guintptr; "".tail "".guintptr }; "".sweepWaiters struct { "".lock "".mutex; "".head "".guintptr }; "".cycles uint32; "".stwprocs int32; "".maxprocs int32; "".tSweepTerm int64; "".tMark int64; "".tMarkTerm int64; "".tEnd int64; "".pauseNS int64; "".pauseStart int64; "".heap0 uint64; "".heap1 uint64; "".heap2 uint64; "".heapGoal uint64 }
build failed

咦……编译器构建出错？？？ 测试都通过了啊！?

再运行一次all.bash，发现出错的地方还不一样？？？

用gdb断点在我写的asm_arm64.s:aeshash，跟踪执行流程，在对长字符串（>129)哈希也没有问题。 难道是编译器的bug？

所以我开始跟踪编译器的动作，发现只有符号表（symbol）使用了map的功能。 恶补了编译器的基本原理和Go实现后，我才意识到，这个符号表也仅仅用了aeshashstr（对字符做hash）的功能。 我把Smhasher中对aeshash的全部改装成了aeshashstr，发现还是能奇迹般地通过测试！ 手动校验了一次，发现就算把aeshash32和aeshash64都搞得和x86实现一样,包括结果，还是报错！

于是我把这怪异的问题发邮件，发帖子，发群里问遍了所有人。还是无解。

就这样折腾了1个月业余的时间，基本看完了编译器的相关代码， 发现明明是两个不同的符号（symbol）还是会被认为是同一个。 最后还蛋疼地想用钱看看有没有人愿意帮debug一下。 态度惹怒了不少人。我想我是被这bug整得脑子进水了吧……

出坑

直到最近，我才突然意识到没准Smhasher测试并没有覆盖完所有情况？ 果然，仔细检查后在aeshash129plus这一段有

SUBS	$1, R1, R1
BHS	aesloop

这个SUBS是SUB再对比，在R1=1的时候，就退出了。 但Smhasher仅仅对128个字节做了完整的测试，所以测试能通过，但是编译不了。 而这个bug仅仅在256个字节以上才会触发（摔。

改进后是

SUB	$1, R1, R1
CBNZ	R1, aesloop

最终可以提交CL

runtime: implement aeshash for arm64 platform

注意，如果使用PRFM指令，速度能加快30-40MB左右(Hash1024)。可能是下次优化的重点（对齐和Cache)

name                  old speed      new speed      delta
Hash5                 97.0MB/s ± 0%  97.0MB/s ± 0%  -0.03%  (p=0.008 n=5+5)
Hash16                 329MB/s ± 0%   329MB/s ± 0%    ~     (p=0.302 n=4+5)
Hash64                 858MB/s ±20%   890MB/s ±11%    ~     (p=0.841 n=5+5)
Hash1024              3.50GB/s ±16%  3.57GB/s ± 7%    ~     (p=0.690 n=5+5)
Hash65536             4.54GB/s ± 1%  4.57GB/s ± 0%    ~     (p=0.310 n=5+5)

Tips

如何用GNU汇编语言生成原生ARM64指令字节码？

$cat vld.s
ld1 {v2.b}[14], [x0]   

$as -o vld.o -al vld.lis vld.s
AARCH64 GAS  vld.s                      page 1    

   1 0000 0218404D      ld1 {v2.b}[14], [x0] 

其中第三列就是生成的字节码，复制到go中就OK了

WORD $0x4D401802

其实还有工具asm2plan9s, 只是目前这个工具没办法编译ARM64

感谢

最后非常感谢

• Wei Xiao
• Fangming
• Keith Randall

对于我细致的帮助