cpython 子解释器并行实现

https://github.com/ericsnowcurrently/multi-core-python
multi-core-python 项目 提出,可以通过基于隔离子解释器的状态,让子解释器可以并行执行,实现在一个进程内真正的并行执行python代码。

目前multi-core-python距离完成实现还有很长的距离, 估计在python3是不会问世了(因为改法的兼容性问题),我们基于multi-core-python项目的思路,自行实现了子解释器并行。

我们对cpython代码主要做了以下改动:

  1. 解释器隔离
  2. sub interperter 能力补全
  3. 虚拟机的对象共享
  4. 实现子解释器池
  5. 实现调度模块

overview.png

cpython痛, GIL

cpython是python官方的解释器实现。在cpython中,GIL,用于保护对Python对象的访问,从而防止多个线程同时执行Python字节码。GIL防止出现竞争情况并确保线程安全。
因为GIL的存在,cpython 是无法真正的并行执行python字节码的. GIL虽然限制了python的并行,但是因为cpython的代码没有考虑到并行执行的场景,充满着各种各样的共享变量,改动复杂度太高,官方一直没有移除GIL。

解释器隔离

换种思路,我们不移除GIL,而是每个解释器持有自己独立的GIL,这样就避免移除GIL所带来的改动。如果解释器执行时不相互影响,就可以并行执行了。

共享变量的隔离

解释器执行中使用了很多共享的变量,他们普遍以全局变量的形式存在.多个解释器运行时,会同时对这些共享变量进行读写操作,线程不安全。
我们梳理了cpython内部的主要共享变量:

  • free lists (bpo-40521):
    • MemoryError
    • asynchronous generator
    • context
    • dict
    • float
    • frame
    • list
    • slice
  • singletons
    • small integer ([-5; 256] range) (bpo-38858)
    • empty bytes string singleton
    • empty Unicode string singleton
    • empty tuple singleton
    • single byte character (b’\x00’ to b’\xFF’)
    • single Unicode character (U+0000-U+00FF range)
  • cache
    • slide cache
    • method cache
    • bigint cache
  • interned strings
  • PyUnicode_FromId static strings

如何让每个解释器独有这些变量呢?

cpython是c语言实现的,在c中,我们一般会通过 参数中传递 interpreter_state 结构体指针来保存属于一个解释器的成员变量。这种改法也是性能上最好的改法。但是如果这样改,那么所有使用interpreter_state的函数都需要修改函数签名。从工程角度上是几乎无法实现的。

只能换种方法,我们可以将interpreter_state存放到thread specific data中。interpreter执行时,通过thread specific key获取到 interpreter_state.这样就可以通过thread specific的API,获取到执行状态,并且不用修改函数的签名。

1
2
3
4
5
6
7
static inline PyInterpreterState* _PyInterpreterState_GET(void) {
PyThreadState *tstate = _PyThreadState_GET();
#ifdef Py_DEBUG
_Py_EnsureTstateNotNULL(tstate);
#endif
return tstate->interp;
}

变量隔离
我们将所有的共享变量存放到 interpreter_state里。

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
    /* Small integers are preallocated in this array so that they
can be shared.
The integers that are preallocated are those in the range
-_PY_NSMALLNEGINTS (inclusive) to _PY_NSMALLPOSINTS (not inclusive).
*/
PyLongObject* small_ints[_PY_NSMALLNEGINTS + _PY_NSMALLPOSINTS];
struct _Py_bytes_state bytes;
struct _Py_unicode_state unicode;
struct _Py_float_state float_state;
/* Using a cache is very effective since typically only a single slice is
created and then deleted again. */
PySliceObject *slice_cache;

struct _Py_tuple_state tuple;
struct _Py_list_state list;
struct _Py_dict_state dict_state;
struct _Py_frame_state frame;
struct _Py_async_gen_state async_gen;
struct _Py_context_state context;
struct _Py_exc_state exc_state;

struct ast_state ast;
struct type_cache type_cache;
#ifndef PY_NO_SHORT_FLOAT_REPR
struct _PyDtoa_Bigint *dtoa_freelist[_PyDtoa_Kmax + 1];
#endif
#if BD_DXP
struct _BD_Py_dxp_state dxp_state;
#endif

通过 _PyInterpreterState_GET 快速访问。
例如

1
2
3
4
5
6
struct _BD_Py_dxp_state *
get_dxp_state(void)
{
PyInterpreterState *is = _PyInterpreterState_GET();
return &is->dxp_state;
}

注意,将全局变量改为thread specific data是有性能影响的,不过只要控制该API调用的次数,性能影响还是可以接受的。具体thread specific data是怎么实现的,可以参考我的另一篇文章《iOS ARM64 __thread 线程本地存储的实现原理分析》https://tech.bytedance.net/articles/6931246803824148494

问题,API兼容性

Type变量
目前cpython3.x 暴露了PyType_xxx 类型变量在API中。这些全局类型变量被第三方扩展代码以&PyType_xxx的方式引用。如果将Type隔离到子解释器中,势必造成不兼容的问题。这也是官方改动停滞的原因,这个问题无法以合理改动的方式出现在python3中。只能等到python4修改API之后改掉。

我们通过另外一种方式快速的改掉了这个问题,从代码实现上看是比较丑陋的。

Type共享变量会导致以下的问题

  1. Type Object的 Ref count被频繁修改,线程不安全
  2. Type Object 成员变量被修改,线程不安全

改法:

  1. immortal type object. 设置Type Object的 Ref count = UINT_MAX.
  2. 使用频率低的不安全处加锁。
  3. 高频使用的场景,使用的成员变量设置为immortal object.

sub interperter 能力补全

官方master最新代码 subinterpreter 模块只提供了interp_run_string可以执行code_string. 出于体积和安全方面的考虑,我们已经删除了python动态执行code_string的功能。
我们给subinterpreter模块添加了两个额外的能力

  1. interp_call_file 调用执行任意加密后的python pyc文件
  2. interp_call_function 执行任意函数

subinterpreter 执行模型

python中,我们执行代码默认运行的是main interpreter, 我们也可以创建的sub interpreter执行代码,

1
2
interp = _xxsubinterpreters.create()
result = _xxsubinterpreters.interp_call_function(*args, **kwargs)

这里值得注意的是,我们是在 main interpreter 创建 sub interpreter, 随后在sub interpreter 执行,最后把结果返回到main interpreter. 这里看似简单,但是做了很多事情。

  1. main interpreter 将参数传递到 sub interpreter
  2. 线程切换到 sub interpreter的 interpreter_state。获取并转换参数
  3. sub interpreter 解释执行代码
  4. 获取返回值,切换到main interpreter
  5. 转换返回值
  6. 异常处理

这里有两个复杂的地方:

  1. interpreter state 状态的切换
  2. interpreter 数据的传递

interpreter state 状态的切换

1
2
interp = _xxsubinterpreters.create()
result = _xxsubinterpreters.interp_call_function(*args, **kwargs)

我们可以分解为

1
2
3
4
5
6
7
8
9
10
11
12
13
# Running In thread 11:
# main interpreter:
# 现在 thread specific 设置的 interpreter state 是 main interpreter的
do some things ...
create subinterpreter ...
interp_call_function ...
# thread specific 设置 interpreter state 为 sub interpreter state
# sub interpreter:
do some thins ...
call function ...
get result ...
# 现在 thread specific 设置d interpreter state 为 main interpreter state
get return result ...

interpreter 数据的传递

因为我们解释器的执行状态是隔离的,在main interpreter 中创建的 Python Object是无法在 sub interpreter 使用的.
我们需要:

  1. 获取 main interpreter 的 PyObject 关键数据
  2. 存放在 一块内存中
  3. 在sub interpreter 中根据该数据重新创建 PyObject

interpreter 状态的切换 & 数据的传递 的实现可以参考以下示例 …

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
static PyObject *
_call_function_in_interpreter(PyObject *self, PyInterpreterState *interp, _sharedns *args_shared, _sharedns *kwargs_shared)
{
PyObject *result = NULL;
PyObject *exctype = NULL;
PyObject *excval = NULL;
PyObject *tb = NULL;
_sharedns *result_shread = _sharedns_new(1);

#ifdef EXPERIMENTAL_ISOLATED_SUBINTERPRETERS
// Switch to interpreter.
PyThreadState *new_tstate = PyInterpreterState_ThreadHead(interp);
PyThreadState *save1 = PyEval_SaveThread();

(void)PyThreadState_Swap(new_tstate);
#else
// Switch to interpreter.
PyThreadState *save_tstate = NULL;
if (interp != PyInterpreterState_Get()) {
// XXX Using the "head" thread isn't strictly correct.
PyThreadState *tstate = PyInterpreterState_ThreadHead(interp);
// XXX Possible GILState issues?
save_tstate = PyThreadState_Swap(tstate);
}
#endif

PyObject *module_name = _PyCrossInterpreterData_NewObject(&args_shared->items[0].data);
PyObject *function_name = _PyCrossInterpreterData_NewObject(&args_shared->items[1].data);

...

PyObject *module = PyImport_ImportModule(PyUnicode_AsUTF8(module_name));
PyObject *function = PyObject_GetAttr(module, function_name);

result = PyObject_Call(function, args, kwargs);

...

#ifdef EXPERIMENTAL_ISOLATED_SUBINTERPRETERS
// Switch back.
PyEval_RestoreThread(save1);
#else
// Switch back.
if (save_tstate != NULL) {
PyThreadState_Swap(save_tstate);
}
#endif

if (result) {
result = _PyCrossInterpreterData_NewObject(&result_shread->items[0].data);
_sharedns_free(result_shread);
}

return result;
}

实现子解释器池

我们已经实现了内部的隔离执行环境,但是这是API比较低级,需要封装一些高度抽象的API,提高子解释器并行的易用能力。

1
2
interp = _xxsubinterpreters.create()
result = _xxsubinterpreters.interp_call_function(*args, **kwargs)

这里我们参考了,python concurrent库提供的 thread pool, process pool, futures的实现,自己实现了 subinterpreter pool. 通过concurrent.futures 模块提供异步执行回调高层接口。

1
2
3
4
executer = concurrent.futures.SubInterpreterPoolExecutor(max_workers)
future = executer.submit(_xxsubinterpreters.call_function, module_name, func_name, *args, **kwargs)
future.context = context
future.add_done_callback(executeDoneCallBack)

我们内部是这样实现的:
继承 concurrent 提供的 Executor 基类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SubInterpreterPoolExecutor(_base.Executor):

# SubInterpreterPool 初始化时创建线程,并且每个线程创建一个 sub interpreter

interp = _xxsubinterpreters.create()
t = threading.Thread(name=thread_name, target=_worker,
args=(interp,
weakref.ref(self, weakref_cb),
self._work_queue,
self._initializer,
self._initargs))

# 线程 worker 接收参数,并使用 interp 执行

result = self.fn(self.interp ,*self.args, **self.kwargs)

实现外部调度模块

针对sub interpreter的改动较大,存在两个隐患

  1. 代码可能存在兼容性问题,Python 提供了许多控制执行状态的CAPI给第三方库使用,sub interpreter有些API是不兼容的
  2. python存在着极少的一些模块.sub interpreter无法使用。例如process

我们希望能统一对外的接口,让使用者不需要关注这些细节,我们自动的切换调用方式。自动选择在主解释器使用(兼容性好,稳定)还是子解释器(支持并行,性能佳)

在dispatch.py 中,抽象了调用方式,提供统一的执行接口,统一处理异常和返回结果。
dispatch.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def executeFunc(module_name, func_name, context=None, use_main_interp=True, *args, **kwargs):
print("submit call ", module_name, ".", func_name)
if use_main_interp == True:
result = None
exception = None
try:
m = __import__(module_name)
f = getattr(m, func_name)
r = f(*args, **kwargs)
result = r
except:
exception = traceback.format_exc()
singletonExecutorCallback(result, exception, context)

else:
future = singletonExecutor.submit(_xxsubinterpreters.call_function, module_name, func_name, *args, **kwargs)
future.context = context
future.add_done_callback(executeDoneCallBack)


def executeDoneCallBack(future):
r = future.result()
e = future.exception()
singletonExecutorCallback(r, e, future.context)

改造结果

  • 我们对sub interpreter的改动目前已经跑过了官方的单元测试.
  • 相关的一些改动观点已经提交issue
  • 部分改动已经合入官方Master分支

Enjoy it, Parallel python execution.

cpython项目软件工程

开发者文档 Python Developer’s Guide

Python 给cpython虚拟机的开发者提供了详尽的文档。具体内容很多,可以直接查阅 https://devguide.python.org/。这里想说一下,国内公司的项目(我维护过的淘宝的字节的)和cpython相比有哪些可以补足的地方。

cpython的文档主要包含了

  • 如何快速运行项目
  • 在哪里提问和获取帮助
  • 如何编写和使用单元测试
  • 如何使用和编写Python的帮助文档
  • 如何提交解决协作问题
  • 版本管理和发布
  • 持续基础
  • 如何新增功能
  • 核心模块的设计文档
  • 如何调试cpython
  • 开发辅助工具的使用

因为完善的文档和协作机制,cpython在20多年的生命周期内不断迭代发展。我也是根据这些文档,很快完成了第一次pull request,合入cpython仓库

  1. 缺乏如何把项目Quick Start
    代码在哪?在哪里开发?代码提交流程?

  2. 缺乏版本管理的概念
    对外提供哪些版本?在哪些分支开发?各个版本的兼容性?

  3. 文档缺失
    主要模块设计,项目结构介绍

  4. 项目开发技巧工具介绍
    开发这个项目会用到哪些工具?有哪些开发规范和调试技巧

未完。。。

behind __thread. __thread实现原理

最近在改造cpython的时候大量使用了thread local storage, 有 pthread_setspecific__thread两种使用方式,pthread_setspecific是一个函数调用,比较容易理解,__thread就有意思了,他是怎么在编译之后,运行时不同线程使用不同的地址呢。搜了一圈,没有iOS下实现原理的相关文章,于是自己研究了一下__thread的实现原理,这里分享一下。

__thread的实现还是比较复杂的,涉及到编译器、动态链接、arm汇编的相关知识。这里我会从自己反编译和源码分析的角度一窥究竟。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
__thread int tlv_v1 = 0;
__thread int tlv_v2 = 0;
__thread int tlv_v3 = 0;
__thread int tlv_v4 = 4;

// 使用所有变量 防止被编译优化
tlv_v1 = tlv_v1 + 1;
tlv_v2 = tlv_v2 + 1;
tlv_v3 = tlv_v3 + 1;
tlv_v4 = tlv_v4 + 1;

printf("%d\n", tlv_v1);
printf("%p\n", &tlv_v1);

dispatch_async(dispatch_get_global_queue(0, 0), ^{
tlv_v1 = tlv_v1 + 1;
printf("%d\n", tlv_v1);
printf("%p\n", &tlv_v1);
});

编译, 通过hopper查看反编译后的代码

  1. 调用 __tlv_bootstrap 获取 variable 的地址
  2. 读取内容
1
2
3
4
5
6
7
8
0000000100006264         adrp       x0, #0x10000d000                            ; 0x10000d4d0@PAGE
0000000100006268 add x0, x0, #0x4d0 ; 0x10000d4d0@PAGEOFF, _tlv_v1
000000010000626c ldr x8, [x0] ; _tlv_v1,__tlv_bootstrap
0000000100006270 blr x8
0000000100006274 mov x19, x0
0000000100006278 ldr w8, [x0] ; _tlv_v1
000000010000627c add w8, w8, #0x2
0000000100006280 str w8, [x0] ; _tlv_v1

来看看 __tlv_bootstrap 是什么
找了一下dyld的代码, 好吧 原来就是站位的,没什么用处。

1
2
3
4
5
// linked images with TLV have references to this symbol, but it is never used at runtime
void _tlv_bootstrap()
{
abort();
}

随后看了一下相关的代码,发现 tlv_initialize_descriptors会对 _tlv_v1做相应的处理

tlv_allocate_and_initialize_for_key 通过注册到dyld在 动态库加载时进行调用. 主要做以下事情

  1. d->thunk = tlv_get_addr; // 把原来的__tlv_bootstrap 换成 tlv_get_addr
  2. 注册mh到tlv_live_images列表中
  3. 隐式的设置offset
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
void* tlv_allocate_and_initialize_for_key(pthread_key_t key)
{
// ...
for (const macho_section* sect=sectionsStart; sect < sectionsEnd; ++sect) {
if ( (sect->flags & SECTION_TYPE) == S_THREAD_LOCAL_VARIABLES ) {
if ( sect->size != 0 ) {
// allocate pthread key when we first discover this image has TLVs
if ( key == 0 ) {
int result = pthread_key_create(&key, &tlv_free);
if ( result != 0 )
abort();
tlv_set_key_for_image(mh, key);
}
// initialize each descriptor
TLVDescriptor* start = (TLVDescriptor*)(sect->addr + slide);
TLVDescriptor* end = (TLVDescriptor*)(sect->addr + sect->size + slide);
for (TLVDescriptor* d=start; d < end; ++d) {
d->thunk = tlv_get_addr; // 把原来的__tlv_bootstrap 换成 tlv_get_addr
d->key = key;
//d->offset = d->offset; // offset 在macho中已经写入
}
}
}
}
// ...
}

static void tlv_set_key_for_image(const struct mach_header* mh, pthread_key_t key)
{
pthread_mutex_lock(&tlv_live_image_lock);
if ( tlv_live_image_used_count == tlv_live_image_alloc_count ) {
unsigned int newCount = (tlv_live_images == NULL) ? 8 : 2*tlv_live_image_alloc_count;
struct TLVImageInfo* newBuffer = malloc(sizeof(TLVImageInfo)*newCount);
if ( tlv_live_images != NULL ) {
memcpy(newBuffer, tlv_live_images, sizeof(TLVImageInfo)*tlv_live_image_used_count);
free(tlv_live_images);
}
tlv_live_images = newBuffer;
tlv_live_image_alloc_count = newCount;
}
tlv_live_images[tlv_live_image_used_count].key = key;
tlv_live_images[tlv_live_image_used_count].mh = mh;
++tlv_live_image_used_count;
pthread_mutex_unlock(&tlv_live_image_lock);
}

_tlv_v1 在 S_THREAD_LOCAL_VARIABLES section. 结合TLVDescriptor可以发现

  • thunk = __tlv_bootstrap
  • offset = 0x04
1
2
3
4
5
6
struct TLVDescriptor
{
void* (*thunk)(struct TLVDescriptor*);
unsigned long key;
unsigned long offset;
};
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
        ; Section __thread_vars
; Range: [0x10000d4d0; 0x10000d530[ (96 bytes)
; File offset : [54480; 54576[ (96 bytes)
; Flags: 0x13
; S_THREAD_LOCAL_VARIABLES

_tlv_v1:
000000010000d4d0 extern __tlv_bootstrap

000000010000d4d8 db 0x00 ; '.'
000000010000d4d9 db 0x00 ; '.'
000000010000d4da db 0x00 ; '.'
000000010000d4db db 0x00 ; '.'
000000010000d4dc db 0x00 ; '.'
000000010000d4dd db 0x00 ; '.'
000000010000d4de db 0x00 ; '.'
000000010000d4df db 0x00 ; '.'

000000010000d4e0 db 0x04 ; '.' //offset
000000010000d4e1 db 0x00 ; '.'
000000010000d4e2 db 0x00 ; '.'
000000010000d4e3 db 0x00 ; '.'
000000010000d4e4 db 0x00 ; '.'
000000010000d4e5 db 0x00 ; '.'
000000010000d4e6 db 0x00 ; '.'
000000010000d4e7 db 0x00 ; '.'

现在关注一下 tlv_get_addr 的实现,这个是最关键的实现,涉及到不同的thread 如何获取线程对应的变量地址

_tlv_get_addr 会根据key、TPIDRRO_EL0、和offset来计算出 __thread variable的真正存储地址
LlazyAllocate 会根据在不同的线程分配buffer用来存储__thread variable. 这个实现在 _tlv_allocate_and_initialize_for_key

这里有一段非常疑惑的代码,怎么就几行汇编指令就找到 thread allocation的地址了呢, 而且看注释,感觉写这段代码的本人也没看懂。。

这里我想了很久,貌似没有什么关联。于是看了一下xnu里 TPIDRRO_EL0 相关的代码,libpthread pthread_setspecific的代码, 最终发现 之所以这样找是和 pthread_setspecific的代码有关。

1
2
3
4
5
6
7
8
9
10
11
12
13
_tlv_get_addr:
#if __LP64__
ldr x16, [x0, #8] // get key from descriptor
#else
ldr w16, [x0, #4] // get key from descriptor
#endif
mrs x17, TPIDRRO_EL0
and x17, x17, #-8 // clear low 3 bits??? :):这里加了个注释是自己也没看懂吗。。。
#if __LP64__
ldr x17, [x17, x16, lsl #3] // get thread allocation address for this key
#else
ldr w17, [x17, x16, lsl #2] // get thread allocation address for this key
#endif

pthread_setspecific 会把value 放到thread->tsd里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static inline int
_pthread_setspecific(pthread_t thread, pthread_key_t key, const void *value)
{
int res = EINVAL;

if (key >= __pthread_tsd_first && key < __pthread_tsd_end) {
bool created = _pthread_key_get_destructor(key, NULL);
if (key < __pthread_tsd_start || created) {
thread->tsd[key] = (void *)value;
res = 0;

if (key < __pthread_tsd_start) {
// XXX: is this really necessary?
_pthread_key_set_destructor(key, NULL);
}
if (key > thread->max_tsd_key) {
thread->max_tsd_key = (uint16_t)key;
}
}
}

return res;
}

在xnu代码中发现 thread tsd 可以通过 以下汇编的操作快速获得。这个等价于

1
2
mrs		x17, TPIDRRO_EL0
and x17, x17, #-8 // clear low 3 bits???
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
__attribute__((always_inline, pure))
static __inline__ void**
_os_tsd_get_base(void)
{
#if defined(__arm__)
uintptr_t tsd;
__asm__("mrc p15, 0, %0, c13, c0, 3\n"
"bic %0, %0, #0x3\n" : "=r" (tsd));
/* lower 2-bits contain CPU number */
#elif defined(__arm64__)
uint64_t tsd;
__asm__("mrs %0, TPIDRRO_EL0\n"
"bic %0, %0, #0x7\n" : "=r" (tsd));
/* lower 3-bits contain CPU number */
#endif

return (void**)(uintptr_t)tsd;
}

xnu里 machine_thread_set_tsd_base 会把 TPIDRRO_EL0 的值设置为 tsd_base | cpunum. 由于设置了cpunum 在后三bit。因此我们需要清0,在能计算出 tsd_base.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
kern_return_t
machine_thread_set_tsd_base(thread_t thread,
mach_vm_offset_t tsd_base)
{
// ...
thread->machine.cthread_self = tsd_base;

/* For current thread, make the TSD base active immediately */
if (thread == current_thread()) {
uint64_t cpunum, tpidrro_el0;

mp_disable_preemption();
tpidrro_el0 = get_tpidrro();
cpunum = tpidrro_el0 & (MACHDEP_CPUNUM_MASK);
set_tpidrro(tsd_base | cpunum);
mp_enable_preemption();
}

return KERN_SUCCESS;
}

拿到tsd之后, x16:key 左移3位得到tsd数组的offset, 计算出 thread allocation address.

1
2
//x17: tsd
ldr x17, [x17, x16, lsl #3]
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
_tlv_get_addr:
#if __LP64__
ldr x16, [x0, #8] // get key from descriptor
#else
ldr w16, [x0, #4] // get key from descriptor
#endif
mrs x17, TPIDRRO_EL0
and x17, x17, #-8 // clear low 3 bits???
#if __LP64__
ldr x17, [x17, x16, lsl #3] // get thread allocation address for this key
#else
ldr w17, [x17, x16, lsl #2] // get thread allocation address for this key
#endif
cbz x17, LlazyAllocate // if NULL, lazily allocate
#if __LP64__
ldr x16, [x0, #16] // get offset from descriptor
#else
ldr w16, [x0, #8] // get offset from descriptor
#endif
add x0, x17, x16 // return allocation+offset
ret lr

LlazyAllocate:
stp fp, lr, [sp, #-16]!
mov fp, sp
sub sp, sp, #288
stp x1, x2, [sp, #-16]! // save all registers that C function might trash
stp x3, x4, [sp, #-16]!
stp x5, x6, [sp, #-16]!
stp x7, x8, [sp, #-16]!
stp x9, x10, [sp, #-16]!
stp x11, x12, [sp, #-16]!
stp x13, x14, [sp, #-16]!
stp x15, x16, [sp, #-16]!
stp q0, q1, [sp, #-32]!
stp q2, q3, [sp, #-32]!
stp q4, q5, [sp, #-32]!
stp q6, q7, [sp, #-32]!
stp x0, x17, [sp, #-16]! // save descriptor

mov x0, x16 // use key from descriptor as parameter
bl _tlv_allocate_and_initialize_for_key
ldp x16, x17, [sp], #16 // pop descriptor
#if __LP64__
ldr x16, [x16, #16] // get offset from descriptor
#else
ldr w16, [x16, #8] // get offset from descriptor
#endif
add x0, x0, x16 // return allocation+offset

ldp q6, q7, [sp], #32
ldp q4, q5, [sp], #32
ldp q2, q3, [sp], #32
ldp q0, q1, [sp], #32
ldp x15, x16, [sp], #16
ldp x13, x14, [sp], #16
ldp x11, x12, [sp], #16
ldp x9, x10, [sp], #16
ldp x7, x8, [sp], #16
ldp x5, x6, [sp], #16
ldp x3, x4, [sp], #16
ldp x1, x2, [sp], #16

mov sp, fp
ldp fp, lr, [sp], #16
ret lr

#endif

可以看到,我们访问__thread variable 总共使用了11条指令。其性能还是非常快的。
对比使用 pthread_getspecific要快20%.

到目前为止,我们已经探明了__thread实现机制的主要原理,还有S_THREAD_LOCAL_INIT_FUNCTION_POINTERS数据端存储的内容是如何使用的就不再赘述,感兴趣的同学可以自行阅读一下。

Section Name 作用
S_THREAD_LOCAL_VARIABLES Section with thread local variable structure data.
S_THREAD_LOCAL_REGULAR Thread local data section.
S_THREAD_LOCAL_ZEROFILL Thread local zerofill section.
S_THREAD_LOCAL_INIT_FUNCTION_POINTERS Section with thread local variable initialization pointers to functions.

相关资料:
https://github.com/apple/darwin-libpthread
https://courses.cs.washington.edu/courses/cse469/19wi/arm64.pdf
https://github.com/apple-open-source-mirror/dyld/blob/f08acb406794f8168bbc5d39bdef3ca9186a8fc1/src/threadLocalHelpers.s#L239
https://github.com/apple/darwin-xnu

cpython mutilcore 实现

最近给公司内部的cpython实现了一个进程内同时运行多个虚拟机实例的方案(基于3.8版本)(为啥要自己改?tmd3.8版本没有啊,要吃饭啊)。最近看到开源在master分支也有相应的实现,预计在今年10月合入3.10版本,review了一下代码对照了一下改法,这里总结下异同。这里就不单独分享我实现的了,主要实现思路都一样。

Cpython opensource 3.10 SubInterpreter 并行提交review

cpython已经改动完成的

  • https://github.com/ericsnowcurrently/multi-core-python/

  • bpo-36476: Runtime finalization assumes all other threads have exited

  • bpo-1635741: Py_Finalize() doesn’t clear all Python objects at exit created in 2007

  • LWN: Subinterpreters for Python (May 13, 2020) By Jake Edge

  • Multiphase: 64% (76/118). At 2020-10-06, 76 extensions on a total of 118 use the new multi-phase initialization API. There are 42 remaining extensions using the old API (bpo-1635741).

    Diff: 我们的处理是模块只初始化一次,这块可以跟进改动优化一下

  • Heap types: 35% (69/200). At 2020-11-01, 69 types are defined as heap types on a total of 200 types. There are 131 remaining static types (bpo-40077).

    Diff: 我们的处理是共享Type使用,核心地方加锁,类型永远不释放,保证多线程安全。这块可以跟进改动优化一下

  • Per-interpreter free lists (bpo-40521):

    • MemoryError
    • asynchronous generator
    • context
    • dict
    • float
    • frame
    • list
    • slice
    • tuple

      Diff: 类似

  • Per-interpreter singletons (bpo-40521):

    • small integer ([-5; 256] range) (bpo-38858)
    • empty bytes string singleton
    • empty Unicode string singleton
    • empty tuple singleton
    • single byte character (b’\x00’ to b’\xFF’)
    • single Unicode character (U+0000-U+00FF range)
    • Note: the empty frozenset singleton has been removed.

      Diff: 类似

  • Per-interpreter slice cache (bpo-40521).

    Diff: 类似

  • Per-interpreter pending calls (bpo-39984).

    Diff: 没有处理,目前没使用该功能

  • Per-interpreter type attribute lookup cache (bpo-42745).

    Diff: 类似

  • Per-interpreter interned strings (bpo-40521).

    Diff: 我们直接禁用了interned string机制

  • Per-interpreter identifiers: _PyUnicode_FromId() (bpo-39465)

    Diff: 没有处理这块,因为基本上不会有并行的线程问题,概率较小。可以参考改动

  • Per-interpreter states:

    • ast (bpo-41796)
    • gc (bpo-36854)
    • parser (bpo-36876)
    • warnings (bpo-36737 and bpo-40521)

      Diff: 原理类似,都采用Pthread Specific Data

  • Fix crashes with daemon threads: https://vstinner.github.io/gil-bugfixes-daemon-threads-python39.html

  • Fix bugs related to heap types:

    • Fix the traverse function of heap types for GC collection (bpo-40217, bpo-40149)
    • Fix pickling heap types implemented in C with protocols 0 and 1 (bpo-41052)
      Milestones
  • May 2020: PoC: Subinterpreters 4x faster than sequential execution or threads on CPU-bound workaround

  • Open Questions
    Thread local variable for tstate and interp?
    If multiple interpreters can run in parallel, _PyThreadState_GET() and _PyInterpreterState_GET() must be able to get the Python thread state and intepreter of the current thread in an efficient way.
    pthread_getspecific() is a function call: may slow down Python. GCC and clang have a __thread extension for thread local variable: use FS register on x86-64.

    Diff: 一样都 使用Thread Specific Data

    Allocate an unique index per interperter
    _PyUnicode_FromId(): https://bugs.python.org/issue39465 fix adds an array per interpreter. The first _PyUnicode_FromId() call assigns an unique identifier (unique for the whole process, shared by all intepreters) to the identifier and the value is stored in the array.
    The question is how to get and set the index in an efficient way.
    An alternative is to use the identifier memory address as a key and use an hash table to store identifier values.

    Diff: 引入C++ Vector持有每个线程的 _Runtime

    cpython还没改完的

    TODO list for per-interpreter GIL

    实现类似

    Search for Subinterpreters issues at bugs.python.org.
    Meta issue: per-interpreter GIL.
    Effects of the EXPERIMENTAL_ISOLATED_SUBINTERPRETERS macro:

  • Good things!

    • Per-interpreter GIL!!!
    • Use a TSS to get the current Python thread state (‘tstate’)
    • _xxsubinterpreters.run_string() releases the GIL to run a subinterprer
  • Bad things :-( (mostly workarounds waiting for a real fix)

    • Disable pymalloc in preconfig.c: force malloc (or malloc_debug) allocator.

      Diff: More: pymalloc适配即可

    • Don’t run GC collections in subinterpreters (see gc_collect_main).

      Diff: More:每个虚拟机持有GC即可

      Issues:
  • Make the PyGILState API compatible with subinterpreters

  • parser_init(): _PyArg_Parser

  • None, True, False, Ellipsis singletons: https://bugs.python.org/issue39511

  • Heap types

  • bpo-40533: Temporary workaround: make PyObject.ob_refcnt atomic in subinterpreters: https://github.com/python/cpython/pull/19958

  • tstate: get/set TSS: https://bugs.python.org/issue40522
    Enhancements:

  • Debug: ensure that an object is not accessed by two interpreters: https://bugs.python.org/issue33607

  • _xxsubinterpreters.run_string(): release the GIL: https://github.com/python/cpython/commit/fb2c7c4afbab0514352ab0246b0c0cc85d1bba53

  • subprocess: close_fds=False, posix_spawn() is safe in subinterpreters
    Limitations
    Not supported in subinterpreter:

  • os.fork(): it may be possible to fix it.

  • signal.signal()

  • static types
    Current workarounds:

  • Disable GC

    Diff: More:每个虚拟机持有GC即可

  • Disable many caches like frame free list

clang添加命令行参数

clang 怎么处理 options

  1. Options.td 定义参数描述
  2. tablegen 生成 Options.inc
  3. #include "clang/Driver/Options.inc"

我们添加的参数在compiler-front-end使用
// CC1Option - This option should be accepted by clang -cc1.
def CC1Option : OptionFlag;

不带参数的flag

1
2
3
def custom_option1 : Flag <["-"], "custom_option1">, Group<f_Group>,
Flags<[CC1Option]>,
HelpText<"custom_option1">;

带参数的flag

1
2
3
def custom_option2 : JoinedOrSeparate<["-"], "custom_option2">, Group<I_Group>,
Flags<[CC1Option]>, MetaVarName<"<name>">,
HelpText<"custom_option2">;

多个相同option时 可以使用getAllArgValues获取所有参数值
Args.getAllArgValues(OPT_custom_option2)

使用getLastArgValue获取最后一个argvalue
Args.getLastArgValue(OPT_custom_option2)

修复ffi ios 14.2 crash

libffi 跳板原理介绍

最近libffi 在iOS14.2上发生了crash, 偶现,是vmremap页导致code sign error. 暂时通过使用静态trampoline的方式绕过了这个问题。这里就介绍一下相关的实现原理。

libffi 实现原理

高层语言的编译器生成遵循某些约定的代码。这些公约部分是单独汇编工作所必需的。“调用约定”本质上是编译器对函数入口处将在哪里找到函数参数的假设的一组假设。“调用约定”还指定函数的返回值在哪里找到。

一些程序在编译时可能不知道要传递给函数的参数。例如,在运行时,解释器可能会被告知用于调用给定函数的参数的数量和类型。Libffi可用于此类程序,以提供从解释器程序到编译代码的桥梁。

libffi库为各种调用约定提供了一个便携式、高级的编程接口。这允许程序员在运行时调用调用接口描述指定的任何函数。

ffi的使用

简单的找了一个使用ffi的库看一下他的调用接口

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
ffi_type *returnType = st_ffiTypeWithType(self.signature.returnType);
NSAssert(returnType, @"can't find a ffi_type of %@", self.signature.returnType);

NSUInteger argumentCount = self->_argsCount;
_args = malloc(sizeof(ffi_type *) * argumentCount) ;

for (int i = 0; i < argumentCount; i++) {
ffi_type* current_ffi_type = st_ffiTypeWithType(self.signature.argumentTypes[i]);
NSAssert(current_ffi_type, @"can't find a ffi_type of %@", self.signature.argumentTypes[i]);
_args[i] = current_ffi_type;
}

// 创建 ffi 跳板用到的 closure
_closure = ffi_closure_alloc(sizeof(ffi_closure), (void **)&xxx_func_ptr);

// 创建 cif,调用函数用到的参数和返回值的类型信息, 之后在调用时会结合call convention 处理参数和返回值
if(ffi_prep_cif(&_cif, FFI_DEFAULT_ABI, (unsigned int)argumentCount, returnType, _args) == FFI_OK) {

// closure 写入 跳板数据页
if (ffi_prep_closure_loc(_closure, &_cif, _st_ffi_function, (__bridge void *)(self), xxx_func_ptr) != FFI_OK) {
NSAssert(NO, @"genarate IMP failed");
}
} else {
NSAssert(NO, @"FUCK");
}

看完这段代码,大概能理解 ffi 的操作。

  1. 提供给外界一个指针(指向trampoline entry)
  2. 创建一个closure, 将调用相关的参数返回值信息放到closure里
  3. 将closure写入到trampoline 对应的trampoline data entry 处

之后我们调用 trampoline entry func ptr 时,

  1. 会找到 写入到 trampoline 对应的trampoline data entry 处的 closure 数据
  2. 根据closure 提供的调用参数和返回值信息,结合调用约定,操作寄存器和栈,写入参数 进行函数调用,获取返回值。

那ffi 是怎么找到 trampoline 对应的trampoline data entry 处的 closure 数据 呢?

我们从 ffi 分配 trampoline 开始说起:

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
static ffi_trampoline_table *
ffi_remap_trampoline_table_alloc (void)
{
.....
/* Allocate two pages -- a config page and a placeholder page */
config_page = 0x0;
kt = vm_allocate (mach_task_self (), &config_page, PAGE_MAX_SIZE * 2,
VM_FLAGS_ANYWHERE);
if (kt != KERN_SUCCESS)
return NULL;

/* Allocate two pages -- a config page and a placeholder page */
//bdffc_closure_trampoline_table_page

/* Remap the trampoline table on top of the placeholder page */
trampoline_page = config_page + PAGE_MAX_SIZE;
trampoline_page_template = (vm_address_t)&ffi_closure_remap_trampoline_table_page;
#ifdef __arm__
/* bdffc_closure_trampoline_table_page can be thumb-biased on some ARM archs */
trampoline_page_template &= ~1UL;
#endif
kt = vm_remap (mach_task_self (), &trampoline_page, PAGE_MAX_SIZE, 0x0,
VM_FLAGS_OVERWRITE, mach_task_self (), trampoline_page_template,
FALSE, &cur_prot, &max_prot, VM_INHERIT_SHARE);
if (kt != KERN_SUCCESS)
{
vm_deallocate (mach_task_self (), config_page, PAGE_MAX_SIZE * 2);
return NULL;
}


/* We have valid trampoline and config pages */
table = calloc (1, sizeof (ffi_trampoline_table));
table->free_count = FFI_REMAP_TRAMPOLINE_COUNT/2;
table->config_page = config_page;
table->trampoline_page = trampoline_page;

......
return table;
}

首先 ffi 在创建trampoline 时,
会分配两个连续的 page

trampoline page 会 remap 到我们事先在代码中汇编写的 ffi_closure_remap_trampoline_table_page。

其结构如图所示:

1
2
3
4
5
6
7
8
9
---------------------
- data page -
- closuer1 - <--
- - |
--------------------- |
- trampoline page - |
- entry1 -----
- -
---------------------

当我们 ffi_prep_closure_loc(_closure, &_cif, _st_ffi_function, (__bridge void *)(self), entry1)) 写入closure数据时, 会写入到 entry1 对应的 closuer1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ffi_status
ffi_prep_closure_loc (ffi_closure *closure,
ffi_cif* cif,
void (*fun)(ffi_cif*,void*,void**,void*),
void *user_data,
void *codeloc)
{
......

if (cif->flags & AARCH64_FLAG_ARG_V)
start = ffi_closure_SYSV_V; // ffi 对 closure的处理函数
else
start = ffi_closure_SYSV;

void **config = (void**)((uint8_t *)codeloc - PAGE_MAX_SIZE);
config[0] = closure;
config[1] = start;

......
}

这是怎么对应到的呢? closure1 和 entry1 距离其所属Page的offset是一致的,通过offset,成功建立 trampoline entry 和 trampoline closure 的对应关系。(熟悉hook的同学应该知道,怎么毫无副作用的将数据传递给hook func 是比较困难的事情)page offset的对应关系这个实现真的666.

现在我们知道这个关系,我们通过代码看一下到底在程序运行的时候 是怎么找到 closure 的。
这四条指令是我们trampoline entry的代码实现,就是 ffi 返回的 xxx_func_ptr

1
2
3
4
adr x16, -PAGE_MAX_SIZE 
ldp x17, x16, [x16]
br x16
nop

通过 .rept 我们创建 PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE 个跳板,刚好一个页的大小

1
2
3
4
5
6
7
8
9
10
# 动态remap的 page
.align PAGE_MAX_SHIFT
CNAME(ffi_closure_remap_trampoline_table_page):
.rept PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE
# 这是我们的 trampoline entry, 就是ffi生成的函数指针
adr x16, -PAGE_MAX_SIZE // 将pc地址减去PAGE_MAX_SIZE, 找到 trampoine data entry
ldp x17, x16, [x16] // 加载我们写入的 closure, start 到 x17, x16
br x16 // 跳转到 start 函数
nop /* each entry in the trampoline config page is 2*sizeof(void*) so the trampoline itself cannot be smaller that 16 bytes */
.endr

通过pc地址减去 PAGE_MAX_SIZE 就找到对应的 trampoline data entry了。

静态跳板的实现

由于代码段和数据段在不同的内存区域。
我们此时不能通过 像vmremap一样分配两个连续的PAGE,在寻找trampoline data entry只是简单的-PAGE_MAX_SIZE找到对应关系,需要稍微麻烦点的处理。

主要是通过adrp找到_ffi_static_trampoline_data_page1_ffi_static_trampoline_page1的起始地址,用pc-_ffi_static_trampoline_page1的起始地址计算offset,找到trampoline data entry。

静态分配的page

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
#ifdef __MACH__
#include <mach/machine/vm_param.h>

.align 14
.data
.global _ffi_static_trampoline_data_page1
_ffi_static_trampoline_data_page1:
.space PAGE_MAX_SIZE*5
.align PAGE_MAX_SHIFT
.text
CNAME(_ffi_static_trampoline_page1):

_ffi_local_forwarding_bridge:
adrp x17, ffi_closure_static_trampoline_table_page_start@PAGE;// text page
sub x16, x16, x17;// offset
adrp x17, _ffi_static_trampoline_data_page1@PAGE;// data page
add x16, x16, x17;// data address
ldp x17, x16, [x16];// x17 closure x16 start
br x16
nop
nop
.align PAGE_MAX_SHIFT
CNAME(ffi_closure_static_trampoline_table_page):

#这个label 用来adrp@PAGE 计算 trampoline 到 trampoline page的offset
#留了5个用来调试。
# 我们static trampoline 两条指令就够了,这里使用4个,和remap的保持一致
ffi_closure_static_trampoline_table_page_start:
adr x16, #0 // mv pc t0 x16
b _ffi_local_forwarding_bridge
nop
nop

adr x16, #0
b _ffi_local_forwarding_bridge
nop
nop

adr x16, #0
b _ffi_local_forwarding_bridge
nop
nop

adr x16, #0
b _ffi_local_forwarding_bridge
nop
nop

adr x16, #0
b _ffi_local_forwarding_bridge
nop
nop

// 5 * 4
.rept (PAGE_MAX_SIZE*5-5*4) / FFI_TRAMPOLINE_SIZE
adr x16, #0
b _ffi_local_forwarding_bridge
nop
nop
.endr

.globl CNAME(ffi_closure_static_trampoline_table_page)
FFI_HIDDEN(CNAME(ffi_closure_static_trampoline_table_page))
#ifdef __ELF__
.type CNAME(ffi_closure_static_trampoline_table_page), #function
.size CNAME(ffi_closure_static_trampoline_table_page), . - CNAME(ffi_closure_static_trampoline_table_page)
#endif
#endif

Patch

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
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
From 047d8c8f10368fe89362cb7afcd3a11a9e969f2c Mon Sep 17 00:00:00 2001
From: xiejunyi <xie.junyi@outlook.com>
Date: Fri, 20 Nov 2020 18:28:14 +0800
Subject: [PATCH] patch

---
Stinger/libffi/darwin_common/src/closures.c | 107 ++++++++++++++----
.../libffi/darwin_ios/src/aarch64/ffi_arm64.c | 18 ++-
.../darwin_ios/src/aarch64/sysv_arm64.S | 89 +++++++++++++--
.../libffi/darwin_ios/src/arm/sysv_armv7.S | 4 +-
4 files changed, 182 insertions(+), 36 deletions(-)

diff --git a/Stinger/libffi/darwin_common/src/closures.c b/Stinger/libffi/darwin_common/src/closures.c
index 4fe6158..ff39dae 100644
--- a/Stinger/libffi/darwin_common/src/closures.c
+++ b/Stinger/libffi/darwin_common/src/closures.c
@@ -153,14 +153,19 @@ ffi_closure_free (void *ptr)
#endif
#include <stdio.h>
#include <stdlib.h>
-
-extern void *ffi_closure_trampoline_table_page;
+extern void *ffi_closure_remap_trampoline_table_page;
+extern void *ffi_closure_static_trampoline_table_page;
+extern void *ffi_bridge_data_page1;

typedef struct ffi_trampoline_table ffi_trampoline_table;
typedef struct ffi_trampoline_table_entry ffi_trampoline_table_entry;

+#define FFI_STATIC_PAGE 0
+#define FFI_REMAP_PAGE 1
struct ffi_trampoline_table
{
+ // 0 static, 1 remap
+ uint64_t page_type;
/* contiguous writable and executable pages */
vm_address_t config_page;
vm_address_t trampoline_page;
@@ -172,6 +177,8 @@ struct ffi_trampoline_table

ffi_trampoline_table *prev;
ffi_trampoline_table *next;
+
+
};

struct ffi_trampoline_table_entry
@@ -181,71 +188,122 @@ struct ffi_trampoline_table_entry
};

/* Total number of trampolines that fit in one trampoline table */
-#define FFI_TRAMPOLINE_COUNT (PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE)
+#define FFI_STATIC_TRAMPOLINE_COUNT (PAGE_MAX_SIZE*5 / FFI_TRAMPOLINE_SIZE)
+#define FFI_REMAP_TRAMPOLINE_COUNT (PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE)

static pthread_mutex_t ffi_trampoline_lock = PTHREAD_MUTEX_INITIALIZER;
static ffi_trampoline_table *ffi_trampoline_tables = NULL;

static ffi_trampoline_table *
-ffi_trampoline_table_alloc (void)
+ffi_static_trampoline_table_alloc (void)
+{
+ ffi_trampoline_table *table;
+ uint16_t i;
+
+ /* We have valid trampoline and config pages */
+ table = calloc (1, sizeof (ffi_trampoline_table));
+ table->free_count = FFI_STATIC_TRAMPOLINE_COUNT;
+ table->config_page = (vm_address_t)&ffi_bridge_data_page1;
+ table->trampoline_page = (vm_address_t)&ffi_closure_static_trampoline_table_page;
+ table->page_type = FFI_STATIC_PAGE;
+ /* Create and initialize the free list */
+ table->free_list_pool =
+ calloc (FFI_STATIC_TRAMPOLINE_COUNT, sizeof (ffi_trampoline_table_entry));
+
+ for (i = 0; i < table->free_count; i++)
+ {
+ ffi_trampoline_table_entry *entry = &table->free_list_pool[i];
+ entry->trampoline =
+ (void *) (table->trampoline_page + (i * FFI_TRAMPOLINE_SIZE));
+
+ if (i < table->free_count - 1)
+ entry->next = &table->free_list_pool[i + 1];
+ }
+
+ table->free_list = table->free_list_pool;
+
+ return table;
+}
+
+static ffi_trampoline_table *
+ffi_remap_trampoline_table_alloc (void)
{
ffi_trampoline_table *table;
+ uint16_t i;
+
vm_address_t config_page;
vm_address_t trampoline_page;
vm_address_t trampoline_page_template;
vm_prot_t cur_prot;
vm_prot_t max_prot;
kern_return_t kt;
- uint16_t i;

/* Allocate two pages -- a config page and a placeholder page */
config_page = 0x0;
kt = vm_allocate (mach_task_self (), &config_page, PAGE_MAX_SIZE * 2,
- VM_FLAGS_ANYWHERE);
+ VM_FLAGS_ANYWHERE);
if (kt != KERN_SUCCESS)
- return NULL;
+ return NULL;
+
+ /* Allocate two pages -- a config page and a placeholder page */
+ //bdffc_closure_trampoline_table_page

/* Remap the trampoline table on top of the placeholder page */
trampoline_page = config_page + PAGE_MAX_SIZE;
- trampoline_page_template = (vm_address_t)&ffi_closure_trampoline_table_page;
+ trampoline_page_template = (vm_address_t)&ffi_closure_remap_trampoline_table_page;
#ifdef __arm__
- /* ffi_closure_trampoline_table_page can be thumb-biased on some ARM archs */
+ /* bdffc_closure_trampoline_table_page can be thumb-biased on some ARM archs */
trampoline_page_template &= ~1UL;
#endif
kt = vm_remap (mach_task_self (), &trampoline_page, PAGE_MAX_SIZE, 0x0,
- VM_FLAGS_OVERWRITE, mach_task_self (), trampoline_page_template,
- FALSE, &cur_prot, &max_prot, VM_INHERIT_SHARE);
+ VM_FLAGS_OVERWRITE, mach_task_self (), trampoline_page_template,
+ FALSE, &cur_prot, &max_prot, VM_INHERIT_SHARE);
if (kt != KERN_SUCCESS)
- {
+ {
vm_deallocate (mach_task_self (), config_page, PAGE_MAX_SIZE * 2);
return NULL;
- }
+ }
+

/* We have valid trampoline and config pages */
table = calloc (1, sizeof (ffi_trampoline_table));
- table->free_count = FFI_TRAMPOLINE_COUNT;
+ table->free_count = FFI_REMAP_TRAMPOLINE_COUNT;
table->config_page = config_page;
table->trampoline_page = trampoline_page;
-
+ table->page_type = FFI_REMAP_PAGE;
/* Create and initialize the free list */
table->free_list_pool =
- calloc (FFI_TRAMPOLINE_COUNT, sizeof (ffi_trampoline_table_entry));
+ calloc (FFI_REMAP_TRAMPOLINE_COUNT, sizeof (ffi_trampoline_table_entry));

for (i = 0; i < table->free_count; i++)
- {
+ {
ffi_trampoline_table_entry *entry = &table->free_list_pool[i];
entry->trampoline =
- (void *) (table->trampoline_page + (i * FFI_TRAMPOLINE_SIZE));
+ (void *) (table->trampoline_page + (i * FFI_TRAMPOLINE_SIZE));

if (i < table->free_count - 1)
- entry->next = &table->free_list_pool[i + 1];
- }
+ entry->next = &table->free_list_pool[i + 1];
+ }

table->free_list = table->free_list_pool;

return table;
}

+static ffi_trampoline_table *
+ffi_trampoline_table_alloc (void)
+{
+#ifdef __arm64__
+ static int static_page_used = 0;
+ if (static_page_used == 0) {
+ static_page_used = 1;
+ return ffi_static_trampoline_table_alloc();
+ }
+#endif
+
+ return ffi_remap_trampoline_table_alloc();
+}
+
static void
ffi_trampoline_table_free (ffi_trampoline_table *table)
{
@@ -257,7 +315,7 @@ ffi_trampoline_table_free (ffi_trampoline_table *table)
table->next->prev = table->prev;

/* Deallocate pages */
- vm_deallocate (mach_task_self (), table->config_page, PAGE_MAX_SIZE * 2);
+// vm_deallocate (mach_task_self (), table->config_page, PAGE_MAX_SIZE * 2);

/* Deallocate free list */
free (table->free_list_pool);
@@ -331,11 +389,16 @@ ffi_closure_free (void *ptr)

/* If all trampolines within this table are free, and at least one other table exists, deallocate
* the table */
- if (table->free_count == FFI_TRAMPOLINE_COUNT
+ if (table->page_type == FFI_STATIC_PAGE && table->free_count == FFI_STATIC_TRAMPOLINE_COUNT
&& ffi_trampoline_tables != table)
{
ffi_trampoline_table_free (table);
}
+ else if (table->page_type == FFI_REMAP_PAGE && table->free_count == FFI_REMAP_TRAMPOLINE_COUNT
+ && ffi_trampoline_tables != table)
+ {
+ ffi_trampoline_table_free (table);
+ }
else if (ffi_trampoline_tables != table)
{
/* Otherwise, bump this table to the top of the list */
diff --git a/Stinger/libffi/darwin_ios/src/aarch64/ffi_arm64.c b/Stinger/libffi/darwin_ios/src/aarch64/ffi_arm64.c
index 8da41f6..66ad620 100644
--- a/Stinger/libffi/darwin_ios/src/aarch64/ffi_arm64.c
+++ b/Stinger/libffi/darwin_ios/src/aarch64/ffi_arm64.c
@@ -807,9 +807,21 @@ ffi_prep_closure_loc (ffi_closure *closure,
#ifdef HAVE_PTRAUTH
codeloc = ptrauth_strip (codeloc, ptrauth_key_asia);
#endif
- void **config = (void **)((uint8_t *)codeloc - PAGE_MAX_SIZE);
- config[0] = closure;
- config[1] = start;
+ // trampoline_table 前8个字节 page_type字段
+ if (*((uint64_t *)closure->trampoline_table) == 0) {
+ extern void *ffi_closure_static_trampoline_table_page;
+ extern void *ffi_bridge_data_page1;
+ size_t offset = (intptr_t)codeloc - (intptr_t)(&ffi_closure_static_trampoline_table_page);
+ void **config = (void**)((int64_t)&ffi_bridge_data_page1 + offset);
+ config[0] = closure;
+ config[1] = start;
+ } else {
+ void **config = (void**)((uint8_t *)codeloc - PAGE_MAX_SIZE);
+ config[0] = closure;
+ config[1] = start;
+ }
+
+
#endif
#else
static const unsigned char trampoline[16] = {
diff --git a/Stinger/libffi/darwin_ios/src/aarch64/sysv_arm64.S b/Stinger/libffi/darwin_ios/src/aarch64/sysv_arm64.S
index 05a612f..fa384d3 100644
--- a/Stinger/libffi/darwin_ios/src/aarch64/sysv_arm64.S
+++ b/Stinger/libffi/darwin_ios/src/aarch64/sysv_arm64.S
@@ -67,7 +67,7 @@ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
# define BR(r) br r
# define BLR(r) blr r
#endif
-
+.extern _ffi_bridge_data_page1;
.text
.align 4

@@ -371,22 +371,93 @@ CNAME(ffi_closure_SYSV):

#if FFI_EXEC_TRAMPOLINE_TABLE

+# 动态remap的 page
#ifdef __MACH__
#include <mach/machine/vm_param.h>
- .align PAGE_MAX_SHIFT
-CNAME(ffi_closure_trampoline_table_page):
+ .align PAGE_MAX_SHIFT
+ CNAME(ffi_closure_remap_trampoline_table_page):
.rept PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE
adr x16, -PAGE_MAX_SIZE
ldp x17, x16, [x16]
- BR(x16)
- nop /* each entry in the trampoline config page is 2*sizeof(void*) so the trampoline itself cannot be smaller than 16 bytes */
+ br x16
+ nop /* each entry in the trampoline config page is 2*sizeof(void*) so the trampoline itself cannot be smaller that 16 bytes */
+ .endr
+
+.globl CNAME(ffi_closure_remap_trampoline_table_page)
+#ifdef __ELF__
+ .type CNAME(ffi_closure_remap_trampoline_table_page), #function
+ .hidden CNAME(ffi_closure_remap_trampoline_table_page)
+ .size CNAME(ffi_closure_remap_trampoline_table_page), . - CNAME(ffi_closure_remap_trampoline_table_page)
+#endif
+#endif
+
+# 静态分配的page
+#ifdef __MACH__
+#include <mach/machine/vm_param.h>
+
+ .align 14
+ .data
+ .global _ffi_bridge_data_page1
+ _ffi_bridge_data_page1:
+ .space PAGE_MAX_SIZE*5
+ .align PAGE_MAX_SHIFT
+ .text
+ CNAME(_ffi_local_forwarding_bridge_page):
+
+ _ffi_local_forwarding_bridge:
+ adrp x17, ffi_closure_static_trampoline_table_page_start@PAGE;// text page
+ sub x16, x16, x17;// offset
+ adrp x17, _ffi_bridge_data_page1@PAGE;// data page
+ add x16, x16, x17;// data address
+ ldp x17, x16, [x16];// x17 closure x16 start
+ br x16
+ nop
+ nop
+ .align PAGE_MAX_SHIFT
+ CNAME(ffi_closure_static_trampoline_table_page):
+
+#这个label 用来adrp@PAGE 计算 trampoline 到 trampoline page的offset
+#留了5个用来调试。
+# 我们static trampoline 两条指令就够了,这里使用4个,和remap的保持一致
+ ffi_closure_static_trampoline_table_page_start:
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
+
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
+
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
+
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
+
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
+
+ // 5 * 4
+ .rept (PAGE_MAX_SIZE*5-5*4) / FFI_TRAMPOLINE_SIZE
+ adr x16, #0
+ b _ffi_local_forwarding_bridge
+ nop
+ nop
.endr

- .globl CNAME(ffi_closure_trampoline_table_page)
- FFI_HIDDEN(CNAME(ffi_closure_trampoline_table_page))
+ .globl CNAME(ffi_closure_static_trampoline_table_page)
+ FFI_HIDDEN(CNAME(ffi_closure_static_trampoline_table_page))
#ifdef __ELF__
- .type CNAME(ffi_closure_trampoline_table_page), #function
- .size CNAME(ffi_closure_trampoline_table_page), . - CNAME(ffi_closure_trampoline_table_page)
+ .type CNAME(ffi_closure_static_trampoline_table_page), #function
+ .size CNAME(ffi_closure_static_trampoline_table_page), . - CNAME(ffi_closure_static_trampoline_table_page)
#endif
#endif

diff --git a/Stinger/libffi/darwin_ios/src/arm/sysv_armv7.S b/Stinger/libffi/darwin_ios/src/arm/sysv_armv7.S
index 45be58d..c9c8cd6 100644
--- a/Stinger/libffi/darwin_ios/src/arm/sysv_armv7.S
+++ b/Stinger/libffi/darwin_ios/src/arm/sysv_armv7.S
@@ -362,13 +362,13 @@ ARM_FUNC_END(ffi_closure_ret)
#include <mach/machine/vm_param.h>

.align PAGE_MAX_SHIFT
-ARM_FUNC_START(ffi_closure_trampoline_table_page)
+ARM_FUNC_START(ffi_closure_remap_trampoline_table_page)
.rept PAGE_MAX_SIZE / FFI_TRAMPOLINE_SIZE
adr ip, #-PAGE_MAX_SIZE @ the config page is PAGE_MAX_SIZE behind the trampoline page
sub ip, #8 @ account for pc bias
ldr pc, [ip, #4] @ jump to ffi_closure_SYSV or ffi_closure_VFP
.endr
-ARM_FUNC_END(ffi_closure_trampoline_table_page)
+ARM_FUNC_END(ffi_closure_remap_trampoline_table_page)
#endif

#else
--
2.23.0

imp_implementationWithBlock 的内部实现 trampoline

imp_implementationWithBlock 把 block 转化为imp, 是如何实现的呢?

block的函数调用,需要传递block对象,这需要我们在 调用imp的时候,能够找到block对象。 看看objc是如何实现的。

具体实现的思路是,将block对象存在 trampoline’s data 中。trampoline data 和 text page offset 为2个page size(由申请的时候决定)

返回的imp是一个跳板。

这个跳板技术可用于hook, 怎么搞,自行发挥想象吧

1
2
3
4
5
6
7
8
9
10
11
12
13
IMP trampoline(int aMode, uintptr_t index) {
assert(validIndex(index));
char *base = (char *)trampolinesForMode(aMode);
char *imp = base + index*slotSize();
#if __arm__
imp++; // trampoline is Thumb instructions
#endif
#if __has_feature(ptrauth_calls)
imp = ptrauth_sign_unauthenticated(imp,
ptrauth_key_function_pointer, 0);
#endif
return (IMP)imp;
}

执行时,TrampolineEntry 为跳板,通过 偏移量取到 block对象,随后进行调用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
L_objc_blockTrampolineImpl:
/*
x0 == self
x17 == address of called trampoline's data (2 pages before its code)
lr == original return address
*/

mov x1, x0 // _cmd = self
ldr p0, [x17] // self = block object
add p15, p0, #BLOCK_INVOKE // x15 = &block->invoke
ldr p16, [x15] // x16 = block->invoke
TailCallBlockInvoke x16, x15

// pad up to TrampolineBlockPagePair header size
nop
nop
nop

.macro TrampolineEntry
// load address of trampoline data (two pages before this instruction)
adr x17, -2*PAGE_MAX_SIZE
b L_objc_blockTrampolineImpl
.endmacro

lli源码阅读

最近需要了解一下解释器的实现。通过阅读lli学习了一波。

MachO(一) ObjC类结构的加载

最近做的事情跟MachO中的ObjC内容十分相关。OC Runtime 通过加载MachO中的文件信息,将类的信息添加到运行时,理论上,我们也可以自己去 加载指定位置的类信息注册加载到Runtime中。

首先看看OBJC类结构在MachO中有哪些内容。本文通过MachoView, Hopper 进行分析。

1
2
3
4
5
6
7
8
__TEXT, __objc_classname 类名列表
__TEXT,__objc_methodname 方法名列表
__TEXT,__objc_methtype 方法类型列表
__DATA, __objc_classlist 记录镜像所定义的类,每个条目都是一个指针,指向到 __objc_data section
__DATA,objc_imageinfo 记录 Objective-C 环境信息等,dyld 用它来判断镜像是否是 objc 镜像
__DATA,__objc_const 存放类的元数据,包括:method list、variable list、property list、class info
__DATA,__objc_data 存放真正的类数据,和 __objc_classlist 条目呼应
__DATA,__objc_classrefs 类引用列表

我关注的主要内容是 ObjC 类如何被加载注册的。
首先分析一下 大致的数据结构。

__objc_classlist其内容指向所定义类的地址,那就看看class定义的结构大致是什么样子的,通过MachOview查看 __objc_classlist的一个条目0x0000000000008100 hopper 看一下,位于__objc_data
hopper 中的 objc_class 这个结构在objc_runtime中是有的,之后分析runtime源码会用到。

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
struct objc_class : objc_object {
// Class ISA;
Class superclass;
cache_t cache; // formerly cache pointer and vtable
class_data_bits_t bits; // 先是ro,后被设置为rw
class_rw_t* data() {
return (class_rw_t *)(bits & FAST_DATA_MASK);
}
...
}

struct objc_object {
private:
isa_t isa;
...
}

struct class_ro_t {
uint32_t flags;
uint32_t instanceStart;
uint32_t instanceSize;
#ifdef __LP64__
uint32_t reserved;
#endif

const uint8_t * ivarLayout;

const char * name;
method_list_t * baseMethodList;
protocol_list_t * baseProtocols;
const ivar_list_t * ivars;

const uint8_t * weakIvarLayout;
property_list_t *baseProperties;
...
}

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
_OBJC_CLASS_$_ExampleObject:
0000000000008100 struct __objc_class { ; DATA XREF=0x8018
_OBJC_METACLASS_$_ExampleObject, // metaclass 元类
_OBJC_CLASS_$_NSObject, // superclass 父类
__objc_empty_cache, // cache 先不管
0x0, // vtable 先不管
__objc_class_ExampleObject_data // data objc_const段内
}


元类
_OBJC_METACLASS_$_ExampleObject:
00000000000080d8 struct __objc_class { ; DATA XREF=_OBJC_CLASS_$_ExampleObject
_OBJC_METACLASS_$_NSObject, // metaclass
_OBJC_METACLASS_$_NSObject, // superclass
__objc_empty_cache, // cache
0x0, // vtable
__objc_metaclass_ExampleObject_data // data
}

看这个注释,是 class_ro_t
__objc_class_ExampleObject_data:
0000000000008090 struct __objc_data { ; "ExampleObject", DATA XREF=_OBJC_CLASS_$_ExampleObject
0x80, // flags
8, // instance start
8, // instance size
0x0,
0x0, // ivar layout
0x7f5d, // name
__objc_class_ExampleObject_methods, // base methods
0x0, // base protocols
0x0, // ivars
0x0, // weak ivar layout
0x0 // base properties
}

结合源码查看一下 加载的过程。从别人的博客中看到 入口是 _objc_init。
加载通过 注册dyld回调的方式。

1
_dyld_objc_notify_register(&map_images, load_images, unmap_image);//map_images加载镜像

通过阅读一些大佬 https://zhangbuhuai.com/post/runtime.html 的博客,大致了解了OBJC加载的步骤,根据我最编译的简单的Dylib,大致过滤了一下需要关注的内容。

  1. discover classes. 即从镜像提取类信息,并存到名为allocatedClasses的全局 hash table 中 // 提取信息,不看了
  2. remap classes. 重新调整类之间的引用 // 没执行到不管了
  3. fix up selector references. 提取方法,并注册到名为namedSelectors的全局 map table 中
  4. fix up objc_msgSend_fixup // 没有这个内容,不管了
  5. discover protocols. 提取 protocols,存储到全局 map table // 先不考虑
  6. fix up @protocol references. 和类一样,protocol 也有继承关系,此过程 fixup 它们的依赖关系 // 先不考虑
  7. realize non-lazy classes. realize 含有+load方法或者静态实例的类
  8. realize future classes. realize 含有RO_FUTURE标识的类,这些类一般是 Core Foundation 中的类
  9. discover categories. 提取 categories,存储到全局 map table

Runtime 提供 void objc_registerClassPair(Class cls); 方法去注册类。

Class 类型就是 typedef struct objc_class *Class;, 看起来我们需要从MachO中读取数据,随后修正objc_class结构就能做到了。具体如何修正那就参考runtime自己的实现。

Dobby源码学习(一) Inline Hook

Inline Hook

方法拦截:

  • 找到方法地址
  • remap 替换方法开头为跳转指令
    问题:替换的指令, b的 range 在 替换指令内。会不会有问题?

构造跳转指令
_ Ldr(Register::X(17), &address_ptr);
_ br(Register::X(17));
_ PseudoBind(&address_ptr);
_ EmitInt64(address);

因为方法开头的指令被替换到其他页,因此需要:修正被替换的指令
fix pc 相关指令.. 添加跳转跳回指令