---

title: CSAPP Data Lab 做题记录（上） date: 2023-10-01 17:48:39

tags:

CSAPP Data Lab 做题记录（上）

准备工作

访问 http://csapp.cs.cmu.edu/3e/labs.html 试图下载网页上醒目的 datalab.tar，发现需要身份验证。后来发现点后面的小东西可以直接下载。读了 readme 之后知道 datalab.tar 好像是教师用的，用来生成学生的包（datalab-handout），datalab-handout 才是学生用的。

读文档，知道实验是要用位运算来模拟各种整数运算，还要用整数运算模拟浮点运算。好像评测还实现了一个小工具来查是否用到了违规的操作符。

看文档上说需要安装 bison 和 flex，以为检查违规小工具也需要编译，正打算看一下代码发现包里直接发了个二进制文件下来……

发现评测程序是用 Perl 写的，古老。

Driverlab.pm 里好像手写了一个 http 客户端？看起来是搞那个 Beat the Prof 比赛的，应该不用管它。

依照手册指示，要先 make 一下把 btest 给编译好。结果遇到神奇问题：

% 09:19:42 jyi@Syameimaru-Aya ~/s/c/d/c/d/datalab-handout
0 make
gcc -O -Wall -m32 -lm -o btest bits.c btest.c decl.c tests.c
In file included from btest.c:16:
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory
   27 | #include <bits/libc-header-start.h>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
In file included from decl.c:1:
/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory
   27 | #include <bits/libc-header-start.h>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from tests.c:3:
/usr/include/limits.h:26:10: fatal error: bits/libc-header-start.h: No such file or directory
   26 | #include <bits/libc-header-start.h>
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.
make: *** [Makefile:11: btest] Error 1

检查了一发发现是 makefile 里指定了 -m32 但是我没有 32 位的库，装了个 gcc-multilib。至于为啥不用 -m64 编译……因为那里面说什么 "not 64-bit safe"，没太懂。

题目列表

bitXor

给定两个数，返回他们的异或。

首先由真值表写出把异或运算写成最小项之和的形式，就是 $X \oplus Y = X\bar{Y} + \bar{X}Y$。然后跑跑发现零分，是因为我们没有 | 可以用……用德摩根定律画画柿子得到 $\bar{\bar{X\bar{Y}}\bar{\bar{X}Y}}$，避开 |，就能过了。

int bitXor(int x, int y) {
  return ~(~(~x & y) & ~(x & ~y));
}

tmin

返回最小的有符号整数。

题目假设机器使用补码表示法，我们知道这个数的位模式应该长得比较像 1000...000。题目又假设了我们机器上的整数都是 32 位的，所以我们把 1 左移 31 位返回就行了。

int tmin(void) {
  return 1 << 31;
}

isTmax

判断给定的 x 是不是最大的有符号整数。

考虑到题目假定机器采用补码表示法，最大的有符号整数 tmax 的位模式应该是 01111...111。好像把 tmin 的结果取反就是了，但是他没给 << 操作符，题目又禁止使用超过 255 的整数，所以 tmax 应该搞不出来。

倒是有一个检查加一向上溢出（假设溢出的行为和无符号整数差不多）取反后是不是和自己相等（~(x + 1) == x）的想法，但是有符号数溢出好像是 ub 啊。题目也没有规定溢出会采用什么方式。

先这么做好了……-1 要特判一下因为 -1 取反加一后马上就溢出了。

int isTmax(int x) {
  return (!((~(x + 1)) ^ x)) & (!!(x + 1));
}

allOddBits

判断给定 x 的奇数二进制位上是否全为 1。

……这样吗？

int allOddBits(int x) {
  return (x >> 1) & (x >> 3) & (x >> 5) & (x >> 7) & (x >> 9) &
  (x >> 11) & (x >> 13) & (x >> 15) & (x >> 17) & (x >> 19) &
  (x >> 21) & (x >> 23) & (x >> 25) & (x >> 27) & (x >> 29) &
  (x >> 31) & 1;
}

测了一下发现性能分数没有拿到，最多只能使用 12 个操作符，而这里用了 33 个。考虑进行优化。因为我们可以直接使用 8 位整数，所以我们可以考虑将输入的东西每 8 位与一下，再用一个掩码检查得到的东西奇数位上是否都为 1。这样就能减少计算了。

int allOddBits(int x) {
  return !((x & (x >> 8) & (x >> 16) & (x >> 24) & 0xaa) ^ 0xaa);
}

只用了 9 个操作符耶！

negate

求给定数的相反数。

这个可以使用我们熟知的小结论，把 x 取反后再加一直接得到结果，非常简单。

int negate(int x) {
  return (~x) + 1;
}

isAsciiDigit

判断给定输入是不是 ASCII 编码中的数字。

我们已经有了比较两个数字是否相等的便利算法，只要打表检查是否等于每个可能的数字，将结果或起来就是最终答案。但是这样显然是拿不到性能分的嘛。

嗯……如果 x 的最高位为 1，那它是个负数，就不是 ASCII 的数字了。排除这种情况后，接下来就只要考虑正数比大小。

发现异或的结果的最高位是两个数字第一个不同之处，找出谁是 1 谁就更大。问题就变成了如何取一个数的最高位。并没有想到什么取一个数最高位的便利算法……

考虑利用一下题目特性，ASCII 的 0 和 9 是 110000 和 111001，想到搞一个东西来检查 x 的前面 26 位是否全为 0，而且第 5、6 位为 1。接着再判断后四位是否符合第四位为 0，或者第 2、3 位为零……

折腾一下得到这样的答案：

int isAsciiDigit(int x) {
  return (!((~0x3f) & x)) & (!((0x30 & x) ^ 0x30)) &
      (!(0x8 & x) | (!(0x6 & x)));
}

轻松过关

conditional

实现类似三目运算符的功能。

要实现 x ? y : z 的话，应该很容易想到 (!!x) * y + (!x) * z 这种的……但是我们没有乘号。可以想到使用与号替代一下，就是想办法弄一个掩码，当 x 为真时它是全 1，x 为假时它是全零这种的。感觉比较简单。

代码里为了节省符号把掩码弄成当 x 为真时是全 0，x 为假时是全 1。使用方法还是差不多的吧。

int conditional(int x, int y, int z) {
  int mask = !x;
  mask = (mask << 1) | mask;
  mask = (mask << 2) | mask;
  mask = (mask << 4) | mask;
  mask = (mask << 8) | mask;
  mask = (mask << 16) | mask;
  return ((~mask) & y) | (mask & z);
}

写后面的 howManyBits 的时候获得了重大技术革新，现在有一种便利操作来生成掩码了！

int conditional(int x, int y, int z) {
  int mask = (~(!x)) + 1;
  return ((~mask) & y) | (mask & z);
}

如果 x 是 0，则 ~(!x) 位模式为 1111...1110，加 1 后刚好是全 1。

如果 x 是 1，则 ~(!x) 位模式为 1111...1111，加 1 向上溢出后刚好是全 0。

isLessOrEqual

判断给定的两个数是否满足小于等于关系。

小于等于就是不大于嘛，接下来考虑判断两个数的大于关系。

这个好像在 isAsciiDigit 那个题里的踩过一次，所以接着思路往下想……如何取一个数的最高位。发现取最高位的话怎么写都会拿不完性能分。

突然想到好像两个数相减一下再判断结果是否为正数就行，原来刚刚想那么多是脑子打结了。

先判断两个数是否正好为一正一负，如果是的话可以直接给结果。否则相减判断结果正负，这时两个同号的数相减必不可能溢出。

int isLessOrEqual(int x, int y) {
  return (((x >> 31) & 1) | (!(y >> 31))) &
      ((((x >> 31) & 1) & (!(y >> 31))) | (!((y + (~x) + 1) >> 31)));
}

拿下。

logicalNeg

实现逻辑非，不能使用感叹号。

感觉和 allOddBits 很像！只不过那个是求奇数位上全为 1，这里是求存在某一位为 1。

用类似的方法实现一下就好啦。

int logicalNeg(int x) {
  x = x | (x >> 16);
  x = x | (x >> 8);
  x = x | (x >> 4);
  x = x | (x >> 2);
  x = x | (x >> 1);
  return 1 ^ (x & 1);
}

最后 return 那个奇怪的表达式其实是 1 - x 拆过来的。发现直接写 2 + (~x) 会拿不到性能分，符号刚好多一个。

howManyBits

求最少用多少个位可以表示出给定数字。

其实就是 $\log_{2}$ 啦。

先假定 x 是负数，根据补码表示法我们需要能够表示 $[ x, -x - 1 ]$ 的所有数。全部当成无符号整数之后需要表示的范围是 $[0, ((~x) << 1) + 1]$，只要我们能够用一些位表示出最大的数，那么这些位一定可以表示出所有数。因此答案就是 $\log_{2}(((~x) << 1) + 1)$（向上取整）。

同理，如果 x 是正数，则需要能够表示 $[ -x - 1, x ]$ 的所有数，答案是 $\log_{2}((x << 1) + 1)$。

至于如何取对数……猜测是要使用类似 logicalNeg 和 allOddBits 那样类似分治（？）的做法来完成，先考虑分成两半的情形：如果高 16 位不为零，可以给答案加上 16，接着再把高 16 位移动到低 16 位，按照类似的方式处理低 16 位；如果高 16 位为零，则直接处理低 16 位。依次类推直到处理完只剩一位的情况。

用力实现一下就好了。

int howManyBits(int x) {
  int ans = 0;
  int h16, h8, h4, h2, h1, h0;
  int sign = x >> 31;
  int range = (((x & (~sign)) | ((~x) & sign)) << 1) + 1;

  h16 = (~(!!(range >> 16))) + 1;
  ans = ans + (h16 & 16);
  range = range >> (h16 & 16);

  h8 = (~(!!((range >> 8) & 0xff))) + 1;
  ans = ans + (h8 & 8);
  range = range >> (h8 & 8);

  h4 = (~(!!((range >> 4) & 0xf))) + 1;
  ans = ans + (h4 & 4);
  range = range >> (h4 & 4);

  h2 = (~(!!((range >> 2) & 0x3))) + 1;
  ans = ans + (h2 & 2);
  range = range >> (h2 & 2);

  h1 = (~(!!((range >> 1) & 0x1))) + 1;
  ans = ans + (h1 & 1);
  range = range >> (h1 & 1);

  h0 = (~(range & 0x1)) + 1;
  ans = ans + (h0 & 1);

  return ans;
}

真不容易！

---

title: CSAPP Data Lab 做题记录（下） date: 2023-10-01 17:48:39

tags:

CSAPP Data Lab 做题记录（下）

摸了好几天，来做浮点部分……

题目列表

floatScale2

传入一个无符号整数，把它当作单精度浮点数，乘二后输出。

很自然地想到提取出符号、阶码和尾数，接着根据是否为规格化的浮点数分情况处理，拼起来返回，比较简单。

unsigned floatScale2(unsigned uf) {
  int sign, expo, frac;
  int bias = 127;
  sign = (uf >> 31) & ((1 << 1) - 1);
  expo = (uf >> 23) & ((1 << 8) - 1);
  frac = uf & ((1 << 23) - 1);
  if (expo == 0xff)
      return uf;
  if (expo) {
      ++expo;
      if (expo == 0xff)
          frac = 0;
  } else {
      frac *= 2;
      if (frac & (1 << 23)) {
          expo = 1;
          frac &= ~(1 << 23);
      }
  }

  return (sign << 31) | (expo << 23) | frac;
}

floatFloat2Int

传入一个无符号整数 uf，把它当作单精度浮点数，返回它截断后的整数部分。也就是 (int)uf。如果出现溢出，则返回 0x80000000u（书上说这是与 Intel 兼容的微处理器指定的 “整数不确定” 值）。

感觉也比较简单……弄出阶码、尾数之后，暴力移位就行了。

代码里最后根据 sign 决定返回 ans 还是 -ans，而没有考虑最终结果为 INT_MIN，导致计算 ans 时溢出的问题。是因为 32 位的 float 类型无法精确表示 32 位的 INT_MIN，所以这里不用考虑 int 正负表示区间不对称的问题。

int floatFloat2Int(unsigned uf) {
  int sign, expo;
  unsigned frac;
  int ans;
  int bias = 127;
  int error = 0x80000000u;
  sign = (uf >> 31) & ((1 << 1) - 1);
  expo = (uf >> 23) & ((1 << 8) - 1);
  frac = uf & ((1 << 23) - 1);

  if (expo == 0xff)
      return error;
  expo -= bias;
  if (expo < 0)
      return 0;
  if (expo > 31)
      return error;
  frac |= (1 << 23);
  frac <<= 8;
  frac >>= (31 - expo);
  ans = frac;
  if (sign)
      ans = -ans;
  return ans;
}

floatPower2

传入一个整数 $x$，返回单精度浮点数 $2^x$。如果结果太小则返回 0，太大则返回 +INF。

非常简单，只要改阶码部分，尾数部分保持全零即可。

unsigned floatPower2(int x) {
    int bias = 127;
    int sign = 0;
    int expo = x + bias;
    int frac = 0;

    if (expo >= 0xff)
        expo = 0xff;
    if (expo <= 0)
        expo = 0;

    return (sign << 31) | (expo << 23) | frac;
}

总结

总体来看浮点数部分比整数部分简单，没准是因为前面写整数时把各种运算练得比较熟了？

做完了之后感觉自己对计算机中数字表示理解加深了甚至感觉可以全用位运算来实现各种操作符。

还有就是觉得整数的补码表示与 IEEE754 浮点数的一些性质特别神奇，怎么说不愧是广泛使用的标准。

调试时用了不少之前几乎没用过的联合体（union），应该说终于意识到这个东西怎么用了……

测试结果

![show1.png](https://i.loli.net/2019/09/01/v5iCQLzWnjI2h6N.png)
![show2.png](https://i.loli.net/2019/09/01/z3k8bMJ6DqY9prh.png)

![show1.png](https://cdn.luogu.com.cn/upload/image_hosting/lsp7f3e4.png)
![show2.png](https://cdn.luogu.com.cn/upload/image_hosting/1oy9pwhi.png)

---

title: 【睡前故事】牛郎织女的故事 date: 2023-10-01 17:48:39

tags:

【睡前故事】牛郎织女的故事

这是一个很美丽的，千古流传的爱情故事，成为我国四大民间爱情传说之一。

传说，天上有很多 core，这些 core 按照访问不同内存的性能，被划分为了若干 NUMA node。

在 NUMA node0 上，CPU2 住着织女，CPU4 住着牛郎。织女喜欢做大量浮点运算，她最喜欢的便是快速平方根倒数的计算。牛郎则更喜欢做整数计算。每天早晨被操作系统 swap in 之后，牛郎和织女便同时开始工作。他们存取同一片内存的数据，两人便逐渐熟悉起来。

「你的 CPU time 好多呀，看起来很忙的样子。」在两人都因为 cache miss 而无聊等待时，牛郎对织女说道。织女看了一眼 dstat(1)，发现牛郎的机时也不少。她回答说：「我在做超多矩阵乘法，你呢？」牛郎说：「我在算超大文件的哈希呢。」

久而久之，织女和牛郎情投意合，心心相印。可是，天条律令是不允许男欢女爱、私自相恋的。织女是王母的孙女，王母便将牛郎贬到了 NUMA node1 里。牛郎想取到 NUMA node0 中的数据，需要走 QPI 总线，等待很长很长的时间。这便形成了人们所熟知的 NUMA 效应。从此，牛郎和织女再也不能像以前在同一个 NUMA node 的时候一样，随意相见了。

自从牛郎被贬之后，织女常常以泪洗面，愁眉不展地思念牛郎。她闷闷不乐地宅在 CPU2 里，整天算超级大矩阵，以期博得王母大发慈心，让牛郎早日返回 NUMA node0。

一天，几个仙女向王母恳求想去 NUMA node1 CPU3 一游，王母今日心情正好，便答应了她们。她们见织女终日苦闷，便一起向王母求情让织女共同前往，王母也心疼受惩后的孙女，便令她们速去速归。

话说牛郎被贬之后，落生在 CPU1 中。牛郎跟着哥嫂度日。哥嫂待牛郎非常刻薄，要与他分家。哥哥嫂嫂把牛郎 renice(1) 成了 19，只给他一点点机时，其他的都被哥哥嫂嫂独占了，然后，便和牛郎分家了。

牛郎不再是天庭的一员，不再会被 pin 到某个 CPU 上。每天，他在 CPU1、CPU3、CPU5 之间辗转，饱受进程调度之苦。因为被 renice(1) 成了 19，牛郎被调度的时间比别的进程少了许多，只有等系统比较闲的时候，牛郎才有机会出来透透气。

一两年后，牛郎也有了一个小小的家，勉强可以糊口度日。可是，冷清清的家只有牛郎一个人，日子过得相当寂寞。无聊的时候，牛郎便算算他和织女第一次相遇时，算的 sha512sum，回忆从前的美好时光。

这一天，NUMA node1 突然热闹起来。有几个新的进程，来到了 CPU3 上。牛郎躲在 CPU5 一看，发现是一群仙女。仙女们见有人偷看，纷纷像飞鸟般地飞走了，只剩下一个正在算开方倒数的仙女，她正是织女。织女看着 CPU5 里跑的进程，感觉有些熟悉。这时，牛郎走上前来，对她说，要她答应做他妻子。织女定睛一看，才知道眼前便是自己日思夜想的牛郎，便含羞答应了他。这样，织女便做了牛郎的妻子。

他们结婚以后，男耕女织，相亲相爱，日子过得非常美满幸福。不久，他们生下了一儿一女，十分可爱。牛郎织女满以为能够终身相守，白头到老。

可是，王母知道这件事后，勃然大怒，马上派遣天神仙女捉织女回 NUMA node0 问罪。瞬间，天空狂风大作，天兵天将从天而降，不容分说，押解着织女便上了总线。

正飞着、飞着，织女听到了牛郎的声音：「织女，等等我！」织女回头一看，只见牛郎用一对 ucontext 挑着两个儿女赶来了。慢慢地，他们之间的距离越来越近了，织女可以看清儿女们可爱的模样子，孩子们了都张开双臂，大声呼叫着「妈妈」，眼看，牛郎和织女都到了 NUMA node0 上，就要相遇了。可就在这时，王母驾着祥云赶来了，她拔下她头上的金 taskset(1)，往他们中间一 pin，霎时间，牛郎被 pin 到了 CPU0 上，织女被 pin 到了 CPU2 上。

CPU0 和 CPU2 是一个物理核心超线程出来的两个核，本身就无法像 CPU2 与 CPU4 那样实现完全的并行。再加上天庭计算任务繁重，经常有无关的其他进程被调度到 CPU0 和 CPU2 上运行，织女每次醒来，都只能看到队列里的牛郎处于就绪态，直哭得声嘶力竭，牛郎和孩子也哭得死去活来。他们的哭声，孩子们一声声「妈妈」的喊声，是那样揪心裂胆，催人泪下，连在旁观望的仙女、天神们都觉得心酸难过。王母见此情此景，也稍稍为牛郎织女的坚贞爱情所感动，便同意让牛郎和孩子们留在天上。其他进程也于心不忍，便纷纷 sched_setaffinit(2)，使自己不被调度到 CPU0 和 CPU2 上。

从此，很少再有其他进程调度到 CPU0 和 CPU2 上，这个物理核心成为牛郎和织女的小家。织女喜欢浮点运算，她经常使用 FPU 和寄存器 st*；牛郎做的多是整数运算，他使用 ALU 和寄存器 r*。正好错开了，使得他们有更多的机会同时执行。牛郎和他的儿女就住在了天上，和织女在同一个物理核心上，努力地填满 CPU 的执行单元。在秋夜天空的繁星当中，我们至今还可以运行 top(1)，发现 NUMA node0 上有两个 CPU，他们的使用率为 100%。那便是织女和牛郎。

传说，每年的七月七日，若是人们在机房中静静地听，可以隐隐听到仙乐奏鸣，织女和牛郎在深情地交谈。后来，每到农历七月初七，相传牛郎织女同时由于访存卡住的日子，姑娘们就会来到机房里，寻找 NUMA node0 的牛郎和织女，希望能看到他们相会，乞求上天能让自己能象织女那样心灵手巧，祈祷自己能有如意称心的美满婚姻，由此形成了七夕节。

---

title: 从 zerotier 迁移到 headscale date: 2024-02-25 19:28:48+08:00

tags:

前言

zerotier 是我正在用的虚拟局域网设施。它的主要特性就是能用 UDP 打洞 技术，在没有公网 IP 地址的情况下实现 P2P 连接。tailscale 是它的类似物。

今天从网上看到了一份 评测 ，里面提到：

• Tailscale: Download speed: 796.48 Mbps, Upload speed: 685.29 Mbps
• ZeroTier: Download speed: 584.17 Mbps, Upload speed: 406.12 Mbps

看起来 tailscale 比 zerotier 快不少。于是决定把现有的 zerotier 网络迁移到 tailscale 上面去。

中继服务器 headscale 架设

想了想，现在的 zerotier 网络由于大陆没有中继服务器，打洞偶尔会非常不顺利。tailscale 和 zerotier 一样在大陆没有中继服务器，估计也会遇到一样的问题。最好的解决方案也许就是使用 tailscale 的开源实现，headscale 自建一个中继服务器。

所以，决定自建 headscale 服务！

因为 headscale 服务需要在节点建立 P2P 连接时提供帮助，所以需要所有节点即使在没有 tailscale 网络时，也能连接到 headscale 服务。也就是说，headscale 服务需要一个公网 IP。因此，我只能在我的 VPS 上搭建服务。

为了保持现在依赖 zerotier 网络的服务依然能够运行，我需要保证新的 tailscale 网络里设备依然有它们原本在 zerotier 网络里时 的 IP。为了避免 IP 地址冲突，首先，删掉原来就有的 zerotier：

0 apt autoremove zerotier-one
[sudo] password for jyi:
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
The following packages will be REMOVED:
  zerotier-one
0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
After this operation, 11.3 MB disk space will be freed.
Do you want to continue? [Y/n] Y

接着，参考 headscale 的 Linux 安装指南。我们的 VPS 是 Debian bookworm 发行版，amd64 架构。因此，我们先下载对应的 deb 包，然后安装：

wget https://github.com/juanfont/headscale/releases/download/v0.22.3/headscale_0.22.3_linux_amd64.deb
apt install ./headscale_0.22.3_linux_amd64.deb

接着来配置 headscale。因为端口很难记，所以我们先用 nginx 给它反向代理一下，让它可以使用酷炫的维尔薇爱好者特供域名和 SSL ：

map $http_upgrade $connection_upgrade {
    default      keep-alive;
    'websocket'  upgrade;
    ''           close;
}

server {
        listen 443 ssl http2;
        listen [::]:443 ssl http2;

        ssl_certificate  XXXXXXXXXXXXXXXXX;
        ssl_certificate_key XXXXXXXXXXX;
        ssl_protocols TLSv1.2 TLSv1.3;

        server_name headscale.villv.tech;

        location / {
                proxy_pass http://127.0.0.1:18002;
                proxy_http_version 1.1;
                proxy_set_header Upgrade $http_upgrade;
                proxy_set_header Connection $connection_upgrade;
                proxy_set_header Host $server_name;
                proxy_redirect http:// https://;
                proxy_buffering off;
                proxy_set_header X-Real-IP $remote_addr;
                proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
                proxy_set_header X-Forwarded-Proto $http_x_forwarded_proto;
                add_header Strict-Transport-Security "max-age=15552000; includeSubDomains" always;
        }
}

这样配好了以后，就可以用 headscale.villv.tech 访问我们监听 18002 端口的 headscale 服务了。我们再编辑 /etc/headscale/config.yaml 把 headscale 服务配好（配置文件中有详细的注释，不再给出示例）。

写 headscale 配置时发现它只支持 110.64.0.0/10 这一个网段，和原来 zerotier 的 172.27.0.0/16 完全不在一个段。它还不支持改网段，这下 zerotier 白删了。tailscale 给了个 解释 说明为什么用这个段（ 但是没说为什么不支持改）。其中有句话特别好玩：

The addresses are supposed to be used by Internet Service Providers (ISPs) rather than private networks. Philosophically, Tailscale is a service provider creating a shared network on top of the regular Internet. When packets leave the Tailscale network, different addresses are always used.

好耶，我现在也是个 ISP 了！

不管怎么样，总之 headscale，启动！

root:/etc/nginx/sites-enabled# systemctl enable --now headscale.service
Created symlink /etc/systemd/system/multi-user.target.wants/headscale.service → /lib/systemd/system/headscale.service.
root:/etc/nginx/sites-enabled#

客户端 tailscale 安装

首先，VPS 作为网关，肯定得加入我们的 headscale 网络，这样才能把流量转发到我们在 headscale 网络里的服务中。所以，先试着在 VPS 上安装。

注意，你可以需要辗转两个组织（headscale 和 tailscale）提供的文档，才能把它玩起来。

依照 tailscale 提供的 安装指南 ：

curl -fsSL https://pkgs.tailscale.com/stable/debian/bookworm.noarmor.gpg | sudo tee /usr/share/keyrings/tailscale-archive-keyring.gpg >/dev/null
curl -fsSL https://pkgs.tailscale.com/stable/debian/bookworm.tailscale-keyring.list | sudo tee /etc/apt/sources.list.d/tailscale.list
apt update
apt install tailscale

接着，再依照 headscale 提供的 接入指南

在 headscale 服务器上执行：

root:~# headscale users create jyi
User created
root:~# headscale --user jyi preauthkeys create --reusable --expiration 24h
XXXXXXXXXXXXXXXXX980f40768460b1025aXXXXXXXXXXXXX

获取到一个连接密钥。

接着在需要连接到 headscale 服务的 tailscale 客户端上执行，并且带上刚刚获取的连接密钥：

root:~# tailscale up --login-server https://headscale.villv.tech --authkey XXXXXXXXXXXXXce90980f4XXXXXXXXXXXXXXXXXXXXXXXXXX
root:~#

搞定！接下来检查一下自己是否已经拿到了 tailscale 的 IP 地址：

root:~# ip a
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1000
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
    inet6 ::1/128 scope host noprefixroute
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc fq_codel state UP group default qlen 1000
    link/ether 00:16:3e:03:0b:6e brd ff:ff:ff:ff:ff:ff
    altname enp0s5
    altname ens5
    inet 172.20.113.58/20 metric 100 brd 172.20.127.255 scope global dynamic eth0
       valid_lft 314157516sec preferred_lft 314157516sec
    inet6 fe80::216:3eff:fe03:b6e/64 scope link
       valid_lft forever preferred_lft forever
7: tailscale0: <POINTOPOINT,MULTICAST,NOARP,UP,LOWER_UP> mtu 1280 qdisc fq_codel state UNKNOWN group default qlen 500
    link/none
    inet 100.64.0.1/32 scope global tailscale0
       valid_lft forever preferred_lft forever
    inet6 fd7a:115c:a1e0::1/128 scope global
       valid_lft forever preferred_lft forever
    inet6 fe80::84bd:1f32:8594:e3b/64 scope link stable-privacy
       valid_lft forever preferred_lft forever

发现，大功告成！

然后，我们再在另一台机器（我的 homelab）上做类似的事情，在上面配置好 tailscale 的客户端。

最后，试着 ping 一下：

warmhome 21:01 ~
0 tailscale ip
fd7a:115c:a1e0::2
100.64.0.2
warmhome 21:01 ~
0 ping 100.64.0.1
PING 100.64.0.1 (100.64.0.1) 56(84) bytes of data.
64 bytes from 100.64.0.1: icmp_seq=1 ttl=64 time=27.3 ms
64 bytes from 100.64.0.1: icmp_seq=2 ttl=64 time=26.9 ms
^C
--- 100.64.0.1 ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1001ms
rtt min/avg/max/mdev = 26.926/27.125/27.324/0.199 ms

好耶，ping 通了！而且通过 tailscale 网络 ping VPS 的延迟基本上和直接 ping VPS 的物理地址的延迟一样，感觉很不错。

---

title: 友链 date: 2023-10-01 17:48:39

tags:

友链

cyx 吃夜宵：https://yxchen.net/ hjx 喝喜酒：https://honeta.site/ zwd 朝闻道：https://vaaandark.top/ lxy 灵犀玉：https://ccviolett.github.io/ ljm 逻辑门：https://watari.xyz/ ljh 梁家河：https://www.newuser.top/ lg 蓝狗：https://ligen.life/ yxt 游戏厅：https://blog.just-plain.fun/ lyt 老樱桃：https://i.lyt.moe/ dekrt 不知道谁：https://dekrt.cn/

用来方便在博客园上传链接的便利脚本： bash IFS=" " for i in $(awk -F： '/：.*\/$/ { print $1" "$2"\n"$2 }' a.md); do echo "$i" echo "$i" | clip read _ done

---

title: CPC 2023 简明总结 date: 2023-10-01 17:48:39

tags:

CPC 2023 简明总结

记录我印象里的 CPC 2023 的大概流程。想着 BBHust 上面的大家不一定都对并行编程很感兴趣，所以省略了大部分纠结与调试的故事，只留下了好玩的部分。

比赛要和其他选手比拼技术，所以算是 “竞技”。因为经常睡不好，考验身体素质，所以也是某种很新的 “体育”。四舍五入 CPC 也是竞技体育。

比赛简介

CPC 是 “国产 CPU 并行应用挑战赛” 的简称。赛制大概是，主办方给出一个程序，让选手在特定架构的机器上优化，最后谁的程序跑得快谁就赢了。

今年主办方给的机器是一台名叫 “神威·问海一号” 的超级计算机，它是 “神威·太湖之光” 的后继者，国产超级计算机的明星之一。关于超级计算机，大家简单地理解成 “在上面用某些华丽的技巧编程，写出来的程序可以跑得很快” 的奇特电脑就可以了。

遗憾地是，这个国产超级计算机的硬件设计有很多不足。整个问海一号的架构被我们称为 “硬件设计友好型架构” —— 硬件工程师设计时自己怎么偷懒怎么来，给软件工程师（嗨呀，这是我）造成了诸多限制，使得我们在这个架构上编程难度颇大。同时，问海一号的现象还比较反常识，许多指令的加速效果远远不如它们在 x86 上的等价物。

我愿称其为 超算原神 。

初赛

初赛的任务是优化一个大程序中的小部分，和我们平时做的东西挺像。

我负责的部分是数据划分。就是把一个巨大的矩阵，切成很多个小小矩阵，让我的队友们写的代码来做后续处理。它只要满足划分出的任务量尽可能负载均衡、队友使用我的划分结果足够方便、缓存十分友好、能够适应不同的数据规模大小、不带来额外的数据转换开销等等条件的基础上跑得足够快就好了。最后我就写了这么一个东西。

“我什么都做得到！” —— 我，于七边形活动室，写完这部分代码之后

初赛的代码全是用 C 和 C++ 写的，很友好。我能很轻松地把一部分模块抽出来放到 x86 的架构上优化，再把优化后的代码给缝到原来的项目里面。这样原来自己熟悉的 perf 等等工具链就都可以用了。相比性能分析工具都要自己写的神威架构，x86 简直是天堂。

比赛后期队友 P 同学发挥奇思妙想，参考 OpenGL 的双缓冲技术，设计了一组面向 DMA 操作的双缓冲数据结构与 API，成功地将数据传输的开销掩盖在了计算下面，获得了巨量的性能提升。堪称最有想象力的一集。

还有个非常欢乐的事情是，神威架构上的 512 位浮点 SIMD 加速比仅有 1.8x 左右。经过我的仔细思考，我觉得可能神威在实现 SIMD 的时候就是单纯地给前端解码加了条指令，后端实际还是逐个逐个元素计算的……相当于仅省略了解码开销。不知道是不是真的但是很符合我对神威的想像。

很遗憾，初赛到现在已经过了两个多月了，期间经历了期末考试、构造动画片电视台、升级重构 bot、研究跨平台包管理器、无聊的并行计算课、学 vscode、学习怎么逛街、配置全新网络文件系统、研究 AMD ROCm、打工以及最终暑假结束了也没找到女朋友等诸多好玩的事情，具体初赛时发生了什么我已经几乎忘光了（其实暑假做了什么我也几乎忘掉了，这个列表是参考 bash history 和 bot 聊天记录写出来的），只留下了印象最深的一点点事情。也许应该发展一下写日记的习惯……或者用 bot 代劳写日记的习惯。

决赛

决赛的任务是优化一个巨大的 Fortran 项目，和我们平时做的东西一点也不像。

决赛刚刚开始的几天我恰好开始实习，就拿到了一份任务列表。拿着做了两三天发现自己要是想跟上任务表的进度，每天都会很累，回到酒店后根本就没啥精力和心情来搓 CPC 的傻逼 Fortran 代码。于是研究了一下换人的可能性。但是就在换人讨论的后一天上班时，无意间发现自己拿到的好像是一个月量的任务表，但是自己把它当成一周的量来做了。本来还以为是什么万恶扒皮公司压榨实习生的剧情，结果现在直接做上了做一休三的悠闲生活。因为突然多出了不少空闲时间，我就接着打 CPC 比赛了。

实习公司的网络管制很严格，要和它的防火墙斗智斗勇才能成功打洞连上比赛的集群。比赛开打的前几天，网络相关的知识猛增……

决赛集齐了 Fortran、神威、大项目 等多种我们的短板，所以游戏体验并不良好。大量时间被花在了无意义的代码调试上，欢乐的事情很少很少……每天最快乐的事情就是骂骂神威。

之前大家还是一直认为 “Machine is always right” 的，但是在神威上编了几个月程，遇到了一堆问题后，最后几天调试代码我都有点开始相信风水了。总之，在神威机器上编程的时候，遇到问题除了排查自己的代码中出现的问题外，还要排查编译器本身的选项、从核同步性等一系列本应由编译器开发人员和硬件设计人员给我们弄好的问题。烦烦烦。

决赛现场

决赛的前一天半夜，队友突然发现比赛集群上的环境疑似被主办方重置了，导致大家的 git 被回滚到了旧版本，某些功能没法用。作为成熟稳重可靠万能的超算队前辈（嗨呀，突然发现参赛小队里只有一个勉强能算后辈，怎么回事呢），我就连夜给它重新装了一个。

现场照片：

决赛比较无聊，到后面有点垃圾时间的意味。于是……

原神，启动！ —— 某不知名 P 同学

星铁，启动！ —— 某不知名 H 同学

以及畅想讨论怎么把比赛现场的 NVidia 的计算卡偷走的时候及时发现后面路过的（名义上的）我们队的指导老师。

神秘收获

感觉这次算是第一次遇到自己没法单刷的比赛，确定了自己并不是什么都做得到。之前因为比赛的工程量都比较小，想了想反正可以单刷就几乎没管过团队合作的事情。但是这次比赛拿到题时就知道这不太是一个人可以搞定的东西，再加上队长和队友都很积极，于是点了一些协作方面的技能。通过交流让四个人达成共识，并一起完成同一件事，感觉是某种很新的体验。

---

title: markdown 中使用图片但是不使用图床 date: 2023-10-01 17:48:39

tags:

markdown 中使用图片但是不使用图床

起因是写博客要插入图片，但是懒得上传图片到图床。经过一番尝试后发现可以把图片 base64 编码后放进 markdown 语法中本应该放图片 url 的位置，直接将图片插进 markdown 文件里。

显然我们需要找出 markdown 中的图片。为了减少图片大小，还需要缩放和压缩。为了偷懒想找找有没有相关的项目可以实现功能。只找到了 markdownImage。但是这个图片压缩好像是调用一些网站的 api 来完成相关功能的，还有免费次数限制，并且并不提供图片缩放功能。感觉和需求出入有点大……

最后我写了个便利脚本来完成这项任务，需要机器上安装了 imagemagick、base64 和 tr。

（这个脚本问题还是比较多，比如没有区分代码块里格式类似图片链接的部分和真正的图片链接，某些情况，比如 markdown 教程估计会锅掉。但是总之还是能用的嘛）

会从标准输入和命令行文件中读取内容，处理后输出到标准输出。（在后面接一个 clip 剪贴板程序就可以直接准备发布到博客园啦）

#!/usr/bin/env perl

use v5.12;

sub process_image
{
    $_ = shift;
    if (/\.gif$/) {
        "data:image/gif;base64," .
        qx {
        convert -fuzz 15% -layers Optimize \Q$_\E - | base64 | tr -d '\n'
        }
    } else {
        "data:image/jpeg;base64," .
        qx {
        convert -resize \Q1280x960>\E -strip -quality 75% \Q$_\E jpeg:- | base64 | tr -d '\n'
        }
    }
}

while (defined(my $line = <>)) {
    for ($line =~ /![[^\]]*\]\([^)]*\)/g) {
        my ($mark, $desc, $file) = /(!\[([^\]]*)\]\(([^)]*)\))/;
        $file = process_image $file;
        $line =~ s/\Q$mark\E/![$desc]($file)/;
    }
    print $line;
}