hung 之 Android llkd

以 T1 为周期 check 目标进程（所有进程都是目标进程）状态。

每次 check

用变量 count 记录进程在当前状态下持续的时间;

用变量 nrSwitches 记录进程状态切换次数

用变量 schedUpdate 记录进程最近一次调度时的时间戳

check 时

如果进程状态改变，则将 count 置为 0，否则将 count 值 + T1

如果当前状态为 D 或 Z，且 count 值 >= D 或 Z 的 timeout 阈值时，则认为可能发生了 live-lock，执行 kill 进程的动作，将该进程标记为 killed。

下一次 check 时，如果发现 killed 进程仍然存在（即没有 kill 掉），则判定的确发生了内核 live-lock，触发 kernel panic。

在 debug 版本上增加了 persistent stack signature 检测机制，检测标准是进程的内核态调用栈长时间没有发生变化。

首先，persistent stack signature 检测机制不考虑 Z 状态的进程。

其次，persistent stack signature 只匹配特定的栈帧符号，这些符号存放在变量 llkCheckStackSymbols 中，用 idx 表示符号在 llkCheckStackSymbols 中的存放顺序。

每次 check

用变量 stack 记录进程的内核态调用栈匹配到的特定栈帧符号的 idx（按 idx 顺序匹配到第一个即止）

用变量 count_stack 记录进程在当前调用栈下持续的时间

check 时

如果匹配到的 idx 变化，则将 count_stack 置为 0；否则将 count_stack 值 + T1

如果 count_stack 值 >= timeout 阈值，则认为可能发生了 live-lock，执行 kill 进程的动作，将该进程标记为 killed。

如果下一次 check 时，发现 killed 进程仍然存在（即没有 kill 掉），则判定的确发生了内核 live-lock，触发 kernel panic。

2.3 为什么 persistent stack signature 检测机制不执行 ABA 检查？

llkd 在以周期 T1 进行 persistent stack signature 检查时，有可能两次 check 时内核调用栈相同，但是在周期 T1 内调用栈实际上发生了变化，这就产生了 ABA 问题。

但是 llkd 没有进行 ABA 检查，这是因为 llkd 的 persistent stack signature 检查机制允许进程前向调度。即，persistent stack signature 检查并不会使目标进程停止运行，在 persistent stack signature 检查包括 T1 周期内目标进程照常运行，所以没办法做 ABA 检查。

即，非不为也，实不能也~

ABA 问题以及 ABA 检测

ABA 问题发生在一个线程或进程在检查共享资源的状态时，该状态在检查过程中被其他线程或进程更改并恢复到原始状态。具体来说：

线程 A 读取一个共享变量，发现其值为 A

线程 A 在进行一些处理时，线程 B 修改了该共享变量的值，从 A 到 B，再从 B 回到 A

线程 A 再次检查共享变量的值，发现它仍然是 A，于是认为该值从未被修改过，继续执行

这种情况下，线程 A 会误认为共享变量的状态没有发生变化，可能会导致程序错误。为了防止这种情况，需要进行 ABA 检测，即在每次修改共享变量时附加一个版本号或其他标识符，以便检测到状态的变化。

前向调度（Forward Scheduling）

前向调度，是指系统允许线程或进程在未来的某个时间点被调度和执行。这意味着系统可以根据某些条件提前安排线程的执行顺序，而不是严格按照先来先服务的原则。

2.4 为什么 kill 进程后，进程还存在就能判定发生了内核 live-lock？

按照活锁的定义，发生活锁的目标进程是持续运行的，应该不会一直处于 D 或 Z 状态，那么就应该有机会执行到 kill -9 信号，从而被 killed 掉。

但是，内核活锁不一样，如果 live-lock 发生在内核态，进程陷入到内核态的循环中，是没有机会返回用户态的。在这种情况下，常规的信号处理机制（如SIGKILL）就无法生效，因为这些信号通常在用户态中处理，而不是内核态。因此，发生内核活锁的进程杀不掉。

3. 代码

3.1 内核 live-lock 检查

检查内核 live-lock 的关键函数是 llkCheck。

// system/core/llkd/libllkd.cpp

milliseconds llkCheck(bool checkRunning) {
// 遍历进程

...
            // 更新目标进程的 count、state 值
            // ABA mitigation watching last time schedule activity happened
            llkCheckSchedUpdate(procp, piddir);

// DEBUG 版本 __PTRACE_ENABLED__ 使能
#ifdef __PTRACE_ENABLED__
            // 执行 persistent stack signature 检查
            auto stuck = llkCheckStack(procp, piddir);
            // 执行 persistent state 检查
            if (llkIsMonitorState(state)) {
                if (procp->count >= llkStateTimeoutMs[(state == 'Z') ? llkStateZ : llkStateD]) {
                    stuck = true;
                } else if (procp->count != 0ms) {
                    LOG(VERBOSE) << state << ' ' << llkFormat(procp->count) << ' ' << ppid << "->"
                                 << pid << "->" << tid << ' ' << process_comm;
                }
            }
            if (!stuck) continue;
#else
            // 执行 persistent state 检查
            if (procp->count >= llkStateTimeoutMs[(state == 'Z') ? llkStateZ : llkStateD]) {
                if (procp->count != 0ms) {
                    LOG(VERBOSE) << state << ' ' << llkFormat(procp->count) << ' ' << ppid << "->"
                                 << pid << "->" << tid << ' ' << process_comm;
                }
                continue;
            }
#endif
...
            // 代码执行到这里，说明目标进程可能发生了内核 live-lock。
            // 目标进程还没尝试 kill，则执行 kill。
            // 对于 Z 状态的进程，需要 kill 它的父进程。
            if (procp->killed == false) {
                procp->killed = true;
                // confirm: re-read uid before committing to a panic.
                procp->uid = -1;
                switch (state) {
                    case 'Z':  // kill ppid to free up a Zombie
                        // Killing init will kernel panic without diagnostics
                        // so skip right to controlled kernel panic with
                        // diagnostics.
                        if (ppid == initPid) {
                            break;
                        }
                        LOG(WARNING) << "Z " << llkFormat(procp->count) << ' ' << ppid << "->"
                                     << pid << "->" << tid << ' ' << process_comm << " [kill]";
                        if ((llkKillOneProcess(pprocp, procp) >= 0) ||
                            (llkKillOneProcess(ppid, procp) >= 0)) {
                            continue;
                        }
                        break;

                    case 'D':  // kill tid to free up an uninterruptible D
                        // If ABA is doing its job, we would not need or
                        // want the following.  Test kill is a Hail Mary
                        // to make absolutely sure there is no forward
                        // scheduling progress.  The cost when ABA is
                        // not working is we kill a process that likes to
                        // stay in 'D' state, instead of panicing the
                        // kernel (worse).
                    default:
                        LOG(WARNING) << state << ' ' << llkFormat(procp->count) << ' ' << pid
                                     << "->" << tid << ' ' << process_comm << " [kill]";
                        if ((llkKillOneProcess(llkTidLookup(pid), procp) >= 0) ||
                            (llkKillOneProcess(pid, state, tid) >= 0) ||
                            (llkKillOneProcess(procp, procp) >= 0) ||
                            (llkKillOneProcess(tid, state, tid) >= 0)) {
                            continue;
                        }
                        break;
                }
            }

            // 代码执行到这里，说明确认了内核活锁，触发 kernel panic
            // We are here because we have confirmed kernel live-lock
            std::vector<std::string> threads;
            auto taskdir = procdir + std::to_string(tid) + "/task/";
            dir taskDirectory(taskdir);
            for (auto tp = taskDirectory.read(); tp != nullptr; tp = taskDirectory.read()) {
                std::string piddir;
                if (getValidTidDir(tp, &piddir))
                    threads.push_back(android::base::Basename(piddir));
            }
            const auto message = state + " "s + llkFormat(procp->count) + " " +
                                 std::to_string(ppid) + "->" + std::to_string(pid) + "->" +
                                 std::to_string(tid) + " " + process_comm + " [panic]\n" +
                                 "  thread group: {" + android::base::Join(threads, ",") +
                                 "}";
            llkPanicKernel(dump, tid,
                           (state == 'Z') ? "zombie" : (state == 'D') ? "driver" : "sleeping",
                           message);
            dump = false;
        }
        LOG(VERBOSE) << "+closedir()";
    }

3.2 更新 state & count

state 的更新比较简单，只需要在 check 时记录下目标进程当前的 state 即可。

而 count 的更新则要考虑目标进程在 check 周期内是否发生了变化，即需要做 ABA 检查。

是否可以考虑用进程在用户态、内核态的运行时间来表示"持续时间"呢，即只有当用户态、内核态运行时间没有增加时我们才增加"持续时间"？

即，通过 /proc/<pid>/stat 节点可以获取目标进程在用户态、内核态的运行时间。

比如下面的示例进程在用户态的运行时长为 86，内核态运行时间为 77~~~ 单位是 jiffies。

一个jiffy表示CPU调度（软件时钟）的周期，是 CONFIG_HZ 的倒数，比如 CONFIG_HZ 为100，则一个jiffy为10s。

yudi:/ # cat /proc/2523/stat
2523 (binder:2523_2) S 1 2523 0 0 -1 1077936384 3575 4242 0 3 86 77 5 9 20 0 7 0 18048945 11271012352 2012 18446744073709551615 405566062592 405566180224 548682767680 0 0 0 0 0 1073775864 0 0 0 17 1 0 0 0 0 0 405566267184 405566267184 405863604224 548682771308 548682771336 548682771336 548682776540 0

首先，用进程的内核态运行时间不变来认定 "持续" 是不行的，因为内核活锁的主要表现就是进程会在内核态持续运行。内核态运行时间增加，不能说明进程没有内核活锁。

用进程的用户态运行时间不变来认定 "持续" 也不行。虽然用户态运行时间增加，可以说明进程在用户态执行了，不是内核活锁；但是用户态运行时间不增加，却不能说明进程发生了内核 live-lock。

llkd 使用了另外一种方式，确保只有在进程状态在周期内没有变化时，才会增加"持续时间"。

通过 /proc/<pid>/sched 的 last_update_time 字段获取进程状态最近一时更新的时间戳；
通过 /proc/<pid>/schedstat 获取进程状态切换次数。

只要两次 check 时进程状态的切换次数或者更新时间不同，就认为状态发生过变化，将 count 置 0！

1|yudi:/ # cat /proc/2523/sched|grep last_update_time
se.avg.last_update_time                      :      179663295832064

yudi:/ # cat /proc/2523/schedstat
230446929 10297343 451

llkCheckSchedUpdate 方法更新 state & count 。

848  // Primary ABA mitigation watching last time schedule activity happened
849  void llkCheckSchedUpdate(proc* procp, const std::string& piddir) {
850      // Audit finds /proc/<tid>/sched is just over 1K, and
851      // is rarely larger than 2K, even less on Android.
852      // For example, the "se.avg.lastUpdateTime" field we are
853      // interested in typically within the primary set in
854      // the first 1K.
855      //
856      // Proc entries can not be read >1K atomically via libbase,
857      // but if there are problems we assume at least a few
858      // samples of reads occur before we take any real action.
859      std::string schedString = ReadFile(piddir + "/sched");
860      if (schedString.empty()) {
861          // /schedstat is not as standardized, but in 3.1+
862          // Android devices, the third field is nr_switches
863          // from /sched:
864          schedString = ReadFile(piddir + "/schedstat");
865          if (schedString.empty()) {
866              return;
867          }
868          auto val = static_cast<unsigned long long>(-1);
869          if (((::sscanf(schedString.c_str(), "%*d %*d %llu", &val)) == 1) &&
870              (val != static_cast<unsigned long long>(-1)) && (val != 0) &&
871              (val != procp->nrSwitches)) {
872              procp->nrSwitches = val;
873              procp->count = 0ms;
874              procp->killed = !llkTestWithKill;
875          }
876          return;
877      }
878  
879      auto val = getSchedValue(schedString, "\nse.avg.lastUpdateTime");
880      if (val == -1) {
881          val = getSchedValue(schedString, "\nse.svg.last_update_time");
882      }
883      if (val != -1) {
884          auto schedUpdate = nanoseconds(val);
885          if (schedUpdate != procp->schedUpdate) {
886              procp->schedUpdate = schedUpdate;
887              procp->count = 0ms;
888              procp->killed = !llkTestWithKill;
889          }
890      }
891  
892      val = getSchedValue(schedString, "\nnr_switches");
893      if (val != -1) {
894          if (static_cast<uint64_t>(val) != procp->nrSwitches) {
895              procp->nrSwitches = val;
896              procp->count = 0ms;
897              procp->killed = !llkTestWithKill;
898          }
899      }
900  }

3.3 persistent stack signature

3.3.1 开关

llkd 代码中通过宏 __PTRACE_ENABLED__ 控制 persistent stack signature 是否使能。

debug 版本编译时默认开启宏 __PTRACE_ENABLED__，因此 debug 版本才会使能 persistent stack signature。

// system/core/llkd/Android.bp

cc_library_static {
    name: "libllkd",

    srcs: [
        "libllkd.cpp",
    ],

    shared_libs: [
        "libbase",
        "libcutils",
        "liblog",
    ],

    export_include_dirs: ["include"],

    cflags: ["-Werror"],

    product_variables: {
        debuggable: {
            cppflags: ["-D__PTRACE_ENABLED__"],
        },
    },
}

这里有个疑问，persistent stack signature 功能并不需要 ptrace 目标进程，为什么功能开关要用 __PTRACE_ENABLED__ 这样一个看似与 ptrace 有关的宏控制？

persistent stack signature 功能需要读 /proc/<pid>/stack 节点，该节点返回进程（线程）的内核态调用栈。读 /proc/<pid>/stack 节点时，内核方法会检查 caller 是否有 ptrace 目标进程的权限，然后通过 unwind 获取调用栈。也就是说，如果要使能 persistent stack signature，llkd 需要设置 ptrace 权限（SYS_PTRACE capabilitiy）。

yudi:/ # cat /proc/7187/stack
[<0>] __switch_to+0x244/0x4e4
[<0>] binder_wait_for_work+0x1ac/0x77c
[<0>] binder_thread_read+0x3c8/0x35b0
[<0>] binder_ioctl_write_read+0x120/0x854
[<0>] binder_ioctl+0x294/0x1dc4
[<0>] __arm64_sys_ioctl+0x174/0x1f8
[<0>] el0_svc_common+0xd4/0x270
[<0>] el0_svc+0x28/0x88
[<0>] el0_sync_handler+0x8c/0xf0
[<0>] el0_sync+0x1b4/0x1c0

但是，SYS_PTRACE capabilitiy 权限只有在 debug 版本上才能获取到（sepolicy 限制）。

llkd 在 debug 版本上使用的 rc 配置文件是 llkd-debuggable.rc，在 llkd-debuggable.rc 文件中给 lldk 服务设置了 SYS_PTRACE capabilitiy 权限。

//system/core/llkd/llkd-debuggable.rc

service llkd-1 /system/bin/llkd
    class late_start
    disabled
    user llkd
    group llkd readproc
    capabilities KILL IPC_LOCK SYS_PTRACE DAC_OVERRIDE SYS_ADMIN
    file /dev/kmsg w
    file /proc/sysrq-trigger w
    task_profiles ServiceCapacityLow

3.3.2 检测

检测时，首先过滤掉 Z 状态的进程。

忽略掉 llkIgnorelistStack 中定义的进程。

然后检查目标进程的内核态调用栈是否包含 llkCheckStackSymbols 中定义的符号。

// system/core/llkd/libllkd.cpp

#ifdef __PTRACE_ENABLED__
bool llkCheckStack(proc* procp, const std::string& piddir) {
    if (llkCheckStackSymbols.empty()) return false;
    if (procp->state == 'Z') {  // No brains for Zombies
        procp->stack = -1;
        procp->count_stack = 0ms;
        return false;
    }

    // Don't check process that are known to block ptrace, save sepolicy noise.
    // 忽略掉 llkIgnorelistStack 中定义的进程
    if (llkSkipProc(procp, llkIgnorelistStack)) return false;
    auto kernel_stack = ReadFile(piddir + "/stack");
    if (kernel_stack.empty()) {
        LOG(VERBOSE) << piddir << "/stack empty comm=" << procp->getComm()
                     << " cmdline=" << procp->getCmdline();
        return false;
    }
    // A scheduling incident that should not reset count_stack
    if (kernel_stack.find(" cpu_worker_pools+0x") != std::string::npos) return false;
    char idx = -1;
    char match = -1;
    std::string matched_stack_symbol = "<unknown>";
    // 检查目标进程的内核态调用栈是否包含 llkCheckStackSymbols 中定义的符号
    for (const auto& stack : llkCheckStackSymbols) {
        if (++idx < 0) break;
        if ((kernel_stack.find(" "s + stack + "+0x") != std::string::npos) ||
            (kernel_stack.find(" "s + stack + ".cfi+0x") != std::string::npos)) {
            match = idx;
            matched_stack_symbol = stack;
            break;
        }
    }
    if (procp->stack != match) {
        procp->stack = match;
        procp->count_stack = 0ms;
        return false;
    }
    if (match == char(-1)) return false;
    procp->count_stack += llkCycle;
    if (procp->count_stack < llkStateTimeoutMs[llkStateStack]) return false;
    LOG(WARNING) << "Found " << matched_stack_symbol << " in stack for pid " << procp->pid;
    return true;
}
#endif

llkCheckStackSymbols 包含目标 symbols。

#define LLK_CHECK_STACK_DEFAULT         \
    "cma_alloc,__get_user_pages,bit_wait_io,wait_on_page_bit_killable"

llkIgnorelistStack 包含要忽略的进程。原因是这个名单中的进程不能被 ptrace（ptrace 时会 block），所以不能 check 这些进程的 stack，这个名单包含 init、llkd 等进程...

// system/core/llkd/include/llkd.h

#define LLK_IGNORELIST_STACK_DEFAULT    "init,lmkd.llkd,llkd,keystore,keystore2,ueventd,apexd"

4. 使能

本地的 Android 设备没有使能 lldk。

yudi:/ # ps -A|grep llkd
yudi:/ #

llkd 服务默认 disable，通过 prop llk.enable 启动。

在非 debug 版本上，启动 llkd-0 服务，

在 debug 版本上，启动 llkd-1 服务（定义在 llkd-debuggable.rc 中）。

可以通过手动设置 llk.enable 为 1 或 true 来启动服务。

// system/core/llkd/llkd.rc

on property:llk.enable=true
    start llkd-${ro.debuggable:-0}

service llkd-0 /system/bin/llkd
    class late_start
    disabled
    user llkd
    group llkd readproc
    capabilities KILL IPC_LOCK
    file /dev/kmsg w
    file /proc/sysrq-trigger w
    task_profiles ServiceCapacityLow

debug 版本如果设置了 ro.llk.enable 为 1，则开机时会自动设置 llk.enable 为 true 并启动 llkd 服务。

// // system/core/llkd/llkd.rc

# eng default for ro.llk.enable and ro.khungtask.enable
on property:ro.debuggable=*
    setprop llk.enable ${ro.llk.enable:-0}
    setprop khungtask.enable ${ro.khungtask.enable:-0}

on property:ro.llk.enable=true
    setprop llk.enable true

on property:llk.enable=1
    setprop llk.enable true

on property:llk.enable=0
    setprop llk.enable false