hdiffpatch
[TOC] hdiffi.cpphdiffi & hdiffi_in_mem 内存模式下的补丁生成这是 HDiffPatch 工具集中负责制作补丁的核心业务逻辑。hdiffi 是一个上层封装，而 hdiffi_in_mem 实现了将整个文件加载到内存中进行差分的核心流程。 原理与设计思路解析这部分代码的 overarching goal 是协调整个补丁制作过程，它是一个高层次的控制器，调用底层的差分算法和压缩库来完成任务。 核心策略：内存模式 (In-Memory) 函数名 hdiffi_in_mem 明确指出了其核心设计：将旧文件和新文件完全读入内存中，然后再进行比较和差分。 优点： 差分算法（特别是基于后缀数组的算法）需要对数据进行大量的、非线性的随机访问。在内存中操作可以极大地提升算法的执行速度，避免了缓慢的磁盘I/O。 缺点： 这种模式的内存消耗巨大，它要求系统的可用RAM必须能同时容纳整个旧文件和新文件。因此，它不适用于超出内存容量的超大文件。 模块化与可配置性 代码通过 TDiffiSets 结构体和 compressPlugin 接口...
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...
GCC
[TOC] 属性__cleanup__attribute_malloc__ 用于标记函数返回一个新分配的内存块 这有助于编译器进行优化，例如避免不必要的内存检查。 __attribute_alloc_size__ 用于指定分配的内存大小 attribute_alloc_size__ ((1)) 是另一个 GCC 特定的扩展，用于指定分配的内存大小。参数 (1) 表示第一个参数 __size 是分配的内存大小。这有助于编译器进行优化和静态分析 attribute((const)) 标记为纯函数(pure function)纯函数具有以下特性： 无副作用：纯函数不依赖于任何可变的全局状态，也不会修改任何全局状态。这意味着函数的输出仅依赖于其输入参数，不会对程序的其他部分产生影响。 可优化：由于纯函数的输出仅依赖于输入参数，编译器可以进行更激进的优化。例如，编译器可以将纯函数的多次调用合并为一次调用，或者在调用纯函数时进行常量传播和代码移动等优化。 attribute((externally_visible)) 使其在编译器优化过程中保持对外部模块的可见性 用于标记函数或变量，...
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 块，则...
linux_makefile
[TOC] 阅读技巧 使用make V=1来查看详细的编译过程 使用make -p来查看所有的变量和规则 顶层makefile判断GUN make 版本 检查当前的 Make 版本以确保满足条件 如果 output-sync 不在其中，这意味着当前使用的 GNU Make 版本低于 4.0，因此代码会触发一个错误，提示用户需要 GNU Make 4.0 或更高版本，并显示当前的 Make 版本 $(MAKE_VERSION)。 123ifeq ($(filter output-sync,$(.FEATURES)),)$(error GNU Make >= 4.0 is required. Your Make version is $(MAKE_VERSION))endif 检测内部变量是否被覆盖 检查 $(MAKECMDGOALS) 变量中是否包含以 __ 开头的目标。$(MAKECMDGOALS) 是一个特殊变量，包含了命令行中指定的所有目标。如果发现有以 __ 开头的目标，代码会触发一个错误，提示这些目标仅供内部使用。这种检查有助于防止用户意外调用内部目标，确保构...
shell命令
[TOC] 语法if 条件语句 if：用于执行一个命令并根据其退出状态码执行不同的操作。 $(if $(KBUILD_OUTPUT),, ...)： 这是一个条件判断语句。(if ...) 函数的语法是 $(if condition, then-part, else-part)如果 condition 为真，则执行 then-part；否则，执行 else-part。 环境变量 shift 命令用于移动参数 shift 命令用于移动参数。它会将所有参数左移一个位置，即 $2 的值赋给 $1，$3 的值赋给 $2，以此类推。$1 的值会被丢弃，而 $0（脚本名称）不会受到影响。 local 命令用于声明局部变量${parameter+word} 用于检查变量是否已经定义 一种参数替换语法，用于检查变量是否已设置并根据结果返回不同的值。以下是对这种语法的详细解释： 1${parameter+word} 如果 parameter 已设置且不为空，则结果为 word。 如果 parameter 未设置或为空，则结果为空字符串。 标志$BASH 指向的 she...
构建说明
[TOC] art-pi 构建命令12345678910111213141516171819202122232425262728293031export CROSS_COMPILE=arm-none-eabi- ARCH=armmake stm32_defconfigmake menuconfig > General setup [*] Initial RAM filesystem and RAM disk (initramfs/initrd) support > Device Drivers > Block devices [*] RAM block device support (1) Default number of RAM disks (2048) Default RAM disk size (kbytes) > System Type (0xC0000000) (S)DRAM Base Address (0x02000000) (...