10
29
2020
4

tar 归档的权限问题

一次系统升级之后,我的许多 Python 程序突然开始报错:

[...]
  File "/usr/lib/python3.8/site-packages/pkg_resources/__init__.py", line 2762, in _get_metadata
    for line in self.get_metadata_lines(name):
  File "/usr/lib/python3.8/site-packages/pkg_resources/__init__.py", line 1415, in get_metadata_lines
    return yield_lines(self.get_metadata(name))
  File "/usr/lib/python3.8/site-packages/pkg_resources/__init__.py", line 1405, in get_metadata
    value = self._get(path)
  File "/usr/lib/python3.8/site-packages/pkg_resources/__init__.py", line 1609, in _get
    with open(path, 'rb') as stream:
PermissionError: [Errno 13] Permission denied: '/usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/PKG-INFO'

WTF 滚坏了!立即回滚!

回滚完之后,我开始调查这个事件——因为 [archlinuxcn] 的这个包是我管的呀。而且我记得之前也遇到过一次类似的情况,当时没有深究。

检查一下软件包里的文件的权限:

>>> tar tvf python-telethon-1.17.4-1-any.pkg.tar.zst | grep PKG-INFO
-rw------- root/root      3659 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/PKG-INFO
>>> tar tvf python-telethon-1.17.4-1-any.pkg.tar.zst | grep -- ----
-rw------- root/root      3659 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/PKG-INFO
-rw------- root/root     12078 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/SOURCES.txt
-rw------- root/root         1 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/dependency_links.txt
-rw------- root/root        27 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/requires.txt
-rw------- root/root        15 2020-10-24 10:05 usr/lib/python3.8/site-packages/Telethon-1.17.4-py3.8.egg-info/top_level.txt

好奇怪,Telethon 这些包信息文件怎么只让 root 读了呢?

从 PyPI 上下载 Telethon 的原始 tar 归档回来看看,发现最近几个版本里,文件权限全部只有自己可以读(-rw-------),而所有者是 u0_a167/10167。开发者突然在 Android 系统上打包了呢……安装的时候,部分文件的权限被保留了下来(Arch Linux 打包时强烈反对使用 root 权限执行,因此我用 devtools 打包,解包部分自然是普通用户操作的,所有者无法被保留)。

然后我又看了一下之前的版本,哦豁,所有者成开发者的 id 了,但是有三个版本的 pyc 文件,还有好几个 pyc 文件都是 -rwxrwxrwx。大概系统上的低权限用户可以去改改,然后看谁跑 Telegram 机器人就拿谁的权限?

经过跟开发者的讨论,最终干掉了 pyc 文件,也不在 Android 上打包了。777 权限问题还待解决。不过我更在意的是,为什么会发生这种状况呢?setuptools 干嘛不修一修呢?别的工具创建的用于发布的 tar 归档会不会有类似的问题呢?

结果找了找,发现 setuptools 前年就有人报告这个问题,但是并没有解决。行吧,我打包时统一修正一下权限好了……

下一个 GitHub 生成的 tar 归档看看?咦,-rw-rw-r-- root/root,是处理过了么?啊对,git archive 生成的包是怎么样的?去试了试,原来一样的啊。看来 git 想到了这个问题并且处理了,只是 002 的 umask 有点意外。

Arch Linux 为了普通用户打出文件为 root 所有的 tar 归档使用了 fakeroot,那么 git 是怎么实现的呢?翻了翻代码,git 是自己生成 tar 文件的,写死了所有者是 root/root,但是权限位还是有专门的 umask,默认是 002。可以配置,比如git config --global tar.umask user一下,就会取当前 umask 作为 tar 归档里文件的 umask 了。

至于传统的 GNU autotools 构建系统创建的 tar 归档,我也创建了一个看了一下,并没有特殊处理,跟手动跑 tar 一样。

Category: Linux | Tags: linux python Git
7
22
2020
12

Linux 的环境变量怎么设

最近,Arch Linux 的 pam 包将更新到 1.4.0,然后因为一个字符的变化,不少中文用户都开始避难了:pam_env 将默认不读取用户的环境变量设置。许多中文用户使用~/.pam_environment文件来配置 fcitx 输入法所需要的那三个环境变量。更新之后,这些配置将不再生效,意味着他们可能无法输入中文了,于是大家热烈讨论现在要在哪里配置环境变量比较好。

当然了,在 pam 的配置文件里加上user_readenv=1就可以恢复原先的行为。只是,pam 的开发者这么改当然是有原因的:CVE-2010-4708。简单地说,就是在鉴权模块里设置用户指定的环境变量不安全,怕被提权。

2020年08月20日更新:Arch Linux 打包时添加了以上这个配置

当然啦,桌面用户完全可以去改系统级的环境变量设置,只要你愿意让你个人的配置信息跑到系统配置那边去的话。

正文

用户经常需要设置一些环境变量,比如输入法,比如语言和地区选项,比如自定义的 PATH,等等。然而 Linux 的环境变量又不像 Windows 那样有一个专门设置所谓「系统环境变量」的地方,而是所有环境变量全部由子进程继承父进程获得,这么一路继承下来的。于是,想要给所有想设置上的进程都设置上,就不是一件简单的事情了。

这里关注的是桌面用户,自然首先从图形界面说起。

使用 X11 的桌面环境,通常通过 display manager 来登录,比如 lightdm 和 sddm。这俩都支持 ~/.xprofile。这个文件会在启动过程中被 source,使用的 shell 是由 dm 自己确定的。lightdm 和 sddm 都是用的 /bin/sh(分别位于 /etc/lightdm/Xsession 和 /usr/share/sddm/scripts/Xsession 文件里)。可以看到,除了读取 .xprofile 外,lightdm 也会读取 .profile。sddm 甚至连 bash、zsh、tcsh、fish 的启动配置脚本都给读了。

对于 Wayland,我这儿只有 sddm,类似的,也是各种 shell 的都给你读了。(当然就不读 X11 相关的东西了。)

而对于手动 startx 的用户,~/.xinitrc 里自己写上呗。还有 VNC 啥的,也都可以自己看启动脚本找到方法。

没有图形界面的登录,通常是从 tty 或者 ssh 登录。这两者都是登录到命令行 shell。写在 shell 配置里就可以了。具体到 zsh,我是写到 ~/.zprofile,这样不管是否交互,只要是登录 shell 就执行,不登录的大概已经继承到了。另外有些情况可能写这儿也没有用,比如 cron 调用的时候。非要搞的话其实可以写到 ~/.zshenv,这个基本上所有的 zsh 都会读,只能被系统级设置或者命令行参数禁用掉。而如果是 bash 用户,.bash_profile .bash_login .profile 这仨,会读找到的第一个(sddm 也会按这个顺序找,但是 lightdm 只会找 .profile)。Arch Linux 现在默认会给新用户建立 .bash_profile,我建议 bash 用户把它改名成 .profile。这里有个图 ,大致上说明了 bash 和 zsh 不同情况下会读取的配置文件

systemd 用户实例也有一份环境变量,用于通过 systemd 启动的用户级服务,通过 systemctl --user 的子命令可以查看和更新。D-Bus 也有一份,可以通过 dbus-update-activation-environment 命令来更新。这俩通常不需要用户操心,桌面环境应该会维护好。

如果你用 tmux 的话,那么 tmux 还有一份,用于新创建的窗格。tmux 会在被连接时更新 update-environment 选项指定的环境变量。当然你也可以用 tmux setenv 子命令去更新。这个尤其值得注意,因为 tmux 可能在不同的环境中被连接,导致环境变量混乱(比如 X11 下没有 DISPLAY 变量)。

要注意的一点是,不同的登录过程并不是只会读取自己专属的配置文件,尽管大家都在努力,也并没有完全统一好用的配置文件。所以有些环境变量,你可能想尽量避免重复设置(比如冗长重复的 PATH 项就很讨厌)。好在这些都是 shell 脚本,不光能设置环境变量,也能做条件判断。

要查看当前进程的环境变量,可以用 env 命令。要查看别的进程的,去读它的 /proc/PID/environ 文件,或者开个 htop 然后在进程上按 e 键。要看看某个环境变量在不同进程里是什么情况,可以用我写的小工具 compare-env

Linux 软件生态的特点就是这样,没有谁规定一定要用怎样的方式做一件事情,所以大家的想法总会有些出入,就导致设置个环境变量还有这么一大群配置文件(systemd 还有一份呢,我还没读没试所以没说)。但另一方面,理解它们也是十分容易的:不用猜测,不用撞大运般地耗费时间去尝试,顺着代码摸过去,总能弄明白软件的行事逻辑。即使文档像 pam_env 那样前后矛盾,也有源代码这条路可以精确刻画软件的行为。

Category: Linux | Tags: linux 环境变量
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
12

桥接无线网卡!

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

但是 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
6

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
10

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
3

自制大上 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
22

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
6

红黑树到底是个什么树

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

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

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

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

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: 算法 编程

| Theme: Aeros 2.0 by TheBuckmaker.com