bpf资料整理以及使用

这个文章 介绍了BPF的基本知识 概念,也有自己的学习资料repo 本文大部分抄自这里 自己的整理记录,复读等于自己也会了!

就是一种vm,之前是class bpf,只做抓数据包,典型应用 tcpdump

架构图

原理图

eBPF 相关的知名的开源项目:

  • Facebook 高性能 4 层负载均衡器 Katran
  • Cilium 为下一代微服务 ServiceMesh 打造了具备API感知和安全高效的容器网络方案;底层主要使用 XDP 和 TC 等相关技术;
  • IO Visor 项目开源的 BCCBPFTraceKubectl-TraceBCC 提供了更高阶的抽象,可以让用户采用 Python、C++ 和 Lua 等高级语言快速开发 BPF 程序;BPFTrace 采用类似于 awk 语言快速编写 eBPF 程序;Kubectl-Trace 则提供了在 kubernetes 集群中使用 BPF 程序调试的方便操作;
  • CloudFlare 公司开源的 eBPF Exporterbpf-toolseBPF Exporter 将 eBPF 技术与监控 Prometheus 紧密结合起来;bpf-tools 可用于网络问题分析和排查;

bcc bpf工具集

我公司的开发机器不支持回去用linux笔记本试试

yum install bcc-tools

/usr/share/bcc/tools/opensnoop 
In file included from <built-in>:2:
/virtual/include/bcc/bpf.h:13:10: fatal error: 'linux/bpf_common.h' file not found
#include <linux/bpf_common.h>
         ^~~~~~~~~~~~~~~~~~~~
1 error generated.
Traceback (most recent call last):
  File "/usr/share/bcc/tools/opensnoop", line 181, in <module>
    b = BPF(text=bpf_text)
  File "/usr/lib/python2.7/site-packages/bcc/__init__.py", line 320, in __init__
    raise Exception("Failed to compile BPF text")
Exception: Failed to compile BPF text

linux支持程度以及对应的版本

工具介绍

execsnoop抓调用,可以抓到slab dentry过大的问题 (经典问题,见过用systemtap抓的。现如今systemtap不如bpf工具好用)

profile抓系统耗时指标

$ profile -af 30 > out.stacks01
$ git clone https://github.com/brendangregg/FlameGraph
$ cd FlameGraph
$ ./flamegraph.pl --color=java < ../out.stacks01 > out.svg

tcplife/tcptracer/tcpstates 抓连接信息/tcp状态/tcp流转状态!这个很牛逼

如何使用bpf定制工具?

  • bpftrace 基本相当于systemtap那种用法了
# 统计进程调用 sys_enter 的次数
#bpftrace -e 'tracepoint:raw_syscalls:sys_enter { @[comm] = count(); }'
Attaching 1 probe...
^C

@[bpftrace]: 6
@[systemd]: 24
@[snmp-pass]: 96
@[sshd]: 125

# 统计内核中函数堆栈的次数
# bpftrace -e 'profile:hz:99 { @[kstack] = count(); }'
Attaching 1 probe...
^C

[...]
@[
filemap_map_pages+181
__handle_mm_fault+2905
handle_mm_fault+250
__do_page_fault+599
async_page_fault+69
]: 12
[...]
@[
cpuidle_enter_state+164
do_idle+390
cpu_startup_entry+111
start_secondary+423
secondary_startup_64+165
]: 22122
  • bcc工具可以照常用,新的工具,建议使用libbpf来写,bcc下面也有例子

https://github.com/iovisor/bcc/tree/master/libbpf-tools 按照

pingcap公司也提供了几个工具

参考

  • 这个文章列了非常多的资料 https://linux.cn/article-9507-1.html 我也转了,做记录备忘

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

(转)(译)深入理解 BPF:一个阅读清单

英语原文链接 https://qmonnet.github.io/whirl-offload/2016/09/01/dive-into-bpf/ 作者:Quentin Monnet 中文翻译 转自 https://linux.cn/article-9507-1.html 感谢 译者:qhwdw 校对:wxy 感谢 Linux中国-LCTT 原创编译!

什么是 BPF?

BPF,及伯克利包过滤器Berkeley Packet Filter,最初构想提出于 1992 年,其目的是为了提供一种过滤包的方法,并且要避免从内核空间到用户空间的无用的数据包复制行为。它最初是由从用户空间注入到内核的一个简单的字节码构成,它在那个位置利用一个校验器进行检查 —— 以避免内核崩溃或者安全问题 —— 并附着到一个套接字上,接着在每个接收到的包上运行。几年后它被移植到 Linux 上,并且应用于一小部分应用程序上(例如,tcpdump)。其简化的语言以及存在于内核中的即时编译器(JIT),使 BPF 成为一个性能卓越的工具。

然后,在 2013 年,Alexei Starovoitov 对 BPF 进行彻底地改造,并增加了新的功能,改善了它的性能。这个新版本被命名为 eBPF (意思是 “extended BPF”),与此同时,将以前的 BPF 变成 cBPF(意思是 “classic” BPF)。新版本出现了如映射和尾调用tail call这样的新特性,并且 JIT 编译器也被重写了。新的语言比 cBPF 更接近于原生机器语言。并且,在内核中创建了新的附着点。

感谢那些新的钩子,eBPF 程序才可以被设计用于各种各样的情形下,其分为两个应用领域。其中一个应用领域是内核跟踪和事件监控。BPF 程序可以被附着到探针(kprobe),而且它与其它跟踪模式相比,有很多的优点(有时也有一些缺点)。

另外一个应用领域是网络编程。除了套接字过滤器外,eBPF 程序还可以附加到 tc(Linux 流量控制工具)的入站或者出站接口上,以一种很高效的方式去执行各种包处理任务。这种使用方式在这个领域开创了一个新的天地。

并且 eBPF 通过使用为 IO Visor 项目开发的技术,使它的性能进一步得到提升:也为 XDP(“eXpress Data Path”)添加了新的钩子,XDP 是不久前添加到内核中的一种新式快速路径。XDP 与 Linux 栈组合,然后使用 BPF ,使包处理的速度更快。

甚至一些项目,如 P4、Open vSwitch,考虑 或者开始去接洽使用 BPF。其它的一些,如 CETH、Cilium,则是完全基于它的。BPF 是如此流行,因此,我们可以预计,不久之后,将围绕它有更多工具和项目出现 …

深入理解字节码

就像我一样:我的一些工作(包括 BEBA)是非常依赖 eBPF 的,并且在这个网站上以后的几篇文章将关注于这个主题。按理说,在深入到细节之前,我应该以某种方式去介绍 BPF —— 我的意思是,真正的介绍,在第一节所提供的简要介绍上更多地介绍在 BPF 上开发的新功能:什么是 BPF 映射?尾调用?内部结构是什么样子?等等。但是,在这个网站上已经有很多这个主题的介绍了,而且,我也不希望去写另一篇 “BPF 介绍” 的重复文章。

毕竟,我花费了很多的时间去阅读和学习关于 BPF 的知识,因此,在这里我们将要做什么呢,我收集了非常多的关于 BPF 的阅读材料:介绍、文档,也有教程或者示例。这里有很多的材料可以去阅读,但是,为了去阅读它,首先要去 找到 它。因此,为了能够帮助更多想去学习和使用 BPF 的人,现在的这篇文章给出了一个资源清单。这里有各种阅读材料,它可以帮你深入理解内核字节码的机制。

资源

简介

这篇文章中下面的链接提供了 BPF 的基本概述,或者,一些与它密切相关的一些主题。如果你对 BPF 非常陌生,你可以在这些介绍文章中挑选出一篇你喜欢的文章去阅读。如果你已经理解了 BPF,你可以针对特定的主题去阅读,下面是阅读清单。

关于 BPF

关于 eBPF 的常规介绍

BPF 内部结构

IO Visor 博客 有一些关于 BPF 的值得关注技术文章。它们中的一些包含了一点营销讨论。

内核跟踪:总结了所有的已有的方法,包括 BPF:

  • 邂逅 eBPF 和内核跟踪 (Viller Hsiao, July 2016):

    Kprobes、uprobes、ftrace

  • Linux 内核跟踪(Viller Hsiao, July 2016):

    Systemtap、Kernelshark、trace-cmd、LTTng、perf-tool、ftrace、hist-trigger、perf、function tracer、tracepoint、kprobe/uprobe …

关于 事件跟踪和监视,Brendan Gregg 大量使用了 eBPF,并且就其使用 eBPFR 的一些案例写了极好的文档。如果你正在做一些内核跟踪方面的工作,你应该去看一下他的关于 eBPF 和火焰图相关的博客文章。其中的大多数都可以 从这篇文章中 访问,或者浏览他的博客。

介绍 BPF,也介绍 Linux 网络的一般概念

硬件卸载offload(LCTT 译注:“卸载”是指原本由软件来处理的一些操作交由硬件来完成,以提升吞吐量,降低 CPU 负荷。):

  • eBPF 与 tc 或者 XDP 一起支持硬件卸载,开始于 Linux 内核版本 4.9,是由 Netronome 提出的。这里是关于这个特性的介绍:eBPF/XDP 硬件卸载到 SmartNICs(Jakub Kicinski 和 Nic Viljoen, netdev 1.2, Tokyo, October 2016)

  • 一年后出现的更新版:

    综合 XDP 卸载——处理边界案例(Jakub Kicinski 和 Nic Viljoen,netdev 2.2 ,Seoul,November 2017)

  • 我现在有一个简短的,但是在 2018 年的 FOSDEM 上有一个更新版:

    XDP 硬件卸载的挑战(Quentin Monnet,FOSDEM 2018,Brussels,February 2018)

关于 cBPF

关于 XDP

  • 在 IO Visor 网站上的 XDP 概述

  • eXpress Data Path (XDP) (Tom Herbert, Alexei Starovoitov, March 2016):

    这是第一个关于 XDP 的演讲。

  • BoF - BPF 能为你做什么? (Brenden Blanco, LinuxCon, Toronto, August 2016)。

  • eXpress Data Path (Brenden Blanco, Linux Meetup at Santa Clara, July 2016):

    包含一些(有点营销的意思?)基准测试结果!使用单一核心:

    • ip 路由丢弃: ~3.6 百万包每秒(Mpps)

    • 使用 BPF,tc(使用 clsact qdisc)丢弃: ~4.2 Mpps

    • 使用 BPF,XDP 丢弃:20 Mpps (CPU 利用率 < 10%)

    • XDP 重写转发(在端口上它接收到的包):10 Mpps

    (测试是用 mlx4 驱动程序执行的)。

  • Jesper Dangaard Brouer 有几个非常好的幻灯片,它可以从本质上去理解 XDP 的内部结构。

    • XDP − eXpress Data Path,介绍及将来的用法 (September 2016):

      “Linux 内核与 DPDK 的斗争” 。未来的计划(在写这篇文章时)它用 XDP 和 DPDK 进行比较。

    • 网络性能研讨 (netdev 1.2, Tokyo, October 2016):

      关于 XDP 内部结构和预期演化的附加提示。

    • XDP – eXpress Data Path, 可用于 DDoS 防护 (OpenSourceDays, March 2017):

      包含了关于 XDP 的详细情况和使用案例,以及 性能测试性能测试结果代码片断,以及使用 eBPF/XDP(基于一个 IP 黑名单模式)的用于 基本的 DDoS 防护

    • 内存 vs. 网络,激发和修复内存瓶颈 (LSF Memory Management Summit, March 2017):

      提供了许多 XDP 开发者当前所面对 内存问题 的许多细节。不要从这一个开始,但如果你已经理解了 XDP,并且想去了解它在页面分配方面的真实工作方式,这是一个非常有用的资源。

    • XDP 能为其它人做什么(netdev 2.1, Montreal, April 2017),及 Andy Gospodarek:

      普通人怎么开始使用 eBPF 和 XDP。这个演讲也由 Julia Evans 在 她的博客 上做了总结。

    • XDP 能为其它人做什么,第二版(netdev 2.2, Seoul, November 2017),同一个作者:

      该演讲的修订版本,包含了新的内容。

(Jesper 也创建了并且尝试去扩展了有关 eBPF 和 XDP 的一些文档,查看 相关节。)

  • XDP 研讨 — 介绍、体验和未来发展(Tom Herbert, netdev 1.2, Tokyo, October 2016)

    在这篇文章中,只有视频可用,我不知道是否有幻灯片。

  • 在 Linux 上进行高速包过滤 (Gilberto Bertin, DEF CON 25, Las Vegas, July 2017)

    在 Linux 上的最先进的包过滤的介绍,面向 DDoS 的保护、讨论了关于在内核中进行包处理、内核旁通、XDP 和 eBPF。

关于 基于 eBPF 或者 eBPF 相关的其它组件

  • 在边界上的 P4 (John Fastabend, May 2016):

    提出了使用 P4,一个包处理的描述语言,使用 BPF 去创建一个高性能的可编程交换机。

  • 如果你喜欢音频的演讲,这里有一个相关的 OvS Orbit 片断(#11),叫做 在边界上的 P4,日期是 2016 年 8 月。OvS Orbit 是对 Ben Pfaff 的访谈,它是 Open vSwitch 的其中一个核心维护者。在这个场景中,John Fastabend 是被访谈者。

  • P4, EBPF 和 Linux TC 卸载 (Dinan Gunawardena 和 Jakub Kicinski, August 2016):

    另一个 P4 的演讲,一些有关于 Netronome 的 NFP(网络流处理器)架构上的 eBPF 硬件卸载的因素。

  • Cilium 是一个由 Cisco 最先发起的技术,它依赖 BPF 和 XDP 去提供 “基于 eBPF 程序即时生成的,用于容器的快速内核强制的网络和安全策略”。这个项目的代码 在 GitHub 上可以访问到。Thomas Graf 对这个主题做了很多的演讲:

    在上述不同的演讲中重复了大量的内容;嫌麻烦就选最近的一个。Daniel Borkmann 作为 Google 开源博客的特邀作者,也写了 Cilium 简介

  • 这里也有一个关于 Cilium 的播客节目:一个是 OvS Orbit episode (#4),它是 Ben Pfaff 访谈 Thomas Graf (2016 年 5 月),和 另外一个 Ivan Pepelnjak 的播客,仍然是 Thomas Graf 关于 eBPF、P4、XDP 和 Cilium 方面的(2016 年 10 月)。

  • Open vSwitch (OvS),它是 Open Virtual Network(OVN,一个开源的网络虚拟化解决方案)相关的项目,正在考虑在不同的层次上使用 eBPF,它已经实现了几个概念验证原型:

    据我所知,这些 eBPF 的使用案例看上去仅处于提议阶段(并没有合并到 OvS 的主分支中),但是,看它带来了什么将是非常值得关注的事情。

  • XDP 的设计对分布式拒绝访问(DDoS)攻击是非常有用的。越来越多的演讲都关注于它。例如,在 2017 年 4 月加拿大蒙特利尔举办的 netdev 2.1 会议上,来自 Cloudflare 的人们的讲话(XDP 实践:将 XDP 集成到我们的 DDoS 缓解管道)或者来自 Facebook 的(Droplet:由 BPF + XDP 驱动的 DDoS 对策)都存在这样的很多使用案例。

  • Kubernetes 可以用很多种方式与 eBPF 交互。这里有一篇关于 在 Kubernetes 中使用 eBPF 的文章,它解释了现有的产品(Cilium、Weave Scope)如何支持 eBPF 与 Kubernetes 一起工作,并且进一步描述了,在容器部署环境中,eBPF 感兴趣的交互内容是什么。

  • CETH for XDP (Yan Chan 和 Yunsong Lu、Linux Meetup、Santa Clara、July 2016):

    CETH,是由 Mellanox 发起的,为实现更快的网络 I/O 而主张的通用以太网驱动程序架构。

  • VALE 交换机,另一个虚拟交换机,它可以与 netmap 框架结合,有 一个 BPF 扩展模块

  • Suricata,一个开源的入侵检测系统,它的旁路捕获旁特性依赖于 XDP。有一些关于它的资源:

    当使用原生驱动的 XDP 时,这个项目要求实现非常高的性能。

  • InKeV:对于 DCN 的内核中分布式网络虚拟化 (Z. Ahmed, M. H. Alizai 和 A. A. Syed, SIGCOMM, August 2016):

    InKeV 是一个基于 eBPF 的虚拟网络、目标数据中心网络的数据路径架构。它最初由 PLUMgrid 提出,并且声称相比基于 OvS 的 OpenStack 解决方案可以获得更好的性能。

  • gobpf - 在 Go 中使用 eBPF (Michael Schubert, fosdem17, Brussels, Belgium, February 2017):

    “一个来自 Go 库,可以去创建、加载和使用 eBPF 程序”

  • ply 是为 Linux 实现的一个小而灵活的开源动态 跟踪器,它的一些特性非常类似于 bcc 工具,是受 awk 和 dtrace 启发,但使用一个更简单的语言。它是由 Tobias Waldekranz 写的。

  • 如果你读过我以前的文章,你可能对我在这篇文章中的讨论感兴趣,使用 eBPF 实现 OpenState 接口,关于包状态处理,在 fosdem17 中。

文档

一旦你对 BPF 是做什么的有一个大体的理解。你可以抛开一般的演讲而深入到文档中了。下面是 BPF 的规范和功能的最全面的文档,按你的需要挑一个开始阅读吧!

关于 BPF

  • BPF 的规范(包含 classic 和 extended 版本)可以在 Linux 内核的文档中,和特定的文件 linux/Documentation/networking/filter.txt 中找到。BPF 使用以及它的内部结构也被记录在那里。此外,当加载 BPF 代码失败时,在这里可以找到 被校验器抛出的错误信息,这有助于你排除不明确的错误信息。

  • 此外,在内核树中,在 eBPF 那里有一个关于 常见问答 的文档,它在文件 linux/Documentation/bpf/bpf_design_QA.txt 中。

  • … 但是,内核文档是非常难懂的,并且非常不容易阅读。如果你只是去查找一个简单的 eBPF 语言的描述,可以去 IO Visor 的 GitHub 仓库,那儿有 它的概括性描述

  • 顺便说一下,IO Visor 项目收集了许多 关于 BPF 的资源。大部分分别在 bcc 仓库的 文档目录 中,和 bpf-docs 仓库 的整个内容中,它们都在 GitHub 上。注意,这个非常好的 BPF 参考指南 包含一个详细的 BPF C 和 bcc Python 的 helper 的描述。

  • 想深入到 BPF,那里有一些必要的 Linux 手册页。第一个是 bpf(2) man 页面 关于 bpf() 系统调用,它用于从用户空间去管理 BPF 程序和映射。它也包含一个 BPF 高级特性的描述(程序类型、映射等等)。第二个是主要是处理希望附加到 tc 接口的 BPF 程序:它是 tc-bpf(8) man 页面,是 使用 BPF 和 tc 的一个参考,并且包含一些示例命令和参考代码。

  • Jesper Dangaard Brouer 发起了一个 更新 eBPF Linux 文档 的尝试,包含 不同的映射他有一个草案,欢迎去贡献。一旦完成,这个文档将被合并进 man 页面并且进入到内核文档。

  • Cilium 项目也有一个非常好的 BPF 和 XDP 参考指南,它是由核心的 eBPF 开发者写的,它被证明对于 eBPF 开发者是极其有用的。

  • David Miller 在 xdp-newbies 邮件列表中发了几封关于 eBPF/XDP 内部结构的富有启发性的电子邮件。我找不到一个单独的地方收集它们的链接,因此,这里是一个列表:

    最后一个可能是目前来说关于校验器的最佳的总结。

  • Ferris Ellis 发布的 一个关于 eBPF 的系列博客文章。作为我写的这个短文,第一篇文章是关于 eBPF 的历史背景和未来期望。接下来的文章将更多的是技术方面,和前景展望。

  • 每个内核版本的 BPF 特性列表 在 bcc 仓库中可以找到。如果你想去知道运行一个给定的特性所要求的最小的内核版本,它是非常有用的。我贡献和添加了链接到提交中,它介绍了每个特性,因此,你也可以从那里很容易地去访问提交历史。

关于 tc

当为了网络目的结合使用 BPF 与 tc (Linux 流量控制traffic control</ruby>工具)时,它可用于收集 tc 的常规功能的信息。这里有几个关于它的资源。

关于 XDP

  • 对于 XDP 的一些 进展中的文档(包括规范) 已经由 Jesper Dangaard Brouer 启动,并且意味着将成为一个协作工作。正在推进的(2016 年 9 月):你期望它去改变,并且或许在一些节点上移动(Jesper 称为贡献,如果你想去改善它)。

  • 自来 Cilium 项目的 BPF 和 XDP 参考指南 … 好吧,这个名字已经说明了一切。

关于 P4 和 BPF

P4 是一个用于指定交换机行为的语言。它可以为多种目标硬件或软件编译。因此,你可能猜到了,这些目标中的一个就是 BPF … 仅部分支持的:一些 P4 特性并不能被转化到 BPF 中,并且,用类似的方法,BPF 可以做的事情,而使用 P4 却不能表达出现。不过,P4 与 BPF 使用 的相关文档,被隐藏在 bcc 仓库中。这个改变在 P4_16 版本中,p4c 引用的编辑器包含 一个 eBPF 后端

教程

Brendan Gregg 为想要 使用 bcc 工具 跟踪和监视内核中的事件的人制作了一个非常好的 教程第一个教程是关于如何使用 bcc 工具,它有许多章节,可以教你去理解怎么去使用已有的工具,而 针对 Python 开发者的一篇 专注于开发新工具,它总共有十七节 “课程”。

Sasha Goldshtein 也有一些 Linux 跟踪研究材料 涉及到使用几个 BPF 工具进行跟踪。

Jean-Tiare Le Bigot 的另一篇文章提供了一个详细的(和有指导意义的)使用 perf 和 eBPF 去设置一个低级的跟踪器 的示例。

对于网络相关的 eBPF 使用案例也有几个教程。有一些值得关注的文档,包括一篇 eBPF 卸载入门指南,是关于在 Open NFP 平台上用 Netronome 操作的。其它的那些,来自 Jesper 的演讲,XDP 能为其它人做什么(及其第二版),可能是 XDP 入门的最好的方法之一。

示例

有示例是非常好的。看看它们是如何工作的。但是 BPF 程序示例是分散在几个项目中的,因此,我列出了我所知道的所有的示例。示例并不是总是使用相同的 helper(例如,tc 和 bcc 都有一套它们自己的 helper,使它可以很容易地去用 C 语言写 BPF 程序)

来自内核的示例

内核中包含了大多数类型的程序:过滤器绑定到套接字或者 tc 接口、事件跟踪/监视、甚至是 XDP。你可以在 linux/samples/bpf/ 目录中找到这些示例。

现在,更多的示例已经作为单元测试被添加到 linux/tools/testing/selftests/bpf 目录下,这里面包含对硬件卸载的测试或者对于 libbpf 的测试。

Jesper 的 Dangaard Brouer 在他的 prototype-kernel 仓库中也维护了一套专门的示例。 这些示例与那些内核中提供的示例非常类似,但是它们可以脱离内核架构(Makefile 和头文件)编译。

也不要忘记去看一下 git 相关的提交历史,它们介绍了一些特定的特性,也许包含了一些特性的详细示例。

来自包 iproute2 的示例

iproute2 包也提供了几个示例。它们都很明显地偏向网络编程,因此,这个程序是附着到 tc 入站或者出站接口上。这些示例在 iproute2/examples/bpf/ 目录中。

来自 bcc 工具集的示例

许多示例都是 与 bcc 一起提供的

  • 一些网络的示例放在相关的目录下面。它们包括套接字过滤器、tc 过滤器、和一个 XDP 程序。

  • tracing 目录包含许多 跟踪编程 的示例。前面的教程中提到的都在那里。那些程序涉及了很大部分的事件监视功能,并且,它们中的一些是面向生产系统的。注意,某些 Linux 发行版(至少是 Debian、Ubuntu、Fedora、Arch Linux)、这些程序已经被 打包了 并且可以很 “容易地” 通过比如 # apt install bcc-tools 进行安装。但是在写这篇文章的时候(除了 Arch Linux),首先要求安装 IO Visor 的包仓库。

  • 也有一些 使用 Lua 作为一个不同的 BPF 后端(那是因为 BPF 程序是用 Lua 写的,它是 C 语言的一个子集,它允许为前端和后端使用相同的语言)的一些示例,它在第三个目录中。

  • 当然,bcc 工具 自身就是 eBPF 程序使用案例的值得关注示例。

手册页面

虽然 bcc 一般很容易在内核中去注入和运行一个 BPF 程序,将程序附着到 tc 接口也能通过 tc 工具自己完成。因此,如果你打算将 BPF 与 tc 一起使用,你可以在 tc-bpf(8) 手册页面 中找到一些调用示例。

代码

有时候,BPF 文档或者示例并不够,而且你只想在你喜欢的文本编辑器(它当然应该是 Vim)中去显示代码并去阅读它。或者,你可能想深入到代码中去做一个补丁程序或者为机器增加一些新特性。因此,这里对有关的文件的几个建议,找到你想要的函数只取决于你自己!

在内核中的 BPF 代码

  • 文件 linux/include/linux/bpf.h 及其相对的 linux/include/uapi/bpf.h 包含有关 eBPF 的 定义,它们分别用在内核中和用户空间程序的接口。

  • 相同的方式,文件 linux/include/linux/filter.hlinux/include/uapi/filter.h 包含了用于 运行 BPF 程序 的信息。

  • BPF 相关的 主要的代码片断linux/kernel/bpf/ 目录下面。系统调用的不同操作许可,比如,程序加载或者映射管理是在文件 syscall.c 中实现,而 core.c 包含了 解析器。其它文件的命名显而易见:verifier.c 包含 校验器(不是开玩笑的),arraymap.c 的代码用于与数组类型的 映射 交互,等等。

  • 有几个与网络(及 tc、XDP )相关的函数和 helpers 是用户可用,其实现在 linux/net/core/filter.c 中。它也包含了移植 cBPF 字节码到 eBPF 的代码(因为在运行之前,内核中的所有的 cBPF 程序被转换成 eBPF)。

  • 相关于 事件跟踪 的函数和 helpers 都在 linux/kernel/trace/bpf_trace.c 中。

  • JIT 编译器 在它们各自的架构目录下面,比如,x86 架构的在 linux/arch/x86/net/bpf_jit_comp.c 中。例外是用于硬件卸载的 JIT 编译器,它们放在它们的驱动程序下,例如 Netronome NFP 网卡的就放在 linux/drivers/net/ethernet/netronome/nfp/bpf/jit.c

  • linux/net/sched/ 目录下,你可以找到 tc 的 BPF 组件 相关的代码,尤其是在文件 act_bpf.c (action)和 cls_bpf.c(filter)中。

  • 我并没有在 BPF 上深入到 事件跟踪 中,因此,我并不真正了解这些程序的钩子。在 linux/kernel/trace/bpf_trace.c 那里有一些东西。如果你对它感 兴趣,并且想去了解更多,你可以在 Brendan Gregg 的演示或者博客文章上去深入挖掘。

  • 我也没有使用过 seccomp-BPF,不过你能在 linux/kernel/seccomp.c 找到它的代码,并且可以在 linux/tools/testing/selftests/seccomp/seccomp_bpf.c 中找到一些它的使用示例。

XDP 钩子代码

一旦装载进内核的 BPF 虚拟机,由一个 Netlink 命令将 XDP 程序从用户空间钩入到内核网络路径中。接收它的是在 linux/net/core/dev.c 文件中的 dev_change_xdp_fd() 函数,它被调用并设置一个 XDP 钩子。钩子被放在支持的网卡的驱动程序中。例如,用于 Netronome 硬件钩子的 ntp 驱动程序实现放在 drivers/net/ethernet/netronome/nfp/ 中。文件 nfp_net_common.c 接受 Netlink 命令,并调用 nfp_net_xdp_setup(),它会转而调用 nfp_net_xdp_setup_drv() 实例来安装该程序。

在 bcc 中的 BPF 逻辑

在 bcc 的 GitHub 仓库 能找到的 bcc 工具集的代码。其 Python 代码,包含在 BPF 类中,最初它在文件 bcc/src/python/bcc/__init__.py 中。但是许多我觉得有意思的东西,比如,加载 BPF 程序到内核中,出现在 libbcc 的 C 库中。

使用 tc 去管理 BPF 的代码

当然,这些代码与 iproute2 包中的 tc 中的 BPF 相关。其中的一些在 iproute2/tc/ 目录中。文件 f_bpf.cm_bpf.c(和 e_bpf.c)各自用于处理 BPF 的过滤器和动作的(和 tc exec 命令,等等)。文件 q_clsact.c 定义了为 BPF 特别创建的 clsact qdisc。但是,大多数的 BPF 用户空间逻辑 是在 iproute2/lib/bpf.c 库中实现的,因此,如果你想去使用 BPF 和 tc,这里可能是会将你搞混乱的地方(它是从文件 iproute2/tc/tc_bpf.c 中移动而来的,你也可以在旧版本的包中找到相同的代码)。

BPF 实用工具

内核中也带有 BPF 相关的三个工具的源代码(bpf_asm.cbpf_dbg.cbpf_jit_disasm.c),根据你的版本不同,在 linux/tools/net/ (直到 Linux 4.14)或者 linux/tools/bpf/ 目录下面:

  • bpf_asm 是一个极小的 cBPF 汇编程序。

  • bpf_dbg 是一个很小的 cBPF 程序调试器。

  • bpf_jit_disasm 对于两种 BPF 都是通用的,并且对于 JIT 调试来说非常有用。

  • bpftool 是由 Jakub Kicinski 写的通用工具,它可以与 eBPF 程序交互并从用户空间的映射,例如,去展示、转储、pin 程序、或者去展示、创建、pin、更新、删除映射。

阅读在源文件顶部的注释可以得到一个它们使用方法的概述。

与 eBPF 一起工作的其它必需的文件是来自内核树的两个用户空间库,它们可以用于管理 eBPF 程序或者映射来自外部的程序。这个函数可以通过 linux/tools/lib/bpf/ 目录中的头文件 bpf.hlibbpf.h(更高层面封装)来访问。比如,工具 bpftool 主要依赖这些库。

其它值得关注的部分

如果你对关于 BPF 的不常见的语言的使用感兴趣,bcc 包含 一个 BPF 目标的 P4 编译器以及 一个 Lua 前端,它可以被用以代替 C 的一个子集,并且(用 Lua )替代 Python 工具。

LLVM 后端

这个 BPF 后端用于 clang / LLVM 将 C 编译到 eBPF ,是在 这个提交 中添加到 LLVM 源代码的(也可以在 这个 GitHub 镜像 上访问)。

在用户空间中运行

到目前为止,我知道那里有至少两种 eBPF 用户空间实现。第一个是 uBPF,它是用 C 写的。它包含一个解析器、一个 x86_64 架构的 JIT 编译器、一个汇编器和一个反汇编器。

uBPF 的代码似乎被重用来产生了一个 通用实现,其声称支持 FreeBSD 内核、FreeBSD 用户空间、Linux 内核、Linux 用户空间和 Mac OSX 用户空间。它被 VALE 交换机的 BPF 扩展模块使用。

其它用户空间的实现是我做的:rbpf,基于 uBPF,但是用 Rust 写的。写了解析器和 JIT 编译器 (Linux 下两个都有,Mac OSX 和 Windows 下仅有解析器),以后可能会有更多。

提交日志

正如前面所说的,如果你希望得到更多的关于一些特定的 BPF 特性的信息,不要犹豫,去看一些提交日志。你可以在许多地方搜索日志,比如,在 git.kernel.org在 GitHub 上、或者如果你克隆过它还有你的本地仓库中。如果你不熟悉 git,你可以尝试像这些去做 git blame <file> 去看看介绍特定代码行的提交内容,然后,git show <commit> 去看详细情况(或者在 git log 的结果中按关键字搜索,但是这样做通常比较单调乏味)也可以看在 bcc 仓库中的 按内核版本区分的 eBPF 特性列表,它链接到相关的提交上。

排错

对 eBPF 的追捧是最近的事情,因此,到目前为止我还找不到许多关于怎么去排错的资源。所以这里只有几个,是我在使用 BPF 进行工作的时候,对自己遇到的问题进行的记录。

编译时的错误

  • 确保你有一个最新的 Linux 内核版本(也可以看 这个文档)。

  • 如果你自己编译内核:确保你安装了所有正确的组件,包括内核镜像、头文件和 libc。

  • 当使用 tc-bpf(用于去编译 C 代码到 BPF 中)的 man 页面提供的 bcc shell 函数时:我曾经必须添加包含 clang 调用的头文件:

    __bcc() {
            clang -O2 -I "/usr/src/linux-headers-$(uname -r)/include/" \
                      -I "/usr/src/linux-headers-$(uname -r)/arch/x86/include/" \
                    -emit-llvm -c $1 -o - | \
            llc -march=bpf -filetype=obj -o "`basename $1 .c`.o"
    }
    

    (现在似乎修复了)。

  • 对于使用 bcc 的其它问题,不要忘了去看一看这个工具集的 答疑

  • 如果你从一个并不精确匹配你的内核版本的 iproute2 包中下载了示例,可能会由于在文件中包含的头文件触发一些错误。这些示例片断都假设安装在你的系统中内核的头文件与 iproute2 包是相同版本的。如果不是这种情况,下载正确的 iproute2 版本,或者编辑示例中包含的文件的路径,指向到 iproute2 中包含的头文件上(在运行时一些问题可能或者不可能发生,取决于你使用的特性)。

在加载和运行时的错误

  • 使用 tc 去加载一个程序,确保你使用了一个与使用中的内核版本等价的 iproute2 中的 tc 二进制文件。

  • 使用 bcc 去加载一个程序,确保在你的系统上安装了 bcc(仅下载源代码去运行 Python 脚本是不够的)。

  • 使用 tc,如果 BPF 程序不能返回一个预期值,检查调用它的方式:过滤器,或者动作,或者使用 “直传” 模式的过滤器。

  • 还是 tc,注意不使用过滤器,动作不会直接附着到 qdiscs 或者接口。

  • 通过内核校验器抛出错误到解析器可能很难。内核文档或许可以提供帮助,因此,可以 参考指南 或者,万不得一的情况下,可以去看源代码(祝你好运!)。记住,校验器 不运行 程序,对于这种类型的错误,记住这点是非常重要的。如果你得到一个关于无效内存访问或者关于未初始化的数据的错误,它并不意味着那些问题真实发生了(或者有时候是,它们完全有可能发生)。它意味着你的程序是以校验器预计可能发生错误的方式写的,并且因此而拒绝这个程序。

  • 注意 tc 工具有一个 verbose 模式,它与 BPF 一起工作的很好:在你的命令行尾部尝试追加一个 verbose

  • bcc 也有一个 verbose 选项:BPF 类有一个 debug 参数,它可以带 DEBUG_LLVM_IRDEBUG_BPFDEBUG_PREPROCESSOR 三个标志中任何组合(详细情况在 源文件中)。 为调试该代码,它甚至嵌入了 一些条件去打印输出代码

  • LLVM v4.0+ 为 eBPF 程序 嵌入一个反汇编器。因此,如果你用 clang 编译你的程序,在编译时添加 -g 标志允许你通过内核校验器去以人类可读的格式去转储你的程序。处理转储文件,使用:

    $ llvm-objdump -S -no-show-raw-insn bpf_program.o
    
  • 使用映射?你应该去看看 bpf-map,这是一个为 Cilium 项目而用 Go 创建的非常有用的工具,它可以用于去转储内核中 eBPF 映射的内容。也有一个用 Rust 开发的 克隆

  • StackOverflow 上有个旧的 bpf 标签,但是,在这篇文章中从没用过它(并且那里几乎没有与新版本的 eBPF 相关的东西)。如果你是一位来自未来的阅读者,你可能想去看看在这方面是否有更多的活动(LCTT 译注:意即只有旧东西)。

更多!

请经常会回到这篇博客中,来看一看 关于 BPF 有没有新的文章!

特别感谢 Daniel Borkmann 指引我找到了 更多的文档,因此我才完成了这个合集。


via: https://qmonnet.github.io/whirl-offload/2016/09/01/dive-into-bpf/

作者:Quentin Monnet 译者:qhwdw 校对:wxy

本文由 LCTT 原创编译,Linux中国 荣誉推出


看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

(译)dd, bs= and why you should use conv=fsync

整理自这篇文章 https://abbbi.github.io/dd/

简单总结

If one uses dd with a bigger block size (>= 4096), be sure to use either the oflag=direct or conv=fsync option to have proper error reporting while writing data to a device. I would prefer conv=fsync, dd will then fsync() the file handle once and report the error, without having the performance impact which oflag=direct has.

用dd的时候尽可能用conv=fsync提前发现system error

作者用dd来做测试,测试盘有坏块的场景

预备工作

 truncate -s 1G /tmp/baddisk
 losetup /dev/loop2 /tmp/baddisk
 dmsetup create baddisk << EOF 
    0 6050 linear /dev/loop2 0
    6050 155 error
    6205 2090947 linear /dev/loop2 6205 
 EOF

可以看到设置之后的盘的属性

fdisk -l

磁盘 /dev/loop2:1073 MB, 1073741824 字节,2097152 个扇区
Units = 扇区 of 1 * 512 = 512 bytes
扇区大小(逻辑/物理):512 字节 / 512 字节
I/O 大小(最小/最佳):512 字节 / 512 字节

可以看到每个扇区是0.5KB

写到错误的位置,也就是6050,需要3M(6050*0.5k)所以,我们调用dd写入4M,肯定就写到错误的地方,就会有报错

但是实际上没有任何报错 算一下 4096*1000就是4M

dd if=/dev/zero of=/dev/mapper/baddisk bs=4096 count=1000
  4096000 bytes (4.1 MB, 3.9 MiB) copied, 0.0107267 s, 382 MB/s

如果不指定bs就会报错,一直写

dd if=/dev/zero of=/dev/mapper/baddisk
 dd: writing to '/dev/mapper/baddisk': Input/output error
 3096576 bytes (3.1 MB, 3.0 MiB) copied, 0.0238947 s, 130 MB/s

抓dmesg的信息,也是有报错的

dmesg
[8807366.717526] Buffer I/O error on device dm-0, logical block 766
[8807366.718560] lost page write due to I/O error on dm-0

为什么dd命令不报错?

strace抓信息

我这里抓的是这样的

open("/dev/mapper/baddisk", O_WRONLY|O_CREAT|O_TRUNC, 0666) = 3
dup2(3, 1)                              = 1
close(3)  = 0
read(0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"..., 4096) = 4096
write(1, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"..., 4096) = 4096
read(0, "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"..., 4096) = 4096

可见打开文件读写都没遇到报错,如果强制加上O_DIRECT O_SYNC之类的符号,就会报错了

背后的细节问题: Linux内核buffered IO影响,有buffered IO,写入不是立即的

而且,对于buffered IO遇到的硬件异常,api是不能立刻感知到的,只有写回的时候才会感知到,所以才有这个问题

指定两个FLAG中的一个就解决了这个问题 ,oflag=direct慢一鞋,相当于O_SYNC O_DIRECT组合,conv=fsync更好一些

buffered-io原理

当然面对这个问题,即buffered IO写入遇到硬件层异常,在写回时才出错,如何提前感知错误,也有很多讨论

比如这个SO问题

答主Craig Ringer 也是pg开发人员,遇到了这个问题,解决方案就是用fsync要检查错误

引述一下他的回答:如果以为用fsync(循环调用fsync直到成功)就万事大吉,那就错了

换句话说如果fsync遇到错误,那就是硬件有问题,应该abort退出

which is then detected by wait_on_page_writeback_range(...) as called by do_sync_mapping_range(...) as called by sys_sync_file_range(...) as called by sys_sync_file_range2(...) to implement the C library call fsync().

But only once!

This comment on sys_sync_file_range

168  * SYNC_FILE_RANGE_WAIT_BEFORE and SYNC_FILE_RANGE_WAIT_AFTER will detect any
169  * I/O errors or ENOSPC conditions and will return those to the caller, after
170  * clearing the EIO and ENOSPC flags in the address_space.

suggests that when fsync() returns -EIO or (undocumented in the manpage) -ENOSPC, it will clear the error state so a subsequent fsync() will report success even though the pages never got written.

Sure enough wait_on_page_writeback_range(...) clears the error bits when it tests them:

301         /* Check for outstanding write errors */
302         if (test_and_clear_bit(AS_ENOSPC, &mapping->flags))
303                 ret = -ENOSPC;
304         if (test_and_clear_bit(AS_EIO, &mapping->flags))
305                 ret = -EIO;

So if the application expects it can re-try fsync() until it succeeds and trust that the data is on-disk, it is terribly wrong.

另外在4.9之后的新内核,直接返回EIO,综上,要判定fsync返回EIO

作者的验证代码在这 https://github.com/ringerc/scrapcode/blob/fd71dffea787847d303e22db95e8b6ca23d06a6d/testcases/fsync-error-clear/standalone/fsync-error-clear.c

作者在PG的讨论串在这里https://www.postgresql.org/message-id/flat/CAMsr%2BYE5Gs9iPqw2mQ6OHt1aC5Qk5EuBFCyG%2BvzHun1EqMxyQg%40mail.gmail.com#CAMsr+YE5Gs9iPqw2mQ6OHt1aC5Qk5EuBFCyG+vzHun1EqMxyQg@mail.gmail.com

另外LWN有两个帖子

https://lwn.net/Articles/724307/

https://lwn.net/Articles/752063/

也介绍了关于这个问题相关的内核应该做的改动,更好的IO错误处理,此处不提


ref

  • https://hustcat.github.io/blkcg-buffered-io/ 博客也不错,好像没做seo

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

c++参数传值以及move

https://xania.org/202101/cpp-by-value-args

就是使用move需要注意的地方,取决于原来的值到底能不能move,move就是偷,掏空

作者贴了一个对比 https://godbolt.org/z/G4hYrT

注意到一个调用了一次 std::string::_M_create 另一个调用了两次,

这两种accessor 一种是传值 move,一种是传const引用 (不是常量引用是编不过的)

//调用一次_M_create
#include <string>

struct Thing {
  std::string s_;
  void set_s(std::string s) { s_ = std::move(s); }
};

void test(Thing &t) {
  t.set_s("this is a long string to show something off");
}
//调用两次_M_create
#include <string>

struct Thing {
  std::string s_;
  void set_s(const std::string &s) { s_ = s; //s_ = std::move(s); }
};

void test(Thing &t) {
  t.set_s("this is a long string to show something off");
}

为什么结果不同?主要原因是常量引用初始化之后,根本无法调用move,于是又拷贝构造一遍,所以调用两次create

而第一种写法,只一次构造。这也是现在推荐的accessor的写法

PS: 另外,测试代码的string要足够长 > 24,不然会有SBO优化,不会调用M_create

不过小串的版本,move也是要比传常量引用要省的 看这个对比 https://godbolt.org/z/xr1bno

PPS: 如果参数是unique_ptr

#include <string>
#include <memory>
struct Thing {
  std::unique_ptr<std::string> s_;
  void set_s(std::unique_ptr<std::string> s) { s_ = std::move(s); }
};

void test(Thing &t) {
  auto s = std::make_unique<std::string>("this is a long string to show something off")
  //t.set_s(s);
  t.set_s(std::move(s));
}

传参数不能发生构造,必须强制move,不move直接编译不过,也不能直接传右值

PPPS:

如果是循环中调用setter,可能分配会更多

std::string s;
Thing t;
for (int i = 0 ; i < 900 ; ++i) {
  set_next_string(s, i);
  t.set_s(s);
}

不过作为setter/accessor,不像是正常人的用法,这种场景下,s_是最开始有分配,后面有足够的空间,能省一些malloc,但是传右值+move绝对会多次malloc

如果能保证s的声明周期,并不是非得落在Thing中,那么用std::string_view会更好。

没有绝对正确的方案,取决于你怎么用


看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

用python做个小调试器

翻译整理自这几片文章 链接1

作者自制了个语言 设计到底层原语的调试,需要调试器,他用 python-ptrace library, pyelftoolsdistorm3 糊了一个

下面是介绍

先安装

pip3 install python-ptrace

然后执行下面的python语句,注意: a.out 随便写个c程序,生成可执行文件,这个程序不能直接退出,否则会出现错误

ptrace.error.PtraceError: ptrace(cmd=16, pid=30165, 0, 0) error #1: Operation not permitted

这个错误会误导你以为什么系统错误,实际上不是的,进程pid不在strace肯定错误的

作者的代码是这样的

#include <stdio.h>
#include <unistd.h>

int my_var;
typedef int (*func_ptr_t)(void);

void test_function(){
  printf("Called test_function! Probably from the debugger.\n");
  printf("my_var=%i\n", my_var);
}

int main(){
  printf("Starting main loop\n");
  my_var = 1;
  while (1){
    usleep(100000);
  }
}

python脚本准备

import ptrace.debugger
import subprocess
shell_command = ["./a.out"]
child_proc = subprocess.Popen(shell_command)
pid = child_proc.pid
debugger = ptrace.debugger.PtraceDebugger()
process = debugger.addProcess(pid, False)

这样就有了一个简单的调试环境,和操作gdb是一样的,不过更清晰一些

获取寄存器

regs = process.getregs()
registers = {k:getattr(regs, k) for k in dir(regs) if not k.startswith('_')}
registers
{'cs': 51, 'ds': 0, 'eflags': 582, 'es': 0, 'fs': 0, 'fs_base': 139788087355200, 'gs': 0, 'gs_base': 0, 'orig_rax': 35, 'r10': 140721172406752, 'r11': 582, 'r12': 4195536, 'r13': 140721172408432, 'r14': 0, 'r15': 0, 'r8': 18446744073709551615, 'r9': 0, 'rax': 18446744073709551100, 'rbp': 140721172408208, 'rbx': 0, 'rcx': 18446744073709551615, 'rdi': 140721172408176, 'rdx': 0, 'rip': 139788083114400, 'rsi': 0, 'rsp': 140721172408168, 'ss': 43}

读内存

import binascii
binascii.hexlify(process.readBytes(registers['rsp'], 8))
b'd4be0cf3227f0000'

单步执行汇编

process.getreg('rip')  #139788083114406
process.singleStep()
process.getreg('rip') #139788083114408

触发信号

import signal
process.waitSignals(signal.SIGTRAP)

这里是埋信号,后面主动写寄存器出发

也可以把这两步结合起来

def step():
    process.singleStep()
    process.waitSignals(signal.SIGTRAP)

Int 3触发,对应0xCC

直接写入

process.writeBytes(process.getreg('rip'), bytes(0xCC))
process.cont()
process.waitSignals(signal.SIGTRAP)

ref

  • 作者的演示代码仓库 https://github.com/asrp/ptracedbg/blob/master/
  • strace遇到错误的解决方案 https://blog.packagecloud.io/eng/2015/11/15/strace-cheat-sheet/

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

实现一个benchmark cli应该考虑点啥

benchmark的典型架子,网络端

  • 多线程worker,worker死循环干活
  • 统计信息,统计p99统计
  • 后台线程实时打印qps/打印进度条
  • 参数读取
  • 日志打印设计,日志要方便解析,最好支持open traceing那种,这样不用人来看了
    • 还可以设计unique id,这样来区分不同的bench
  • 数据打印更直观一些histogram

一个典型的例子是memtier-benchmark,多线程worker,worker内部潜入libevent填数据,这个架构

cli典型架子

  • repl 循环

  • 补全

  • 参数读取

典型例子redis-cli

Arangodb 的cli/bench就设计的很有意思,值得解读并把他的代码抽出来抽成公共库


ref

  • https://clig.dev/

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

实现类型为key的map

翻译整理自这篇文章,加了点自己的理解

类型为key,value不重要,以string举例

其实主要就是解决类型的映射,如何把类型映射成什么东西,肯定离不开模版就是了

静态map

先说一种static compile time map的方法,也就是模版偏特化

形状可以是这样的

template<typename K, typename V>
struct TypeMap { static const V v;}

然后根据不同的K来偏特化

这里弱化一下,用string举例,去掉V

#include <iostream>
#include <string>
template <typename T>
struct StringAnnotationTypeMap { static const std::string annotation; };
//故意不实现,这样没注册的类型会直接link error
//template <typename T>                         
//const std::string StringAnnotationTypeMap<T>::annotation = "default";

#define _TYPE_REGISTER(T, s)                            \
template <>                                                   \
const std::string StringAnnotationTypeMap<T>::annotation = (s);\
template <>                                                   \
const std::string StringAnnotationTypeMap<T&>::annotation = (s)
//这个T&是为了方便从指针推导出类型的特化

#define __STR(x) #x
#define _STR(x) __STR(x)
// 这个宏的目的是拼不同的类型
// 在rpc场景下,rpc函数名, rpc的request response参数都有相同的前缀
// 通过宏帮忙拼接出 参数 < - > rpc函数名字的映射
#define REQ(F) _TYPE_REGISTER(F##Request, _STR(F))
#define RSP(F) _TYPE_REGISTER(F##Response, _STR(F))

struct ARequest{};
struct BResponse{};
REQ(A);
RSP(B);

int p(const std::string & a) {
    std::cout<<a<<'\n';
    return 0;
}

int main() {
  p(StringAnnotationTypeMap<ARequest>::annotation);
  p(StringAnnotationTypeMap<BResponse>::annotation);
  BResponse *p;
  p(StringAnnotationTypeMap<decltype(*p)>::annotation);
}

这个方案用用还行,缺点是必须在编译期间就定好。

如果想要runtime方案,如何设计?

运行时typemap

考虑ECS设计模式 可以看这个链接简单了解,不是本文的重点

大概意思就是尽可能的组件化,每个组件有各自的侵入方法,更灵活的组装实现

而不是去操作一个大的数据结构,对数据结构提供N个接口

每个Entity对应一个实例,每个组件是Component

不想让Entity和具体的Component绑定,那就需要一个字符串 <->类型的typemap来辅助,运行时注册

下面举例

class Entity {
public:
// ...
  AbstractComponent* get (const std::string &component_name) {
    auto it = m_components.find(component_name);
    assert(it != m_components.end());
    return it->second.get();
  }

private:
  std::unordered_map<std::string, std::unique_ptr<AbstractComponent>> m_components;
//...
};

至于component,继承基类就可以

class HitPointComponent : public AbstractComponent {
public:
  void takeHitFrom(const Entity *other_entity);
  void add(int hp);
  void setCurrentCap(int c);
  
private:
  int m_hitPoints;  // amount of hitpoints, can't be greater than m_currentCap
  int m_currentCap; // maximum amount of hitpoints
};

调用就这个德行

dynamic_cast<HitPointComponent>(player->get("HitPointComponent"))->takeHitFrom(projectile)

就是看着闹心,犯个错实在太轻松,core给你看

我们需要type map,而不是type-string map

既然有类型type,提供类型模版接口,帮助指针转换, 类似这种用法

auto e = std::make_unique<Entity>();
e->provideComponent<HitPointComponent>(std::make_unique<HitPointComponent>());
//...
e->get<HitPointComponent>()->takeHitFrom(projectile);

增加与调用接口需要指定参数类型,也就是说子类的信息没丢,那么,基类实际上不需要放接口,只需要定义虚析构函数就行了

如何实现typemap 之保存类型信息

首先考虑的就是type_info 返回整数

这里要考虑两个问题,1 是type_info的实现是依赖RTTI的,2是type_info是内部调用hash_code,这个实现是不透明的,换言之,这个返回值是不是唯一的,不能保证,只能确定同一个类型肯定返回同一个值

解决方案,自己引入一个getTypeId 保证每个类型的值唯一,一个很简单的唯一方法,自增id

// In a header file:
#include <atomic>

extern std::atomic_int TypeIdCounter;

template <typename T>
int getTypeId() {
  static int id = ++TypeIdCounter;
  return id;
}

// In a *.cpp file:
std::atomic_int TypeIdCounter(0);

当然,如果是单线程,可以用int代替atomic_int

这样,调用一次,就会特化一次,而且每个类型的id是不同的,在不同的翻译单元(TU)里,这就保证了id唯一

有唯一id之后,再保存一个id < - > value 就可以了,当然value是模版,随便是什么都可以

#include <unordered_map>
#include <atomic>

template <class ValueType>
class TypeMap {
  // Internally, we'll use a hash table to store mapping from type
  // IDs to the values.
  typedef std::unordered_map<int, ValueType> InternalMap;
public:
  typedef typename InternalMap::iterator iterator;
  typedef typename InternalMap::const_iterator const_iterator;
  typedef typename InternalMap::value_type value_type;

  const_iterator begin() const { return m_map.begin(); }
  const_iterator end() const { return m_map.end();  }
  iterator begin() { return m_map.begin();  }
  iterator end() { return m_map.end(); }

  // Finds the value associated with the type "Key" in the type map.
  template <class Key>
  iterator find() { return m_map.find(getTypeId<Key>());  }

  // Same as above, const version
  template <class Key>
  const_iterator find() const { return m_map.find(getTypeId<Key>()); }

  // Associates a value with the type "Key"
  template <class Key>
  void put(ValueType &&value) {
    m_map[getTypeId<Key>()] = std::forward<ValueType>(value);
  }  

private:
  template <class Key>
  inline static int getTypeId() {
    static const int id = LastTypeId++;
    return id;
  }

  static std::atomic_int LastTypeId;
  InternalMap m_map;
};

template <class ValueType>
std::atomic_int TypeMap<ValueType>::LastTypeId(0);

这样用起来就是这样的

TypeMap<std::string> tmap;
tmap.put<int>("integers!");
tmap.put<double>("doubles!");
std::cout << tmap.find<int>()->second << "\n";

最终回到ECS模型上来,把Component做Value,问题就解决了

class Entity {
public:
// ...
  template <typename Component>
  Component* get() {
    auto it = m_components.find<Component>();
    assert(it != m_components.end());
    return static_cast<Component*>(it->second.get());
  }
  
  template <typename Component>
  void provideComponent(std::unique_ptr<Component> &&c) {
    m_components.put<Component>(std::forward<std::unique_ptr<Component>>(c));
  }

private:
  TypeMap<std::unique_ptr<AbstractComponent>> m_components;
//...
};

老知识,新复习


update 2021-01-10-20-14

其实这种模式,如果是全局的组件,用type_id就够用了,以arangodb为例子,全局server有个addFeature和getFeature接口,思路和上面基本一致,这里把代码贴出来

其中_features就是type map

class ApplicationServer {
  using FeatureMap =
      std::unordered_map<std::type_index, std::unique_ptr<ApplicationFeature>>;
  ApplicationServer(ApplicationServer const&) = delete;
  ApplicationServer& operator=(ApplicationServer const&) = delete;
////省略一部分代码
 public:
   // adds a feature to the application server. the application server
   // will take ownership of the feature object and destroy it in its
   // destructor
   template <typename Type, typename As = Type, typename... Args,
             typename std::enable_if<std::is_base_of<ApplicationFeature, Type>::value, int>::type = 0,
             typename std::enable_if<std::is_base_of<ApplicationFeature, As>::value, int>::type = 0,
             typename std::enable_if<std::is_base_of<As, Type>::value, int>::type = 0>
   As& addFeature(Args&&... args) {
     TRI_ASSERT(!hasFeature<As>());
     std::pair<FeatureMap::iterator, bool> result =
         _features.try_emplace(std::type_index(typeid(As)),
                           std::make_unique<Type>(*this, std::forward<Args>(args)...));
     TRI_ASSERT(result.second);
     result.first->second->setRegistration(std::type_index(typeid(As)));
#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
     auto obj = dynamic_cast<As*>(result.first->second.get());
     TRI_ASSERT(obj != nullptr);
     return *obj;
#else
     return *static_cast<As*>(result.first->second.get());
#endif
   }

   // checks for the existence of a feature by type. will not throw when used
   // for a non-existing feature
   bool hasFeature(std::type_index type) const noexcept {
     return (_features.find(type) != _features.end());
   }

   // checks for the existence of a feature. will not throw when used for
   // a non-existing feature
   template <typename Type, typename std::enable_if<std::is_base_of<ApplicationFeature, Type>::value, int>::type = 0>
   bool hasFeature() const noexcept {
     return hasFeature(std::type_index(typeid(Type)));
   }

   // returns a reference to a feature given the type. will throw when used for
   // a non-existing feature
   template <typename AsType, typename std::enable_if<std::is_base_of<ApplicationFeature, AsType>::value, int>::type = 0>
   AsType& getFeature(std::type_index type) const {
     auto it = _features.find(type);
     if (it == _features.end()) {
       throwFeatureNotFoundException(type.name());
     }
#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
     auto obj = dynamic_cast<AsType*>(it->second.get());
     TRI_ASSERT(obj != nullptr);
     return *obj;
#else
     return *static_cast<AsType*>(it->second.get());
#endif
   }

   // returns a const reference to a feature. will throw when used for
   // a non-existing feature
   template <typename Type, typename AsType = Type,
             typename std::enable_if<std::is_base_of<ApplicationFeature, Type>::value, int>::type = 0,
             typename std::enable_if<std::is_base_of<Type, AsType>::value || std::is_base_of<AsType, Type>::value, int>::type = 0>
   AsType& getFeature() const {
     auto it = _features.find(std::type_index(typeid(Type)));
     if (it == _features.end()) {
       throwFeatureNotFoundException(typeid(Type).name());
     }
#ifdef ARANGODB_ENABLE_MAINTAINER_MODE
     auto obj = dynamic_cast<AsType*>(it->second.get());
     TRI_ASSERT(obj != nullptr);
     return *obj;
#else
     return *static_cast<AsType*>(it->second.get());
#endif
   }

   // map of feature names to features
   FeatureMap _features;
}

其实可以把type_index和type_info隐藏的更深一些,不提供type_index的接口,这样背后替换更轻松一些

使用时这样的

    ApplicationServer server(options, SBIN_DIRECTORY);
//...
    // Adding the Phases
    server.addFeature<AgencyFeaturePhase>();
    server.addFeature<CommunicationFeaturePhase>();
    server.addFeature<AqlFeaturePhase>();
    server.addFeature<BasicFeaturePhaseServer>();
    server.addFeature<ClusterFeaturePhase>();
//...

效果类似


ref

  • https://gpp.tkchu.me/ 意外找到了游戏编程模式的中文翻译
  • Arangodb 源码 https://github.com/arangodb/arangodb

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

12月待读

http://ot-note.logdown.com/posts/231212/compile-time-constant-comparison-take-the-character-the-length-of-the-string-test

介绍crow里的编译期比较字符串。crow star了,一直没机会看

保存type类型的库 https://github.com/Neargye/nameof

字节跳动的rocksdb开源了

https://github.com/bytedance/terarkdb

https://www.tuicool.com/wx/BFRRb2y

他们也实现了kv分离,复习一下kv分离

https://en.pingcap.com/blog/titan-storage-engine-design-and-implementation

字节小伙的sig_tree

https://github.com/JimChengLin/sig_tree/

我数据结构的基础还是差

腾讯的tendis开源了

https://github.com/Tencent/Tendis

没有exporter 其实可以照着https://github.com/oliver006/redis_exporter 改,我发现他们这个还不支持集群模式,所以一时半会还改不了

boost hana的中文翻译,其实一直没机会用,也就没看

有机会调查一下

https://github.com/freezestudio/hana.zh/blob/master/hana-zh.md

https://plywood.arc80.com/

有反射

React 教程 https://zh-hans.reactjs.org/tutorial/tutorial.html

lisp方言

https://github.com/SuperFola/Hitoban

https://github.com/ArkScript-lang/Ark

一个小脚本语言,架构类似lua

https://github.com/Skiars/berry

这种脚本语言和mruby相比有啥优势?哦嵌入式

https://github.com/ssloy/tinyraycaster

https://github.com/ssloy/tinyraytracer

简短的教程,教你写光锥

rust中文教程

https://kaisery.github.io/trpl-zh-cn

了解lua

https://github.com/lichuang/Lua-Source-Internal/blob/master/doc/ch02-Lua%E4%B8%AD%E7%9A%84%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B.md

https://www.zhihu.com/question/20617406

分形树

http://mysql.taobao.org/monthly/2016/04/09/

https://github.com/percona/PerconaFT

https://github.com/percona/tokudb-engine

http://www.fxysw.com/thread-5061-1-1.html

http://mysql.taobao.org/monthly/2016/03/01/

toydb

https://github.com/erikgrinaker/toydb


看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

(译)Data Structures and Algorithms for Big Databases


这篇文章是percona的在xldb2012的分享,是一篇教程,介绍了一些基本概念,比较旧了,了解概念

官方总结 ppt链接

  • 如何选取数据结构能显著减轻(signaficantly mitigate)插入/查询/更新 的开销
  • 这些数据结构数据量大了,怎样更高效的利用内存

大数据,也就是放不下内存,靠数据结构来管理,教程也是针对大数据场景下数据结构的管理来展开的

Module 1: I/O model and cache-oblivious analysis.

IO带宽,三个参数, 数据大小N,内存大小M,传块大小B

  • 如果有1000M数据,10M内存,数据块1M,怎么排序呢
    • 首先读10M 排一次,一共排100次
    • 然后10个10M合并,一共10次
    • 然后10个100M合并
  • 浪费的IO
    • 首先是N/B次 传输,然后是合并logM/B(N/B)

上面这个也叫做DAM(Disk-Access-Model)分析,因为这种场景下,内存不是瓶颈,IO是瓶颈

问题在于,对于cache-oblivious的场景,你是不知道M(可用内存) B(传输块大小)的,作者做了一版穷举B的测试,数据表示没有最佳的B

感觉作者没说完啊,对于CO怎么优化也没说

Module 2: Write-optimized data structures. We give the optimal trade-off between inserts and point queries. We show how to build data structures that lie on this tradeoff curve.

这里列的是tokudb,用的lsm tree,没啥说的

Module 2 continued: Write-optimized data structures perform writes much faster than point queries; this asymmetry affects the design of an ACID compliant database.

这里提到了mongo用的Fractal-Tree Index 没听说过这数据结构

Module 3: Case study – TokuFS. How to design and build a write-optimized file systems.

介绍tokufs,读写指标吊锤ext4

论文在这里

实现细节

  • metadata index data block index 加速
  • metadata index key记录文件名,data block index记录文件名和blocknum 连续读
  • blocksize固定512
  • 压缩索引
    • 路径名字前缀非常多余,可以优化移除
    • zero-padding,很多块占用用了padding,可以移除(?有没有安全风险?)
  • 原型阶段,不知道谁用了

Module 4: Page-replacement algorithms. We give relevant theorems on the performance of page-replacement strategies such as LRU.

讨论缓存有效性问题,引入各种cache组件,比如LRU

讨论最佳替换算法,以及竞争性分析,在线算法竞争性分析可以看这篇文章 也放在参考链接里了

具体的概念就不展开了,直接说结论

LRU LFU FIFO k-competitive

基本上LRU和内存(OPT)表现一致,多了一些内存浪费

大段时间都在证明上

还有一些需要考证的问题

  • 如果block大小不一,性能表现如何?
  • 写回(write-back)的代价
  • LRU实现起来 代价稍高(调用系统时间,其实这不算什么问题)

Module 5: Index design, including covering indexes.

b树索引加速查询但是影响插入,维护索引代价不大,所以如何索引需要考虑清楚

  • 索引缩小数据规模
  • 提高局部性
  • 排序

Module 6: Log-structured merge trees and fractional cascading.

介绍LSM tree以及LSM tree在DAM模型上的表现

如何提高点查效率

  • 缓存
  • 不聋过滤器 Bloom filter
  • fractional cascading.(?啥意思)

以及LSM加优化之后和COLA差不多

LSM tree + forward + ghost = COLA

没看懂细节 总之tokudb论文里有

还有buffer tree之类的都是对btree的优化。这里不展开了

Module 7: Bloom filters.

读完感觉没有参考资料有可读性。毕竟比较旧了,2012年的,还是挺有前瞻性的

参考资料

  • 需要了解cache-bolivious 概念 https://users-cs.au.dk/gerth/emF03/slides/cacheoblivious.pdf
  • 一个CO的简单优化,就是分治 https://blog.csdn.net/toughbro/article/details/5931029

考量cache oblivious最好是对比完全不考虑memory hierarchy结构的算法复杂度测量机制,O(nlogn)这样的,只是计数计算的复杂度。或者在console上常常做的cache aware的优化,就是针对cache line size来组织数据结构大小,一次prefetch一个cache line的数据做操作。这个cache oblivious比理想算法更接近于电脑硬件(考虑到memory hierarchiy)但也没有变态到完全根据cache line size来设计数据结构和算法。简单说来,就是假设一个cache line size,对问题进行分而治之,分的粒度到virtual cache line size,就停止分解

  • 和我第一小节差不多 https://www.jianshu.com/p/8bfb47c01a7e
  • 随便搜co搜到一篇论文 https://www.cse.ust.hk/catalac/papers/coqp_tods08.pdf
  • 算法介绍 https://blog.csdn.net/dc_726/article/details/51724097
    • 第五小结,介绍了具体的优化算法,以及列出了很多论文,不错
    • 第四小结,写优化数据结构,除了LSM tree还有很多,提供思路
  • 竞争性分析,建议看这篇文章 https://blog.csdn.net/anshuai_aw1/article/details/108467900 写的不错
  • tokudb有很多点子,催生了很多想法
    • 写优化数据库 https://github.com/weicao/cascadb
    • fractal-tree数据库 https://github.com/BohuTANG/nessDB
      • 另外,这个兄弟的博客不错,对于了解CK来说。值得看一看 https://bohutang.me/2020/06/05/clickhouse-and-friends-development/

看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

(译)Scaling Cache Infrastructure at Pinterest


原文链接

需求,业务激增,缓存不够,要分布式缓存

pinterest的业务架构图

分布式缓存,使用mcrouter + memcache架构,facebook的方案,他们还发了paper

memcache可以开启extstore,如果数据过大放不下,可以保存到硬盘里,flash nvme之类的

mcrouter的抽象能力非常好

  • 解藕数据面控制面
  • 提供上层更精细的控制 修改ttl之类

这套方案mcrouter也高可用

  • 背后的复制行为对上层来说也是透明的 双活等等
  • 也可以接入测试流量,更好的隔离流量

主要风险

  • 配置文件容易出错
  • 瓶颈在proxy 得多个proxy
  • 尽管业务侧可以灵活的设计key,热点key问题还是不可避免 (有没有mongodb的那种分裂range机制?如果没有,能引入吗?)

说实话这个软文没讲什么东西


PS

我浏览的途中又一次看了眼beandb,原来也是mc的协议啊

一个db的列表 https://github.com/sdcuike/issueBlog/blob/master/%E5%AD%98%E5%82%A8%E5%BC%95%E6%93%8E.md

https://github.com/alibaba/tair


看到这里或许你有建议或者疑问或者指出我的错误,请留言评论或者邮件mailto:wanghenshui@qq.com, 多谢! 你的评论非常重要!

觉得写的不错可以点开扫码赞助几毛 微信转账
Read More

^