Skip to content
Snippets Groups Projects
  • Bhatu's avatar
    07901e61
    Add a new garbage collector pass. · 07901e61
    Bhatu authored
    For identity like ops (a=b), we sometimes run into use-after-free and
    double-free bugs.
    
    For this snippet
        J100 = J99
        J101 = J99 + 3         <- last use of J99
        J102 = J100 * 2        <- last use of J100
    before we were doing:
        J100 = J99
        J101 = J99 + 3
        free(J99)
        J102 = J100 * 2        <- use-after-free
        free(J100)             <- double-free
    now we do:
        J100 = J99
        J101 = J99 + 3
        J102 = J100 * 2
        free(J100)
    
    Algorithm:
    We iterate through the program in reverse order and every time we see a
    use of a variable, we insert a free after it, unless we have already
    freed it before. When we check a variable has been freed, we also check
    whether any of its aliases have also been freed.
    
    For alias analysis, we maintain alias sets using disjoint sets. Whenever
    we encounter an a=b statement, we simply do a union of a and b sets.
    
    This replaces the old LivenessOpti pass.
    07901e61
    History
    Add a new garbage collector pass.
    Bhatu authored
    For identity like ops (a=b), we sometimes run into use-after-free and
    double-free bugs.
    
    For this snippet
        J100 = J99
        J101 = J99 + 3         <- last use of J99
        J102 = J100 * 2        <- last use of J100
    before we were doing:
        J100 = J99
        J101 = J99 + 3
        free(J99)
        J102 = J100 * 2        <- use-after-free
        free(J100)             <- double-free
    now we do:
        J100 = J99
        J101 = J99 + 3
        J102 = J100 * 2
        free(J100)
    
    Algorithm:
    We iterate through the program in reverse order and every time we see a
    use of a variable, we insert a free after it, unless we have already
    freed it before. When we check a variable has been freed, we also check
    whether any of its aliases have also been freed.
    
    For alias analysis, we maintain alias sets using disjoint sets. Whenever
    we encounter an a=b statement, we simply do a union of a and b sets.
    
    This replaces the old LivenessOpti pass.