跳至正文

root

在Hifive unmatched上安装FreeBSD

  • 2022-06-262022-06-26

最近手痒想试试FreeBSD,正好FreeBSD ports 也在找一台builder,吴博给我凑了2台Unmatched 跑Linux的Go builder,所以我这台就空出来了~

其实按着官方的教程就好,官方教程:https://wiki.freebsd.org/riscv/HiFiveUnmatched

不过要注意2点!!(花了我两个晚上),一切的错误都从我没仔细看教程开始……第一个错误是直接把FreeBSD的镜像直接烧进了SD卡里!然后以为这就行了~结果发现,其实Unmatched的固件决定了必须从SD上特定的分区才能启动!所以直接烧进SD卡里,应该是根据教程写进一个U盘里。

诡异的是,重新给SD卡烧录了Ubuntu的镜像,系统nvme就因为找不到root直接进(initramfs)了。

我脑子抽了就直接用SD卡里的Ubuntu shell 直接 dd if=/dev/zero of=/dev/nvme0n1 …… 想通过干掉分区表(GPT)来阻止从nvme启动。结果噩梦就开始了,SD卡里的Ubuntu怎么都找不到nvme和U盘了。折腾了一晚没啥收获,第二天不停的重启和对比才发现。UBoot启动的过程中需要启动pci!要不然你怎么执行命令启动USB都是不行的,usb start 就会报错 no working controllers found

所以正确的做法是,在U-boot自动启动过程中先启动pci 子系统

pci enum
setenv boot_targets usb0
boot

最后就是标准的FreeBSD安装流程了~ yes~

Go团队如何解bug[1]: 乱序执行与内存屏障

  • 2020-05-212022-06-19

开篇前言

Go项目在发展过程中有过许许多多的bug,核心开发组在解决bug的时候有各种各样的方法,涉及的知识点都很值得学习。
我觉得这些都挺值得跟大家分享,也希望做成一个不鸽系列。

正题

Issue地址:issues/35541

开发:Cherry Zhang, Michael Knyszek

这个bug是由Go的自动构建机器linux-mipsle-mengzhuo在日常测试过程中首次发现的,
表现是某个对象里的指针指向了一个不存在的span上,导致runtime panic。

Cherry根据 经验 判断出这个span类型是goroutine用的,并且贴出了对应的对象映射(如下)

object=0xc000106300 s.base()=0xc000106000 s.limit=0xc000107f80 s.spanclass=42 s.elemsize=384 s.state=mSpanInUse
*(object+0) = 0xc00052a000 g.stack.lo
*(object+8) = 0xc000532000 g.stack.hi
*(object+16) = 0xc00052a380 g.stackguard0 = g.stack.lo + _Stackguard = g.stack.lo + 896
*(object+24) = 0xffffffffffffffff g.stackguard1
*(object+32) = 0x0 g._panic
*(object+40) = 0xc0005313e0 <== // 故障点 g._defer
*(object+48) = 0xc000080380 g.m
*(object+56) = 0xc0005310b8 g.sched.sp
*(object+64) = 0x87038 g.sched.pc
*(object+72) = 0xc000106300 g.sched.g

虽然Cherry没有明说如何判断出是goroutine,但其中的偏移量24字节处的数据正好是64位的满位,
看起来确实像一般的goroutine的stackguard1 (malg时分配的)

这个bug奇怪的地方在于不是必现,是在不同的函数,时不时runtime panic, 而且出问题的span有时是在用的,有时又是废弃的。
更奇怪的是,RTRK(塞尔维亚的一家科研机构)提供的MIPS构建机从来都没有出现过一次类似原因的runtime panic。

一开始,开发组认为是MIPS的问题,时间长了,发现还有plan9-arm,
darwin-arm64-corellium这两个架构也出现了类似问题,然而出现的频率远不如MIPS高。
因为没有有效解,几乎每周Bryan Mills(负责Go开发质量的工程师)都会在Github Issue中填上新增的panic日志地址,最后他也嫌烦了……

脑袋疼.jpg

问题定位

事情的转机是我有一次debug过程中,发现runtime有个测试函数TestDeferHeapAndStack 总是 会引发这个panic。
而在Go项目的自动化整体测试中,为了测试尽快完成,通常速度慢的机器都会选择short mode,
而恰好这个short mode不会导致panic。

本身这个测试也很有意思,因为编译器只会把函数作用域中无指针的defer分配在stack上,而循环体中的defer就会分配在heap中。

测试用例如下:

func deferHeapAndStack(n int) (r int) {
if n == 0 {
return 0
}
if n%2 == 0 {
// heap-allocated defers
for i := 0; i < 2; i++ {
defer func() {
r++
}()
}
} else {
// stack-allocated defers
defer func() {
r++
}()
defer func() {
r++
}()
}
r = deferHeapAndStack(n - 1)
escapeMe(new([1024]byte)) // force some GCs
return
}

我尝试着自己修复这个bug,然而失败了,不过既然可以稳定重现,那可以帮助核心团队来bisect这个bug。

这个技能是从Austin(Go runtime leader)学来的(他如何从Go定位Linux bug正好可以写下一期哈)。

因为这个bug是从1.13之后才有的,所以我选择了HEAD 和 go1.13.9之间开始定位。

$ git bisect HEAD go1.13.9
$ git bisect run ./test.sh // 就是跑上面deferTest的脚本

最后发现是runtime: rearrange mheap_.alloc* into allocSpan这个commit导致了bug。

修复方法

Cherry在和Michael聊这个bug之后发现在allocSpan的过程中由于缺了一个内存屏障(memory barrier),
在弱内存顺序模型的机器上这个bug会随机出现。以下是她的修复commit:

When copying a stack, we
1. allocate a new stack,
2. adjust pointers pointing to the old stack to pointing to the
new stack.
If the GC is running on another thread concurrently, on a machine
with weak memory model, the GC could observe the adjusted pointer
(e.g. through gp._defer which could be a special heap-to-stack
pointer), but not observe the publish of the new stack span. In
this case, the GC will see the adjusted pointer pointing to an
unallocated span, and throw. Fixing this by adding a publication
barrier between the allocation of the span and adjusting pointers.
One testcase for this is TestDeferHeapAndStack in long mode. It
fails reliably on linux-mips64le-mengzhuo builder without the fix,
and passes reliably after the fix.

简单翻译一下:

当拷贝一个栈数据(stack)时,我们先:
1. 申请一个新的栈空间
2. 将老的栈上的指针(pointer)从老栈指向新栈上。
如果此时在另一个线程并行地执行着GC(垃圾回收),且架构是弱内存顺序模型时,GC可以观察到指针的调整
(例如: gp._defer 就是一个特殊的 heap-to-stack 指针),但是观察不到新的栈分配。
这时GC就会观察到指针分配到了一个没有分配的空间中。
我们通过在分配和调整指针之间添加内存屏障(memory barrier)来修复这个bug。

代码就更简单了,只是在allocSpan的过程中添加了一个函数publicationBarrier()

什么是内存顺序模型可以参考这个系列的文章《Memory Barriers Are Like Source Control Operations》

X86没有问题,是因为强内存模型保证了每个写入操作的顺序能在各个CPU之间保证同步。
而弱内存模型就没有保证这点,所以强制sync

等等,你问为啥ARM没有这个问题?这是玄学(划掉
因为ARM虽然是弱内存模型,但是保证了“Data dependency barrires

所以以后碰到诡异的多线程问题,就先sync(手动狗头

那么什么是内存顺序模型?

咕咕咕……回头再补

多线程问题

MESI

小结

参考资料

[^1] https://blog.golang.org/ismmkeynote
[^2] https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html
[^3] https://zhuanlan.zhihu.com/p/48157076

龙芯 & Golang!

  • 2019-10-042022-06-19

龙芯,不少人都比较陌生,见过的就更少了。

龙芯活着,还在云时代的2019年拯救了一下MIPS这棵34年的枯树。

一点背景故事

事情还要从去18年底,Go的MIPS架构的构建机(builder)集体下线说起。
这里顺便说一下builder的功能,其实就是Go在验证各个平台兼容性用的机器,
主要是各大公司和志愿者捐赠的,绝大部分是国内开发者很少见的PowerPC、ARM、S390X这类ISA,
操作系统更多,具体可以看看build.golang.org

19年4月时,
Go核心团队的Bradfitz发现ImgTec负责的mips、
mipsle、mips64le、mips64(大小端/32/64位)四种机型的builder已经下线半年多了,
根据Go的平台支持条件要求,任何一个架构+操作系统组合都需要有验证机型,否则就要踢出Go的支持列表。
所以Bradfitz发邮件给ImgTec维护者,
收到的只有查无此人的自动回复
他觉得是这哥们离职的原因,
但实际上是2017年底的时候MIPS背后的ImgTec把MIPS卖了……这些builder竟然还多撑了一年。

大概同时,我从国内Go开发大牛Ben那里获得了一台龙芯3A1500,
这台机器是龙芯团队希望能有人维护Go MIPS,毕竟Go已经是云时代的C了,
不少服务是运行在Go的runtime上的,
另一方面docker已经成了事实标准,龙芯云也是基于docker的。
所以把机器寄给了Ben,但Ben忙于工作,我又喜欢多管闲事性能优化……于是我愉快地收下了这台3A1500。

Loongson 3A1500

不过这台机器可能因为暴力的快递摔坏了,一直点不亮,我只好退给了Ben,
从龙梦公司通过古老的转账汇款方式买了一台3A3000。

就在我搜索MIPS可优化点的时候,发现了MIPS要被踢出去的帖子,
所以我回帖说可以让我的这台龙芯替代ImgTec做builder。
经过自己

  1. 编译4.19内核
  2. 申请密钥
  3. 改Go build项目代码
  4. 艰难地设置网络之后

龙芯的builder: linux-mipsle-mengzhuo终于上线了。(名字不是我挑的)
具体的申请builder的wiki可以看这里

龙芯Go现状

毕竟3A3000是16年的CPU,加上是1.5Ghz/8KB L3 Cache/28nm 制程自然也不能和Intel、AMD比。

其他问题嘛……

Unalign access penalty,没有Hyper Threading,SIMD支持也几乎没有。
就算这么多缺陷,龙芯也是目前市面上零售方式能买到的唯一的MIPS架构的CPU了,
MIPS新东家Wave computing是搞AI的,不知道买MIPS来干嘛,架构不发展,只是
开源了r6架构,但是看官网制程还是28nm的……
所以可以说龙芯是MIPS,这个1985年就出现的架构最后脸面了(欢迎打脸)。

大家可以看看龙芯的cpuinfo哈

Linux ls-3a3k 4.19.53+ #1 SMP PREEMPT Wed Jul 10 15:12:52 UTC 2019 mips64 mips64 mips64 GNU/Linux
system type : generic-loongson-machine
machine : loongson,generic
processor : 0
cpu model : Loongson-3 V0.13 FPU V0.1
model name : Loongson-3A R3 (Loongson-3A3000) @ 1450MHz
CPU MHz : 1450.00
BogoMIPS : 2887.52
wait instruction : yes
microsecond timers : yes
tlb_entries : 1088
extra interrupt vector : no
hardware watchpoint : yes, count: 0, address/irw mask: []
isa : mips1 mips2 mips3 mips4 mips5 mips32r1 mips32r2 mips64r1 mips64r2
ASEs implemented : dsp dsp2 vz
shadow register sets : 1
kscratch registers : 6
package : 0
core : 0
VCED exceptions : not available
VCEI exceptions : not available

说到Go在龙芯上的实际性能,通过观察,大概比PPC64、ARM这些builder快点,
Go所有源代码编译+测试一次大概要耗时25分钟左右。

不过我发现不少性能关键路径上的代码甚至都没按一台正常的64位机器写,
而是明显的“能用”的状态,可能和Minux和Cherry移植的时候先让MIPS架构能跑起来有关。
更要命的是,Go不知道为啥,最小版本要求竟然是MIPS III(1993年发布),
想在Go上用常见的优化指令,比如count leading zero(CLZ),
conditional move (CMOV.CON),
BSWAP ( ROR DSHB )
prefech统统都不行……

不过我还是提交了一些优化的CL,平时还要忙无聊的工作,精力有限,目前只有:

未来的展望

如果我能多提交一些bytealg,syscall,SSA相关优化之后应该就能更快点,
就算没有向量优化,硬件指令集,至少总体性能也应该能提升30%左右。
国内我知道在优化的人也就Xenon一个了,如果你也有兴趣搞龙芯Go优化的欢迎联系我。

有可能的话,我也想尽可能地推动核心团队提升Go MIPS的版本,MIPS III 实在是太老了。

同时我也希望各位开发们能借着“国产化”的春风,在工作中多用国产CPU,帮助提升性能,
丰富一下生态,多影响一下上游。至少不是做个冷嘲热讽的键盘侠。顺便祈祷MIPS的新东家Wave computing
不要再搞什么幺蛾子把MIPS真的送进博物馆里了。

最后附上这台builder的样子,毕竟应该是国内第一台在Go项目里的服务器。

LS 3A3K

Go Contributor Summit 2019参会记

  • 2019-08-06

今年有幸去美国圣地亚哥参加了Go Contributor Summit 2019,主要是Go的代码贡献者和核心开发团队在一起讨论关于Go相关的话题。

紧跟着的GopherCon也是第一次换城市到了圣地亚哥,还在中途岛号航母(USS Midway)上搞了欢迎party,真是毕生难忘了。

破冰环节

刚进门,就发现Russ Cox站在门口,跟他打了打招呼,顺便吐槽了一番他的范型设计在国内引起的巨大讨论,不过大佬很快就被其他人抓去讨论别的话题了。
这时热情的Joe Tsai(Protobuf维护者)跟我打招呼,然后给我介绍他认识的Google同事,
但毕竟是大型网友见面会,除了Github上见过照片的,基本都名字对不上脸,大家很腼腆,当然也有像Möhrmann(Google SRE)热心地跑来跑去介绍自己的人。

这么尴尬怎么玩?没事,Google组织方已经想好了,接下来就是破冰环节。

图1

图1: 会议日程表,左spf13 右rsc

其实很简单,就是一桌人按生日的月排序,小的介绍大的。介绍内容除了名字公司以外还要介绍个自己的fun fact,这下真难倒我了,
幸好我的介绍人Julie Qiu(Go文档维护)给我想到了一个,坐了14个小时的飞机第一次来美国(虽然我没get到fun是啥……
轮到我介绍了,正好介绍的是Joe,他的fun fact是一家3姐弟都在Google上班,又一次没get到。
最让我震惊的是Cherry Zhang(ARM/MIPS 维护者)是个妹子!主要是看代码和说话风格,感觉都是个男的,轮到她介绍的时候了才发现是个妹子。

因为是贡献者大会,所以主办方希望大家自选话题并分组讨论各自感兴趣的话题。
大家先头脑风暴,讲出了自己关心的话题,然后经过投票之后,上午的话题分成以下4组:

  1. 编译器
  2. 范型和错误处理
  3. 社区相关问题,发展和规划
  4. 工具相关问题,proxy mod这类

讨论环节

每个组讨论都要选一个负责人来组织讨论,防止一言堂,然后有个两个志愿者来记录一下大家说的话题。
我参加了编译器组,见识到了Keith Randell(编译器维护),Austin Clements(编译器组负责人)和其他大牛们讨论的问题:

  • SSA更加激进地向量优化还是直接提供向量优化包x/vector
  • 怎么让不同架构兼容互通,可以再增加一层高等汇编,白胡子的David Chase(编译器维护)就吐槽当年Sun就类似的替换机制,不过Google的核心开发们纷纷表示没有精力搞。
  • 编译器如何识别用户的可优化Loop pattern,例如for range byte并xor,组里决定还是先试试x/vector
  • goroutine如何绑定CPU核,这里Keith说其实有试验过,很多地方需要调优,但是组内人力实在是不够
  • 增添FDO(feeback-directed optimization)记录运行时数据,形成一个优化profile文件,给下一次编译时提供一个参考。
  • 内部ABI文档构建,Austin说其实Go的ABI已经稳定了,现在就缺人手搞。
  • 添加一个可选参数,把编译时数据发送给Google,好让他们优化(大家纷纷吐槽各种隐私问题

后来的事实证明,我适合去社区相关组,毕竟我在组里几乎没发言,而我又是唯一一个从中国来的开发者,而Go的核心团队相当关心Go在中国的发展。

图2

图2:社区组讨论如何提Bug和proposal,大佬云集

杂事体会

国外开会真心体验到了什么叫人性化,每40分钟就停下来休息,然后每2次休息就有茶歇。这样开会一点都不累。
由于是Contributor Summit,所以是管午饭的,吃的嘛……真不敢恭维,都是三明治+沙拉。
在午饭时,Joe Tsai跟我聊了聊中国用户时怎么使用文档的,我跟他说大家基本都能看懂英语的或者代码,
所以一般不用操心中国用户看文档,当然也聊了protobuf维护的坑啊,中国美国社会、政治问题之类的。
期间还有些其他开发者看到我衣服上的公司名字,跑过来问某鹅怎么用Go啊,中国开发者怎么盗用weather.com的API的这类的事。

还有就是我真心不建议英语不好的朋友来参加,我雅思听力6.5、平时基本能不看字幕看美剧也扛不住各种口音的攻击,特别是8小时的大型听力考试+技术能力考试+时差,
脑子基本转不动了,而且很多俚语和文化确实需要浸入式地学习才能了解,出现了几次全场大笑,我还很懵逼的状态。

总体还是收获特别大,不仅是跟一堆核心开发面对面,而且还认识了不少好朋友哈~

沈阳美签记

  • 2019-07-01

水一篇。

念念不忘,必有回响。

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

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

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

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

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

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

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

东北酸菜饺子

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

沈阳电视塔

沈阳电视塔

好像是图书馆

好像是图书馆

电车

电车

NABHash介绍及原理

  • 2019-05-05

项目地址

github.com/mengzhuo/nabhash

什么是NABHash?

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

有以下特点:

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

性能对比图

![NABHash性能对比图](/2019/05/Hash speed vs size.png)

可以看到,在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支持

  • 2019-04-14

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编码优化小记

  • 2018-11-29

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

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

总结一下

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

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

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

Go ARM64 vDSO优化之路

  • 2018-03-16

背景

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 ARM64 Map优化小记

  • 2018-03-15

背景

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)

如何用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

对于我细致的帮助