Skip to content

Welcome to call_in_stack

Jump to bottom
yuanzhubi edited this page May 30, 2017 · 39 revisions

https://github.com/yuanzhubi/call_in_stack/issues/1 Here is another English introduction.（这里有个略高阶一点的英文介绍，注意不要错过回复2.）

Coroutines programming is now widely used now in network programming. It reduces the complexity of non-blocking I/O multiplexing. Stackful coroutines enable you writing non-blocking network server like blocking network server. See libgo,libco

协程编程现在已经在网络编程中广泛使用。它减少了非阻塞io多路复用的难度。有栈协程能让你用有阻塞服务器网络服务器的语法去写一个无阻塞网络服务器。可以去看看libgo,libco。

But the stack of a stackful coroutine must pre-allocated before its running. For safety, it is usually a large number of memory(usually 64KB-128KB? To print/cout a long double number costs above 4KB stack in glibc of x64 platform). It lows downs the maximum number of coroutines.

但是我们必须为一个有栈协程在他执行之前分配好堆栈。为了安全，这个堆栈得是一大块内存（一般64KB到128KB？要知道在x64 glibc里，printf或者cout一个long double浮点数，调用过程堆栈消耗最多可超过4KB栈）。这降低了可创建的协程的最大数量。

Sometimes, the most expensive stack cost only happens in some rare case, for example, exception handling and logging. So we must always waste memory to prepare for some unusual case. Another case is recursive function (for example, quick sort algorithm). The size of stack it costs is a variable(The worst case of quick sort of a n-length array is O(n)), but we may not know the variable before the coroutine running，so we have to prepare stack for its maximum value.

有时候，特别消耗堆栈的一般都是一些稀有场景，例如，错误处理往往伴随着记日志。所以我们不得不总是为了预备处理一些不太容易发生的情况而浪费内存。还有一种情况是递归函数(例如快速排序算法)。它需要消耗的堆栈数量是一个变量（对一个n长数组执行快排最坏的时候消耗O(n)栈内存），但是我们可能在协程执行前无法知道这个变量的值（例如你需要parse一个用户输入的json并排序输出）, 所以我们不得不按它可能出现的最大值去准备堆栈。

call_in_stack is aimed at above problems. It enables you calling a function in a new stack and cost only O(1) stack of the caller. The new stack can be any writable memory, either global array or local array in stack of main function or result of new/malloc with variable size. It enables delaying the stack allocation for accurate allocation. For functions never switching coroutine, it also enables "sharing stack" with no cost between every coroutine（in one thread）, by using a global array for the functions.

call_in_stack 就是用来解决上述问题的，他允许你用一个新的堆栈来调用一个函数，只需消耗调用者O(1)的堆栈。这个新堆栈可以是任何一块可写的内存，可能是一个全局数组或main函数堆栈下的局部数组，也可能是new或malloc的分配的运行时变长空间。它通过允许延迟堆栈分配来实现精确的堆栈分配。它还无成本的允许在同一个线程中的所有协程间通过全局内存“共享栈”，只要这块栈内存上执行的函数不会发生协程切换。

Examples:

char buf[12*1024];

void let_us_call_in_stack(){

int x = 5;

call_in_stack(buf, &printf, "%d%d%p%f%d%s\n", 1, x, buf, 3.0, x++, "Hello world!");

//printf will run using buf as stack.

char* new_buf = new char[12*1024];

call_in_stack(new_buf, 12*1024, &printf, "%d%d%p%f%d%s\n", 1, x, buf, 3.0, ++x, "Hello world!");

//printf will run using new_buf as stack.

delete []new_buf;

call_in_stack(12*1024, &printf, "%d%d%p%f%d%s\n", 1, x, buf, 3.0, ++x, "Hello world!");

//printf will run using auto allocated 12*1024 KB memory as stack.

call_in_stack(&printf, "%d%d%p%f%d%s\n", 1, x, buf, 3.0, ++x, "Hello world!");

//printf will run using auto allocated default 16*1024 KB memory as stack.

//call_in_stack may calls a function A that also call_in_stack function B while both call_in_stack calling use same global array as stack. This is dangerous!

call_in_stack_safe(buf, &printf, "%d%d%p%f%d%s\n", 1, x, buf, 3.0, ++x, "Hello world!");

//If let_us_call_in_stack does not run using buf as stack, printf will run using buf as stack, or else printf will run in the stack of let_us_call_in_stack.

//call_in_stack_safe will check whether the caller and the callee function use the same stack, which is useful in nested using same stack.

std::string a("Hello world"); call_in_stack(printf, "%s\n", call_in_stack(from_member_fun(a,c_str))) ;

//call_in_stack for member function c_str of std::string!

struct functor{int operator()(int a){return a;}}b; call_in_stack(printf, "%d\n", call_in_stack(from_functor(b,3)));

//call_in_stack for functor object!

call_in_stack_safe(buf, printf, "%d\n", call_in_stack_safe(buf, from_functor([=](int arg){printf("%s\n", a.c_str()); return arg;},2))) ;

//call_in_stack for lambda object!

}

Tips: 0. call_in_stack is a header only library.

1.call_in_stack now only supports x86 & x64 in sysv abi (including operating system: Linux, Mac) with g++ compiler(CLANG or INTEL c++ compiler may be also supported, but I do not test it for lacking utility. Warmly welcome for your help!).

2.call_in_stack is type safe.

3.Time cost: the arguments are passed by stack-copying will be copying to the new stack and the arguments passed by register will not need to be copied again.

4.If you call_in_stack a function that never switches to another coroutine in it, then it can (share to) use a (thread local) global memory as stack! Using call_in_stack_safe if the memory will be nesting used.

要点： 0.call_in_stack是一个纯头文件的库。

1.call_in_stack 目前只支持在x86和x64 的 sysv abi 上(操作系统包括Linux,Mac)使用g++编译器编译，clang和intel编译器也可能是支持的，但是我缺乏必要的测试设施。热烈欢迎你们的帮助!

2.call_in_stack是类型安全的。

3.时间开销：通过栈拷贝的传参，会拷贝到新的堆栈。使用寄存器传递的参数不会重新拷贝。

4.如果你call_in_stack一个函数，它的函数体内不会发生协程切换，那么他可以（共享）使用一个（线程局部的）全局变量内存作为栈！使用call_in_stack_safe如果这个全局变量内存会被嵌套使用。

Usage limit:

We define: the signed or unsigned integer type char, wchar_t, short, int, long, long long; float number type float, double, long double; pointer or function pointer or C++ reference or C++ right value reference(enabled by defining ENABLE_RIGHT_VALUE_REFERENCE macro) of any type, excepting pointers or reference to non-static member functions or class data; const or volatile modified type of all previous type; are "basic_type".

call_in_stack can call a function f in a new stack unless:

  1. f is declared with all of its arguments in basic_type, either f is declared with fixed or not fixed number of arguments; if f is declared with variable arguments list, it must has at least one “named” argument(like the first arguments of printf) before the list!

  2. f is called with no more than 10 arguments, either f is declared with fixed or not fixed number of arguments.

  3. The return type of f is either basic_type or void.

  4. For C++ non-static class member function, function object or lambda object, we can use an adapter to wrap them so that we can continue to use call_in_stack. They share the same restrict rule(see 1,2,3) of traditional function and the interface and further restrict are in below:

4.1. For C++ non-static class member function，from_member_fun(obj, member_function_name) returns a function pointer via a class object and the name of class member function. The restrict of arguments and return value of the member_function_name are as same as of f mentioned previous. But only 9 arguments are accepted (obj itself is an argument) and variable arguments list is forbidden. obj is passed by value so member_function_name can be a virtual function.

4.2. For function object or lambda object，from_functor(obj) returns a function pointer via a class object. The restrict of arguments and return value of the operator() are as same as of f mentioned previous. But only 9 arguments are accepted (obj itself is an argument) and variable arguments list is forbidden. The function object can has data member of non-basic_type and lambda object can capture non-basic_type by copy as well.

  1. You need to point out the template argument of f, if it is a template function. Template member function is not supported in call_in_stack. Lambda with auto arguments type (since C++ 14) is not supported as well.

  2. f throws C++ exception will leads to undefined behaviors. Because stack unwind will not work properly. You can use a function F wrapping f to catch exception and do not re-throw. Then use call_in_stack with F instead of f. std::exception_ptr/std::rethrow_exception will be used for c++11 compiler in plan(but low priority) to solve this inconvenience, with particular new interface.

  3. If you want to use right value reference, define ENABLE_RIGHT_VALUE_REFERENCE macro

  4. If f has "function overloading", you should use a function pointer p with proper type to point at f, then use call_in_stack with p instead of the function name of f; or cast f to the type explicitly. It is not supported for overloaded member function or operator() of function object using in from_member_fun or from_functor. For example,

#include "cmath"

double (*plog)( double ) = &log;

call_in_stack(4*1024, plog, 2.0);

call_in_stack((float (*)( float ))(&log), 2.0);

使用限制

我们把：有符号或者无符号的整数类型char, wchar_t, short, int, long, long long; 浮点数类型float, double, long double; 任何指针(除了非静态类成员函数或者非静态类成员变量，的指针和引用)或者引用类型或者右值引用(可以通过定义ENABLE_RIGHT_VALUE_REFERENCE宏来启用)类型;任何前述类型的const或者volatile修饰类型， 统称为基本类型。

call_in_stack 可以在一个新的栈调用一个函数f, 只要能满足以下条件：

  1. f 被声明为只拥有基本类型参数，不管他拥有定长或者变长参数列表。如果f拥有变长参数列表，那么在列表前面至少有一个“具名”参数(如同printf的第一个参数)！

  2. f 被调用时只有不超过10个参数，不管他拥有定长或者变长参数列表。

  3. f 的返回类型需要是基本类型或者void。

  4. 对于C++非静态成员函数或者函数对象甚至lambda，我们使用一个小小的适配器对它们进行包装就可以继续使用call_in_stack。当然对于参数和返回值的限制依然适用(见1，2，3)，具体各个场景的用法见下：

4.1. 对于C++类非静态成员函数，from_member_fun(obj, member_function_name)可以通过传入的对象和成员函数名字产生一个可以用于call_in_stack的函数指针。这里的成员函数的参数和返回值的约束和前述的f相同，但是只能使用最多9个参数了（传入的对象obj自己占用了一个参数位置），而且不能使用变长参数列表。obj是传引用的，所以支持成员函数是虚函数。

4.2. 对于函数对象或者lambda对象，from_functor(obj)可以通过传入的对象产生一个可以用于call_in_stack的函数指针。这里的函数对象operator()操作符的参数和返回值的约束同和前述的f相同，但是只能使用最多9个参数了（传入的对象obj自己占用了一个参数位置），而且不能使用变长参数列表。函数对象可以持有非基本类型数据成员，同理lambda也允许按拷贝或引用或右值引用捕获非基本类型数据。

  1. 如果f是一个模版函数，你需要显示指定模版参数。成员函数模版在call_in_stack是不支持的。同理有auto参数的lambda（c++14）也是不支持的。

  2. f 如果抛出异常会导致未定义行为。因为堆栈回卷不能正确的工作。你可以定义一个包装函数F把f包起来捕获异常并且不让异常被重新抛出。此时call_in_stack就应该调用F而不是f了。有计划为支持C++11的编译器提供新接口，通过使用std::exception_ptr/std::rethrow_exception来解决这个不便（本任务优先级较低）。

  3. 如果需要使用右值，请define ENABLE_RIGHT_VALUE_REFERENCE宏。

  4. 如果f有被函数重载，那你需要用一个有合适类型的函数指针p指向f, 然后call_in_stack去调用p; 或者直接对f做类型转换。**用于from_member_fun 或者from_functor的成员函数或者函数对象完全不支持函数重载（例如std::string::at）。**例如

#include "cmath"

double (*plog)( double ) = &log;

call_in_stack(4*1024, plog, 2.0);

call_in_stack((float (*)( float ))(&log), 2.0);

Clone this wiki locally