# 2024q1 Homework1 (lab0)
contributed by < `jiaoshijie` >

老师，我是大陆的一名学生，无意间在网上发现了这个课程，觉得很棒想要跟着学习，抱歉用的**简体字**，因为没有使用过繁体字，表达用词可能会不准确。

:::warning
歡迎，若你能用 Facebook，請用討論區交流。
:notes: jserv
:::

## 开发环境

$gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         48 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  16
  On-line CPU(s) list:   0-15
Vendor ID:               AuthenticAMD
  Model name:            AMD Ryzen 7 7840HS w/ Radeon 780M Graphics
    CPU family:          25
    Model:               116
    Thread(s) per core:  2
    Core(s) per socket:  8
    Socket(s):           1
    Stepping:            1
    BogoMIPS:            7585.30

## 开发记录

### q_sort

在实现 q_sort 函数的时候，一开始实现了一个非递归的快速排序，但因为快速排序在最糟情况下的时间复杂度为 $O(n^2)$，而在测试用例中就存在这中最糟的情况，导致无法通过测试用例。然后实现了一个归并排序来通过测试。

在排序中因为需要对比 `element_t` 类型中的 value 的值。因此定义了一个 cmp 的宏来完成这个简化每次要书写的代码量。

#define cmp(a, b)                                  \
    (strcmp(list_entry((a), element_t, list)->value, \
            list_entry((b), element_t, list)->value))

而且 q_sort 函数还可以通过 descend 参数来指定是否为降序排序。因为这个类型为一个 bool 值，只有最低位会被设置为1或0，因此可以通过 `(cmp(a, b) > 0) ^ descend` 来改变排序的行为。

- 如果 descend 为 `false`，即排序结果为升序，`cmp(a, b) > 0` 为 true， 异或 descend 后依然为 true。
- 如果 descend 为 `true`，即排序结果为降序，`cmp(a, b) > 0` 依然为 true，异或 descend 后结果会变为 false。

这个方法的问题是当 a 和 b 相等时的行为会不一致，如当 descend 为 `false` 时不交换 a 和 b，则当 descend 为 `true` 时就会交换 a 和 b，反之亦然。因此当排序要求稳定排序时，需要额外考虑 a 和 b 相等的情况。

另外，因为本程序使用的是双向循环链表，在进行归并排序寻找中间结点时，除了使用快慢指针，还可以定义两个指针，一个指向链表的第一个结点，一个指向链表的最后一个结点，向中间走，当两结点碰面时即为中间结点。

struct list_head *p = head->next, *q = head->prev;
while (p != q && p->next != q) {
    p = p->next;
    q = q->prev;
}

### `q_ascend` 和 `q_descend`

这两个函数实现基本一致，就是一个结点，当这个结点右边有大于(或小于)该节点值的结点时，删除该结点。这两个函数实现时遇到的问题是没想到一个好的算法解决这个问题，暴力求解的话，时间复杂度是 $O(n^2)$，后面去 leetcode 看了原题，下面有一个 hint 显示反过来遍历链表，这个问题瞬间就解决了。

在其它函数的实现上没有遇到太大的问题。

## dudect 算法

根据 《Dude, is my code constant time?》 论文的描述 dudect 算法流程主要可以分为三大步骤：

1. 测量执行时间
2. 对采集的样本进行一些后置处理
3. 进行统计分析验证

### 1. 测量执行时间

- 数据分类

dudect 算法使用 leakage detection test 需要使用两类数据集作为输入数据，论文中将使用的数据集分为了 fix 和 random 两种。random 就是数据集中的数据随机产生，选择一个常量作为数据这个常量一般选取要测试函数的某种特殊情况。在 lab0-c 的实验中，同样使用了 `fix-vs-random` 这种数据集分类方式，fix 在插入时为 0(即向一个空链表中插入)，在删除时为 1(即删除一个只有一个结点的链表)，而 random 在插入和删除时都为随机数。这样做的原因是只要实现的插入和删除函数的功能是正确的，向空链表插入和删除一个只有一个结点的链表一定为 constant time。

- CPU周期计数器(cycle counters)

现代的CPU有提供周期计数器，像 x86 家族的 [TSC](https://en.wikipedia.org/wiki/Time_Stamp_Counter) 寄存器，ARM 也有一个可选的 systick peripheral 可用。当然也可以使用一个 high-resolution timer 来计算时间。

在使用 TSC 时也有需要注意的情况，因为每个 CPU core 的 TSC 寄存器的值是不同的。

- 环境因素的影响

一个程序在运行过程中可能会被各种情况打断(如一些中断)，从而导致测量不准确，因此为了确保两个类别可以相对公平的运行，每次执行的类别也是随机的。在 lab0-c 的实验和原论文的样例中，都在 `prepare_input` 函数中使用 `randombit` 函数对每次运行的类别进行了随机初始化。并且对输入数据的初始化是在 `measure` 函数之前完成的，而不是在运行时初始化。

### 2. 对采集的样本进行一些后置处理

- 裁剪数据

虽然使用上述的方法可以避免一些测量误差，但依然有可能产生异常数据，因此可以使用某种方法对数据进行裁剪。lab0-c 实验并没有实现该功能，但论文源代码有实现相关功能。

论文中源代码裁剪数据的依据是将第一次采样的数据排序后，划分为多个阈值，并同时申请多个 `t_context_t` 来保存满足不同阈值的数据，最后选择最大的 t 值作为判断依据。

如下面代码(来自论文源代码)，`DUDECT_NUMBER_PERCENTILES` 宏指明要添加100个阈值，可以对应下面 `dudect_init` 函数中对 `ctx->percetiles` 的初始化。而 `DUDECT_TESTS` 为 `ttest_ctxs` 的个数，大小为 `DUDECT_NUMBER_PERCENTILES + 2`，其中 `DUDECT_NUMBER_PERCENTILES` 就是存放满足特定阈值的 `dudect_ctx_t`，而前面的 1 为存放所有的采样结果(也就是没有裁剪的数据)，后面的 1 为 higher-order preprocessing 使用的为 Centerd Product 方法。

#define DUDECT_NUMBER_PERCENTILES  (100)
// ....
#define DUDECT_TESTS (1+DUDECT_NUMBER_PERCENTILES+1)

int dudect_init(dudect_ctx_t *ctx, dudect_config_t *conf) {
    // ...
    for (int i = 0; i < DUDECT_TESTS; i++) {
      ctx->ttest_ctxs[i] = (ttest_ctx_t *)calloc(1, sizeof(ttest_ctx_t));
      assert(ctx->ttest_ctxs[i]);
      t_init(ctx->ttest_ctxs[i]);
    }

    ctx->percentiles = (int64_t*) calloc(DUDECT_NUMBER_PERCENTILES, sizeof(int64_t));
    // ...
}

在 `dudect_main` 中可以看到，首先检查该测试是否为第一次执行，如果为第一次执行就会执行 `prepare_percentiles` 函数更新 `ctx->percentiles`, 第二次执行才会执行 `update_statistics` 函数。

dudect_state_t dudect_main(dudect_ctx_t *ctx) {
    bool first_time = ctx->percentiles[DUDECT_NUMBER_PERCENTILES - 1] == 0;
    // ...
    if (first_time) {
      prepare_percentiles(ctx);
    } else {
      update_statistics(ctx);
      ret = report(ctx);
    }
}

通过观察 `update_statistics` 函数代码可以发现，首先剔除了最开始测量的一些数据 `size_t i = 10;`，然后将 `difference` 先 `t_push` 到 `ttest_ctxs[0]` (未剪枝的样本中)中，然后开始 for 循环，判断这次的数据是否小于 `percentiles[crop_index]` 的阈值，如小于就将其放到特定的剪枝样本中。

  static void update_statistics(dudect_ctx_t *ctx) {
    for (size_t i = 10 /* discard the first few measurements */; i < (ctx->config->number_measurements-1); i++) {
      int64_t difference = ctx->exec_times[i];

      if (difference < 0) {
        continue; // the cpu cycle counter overflowed, just throw away the measurement
      }

      // t-test on the execution time
      t_push(ctx->ttest_ctxs[0], difference, ctx->classes[i]);

      // t-test on cropped execution times, for several cropping thresholds.
      for (size_t crop_index = 0; crop_index < DUDECT_NUMBER_PERCENTILES; crop_index++) {
        if (difference < ctx->percentiles[crop_index]) {
          t_push(ctx->ttest_ctxs[crop_index + 1], difference, ctx->classes[i]);
        }
      }

      // second-order test (only if we have more than 10000 measurements).
      // Centered product pre-processing.
      if (ctx->ttest_ctxs[0]->n[0] > 10000) {
        double centered = (double)difference - ctx->ttest_ctxs[0]->mean[ctx->classes[i]];
        t_push(ctx->ttest_ctxs[1 + DUDECT_NUMBER_PERCENTILES], centered * centered, ctx->classes[i]);
      }
    }
  }

而在 `report` 函数中，在计算 `max_t` 之前会执行一个 `max_test` 函数，该函数的功能是从剪枝的样本中，找出拥有足够样本数且 `t` 最大的那个样本返回。因此在 `report` 函数中，`max_t` 是剪枝样本中 `t` 值最大的那个，来判断是否满足一个容忍值，从而判断待测函数是否满足常量运行时间。

static dudect_state_t report(dudect_ctx_t *ctx) {
    // ...
    ttest_ctx_t *t = max_test(ctx);
    double max_t = fabs(t_compute(t));
    // ...
}

static ttest_ctx_t *max_test(dudect_ctx_t *ctx) {
  size_t ret = 0;
  double max = 0;
  for (size_t i = 0; i < DUDECT_TESTS; i++) {
    if (ctx->ttest_ctxs[i]->n[0] > DUDECT_ENOUGH_MEASUREMENTS) {
      double x = fabs(t_compute(ctx->ttest_ctxs[i]));
      if (max < x) {
        max = x;
        ret = i;
      }
    }
  }
  return ctx->ttest_ctxs[ret];
}

### 3. 进行统计分析验证

下面来解释一下如何使用 Student's t-test 判断两个采样分布是相似的。

先介绍一下统计学中的两个假设 [Null hypothesis](https://en.wikipedia.org/wiki/Null_hypothesis) 和 [Alternative hypothesis](https://en.wikipedia.org/wiki/Alternative_hypothesis)，在统计学中，null hypothesis 和 alternative hypothesis 是相互排斥的两种假设。

如学生实现了一个双向链表的从头插入函数，并认为该函数的执行时间是常量时间，而老师认为不是，并准备实验来验证自己的想法。这里的 $H_0$(null hypothesis) 假设和 $H_a$(alternative hypothesis) 假设分别为：

- $H_0$ 该函数的执行时间是常量时间(要证伪的假设)
- $H_a$ 该函数的执行时间不是常量时间(要证明的假设)

[这个视频有提供更好的例子来解释 $H_0$ 和 $H_a$](https://www.youtube.com/watch?v=wiYJWyfdGg4)

t-distribution 是标准正态分布在有限样本下的一种类型。t-distribution 可以用来描述一组样本大致满足正态分布，但这组样本的方差是不知道的。在用 t-distribution 来描述这组数据时其方差是根据自由度估计的。

t-test 可以被用来检测两组采样样本的均值是否相同，但只有也要求两组采样样本的方差相同时才可以被称为 Student's t-test，否则被称为 Welch's t-test。

[这个视频有使用Welch's t-test的详细步骤](https://www.youtube.com/watch?v=UcZwyzwWU7o&t=671s)

大致流程就是首先计算出 `t` 和自由度 `v`，然后再根据置信度查[表](https://en.wikipedia.org/wiki/Student%27s_t-distribution#Table_of_selected_values)来判断 `t` 是不是再满足条件的范围内。

因为 t-distribution 是一种标准正态分布的一种变体，因此其关于 y 轴对称，因此可以简单的得出 `t` 的绝对值越小，两组样本的均值就越接近。

再 dudect 代码中，并没有计算自由度，而是自己设定了一个值，当 `t` 小于这个值时就通过。

在将 lab0-c 中的代码修改之后，依然无法跑通测试，后续要分析一下什么问题。

## TODO

- [ ] 研读 `lib/list_sort.c` 代码，整合到 lab0-c 中
- [ ] 使用 `qtest` 中的 `web` 命令后，`CTRL-D` 和 `CTRL-C` 不能退出 `qtest`
- [ ] 使用 Fisher-Yates shuffle 算法，为 `qtest` 提供 `suffle` 命令
- [ ] ......

## 参考
- [2024 年 Linux 核心設計/實作課程作業](https://hackmd.io/@sysprog/linux2024-lab0)