目录
1. llkd 简介
2. 原理
2.1 内核活锁
2.2 检测机制
2.3 为什么 persistent stack signature 检测机制不执行 ABA 检查？
2.4 为什么 kill 进程后，进程还存在就能判定发生了内核 live-lock？
3. 代码
3.1 内核 live-lock 检查
3.2 更新 state & count
3.3 persistent stack signature
3.3.1 开关
3.3.2 检测
4. 使能
1. llkd 简介
linux kernel 的 hungtaskd（由 CONFIG_DETECT_HUNG_TASK 使能）功能可以检测 hung tassk，即长时间处于 D 状态的进程。
lldk 是 hungtaskd 功能的用户空间平替（加强）。
llkd 在 debug、非 debug 版本上有不同的检测机制。
- debug 版本，使用 persistent stack signature 检测机制
目标是发现内核态调用栈长时间没有变化的进程。
- 非 debug 版本，增加 persistent D or Z state 检测机制
目标是发现长时间处于 D 或 Z 状态的进程。
llkd 的 AOSP 代码路径：system/core/llkd
llkd 官方介绍文档：https://source.android.google.cn/docs/core/architecture/kernel/llkd?hl=zh-cn
2. 原理
2.1 内核活锁
根据官方文档的描述，llkd 的作用是发现和减少内核死锁。
而由 llkd 的名字 live-lock daemon 可知，llkd 实际的作用是发现内核活锁。
活锁（live-lock）
活锁是一种情况：线程或进程虽然在不断运行，但实际上并未取得任何进展。
与死锁不同，活锁不会完全停止运行，而是陷入一个无效的循环。
即：死锁时，线程一般会一直处于 sleep 状态；活锁时，线程一般会不断运行。
广义的死锁包含活锁。
内核活锁：是指进程在内核态处于活锁状态。
2.2 检测机制
设置一个检测周期，每个检测周期进行一次内核活锁检测。
在非 debug 版本上使用 persistent D or Z state 检测机制，检测标准是进程长时间处于 D 或 Z 状态且状态没有发生变化。
以 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.cppmilliseconds llkCheck(bool checkRunning) {
// 遍历进程...// 更新目标进程的 count、state 值// ABA mitigation watching last time schedule activity happenedllkCheckSchedUpdate(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-lockstd::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 : 179663295832064yudi:/ # cat /proc/2523/schedstat
230446929 10297343 451llkCheckSchedUpdate 方法更新 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.bpcc_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.rcservice llkd-1 /system/bin/llkdclass late_startdisableduser llkdgroup llkd readproccapabilities KILL IPC_LOCK SYS_PTRACE DAC_OVERRIDE SYS_ADMINfile /dev/kmsg wfile /proc/sysrq-trigger wtask_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 Zombiesprocp->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_stackif (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;
}
#endifllkCheckStackSymbols 包含目标 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.rcon property:llk.enable=truestart llkd-${ro.debuggable:-0}service llkd-0 /system/bin/llkdclass late_startdisableduser llkdgroup llkd readproccapabilities KILL IPC_LOCKfile /dev/kmsg wfile /proc/sysrq-trigger wtask_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=truesetprop llk.enable trueon property:llk.enable=1setprop llk.enable trueon property:llk.enable=0setprop llk.enable false
