Yuerer's Blog

虽然本系列主要讲的是 Lua 5.3 中的实现，不过在本篇中，想先聊聊 Lua 垃圾回收的历史。只有了解其历史，才知道为什么这么设计。

Lua GC 历史

Lua 5.0 之前

在 Lua 5.0 之前，Lua 因为没有 userdata ，垃圾回收的工作就很简单了，因为没有 userdata 也就没有了 __gc 元方法，也就不需要针对有特殊析构操作的对象进行特殊处理。

Lua 从早期到现在 2020年 推出的 最新版 Lua 5.4 都是采用的标记扫描算法，垃圾回收算法一般分为两类。

1. 标记扫描算法
2. 引用计数算法

引用计数的话，每个对象都要占用多一块内存，同时需要频繁的增减引用计数值，特别指的是在栈上的时候，Lua 解释器做的又非常简单，如果采用引用计数，还要对指令进行优化。

而早期 标记扫描 也是比较简单，首先它每次扫描且回收垃圾都是需要一次执行完的，其次它只有两种标记，用到或没用到，而且每次创建新对象都会跑一次GC。

显然，这种垃圾回收注定了没人敢用。。。我每创建一个对象，你都跑一次GC，这谁顶得住？

Lua的协程和 Golang的协程不同，它是在同一个主线程上跑的协程，个人感觉用途不是很大，毕竟没有发挥多核的优势，不过还是有不少人认为这是 Lua的一个亮点，可以用来实现异步代码改写为同步代码，减轻人脑负担，然而很多人用的时候，并不了解当 Lua协程调用到C函数而C函数又调用到Lua函数后又执行 yield 的解决方案。本篇主要是来探讨Lua协程的设计。

Lua协程的设计思路

试想一下，如果你来设计一个在同一个主线程上跑，且没有调度的协程，你会怎么做？

可能你会说这还不简单，我们都已经知道了 CallInfo 这样的结构，只需要创建一个新的Lua栈，将新的 函数设置进其 CallInfo ，当执行到 resume 时，则将 Lua栈 推入，去执行新的指令不就行了？

如果Lua只在自己的世界里面玩，从来不调用 C函数，那就还好。但问题是Lua会与其宿主语言也就是C语言进行打交道，会调用C的函数，如果这个C函数又调用了Lua Function，而其又调用了 yield，等到它又被 resume 的时候，它就没办法继续执行那尚未执行完成的C函数。

大致执行流程如下

1
2
3
4
5
6
7
8

// 因为 lua 的 resume，其实是在C中导出的
(1)Lua:resume->[C:resume]
// C函数又调用了 lua的函数 因此会执行到 lua_call
->Lua:Function->[C:Function]->[C:lua_call]
// lua的函数被执行到后，又去执行 yield
->(Lua:Function)->Lua:yield

// 某一刻协程又被启动，此时回不到 C:lua_call

一种可行的思路是，将Lua的协程与每一个系统线程绑定，消耗高(不过我觉得这样才能发挥出多线程的优势嘛)。

Lua采用的方案则是，通过保存C函数和其状态，并标记状态，当 resume时根据已有信息，回到原来未执行完C函数的位置。

以下的 lua_pcallk 为使用例子，倒数第二个参数为上下文，倒数第一个参数则是该C函数如果被中断后，应该继续执行的事情。

1
2
3
4
5
6
7
8

static int luaB_pcall (lua_State *L) {
  int status;
  luaL_checkany(L, 1);
  lua_pushboolean(L, 1);  /* first result if no errors */
  lua_insert(L, 1);  /* put it in place */
  status = lua_pcallk(L, lua_gettop(L) - 2, LUA_MULTRET, 0, 0, finishpcall);
  return finishpcall(L, status, 0);
}

Closure 其实对于 C/C++ 程序员可以简单理解为 函数。不过由于有了 Upvalues 的概念，会让人理解起来不那么容易，但是 Lua 中的所有函数 其实都是 闭包，包括我们第一篇 Lua 5.3 设计实现(一) Lua是怎么跑起来的？) 文章中提到的运行流程的第一个主函数，其实也是一个闭包。

本文中 函数与闭包的名字会混用，请根据其是否含有 Upvalue 进行区分。

Closure

闭包是由 函数原型（Proto）+ （UpValue）组合而成的。

而 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
27

typedef struct Proto {
  CommonHeader;
  lu_byte numparams;  // 固定函数个数
  lu_byte is_vararg;  // 是否是可变长参数
  lu_byte maxstacksize;  // 寄存器数量，用栈模拟
  int sizeupvalues;  // Upvalues 个数

  int sizek;  /* size of 'k' */
  int sizecode;
  int sizelineinfo;
  int sizep;  /* size of 'p' */
  int sizelocvars;

  int linedefined;  // 开始行号
  int lastlinedefined;  // 结束行号
  TString  *source; // 源文件名

  TValue *k;  // 常量表
  Instruction *code;  // 指令表
  struct Proto **p;  // 子函数原型表
  int *lineinfo;  // 行号表 行号与指令对应
  LocVar *locvars;  // 局部变量表
  Upvaldesc *upvalues;  // Upvalue 表

  struct LClosure *cache;  /* last-created closure with this prototype */
  GCObject *gclist;
} Proto;

我们更关注的是 Upvalues。

上一篇主要是讲了 Table 和 MetaMethod 的一些设计实现，谈论到了 Lua 会对 元方法的字符串名字作缓存，同时提到了 Lua 字符串分为长短字符串。这一篇主要是谈论一下 Lua 的长短字符串是怎么设计的？为什么要分长短这两种类型？

TString 结构

可以看到字符串内部会记录哈希值，每个字符串被创建出来就不能被改写，因此为了节约内存，Lua会复用相同的字符串，但是逐字节比较太慢了，因此会预处理将字符串hash，存入字符串的 hash 字段中。

字符串的实际内容会追加到 TString 的后面。

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

typedef struct TString {
  CommonHeader;  // GC 回收
  // 短字符串时 0为需要被GC接管, 1为不被GC回收
  // 长字符串时 0为未hash, 1为已hash
  lu_byte extra;
  lu_byte shrlen; // 短字符串长度, 如果是长字符串则无意义
  unsigned int hash; // 字符串哈希值
  union {
    size_t lnglen; // 长字符串长度 如果为短字符串则无效
    struct TString* hnext; // 短字符串的时候 与相同哈希值的字符串串起的链表
  } u;
} TString;

短字符串全局只有一份，Lua解释器会将其存到 stringtable 这个结构中。字符串 hash 会根据 global_State 的 seed 进行哈希。

上一篇主要讲了 Lua代码 的运作过程，这一篇主讲 Lua Table 和 基于 MetaTable 实现的 MetaMethod。

其实我觉得，Lua之所以能大放异彩，其一是它非常精小，其二是其开源，其三则是因为它的MetaMethod 的设计。

Lua 类型

虽然本篇主要讲 table，不过在那之前，最好先来认识一下 Lua 其他类型在 Lua解释器中的实现。

UserData 暂且不谈，NUMBER细分为浮点数和整数，字符串则分长短字符串，函数又分Lua函数和C函数还有轻量的C函数，这一部分会分别留到字符串和闭包的时候再谈论。

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

#define LUA_TNIL		0
#define LUA_TBOOLEAN		1
#define LUA_TLIGHTUSERDATA	2
#define LUA_TNUMBER		3
#define LUA_TSTRING		4
#define LUA_TTABLE		5
#define LUA_TFUNCTION		6
#define LUA_TUSERDATA		7
#define LUA_TTHREAD		8

#define LUA_TNUMFLT	(LUA_TNUMBER | (0 << 4))  /* float numbers */
#define LUA_TNUMINT	(LUA_TNUMBER | (1 << 4))  /* integer numbers */

#define LUA_TSHRSTR	(LUA_TSTRING | (0 << 4))  /* short strings */
#define LUA_TLNGSTR	(LUA_TSTRING | (1 << 4))  /* long strings */

#define LUA_TLCL	(LUA_TFUNCTION | (0 << 4))  /* Lua closure */
#define LUA_TLCF	(LUA_TFUNCTION | (1 << 4))  /* light C function */
#define LUA_TCCL	(LUA_TFUNCTION | (2 << 4))  /* C closure */

其实在此之前已经写了一个 Lua 5.3 源码剖析系列，还有好几篇存档没有发。为什么突然又不发了呢？（甚至还删了），是因为我感觉之前那样学习的方式过于难受，折磨心智（人这一生最不该做的就是折磨自己），没有抓清主次，同时和网络上的博文同质化严重。因此就决定，再读一次 Lua 的源码，这次读的是 Lua 5.3.6 是 Lua 5.3 系列的最后一个版本。

本系列，不会谈论 Lua 语法，也默认读者已经有 Lua使用经验，我们将绕过 Lua 的编译器（大部分都是词法语法分析），直接进入到 Lua解释器中，来学习我们写好的 Lua 源码是怎么跑起来的。为了理解的方便，代码会有大量删减，只抽取其核心。

Lua 编译过程

虽然，我们在一开始就说好，不谈论 Lua 编译器，但是还是要先理解 Lua 的运行机制。这里简单提一下，你写好的 xxx.lua 文件 会经过 luac 工具将 Lua源代码编译成 二进制文件，Lua 作者在代码中称其为 Chunk，接着 Lua解释器会加载它并执行，所以 Lua执行起来，看起来是边执行边编译，但实际上是先编译成 Chunk，再加载 Chunk去执行。

加载 Chunk

假设我们现在有一段 lua代码，且已经过了 luac工具 编译出了 Chunk，那么 Lua解释器是怎么将其加载的呢？

我们可以大胆猜测，Lua会有个load函数，去load我们的 Chunk。

1
2
3
4
5
6
7
8
9
10

LUA_API int lua_load (lua_State *L, lua_Reader reader, void *data,
                      const char *chunkname, const char *mode) {
  ....
  status = luaD_protectedparser(L, &z, chunkname, mode);
  if (status == LUA_OK) {  /* no errors? */
    LClosure *f = clLvalue(L->top - 1);  /* get newly created function */
		....
  }
  return status;
}

近期工作的内容主要是设计一个通用的游戏排行榜服务器, 通用的含义指的是同时为多个项目组提供一套通用的解决方案, 经过不断的调研, 最终写下此文.

本文将会讲述 排行榜的多种实现方式, 不过最终我选择了 SkipList 作为底层的数据结构, 因此会着重讲SkipList.

先来讲一下排行榜的主要功能.

排行榜主要功能

• 更新/删除/获取 一个 Key 在某个 排行榜 上的 排名, 及展示信息
• 获取 一个排行榜 任意区间(例如排名区间) 的展示信息

排行榜排序方案

游戏中的排行榜的排序方案无非就两种

• 实时排序, 即玩家数值变化的瞬间, 就完成了对它的排序
• 非实时排序, 亦可称之为定时排序, 玩家数据变动不立即排序, 而是直到策划所配的时间点到的时候才进行排序

这两种排序方案没有好坏之分, 主要是看策划他想要什么? (或许他自己也不知道想要什么, 他都想试试看, 他只顾着他自己)

前言

本节主要是讲 网络编程中, 常用的I/O 多路复用. 全文大概分为以下几点.

1. 为什么需要I/O多路复用?
2. I/O多路复用的使用场景?
3. 为什么都是与非阻塞I/O进行搭配, 而不是与阻塞I/O进行搭配呢?
4. select 的 优缺点 及 内核实现
5. poll 的 优缺点 及 内核实现
6. epoll 的 优缺点 及 内核实现

这是 Linux 系统编程系列 中的第一篇, 在这个系列里面, 我想以这么个顺序来讲述每一篇的内容, 先是快速简单地了解一下 常见的使用方法, 即API如何使用, 接着再深入其中, 了解内核为API提供的帮助, 大致是 C标准库 → 系统调用 这么个学习路线.

时间的定义

首先要记住 计算机的起始时间 为 (格林威治时间)1970年1月1日0点, 被称作 GMT时间 是时区时间, 不过它是根据地球公转和自转来计算的, 不是特别准确. 在计算机世界中, 往往被称作 UTC时间, 它是以原子钟来计算时间, 简单来说就是 UTC时间 比 GMT时间要准确, 同时两个时间又恰好没有时差, 但是UTC时间又不是时区时间, 因此容易被人弄混.

Loki Allocator 有三个类 这玩意对比起 pool allocator 的优点就在于 它有把内存还给系统

但是它作为一个 内存分配器 却在里面使用了 vector 作为容器… 按道理来说 应该在其内部实现一个简易版的 vector 才不会那么奇怪 但也没所谓 只是 先用了一次标准库的分配器 后续使用容器的时候 就可以用 Loki 分配器了.

• Chunk
• FixedAllocator
• SmallObjAllocator

Chunk 解剖

Chunk 是整个分配器的最底层 里面主要是三个 成员变量

1
2
3
4
5
6

// 指向内存块
unsigned char * pData_;
// 目前可用区块的第一块的索引
unsigned char firstAvailableBlock_;
// 有多少块可用
unsigned char blocksAvailable_;

Chunk 的几个关键函数 已进行 剪裁 和 修改

Chunk 分配

分配流程很简单 就是 申请了内存以后 将每个小区块的第一个字节设置为索引 排好号

取的流程:

1. 从 当前可用区块的第一块索引中取 得当前可用区块
2. 当前可用区块会被返回
3. 被返回的可用区块中的索引 被设置到 当前可用区块索引去(这样下一次就会使用到它)
4. 可用区块数目 - 1