zhuo/blog

NABHash介绍及原理

项目地址

github.com/mengzhuo/nabhash

什么是NABHash?

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

有以下特点:

性能对比图

NABHash性能对比图

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

为啥可以这么快?

因为“简约”。

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

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

AESENC

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

主要流程可见下图: NABHash流程图

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

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

最后,为啥叫NABHash

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

Go开启UDP SO_REUSEPORT支持

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

启用前后的对比图(借用nginx的 reuseport before after

不过这么好的特性,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堆积的情况了。

UDP recv buf VS throughput

Go ARM64 Base64编码优化小记

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版本的文章。 这里就大致翻译下上面文章的思路,一些解释和背景讲解:

在内存里,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的码表塞进查询向量寄存器中即可 VTBL指令示意

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

总结一下

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

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

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

Go ARM64 vDSO优化之路

背景

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

很简单吧?但是这里有一个优化点,就是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 ARM64 Map优化小记

背景

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

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

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

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

Fishman on Danang Beach

开工

打蛇打七寸,看代码实现自然要先看头。 初始化代码在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。

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

SpongeBob

构建日志

$ ./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

感谢

最后非常感谢

对于我细致的帮助