1. 综述
协程库 State Threads Library 是一个基于 setjmp/longjmp 实现的 C 语言版用户线程库或协程库（user level thread）。
基本协程例子： Building Coroutines
基于 ST 的 ESDM 程序模型图
基于 setjmp/longjmp 实现协程库的基本步骤（下述线程指用户线程）：
- 需要用 jmpbuf 变量保存每一个线程的运行时环境，称为线程上下文 context。
- 为每个线程分配（malloc/mmap）一个 stack，用于该线程运行时栈，该 stack 完全等效于普通系统线程的函数调用
栈。该 stack 地址是在线程初始化时设置，所以不需要考虑 setjmp 时保存线程的栈上 frames 数据的问题。 - 通过调用 setjmp 初始化线程运行时上下文，将 context 数据存放到 jmpbuf 结构中。然后修改其中的栈指针 SP 指向上
一步分配的 stack。根据当前系统栈的增长方向，将 SP 设置为 stack 的最低或最高地址。 - 线程退出时，需要返回一个安全的系统位置。即，需要有一个主线程 main thread 或 idle thread 来作为其他线程最终的
退出跳转地址。需要为主线程保存一个 jmpbuf。 - 设置过 main thread 的 jmpbuf 后，需要跳转到其他线程开始执行业务线程。
- 实现一个 context 交换函数，在多个线程之间进行跳转：保存自己的 jmpbuf，longjmp 到另一个线程的 jmpbuf。
State Threads 底层基于 event-driven select/poll/kqueue/epoll 等 IO 复用机制。
ST 中有 IOQ, ZOMEBIEQ, RUNQ, SLEEPQ 等几个队列，用来存储处于对应状态的 threads。
- RUNQ 中存储的是可以被调度运行的 threads，每次调用 _st_vp_schedule 即从该队列中取出一个 threads 去运行。
- IOQ 存储处于 IO 等待状态的 threads，当上层调用 st_poll 时，将该 thread 放入 IOQ 中；当底层 epoll 有 IO 事件到达
时，将该 thread 从 IOQ 中移除，并放入 RUNQ 中。 - 当 thread 退出时，放入 ZOMBIEQ 中。
- 当 st_poll 传入的超时参数 > 0 或调用 st_usleep 和 st_cond_timewait 时，将 thread 加入 SLEEPQ 中。
2. 重要结构体
2.1 st_thread_t
#include <st.h>
typedef struct _st_thread * st_thread_t;
#include <common.h>
typedef struct _st_thread _st_thread_t;
struct _st_thread {
int state; /* Thread's stage */
int flags; /* Thread's flags */
void *(*start)(void *arg); /* The start function of the thread */
void *arg; /* Argument of the start function */
void *retval; /* Return value of the start function */
_st_stack_t *stack; /* Info about thread's stack */
_st_clist_t links; /* For putting on run/sleep/zombie queue */
_st_clist_t wait_links; /* For putting on mutex/condvar wait queue */
#ifdef DEBUG
_st_clist_t tlink; /* For puttint on thread queue */
#endif
st_utime_t due; /* Wakeup time when thread is sleeping */
_st_thread_t *left; /* For putting in timeout heap */
_st_thread_t *right; /* -- see docs/timeout_heap.txt for details */
int heap_index;
void **private_data; /* Per thread private data */
_st_cond_t *term; /* Termination condition variable for join */
jmp_buf context; /* Thread's context */
};2.2 st_cond_t
#include <st.h>
typedef struct _st_cond * st_cond_t;
#include <common.h>
typedef struct _st_cond {
_st_clist_t wait_q; /* Condition variable wati queue */
}_st_cond_t;在 State Threads 库中，不需要在等待条件变量之前锁定互斥对象。
2.3 st_mutex_t
#include <st.h>
typedef struct _st_mutex * st_mutex_t;
#include <common.h>
typedef struct _st_mutex {
_st_thread_t *owner; /* Current mutex owner */
_st_clist_t wait_q; /* Mutex wait queue */
}_st_mutex_t;这些互斥锁只能用于进程内线程同步，不可用于进程间同步。
2.4 st_utime_t
#include <st.h>
typedef unsigned long long st_utime_t;该数据类型（无符号 64 bit 整数）表示自过去某个任意时间以来用微妙表示的高分辨率实时。
2.5 st_netfd_t
#include <st.h>
typedef struct _st_netfd * st_netfd_t;
#include <common.h>
typedef struct _st_netfd {
int osfd; /* Underlying OS file descriptor */
int inuse; /* In-use flag */
void *private_data; /* Per descriptor private data */
_st_destructor_t destructor; /* Private data destructor function */
void *aux_data; /* Auxiliary data for internal use */
struct _st_netfd *next; /* For putting on the free list */
}_st_netfd_t;该数据类型通常表示网络通信的任意开放端点（套接字，管道端点，FIFO 等），且可以封装任意打开的文件描述符。
2.6 st_switch_cb_t
#include <st.h>
#ifdef ST_SWITCH_CB
typedef void (*st_switch_cb_t)(void);
#endif该数据类型是用于描述一个指向当线程被设置为停止或运行时将被调用的函数的指针。
2.7 _st_vp_t
#include <common.h>
typedef struct _st_vp {
_st_thread_t *idle_thread; /* Idle thread for this vp */
st_utime_t last_clock; /* The last time we went into vp_check_clock() */
_st_clist_t run_q; /* run queue for this vp */
_st_clist_t io_q; /* io queue for this vp */
_st_clist_t zombie_q; /* zombie queue for this vp */
#ifdef DEBUG
_st_clist_t thread_q; /* all threads of this vp */
#endif
int pagesize;
_st_thread_t *sleep_q; /* sleep queue for this vp */
int sleepq_size; /* number of threads on sleep queue */
#ifdef ST_SWITCH_CB
st_switch_cb_t switch_out_cb; /* called when a thread is switched out */
st_switch_cb_t switch_in_cb; /* called when in thread is switched in */
#endif
}_st_vp_t;3. co-routine 的创建与stack的管理
ST 是实现了co-routine 的一套机制，即用户态线程，或者叫做协程。将 epoll（async，nonblocking socket）的非阻塞变成协程的方式，将所有有状态空间都放到 stack 中，避免异步的大循环和状态空间的判断。
3.1 st 的初始化
#include <sched.c>
/* Global data */
_st_vp_t _st_this_vp; /* This VP */
_st_thread_t *_st_this_thread; /* Current thread */
int _st_active_count = 0; /* Active thread count */
/*
* Intialize this Virtual Processor
*/
int st_init(void)
{
_st_thread_t *thread;
if (_st_active_count) {
/* Already initialized */
return 0;
}
/* We can ignore return value here */
/* 设置使用的事件监控机制，支持 epoll 的一般为 epoll */
st_set_eventsys(ST_EVENTSYS_DEFAULT);
if (_st_io_init() < 0)
return -1;
memset(&_st_this_vp, 0, sizeof(_st_vp_t));
/* 初始化 run，io，zombie，thread 等几个队列 */
ST_INIT_CLIST(&_ST_RUNQ);
ST_INIT_CLIST(&_ST_IOQ);
ST_INIT_CLIST(&_ST_ZOMBIEQ);
#ifdef DEBUG
ST_INIT_CLIST(&_ST_THREADQ);
#endif
/* 调用相应的事件监控机制的回调函数，如 epoll->init */
if ((*_st_eventsys->init)() < 0)
return -1;
_st_this_vp.pagesize = getpagesize();
_st_this_vp.last_clock = st_utime();
/*
* Create idle thread
*/
_st_this_vp.idle_thread = st_thread_create(_st_idle_thread_start, NULL, 0, 0);
if (!_st_this_vp.idle_thread)
return -1;
_st_this_vp.idle_thread->flags = _ST_FL_IDLE_THREAD;
_st_active_count--;
_ST_DEL_RUNQ(_st_this_vp.idle_thread);
/*
* Initialize primordial thread
*/
thread = (_st_thread_t *)calloc(1, sizeof(_st_thread_t) + (ST_KEYS_MAX * sizeof(void *)));
if (!thread)
return -1;
thread->private_data = (void **) (thread + 1);
thread->state = _ST_ST_RUNNING;
/* 线程的 flags 为 _ST_FL_PRIMORDIAL，用来指明 stack 是否是 st 自己分配的 */
thread->flags = _ST_FL_PRIMORDIAL;
_ST_SET_CURRENT_THREAD(thread);
_st_active_count++;
#ifdef DEBUG
_ST_ADD_THREADQ(thread);
#endif
return 0;
}在 st_init() 函数里，创建了 primordial thread 和 idle thread 这两个线程。primordial thread 作为起始线程当有其他线程加入运行队列后从该线程切出，idle thread 作为背景线程在没有可运行线程的时候执行 io 调度函数分发事件。
st_init() 里面调用 st_thread_create 并不会开始执行 idle 线程，创建其他线程也一样，只有在直接或间接调用_st_vp_schedule 之后才会开始执行 RUNQ 上面的线程。_st_vp_schedule 函数在 _ST_SWITCH_CONTEXT 中被调用。
st 的初始线程，或者叫做物理线程，primordial 线程，是调用 st_init 的那个线程。一般而言，调用 st 的程序都是单线程，所以这个初始线程也就是那个系统的唯一的一个线程。
所有 st 的线程都是调用 st_create_thread 创建的，使用 st 自己开辟的 stack；除了一种初始线程，没有重新设置 stack，这个就是初始线程（物理线程）。
3.1.1 st_set_eventsys
int set_set_eventsys(int eventsys)
{
/* 若该全局变量已经被设置了，则直接返回 */
if (_st_eventsys) {
errno = EBUSY;
return -1;
}
/* 默认使用 epoll 事件监控机制 */
switch (eventsys) {
case ST_EVENTSYS_DEFAULT:
case ST_EVENTSYS_ALT:
default:
if (_st_epoll_is_supported()) {
_st_eventsys = &_st_epoll_eventsys;
break;
}
errno = EINVAL;
return -1;
}
return 0;
}该函数主要是设置全局变量 _st_eventsys，来确定该 st 使用的事件监控机制，一般默认为 epoll。
3.1.2 _st_io_init
/* Maximum number of file descriptors that the process can open */
static int _st_osfd_limit = -1;
int _st_io_init(void)
{
struct sigaction sigact;
struct rlimit rlim;
int fdlim;
/* Ignore SIGPIPE */
sigact.sa_handler = SIG_IGN;
sigmeptyset(&sigact.sa_mask);
sigact.sa_flags = 0;
if (sigaction(SIGPIPE, &sigact, NULL) < 0) {
return -1;
}
/* Set maximum number of open file descriptors */
if (getrlimit(RLIMIT_NOFILE, &rlim) < 0) {
return -1;
}
fdlim = (*_st_eventsys->fd_getlimit)();
if (fdlim > 0 && rlim.rlim_max > (rlim_t) fdlim) {
rlim.rlim_max = fdlim;
}
rlim.rlim_cur = rlim.rlim_max;
if (setrlimit(RLIMIT_NOFILE, &rlim) < 0) {
return -1;
}
_st_osfd_limit = (int) rlim.rlim_max;
return 0;
}该函数主要是设置忽略 SIGPIPE 信号，并将当前系统关于可打开文件描述符的个数的硬限制数设置为软限制个数。
下面先分析 stack 的管理。
3.2 stack 的管理
3.2.1 stack 的数据结构
typedef struct _st_stack {
_st_clist_t links;
char *vaddr; /* Base of stack's allocated memory */
int vaddr_size; /* Size of stack's allocated memory */
int stk_size; /* Size of usable portion of the stack */
char *stk_bottom; /* Lowest address of stack's usable portion */
char *stk_top; /* Highest address of stack's usable portion */
void *sp; /* Stack pointer from C's point of view */
}_st_stack_t;实际上 vaddr 是栈的内存开始地址。
栈的分配是在 _st_stack_new 函数，在 st_thread_create 函数调用，先计算 stack 的尺寸，然后分配栈.
3.2.2 _st_stack_new
/* How much space to leave between the stacks, at each end */
#define REDZONE _ST_PAGE_SIZE // 4096
_st_clist_t _st_free_stacks = ST_INIT_STATIC_CLIST(&_st_free_stacks);
int _st_num_free_stacks = 0;
int _st_randomize_stacks = 0;
/**
* The below comment is by winlin:
* The stack memory struct:
* | REDZONE | stack | extra | REDZONE |
* +---------+------------------------+---------+---------+
* | 4k | | 4k/0 | 4k |
* +---------+------------------------+---------+---------+
* vaddr bottom top
* When _st_randomize_stack is on, by st_randomize_stacks(),
* the bottome and top will random movided in the extra:
* long offset = (random() % extra) & ~0xf;
* ts->stk_bottom += offset;
* ts->stk_top += offset;
* Both REDZONE are protected by mprotect when DEBUG is on.
* 上面是栈分配后的结果，两边是 REDZONE 使用 mprotect 保护不被访问（在 DEBUG 开启后），
* extra 是一个额外的内存块，st_randomize_stacks 开启后会调整 bottom 和 top，就是随机
* 的向右边移动一点。
* 总之，最后使用的，对外提供的接口就是 bottom 和 top，st_thread_create 函数会初始化 sp。
* stack 对外提供的服务就是 [bottom, top] 这个内存区域
*/
_st_stack_t *st_stack_new(int stack_size)
{
_st_clist_t *qp;
_st_stack_t *ts;
int extra;
// TODO: WINLIN: remove the stack reuse.
/* 先从 _st_free_stacks(空闲栈) 中查找是否有空闲的栈，有则从其中取出一个栈,
* 同时将从 _st_free_stacks 链表中移除 */
for (qp = _st_free_stacks.next; qp != &_st_free_stacks; qp = qp->next) {
ts = _ST_THREAD_STACK_PTR(qp);
if (ts->stk_size >= stack_size) {
/* Found a stack that is big enough */
ST_REMOVE_LINK(&ts->links);
_st_num_free_stacks--;
ts->links.next = NULL;
ts->links.prev = NULL;
return ts;
}
}
/* _st_free_stacks 中没有空闲的栈则创建一个新的 */
/* Make a new thread stack object. */
if ((ts = (_st_stack_t *)calloc(1, sizeof(_st_stack_t))) == NULL) {
return NULL;
}
extra = _st_randomize_stacks ? _ST_PAGE_SIZE : 0;
ts->vaddr_size = stack_size + 2 * REDZONE + extra;
/* 为该栈映射 ts->vaddr_size 大小的内存空间 */
ts->vaddr = _st_new_stk_segment(ts->vaddr_size);
if (!ts->vaddr) {
free(ts);
return NULL;
}
ts->stk_size = stack_size;
ts->stk_bottom = ts->vaddr + REDZONE;
ts->stk_top = ts->stk_bottom + stack_size;
#ifdef DEBUG
mprotect(ts->vaddr, REDZONE, PROT_NONE);
mprotect(ts->stk_top + extra, REDZONE, PROT_NONE);
#endif
if (extra) {
long offset = (random() % extra) & ~0xf;
ts->stk_bottom += offset;
ts->stk_top += offset;
}
return ts;
}3.2.3 _st_new_stk_segment
static char *_st_new_stk_segment(int size)
{
#ifdef MALLOC_STACK
void *vaddr = malloc(size);
#else
static int zero_fd = -1;
/* 表示该映射的内存是私有的 */
int mmap_flags = MAP_PRIVATE;
void *vaddr;
#if defined (MD_USE_SYSV_ANON_MMAP)
if (zero_fd < 0) {
if ((zero_fd = open("/dev/zero", O_RDWR, 0)) < 0)
return NULL;
fcntl(zero_fd, F_SETFD, FD_CLOEXEC);
}
#elif defined (MD_USE_BSD_ANON_MMAP)
mmap_flags |= MAP_ANON;
#else
#error Unknown OS
#endif
/* 映射 size 大小的内存，该内存可读/写 */
vaddr = mmap(NULL, size, PROT_READ | PROT_WRITE, mmap_flags, zero_fd, 0);
if (vaddr == (void *)MAP_FAILED)
return NULL;
#endif /* MALLOC_STACK */
return (char *)vaddr;
}3.3 线程的创建：st_thread_create
_st_thread_t *st_thread_create(void *(start)(void *arg), void *arg, int joinable, int stk_size)
{
_st_thread_t *thread;
_st_stack_t *stack;
void **ptds;
char *sp;
#ifdef __ia64__
char *bsp;
#endif
/* Adjust stack size */
if (stk_size = 0) {
stk_size = ST_DEFAULT_STACK_SIZE;
}
stk_size = ((stk_size + _ST_PAGE_SIZE - 1) / _ST_PAGE_SIZE) * _ST_PAGE_SIZE;
/* 从栈的空闲链表_st_free_stacks中取出一个空闲栈或重新分配一个新的栈 */
stack = _st_stack_new(stk_size);
if (!stack) {
return NULL;
}
/* Allocate thread object and per-thread data off the stack */
#if defined(MD_STACK_GROWS_DOWN)
sp = stack->stk_top;
#ifdef __ia64__
/*
* The stack segment is split in the middle. The upper half is used
* as backing store for the register stack which grows upward.
* The lower half is used for the traditional memory stack which
* grows downward. Both stacks start in the middle and grow outward
* from each other.
*/
/**
* The below comments is by winlin:
* The Stack public struture:
* +--------------------------------------------------------------+
* | stack |
* +--------------------------------------------------------------+
* bottom top
* The code bellow use the stack as:
* +-----------------+-----------------+-------------+------------+
* | stack of thread |pad+align(128B+) |thread(336B) | keys(128B) |
* +-----------------+-----------------+-------------+------------+
* bottom sp trd ptds top
* (context[0].__jmpbuf.sp) (private_data)
*/
sp -= (stk_size >> 1);
bsp = sp;
/* Make register stack 64-byte aligned */
if ((unsigned long)bsp & 0x3f)
bsp = bsp + (0x40 - ((unsigned long)bsp & 0x3f));
stack->bsp = bsp + _ST_STACK_PAD_SIZE;
#endif
sp = sp - (ST_KEYS_MAX * sizeof(void *));
ptds = (void **) sp;
sp = sp - sizeof(_st_thread_t);
thread = (_st_thread_t *) sp;
/* Make stack 64-byte aligned */
if ((unsigned long) sp & 0x3f) {
sp = sp - ((unsigned long) sp & 0x3f);
}
stack->sp = sp - _ST_STACK_PAD_SIZE;
#elif defined (MD_STACK_GROWS_UP)
sp = stack->stk_bottom;
thread = (_st_thread_t *) sp;
sp = sp + sizeof(_st_thread_t);
ptds = (void **) sp;
sp = sp + (ST_KEYS_MAX * sizeof(void *));
/* Make stack 64-byte aligned */
if ((unsigned long)sp & 0x3f)
sp = sp + (0x40 - ((unsigned long)sp & 0x3f));
stack->sp = sp + _ST_STACK_PAD_SIZE;
#else
#error "Only Supports Stack Grown Down"
#endif
memset(thread, 0, sizeof(_st_thread_t));
memset(ptds, 0, ST_KEYS_MAX * sizeof(void *));
/* Initialize thread */
thread->private_data = ptds;
thread->stack = stack;
thread->start = start;
thread->arg = arg;
#ifndef __ia64__
_ST_INIT_CONTEXT(thread, stack->sp, _st_thread_main);
#else
_ST_INIT_CONTEXT(thread, stack->sp, stack->bsp, _st_thread_main);
#endif
/* If thread is joinable, allocate a termination condition variable */
if (joinable) {
thread->term = st_cond_new();
if (thread->term == NULL) {
_st_stack_free(thread->stack);
return NULL;
}
}
/* Make thread runnable */
thread->state = _ST_ST_RUNNABLE;
/* 活跃线程计数值加 1 */
_st_active_count++;
/* 将该线程添加到 run 队列中，等待虚拟处理器调度该线程运行 */
_ST_ADD_RUNQ(thread);
#ifdef DEBUG
/* 将该线程添加到 thread 队列中 */
_ST_ADD_THREADQ(thread);
#endif
return thread;
}co-routine 必须要自己分配 stack，因为 setjmp 保存的只是 sp 的值，而没有全部 copy 栈，所有若使用系统的 stack，各个 thread 之间 longjmp 时会导致混淆。参考： coroutine和setjmp/longjmp的关系
3.3.1 _ST_INIT_CONTEXT
#define MD_INIT_CONTEXT(_thread, _sp, _main) \
ST_BEGIN_MACRO \
/* 第一次 setjmp，保存当前线程的上下文后，返回 0，当在其他地方调用 longjmp
* 跳转到这里时，返回 1，此时会执行 _main() 函数 */
if (MD_SETJMP((_thread)->context)) \
_main(); \
(_thread)->context[3] = (long) (_sp); \
ST_END_MACRO3.4 线程的启动和切换
当在其他地方调用 longjmp 到上面创建的 idle_thread 线程，这时会从 setjmp 地方开始执行，返回值非 0，因而进入 thread 的主函数：_st_thread_main。
3.4.1 _st_thread_main
void _st_thread_main(void)
{
_st_thread_t *thread = _ST_CURRENT_THREAD();
/*
* Cap the stack by zeroing out the saved return address register
* value. This allows some debuggin/profiling tools to know when
* to stop unwinding the stack. It's a no-op on most platforms.
*/
MD_CAP_STACK(&thread);
/* Run thread main */
thread->retval = (*thread->start)(thread->arg);
/* All done, time to go away */
st_thread_exit(thread->retval);
}进入到 _st_thread_main 中后，会调用用户指定的线程函数（这个函数里面会调用 st 函数 setjmp，下次 longjmp 是到这个位置了）；从线程函数返回后，会调用 st_thread_exit 清理线程，然后切换到其他函数，直到完整最后一个函数就返回了。
这个就是 st 的 thread 启动和调度的过程。
第一次创建线程和 setjmp 后，会设置 sp，即设置 stack。也就是说，这个函数的所有 stack 信息在 longjmp 之后都是未知的了，这就是所有 st 的 thread 结束后，必须 longjmp 到其他的线程，或者退出，不能直接直接 return 的原因（因为没法 return 了，* stack 就是 _st_thread_main）。
st 在调用 st_init 初始化时，会把当前线程当做 _ST_FL_PRIMORDIAL，也就是初始化线程，这个线程若调用 exit，等待其他 thread 完成后，会直接 exit。实际上是没有线程时会切换到 idle 线程。
3.4.2 idle 线程
idle 线程是在 st_init 时创建的，st_init 创建了一个 idle 线程（使用 st_thread_create），以及直接创建一个 _ST_FL_PRINORDIAL 线程（直接calloc）。第一次在其他地方调用 longjmp 时，调用到的第一个线程就是 idle 线程：
void *_st_idle_thread_start(void *arg)
{
_st_thread_t *me = _ST_CURRENT_THREAD();
while (_st_active_count > 0) {
/* Idle vp till I/O is ready or the smallest timeout expired */
_ST_VP_IDLE();
/* Check sleep queue for expired threads */
_st_vp_check_clock();
me->state = _ST_ST_RUNNABLE;
_ST_SWITCH_CONTEXT(me);
}
/* No more threads */
exit(0);
/* NOTHREACHED */
return NULL;
}该函数的主循环就是监听 I/O 事件或检测是否有超时事件发生，然后切换上下文。
3.5 thread 的生命周期
- 第一阶段：st_init 创建 idle 线程和创建 priordial 线程（初始线程，物理线程，_ST_FL_PRIORDIAL），这时候 _st_active_count 是 1，也就是初始线程（调用 st_init，也是物理线程）在运行，idle 线程不算一个 active 线程，它主要是做切换和退出。
- 第二阶段：可选的阶段，用户创建线程。调用 st_thread_create 时，会把 _st_active_count 递增，并且加入线程队列。譬如创建了一个线程；这时候 st 调度有两个线程，一个是初始线程，一个是刚刚创建的线程。
- 第三个阶段，初始线程切换，将控制权交给 ST。也就是初始线程，做完 st_init 和创建其他线程后，这个时候还没有任何的线程切换。初始线程（物理线程）需要将控制权切换给 ST，可以调用 st_sleep 循环和休眠，或者调用 st_thread_exit(NULL) 等待其他线程结束。假设这个阶段物理线程不进行切换，ST 将无法获取控制权，程序会直接返回。
如果物理线程不 exit，那么 st 的 idle 线程也不退出（认为有个初始线程还在运行）。如果初始线程直接退出，那么 idle 线程不会拿到控制权。如果初始线程调用 st_thread_exit(NULL)，认为是物理线程也退出，那么 idle 会等所有线程完了再 exit，相当于控制权交给了 ST。
或者说，可以在初始线程（物理线程）里面做各种的业务逻辑，譬如 SRS 用初始线程更新各种数据，给 API 使用。或者可以直接创建线程后 st_thread_exit，就等所有线程退出。