欢迎来到我的博客

学习一些东西，记录一些东西。 当做备忘录。

Tips: 左侧边栏有搜索框，可以关键字检索整个博客内容。

目录索引

• 我的博客分类
• iOS基础相关
• 音视频相关
• lua相关
• dyly-简阅
• Breakpad跨平台Crash Report解决方案
• MacOS和iOS操作系统

快速导航/查询

• objc4
• GCD看这一篇就够了
• 音视频微信公众号

半途而废

• Python 未完待续，后期慢慢补上
  • 学习来源github 共勉之！(https://github.com/jackfrued/Python-100-Days)
  • 微软出了一个《Develop With Python on Windows》
    (https://docs.microsoft.com/zh-cn/windows/python/get-started/python-for-education)
• Vue
• Linux相关知识点
• Swift 没有记录
• Flutter 没有记录
• Reactnative 没有记录

我的公众号

参考

• 音视频微信公众号

学习记录

声音

要计算一个 PCM 音频流的码率需要数字音频的三要素信息即可：码率 = 采样率 × 量化位深 × 声道数。
所里这里核心的数据结构是 CMSampleBuffer，关于它有如下几点需要注意：

CMSampleBuffer

CMSampleBuffer 则是一个 Core Foundation 的对象，这意味着它的接口是 C 语言实现，它的内存管理是非 ARC 的，需要手动管理，它与 Foundation 对象之间需要进行桥接转换。
CMSampleBuffer 是系统用来在音视频处理的 pipeline 中使用和传递媒体采样数据的核心数据结构。你可以认为它是 iOS 音视频处理 pipeline 中的流通货币，摄像头采集的视频数据接口、麦克风采集的音频数据接口、编码和解码数据接口、读取和存储视频接口、视频渲染接口等等，都以它作为参数。
CMSampleBuffer 中包含着零个或多个某一类型（audio、video、muxed 等）的采样数据。比如：
要么是一个或多个媒体采样的 CMBlockBuffer[3]。其中可以封装：音频采集后、编码后、解码后的数据（如：PCM 数据、AAC 数据）；视频编码后的数据（如：H.264 数据）。
要么是一个 CVImageBuffer[4]（也作 CVPixelBuffer[5]）。其中包含媒体流中 CMSampleBuffers 的格式描述、每个采样的宽高和时序信息、缓冲级别和采样级别的附属信息。缓冲级别的附属信息是指缓冲区整体的信息，比如播放速度、对后续缓冲数据的操作等。采样级别的附属信息是指单个采样的信息，比如视频帧的时间戳、是否关键帧等。其中可以封装：视频采集后、解码后等未经编码的数据（如：YCbCr 数据、RGBA 数据）。

lua虚拟机

阅读源代码的次序

首先、阅读外围的库是如何实现功能扩展的，
然后、阅读 Lua 的具体实现。
之后、可以开始了解 Lua VM 的实现。
接下来就是分别理解函数调用、返回，string，metatable，table实现
debug模块是一个额外的设施、
最后是parse 等等编译相关的部分。
垃圾收集将是最难的部分，可能会花掉最多的时间去理解细节。Lua GC 的源码剖析

虚拟机核心功能

源代码解析和预编译

内嵌库

外部符号的前缀指示其来自的模块：

luaA_-lapi.c
luaB_-lbaselib.c
luaC_-lgc.c 垃圾回收部分
luaD_-ldo.c 函数的运行流程：函数调用及返回
luaE_-lstate.c 虚拟机的当前状态
luaF_-lfunc.c function实现
luaG_-ldebug.c
luaH_-ltable.c table实现
luaI_-lauxlib.c
luaK_-lcode.c
luaL_-lauxlib.c / h，linit.c（公共函数）
luaM_-lmem.c 内存管理
luaO_-lobject.c 不同的数据类型
luaP_-lopcodes.c 虚拟机的行为是由一组 opcode 控制的
luaS_-lstring.c string实现
luaT_-ltm.c 元表
luaU_-lundump.c
luaV_-lvm.c 虚拟机对 opcode 的解析和运作
luaX_-llex.c
luaY_-lparser.c
luaZ_-lzio.c 带缓冲的流处理
lua_-lapi.c / h + luaconf.h，debug.c
luai_-luaconf.h
luaopen_-luaconf.h +库（lbaselib.c，ldblib.c，liolib.c，lmathlib.c，
loadlib.c，loslib.c，lstrlib.c，ltablib.c）

结构体/类型

Value结构体

1
2
3
4
5
6
7
8
9
10

/*
** Union of all Lua values
*/
typedef union Value {
  struct GCObject *gc;    /* collectable objects */
  void *p;         /* light userdata */
  lua_CFunction f; /* light C functions */
  lua_Integer i;   /* integer numbers */
  lua_Number n;    /* float numbers */
} Value;

TValue结构体

1
2
3
4
5
6
7
8
9
10

/*
** Tagged Values. This is the basic representation of values in Lua:
** an actual value plus a tag with its type.
*/

#define TValuefields	Value value_; lu_byte tt_

typedef struct TValue {
  TValuefields;
} TValue;

GCObject

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/*
** Common Header for all collectable objects (in macro form, to be
** included in other objects)
*/

#define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked


/*
** Common type has only the common header
*/
struct GCObject {
  CommonHeader;
};

可回收的类型,都继承自GCObject

• TString
• Udata
• Proto
• Closure
• Table

TString的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

/*
** Header for string value; string bytes follow the end of this structure
** (aligned according to 'UTString'; see next).
*/
typedef struct TString {
  CommonHeader;
  lu_byte extra;  /* reserved words for short strings; "has hash" for longs */
  lu_byte shrlen;  /* length for short strings */
  unsigned int hash;
  union {
    size_t lnglen;  /* length for long strings */
    struct TString *hnext;  /* linked list for hash table */
  } u;
} TString;

Udata定义

1
2
3
4
5
6
7
8
9
10
11

/*
** Header for userdata; memory area follows the end of this structure
** (aligned according to 'UUdata'; see next).
*/
typedef struct Udata {
  CommonHeader;
  lu_byte ttuv_;  /* user value's tag */
  struct Table *metatable;
  size_t len;  /* number of bytes */
  union Value user_;  /* user value */
} Udata;

Proto定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/*
** Function Prototypes
*/
typedef struct Proto {
  CommonHeader;
  lu_byte numparams;  /* number of fixed parameters */
  lu_byte is_vararg;
  lu_byte maxstacksize;  /* number of registers needed by this function */
  int sizeupvalues;  /* size of 'upvalues' */
  int sizek;  /* size of 'k' */
  int sizecode;
  int sizelineinfo;
  int sizep;  /* size of 'p' */
  int sizelocvars;
  int linedefined;
  int lastlinedefined;
  TValue *k;  /* constants used by the function */
  Instruction *code;  /* opcodes */
  struct Proto **p;  /* functions defined inside the function */
  int *lineinfo;  /* map from opcodes to source lines (debug information) */
  LocVar *locvars;  /* information about local variables (debug information) */
  Upvaldesc *upvalues;  /* upvalue information */
  struct LClosure *cache;  /* last-created closure with this prototype */
  TString  *source;  /* used for debug information */
  GCObject *gclist;
} Proto;

Closure分为两种，Lua闭包和C闭包，定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
** Closures
*/

#define ClosureHeader \
	CommonHeader; lu_byte nupvalues; GCObject *gclist

typedef struct CClosure {
  ClosureHeader;
  lua_CFunction f;
  TValue upvalue[1];  /* list of upvalues */
} CClosure;

typedef struct LClosure {
  ClosureHeader;
  struct Proto *p; //lua函数的原型指针
  UpVal *upvals[1];  /* list of upvalues */
} LClosure;

Table定义：

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct Table {
  CommonHeader;
  lu_byte flags;  /* 1<<p means tagmethod(p) is not present */
  lu_byte lsizenode;  /* log2 of size of 'node' array */
  unsigned int sizearray;  /* size of 'array' array */
  TValue *array;  /* array part */
  Node *node;
  Node *lastfree;  /* any free position is before this position */
  struct Table *metatable;
  GCObject *gclist;
} Table;

从面向对象的角度分析的话，可以认为这5种内部基础类型，都继承自GCObject。
创建一个内部对象，使用同一个的接口函数luaC_newobj (lua_State *L, int tt, size_t sz) 参数说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/*
** create a new collectable object (with given type and size) and link
** it to 'allgc' list.
*/
GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
  global_State *g = G(L);
  GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
  o->marked = luaC_white(g); //标记这个对象是white
  o->tt = tt;  //类型
  o->next = g->allgc; //新创建的对象放到gclist的最前面
  g->allgc = o;
  return o;
}

#define luaM_newobject(L,tag,s)	luaM_realloc_(L, NULL, tag, (s))

/*
** generic allocation routine.
*/
void *luaM_realloc_ (lua_State *L, void *block, size_t osize, size_t nsize) {
  void *newblock;
  global_State *g = G(L);
  size_t realosize = (block) ? osize : 0; //新建的话，block都是NULL
  lua_assert((realosize == 0) == (block == NULL));
#if defined(HARDMEMTESTS)
  if (nsize > realosize && g->gcrunning)
    luaC_fullgc(L, 1);  /* force a GC whenever possible */
#endif
  newblock = (*g->frealloc)(g->ud, block, osize, nsize);  //调用的就是l_alloc
  if (newblock == NULL && nsize > 0) {
    lua_assert(nsize > realosize);  /* cannot fail when shrinking a block */
    if (g->version) {  /* is state fully built? */
      luaC_fullgc(L, 1);  /* try to free some memory... */
      newblock = (*g->frealloc)(g->ud, block, osize, nsize);  /* try again */
    }
    if (newblock == NULL)
      luaD_throw(L, LUA_ERRMEM);
  }
  lua_assert((nsize == 0) == (newblock == NULL));
  g->GCdebt = (g->GCdebt + nsize) - realosize;
  return newblock;
}

GCObjcet类型

通过统一的接口luaC_newobj函数，创建的内部对象都是GCObjcet类型。如果要正常使用，还需要做一次转换，LUA对于这种抽象结构转换为具体对象结构的行为，封装了一套宏函数:

1
2
3
4
5
6
7
8
9
10
11

/* macros to convert a GCObject into a specific value */
#define gco2ts(o)  \
	check_exp(novariant((o)->tt) == LUA_TSTRING, &((cast_u(o))->ts))
#define gco2u(o)  check_exp((o)->tt == LUA_TUSERDATA, &((cast_u(o))->u))
#define gco2lcl(o)  check_exp((o)->tt == LUA_TLCL, &((cast_u(o))->cl.l))
#define gco2ccl(o)  check_exp((o)->tt == LUA_TCCL, &((cast_u(o))->cl.c))
#define gco2cl(o)  \
	check_exp(novariant((o)->tt) == LUA_TFUNCTION, &((cast_u(o))->cl))
#define gco2t(o)  check_exp((o)->tt == LUA_TTABLE, &((cast_u(o))->h))
#define gco2p(o)  check_exp((o)->tt == LUA_TPROTO, &((cast_u(o))->p))
#define gco2th(o)  check_exp((o)->tt == LUA_TTHREAD, &((cast_u(o))->th))

推荐一本书<自己动手实现lua虚拟机>

lundump文件

字节流结构 二进制 chunk

头部header

{
签名， “\x1bLua” (0x1b4c7561)
版本， 0x53
格式(0x00) 0x00
LUAC_DATA 0x1993 0d 0a
cint 4
sizet 8
lua虚拟机指令 4
lua_integer 8
lua_number 8
lua_int 0x5678（判断大小端）
lua_num 370.5 (浮点数格式)

}

函数原型

1. 源文件名
   以@开头的是源码编译而来，以=开头的，是标准库而来
2. 起止行号
   两个cint,主函数为0
3. 固定参数个数
4. 是否是Vararg函数
5. 寄存器数量
   MaxStackSize, 因为lua是一种栈结构,可以按索引访问，模拟寄存器
6. 指令表
7. 常量表
8. Upvalue表 {Instack,Idx}两个字节
9. 子函数原型表
10. 行号表. 和指令表中的指令一一对应
11. 局部变量表
    LocVar
    {

    VarName  String
    StartPC   Uint32
    EndPC       Uint32
    

    }
12. Upvalue名列表

行号表、局部变量表、Upvalue名列表 都是调试信息

解析二进制 chunk

//头部header校验
lundump.h 里面看 checkHeader函数

//函数原型
LoadCode(S, f);
LoadConstants(S, f);
LoadUpvalues(S, f);
LoadProtos(S, f);
LoadDebug(S, f);

指令集

lopcodes文件

1. 基于栈的虚拟机(Stack Based)
   Java、.NET、CLR、Python、ruby、Yarv;
   PUSH/POP操作栈，指令集大，平均长度短
2. 基于寄存器(Resigter Based), lua_5.0以后
   需要把寄存器地址编码进指令，平均长度长

lua采用定长指令集（大约47条指令）， 每条指令4字节32位，6位Opcode操作码，26位操作数Operand

指令编码格式

编码模式

按照高26位区分，四种mode， iABC、iABx、iAsBx、iAx
iABC可以携带ABC三个操作数8+9+9比特
iABx携带 A、Bx，8+18
iAx Ax，26
iAsBx As、Bx 8+18

操作码

6位，最多64条指令，参看opcodes

操作数

A主要用来表示目标寄存器索引，OpArgN、U、R、K

指令表

LUAI_DDEF const lu_byte luaP_opmodes[NUM_OPCODES]

指令解码

CREATE_ABC、CREATE_ABx、CREATE_Ax
sBx是有符号整数，18位。 Excess-K编码模式，Offset Binary. x-K. K取最大无符号一半

Lua API

主要以Lua_开头的。60多个luaL_开头的辅助函数，付主函数建立在基础函数之上

Lua栈

Lua栈是宿主语言和Lua语言沟通的桥梁，api基本上也都是操作这个所谓的栈结构lua_state

Lua数据类型

8种， nil、boolean、number、string、table、function、thread、userdata

虚拟机雏形 Lua运算符

程序计数器(Program Counter, 简称PC)记录正在执行的指令。

表

lua表是一个关联数组, 包含哈希表和数组两个部分

函数调用

参数

• 固定参数个数，未传递则nil，多传递则忽略
• 返回值，外部接受几个，多退少补nil的策略，作为函数参数，如数覆盖

load,加载二进制chunk或者源码。把被调函数推入栈顶
call,

交互 lua <-> 其它语言

lua注册表，lua_status里
lua全局环境 G， GlobalTable

闭包和Upvalue

1. 一等函数，java不支持，可作为参数传递，返回等
2. 变量作用域。 动态作用域、静态作用域
3. 闭包。 词法作用域捕获了非局部变量的嵌套函数

Upvalue是lua里面的术语，就是闭包内部捕获的非局部变量。
嵌套函数，捕获外围的外围的函数的变量，外围函数会捕获更外围的局部变量。扁平闭包。

_ENV — 全局环境 隐式的Upvalue

元变成 Metaprogram

值类型默认没有元表，元表nil。 字符串提供了默认元表。

迭代器

迭代器模式.
数值for循环是借助FORPREP和FORLOOP两条指令完成
通用for循环，TFORCALL和TFORLOOP两条指令

异常和错误处理

Lua语法和编译器

• 词法分析
• 抽象语法树
• 语法分析
• 代码生成

词法分析

字符流(源码)，以’token’的形式分解
类型注释、关键字、标识符、字面量、运算符、分隔符等
lua会忽略 \n \r \t \v \f 空格等空白字符
忽略注释

token -> { … ; : . } .etc

抽象语法树 AST

计算机编程语言一般使用上下文无关文法(Context-free Grammar, CFG)描述，而CFG一般使用巴科斯范式(Backus-Naur Form, BNF)或者其扩展EBNF(Extended BNF)书写

语法分析

YACC、Bison、ANTLR、JavaCC

代码生成

辅助API和基础库

基本分类：

• 1.朴素法：BF(Brute Force)

  暴风(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。

  • 思路

    首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则S向右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)

  • 匹配过程
    

  • 代码
    

• 2.基于前后缀

  • KMP

    • 思路
      假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置。如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值），即移动的实际位数为：j - next[j]，且此值大于等于1。

      next 数组各值的含义：代表当前字符==之前：不包括自身==的字符串中，有多大长度的相同前缀后缀。例如如果next [j] =k，代表j之前的字符串中有最大长度为k的相同前缀后缀。此也意味着在某个字符失配时，该字符对应的next值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，==而不是跳到开头，且具体跳过了k 个字符，这就是KMP相对于BF的优化==。

    • 最长前缀后缀表
      对于P = p0 p1 …pj-1 pj，寻找模式串P中长度最大且相等的前缀和后缀。如果存在p0 p1 …pk-1 pk = pj- k pj-k+1…pj-1 pj，那么在包含pj的模式串中有最大长度为k+1的相同前缀后缀。比如求模式串“ABCDABD”的最长前缀后缀表过程：
      

      所以最后求得的模式串“ABCDABD”的最长前缀后缀表为：
      

    • 根据前缀后缀表推导next数组
      next 数组考虑的是==除当前字符外==的最长相同前缀后缀，所以通过前面最长前缀后缀表求得各个前缀后缀的公共元素的最大长度后，只要稍作变形即可：将前面最长前缀后缀表中求得的值整体右移一位，然后初值赋为-1，如下表格所示：
      

    • 如何求next数组

      • 根据前面匹配的求后一个的next
        给定模式串ABCDABCE，且已知next [j] = k（相当于“p0 pk-1” = “pj-k pj-1” = AB，可以看出k为2），现要求next [j + 1]等于多少？因为pk = pj = C，所以next[j + 1] = next[j] + 1 = k + 1（可以看出next[j + 1] = 3）。代表字符E前的模式串中，有长度k+1 的相同前缀后缀。
        但如果====pk== != pj== 呢？说明“p0 pk-1 pk”  ≠ “pj-k pj-1 pj”。换言之，当pk != pj后，字符E前有多大长度的相同前缀后缀呢？很明显，因为C不同于D，所以ABC 跟 ABD不相同，即字符E前的模式串没有长度为k+1的相同前缀后缀，也就不能再简单的令：next[j + 1] = next[j] + 1。所以，这个时候可以去找p[k]的前缀中有没有合适的前缀。见下图递归推导过程
        
      • 递归的推导过程
        k = next[k];
        待求的是p[j+1]，发现p[j] != p[k]，那就递归寻找p[next[k]]和p[j]是否一样，如果一样，那next[j+1] = next[next[k] + 1
        

    • 求next数组代码
      见IDEA代码

    • 匹配过程
      假设S=“ABCDAB ABCDABCDABDE”，P=“ABCDABD”

      1. P[0]跟S[4]匹配成功，P[1]跟S[5]也匹配成功…，直到当匹配到P[6]处的字符D时失配（即S[10] != P[6]），由于P[6]处的D对应的next值为2，所以下一步用P[2]处的字符C继续跟S[10]匹配，相当于向右移动：j-next[j]=6-2=4位。
         
      2. 向右移动4位后，P[2]处的C再次失配，由于C对应的next值为0，所以下一步用P[0]处的字符继续跟S[10]匹配，相当于向右移动：j - next[j] = 2 - 0 = 2 位。
         
      3. 移动两位之后，A 跟空格不匹配，模式串后移1 位。
         
      4. P[6]处的D再次失配，因为P[6]对应的next值为2，故下一步用P[2]继续跟文本串匹配，当于模式串向右移动 j - next[j] = 6 - 2 = 4 位。
         
      5. 匹配成功，过程结束。
         

    • kmp算法查找过程
      见IDEA代码

    • next数组的优化
      比如，求模式串“abab”的next 数组，可得其next 数组为-1 0 0 1，当它跟下图中的文本串去匹配的时候，发现b跟c失配，于是模式串右移j - next[j] = 3 - 1 =2位。
      

      右移2位后，b又跟c失配。事实上，因为在上一步的匹配中，已经得知p[3] = b，与s[3] = c失配，而右移两位之后，让p[ next[3] ] = p[1] = b 再跟s[3]匹配时，必然失配。问题出在哪呢？
      

      问题出在不该出现p[j] = p[ next[j] ]。为什么呢？理由是：当p[j] != s[i] 时，下次匹配必然是p[ next [j]] 跟s[i]匹配，如果p[j] = p[ next[j] ]，必然导致后一步匹配失败（因为p[j]已经跟s[i]失配，然后还用跟p[j]等同的值p[next[j]]去跟s[i]匹配，很显然，必然失配），所以不能允许p[j] = p[ next[j ]]。如果出现了p[j] = p[ next[j] ]咋办呢？如果出现了，则需要再次递归，即令next[j] = next[ next[j] ]
      见IDEA代码

    • 时间复杂度
      如果文本串的长度为n，模式串的长度为m，那么匹配过程的时间复杂度为O(n)，算上计算next的O(m)时间，KMP的整体时间复杂度为O(m + n)。

    • 参考资料

      • July大神–从头到尾彻底理解KMP
      • 7分钟动画理解KMP

  • BM(Boyer-Moore)
    Boyer-Moore算法平均要比KMP快3-5倍，grep，window电脑的查找还有各种文本查找都用的BM算法。它和之前的BF和KMP匹配的过程不大一样，采用的是从后往前对比的过程。BM算法实际上包含两个并行的算法（也就是两个启发策略）：坏字符算法（bad-character shift）和好后缀算法（good-suffix shift）。这两种算法的目的就是让模式串每次向右移动尽可能大的距离

    • 思路
      从后往前匹配。如果遇到不一致的字符，则这个字符就是==坏的字符==，所以坏字符是针对匹配串S的；匹配的路上相同的字符以及子集称为==好的后缀==，所以好的字符是针对模式串P的。每次失配时，都要根据这两个启发算法中找到能右移动的最大值。接下来详细讨论坏字符算法和好后缀算法这两个启发式。
    • 启发式
      • 坏字符算法
        当出现一个坏字符时,BM算法向右移动模式串,让模式串中==最靠右的对应字符==与坏字符相对,然后继续匹配。坏字符算法有两种情况。
        • case 1: 模式串中不存在坏字符。这种情况直接右移模式串P的长度

            ![bm_bad_1](https://s.momocdn.com/w/u/others/2019/12/26/1577347131411-bm_bad_1.png)     
          

          比如底下的第一次匹配的字符‘d’，在模式串中不存在，直接右移模式串长度

            ![bm_bad_11](https://s.momocdn.com/w/u/others/2019/12/26/1577347131365-bm_bad_11.png)       
          

        • case 2:模式串中有对应的坏字符时，让模式串中最==靠右的对应字符==与坏字符相对
          比如还是上图，在第一次右移模式串P的长度后，模式串末尾的c和主串末尾的b不匹配，说明‘b’是坏字符，但是它在模式串P中有两个出现的位置，如果用从末尾开始数的第二个‘b’会太激进，漏掉匹配；所以得用==最右边==的‘b’去匹配，这就是坏字符算法的第二种case。
          
      • 好后缀算法
        如果匹配了一个好后缀, 并且在模式中还有另外一个相同的完整后缀或后缀的部分, 那把下一个完整后缀或部分移动到当前后缀位置。假如说，P的后u个字符和S都已经匹配了，但是接下来的一个字符不匹配(坏字符)，我需要移动才能匹配。如果说后u个字符在P其他位置也出现过或部分出现，我们将P右移到前面的u个字符或部分和最后的u个字符或部分相同，如果说后u个字符在P其他位置完全没有出现，直接右移整个pattern。这样，好后缀算法有三种情况:
        • case 1:
          模式串中有子串和好后缀==完全匹配==，则将==失配位置前最靠右==的那个子串移动到好后缀的位置继续进行匹配
          比如下面的例子，第一步在5的位置text的‘c’和pattern的‘b’失配了，说明‘c’是个坏字符，并且‘c’在pattern中有出现，那按照上面坏字符算法的case 2移动pattern最右边的‘c’与text失配的位置5中去继续匹配。接下来在位置7中，text的‘a’和pattern的‘b’失配了，如果坏字符的规则相当于走回头路了，所以保守一点移动一步，有没有更好的？可以看到按好字后缀的定义，8和9位置的‘ab’是好的后缀，并且它们在pattern模式串中有‘ab’和它完全匹配，那就是这种case，移动到完全匹配的位置，这样一次移动了两步，多走了一步，优秀了一点。
          
        • case 2:
          模式串种字串和好后缀只能部分匹配，那就从模式串中找到具有如下特征的最长子串,使得P[m-s…m]=P[0…s]。就是从模式串P的第0个元素开始找，找能匹配最长的部分模式串(为啥从0开始而不是找最右边出现的？)
          比如下面的例子，一利用花字符算法移动4位，然后在位置4处text的‘a’和pattern的‘b’失配了，如果按坏字符规则要走回头路，所以保守一点右移一步？看看完整的好的后缀为‘cbab’，显然pattern中没有完整能匹配这个完整的‘cbab’后缀的，那就按这种case，取最长的在pattern中出现的部分后缀‘ab’去对应，但是这里有个限制，就是如果是部分后缀匹配，那==只能从pattern的头开始==。想下为啥得这样？这样的话拿pattern的头部的‘ab’去匹配text的部分后缀‘ab’，一下就移动了4位，➡又优秀。
        • case 3:
          如果完全不存在和好后缀匹配的子串，则右移整个模式串，这种情况和坏字符在pattern中没有出现一样，因为怎么都不会匹配成功的
    • 案例分析
      接下来拿Moore教授自己的案例来分析整个过程，模式串为EXAMPLE，主串为：HERE IS A SIMPLE EXAMPLE
      • 上来text的‘S’和pattern的‘E’不匹配，所以‘S’是坏字符，并且‘S’在pattern中不存在，所以按照坏字符算法case 1，直接向右移动pattern的长度7位。
        
      • 接下来text的‘P’和pattern的‘E’不匹配，所以‘P’也是坏字符，但是‘P’在pattern中存在，所以按照坏字符算法case 2，让pattern中最靠右的‘P’与之对齐，也就是向右移动2位
        
      • 按上面移动后
        
      • 然后从末尾开始依次往前面匹配
        
        
        
        
        
      • 注意上面的红框，在text的‘I’和pattern的‘A’失配的时候，‘I’是坏字符，而‘E’，‘LE’，‘PLE’，‘MPLE’都是好的后缀。如果按坏字符的话，因为‘I’在pattern中没有出现，那么需要整个都移动到‘I’的后面，也就是下面这样移动，只能移动==3==位：
        
        但是因为有这么多的好后缀（MPLE、PLE、LE、E），根据上面好后缀算法，因为MPLE在失配位置前没有完全匹配的，所以case1不满足；接下从（PLE、LE、E）这些匹配的部分后缀中找能在失配位置前==最长的==，并且从pattern的0号位置头部开始的，那只有‘E’满足，所以把pattern头部的‘E’移到和text的‘E’一样的位置重新开始匹配。这样一次就移动了==6==位！显然这样更优秀。
        
      • 接下来继续从尾到头开始匹配，上来就失配了，满足坏字符的case2，所以找到pattern的最靠右边的字符‘P’去匹配
        
      • 从尾到头去匹配，匹配成功
        
    • 参考资料
      Moore教授自己的案例demo
      阿里小姐姐的分析过程
      阮一峰的，得结合上面一起看

  • Sunday

    • 思路
      Sunday算法最主要的特点是匹配失败的时候，关注的是主串中这一轮参与匹配的==最末位字符的下一位字符==，并且和BM不一样的是它是从前往后开始匹配。具体规则是：
      • 如果该字符(主串失配位置的下一个字符)没有在模式串中出现则直接跳过它，即模式串右移位数 = 模式串长度 + 1。因为下一个不可能在模式串中存在，所以可以大胆的全部跳过它
      • 如果在模式串中存在，则模式串右移位数 = 模式串长度 - 该字符最右出现的位置(0开始算) = 模式串中该字符最右出现的位置到尾部的距离 + 1。和BM的坏字符的case 2类型，稳妥起见，拿最右边的相同的字符去对应匹配。
    • 案例分析
      假设现在要在主串”substring searching”中查找模式串”search”。
      • 刚开始时，把模式串和主串的左边对齐
        
      • 发现在第二个字符‘u’和‘e’的时候不匹配，根据规则，不匹配的时候关注主串这一轮参加匹配的的最末尾字符的下一个字符，即蓝色的‘i’，因为‘i’不在模式串中，所以向右移动位数 = 模式串长度 + 1 = 6 + 1 = 7，移动后如下图：
        
      • 继续匹配发现第一个字符就不匹配，按规则还是关注这一轮主串参加匹配的最末尾的字符的下一个字符，即蓝色的‘r’，发现它出现在模式串的倒数第3位，所以向右移动位数 = ‘r’到模式串末尾的距离 + 1 = 2 + 1 = 3，移动后如下图：
        
      • 匹配成功
    • 代码
      
    • 缺点
      Sunday算法的核心在向右移动位数move数组，这个依赖与模式串，所以有可能构造处很差的move数组(move数组的值都为1)，比如：
      主串：baaaabaaaabaaaabaaaa
      模式串：aaaaa
      这个模式串中，move[‘a’]的值都为1，因为最右边出现的‘a’就在末尾，所以每次失配时，只能让模式串移动1位，这就退化位BF的朴素算法了，时间复杂度也会飙升到o(m*n)，所以sunday不适合这种重复的模式串。
    • 参考
      参考资料

• 3.基于hash

  • Rabin-Karp算法
    • 背景
      BF这种朴素的字符串匹配算法慢主要有两点：1.每一轮的比较都是一个字符一个字符去比较；2.前一次匹配的信息对于下一次匹配完全用不上。
      所以Rabin-Karp算法对这两点进行了改进：一是每一轮的匹配不用一个个字符去比较，而是把模式串和这一轮匹配的主串用对应的hash数值去比较，所以一次就能匹配完；二是当失配时，把第一字符去掉，然后把下一个字符加进去，重新计算hash，但是这次计算hash可以根据上次的hash在常数时间内快速的算出来，这样上一次匹配的信息也能充分利用起来
    • 思路
      比如我们要在源串”9876543210520”中查找”520”，因为这些字符串中只有数字，所以我们 可以使用字符集{‘0’,’1’,’2’,’3’,’4’,’5’,’6’,’7’,’8’,’9’}来表示字符串中的所有元 素，并且将各个字符映射到数字0～9，然后用M表示字符集中字符的总个数，这里是10， 那么我们就可以将搜索词 “987” 转化为下面的数值：
      (“9”的映射值 * M + “8”的映射值) * M + “7”的映射值 = (9 * 10 + 8) * 10 + 7 = 987 分析一下这个数值：987，它可以代表字符串 “987”，其中:
      代表字符 “9” 的部分是“ “9”的映射值 * (M 的 n - 1 次方) = 9 * (10 的 2 次方) = 900”
      代表字符 “8” 的部分是“ “8”的映射值 * (M 的 n - 2 次方) = 8 * (10 的 1 次方) = 80”
      代表字符 “7” 的部分是“ “7”的映射值 * (M 的 n - 3 次方) = 0 * (10 的 0 次方) = 7 其实这就是987按10进制的表达方式，同理可以去算模式串“520”的hash，显然这两个hash值不相等。接下来应该把‘9’去掉，把‘6’加进来。那如何利用前面‘987’计算的hash的信息呢？首先我们把 987 减去代表字符 “9” 的部分：987 - (“9”的映射值 * (M 的 n - 1 次方)) = 987 - (9 * (10 的 2 次方)) = 987 - 900 = 87，然后再乘以 M（这里是 10），再加上 “6” 的映射值，就成了‘876’ ：87 * M + “6”的映射值 = 87 * 10 + 6 = 876。然后根据这个规则继续匹配。当两个数值相等时，未必是真正的相等，我们需要进行一次细致的检查（再进行一次朴素的字符串比较）。若不匹配，则可以排除掉，防止hash碰撞的情况。 这里我们列举的是10进制的情况，如果是ASCII 字符集的话M可以取值128；这个M值尽量取较大的素数，这样使得更多的位参与运算减少hash碰撞。如果我们要在 Unicode 字符集范围内查找“搜索词”，由于 Unicode 字符集中有 1114112 个字符，那么 M 就等于 1114112，而 Go 语言中使用 ==16777619== Go的strings源码作为 M 的值，16777619 比 1114112 大（更大的 M 值可以容纳更多的字符，这是可以的），而且 16777619 是一个素数。这样就可以使用上面的方法计算 Unicode 字符串的数值了。进而可以对 Unicode 字符串进行比较了。
    • 代码
      计算待匹配模式串sep的hash和最高位权重的值pow
      匹配算法
      
    • 案例
      比如在ABCDE里去匹配BCD，我们用q表示常数primeRK
      BCD的hash计算出来应该是B q^2 + C q + D
      ABC的hash应该是 A q^2 + B q + C
      当D来的时候如何操作的呢？根据之前的规则：
      [A q^2 + B q + C] q + D - A pow = A q^3 - A pow + B q^2 + C q + D
      而这个pow是可以和go源码里一样提前算出来的，所以在失陪时计算下一个hash能在常数时间快速得到，而两个hash值只是数值对比，一样快的飞起。
    • 参考
      Go的strings源码
      参考资料1
      参考资料2

• 其他

  • AC算法
    基于前缀的AC算法，构造goto表
    参考资料
  • Bitmap算法
    用一个 bit 位来标记某个元素节省存储空间
    参考资料

• Lua源码学习
• 在iOS上面的应用，Lua热修复
• lua随缘记录

参考：
虚拟机之比较，lua 5 的实现

源码我已公开至 github , 持续更新维护

访问链接如下
https://github.com/wangkejie/lua_oc

首先熟悉下lua和原生的交互

1. __call 元方法
2. __index 元方法
3. __newindex 元方法
4. __gc

还有很多 __add __mode等等。自行学习。

方法说明

iOS 14.5 下 fishhook 会 crash

github相关信息
github issue
resolve
protections ios13

Fishhook 考虑到过内存访问权限的问题，在 If hooking in __DATA_CONST, make writable before trying to write 和 Properly restore protections for iOS 13 这两个 PR 中，对于 __DATA_CONST 段中的数据，作者在

1

indirect_symbol_bindings[i] = cur->rebindings[j].replacement;

这一行赋值操作之前，使用了 mprotect 将所属内存区域的访问权限改成了“读写”，在这一行赋值操作以后，再次使用 mprotect 将所属内存区域的访问权限改回了原始值。

然而这两个 PR 其实是有问题的：
1、mprotect 修改内存区域的访问权限时，传入的内存地址是需要按页对齐的，所以开源版本的 fishhook 在旧版 iOS 系统上，mprotect 都有很大概率不成功（返回 -1），官方文档也印证了这点。

2、oldProtection = get_protection(rebindings); 这一行的目的是保存原先的访问权限，但是传入的参数是错误的，这会导致“在这一行赋值操作以后，再次使用 mprotect 将所属内存区域的访问权限改回了原始值”在实际执行中，“改回了原始值”实际是“改成可读写”（当然由于 mprotect 页对齐的问题很大概率修改不成功），因为 rebindings 是 malloc 出来的。

所以，一直以来，这两个 PR 大概率没有发挥预期的作用， indirect_symbol_bindings[i] 所在的内存区域，如果在程序启动后是只读的，那么 fishhook 的过程中，它也是只读的。只要赋值，就会触发 crash。

查看小技巧

1、无论是 iOS 14.4 还是 iOS 14.5，mprotect 修改内存区域为读写时，都失败了（返回 -1）。
2、但是在 mprotect 修改前，iOS 14.4 上 indirect_symbol_bindings[i] 所在的内存区域是读写的，而 iOS 14.5 上变成了只读。
为了便于理解，我们可以在程序启动后、fishhook 开始前，通过 memory graph 来观察各个内存区域的访问权限：

抓取 memory graph 后，在 Xcode 中选择 File -> Export Memory Graph，导出 memory graph 后使用 vmmap 命令得到各个内存区域的快照

观察 libxpc.dylib 的 __DATA_CONST 段映射在内存中的访问权限：

1
2
3
4

# iOS 14.5 
__DATA_CONST                1edadef10-1edae35c0    [   18K    18K     4K     0K] r--/rw- SM=COW          /usr/lib/system/libxpc.dylib
# iOS 14.4
__DATA_CONST                1f30167b0-1f301ae70    [   18K    18K     6K     0K] rw-/rw- SM=COW          /usr/lib/system/libxpc.dylib

可以发现，iOS 14.5 中，libxpc.dylib 的 __DATA_CONST 段是只读的，而 iOS 14.4 中是读写的。
同时观察其他系统库，能发现 iOS 14.5 中，不少系统库的 __DATA_CONST 段都从 iOS 14.4 的读写变成了只读，同时撞上了一直以来都有的 mprotect 失效的问题，所以产生了 crash。

解决参考上面issue, 核心代码如下

1

mprotect((void *)trunc_address, section->size+trunc_size, PROT_READ | PROT_WRITE);

1
2
3
4
5

trunc_address = trunc_page((vm_size_t)indirect_symbol_bindings);
trunc_size =(vm_size_t)indirect_symbol_bindings -trunc_address;
pthread_mutex_lock(&mutex);
oldProtection = get_protection((void *)trunc_address);
mprotect((void *)trunc_address, section->size+trunc_size, PROT_READ | PROT_WRITE);

先看一个断点

App Launch 以及 dyld

自行下载参考dyld源码，下面只是我的简要记录

dyldbootstrap::start
{
rebaseDyld 符号便宜aslr address layout random
__guard_setup 栈溢出保护
dyld::_main
}

rebaseDyld {
遍历所有固定的 chains 然后 rebase dyld
所有基于修正链的映像的基地址为零，因此slide == 加载地址

  // now that rebasing done, initialize mach/syscall layer
mach_init(); // from libc.a

}

重点分析的方法

dyld::_main分析

1. 初始化程序运行环境

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

   //获取主程序的macho_header结构以及主程序的slide偏移值 sMainExecutableMachHeader = mainExecutableMH; sMainExecutableSlide = mainExecutableSlide; //获取主程序路径 // Pickup the pointer to the exec path. sExecPath = _simple_getenv(apple, "executable_path"); if (!sExecPath) sExecPath = apple[0]; if ( sExecPath[0] != '/' ) { // have relative path, use cwd to make absolute .... } //获取进程名称 // Remember short name of process for later logging sExecShortName = ::strrchr(sExecPath, '/'); if ( sExecShortName != NULL ) ++sExecShortName; else sExecShortName = sExecPath; //配置进程受限模式 configureProcessRestrictions(mainExecutableMH, envp); //检测环境变量 checkEnvironmentVariables(envp); defaultUninitializedFallbackPaths(envp); `所谓的启动优化就是在这里，添加dyly参数，进行打印的` //判断是否设置了sEnv.DYLD_PRINT_OPTS以及sEnv.DYLD_PRINT_ENV，分别打印argv参数和envp环境变量 if ( sEnv.DYLD_PRINT_OPTS ) printOptions(argv); if ( sEnv.DYLD_PRINT_ENV ) printEnvironmentVariables(envp); //获取当前程序架构 getHostInfo(mainExecutableMH, mainExecutableSlide);

2. 加载共享缓存 shared cache
   mapSharedCache();

3. 实例化主程序，并赋值给ImageLoader::LinkContext

   1 2 3 4 5 6 7 8

   // try { // add dyld itself to UUID list addDyldImageToUUIDList(); sMainExecutable = instantiateFromLoadedImage(mainExecutableMH, mainExecutableSlide, sExecPath); gLinkContext.mainExecutable = sMainExecutable; gLinkContext.mainExecutableCodeSigned = hasCodeSignatureLoadCommand(mainExecutableMH); }

4. 加载插入的动态库++++++++++++++++++++

   1 2 3 4 5

   // load any inserted libraries if ( sEnv.DYLD_INSERT_LIBRARIES != NULL ) { for (const char* const* lib = sEnv.DYLD_INSERT_LIBRARIES; *lib != NULL; ++lib) loadInsertedDylib(*lib); }

5. 链接主程序++++++++++++++

   1 2 3

   gLinkContext.linkingMainExecutable = true; link(sMainExecutable, sEnv.DYLD_BIND_AT_LAUNCH, true, ImageLoader::RPathChain(NULL, NULL), -1); sMainExecutable->setNeverUnloadRecursive();

6. 链接插入的动态库++++++++

   1 2 3 4 5 6 7 8 9

   ... ImageLoader::applyInterposingToDyldCache(gLinkContext); // Bind and notify for the inserted images now interposing has been registered if ( sInsertedDylibCount > 0 ) { for(unsigned int i=0; i < sInsertedDylibCount; ++i) { ImageLoader* image = sAllImages[i+1]; image->recursiveBind(gLinkContext, sEnv.DYLD_BIND_AT_LAUNCH, true); } }

7. 在链接所有插入的image后，执行弱绑定++++++++++++++++++++++++++++++

   1 2 3 4 5

   // <rdar://problem/12186933> do weak binding only after all inserted images linked sMainExecutable->weakBind(gLinkContext); gLinkContext.linkingMainExecutable = false; sMainExecutable->recursiveMakeDataReadOnly(gLinkContext);

8. 执行所有的初始化方法+++++++++++++++++++++

   1 2	// run all initializers initializeMainExecutable();

9. 查找主程序的入口点并返回

   1 2 3 4 5

   // find entry point for main executable result = (uintptr_t)sMainExecutable->getEntryFromLC_MAIN(); return result; }

总结dyld::_main主要做了以下操作(就不一一分析了)：

主程序运行环境初始化及配置，拿到Mach-O头文件 (macho_header里面包含整个Mach-O文件信息其中包括所有链入的动态库信息)
加载共享缓存 shared cache
实例化主程序，并赋值给ImageLoader::LinkContext
加载所有插入的动态库，将可执行文件以及相应的依赖库与插入库加载进内存生成对应的ImageLoader类的image(镜像文件)对象
链接主程序（必须先链接主程序后才能插入）
链接所有的动态库ImageLoader的image(镜像文件)对象，并注册插入的信息，方便后续进行绑定
在链接完所有插入的动态库镜像文件之后执行弱绑定
执行所有动态库image的初始化方法initializeMainExecutable
查找主程序的入口点LC_MAIN并返回result结果，结束整个_dyld_start流程，进入我们App的main()函数！

这里解释一下共享缓存机制：网上自己查询 dyld1.0版本 - dyld3 版本， 当前使用dyld3版本

dyld加载时，为了优化程序启动，在dyld::_main中启用了共享缓存（shared cache）技术。共享缓存会在进程启动时被dyld映射到内存中，之后，当任何Mach-O映像加载时，dyld首先会检查该Mach-O映像与所需的动态库是否在共享缓存中，如果存在，则直接将它在共享内存中的内存地址映射到进程的内存地址空间。在程序依赖的系统动态库很多的情况下，这种做法对程序启动性能会有明显提升。

分析一下_main的第8步，initializeMainExecutable() 倒数第二步

自行根据下面的方法阅读源码
initializeMainExecutable -> runInitializers -> processInitializers -> recursiveInitialization -> notifySingle

最后我想说的就是这个notifySingle，

1

context.notifySingle(dyld_image_state_dependents_initialized, this, &timingInfo);

找到一个关键的函数指针* sNotifyObjCInit, 全局搜索找到赋值

1
2
3
4
5
6
7
8
9

void registerObjCNotifiers(_dyld_objc_notify_mapped mapped, _dyld_objc_notify_init init, _dyld_objc_notify_unmapped unmapped)
{
    // record functions to call
    sNotifyObjCMapped   = mapped;
    sNotifyObjCInit     = init;
    sNotifyObjCUnmapped = unmapped;

    ...
}

全局搜索，看看registerObjCNotifiers这个方法会被谁调用，找到调用的地方_dyld_objc_notify_register函数

不用找了，在objc的源码里面， _dyld_objc_notify_register 是 _objc_init进行调用的。而_objc_init函数则是Runtime的入口函数！

打开Objc源码,搜索_objc_init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/***********************************************************************
* _objc_init
* Bootstrap initialization. Registers our image notifier with dyld.
* Called by libSystem BEFORE library initialization time
**********************************************************************/

void _objc_init(void)
{
    static bool initialized = false;
    if (initialized) return;
    initialized = true;
    
    // fixme defer initialization until an objc-using image is found?
    environ_init();
    tls_init();
    static_init();
    lock_init();
    exception_init();
    
    //注册回调函数
    _dyld_objc_notify_register(&map_images, load_images, unmap_image);
}

看 _dyld_objc_notify_register 注释

1
2
3
4
5
6

* _objc_init
* Bootstrap initialization. Registers our image notifier with dyld. 
* //引导程序初始化。 用dyld注册我们的image通知程序。
* Called by libSystem BEFORE library initialization time
* //在库初始化之前由libSystem调用!!!!!
* 

_objc_init的调用时机是在其他动态库加载之前由libSystem系统库先调用的。

那么到现在就很明确了，其实在dyld::_main主程序的第8步，初始化所有动态库及主程序的时候之前，就先注册了load_images的回调，之后在Runtime调用load_images加载完所有load方法之后，就会回调到dyld::_main的initializeMainExecutable()内部执行回调。

map_images

自行下载objc源码, 找打 _objc_init 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

/***********************************************************************
* _objc_init
* Bootstrap initialization. Registers our image notifier with dyld.
* Called by libSystem BEFORE library initialization time
**********************************************************************/

void _objc_init(void)
{
    static bool initialized = false;
    if (initialized) return;
    initialized = true;
    
    // fixme defer initialization until an objc-using image is found?
    
    //读取影响运行时的环境变量。
    environ_init();
    
    tls_init();
    
    //运行C ++静态构造函数。libc在dyld调用我们的静态构造函数之前调用_objc_init()
    static_init();
    
    lock_init();
    //初始化libobjc的异常处理系统。由map_images()调用。
    exception_init();

    注册回调函数
    _dyld_objc_notify_register(&map_images, load_images, unmap_image);
}

map_images直接返回了map_images_nolock,直接看实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void 
map_images_nolock(unsigned mhCount, const char * const mhPaths[],
                  const struct mach_header * const mhdrs[])
{
    定义一系列变量
    ......
    
    必要时执行首次初始化
    
    //如果是第一次，就准备初始化环境
    if (firstTime) {
        preopt_init();
    }

    // Find all images with Objective-C metadata.
    hCount = 0;

    计算class数量，根据总数调整各种表的大小。
    // Count classes. Size various table based on the total.
    int totalClasses = 0;
    int unoptimizedTotalClasses = 0;
    {
        ......
    }
    ......
    
    执行一次运行时初始化，必须将其推迟到找到可执行文件本身为止。 这需要在进一步初始化之前完成。（如果可执行文件不包含Objective-C代码，但稍后会动态加载Objective-C，则该可执行文件可能不会出现在此infoList中。
    
    if (firstTime) {
    
        //初始化sel方法表 并注册系统内部专门的方法。
        sel_init(selrefCount);
        arr_init();
    }

    直接开始image读取
    if (hCount > 0) {
        _read_images(hList, hCount, totalClasses, unoptimizedTotalClasses);
    }

    firstTime = NO;
}

总结map_images_nolock的流程就是:

• 判断firstTime，firstTime为YES，则执行环境初始化的准备，为NO就不执行
• 计算class数量，根据总数调整各种表的大小并做了GC相关逻辑处理(不支持GC则打印提示信息)
• 判断firstTime，firstTime为YES，执行各种表初始化操作，为NO则不执行
• 执行_read_images进行读取，然后将firstTime置为NO，就不再进入上面的逻辑了，下次进入map_images_nolock就开始直接_read_images

接下来我们重点分析_read_images

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

/***********************************************************************
* _read_images
* Perform initial processing of the headers in the linked 
* list beginning with headerList. 
*
* Called by: map_images_nolock
*
* Locking: runtimeLock acquired by map_images
**********************************************************************/
void _read_images(header_info **hList, uint32_t hCount, int totalClasses, int unoptimizedTotalClasses)
{

    定义一系列局部变量
    ......

    1. 重新初始化TaggedPointer环境****************
    
    if (!doneOnce) {
        doneOnce = YES;

         ......

        if (DisableTaggedPointers) {
            disableTaggedPointers();
        }
        
        initializeTaggedPointerObfuscator();

        ......
        
        注意！！！！！创建表 gdb_objc_realized_classes 和 allocatedClasses
        
        ......
        
        int namedClassesSize = 
            (isPreoptimized() ? unoptimizedTotalClasses : totalClasses) * 4 / 3;
        gdb_objc_realized_classes =
            NXCreateMapTable(NXStrValueMapPrototype, namedClassesSize);
        
        allocatedClasses = NXCreateHashTable(NXPtrPrototype, 0, nil);
        
        ......
    }


    // Discover classes. Fix up unresolved future classes. Mark bundle classes.
    
    2. 开始遍历头文件，进行类与元类的读取操作并标记(旧类改动后会生成新的类，并重映射到新的类上)************************

    for (EACH_HEADER) {
        //从头文件中拿到类的信息
        classref_t *classlist = _getObjc2ClassList(hi, &count);
        
        if (! mustReadClasses(hi)) {
            // Image is sufficiently optimized that we need not call readClass()
            continue;
        }

        bool headerIsBundle = hi->isBundle();
        bool headerIsPreoptimized = hi->isPreoptimized();

        for (i = 0; i < count; i++) {
            Class cls = (Class)classlist[i];
            
            //!!!!!!核心操作，readClass读取类的信息及类的更新
            Class newCls = readClass(cls, headerIsBundle, headerIsPreoptimized);
            
            ......
            
        }
    }
        
    ......

    3. 读取@selector*************************************
    
    // Fix up @selector references
    static size_t UnfixedSelectors;
    {
        mutex_locker_t lock(selLock);
        for (EACH_HEADER) {
            if (hi->isPreoptimized()) continue;
            
            bool isBundle = hi->isBundle();
            SEL *sels = _getObjc2SelectorRefs(hi, &count);
            UnfixedSelectors += count;
            for (i = 0; i < count; i++) {
                const char *name = sel_cname(sels[i]);
                sels[i] = sel_registerNameNoLock(name, isBundle);
            }
        }
    }


    ......
    
    
    4. 读取协议protocol*************************************
    // Discover protocols. Fix up protocol refs.
    for (EACH_HEADER) {
        extern objc_class OBJC_CLASS_$_Protocol;
        Class cls = (Class)&OBJC_CLASS_$_Protocol;
        assert(cls);
        NXMapTable *protocol_map = protocols();
        bool isPreoptimized = hi->isPreoptimized();
        bool isBundle = hi->isBundle();

        protocol_t **protolist = _getObjc2ProtocolList(hi, &count);
        for (i = 0; i < count; i++) {
            readProtocol(protolist[i], cls, protocol_map, 
                         isPreoptimized, isBundle);
        }
    }

   ......


    5. 处理分类category，并rebuild重建这个类的方法列表method list*******************************
    
    // Discover categories. 
    for (EACH_HEADER) {
        category_t **catlist = 
            _getObjc2CategoryList(hi, &count);
        bool hasClassProperties = hi->info()->hasCategoryClassProperties();

        for (i = 0; i < count; i++) {
            category_t *cat = catlist[i];
            Class cls = remapClass(cat->cls);
            
            ......
            
            bool classExists = NO;
            if (cat->instanceMethods ||  cat->protocols  
                ||  cat->instanceProperties) 
            {
                addUnattachedCategoryForClass(cat, cls, hi);
                if (cls->isRealized()) {
                    remethodizeClass(cls);
                    classExists = YES;
                }
                if (PrintConnecting) {
                    _objc_inform("CLASS: found category -%s(%s) %s", 
                                 cls->nameForLogging(), cat->name, 
                                 classExists ? "on existing class" : "");
                }
            }

            if (cat->classMethods  ||  cat->protocols  
                ||  (hasClassProperties && cat->_classProperties)) 
            {
                addUnattachedCategoryForClass(cat, cls->ISA(), hi);
                if (cls->ISA()->isRealized()) {
                    remethodizeClass(cls->ISA());
                }
                if (PrintConnecting) {
                    _objc_inform("CLASS: found category +%s(%s)", 
                                 cls->nameForLogging(), cat->name);
                }
            }
        }
    }

    ......

    if (DebugNonFragileIvars) {
        realizeAllClasses();
    }


    最后是一堆打印***********
    ......
   
}

_read_images的实现主要分为以下步骤：

1. 重新初始化TaggedPointer环境
2. 开始遍历头文件，进行类与元类的读取操作并标记(旧类改动后会生成新的类，并重映射到新的类上)
3. 读取@selector方法
4. 读取协议protocol
5. 处理分类category，并rebuild重建这个类的方法列表method list

两个表，一个叫gdb_objc_realized_classes用来存放已命名的类的列表，另一个叫allocatedClasses用来存放已分配的所有类(和元类)

逐步分析 readClass、@selector、 protocol、 category

从源码中可以看出， readClass 方法有返回值，并且包含三种逻辑处理：

• 找不到该类的父类，可能是弱绑定，直接返回nil；
• 找到类了，判断这个类是否是一个future的类(可以理解为需要实现的一个类，也可以理解为这个类是否有变化)，如果有变化则创建新类，并把旧类的数据拷贝一份然后赋值给新类newCls，然后调用addRemappedClass进行重映射，用新的类替换掉旧的类，并返回新类newCls的地址
• 找到类了，如果类没有任何变化，则不进行任何操作，直接返回class

从readClass的底层实现部分做个延伸思考：日常开发中，对于已经启动完成的工程项目，如果我们未修改任何类的数据，那么再次点击运行会很快完成，但是一旦我们在对这些类进行修改后，在读取这些类的信息(包括类本身的信息以及下面我们要继续分析的协议protocol、分类category、方法selector)，就需要对该类的数据进行更新，这个更新实际上是新建一个类，然后拷贝旧类的数据赋值给新类，然后重映射并用新类替换掉新类，这里面的拷贝以及读写过程其实是相当耗时的！这是类信息改动之后项目再次Run运行起来会比较慢的原因之一。

已经读取完成的类，会被存放到了这个表gdb_objc_realized_classes里面！

分析源码注释及源码得出，addClassTableEntry里面会把这个读取完成的类直接先添加到allocatedClasses表里面，然后再判断addMeta是否为YES，然后会把当前这个类的元类metaClass也添加到allocatedClasses这个表里面。

@selector

点击sel_registerNameNoLock，找到__sel_registerName，在它里面找到关键代码
逻辑其实就是：把方法名插入并存储到namedSelectors这个表里面.

protocol

找到关键函数readProtocol，进入发现其实读取protocol的操作是把protocol存进协议表protocol_map。

category

分类category的读取，里面主要做了下面这些步骤：

1. 从头文件中获取所有的分类列表catlist，然后循环遍历这个列表
2. 在循环中，判断当前分类cat所属的类是否存在，如果不存在则把这个分类置为空catlist[i] = nil; 如果这个分类所属的类存在，那么开始下面两个步骤：
3. 第一个步骤：判断这个分类cat中是否有实例方法instanceMethods，协议protocols以及属性实例instanceProperties，如果有，那么进入remethodizeClass，重新rebuild当前类cls的方法列表
4. 第二个步骤：继续判断这个分类cat中是否有类方法classMethods，协议protocols以及类属性_classProperties，然后重新rebuild当前类所对应元类cls->ISA()的方法列表。

loadimage

调用load方法，父类-子类-所有分类

总结

_objc_init 是系统库，很早就已经 由libSystem系统库先调用的，初始化了很多环境 其中有_dyld_objc_notify_register(&map_images, load_images, unmap_image);

dyld 初始化进程环境，链接动态库，进行 _dyld_objc_notify_register 注册

参考

https://www.jianshu.com/p/ea680941e084

回看过去，做了什么，能否沉淀些东西，简要记录

组件化

详细的内容在另外一个组件化篇幅里记录

1. 组件化目的：

• 共享基础设施
• 下沉公共服务
• 隔离业务代码(模块儿)
• 二进制加速编译，带上dwarf符号信息，和源文件
• 开启modular，支持swift混编
  • 主要是解决头文件引用问题
  • 需要采用’<>’尖括号形式，兼容modular和framework

2. X点

• 借鉴Beehive, 注解方式注册。 类似于java的框架spring的模式，
• 使用自定义goto字符串协议
• 统一管理cocoapods版本号，利用bundle工具管理版本号
• 由于podfile.lock和menifest.lock文件不一致问题，把pod文件加入版本控制

热更新方案

1. 方法中带block的,

   • block在原神生成，在脚本中调用
   • block需要在脚本中生成，在原生调用

2. hook方法，msgforwarding，

3. 利用libffi调用原生C函数，

4. 通过符号找函数地址，dlsym，或者fishhook的方案，利用segment_linkedit, lc_symta（字符表和符号表）b, lc_dysymtab(间接符号表，系统/第三方的导出符号)

CRASH && APM

1. 可捕获的
   • C++、OC、数组越界、抛异常等软件异常
   • 断言等
2. 不可捕获的，或者说是abort
   • oom
   • anr
   • 死锁
   • 非法应用签名
   • 后台超时
   • 内存紧张
   • 设备过热
3. crash监控
   • 注册监听，CPPException，OCException、singal、machException

聊天室业务

1. 架构调整

• mvp为主。 管理各种有戏模板，抽取模板抽象类，统一调度，抽取基类，反向调用
• vchatBus。 聊天室事件总线，协议为key，实现为value，储存在单例中，统一分发
• 优先级队列。 通过堆实现

2. 业务模块儿

• 重构Timer，统一调度
• 实现优先级view，以此重构banner区，房间广播，礼物动效等队列管理
• 重构IM消息分发，RTC事件回调，基于vchatbus组件
• 整理视图层级，functionview，popbackgroudview. 管理各种不同层级的视图，和弹窗

3. 媒体报警日志及问题查询

• 媒体查询
  1. 媒体中台
  2. kibanna日志
  3. IM日志捞取
  4. 接口回调
  5. hubble警告
• crash等问题
  1. 公司内部crash后台分析
  2. MDLog的kibana日志
  3. IM日志捞取
  4. 接口查询

问题

• sdwebimage的问题， 老的下载还在排队，新的下载取消了所有的回调
• init方法的问题arc下，过度release

书

• 程序员的自我修养
• 多线程与内存管理
• 深入理解osx/ios操作系统

性能优化

内存优化

卡顿优化

电量优化

启动优化

体积优化

网络优化

编译优化

APM

调试 & Crash

收集中

性能优化

性能优化，架构先行

• 组件化
  • 共享基础设施
  • 下沉公共服务
  • 隔离业务模块
• 标准化
  • 统一的基础服务
  • 统一的应用框架
  • 统一的开发范式
  • 统一的用户体验

收益

• 共享公共服务，业务统一模板，降低项目复杂度
• 代码复用率 0 -> 80%
• 线上性能问题种类，减少3倍以上
• Crash率，减少3倍以上

端上性能监控

• 可用性
  • Crash
  • Abort
  • 业务异常
• 基础性能
  • 启动时间
  • 包体积
• 流畅性
  • 页面测速
  • 卡炖检测
  • 关键路径
  • 渲染检测
• 资源消耗
  • CPU
  • 内存
  • 流量
  • 储存

    解决问题

• 服务端开关
• 热修复
• 新版本

验证效果，AB实验

网络优化

利用http2.0

• 多路复用；二进制分桢；头部压缩；服务端推送
• 页面加载时间缩短 ~7.5%
• 数据

参考

汇总

https://images.apple.com/media/us/osx/2013/docs/OSX_Mavericks_Core_Technology_Overview.pdf