咸的鱼 - Read_Code
type: channel
link: https://saltedfish.fun/index.php/tag/Read_Code/
items: Adb Logcat with Process Name
items: MNN相关代码阅读笔记
items: LLaMA.CPP代码走读
items: 我说火箭(MLSys)就得用水洗煤(NPU)
items: 为侧载Chrome插件生成持久ID
items: 自建TailScale Derper的一点人生的经验

Adb Logcat with Process Name
type: item
date: 2023-09-26T11:32:00+00:00
description: Adb日志想查看Android端侧的日志信息输出,一般采用命令行 adb logcat或Android Stadio中Logcat插件的方式.最近要实现一个Android App的自动测试,所以需要使用真机连接到服务器上运行,因此更多使用命令行输出Logcat的形式.但是Adb Logcat的输出中只包含pid\tid等信息,不包含包名等属性,导致无法过滤来自指定包名所有Activity的log.在Github上翻了下,好像也没有支持Package Name过滤的Logcat客户端.因此决定自己改一个出来.如何获取Package Name?这个问题的解答可能还要从AS的Logcat Plugin的源码入手.这部分功能在Plugin中被称为 ProcessMonitor.具体的代码仓库位于这里.这个功能由两部分组成,运行在端侧的Agent(C++编写),运行在Server端的AgentTracker(来采集并缓存ProcessName与Pid的映射)以及管理Agent运行.端侧的Agent代码十分简单,只是一个loop来从procfs中获取进程信息,并从cmdline文件中截断出文件名.在loop中不断轮询/proc下所有pid,并与缓存的pid set进行比较,来输出pid新增或减少情况.Server端的Tracker根据Agent的输出来更新pid与ProcessName(在Zygote启动的Java App子进程中,这应当是包名). /** * Reads processes from "/proc" and retrieves their name from * "/proc/<pid>/cmdline" and prints: When a process is added: "+ <pid> * <process-name>" When a process is removed: "- <pid>" New processes are * added to the processes set and processes that not longer exists are removed * from it. */ void scanProcesses() { // Whatever is left in this set needs to be removed from ::processes set<int> markedForRemoval(processes); DIR* pDir = opendir("/proc"); while (true) { dirent* pDirent = readdir(pDir); if (pDirent == nullptr) { break; } int pid = parseInt(pDirent->d_name, -1); // Ignore entries that are not a valid pid if (pid < 0) { continue; } markedForRemoval.erase(pid); if (processes.find(pid) != processes.end()) { continue; } // New process found string path = string("/proc/") + pDirent->d_name; const string& name = readCommand(path); if (name.empty() || startsWith(name, "zygote") || name == "<pre-initialized>") { // Ignore processes without a name or that haven't initialized yet continue; } processes.insert(pid); printf("+ %d %s\n", pid, name.c_str()); } closedir(pDir); for (const int pid : markedForRemoval) { processes.erase(pid); printf("- %d\n", pid); } ::fflush(stdout); }这样实现确实比较简单,但是感觉并不算优雅.AS作为第一方的App可以采用这种设计,但是如果要设计一个第三方实现,在端侧启动一个Forever Loop应用程序似乎并不太合适.翻了下老版本的实现,发现有注释提到可以用 ps aux 来提取ProcessName.(这样的另一个好处是避免了权限问题,而且某些命令行服务在cmdline文件中可能是…

MNN相关代码阅读笔记
type: item
date: 2023-09-04T09:42:00+00:00
description: 内存分配MNN中有三种内存分配器：DefaultAllocator,BufferAllocator RecurseAllocator.Recurse分配器,实际上只是BufferAlloator的简单封装,因此这里我们只讨论前两种.DefaultAllocatorclass DefaultAllocator : public BufferAllocator::Allocator { public: DefaultAllocator() { // Do nothing } virtual ~ DefaultAllocator() { // Do nothing } virtual std::pair<void*, size_t> onAlloc(size_t size, size_t align) { return std::make_pair(MNNMemoryAllocAlign(size, MNN_MEMORY_ALIGN_DEFAULT), 0); } virtual void onRelease(std::pair<void*, size_t> ptr) { MNN_ASSERT(ptr.second == 0); MNNMemoryFreeAlign(ptr.first); } };DefaultAllocator提供了底层的malloc 实现,并提供了基本的内存对齐功能.onAlloc生成一个Pair\<内存指针,0>MNNMemoryAllocAlign的实现如下:static inline void **alignPointer(void **ptr, size_t alignment) { return (void **)((intptr_t)((unsigned char *)ptr + alignment - 1) & -alignment); } extern "C" void *MNNMemoryAllocAlign(size_t size, size_t alignment) { MNN_ASSERT(size > 0); #ifdef MNN_DEBUG_MEMORY return malloc(size); #else void **origin = (void **)malloc(size + sizeof(void *) + alignment); MNN_ASSERT(origin != NULL); if (!origin) { return NULL; } void **aligned = alignPointer(origin + 1, alignment); aligned[-1] = origin; return aligned; #endif }首先,(void **)malloc(size + sizeof(void *) + alignment) 用于分配原始内存,sizeof(void*)是用于存储origin地址,即 aligned[-1] = origin, 多申请alignment是保证对齐之后仍然最少有size内存,强转成(void* )是为了传给alignPointer时直接+1跳过开始的部分保留给以后.alignPointer的实现是为了将地址对齐(这块上古魔术转换我也不太理解,看上去是NCNN的时代就在用了)BufferAllocatorBufferAllocator的用途在于池化内存,每块内存优先从池中分配,释放内存时回归内存池.核心逻辑如下:std::pair<void*, size_t> BufferAllocator::alloc(size_t size, bool separate, size_t align) { #ifdef DUMP_USAGE auto memoryUsed = size / 1024.0f / 1024.0f; MNN_PRINT("Alloc: %f\n", memoryUsed); #endif if (0 == align) { align = mAlign; } std::pair<void*, size_t> pointer; // reuse if possible if (!separate) { if (nullptr != mCurrentFreeList) { pointer = getFromFreeList(mCurrentFreeList, size, false, align); } if (nullptr != pointer.first) { return pointer; } pointer = getFromFreeList(&mFreeList, size, true, align);…

LLaMA.CPP代码走读
type: item
date: 2023-09-02T17:14:00+00:00
description: Version: Commit 5488fb78Feature: x86_64 CPU Only, mmap,no blas. 略过了所有有关KV缓存的部分.以下文字可能因代码更新或本人认知水平而不再适用.LLaMA.cpp or GGMLGGML是LLaMa.cpp同一作者的作品,作者将LLaMa和Whisper等cpp实现库中用到的运算相关函数提取到了一个库中,命名为GGML(A Tensor Lib for ML), 因此GGML并不是类似MNN等的推理框架,而仅仅是一个操作算子的加速计算库而已,有关模型序列化\子图划分等上层功能仍要由调用方实现,因此这里还是选择阅读LLaMa.cpp的代码,来梳理一个简单的推理库要做什么工作.Weights File StructrueLLama.cpp(下文简称Lc)没有像其他ML框架一样借助Proto或者FlatBuf这种序列化框架来实现权重的序列化，而是简单采用二进制顺序读写来自定义序列化，比起框架方案缺少了向前兼容和透明迁移等特性，但是毫无疑问简单了很多。下面介绍文件结构:第一个 u32 是Magic Number，用于识别文件格式与版本类型(LLAMA_FILE_VERSION_GGMF_V1 ,LLAMA_FILE_VERSION_GGJT_V1 etc.) ，具体可参考下面的enum.enum llama_file_version { LLAMA_FILE_VERSION_GGML, LLAMA_FILE_VERSION_GGMF_V1, // added version field and scores in vocab LLAMA_FILE_VERSION_GGJT_V1, // added padding LLAMA_FILE_VERSION_GGJT_V2, // changed quantization format LLAMA_FILE_VERSION_GGJT_V3, // changed Q4 and Q8 quantization format };接下来的7个u32是模型的参数，如layer数目,head数目等，是与模型类型紧密结合的，此外还有一个n_vocab 参数，用于决定接下来的vocab存储的数目。再接下来LLama.cpp会从文件中读取vocab，每个vocab由字符串长度len(u32) vocab字符串word(string 长度为len) score (float) 组成,并被按顺序从文件中依次读出.vocab表读取完之后,文件剩下的部分就是Tensor Map了,Lc使用一个while循环一直读到文件末尾来读取出所有的Tensor信息(包括名称和权重).每个Tensor的存储格式为维度数目n_nums(u32) 名称长度 name_len(u32) Tensor type(u32) Tensor 维度数组(长为n_nums的u32数组,记录了每一维的大小 Tensor名称(长为name_len的字符串 ,读出以上metadata之后,如果文件存储格式版本大于LLAMA_FILE_VERSION_GGJT_V1,则metadata之后会有一段padding来对齐到32字节.从下一个32字节开始存储Tensor的weights数据 ,但是在最开始的load过程中不做读取,仅仅计算出应当读取的字节数并记录在llama_load_tensor 结构体中,后期再使用mmap或其他方式读入内存.读取metadata完毕后,会将llama_load_tensor放入一个列表中,并生成一个name_to_tensor_idx的索引便于查找.至此 模型文件的加载就完成了.struct llama_load_tensor { std::string name; enum ggml_type type = GGML_TYPE_F32; std::vector<uint32_t> ne; //维度数据 size_t file_off; //计算在文件中的偏移量 size_t size; //计算字节数 struct ggml_tensor * ggml_tensor = NULL; //指向真正的 可执行计算的 Tensor对象 uint8_t * data; };Lc计算weights的字节数:对于Float32和FP16型的Tensor而言,使用一个相应的Float类型来存储即可,Lc计算出的字节数即为sizeof(float)但是对于量化类型,每个FP32元素会用较低精度的类型来表示(如4bit int),为了弥补精度下降带来的计算误差,必须额外携带纠正数据,因此可能使用一个结构体来存储一组数据.一个典型结构如下: 以Q4_0量化为例,量化后的数据每3…

我说火箭(MLSys)就得用水洗煤(NPU)
type: item
date: 2023-06-22T09:39:00+00:00
description: Intro最近遇到了一个问题:一个基于Distilbert模型Fine-Tune过的模型在NPU上表现很差，推理平均时间远高于GPU，甚至于CPU拉不开差距。测试设备是Google Pixel 7Pro，搭载了Google自研TPU。网络上关于移动边缘侧推理性能的Issue很多，但是牵扯到NPU异构加速的Issue基本上很难有个清晰的解决方案，常见的情形是放弃NPU方案或者更换模型碰碰运气(淦我怎么老是在搞这些没有人搞的破活)。很遗憾在这里两个摆烂方案都不可行，好在一番东翻西找之后解决了问题，将解决方案记录在这里，也给可能有类似问题的后来者一个参考。NNAPI众所周知，随着设备端侧算力的不断加强和诸如隐私计算等政治正确要求的出现，越来越多的MLSys开始注重将Inference(甚至Training)迁移到设备侧。除传统的CPU推理外，越来越多的异构加速模块也开始加入战场，如GPU、DSP甚至厂商定制化的专用加速单元(他们有个好听的名字叫做神经网络运算单元NPU)。高度定制化的加速单元在针对性的模型和算子上可以达到非常高的性能，但想要让加速单元能较好的推理特定的DL模型需要额外的适配和测试工作（如高通NPU(在865之前叫做DSP)只能接受Int8的模型Tensor推理,而华为Kirin的NPU在Float32 Tensor上的性能最好,Google Tensor自研TPU的具体信息更是完全黑盒)。好消息是，面对如此百花齐放又千奇百怪的异构加速单元，Android系统引入了一层虚拟层来封装这些差异，称为(Neural Network API,NNAPI)；坏消息是，NNAPI的版本必须随Android大版本一并更新(因此碎片化现状也不可避免)，而且NNAPI本意是作为DL Framework（如TFLite MNN）等的一个计算后端来设计，因此API十分low-level，文档也过于简洁(见此),给开发者调试的过程带来了很多困难。一个简单的模型推理的调用流程图如图所示，App通过加载ML Lib来运行模型，ML Lib（如TFLite)会视模型内算子的类型将模型分为几个子图，分配的原则是一方面每个子图尽可能大（减少图中运算数据在不同计算后端之间拷贝的时间损耗），另一方面尽可能利用更快的加速单元(若有些算子在GPU和CPU上同样有实现，优先GPU上的加速实现，但如果仅在CPU上有实现，就只能Fallback到CPU上进行运算，同时为了保证第一条，还可能将几个不兼容算子（连同中间夹杂的少数兼容算子）一同Fallback到CPU)。而假设某个子图被判定为NNAPI兼容，则会被分派到NNAPI的运行时上执行，NNAPI会再次进行分割，按照上文类似的方式将算子分配到合适的硬件HAL上真正执行。如上段所示，如果我们不考虑硬件算子实现上出现的Bug，那一个模型如果在NPU上运行不佳的原因可能是：由于大部分算子不兼容NPU，因此被调度到CPU上进行运算，此时NPU的加速性能并没有被很好发挥 –> 这种情况下似乎很难有较好的解决办法，幸运的情况下不兼容算子可以使用其他兼容算子进行组合替代(如MatMul其实是由多个FullyConnected进行组合而成)，不幸运的情况下就只能放弃或者对模型进行大修，如本人曾经在早期尝试过在GPU上对RNN进行推理，彼时只能因为硬件不支持作罢。大部分算子兼容NPU，但是由于几个频繁出现的算子不兼容NPU，导致子图被分割得很碎片化，异构后端之间数据拷贝的Tradeoff太高，导致推理时延过高。这是我猜想本例中更可能出现的情形，也是有相对简单的解决方案的情形：视模型来尝试替换算子，将少数算子去掉或更换。NPU配置问题，查阅资料查找如NPU支持的量化类型不符合或模型是否过大等问题，此外还应当注意，Dynamic Shape Input类型的模型（即输入Shape为(None,X,X)的类型）截止目前可能能不支持。日志追踪对于一个黑盒系统，我们首先能做的只能是去查看运行日志。对于TFLite框架，我建议使用自带的Benchmark Tools尝试运行模型测试，首先去除App调用错误的乌龙。传入--use_nnapi=1 --nnapi_allow_fp16=true --nnapi_accelerator_name=google-edgetpu 来允许Benchmark自动量化模型、启用NNAPI并指定NPU运行。在指定NPU后，所有NPU无法执行的算子就不会调度到NNAPI层，而是有TFLite自行分配到CPU上运行，这有利于我们后面进行的Operation Profiling. Benchmark的结果与一开始类似，NPU的推理平均时延在600ms左右，与我预计的数据(<100ms)相去甚远。好在Benchmark…

为侧载Chrome插件生成持久ID
type: item
date: 2023-06-01T09:16:00+00:00
description: 背景出于菜鸡的摸鱼需求，希望用插件的形式为Github增加用户备注标签功能，大概的设计如下：浏览器插件注入ContentScript修改页面内容，增加标签显示和相关操作按钮利用浏览器提供的Sync Storage功能在多设备同步标签数据经过一天的摸鱼，插件功能已经基本完成:But…跨设备同步功能却出现了问题:对于未上架Chrome Store的拓展而言，拓展的ID安装时生成的，且在不同设备上安装时不一定一致。而Chrome提供给拓展 Sync Storage功能是与ID相绑定的，因此无法完成不同设备上的同步功能。Extension Key的生成在谷歌官方的文档里，我找到了Key 这个Manifest键值，但是官方要求必须在Developer Dashboard才能生成这个公钥属性。随后我发现，谷歌浏览器的开发者需要5刀乐注册费…还不支持银联卡。随手填了个Key值，加载报错Invalid.穷鬼如我决定去翻下Chromium的相关代码，看看PublicKey到底是怎么验证的。好在Chromium的代码仓库很条理，还带有搜索功能，很快就找到了相关代码段：//extensions/common/extension.cc // Computes the |extension_id| from the given parameters. On success, returns // true. On failure, populates |error| and returns false. bool ComputeExtensionID(const base::Value::Dict& manifest, const base::FilePath& path, int creation_flags, std::u16string* error, ExtensionId* extension_id) { if (const base::Value* public_key = manifest.Find(keys::kPublicKey)) { std::string public_key_bytes; if (!public_key->is_string() || !Extension::ParsePEMKeyBytes(public_key->GetString(), &public_key_bytes)) { *error = errors::kInvalidKey; return false; } *extension_id = crx_file::id_util::GenerateId(public_key_bytes); return true; } if (creation_flags & Extension::REQUIRE_KEY) { *error = errors::kInvalidKey; return false; } // If there is a path, we generate the ID from it. This is useful for // development mode, because it keeps the ID stable across restarts and // reloading the extension. *extension_id = crx_file::id_util::GenerateIdForPath(path); if (extension_id->empty()) { NOTREACHED() << "Could not create ID from path."; return false; } return true; } bool Extension::ParsePEMKeyBytes(const std::string& input, std::string* output) { DCHECK(output); if (!output) return false; if (input.length() == 0) return false; std::string working = input; if (base::StartsWith(working, kKeyBeginHeaderMarker, base::CompareCase::SENSITIVE)) { working = base::CollapseWhitespaceASCII(working, true); size_t header_pos = working.find(kKeyInfoEndMarker, sizeof(kKeyBeginHeaderMarker) - 1); …

自建TailScale Derper的一点人生的经验
type: item
date: 2022-12-16T04:59:00+00:00
description: 前言TailScale是一个很优秀的组网服务，特别适合拓展家里的局域网，让你在外面也可以访问家中的内网设备。基于WG 的底层设计也使得TailScale有更好的性能和安全性，但是TailScale的工作机制是先使用Relay节点(Derper)建立连接，再尝试进行打洞直连。由于我国特殊国情，一方面IPv4大部分处于NAT之后，导致连接大部分依赖Derper中转，另一方面Derper并没有国内的节点，导致连接的延迟很高。好在TailScale提供了一个Alpha版本的自建Derper指南(链接)，但是要求必须开放443端口，对国内的VPS很不友好。但是经过测试与审阅源码，发现443并非必须，且仍可以利用客户端验证设备。要求如下：需要域名绑定IP需要HTTPS证书（如果自签证书，要保证连接到VPS的节点均信任此证书）开放端口（不必须443）搭建方法安装最新版Go(版本至少要1.16以上才能执行go install +url@version 命令,且Derper的代码只在最新版Golang下测试)直接按照官方版指南安装官方最新版本Derper为自己的域名签发HTTPS证书，需要 hostname.crt 与hostname.key 保存在同一目录使用下面的语句执行启动Derper命令:sudo derper --a :10080 --http-port -1 --certmode manual --certdir ./certDir --hostname HOSTNAME --verify-clients # 假设SSL端口为10080 关闭http-port（-1) 将证书模式设置为手动(非443不可自动获取证书) # 指定证书的目录在certDir下,指定域名为 HOSTNAME，并开启客户端验证最后记得加入本Derper节点到各客户端配置文件，如果使用官方版本，在Admin Console的ACL部分编辑即可，同步到各个节点可能要花费一部分时间。客户端验证在开启Derper的命令中加入 —verify-clients Flag可开启客户端验证功能，开启后只有账号下的设备可以接入本DERP。开启此功能的要求是：必须有域名和证书绑定Derper节点也要运行TailScale并登录账号，接入用户的校验是通过调用本机的TailScale应用暴露的API来完成的。