Yuerer's Blog

近期在压测服务器的过程中发现内存随着用户数增加而暴涨，用户数减少内存却没有释放回内核，一开始怀疑是内存泄漏，后面上了工具排查，最终定位到是 glibc 的内存管理并没有将内存释放给OS，为了解决这个问题，对 ptmalloc2 进行了剖析。

本篇中，不谈论 brk 和 mmap 系统调用的使用方法，默认环境为 Linux-x86-64，讨论的 ptmalloc2 的版本为 glibc 2.17 的版本。

chunk

ptmalloc2 分配给用户的内存都以 chunk 来表示，可以理解为 chunk 为分配释放内存的载体。

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

#ifndef INTERNAL_SIZE_T
#define INTERNAL_SIZE_T size_t
#endif

/* The corresponding word size */
#define SIZE_SZ                (sizeof(INTERNAL_SIZE_T))

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */
// -----------------------------------------------------------------------
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

chunk 由以上几部分组成， INTERNAL_SIZE_T 为 size_t 为了屏蔽平台之间的差异，这里只谈论64位平台，为8字节。

1. prev_size 代表着上一个 chunk 的大小，是否有效取决于 size 的属性位 P。
2. size 代表当前 chunk 的大小和属性，其中低3位为属性位 [A|M|P]。
3. 当这个 chunk 为空闲时，则会使用 fd, bk 将其加入链表中管理。
4. 同上， fd_nextsize bk_nextsize 只用在 large bin 中，表示 上/下一个大小的指针，加快链表遍历。

最近接手的一个游戏项目是重 Lua 的结构（网络模块在 C++，其余逻辑全在 Lua）。和许多用 Lua 的游戏项目一样，遇到了 Lua 的垃圾回收的性能问题，经常跑着跑着就会掉帧，因此花了一周的时间，给 Lua 虚拟机写了个模块，把 Lua 垃圾回收的速度提高了一个量级。

思路

这个思路其实在之前的一篇博客中也有提到，想要 垃圾回收快，无非就那么几种思路。

1. 使用内存池
2. 减少对象生成
3. 垃圾回收提速

使用内存池

第一种思路，我觉得不合理，因为现代的内存分配器早就有内存池的设计了，手写一个内存池的收益并不大。

减少对象生成

第二种思路，是比较合理的。因为我在项目的代码中发现很多处地方有动态生成 Closure 的情况。

1
2
3
4
5
6
7

function test()
  local fn = function()
    print("test")
  end
  fn()
  fn()
end

上面那个例子，每次调用到 test 函数的时候，都会动态根据 fn 的 函数原型，生成一个 Closure

可能有人会问，Proto 不是有一个 cache 指向 Closure 吗？按道理这里 没有 UpValue（即代表UpValue 完全相同），应该会复用啊，但是很可惜，执行完这个函数以后，因为没有对象指向 Closure 用完再不久的将来又会被回收。

因此，少写这种代码就可以减少对象的生成。

垃圾回收提速

第三种思路，我的想法是，让垃圾回收所要遍历的对象大幅减少，就可以为垃圾回收提速了，由于我们是重 Lua 的框架，因此我们的所有配置都存在于 Lua 的 table中，而这一部分肯定是不需要被回收的，但是每次垃圾回收的时候，又会不停的扫描递归遍历，不合理。同时代码中的很多全局函数，也是根本不需要被回收的，也会被扫描到，于是就想到一个想法，给这些对象打上标记，让他们不被遍历不被清理，就可以大幅度的提速了。

原理简单，但是做起来确实挺难受的，要注意要手动关闭 UpValue 将其保留下来。

目前已经开源，LuaJIT-5.3.6源码。

游戏服务端之所以用 Lua，大多数时候是因为 Lua 方便做热更新，一般来说对 Lua 做热更新基本上都会使用以下两句语句。

1
2

package.loaded[name] = nil
require(name)

这种方式的热更好处就是简单，不过有的代码写起来就要特别小心，当你在代码中看到以下类似的片段，很有可能是为了热更新做的一种妥协。

1

Activity.c2sFun = Activity.c2sFun or {};

同时，如果 Lua 代码中存有大量的 upvalue 时，还要记得保存原有的状态信息，否则会丢失原值，对于开发人员来说，这种热更方式费心费力。

因此， Lua HotFix 就是为了摆脱以上的限制，或者说减少需要关心的事情，让开发人员能够更为简单的做热更新。之所以要自己写这么一套东西，主要是因为网络上开源的热更方案不适合项目，要么支持的Lua版本过旧，要么就约束的过多，项目已经进行到了中后期，这个时候再来规范已经来不及了，其次有很多的错误，这点我会在本文中的第二部分进行讨论。

本文主要分为两个部分，第一部分为 HotFix 实现，第二部分为热更新的错误案例。

虽然本系列主要讲的是 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 在某个 排行榜 上的 排名, 及展示信息
• 获取 一个排行榜 任意区间(例如排名区间) 的展示信息

排行榜排序方案

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

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

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