20KB一级索引的威力ESP32-C3 DNS广告拦截器 blIndex 两级查找结构深度剖析【免费下载链接】esp32-c3-adblockPi-hole-class DNS ad-blocker on a $2 ESP32-C3 (no PSRAM): 537k domains as 40-bit FNV-1a hashes in flash, binary-searched. UDP DNS sinkhole web dashboard. https://youtube.com/shorts/RaxszOUMi8E?featureshare项目地址: https://gitcode.com/GitHub_Trending/es/esp32-c3-adblockesp32-c3-adblock是一个运行在约 2 美元 ESP32-C3 小板上的 DNS 级广告拦截器Pi-hole 风格把 53 万条广告域名以 40 位 FNV-1a 哈希存进 Flash用不到 50 KB 的 RAM 即可在约 10 毫秒内完成一次该不该拦截的判定。本文带你拆透它最核心的工程 trick——blIndex一级索引 Flash 哈希表的两级查找结构只用 20 KB 内存就把在闪存里大海捞针变成了两次小范围快速查找。 先看结论20 KB 内存换来的查找效率指标数值说明一级索引大小4096 条 × 5 字节 20 KB常驻 RAM 的目录拦截列表容量最高约 53.7 万域名仅占约 2.7 MB Flash单次判定内存占用约 50 KB 总 RAM完全不需要 PSRAM平均查找成本约 18 次 Flash 读含 WiFi RTT 约 10 ms对比直接对 2.7 MB 哈希表二分要 19 次随机寻址 一句话概括把 20 KB 的抽样目录常驻内存做第一刀把 2.7 MB 的完整名单留在 Flash 里做第二刀——这就是整个项目的空间换时间的精髓。⚠️ 痛点为什么域名列表塞进 RAM行不通传统 ESP32 DNS sinkhole 的做法是把拦截列表的域名字符串整个加载进 RAM。一条域名平均十几个字节14 万条就需要约 2.5 MB 内存——这逼着你买带 PSRAM 的 ESP32约 8 美元。而 ESP32-C3 没有 PSRAMSRAM 只有几百 KB4 MB Flash 才是它的大件行李额度。esp32-c3-adblock 的思路是反过来不存字符串存哈希每个域名用 64 位 FNV-1a 哈希后截断为 40 位5 字节14 万条仅需 0.67 MB哈希表留在 Flash构建脚本 build_blocklist.py 把所有哈希排序后按小端格式写成blocklist.bin通过 LittleFS 存进 Flash分区表见 partitions.csv查找时按需读取设备端对 Flash 哈希表做二分查找。关键疑问随之而来Flash 不是 RAM每次 seek read 都有延迟直接对 50 万条哈希二分最坏要 19 次 Flash 随机访问。能不能在目录上再省一刀——blIndex登场。 blIndex 是什么Flash 哈希表的抽样书签blIndex的定义在 main.cppstatic const int INDEX_ENTRIES 4096; // 20 KB first-level flash index ... static uint8_t blIndex[INDEX_ENTRIES][HASH_BYTES]; // 每条目 5 字节它是一个 4096 元素的数组每个元素 5 字节40 位哈希总计恰好20 KB。它的构建逻辑见buildFlashIndex()main.cpp启动时或拦截列表热替换后把 Flash 哈希表均匀地切成 4095 段从每段的起点各抽取一个哈希存进blIndex位置 pos(i) i × (numHashes - 1) ÷ (INDEX_ENTRIES - 1)相当于给一本 50 万词条的词典打了 4096 个书签——每个书签指向这一段的第一个词条。书签本身只有 20 KBC3 的 SRAM 完全塞得下。补充构建脚本还会打印理论读取次数build_blocklist.py 的~ceil(log2(n)) reads/query这正是没有索引时纯二分的下界也是 blIndex 想压缩的成本。 两级查找全流程以 isBlocked 为例当一条 UDP DNS 查询到达handleDns 会解析出域名parseQuery随后交给isBlocked。以查询img.ads.example.com为例查询域名 │ ├─① 逐级哈希img.ads.example.com → ads.example.com → example.com │ 父域命中即拦截天然覆盖子域名 │ ├─② 查 256 槽小缓存RAM──── 命中直接返回结果 │ └─③ inFlash() 两级查找 第一刀对 20 KB 的 blIndex 做二分~12 次比较纯 RAM 速度 ├─ 恰好等于目标哈希 → 命中返回拦截 └─ 否则定位到目标落在 blIndex[seg] 与 blIndex[seg1] 之间 第二刀只读这一段≤256 条 ≈ 1.2 KB进 RAM 缓冲区顺序比较 ├─ 相等 → 拦截 └─ 越过目标值 → 放行转交上游 DNS各步对应源码位置如下方便对照阅读步骤作用源码位置逐层父域哈希a.b.com的父域b.com被拉黑则同样拦截main.cpp256 槽直接映射缓存slot h 0xFF重复查询零 Flash 访问main.cpp第一级blIndex 二分纯 RAM 内完成约 12 次比较锁定书签区间main.cpp第二级区间批量读 顺序比较最多MAX_RANGE256条一次read批量进rangeBufmain.cpp⚡ 为什么一级索引选 4096 条20 KB这个甜点inFlash()的实现main.cpp里藏着三个精心设计的取舍越界快速放行先比较blIndex[0]和blIndex[4095]目标哈希若不在整个哈希表范围内一次 Flash 访问都不发生main.cpp。区间长度天然受控50 万哈希 ÷ 4095 段 ≈ 每段 129 条固件用MAX_RANGE 256兜底main.cpp保证第二刀一次最多只搬 1.28 KB 进 RAM——单次查找的 Flash I/O 被封顶了与列表总量脱钩。书签本身就是数据二分过程中若blIndex[mid]恰好等于目标哈希直接判定命中main.cpp20 KB 的索引顺带又白赚了 4096 个查找点。换个角度看这笔账4096 条书签 × 5 字节 20 KB若只打 1024 个书签每段膨胀到约 517 条超过MAX_RANGE后第二刀需要分批读Flash 访问次数回升若打 16384 个书签索引要 80 KB挤压 C3 本就紧张的 SRAM。4096 条是在Flash 读次数与RAM 占用之间解出的最优平衡点这也是标题里20 KB 一级索引的威力的由来。️ 缓存层为什么只缓存 Flash 结果isBlockedHash()前面还挂了一个 256 槽的 RAM 缓存main.cpp按hash 0xFF直接映射到槽位。注释里解释了一个容易踩坑的细节main.cppFlash 拦截列表只在整体重开上传新 blocklist / 远程自动更新时变化重开时索引重建、缓存清空见reopenBlocklist()main.cpp所以放心缓存用户自定义域名Web 面板里随时可加可删走的是inCustom()线性扫描main.cpp刻意不缓存避免面板里删掉域名后设备还在返回过期答案。配合 DNS 层的按客户端统计handleDns 对每个源 IP 分别累计 blocked/allowed设备既能高速应答海量重复查询又不会因缓存产生逻辑错误。 顺带一说40 位哈希为什么够用哈希位宽是这套结构的另一根支柱。按生日悖论估算README 中的说明14.1 万域名 40 位哈希碰撞数约 053.7 万域名约 1——也就是最坏只有一个倒霉域名会被误杀。32 位能省 20% Flash 但 25 万域名时碰撞升至约 764 位则每条多花 3 字节解决一个不存在的问题。5 字节定案构建脚本与固件的HASH_BYTES严格保持一致build_blocklist.py ↔ main.cpp。 动手上手从源码到运行固件主逻辑DNS 应答、两级查找、Web 面板、OTA全部集中在 src/main.cpp其中查找核心是第 79~170 行拦截列表构建工具 tools/build_blocklist.py 支持 hosts 文件、纯域名列表、AdGuard/Adblock 基础规则三种输入支持白名单剔除构建完会打印哈希条数、碰撞数与理论查找读取次数构建流程、分区表取舍双 OTA 槽 vs 单应用分区、约 25 万 vs 53 万域名上限详见 README.md 与 partitions.csv打印外壳注意给 C3 的天线端留空在 hardware/esp32-c3-supermini-enclosure.stl。需要编译烧录时克隆仓库仓库是只读的请遵守git clone https://gitcode.com/GitHub_Trending/es/esp32-c3-adblock✅ 小结小内存芯片上的目录 正文思想blIndex 两级查找本质上是把数据库索引的经典思想搬进了一块 2 KB 不到的单片机里20 KB 抽样索引常驻 RAM把 50 万条 Flash 哈希表切成 4095 个小段第一刀纯内存完成第二刀只读不超过 256 条的片段用一次批量read封顶 Flash 延迟单次查询 ~18 次 Flash 读、约 10 ms 出结果256 槽哈希缓存再吃掉重复查询整套查找逻辑只用了约 50 KB RAM——这就是 $2 的 ESP32-C3 能扛起 Pi-hole 级拦截任务的底气。对任何小内存 大只读数据集的嵌入式场景词表、规则库、白名单这套Flash 存正文、RAM 存目录的 blIndex 模式都值得抄作业。【免费下载链接】esp32-c3-adblockPi-hole-class DNS ad-blocker on a $2 ESP32-C3 (no PSRAM): 537k domains as 40-bit FNV-1a hashes in flash, binary-searched. UDP DNS sinkhole web dashboard. https://youtube.com/shorts/RaxszOUMi8E?featureshare项目地址: https://gitcode.com/GitHub_Trending/es/esp32-c3-adblock创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考