Hoes of Tech

Conceptualization of Technology

Complexity Behind Closure

Introduction

今天,我在ooc-kean上看到了一个注释:

minimum: static func ~multiple(value: This, values: ...) -> This {
    // FIXME: This creates a closure that causes a leak every time this function is called.
    values each(|v|
        if ((v as This) < value)
            value = v
    )
    value
}

minimum是Float类型的一个扩展,这里用了闭包来实现对每个值的比较。如果这些发生在GC之下,那么一切都没有问题,因为任何内存(包括闭包的)都会被GC默默的回收。但OOC-Kean并没有打开GC,这里就出现了问题——闭包需要保存它的临时环境,于是每个闭包都会创建一个结构体,但编译器并没有考虑去回收它。因此就有了这里这个FIXME。

好吧,或许你还不是很明白为什么,那么让我们来看看这段代码最终生成的C代码:

lang_Numbers__Float lang_Numbers__Float_minimum_multiple(lang_Numbers__Float value, lang_VarArgs__VarArgs values) {
    __FloatExtension_FloatExtension_closure4_ctx* __FloatExtension_ctx5 = lang_Memory__gc_malloc(((lang_types__Class*)__FloatExtension_FloatExtension_closure4_ctx_class())->size);
    (*(__FloatExtension_ctx5)) = (__FloatExtension_FloatExtension_closure4_ctx) { 
        &(value)
    };
    lang_types__Closure __FloatExtension_closure6 = (lang_types__Closure) { 
        FloatExtension____FloatExtension_FloatExtension_closure4_thunk, 
        __FloatExtension_ctx5
    };
    lang_VarArgs__VarArgs_each(values, __FloatExtension_closure6);
    return value;
}

让我们来慢慢解释这个函数。

  • 首先,对于没一个闭包(|x|..)编译器会首先生成一个闭包环境用来保存运行时的内容,这里,这个环境叫做__FloatExtension_ctx5,这是一个简单的结构体,随后,我们知道,每个closure都只能在当前Scope里有效,因此在每次使用之前,我们要为它分配新的内存,然后初始化。为什么要这么做?首先,我们可能打算模拟闭包那种随用随舍弃的特性,但这不是最大的原因。最大的问题是大部分Closure都是作为__First-class Function__使用的,如果之是定义之后简单调用的话,本来一切会很美好(我们可以简单的生成macro,或者在module里生成新的函数),但当他是一个指针时,在C语言的层面上,我们只能寻找一个替代品——这个替代品要能够使用当前scope已经存在的变量,函数,同时还能将一切反馈回来。这就是一个十分困难的问题。
  • 在这里,编译器在closure的背后做了许多事情,这里初始化的ctx5包含了一个庞大的初始化函数(未在源代码里显示),这个初始化会根据Scope里每个函数的类型和状态来决定是用Pointer(by reference)还是value。随后我们创建了一个普通的C函数并取它的指针,但它并不直接跟我们声明的closure有一样的参数,而是接受一个叫做__context__的参数,这个参数包含了所有之前的创建几个内容。
  • 最后,不管是我们直接调用闭包,还是把它当作指针使用,都可以通过统一的初始化函数生成ctxcontext了。

显然, 问题也就出在这里——为了使用context,我们分配的内存,但并没有考虑释放它。

The First Encount

第一个有的想法很单纯——既然没有释放,那么我们在Scope的最后加上一个gc_free不就行了么?那么让我们来试一试:

在生成closure之后,让我们添加一个Free的调用:

ctxFreeCall := FunctionCall new("gc_free", token)
ctxFreeCall args add(VariableAccess new(ctxDecl, token))
trail addAfterInScope(this, ctxFreeCall)

trail addAfterInScope会在当前Scope里当前Statement的后方生成对应的函数——当然,前提是编译器的栈没有问题。

然后,理所当然的,刚才的内存泄漏消失了:

lang_Numbers__Float lang_Numbers__Float_minimum_multiple(lang_Numbers__Float value, lang_VarArgs__VarArgs values) {
    __FloatExtension_FloatExtension_closure4_ctx* __FloatExtension_ctx5 = lang_Memory__gc_malloc(((lang_types__Class*)__FloatExtension_FloatExtension_closure4_ctx_class())->size);
    (*(__FloatExtension_ctx5)) = (__FloatExtension_FloatExtension_closure4_ctx) { 
        &(value)
    };
    lang_types__Closure __FloatExtension_closure6 = (lang_types__Closure) { 
        FloatExtension____FloatExtension_FloatExtension_closure4_thunk, 
        __FloatExtension_ctx5
    };
    lang_VarArgs__VarArgs_each(values, __FloatExtension_closure6);
    lang_Memory__gc_free(__FloatExtension_ctx5);
    return value;
}

不过,先别高兴,因为很快就有了新的问题——标准库的一些函数运行时抛出了segmentation fault。一个典型的例子是lang/format下面的一个函数,这个函数在字符串处理里有着关键的角色:

getEntityInfo: inline func (info: FSInfoStruct@, va: VarArgsIterator*, start: Char*, end: Pointer) {

    /* save original pointer */
    p := start

    checkedInc := func {
        if (p < end) p += 1
        else InvalidFormatException new(start) throw()
    }

    /* Find any flags. */
    info flags = 0

    while(p as Pointer < end) {
        checkedInc()
        match(p@) {
            case '#' => info flags |= TF_ALTERNATE
            case '0' => info flags |= TF_ZEROPAD
            case '-' => info flags |= TF_LEFT
            case ' ' => info flags |= TF_SPACE
            case '+' => info flags |= TF_EXP_SIGN
            case => break
        }
    }

    /* Find the field width. */
    info fieldwidth = 0
    while(p@ digit?()) {
        if(info fieldwidth > 0)
            info fieldwidth *= 10
        info fieldwidth += (p@ as Int - 0x30)
        checkedInc()
    }

    /* Find the precision. */
    info precision = -1
    if(p@ == '.') {
        checkedInc()
        info precision = 0
        if(p@ == '*') {
            T := va@ getNextType()
            info precision = argNext(va, T) as Int
            checkedInc()
        }
        while(p@ digit?()) {
            if (info precision > 0)
                info precision *= 10
            info precision += (p@ as Int - 0x30)
            checkedInc()
        }
    }

    /* Find the length modifier. */
    info length = 0
    while (p@ == 'l' || p@ == 'h' || p@ == 'L') {
        info length += 1
        checkedInc()
    }

    info bytesProcessed = p as SizeT - start as SizeT
}

看起来有些长,不过没关系,你不需要理解这个函数,因为引起segmentatian fault的其实只有几行,让我们把它单独拿出来:

    checkedInc := func {
        if (p < end) p += 1
        else InvalidFormatException new(start) throw()
    }

这是什么? 对,闭包,那么我们可以想象到编译器做了什么,让我们来看看C代码:

__lang_Format_lang_Format_closure26_ctx* __lang_Format_ctx27 = lang_Memory__gc_malloc(((lang_types__Class*)__lang_Format_lang_Format_closure26_ctx_class())->size);
(*(__lang_Format_ctx27)) = (__lang_Format_lang_Format_closure26_ctx) { 
    end, 
    start, 
    &(p)
};
lang_types__Closure __lang_Format_closure28 = (lang_types__Closure) { 
    lang_Format____lang_Format_lang_Format_closure26_thunk, 
        __lang_Format_ctx27
    };
lang_types__Closure checkedInc = __lang_Format_closure28;
gc_free(__lang_Format_closure28);
(*info).flags = 0;
while (((lang_types__Pointer) (p)) < end) {

没错,我们为checkedInc生成了一个很漂亮的运行环境,但问题来了,我们在当前Scope里,并且是当前Statement之后就释放了它,那么显然,如果任何后面的代码使用了这个闭包,那么我们得到的就是一个空指针。

解决方法似乎并不是很难,让我们仔细想想——我们到底什么时候才不要这个闭包,显然,如果这个闭包定义来自函数,那么就是这个函数返回时。让我们来实现它:

i := getSize() - 1
while(i>=0){
    if(trail get(i) instanceOf?(FunctionDecl)){
        fun := trail get(i) as FunctionDecl
        for(i in fun body indexOf(this)..fun body size){
            if(fun body[i] instanceOf?(Return)){
                fun add(i, ctxFreeCall)
            }
        }
    }
    i -= 1
}

我们在每个return里都追加了free——并且它们一定要在当前statement之后。不过相信你一定已经注意到了潜在的问题——Function的Body不见得都是Statement,它有可能是If,有可能是Scope,还有可能是别的闭包,这个问题突然就变得麻烦起来了。

不过我们当然有办法,我们针对每个类型判断,然后决定是不是该递归去寻找Return:

if(fun body[i] instanceOf?(ControlStatement)){
    for(i in fun body[i] as ControlStatement body){
        // recursive do
    }
} else if(fun body[i] instanceOf?(Scope)){
    // ....
} else if ....

虽然很麻烦,但不是特别困难,如果问题到此为止,那么它远远算不上是complex,让我们再来想想,闭包还能怎么用? 对,初始化一个函数指针。如果这个发生在Function里面,那么一切都很好,但实际情况是——我们可以在Class里初始化一个函数指针,也可以在Cover里这么做。现在问题一下复杂起来了,因为定义在class里面的闭包并不属于一个函数,我们除了在Destroy(或者finalization)里面添加释放函数之外别无它法。但更大的问题是——我们无法保证class已经被完全解析!也就是说,在某些情况下,我们不知道这个class的任何信息,当然更不要说去添加释放函数。

然后,测试结果给了我们更大的打击——单纯的在Statement前面添加释放函数有时会破坏函数的结构!当我用上面的补丁对编译器进行boostrap的时候,它毫不客气的扔了一个错误,并且压根没有Backtrace。

为什么? 我想你已经注意到了,因为闭包可以作为指针被返回!

The Last, By Last

不知道你怎么看这个问题,至少上面这些东西就已经消耗了我整整一天的时间。并且问题还远远没有解决。

现在是时候来总结下原因了,简单来说,闭包可以作为指针被传来传去。在有GC时,GC会追踪它并且释放它,但当GC被关闭时,用户没法获得闭包真正的内容,因此甚至无法手动释放。而当闭包作为指针被传来传去时,我们找不到合适的时机来释放它。

那么我们来做最后一次尝试:我们追踪这个变量,一旦这个变量不再被使用时,我们就立刻追加一个gc_free,当然,这仅限于当前Scope,当它出了这个scope,我们就要求外界必须获得一个拷贝。这个实现也不难,就像这样:

addByLastUse: func(ctx: VariableDecl, marker: Statement, newcomer: Statement) -> Bool{
    i := getSize() - 1
    while(i >= 0) {
        node := data get(i) as Node
        if(node instanceOf?(Scope)){
            sc := node as Scope
            last := 0
            j := sc list size - 1
            while(j >= sc list indexOf(marker)){
                if(accessed(sc list[j], ctx)){
                    sc list add(j+1, newcomer)
                    return true
                }
                j -= 1
            }
            // no access, we can free it after scope
            return addAfterInScope(marker, newcomer)
        }
        i -= 1
    }

    false
}

access是一个判断当前变量有没有被使用过的函数,我们需要处理很多情况,就像这样:

    if(node instanceOf?(FunctionCall)){
        for(i in node as FunctionCall args){
            if(accessed(i, v)) return true
        }
    } else if(node instanceOf?(VariableAccess)){
        if(node as VariableAccess getRef() && node as VariableAccess getRef() instanceOf?(VariableDecl) && node as VariableAccess getRef() as VariableDecl name == v name){
            return true
        }
    } else if(node instanceOf?(Scope)){
        for(i in node as Scope list){
            if(accessed(i, v)) return true
        }
    } else if(node instanceOf?(ControlStatement)){
        for(i in node as ControlStatement body){
            if(accessed(i, v)) return true
        }
    }

最终,这个功能完成了。按道理,这个问题会被解决。当我们试着用修正后的编译器时,问题来了:我们得到的依然是Segmentation Fault。

为什么?

问题来自与指针,因为一个闭包可以间接的走出当前的Scope。比如

foo := func(){ // closure A
}

mystructB := struct new(foo, varia)

//mystructB go out from scope

这里,mystruct是个结构体,我们不能阻止它走出scope,但它携带了闭包,也就是说我们要阻止他直接拷贝,这是很难的事情。另外一个办法是阻止它走出scope,当然,有一个看起来很合理的规则:

  • 如果一个指针从A赋值到了B,那么它的内容的所有权要从A转移到B。

看起来有点眼熟? 对,这就是Rust。

好吧,让我们来想想如何实现Rust的推断系统——分析其里每一个Node都要有Owner,然后我们要在每一次resolve里都谨慎的判断owner是不是在改变,然后判断它有没有被返回,有没有被拷贝,有没有被当作initializer里的参数…… 这可能要重写编译器50%的代码。

好吧,我放弃了。