hdiffpatch
[TOC] hdiffi.cpphdiffi & hdiffi_in_mem 内存模式下的补丁生成这是 HDiffPatch 工具集中负责制作补丁的核心业务逻辑。hdiffi 是一个上层封装，而 hdiffi_in_mem 实现了将整个文件加载到内存中进行差分的核心流程。 原理与设计思路解析这部分代码的 overarching goal 是协调整个补丁制作过程，它是一个高层次的控制器，调用底层的差分算法和压缩库来完成任务。 核心策略：内存模式 (In-Memory) 函数名 hdiffi_in_mem 明确指出了其核心设计：将旧文件和新文件完全读入内存中，然后再进行比较和差分。 优点： 差分算法（特别是基于后缀数组的算法）需要对数据进行大量的、非线性的随机访问。在内存中操作可以极大地提升算法的执行速度，避免了缓慢的磁盘I/O。 缺点： 这种模式的内存消耗巨大，它要求系统的可用RAM必须能同时容纳整个旧文件和新文件。因此，它不适用于超出内存容量的超大文件。 模块化与可配置性 代码通过 TDiffiSets 结构体和 compressPlugin 接口...
hpatch_lite
[TOC] 学习笔记HPatchLite\HDiffPatch\libHDiffPatch\HPatchLite\hpatch_lite.cHptach 算法1. Hptach 的核心：加法差分 (Additive Diff)这种方法可以被称为加法差分或增量差分。 核心公式： NewData = OldData + DiffData 反向公式： DiffData = NewData - OldData (在生成补丁时计算) 工作流程图： 1234567891011121314151617181920212223242526272829303132 +----------------------+生成补丁时 (hpatch_diff) | | | 新文件 (New File) | +----------------------+ | (减法) ...
SuffixString
[TOC] HDiffPatch\libHDiffPatch\HDiff\private_diff\suffix_string.cpp后缀数组后缀 (Suffix)：一个字符串的后缀是指从字符串的某个位置开始到字符串末尾的所有字符组成的子串。例如，对于字符串 banana，它的所有后缀是： banana (从位置0开始) anana (从位置1开始) nana (从位置2开始) ana (从位置3开始) na (从位置4开始) a (从位置5开始) 后缀数组 (Suffix Array)：后缀数组不是存储这些后缀字符串本身，而是存储这些后缀的起始位置索引。最关键的一步是，这些索引是按照它们所代表的后缀字符串的**字典序（字母顺序）**进行排序的。 我们来为 banana 构建一个后缀数组： 列出所有后缀及其起始位置： 起始位置 后缀 0 banana 1 anana 2 nana 3 ana 4 na 5 a 按字典序对后缀进行排序： a ana anana banana na nana 构建后...
DivSufSort
[TOC] DivSufSort中的后缀类型：A, B, 和 B* 详解 简单来说，这是一种对所有后缀进行分类的巧妙方法，其最终目的是找出并只排序一个规模小得多的“代表性”后缀子集，然后再利用这个排好序的子集，通过廉价的线性扫描来“诱导”出所有其他后缀的正确顺序。 1. Type A 和 Type B 后缀 (基础分类)算法首先将所有后缀（除了最后一个）分为两大类：Type A 和 Type B。分类的依据是该后缀与它紧邻的下一个后缀的字典序大小关系。 我们用 S[i...] 代表从位置 i 开始的后缀。 Type B 后缀 (B for “Bigger-comes-after”): 如果后缀 S[i...] 小于 后缀 S[i+1...]，那么后缀 i 就是 Type B。 判断捷径: 如果 T[i] < T[i+1]，那么后缀 i 一定是 Type B。 如果 T[i] == T[i+1]，那么后缀 i 的类型与后缀 i+1 的类型相同。 Type A 后缀 (A for “Smaller-comes-after”): 如果后缀 S[i...] 大...
trsort
[TOC] trsort Tandem Repeat Sort (串联重复排序)trsort 是 divsufsort 中一个专门用于对整数数组进行排序的、高度优化的算法。在 sort_typeBstar 的流程中，当计算出所有 B* 后缀的排名 (rank) 并将它们存入 ISA 数组后，trsort 就被调用来对这个排名数组进行最终的排序。 原理与设计思路解析trsort 的名称意为“串联重复排序”，这暗示了它特别擅长处理包含大量连续重复数值（即串联重复）的整数数组。这正是 B* 后缀排名数组的典型特征：许多不同的 B* 后缀在经过一定深度的比较后，会被赋予相同的排名。 trsort 本身是一个多关键字内省排序 (Multikey Introsort) 的变体，但它的实现方式与 sssort 完全不同，它采用了一种迭代式的、处理“未排序组”的策略。 核心策略：迭代式细化与预算控制算法通过一个主 for 循环，不断地对 ISA 数组进行多轮 (pass) 排序。每一轮都尝试解决上一轮留下的、还未完全排序的“相等组”。 分组识别: do { ... } while(f...
sssort
[toc] sssort 递归核心：优化的子串排序算法这是 divsufsort 算法的递归心脏，也是执行实际比较和排序工作的函数。当 sort_typeBstar 将 B* 后缀按照前两个字符分入不同的“桶”后，sssort (Substring Sort) 就被调用来对每一个桶内部的后缀进行完全、正确的排序。 原理与设计思路解析sssort 不是一个简单的排序函数，它是一个混合排序 (Hybrid Sort) 算法，结合了多种排序策略的优点，以在不同规模的数据上都达到最佳性能。它主要围绕一种优化的归并排序变体来实现。 核心策略：非递归的分块归并排序 (Non-Recursive Block Merge Sort)标准的归并排序是递归的，这会带来函数调用的开销。sssort 采用了一种迭代式、自底向上的实现方式，避免了深层递归。 分块 (Blocking): 算法首先将需要排序的区间 [first, last) 分成大小为 SS_BLOCKSIZE 的小数据块。SS_BLOCKSIZE 是一个编译时常量，通常是一个经过优化的值（比如1024）。 对每一个小数据块内部...
mmzone
[TOC] lruvec 结构体 页面回收的核心数据结构lruvec 是 Linux 内核中用于管理 LRU（Least Recently Used，最近最少使用）页面列表的一个核心数据结构。它是内存管理子系统的一部分，定义于 mm/vmscan.c 相关头文件中，主要作用是在页面回收（Page Reclamation）过程中，对不同类型、不同状态的内存页面进行分组和跟踪，是内核决定回收哪些页面的关键依据。 历史与背景这项技术是为了解决什么特定问题而诞生的？lruvec 的诞生是为了解决在现代计算机体系结构下，如何高效、精确、可扩展地管理内存页面以供回收的问题。 区分页面类型：不同类型的内存页面回收成本和策略完全不同。例如，文件页（File-backed pages）如果内容未被修改（是干净的），可以直接丢弃，需要时再从磁盘读回；而匿名页（Anonymous pages，如进程堆栈、malloc分配的内存）则必须先交换到交换空间（Swap Area）才能释放，成本更高。lruvec 需要将它们分开管理。 近似LRU算法：真正的LRU算法要求跟踪每个页面的访问时间，这在拥有数十G...
Makefile
[TOC] 执行 输入make命令，执行Makefile文件中的第一个目标。如果没有指定目标，则执行Makefile文件中的第一个目标。 在 Makefile 中，如果你运行 make 而不带任何参数，make 将默认执行第一个目标。如果第一个目标是 __build，那么运行 make 将等同于执行 make __build.在 Makefile 中，第一个出现的目标通常被视为默认目标。如果你运行 make 而不带任何参数，make 将执行这个默认目标。 $(KCONFIG_CONFIG) include/config/auto.conf.cmd: ;这条语句定义了一个目标，它包含两个文件：$(KCONFIG_CONFIG) 和 auto.conf.cmd。当这两个文件被调用时，执行一个空命令;这意味着这两个文件是一起作为一个目标的，只有在这两个文件都存在时，才会执行空命令 语法ifeq && ifneq 条件语句 ifeq 比较两个条件（条件1 和 条件2）。 如果两个条件相等，则执行 ifeq 块中的代码。 如果两个条件不相等，并且存在 else 块，则...
GCC
[TOC] 属性__cleanup__attribute_malloc__ 用于标记函数返回一个新分配的内存块 这有助于编译器进行优化，例如避免不必要的内存检查。 __attribute_alloc_size__ 用于指定分配的内存大小 attribute_alloc_size__ ((1)) 是另一个 GCC 特定的扩展，用于指定分配的内存大小。参数 (1) 表示第一个参数 __size 是分配的内存大小。这有助于编译器进行优化和静态分析 attribute((const)) 标记为纯函数(pure function)纯函数具有以下特性： 无副作用：纯函数不依赖于任何可变的全局状态，也不会修改任何全局状态。这意味着函数的输出仅依赖于其输入参数，不会对程序的其他部分产生影响。 可优化：由于纯函数的输出仅依赖于输入参数，编译器可以进行更激进的优化。例如，编译器可以将纯函数的多次调用合并为一次调用，或者在调用纯函数时进行常量传播和代码移动等优化。 attribute((externally_visible)) 使其在编译器优化过程中保持对外部模块的可见性 用于标记函数或变量，...
init
[TOC] init/init_task.c 内核线程的一个核心特征是：它们没有自己独立的用户地址空间。它们只在内核空间运行，而内核地址空间是所有进程共享的。因此，内核线程不需要一个属于自己的内存描述符 struct mm_struct，所以它们的 task->mm 指针通常是 NULL init_task 就是大名鼎鼎的 PID 0 进程，也常被称为 swapper 进程。从它的标志位 .flags = PF_KTHREAD 可以看出，它是一个内核线程。 init_task 的调度策略(policy)是 SCHED_NORMAL，这意味着它是一个普通的分时调度任务，而不是实时任务。但是初始化阶段调用了init_idle()，使得它的sched_class 是 SCHED_IDLE，这样它就可以作为 CPU 的空闲任务运行。但是fork出来的其他进程继承的还是 SCHED_NORMAL 策略。 进程的“始祖”：init_task 是系统中所有进程的祖先。在系统启动后，它会创建第一个内核线程 kernel_init（它最终会成为 PID 1 的...
