7
6
2020
2

品《当我开始做软件开发时,最希望听到的七条建议》

在 Twitter 上看到一张写在长图片里的文字《当我开始做软件开发时,最希望听到的七条建议》,记录一下感想。

读书

书确实要读,但每年都读软件工程方面的书,会受边际效用递减的影响的。毕竟软件工程并不是很大的话题,而工程还是得实践出真知。看过几本之后,不如把精力花在更理论和学术的方面,比如编程语言理论、分布式算法、概率论与统计、博弈论,等等。总之就是要「move on」。而实际上我读的书更杂一些。

编程语言

学习多种编程语言是极好的。但也千万不要限于两种,尤其是别 Java + C# 或者 C + C++ 这种组合。会一叶障目的。我在大学期间学习过非常多种编程语言(几乎是把我听说到的都学了个开头)。

我的建议是,至少 C 系一门,ML 系一门,Lisp 系一门,脚本系一门,简单学一学。然后挑自己感兴趣、用得上和有钱途的深学。了解过的编程语言越多样,学习新语言就越容易,甚至可以在不学习的情况下上手阅读、做小改动。

测试

测试确实挺有用的。但更多的时候,它挺烦的:不是代码本身坏了,而是测试坏了……

现在我更看重的是,一个像 Rust 甚至是 Idris 那样强大的类型系统,能在省力的同时发现更多的疏忽。

Python 的类型注解不是很强大,不过也是非常有用的。

重构

我不太明白作者在这里讲重构是什么意思。

我的习惯是,按需重构。如果一份代码一直良好运行,我才不管它写得有多糟糕呢。但当我要修改它的时候(不管是为了添加新功能还是修 bug),我会把看着不舒服的代码给顺势改掉。

一个很重要的点是,不要为了重构而重构。另一个点是,重构中的代码应当是可以正确运行的。至少每天工作结束时提交,提交的时候代码应当是可以正确运行的(可能有 bug,但不能有未完成而无法运行的部分)。这样,重构可以随时因为各种原因中止,不会影响后续不相关的工作,也不会分出分支来时间一长根本合不回去。

我才不要假设我的代码可以使用五年。再过两个月 lilac 就要六岁了,而 nvchecker 已经七岁了呢。

lilac 经历过三次重构。开始重构的原因是,一开始并没有想到会发展成现在这样子,管理一千多个包,每天都要打好几十个。所以那时候的代码写得很烂,全局变量也很多,以至于新功能加不上去。前两次重构都是在我有闲的时候,拉一个分支出来,看哪里不顺眼就改哪里。可问题是,改了几天之后,我完全无法预测这代码还跑不跑得动。另一方面,修新 bug 当然是在老代码上改的。那我重构到一半的新代码怎么办呢?作为业余项目,这种情况持续一些天之后,我稍一忙碌,把它放下之后,我就再也想不起来我当时的重构思路了。

第三次重构,并不彻底,但是它很有效。因为每次改完收工的时候,我会判断它现在能正常跑起来吗?如果觉得不行,那就 git checkout .。有希望才提交,然后上线。跑出 bug 就去修。忙了就放下,等有时间才继续。思路不那么重要了,因为代码是好的,换个思路也可以继续。

当然了,类型注解在重构过程中我加上了许多,也避免了很多疏忽导致的 bug 被提交上线。

结对编程

并没有人和我结对啊……

工作经验和舒适区

我不是很理解什么叫「舒适区」。不过我主动做的工作,要么能解决我当前面对的问题,或者是想要达成的目的,要么能让我学到有意思的东西。一直重复昨天的事,你们把这个叫「舒适」??

分享

这正是我正在做的事情呢。不过很可惜的是,我并不太会讲话,所以现在流行的直播我还是算了。写作还是比视频有意思,又省力、又能有深度,多好。

6
9
2020
0

终端色彩总结

终端转义序列里有一个 SGR 代码用于表示「粗体或者增加强度」的字体渲染。相当多的终端将其实现作更明亮的颜色而非粗体字,也有很多终端应用程序如此(比如 mutt 中的 brightXXX 颜色使用此代码;新一点的 mutt 支持使用 lightXXX 来表示亮色了)。

然而最近,GNOME 终端决定将这个「或」字去掉,让 SGR 代码 1 表示粗体,亮色使用另外的颜色代码来表示。这无疑导致了我看到的许多软件里出现粗体字。有时候看着还行(比如 systemd、htop 中的),有时候会让人觉得很不舒服(比如 zsh 里打着命令,字体一会儿变粗一会儿变普通粗细)。我就认真去查了一下相关信息,作出相应的配置更改,顺便做个总结笔记好了。

转义序列

「选择图形展现」(Select Graphic Rendition; SGR)序列用于设置字体的渲染方式。其格式为CSI (code ";")* code m。CSI 就是 ESC "["。一个序列里可以给出多个代码,使用分号分隔。如果一个都不给出,当作代码 0 解释。

八色

这是最基础的八种颜色,代码 30-37 设置前景色,40-47 设置背景色。

16色

这就是大多数终端设置里,那个14色的调色板所指定的色彩了。为什么只有14色呢?因为默认的前景色和背景色是单独的设置项。

如序言中所说,相当多的终端将代码 1 解释为亮色,也就是上述八色再加上对应的明亮版本。

自 GNOME 终端此次改革之后,代码 1 只管粗体。要亮色,使用代码 90-97 设置前景色,100-107 设置背景色。除了 GNOME 终端外,也有一些其它终端跟进,比如 alacritty。有些终端保留了将代码 1 解释为亮色的选项,而 GNOME 终端最近去掉了这个选项(但是还有一个将粗体字显示为亮色的选项)。

256色

16色怎么够?于是出现了256色。

ESC[38;5;<n>m用于设置前景色,ESC[48;5;<n>m用于设置背景色。其中,n 是一个数,0-7 同代码 30-37,是那最初八种颜色。8-15 是它们的亮色变种。16-231 是216种彩色,在RGB空间构成了一个6x6x6的立方体。232-255 是24个灰阶色彩。

一些标准中,这中间的分隔符使用冒号。

真彩色

现代显示器普遍使用8位值表示RGB中每一个通道、共计24位了,终端也不能落后呀。于是有些终端也支持了这个被称为「真彩色」的24位色彩了。

代码格式是256色的扩充。ESC[38;2;<r>;<g>;<b>m来设置前景色,ESC[48;2;<r>;<g>;<b>m设置背景色。这里的 r、g、b 当然就是RGB色彩空间的值了,每一项的取值范围是 0-255。

测试脚本

整合了我从各处收集到的展示方式,写了一个脚本,可以直观地感受终端对各种色彩的支持情况:

colors.py

参考资料

Category: Linux | Tags: linux 终端 色彩
5
19
2020
2

桥接无线网卡!

众所周知,大部分无线网卡是不支持桥接操作的。

但是 VirtualBox 就是能,因为它做了特殊处理:来回改 MAC。

那么,我的 LXCnetnsKVM 啥的也想这么玩,成不?

实际上不仅能成,而且 Debian Wiki 还给出了两个方案。方案一是用 ebtables 来回改 MAC。不过我失败了,可能是 ebtables 不支持改完 MAC 再把包发往另外的网络接口吧。

方案二是内核的一个叫 Proxy ARP 的功能。设置起来超级简单:往/proc/sys/net/ipv4/conf/all/proxy_arp里写1,然后给需要的 IP 地址加一条 /32 路由项就可以了。

这方案相比起 VirtualBox 来是非常手动了,也不支持 DHCP 自动配置的 IP 地址,但好歹能用。至少微信备份能用。(火狐的 Wi-Fi 远程调试已经坏掉了,倒是那个「USB 调试」其实只要 adb 连接上就能用,不一定要走 USB 线。)

Category: 网络 | Tags: linux 网络 虚拟机
5
11
2020
3

Linux 的进程优先级与 nice 值

假设有一个程序叫 use-cpu,它运行的时候会一直消耗一个 CPU 核心。试问,如果我开两个终端窗口,分别执行以下两个进程,其 CPU 会如何分配?

$ taskset 2 ./use-cpu
$ taskset 2 nice -n 10 ./use-cpu

两个进程都在1号CPU上运行,意味着它们必定争抢时间片。第二个进程使用 nice 命令设置其 nice 为 10,那么,是不是第二个进程会占用比较少的 CPU 呢?

很合情合理的推理,然而答案是否定的。

呃,也不一定。cat /proc/sys/kernel/sched_autogroup_enabled 看一下,这个开了的话,CPU 调度会多一个层级。默认是开的,所以这两个进程会均分 CPU 时间。

首先说好了呀,这里只讨论普通进程(SCHED_OTHER)的调度。实时进程啥的不考虑。当然啦,CPU 分配只发生在 R(Runnable)状态的进程之间,暂时用不到 CPU 的进程不管。

最上面的层级是 cgroups 了。按照 cgroup 层级,每一层的子组或者进程间按权重分配。对于 cgroups v1,权重文件是 cpu.shares;cgroups v2 则是 cpu.weight。不管用哪个版本的 cgroups,systemd 默认都没有做特别的设置的。对于 v1,大家全在根组里;对于 v2,CPU 控制器都没有启用。如果你去设置 systemd 单元的 CPUWeight 属性(或者旧的 CPUShares 属性),那么 systemd 就会开始用 cgroups 来分配 CPU 了。一个意外的状况是,使用 cgroups v2 时,systemd-run 不会自动启用上层组的 CPU 控制器,以至于如果上层未手动启用的话,设置不起作用。在使用 cgroups v1 时,用 systemd 设置 CPUWeight 或者 CPUShares 也不太好用,因为它并不会自动把进程挪到相应的层级里去……

其次就是这个默认会开的 autogroup。这个特性是为了提升交互式的桌面系统的性能而引入的,会把同一 session 的进程放一个组里。每个 autogroup 作为一个整体进行调度,每个 autogroup 也有个 nice 值,在 /proc/PID/autogroup 里可以看到,也可以 echo 一个想要的 nice 值进去。至于这个 session,不是 systemd 的那个 session,而是传统 UNIX 的那个 session,也是 setsid(2) 的那个 session。我一直以为它没多大作用,没想到在这里用上了。基本上,同一群进程会在同一个 session 里(比如一群火狐进程,或者一群 make 进程),同一个终端里跑的进程也都在一个 session 里(除非你 setsid 了)。

最后才是轮到进程。其实准确地讲是线程。同一个 autogroup 里的时间片如何分配,就看里边这些线程的 nice 值的大小了。所以其实,我系统里的那些高 nice 值的进程,由于 autogroup 的存在而它们又没有去设置 autogroup 的 nice 值,其实调度起来没什么差别的。

参考资料

  • man 7 sched
  • man 7 cgroups
Category: Linux | Tags: systemd linux cgroups
5
7
2020
6

Intel GVT-g 初体验

准备 GVT-g

把 kvmgt vfio-iommu-type1 vfio-mdev 这仨加到 /etc/mkinitcpio.confMODULES 数组里去。mkinitcpio -P 重新生成一下 initramfs。

添加内核参数 i915.enable_gvt=1。比如是 grub 引导就去改 /etc/default/grub 里的 GRUB_CMDLINE_LINUX 变量,然后 grub-mkconfig ...

去把 /etc/systemd/system.conf 里的 DefaultLimitMEMLOCK 给改了。比如 DefaultLimitMEMLOCK=65536:1073741824

重启。

这个时候应该已经有 /sys/devices/pciXXXX:XX/XXXX:XXXX.X/mdev_supported_types 这个目录了。里边有好几个选项呢。选择一下合适的(查看 description 文件),然后往里边的 create 文件里写一个 UUID 就创建了。

启动 KVM 虚拟机

呃,如果你还没有磁盘镜像就自己 qemu-img 创建一个,然后装机。如果你有别的虚拟机的,也可以用 qemu-img 去转格式。

另外准备一下网络。我早就有个网桥了,所以直接用它了。在 /etc/qemu/bridge.conf 里写一句 allow br0 不然不给用的,毕竟我是普通用户权限而网络接口是要 root 权限操作的,得明确允许一下。

我尽可能地使用了 virtio,据说性能好(VirtualBox 也支持一部分了呢)。如果用已有的虚拟机系统但以前没用过 virtio 的话,记得用 fallback 那个 initramfs 启动,然后进系统之后重新生成一个。

我给分配了四个逻辑 CPU 核,4G 内存。VGA 要关掉,不然两个显卡用起来麻烦。为了避免部分内容显示到别处去(如果关了 VGA 的话就看不到,否则能在默认的那个上看到),要加上 ramfb=on,driver=vfio-pci-nohotplug 选项。

声音当然是要的。添加个 PulseAudio 后端,一张 HDA 声卡。我不懂声卡型号所以找了个顺眼的,能用就好。

合起来是这样子的(那两个省略号,一个是磁盘镜像路径,一个是创建 vGPU 用的 UUID):

#!/bin/bash -e

ulimit -l 1024000

exec qemu-system-x86_64 -enable-kvm \
       -name "ArchKDE" \
       -cpu host -smp 4 \
       -m 4G \
       -drive file=/.../ArchLinuxKDE.qcow2,if=virtio \
       -netdev bridge,id=eth0,br=br0 \
       -device virtio-net,netdev=eth0 \
       -device vfio-pci,sysfsdev=/sys/bus/mdev/devices/...,display=on,x-igd-opregion=on,ramfb=on,driver=vfio-pci-nohotplug \
       -vga none \
       -display gtk,gl=on \
       -audiodev pa,id=pa0,server=/run/user/$UID/pulse/native -device intel-hda -device hda-output,audiodev=pa0 \
       "$@"

如果你使用 GVT-g 显卡的时候整个系统都卡卡卡的话,去看一下宿主的内核日志,是不是有 vfio_pin_page_external: Task qemu-system-x86 (257364) RLIMIT_MEMLOCK (104857600) exceeded 这样的提示,然后去把 RLIMIT_MEMLOCK 给调大,大到它不再报这个错为止。我最后给了1000M才终于不报错地把 KDE 给跑起来了(默认是64K)。

当然如果你没有 GVT-g 支持的话,去掉那行配置,然后 -vga virtio 也能用。

参考链接

Category: Linux | Tags: 虚拟机 linux kvm
1
27
2020
2

自制大上 Paperlike HD「驱动」

大上 Paperlike HD 使用有一段时间了,然而有一点我对其非常不满:它需要以 root 权限运行一个图形界面的程序。具体麻烦的地方是:

  • 图形界面的程序不方便使用 systemd 管理,那个窗口我得找个地方安放,并且在登出图形界面或者 Xorg 出问题时会随之关闭
  • 即使持续运行此程序,当几秒内不使用键盘或者鼠标的时候屏幕就会休眠。这导致我无法将此屏幕用于关注程序日志或者聊天工具的新消息。
  • 它持续不断地执行多个线程的任务(读取键盘事件、读取鼠标事件、通过 ioctl 与设备通讯),耗费了不少 CPU
  • 在屏幕尚未连接时,它的运行会导致内核不断输出日志「drm_dp_i2c_do_msg: 2 callbacks suppressed」

我曾多次想自己实现一个符合自己使用习惯的方案。

首先当然是 strace 上去啦。这会得到许多类似这样的消息:

ioctl(9</dev/i2c-1<char 89:1>>, _IOC(_IOC_NONE, 0x7, 0x7, 0), 0x7f47d8805b70) = 1
nanosleep({tv_sec=0, tv_nsec=100000000}, NULL) = 0
ioctl(9</dev/i2c-1<char 89:1>>, _IOC(_IOC_NONE, 0x7, 0x7, 0), 0x7f47d8805be0) = 1
nanosleep({tv_sec=0, tv_nsec=200000000},  <unfinished ...>

可以看到它在对 /dev/i2c-1 这个文件进行操作,但是具体内容是个指针,strace 看不到。

我尝试过使用大名鼎鼎的 IDA 的免费版本来分析其具体行为。但我对 IDA 并不熟悉,并且 IDA 只支持 Intel 语法的汇编,而我见的 AT&T 语法的比较多,Intel 的很多表示法我不太能看懂。

后来根据 ioctl 的请求参数找到这个文档,里边有这些 i2c 消息的结构体定义。于是想着先把 ioctl 的数据弄出来看看。一开始尝试用 gdb 去看那个地址的数据,但想到数据是变动的,再加上 gdb 查看太累了,就想起了通过 LD_PRELOAD 去 hook ioctl。

所以又要写 C 了?并没有呢!C 写起来那么不舒服,还是用 Rust 吧~然后搜了一下,还真有现成的用于写 LD_PRELOAD 库的 crate,比如我用的 redhook。不用自己去 dlopen,不用在各处写很多错误处理代码,很容易就写好了。代码链接

拿到了 ioctl 里用的消息,我不用理会它具体是什么意思,也没办法去猜测,自然是把它按大上提供的程序那个样子给发过去了。于是又一个 Rust 程序出来了。

一开始写的时候不小心往 unsafe 代码块里传了个悬空的指针,导致程序不工作,调试了好久,甚至我都把完整的整个流程给复刻了一遍。这要是用 C 写文本解析的逻辑可头疼了,不过 Rust 写起来就跟 Python 差不多的了~

至于那个 bug,是 Rust 语句中的临时对象(此例中是包含一个对象的数组)会在语句结束之后就释放导致的。有点坑,但也没什么好的办法。

程序运行起来之后就会保持 Paperlike HD 显示器可用,不会报错让装驱动,也不会过几秒就休眠了。我大幅降低了消息发送的频率(由差不多每秒三次改成了三秒才一次),再加上不需要读取键鼠输入,所以 CPU 占用也会大幅减少。另外内核也不会再打印「drm_dp_i2c_do_msg: 2 callbacks suppressed」的消息了,大概是因为消息频率降低了?重新连接显示器之后,和大上原版程序一样有概率出现显示器亮蓝灯、屏幕不工作的情况。拔插一下电源可解。

当然啦,如果有人要用这个程序的话,记得先确认一下你的 i2c 设备文件路径(去 lsof 大上原版程序就行)。另外,使用此程序后果自负,由此造成的任何设备损坏或者其它损失,我都不负责任的哦~

Category: 硬件 | Tags: 显示器 linux Rust E-ink 硬件
11
26
2019
11

Python 3.8 升级记录

Python 3.8 发布有好多天了,Arch Linux 也早就重新打包了一千多个包(感谢辛勤的肥猫猫),隔天就从 [staging] 进入 [testing] 了,四天之后进入正式仓库([extra] 和 [community])。

Python 3.8 进入官方仓库的次日,我本地进行了更新。之所以要等一天,自然是等 [archlinuxcn] 的更新啦。然后那些需要人工干预而又暂时没人理的我本地重新打包了。使用 pacman -Qo /usr/lib/python3.7/site-packages 查询尚未更新的软件包,然后对着对应的 PKGBUILD 一顿改(基本上也就是 pkgrel 加 0.1 而已),makepkg -si 就好了。

但是这样还没完事哦。

sudo updatedb 更新一下 mlocate 的数据库。然后 locate -be python3.7 | grep -v /var/lib/lxc 找到一些残留的文件,主要是 ~/.local/lib 下的,以及散落在管理之外的 venv 里的。~/.local/lib 下的都是我自己的项目,删掉然后重新去项目里 python setup.py develop --user 就好了。venv 的话,直接删掉吧……

然后是 locate -be python-37 | grep -v /var/lib/lxc | grep -v /usr/lib/python3.7/site-packages。这个是为了查 Python 3.7 的 pyc 文件,所以这次也排除了 Python 3.7 的 site-packages,避免尚未更新的 Python 包的干扰(有些暂时用不到的包我就懒得自己 makepkg 了),等更新完之后整个目录删掉。有些软件包(比如 gdb-common)没有使用标准的 Python 安装流程(比如因为并不是标准的 Python 库),打包者(比如著名的 Allan McRae)没有或者拒绝在打包时编译 pyc 文件,造成 Python 自行创建不被管理的 pyc 文件,软件包卸载或者 Python 升级后就残留下来了。

确认没有问题之后(比如有些软件可能自带了个旧版本的 Python,或者有些并不是 pyc 的文件也包含这个字符串),执行 locate -be python-37 | grep -v /var/lib/lxc | grep -v /usr/lib/python3.7/site-packages | sudo xargs rm -v 删除这些文件。当然如果有需要保留的文件自行从文件列表中删掉先。

pyc 清理之后,接下来清理一下空的 __pycache__ 目录啦。locate -be __pycache__ | sudo xargs rmdir -v 2>/dev/null 就可以了,非空目录不会被删掉的。

哦对了,我现在在用 mypy 了,所以还要 locate -we .mypy_cache/3.7 一下。

我之所以现在记录这事儿,「现在」的原因是,我要在另一个系统上再测试一遍再发布出来,「记录」的原因是,下一次我就不用想要执行哪些命令了。

Category: Linux | Tags: linux python Arch Linux
10
28
2019
19

Poker II 键盘调教记

Poker II 是一款可编程的61键机械键盘,是最小的那种,没有 F1-F12 那一行键。跟 HHKB 有些像。这是我第一次使用这么小的键盘,以前都用的84键的。选择它的原因是,更加小巧,没有旁边的光标移动键,使得打字的时候几乎不需要把手挪来挪去的。编程功能似乎也挺有意思的。我手上这把是红轴的,感觉手感也挺好,虽然没有了青轴那清脆的叫声。照片我就不放啦,网上能搜到的。

研究完说明书,发现它的编程功能并没有想像中的那么好。主要缺点如下:

  • 非默认层会一直亮着个灯,而默认层又不能编程。
  • 只能对非组合键,以及没有预设功能的 Fn 组合键编程。所以额外的 Pn 键很残废。
  • 编程结果无法导入导出。所以哪天不小心重置了键盘,这将导致重复而无趣的劳动。

不过也能凑合着用了。最后我的设置是这样的:

不再使用 xmodmap 来交换 Esc 和 Caps Lock。笔记本键盘改用 hwdb,Poker II 使用内建编程功能。于是我可以在别处(比如手机、BIOS、Win10)使用这把键盘而不感觉别扭与小心翼翼。xmodmap 依旧用来把右 Alt 映射为 Multi(Compose)键,用来输入特殊字符,因为我不知道这个键怎么用 hwdb 映射。哦还要在 /etc/vconsole.conf 里去掉之前给 tty 虚拟终端设置的交换 Caps Lock 和 Esc 的 keymap。

红、绿、蓝三个编程层。红层没什么用,暂时留作测试。绿层作为打字用布局,方向键使用 Fn 组合键完成,Esc 位放 `~。蓝层作为看视频的布局,方向键使用右下角的四个键完成,无处安放的 Pn 暂时放 Esc 位。其余共有映射为:

  • Caps Lock 位放 Esc。
  • 交换 Fn 和右 Alt 键。这样 Fn 键好按一点,反正右 Alt 很少用到。
  • 映射两组 Ctrl-PgUp/PgDn 分别到 Fn-Q/E 和 Fn-O/L。这快捷键非常常用,可以在火狐和 Telegram 切换标签页。

Poker II 编程时有个「编程延迟」设置,我一直没搞明白它要怎么用,也导致我的映射一直有问题,按一次出一到两次。直到后来找到这篇文章,才明白它不是个设置,而是个事件,按下它即导致出键码时延迟指定的时间。

另外我没能在 Poker II 上按出 SysRq 来,不知道是怎么回事。

hwdb 的配置方法来自 ArchWiki Map scancodes to keycodes 页面。我的配置如下:

evdev:atkbd:dmi:*
 KEYBOARD_KEY_01=capslock   # esc
 KEYBOARD_KEY_3a=esc        # capslock
 KEYBOARD_KEY_b7=rightmeta  # prtsc
 KEYBOARD_KEY_c5=print      # pause (Fn+P)

把配置放到 /etc/udev/hwdb.d 下的 .hwdb 后缀文件中,然后执行

sudo systemd-hwdb update
sudo udevadm trigger

就好了。

用了几天了。除了 LED 灯老亮着有些刺眼外,一切安好。也终于把 Caps Lock 的设置方法搬到更底层了。

Category: 硬件 | Tags: 硬件 linux 键盘
10
3
2019
4

红黑树到底是个什么树

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

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

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

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

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

| Theme: Aeros 2.0 by TheBuckmaker.com