10
3
2019
2

红黑树到底是个什么树

红黑树使用得非常多,然而由于它不在我的本科教材上,我又不用自己实现它,所以我一直不知道它是什么样的。现在想了解一下,结果发现网上我看了好几篇的中文资料都是这种介绍方式——

假设要介绍的树叫梧桐树。文章会告诉你梧桐树会长多高,树叶长什么样,分叉有什么特征,它和棕榈树有什么不同,还会贴心地放一张或者多张梧桐树的照片给你看。

然而红黑树不是梧桐树啊!计算机科学也不是植物学啊!它是为特定目的人造的!所以你倒是说说它为什么会被设计成这个样子啊……

然后我去看了一眼英文维基百科上的介绍,才看了第一段就恍然大悟。

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

意思是,红黑树是一种自平衡二叉树。每个节点有一个额外的比特,通常叫它颜色,并且是红的或者黑的。所以红黑树之所以叫红黑树,只是发明者为了方便叙述给加了点颜色,就跟数学里那些个着色问题(以及物理里夸克的颜色和味道)一样。为什么要加这些颜色呢?它们是用来保证树大致平衡的。

神奇了,为什么加了这么个颜色就能保证了?

Balance is preserved by painting each node of the tree with one of two colors in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

哦,是用特定的方法着色的,并且树被修改的时候会重新着色。神奇的算法使得这些操作非常高效。也算是用空间换时间了。

The leaf nodes of red–black trees do not contain data. These leaves need not be explicit in computer memory—a null child pointer can encode the fact that this child is a leaf—but it simplifies some algorithms for operating on red–black trees if the leaves really are explicit nodes.

红黑树的叶子节点总是黑色的,并且不包含额外的信息。所以实现的时候实际上不需要显式地存在,或者用同一个节点就好。它的存在只是为了简化算法描述而已。

红黑树的性质:

  1. 每个节点不是红色就是黑色。多出来一比特的信息,当然只有两种选择了。
  2. 根节点是黑色。
  3. 叶子节点是黑色。
  4. 红色节点的子节点是黑色。这是为什么非要加个不包含任何信息的黑色叶子节点了。不然弄出来红色叶子节点有点麻烦了。
  5. 任意节点到它下方的叶子节点,路径上的黑色节点数是相同的。再一次体现了黑色叶子节点的用处。

这些性质保证了,从根节点到所有叶子节点,最远的路径最多是最近的路径两倍远。不会特别远,甚至是退化成链表了。

然后是树上的操作。

查找就不用说了。二叉树的查找算法而已。

插入的时候,首先把新节点涂成红色,按二叉树的方式插进去,取代某个叶子节点,并自己长出两片叶子。然后修复一下。修复方案如下:

  1. 如果这是个根节点,那么涂黑就完事了。
  2. 如果它的上级节点是黑色,黑色节点下接红色节点,没事,不需要更多操作了。
  3. 如果它的上级节点是红色,并且它的上级邻节点是红色,这就坏事了,违反了性质4。那就把它们涂黑。可这样多了一层黑节点,又会违反性质5。那就把上上级节点涂红(由性质4,上上级节点之前肯定是黑色)。可如果上上级节点是根节点,又违反了性质2。不过上上级节点带的这部分子树肯定是没问题的,那就把整个上上级节点带的这棵子树当整体,递归修复一下好了。
  4. 如果它的上级节点是红色,并且它的上级邻节点是黑色,这还是破坏了性质4。而这个时候如果把上级节点涂黑,那么上上级节点不管涂不涂红,一边加了一个黑节点而另一边没有加,它这个子树本身就已经坏掉了,所以得想另外的办法。
    1. 第一步,如果上级节点在左边,而新加节点在右边,那就左旋。如果上级节点在右边,而新加节点在左边,那就右旋。其它情况不用动。由于是两个上下级红色节点在旋转,这样并不会再破坏任何性质。
    2. 第二步,两个红色节点和可以被取代的叶子节点已经准备好了,现在把上上级节点(也就是动过的子树的上级节点)用子树的根换掉,原来的挂到上一步空出来的叶子节点那里,并且把新根涂黑,把一开始那个碍事的黑色节点涂红。这样,两个红色节点就成了同一个黑色节点的子节点。性质4得到了保持,涂色过程只是把黑色上移取代之前的红色,一边的路径上少了个红色节点,另一边多了个红色节点而已,也不会破坏性质5。

删除就更复杂了。

  1. 如果被删除的节点有两个非叶子节点,按二叉树的方法删除节点,但是保持原来这个位置上节点的颜色。因为子树的根被保留颜色地替换了,所以这一步不会破坏性质。而少了的(被作为新子树根替换的)节点,递归这个删除算法就可以了,一直在深入,总能递归到没有两个非叶子节点的节点。
  2. 你不会想删叶子节点,也不能删它们。
  3. 所以剩下一种情况:被删除的节点最多有一个非叶子子节点。如果有的话就叫它 C 好了,没有就随便找个叶子节点当 C。那被删除的节点我们叫 M。
    1. 如果 M 是红色,那用 C 取代它即可。因为 C 肯定是黑色(而且是叶子节点)。
    2. 如果 M 是黑色,但 C 是红色,用 C 取代 M,并且把 C 涂黑。少了一个红色节点而已,没事的。
    3. 如果 M 和 C 都是黑色,这个时候 C 也一定是叶子节点。先用 C 取代 M,并叫新的 C 为 N,其上级节点为 P,P 的另一个子节点为 S。现在 N 这边少了个黑色节点,相对的,S 这边多了一个。
      1. 如果 N 是根节点(P 不存在),那么没事了。
      2. 如果 P 是黑色,并且 S 是红色,旋转一下,让 S 成为新的子树的根,并将 P 涂红。从颜色上看,只是红色从一个子节点跑到另一个,然后有棵子树从一边换到另一边了,性质不会被再度破坏。但之前被破坏的部分还没修复呢,现在是一个黑色下边有一个黑色的节点那里的路径上多了一个黑色节点,要走下边的步骤。
      3. 如果 P 和 S 都是黑色,N 那边不是被删掉了一个黑色节点吗,现在把 S 涂红,这样 P 的两边(N 和 S)都少了个黑色节点。子树没有问题,然而 P 这边的路径上少了个黑色节点。要么 P 是根节点,不用管了。要么 P 的邻节点那边的路径多了个黑色节点,情况就是一个子树,下方有一个黑色节点,并且这一边的路径上多了个黑色节点。如果子树的根是黑色,那么递归了,回去再走一遍上一步(3.3.2)就好。如果是红色,走下边的步骤。
      4. 如果 P 是红色,并且 S 和 S 的子节点都是黑色,把 P 和 S 的颜色交换一下,S 那边的路径少了个黑色节点,处理好了。
      5. 如果 P 是红色,N 位于左侧,并且 S 的左子节点是红色,右子节点是黑色。N 当然是黑色的啦。那么把 S 右旋,并且把旧 S 的左节点(新的子树根)涂黑,然后旧 S 自己(新右子节点)涂红。继续下边的步骤。
      6. 如果 P 是红色,N 位于左侧,并且 S 的左子节点是黑色,右子节点是红色,把 P 左旋一下,并把之前那个红色子节点涂黑。这样 N 那侧的路径多了个黑色节点。完成了。
      7. 如果 P 是红色,N 位于右侧。把上两步镜像一下就可以了。

总之就是各种涂色和旋转,来保持二叉树和红黑树的性质不被破坏(红黑树是二叉树,所以旋转需要点技巧,不是想旋转就一定能旋转的)。看着复杂,照着前人已经想好的步骤去做其实也并不难。然而中文网络上几乎没有人解释这些步骤的目的,以至于让人理解不能 :-(

Category: 编程 | Tags: 算法 编程
9
9
2019
6

gdb 不肯加载调试信息怎么办?

更新完 buster,我的 morerssplz 崩了好几次了。第一次收到 Grafana 的通知时还以为出什么大事了呢,结果只是进程崩了。

这只 Debian 没有安装 systemd-coredumpctl 所以手动 ulimit -c unlimited 搞到了个 coredump。可随后问题来了:

(gdb) bt
#0  0x00007f9a5bd8b013 in ?? ()
#1  0x00007f9a5bd8bcfa in ?? ()
#2  0x0000000002bdb890 in ?? ()
#3  0x0000000000000000 in ?? ()

啥也没有?

我安装了 python3-dbg 啥的,它还是如此显示,以至于我一度认为 Debian 的 python3-dbg 包只包含调试版本的 Python 而没有 python3 包对应的调试信息。后来才发现不是这样的,因为直接加载 python3 是会读调试信息的:

>>> gdb python3
...
Reading symbols from python3...Reading symbols from /usr/lib/debug/.build-id/66/44f05b3a3ab9727ecee55c58681bc43b94d92e.debug...done.

然而 gdb 读这个 coredump 的时候压根就没尝试读取……即使我使用 symbol-file 命令加载了 python3 的调试信息也依旧如此。以至于我还以为函数调用栈被破坏了,但我越看越是感觉不像。

后来看到一个命令——sharedlibrary,让 gdb 加载动态链接库的调试信息的。这个也执行之后,终于能打出完整的调用栈了!

所以就是这程序崩在了动态链接库里,而 gdb 太懒根本不肯自动加载相关的调试信息,所以才什么都看不到的。

Category: 编程 | Tags: gdb
9
4
2019
16

关于称呼

总有一些人对我用一些不知道怎么来的称呼,所以我来写一下。以后不要不经过大脑乱用了啊。

不可接受的

✘ 老哥、大哥、兄弟、兄台、先生 ✘

使用以上称呼可能导致消息没有回复,或者相关消息被删除。

不建议的

大佬、老师、大大,等

建议

直接叫我「依云」就好啦,想那么多干嘛。

Category: 未分类 | Tags:
9
3
2019
9

NVIDIA PRIME 配置笔记

这是由 NVIDIA 官方提供的新的双显卡配置方案(官方文档),需要最新的驱动及 Xorg 支持。其中 nvidia 驱动已经位于 Arch Linux 官方仓库中(版本号 435.21)。相关 Xorg 补丁还在 git 上,并没有新版本放出,所以需要自行编译包含补丁的版本。这里有现成的 PKGBUILD。我打包好的版本也提供下载

我的硬件是 ThinkPad T470p,Intel Corporation HD Graphics 630 核显和 GeForce 940MX 独显。核显的特点是:省电、支持视频编解码加速。独显的特点是:Minecraft 能开光影,FPS 也要高一点。用来跑火狐的话可以正确渲染 FishGL

配置方法如下。

首先把 bbswitch 啥的都卸载了吧。虽然注意点不卸载也没事,但是毕竟装着没意义还容易出问题。然后看看 /etc/modprobe.d 下有没有黑名单 nvidia 的驱动,给它取消了。我有一个 options nvidia_drm modeset=1 的配置,不知道有没有影响。

Xorg 这边要加一段配置。就保存在 /etc/X11/xorg.conf.d/nvidia.conf 好了。

Section "ServerLayout"
  Identifier "layout"
  Screen 0 "iGPU"
  Option "AllowNVIDIAGPUScreens"
EndSection

Section "Device"
  Identifier "iGPU"
  Driver "modesetting"
  BusID "PCI:0:2:0"
EndSection

Section "Screen"
  Identifier "iGPU"
  Device "iGPU"
EndSection

Section "Device"
  Identifier "dGPU"
  Driver "nvidia"
EndSection

那个 BusID 的值要自己看着 lspci | grep VGA 来改。

如果你之前是用N卡跑 Xorg 的,需要把 xrandr --setprovideroutputsource modesetting NVIDIA-0 之类的设置去掉。

然后重启系统就可以了。请做好通过 tty 或者 ssh 修复配置的准备。

默认情况下,Xorg 及其上的程序运行于i卡。使用 __NV_PRIME_RENDER_OFFLOAD=1 __GLX_VENDOR_LIBRARY_NAME=nvidia 环境变量来指定使用N卡。为了方便起见,做一个别名好了:

alias nvrun="__NV_PRIME_RENDER_OFFLOAD=1 __GLX_VENDOR_LIBRARY_NAME=nvidia"

然后就可以 nvrun minecraft-launcher 啦~

Minecraft BSL 光影效果

对了,要注意一下的是,这两个环境变量对视频硬解也是有效的。比如我如果给 mpv 使用这两个环境变量的话,mpv 就会黑屏(我的N卡不支持硬解……

Category: Linux | Tags: linux nvidia 显卡驱动
8
16
2019
4

寻找最快的 GitHub IP

部分国内网络访问 GitHub 会很慢,严重拖慢了学习和开发效率。除了使用代理绕路之外,有没有什么简便的办法呢?最近我写了个脚本,用来测试所有已经的 GitHub IP 并计时,然后就可以挑一个访问快的写在 hosts 文件里了。

获取脚本请访问 gh-check。脚本依赖 Python 3 近期版本及 aiohttp。

中国大陆目前自然解析 github.com,通常会得到位于新加坡的 IP。然而这几个 IP 的访问速度经常不怎么好。我之前是手动尝试使用西雅图或者阿什本的 IP,但是它们也并不总是很流畅。现在,终于可以让数据说话了:

gh-check demo

IP 来源于四个 GitHub 区域域名的解析结果,以及另外两个我自己通过 DNS 发现的。

检查分为两种:HTTP 和 SSH。默认两者都测试,可如上图中那样通过参数指定只测试一种协议。HTTP 测试时,会验证服务器的 TLS 证书。

Category: 网络 | Tags: github 网络
7
25
2019
6

火狐远程调试火狐

F12。F1。开启 chrome 调试。开启远程调试。汉堡菜单,Web 开发者,浏览器工具箱。

如上操作,就可以打开一个专用火狐实例,连接到之前的火狐上,用来调试火狐的界面(chrome)了。

然而这里有个问题:这样你没法调试任何独占式的弹出菜单。不管是各种右键菜单,还是地址栏补全、汉堡菜单,它们一出现,就会捕获键盘鼠标,你根本不能操作别的窗口了。

遇到这种占用整个 X 服务器的情况,一种策略就是我上一篇文章里调试 fcitx 时那样,通过 ssh 连过来调试。然而火狐的 devtools 显然需要一个 X 服务器才能运行的。所以可以在另一台电脑上调试。当然单机也是有办法的啦——xephyr 就是为此而生的。pacman -S xorg-server-xephyr 就可以了。然后 Xephyr :1 -screen 1024x768 启动。

可还有个问题:之前的 devtools 打开的时候没给机会指定它在哪个 X 服务器上运行呀。虽然 GTK 有能力把窗口从一个服务器转移到另一个,但那也是需要程序主动配合的。不过既然叫「远程调试」的,应该也能像 Firefox for Android 那样通过网络连接才对?

于是搜了一下,果然找到篇 MDN 的文章讲这个的。简单地说就是加个参数就好啦:

DISPLAY=:1 firefox-nightly -no-remote -profile tmp --start-debugger-server 6100

最后要加个端口号,因为默认是 6000,和 X 服务器的冲突了……(我是说怎么明明在监听怎么就是连不上呢,原来连错程序了 QAQ)

然后在另一个火狐实例里打开 about:debugging 去连接就好啦。本地(localhost)连接的话,不需要额外的配置也不需要确认的。如果不是本地连接,还需要去 about:config 改两个选项。


花了些时间,把显示成两行的地址栏补全给弄回来啦~

火狐地址栏两行补全

样式表在这里。想用的话记得要把 toolkit.legacyUserProfileCustomizations.stylesheets 设置为 true 才会加载 userChrome.css 哦。

Category: 火狐 | Tags: 火狐
7
22
2019
4

fcitx 扩展:使用键盘粘贴选区(以及X选区原理科普)

之前的文章中介绍过,X Window 中有个很方便的名叫 PRIMARY 的「剪贴板」,选中即复制,中键即粘贴。

然而问题来了:我在输入的过程中需要之前选中的内容怎么办?又或者我的内容是通过 xsel、Vim 等程序以键盘的方式选中的,我还要继续打字,要怎么粘贴才比较流畅呢?

我之前的解决方案是 fcitx 自带的 fcitx-clipboard 扩展。启用之后可以按 Ctrl-; 来显示几条最近复制的内容。如果启用了的话,第一条、第三至最后,都来自常见的 CLIPBOARD 选区,而第二条(如果用了够久,第一条及本条有的话)是 PRIMARY 选区的内容。于是我只需要按 Ctrl-; 2 就可以粘贴了。

这么用了很久之后,我读到了一篇讲 X Window 选区是如何工作的文章。然后突然意识到一个问题:fcitx-clipboard 是什么时候请求选区内容的呢?

这里先科普一下好了。X Window 的每一个选区,是由某个窗口作为所有者持有的,并且在被请求时输出内容。「复制」的时候,内容并不会被存起来放在某处,而是窗口跟 X 服务器说,「我现在是这个选区的所有者了!」至于是哪个,取决于应用程序(及用户的操作)。通常用户明确的「复制」操作(Ctrl-C 快捷键、菜单项等)会使用 CLIPBOARD 选区,而只是选中内容的话,会使用 PRIMARY 选区。我还没有见到有程序使用别的选区的。

如果使用的是 PRIMARY 选区,这个时候,旧的所有者(如果存在的话)会失去选区。在 Vim / GVim 里,可视区域会由「Visual」高亮组变为「VIsualNOS」高亮组(在我的主题里就是变灰了),而多数终端,选中的区域会失去高亮。下一次,有程序想要「粘贴」PRIMARY 选区,就会跟 X 服务器讲,请把 PRIMARY 选区的内容,以某个指定的格式写到指定窗口的指定属性上。然后 X 服务器把请求传给选区所有者,选区所有者就去按要求写属性。当然选区所有者也可能会拒绝请求,比如它拥有的是文本而请求方想要图片。当然后来大家要粘贴的内容比较大了,于是就有了 INCR 机制来一点一点地传数据。

这样的流程,也可以解释,为什么我往 Telegram 里粘贴图片,GIMP 却莫名其妙地挂掉了……

所以啦,在一个程序里复制之后,退出那个程序,你就粘贴不出来东西啦。可这样岂不是很不方便?是啊,所以又有了剪贴板管理器。它们的工作原理我还没有研究,猜想是支持 SAVE_TARGETS 的话,就等着对方退出之前把内容传过来,不支持的话一复制就传过来。

fcitx-clipboard 是这么干的:选区一有变化,它就获取其纯文本格式的内容,符合一定条件的就存起来。所以,当我在 Vim 里用键盘不断进入可视模式选东西进行各种操作时,因为我设置了 clipboard=autoselect 选项,Vim 会不断地通告「我拥有 PRIMARY 选区啦!」「我这边的 PRIMARY 选区又更新啦!」结果就是,fcitx-clipboard 会不断地把我在 Vim 中选中的内容给拿过去。

就那么点数据,本地传来传去当然没啥问题。但是,当我通过 ssh 使用的时候,我发现我在 Vim 里每一次扩大可视区域都如此地艰难。不得已只好关了 autoselect 选项。当时我还以为就选点文本,怎么就这么慢呢,谁曾想到,每一次更新可视区域,fcitx-clipboard 都会把我选中的文本请求一份……

那么好吧,不用 fcitx-clipboard 了。于是问题又回到了原点:怎么通过键盘粘贴 PRIMARY 选区呢?用程序把鼠标移过去点中键是不行的,因为程序不会知道当前光标在哪里。通过 xdotool type 也行,但是这样一个个字地输入,而且还不仅仅是 ASCII,鬼晓得有多少程序跟 Minecraft 一样会处理不过来而丢字?而且,怎么判断当前是否是输入文本的状态也是个问题。所以我还是走输入法这条路了。

其实这事完成并不难,从肥猫的傲娇扩展开始改,照猫画虎地注册热键,然后请求选区,提交文本。可我遇到一个很奇怪的 bug:扩展加载了,但是热键不生效。为了调试这问题,我通过手机 termux ssh 连过来,tmux attach 上,然后用蓝牙键盘对着屏幕里那只由于 fcitx 被 gdb 停下来了因此从电脑收不到键盘事件的 tmux 调试好久,最终发现热键怎么没注册上,才找到配置文件里一处没有被更新到的 tsundere 字样……

这个扩展名叫 fcitx-paste-primary,源码放 GitHub 上了。Arch Linux 用户可以通过 AUR 或者 archlinuxcn 仓库安装 fcitx-paste-primary-git。

对了,差点忘了说,这个扩展「粘贴」的时候,只是把会被粘贴的文本提交给应用程序,程序并不会认为是真的粘贴,所以在一些需要区分的程序里会出现问题。比如 Vim 和 zsh,都会把来自 fcitx-paste-primary 的文本当作用户输入而非粘贴而可能造成问题。

Category: Linux | Tags: fcitx X Window X window
4
9
2019
4

T470p 使用N卡运行 Xorg

这么做的原因是:这样 minecraft 帧率高,不卡顿。

  • intel 显卡:帧率低,好像是20fps左右吧。开不了光影
  • optirun:坏了
  • primusrun:帧率高了一些,不多
  • nvidia-xrun:丝般顺滑,只是切换回我之前跑程序的 Xorg 时,发现我的 Awesome 已经没了。一开始是黑屏,经过配置之后倒是能得到 LightDM 的登录画图。另外 nvidia-xrun 无法卸载模块,因为被 Xorg 使用了,需要停止 lightdm。

那么,既然 nvidia-xrun 效率不错,我要是把整个桌面都搬上去呢?经过了一些折腾之后,取得了不错的结果。一个意料之外的好处是,播放视频、网页浏览器里滚动页面时常出现的画面撕裂好了~

当然这样做会费电,降低续航时间。不过既然是 T470p,一开始我就没打算整天带着它到处跑,所以无所谓啦。需要的时候再切回去好了。有个叫 optimus-manager 的软件,看介绍是帮助这么切换的。不过我对一切自动化程度太高的软件都心存疑虑,不确定它到底干了什么,会不会和我其他的配置相冲突。所以以后再看看啦。

最终的配置方案是这样的——

首先,把 bumblebeed.service 关掉并禁用。

然后,Xorg 配置一份,放 /etc/X11/xorg.conf.d/ 下就好。这份配置来自于惠狐的《Archlinux 下 Intel 和 NVIDIA 双显卡 de 折腾笔记》一文。

Section "OutputClass"
    Identifier "intel"
    MatchDriver "i915"
    Driver "modesetting"
EndSection

Section "OutputClass"
    Identifier "nvidia"
    MatchDriver "nvidia-drm"
    Driver "nvidia"
    Option "AllowEmptyInitialConfiguration"
    Option "PrimaryGPU" "yes"
    ModulePath "/usr/lib/nvidia/xorg"
    ModulePath "/usr/lib/xorg/modules"
EndSection

lightdm.conf 里在 [Seat:*] 里加一个 hook 配置,否则会黑屏的:

display-setup-script=/usr/local/bin/lightdm-setup

这个脚本内容如下:

#!/bin/bash -e

xrandr --setprovideroutputsource modesetting NVIDIA-0 || exit 0
xrandr --auto

写了一个 systemd service,用来启用 N 卡。因为默认它是关的。

[Unit]
Description=Switch On nvidia card
ConditionPathExists=/proc/acpi/bbswitch
Before=display-manager.service

[Service]
Type=oneshot
ExecStart=/bin/sh -c "echo ON > /proc/acpi/bbswitch"

[Install]
WantedBy=graphical.target

我之前在 ~/.xprofile 配置了视频的硬件加速,现在得删掉。GM108M [GeForce 940MX] 这个显卡的视频加速没法用的。

设置内核模块的选项 options nvidia_drm modeset=1,不然 xrandr --scale 时结果会不对。

暂时就这些了。


2019年07月20日更新:我又换回 Intel 显卡了。虽然这样性能差一点,滚动、视频时画面有点撕裂,外接屏幕中鼠标会闪,但是它稳定可靠啊!Nvidia 的驱动实在是崩得太闹心了(而且我那卡不支持视频硬解)。

2019年09月03日更新:我用上了 NVIDIA 新的 PRIME 方案,效果很好~

Category: Linux | Tags: linux 硬件 显卡驱动
4
4
2019
4

系统在解析哪些域名呢?

最近用 Rust 写了个叫 capture-dns 的小程序,实时显示 DNS 查询结果的。配合 ipmarkup 的效果是这样的:

>>> sudo capture-dns lo | ipmarkup
[sudo] lilydjwg 的密码:
github.com -> 52.74.223.119(新加坡Amazon数据中心)
github.com -> 13.229.188.59(新加坡Amazon数据中心)
github.com -> 13.250.177.223(新加坡Amazon数据中心)
live.github.com -> 192.30.253.125(美国弗吉尼亚州阿什本GitHub)
live.github.com -> 192.30.253.124(美国弗吉尼亚州阿什本GitHub)
collector.githubapp.com -> 34.193.248.191(美国弗吉尼亚州阿什本Amazon数据中心)
collector.githubapp.com -> 52.20.29.9(美国弗吉尼亚州阿什本Amazon数据中心)
collector.githubapp.com -> 34.197.57.23(美国弗吉尼亚州阿什本Amazon数据中心)
api.github.com -> 13.250.94.254(美国Amazon数据中心)
api.github.com -> 13.250.168.23(美国Amazon数据中心)
api.github.com -> 54.169.195.247(新加坡Amazon数据中心)
ocsp.digicert.com -> 117.18.237.29(澳大利亚美国MCI通信服务有限公司(韦里孙商业Verizon Business)EdgeCast亚太网络CDN节点)

可以看到本地的软件们都在查询哪些域名,得到的 IP 又是什么。抓取的是应答,所以没得到 IP 结果的不会显示。我抓取的是 lo 网络接口,因为我本地有用 dnsmasq 做缓存。

其实这个程序一开始不是这样子的。群里有人想抓取系统上进行的 DNS 查询的域名。一开始是用 tshark 抓取的,然而它太占用内存了。我粗略看了一下 Python 的 scapy 工具,也用掉了大几十M内存。那么,用 Rust 写一个好了,也顺便练习一下 Rust。

这个程序运行时只有几M的内存占用,CPU 占用也是非常低的。不过它并没有做完全的协议分析,而是假设抓得的包是以太网帧封装的 IPv4 报文封装的 UDP 数据包里包着 DNS 应答报文。所以如果你是在 eth0 上跑 PPPoE 的话,抓 eth0 上的包就不行了,得抓 ppp0 这种了。当然你要是 IPv6 啊 DoH、DoT 啥的就更抓不到了。

后来我用 bcc 的 tcpretrans 脚本查看我这里到哪些地方的 TCP 连接不太通畅,然而经常会看到一些我猜不到是干嘛的 IP。所以就把这个程序改了一下,把域名对应的解析结果显示出来了。

Rust 不仅节省资源,而且开发的体验真的很棒呢,编译成功之后就能按我预期的运行了。也不用担心什么时候遇到个有问题的报文导致程序崩掉,因为写的时候就已经处理好了出错的情况。不像 Python 写的脚本,刚写好,一跑就抛个异常出来,提示我哪里不小心写错了。好不容易调试好了,跑着跑着,遇到意外情况就挂掉了……

Category: 编程 | Tags: Rust linux 网络 DNS
4
3
2019
0

正确的隐藏挂载点的方法

脚本需要挂载文件系统,但是不希望外部看到。正确的做法是:

mount --make-rprivate /

然后该干嘛干嘛。当然如果你不知道在执行之前先调用 unshare 或者等价的系统调用,说明这篇文章不适合你阅读。

错误的做法是在挂载的时候加 --make-private 或者把 / --make-private。这个标志(MS_PRIVATE)的意思是挂载/卸载事件在这里停止传播,而不是这个挂载点的事件是否传播出去。至于为什么需要使用 --make-rprivate(增加了 MS_REC 标志),暂时我还不理解。

这个用法是从 unshare 工具的 strace 结果里挖掘出来的。因为我的目的跟 unshare -m 一样嘛,当然首先想到的是看看它是怎么干的了。你问我为什么不用 unshare -m?你自己写脚本的时候试试看啰?

Category: Linux | Tags: linux 文件系统

| Theme: Aeros 2.0 by TheBuckmaker.com