leonwxqian 发布的文章

修改CppCheck,做自己的扫描器 - 02

填坑。
CppCheck在解析代码时,会将代码视作不同的Token。Token分类大致如下:

enum Type {
    eVariable, eType, eFunction, eKeyword, eName,
    eNumber, eString, eChar, eBoolean, eLiteral, eEnumerator, 
    eArithmeticalOp, eComparisonOp, eAssignmentOp, eLogicalOp, eBitOp, eIncDecOp, eExtendedOp, 
    eBracket, 
    eOther,
    eNone
};

1、 名称类:变量名 , 类型名 , 函数名, 语言关键字, 其他无法识别的名字
2、 字面量:数字,字符串,字符,布尔值,用户定义的常量(c++11),枚举
3、 操作符:数学操作符,比较符号,赋值符号,逻辑符号,位运算,自增自减符号,扩展符号
4、 括号:{, }, <, >
5、 其他

这些token在保存时都是通过字符串的方式保存的,所以在比较的时候,也是通过字符串比较的形式,来确定是否和规则匹配。

先看一个典型的例子:

bool Token::Match(const Token *tok, const char pattern[], unsigned int varid)

以及它的调用者;

if (Token::Match(tok2, "strncpy|strncat ( %varid% ,", arrayInfo.declarationId())) {

tok2是一个Token对象
pattern为 strncpy|strncat ( %varid% 。
pattern中的 | 代表多重比较,即:multiCompare。从当前token开始依次比较,以空格为界限。也即第一次比较到strncat之后停止。
multiCompare的参数为%varid%(目标参数)。
multiCompare会一直比较,直到token耗尽或者传入的pattern到头,最后给出比较结果。

除了%varid%,multiCompare也支持许多比较,具体可以参考源代码:token.cpp -> multiComparePercent。
可以看到,在匹配、抽取值时,并不需要传入完整的token。

所以,对我们编写CppCheck规则时,了解Token的内容十分重要。

以一个实际的例子来看:

    const MathLib::biguint total_size = arrayInfo.num(0) * arrayInfo.element_size();
    if (printWarning && printInconclusive && Token::Match(tok2, "strncpy|memcpy|memmove ( %varid% , %str% , %num% )", arrayInfo.declarationId())) {
        if (Token::getStrLength(tok2->tokAt(4)) >= total_size) {
            const MathLib::biguint num = MathLib::toULongNumber(tok2->strAt(6));
            if (total_size == num)
                bufferNotZeroTerminatedError(tok2, tok2->strAt(2), tok2->str());
        }
    }

可以看到它:
1、 解析strncpy/memcpy/memmove并抽取varid(目标参数)、str(源字符串)、num(长度即操作数)。
2、 获取第5个token,即%str%处的token,获取它指向内容的长度。
3、 如果源操作数的长度大于等于缓冲区长度(由arrayInfo获取),代表可能潜在有问题。
4、 获取第7个token,即%num%处的token,获取它的值。
5、 如果缓冲区总大小等于长度,则报告缓冲区非零结尾的错误。

测试一下,给定测试用例:

int main()
{
 char a[10];
 memcpy(a, "abcdefghij", 10);

 return 0;
}

打开这三个提示信息以方便我们调试。为了方便我就不改全局的了,只在函数里面直接硬编码修改为true。

const bool printPortability = true; //mSettings->isEnabled(Settings::PORTABILITY);
const bool printWarning = true; //mSettings->isEnabled(Settings::WARNING);
const bool printInconclusive = true; // mSettings->inconclusive;

代码在我们指定的位置停下,调用栈如下:

    cppcheck-core.dll!CheckBufferOverrun::checkScope_inner(const Token * tok, const CheckBufferOverrun::ArrayInfo & arrayInfo) 行 1005   C++
>   cppcheck-core.dll!CheckBufferOverrun::checkScope(const Token * tok, std::map<unsigned int,CheckBufferOverrun::ArrayInfo,std::less<unsigned int>,std::allocator<std::pair<unsigned int const ,CheckBufferOverrun::ArrayInfo> > > arrayInfos) 行 939   C++
    cppcheck-core.dll!CheckBufferOverrun::checkGlobalAndLocalVariable() 行 1242  C++
    cppcheck-core.dll!CheckBufferOverrun::runSimplifiedChecks(const Tokenizer * tokenizer, const Settings * settings, ErrorLogger * errorLogger) 行 79   C++
    cppcheck-core.dll!CppCheck::checkSimplifiedTokens(const Tokenizer & tokenizer) 行 593    C++
    cppcheck-core.dll!CppCheck::checkFile(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & filename, const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & cfgname, std::basic_istream<char,std::char_traits<char> > & fileStream) 行 430 C++
    cppcheck-core.dll!CppCheck::check(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & path) 行 83   C++

可以发现:
1) arrayInfo,为我们定义的char a[10]

-       arrayInfo   {mNum={ size=1 } mVarName="a" mElementSize=1 ...}   const CheckBufferOverrun::ArrayInfo &
-       mNum    { size=1 }  std::vector<__int64,std::allocator<__int64> >
        [capacity]  1   int
+       [allocator] allocator   std::_Compressed_pair<std::allocator<__int64>,std::_Vector_val<std::_Simple_types<__int64> >,1>
        [0] 10  __int64
+       [原始视图]  {...}   std::vector<__int64,std::allocator<__int64> >
+       mVarName    "a" std::basic_string<char,std::char_traits<char>,std::allocator<char> >
        mElementSize    1   __int64
        mDeclarationId  1   unsigned int

2) token的层级列表(向后):

-       tok 0x02bfed58 "memcpy" const Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    "memcpy"    std::basic_string<char,std::char_traits<char>,std::allocator<char> >
-       mNext   0x02bfedf0 "("  Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    "(" std::basic_string<char,std::char_traits<char>,std::allocator<char> >
-       mNext   0x02bfee88 "a"  Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    "a" std::basic_string<char,std::char_traits<char>,std::allocator<char> >
-       mNext   0x02e677e8 ","  Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    "," std::basic_string<char,std::char_traits<char>,std::allocator<char> >
-       mNext   0x02e679b0 "\"abcdefghij\"" Token *

3)token向前,可以看到这东西基本就是一个双向链表:

-       mPrevious   0x02bfe838 ";"  Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    ";" std::basic_string<char,std::char_traits<char>,std::allocator<char> >
+       mNext   0x02bfed58 "memcpy" Token *
-       mPrevious   0x02bfe7a0 "]"  Token *
+       mTokensFrontBack    0x00afed90 "int" - "}"  TokensFrontBack *
+       mStr    "]" std::basic_string<char,std::char_traits<char>,std::allocator<char> >
+       mNext   0x02bfe838 ";"  Token *
-       mPrevious   0x02bfe708 "10" Token *

所以,如果我们不想仅仅依靠正则式写那些简单的规则,就需要自己抽象出一个常见的模式,并根据模式和token来编写规则。token会逐个遍历,所以不用担心跑不到你想要找的函数那里(参考CheckBufferOverrun::checkScope)。

最后需要注意的是CppCheck是按类型来扫描,而不是按代码顺序扫描,所以由于声明全局变量顺序的问题,很有可能你会发现某个靠后的代码先行被提示问题,这都是正常的结果。

修改CppCheck,做自己的扫描器 - 01

CppCheck是一个静态语法扫描器,官方介绍:

Static analysis of C/C++ code. Checks for: memory leaks, mismatching allocation-deallocation, buffer overrun, and many more. The goal is 0% false positives. See http://cppcheck.sourceforge.net for more information.

CppCheck是一个开源工程,要对其进行修改,最好还是理清楚它的工作流程。首先,让我们对一个常见的问题进行检查,代码如下:

int a[10];
a[10] = 0;

对这个越界代码进行扫描,可以发现如下调用栈处报警:

>   cppcheck-core.dll!CheckBufferOverrun::arrayIndexOutOfBoundsError(const Token * tok, const CheckBufferOverrun::ArrayInfo & arrayInfo, const std::vector<ValueFlow::Value,std::allocator<ValueFlow::Value> > & index) 行 142   C++
    cppcheck-core.dll!CheckBufferOverrun::valueFlowCheckArrayIndex(const Token * const tok, const CheckBufferOverrun::ArrayInfo & arrayInfo) 行 878  C++
    cppcheck-core.dll!CheckBufferOverrun::bufferOverrun() 行 1593    C++
    cppcheck-core.dll!CheckBufferOverrun::runChecks(const Tokenizer * tokenizer, const Settings * settings, ErrorLogger * errorLogger) 行 91 C++
    cppcheck-core.dll!CppCheck::checkNormalTokens(const Tokenizer & tokenizer) 行 563    C++
    cppcheck-core.dll!CppCheck::checkFile(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & filename, const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & cfgname, std::basic_istream<char,std::char_traits<char> > & fileStream) 行 416 C++
    cppcheck-core.dll!CppCheck::check(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & path) 行 83   C++
    cppcheck.exe!CppCheckExecutor::check_internal(CppCheck & cppcheck, int __formal, const char * const * argv) 行 871   C++
    cppcheck.exe!CppCheckExecutor::check(int argc, const char * const * argv) 行 198 C++
    cppcheck.exe!main(int argc, char * * argv) 行 95 C++

简单分析一下,基本是这几行起了作用:

    cppcheck-core.dll!CheckBufferOverrun::runChecks(const Tokenizer * tokenizer, const Settings * settings, ErrorLogger * errorLogger) 行 91 C++
    cppcheck-core.dll!CppCheck::checkNormalTokens(const Tokenizer & tokenizer) 行 563    C++
>   cppcheck-core.dll!CppCheck::checkFile(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & filename, const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & cfgname, std::basic_istream<char,std::char_traits<char> > & fileStream) 行 416 C++

注意第一行:

void CppCheck::checkNormalTokens(const Tokenizer &tokenizer)
{
    // call all "runChecks" in all registered Check classes
    for (std::list<Check *>::const_iterator it = Check::instances().begin(); it != Check::instances().end(); ++it) {
        if (mSettings.terminated())
            return;

        if (tokenizer.isMaxTime())
            return;

        Timer timerRunChecks((*it)->name() + "::runChecks", mSettings.showtime, &S_timerResults);
        (*it)->runChecks(&tokenizer, &mSettings, this);
    }

也就是说,it从Check::instances()中遍历所有项目。
Check::instances中有:

    名称  值   类型
▶   [0] 0x01557438 {cppcheck-core.dll!Check64BitPortability instance} {...} Check * {Check64BitPortability}
▶   [1] 0x01557494 {cppcheck-core.dll!CheckAssert instance} {...}   Check * {CheckAssert}
▶   [2] 0x015574ec {cppcheck-core.dll!CheckAutoVariables instance} {...}    Check * {CheckAutoVariables}
▶   [3] 0x01557550 {cppcheck-core.dll!CheckBool instance} {...} Check * {CheckBool}
▶   [4] 0x015575b8 {cppcheck-core.dll!CheckBoost instance} {...}    Check * {CheckBoost}
▶   [5] 0x01557614 {cppcheck-core.dll!CheckBufferOverrun instance} {...}    Check * {CheckBufferOverrun}
▶   [6] 0x01557774 {cppcheck-core.dll!CheckFunctions instance} {...}    Check * {CheckFunctions}
▶   [7] 0x0155768c {cppcheck-core.dll!CheckClass instance} {mSymbolDatabase=0x00000000 <NULL> } Check * {CheckClass}
▶   [8] 0x0155771c {cppcheck-core.dll!CheckCondition instance} {...}    Check * {CheckCondition}
▶   [9] 0x01557864 {cppcheck-core.dll!CheckExceptionSafety instance} {...}  Check * {CheckExceptionSafety}
▶   [10]    0x015578bc {cppcheck-core.dll!CheckIO instance} {...}   Check * {CheckIO}
▶   [11]    0x01557974 {cppcheck-core.dll!CheckLeakAutoVar instance} {...}  Check * {CheckLeakAutoVar}
▶   [12]    0x01557a7c {cppcheck-core.dll!CheckMemoryLeakNoVar instance4} {...} Check * {CheckMemoryLeakNoVar}
▶   [13]    0x01557a0c {cppcheck-core.dll!CheckMemoryLeakInClass instance2} {...}   Check * {CheckMemoryLeakInClass}
▶   [14]    0x015579d4 {cppcheck-core.dll!CheckMemoryLeakInFunction instance1} {...}    Check * {CheckMemoryLeakInFunction}
▶   [15]    0x01557a44 {cppcheck-core.dll!CheckMemoryLeakStructMember instance3} {...}  Check * {CheckMemoryLeakStructMember}
▶   [16]    0x01557b34 {cppcheck-core.dll!CheckNullPointer instance} {...}  Check * {CheckNullPointer}
▶   [17]    0x01557bb0 {cppcheck-core.dll!CheckOther instance} {...}    Check * {CheckOther}
▶   [18]    0x01557d20 {cppcheck-core.dll!CheckStl instance} {...}  Check * {CheckStl}
▶   [19]    0x01557cbc {cppcheck-core.dll!CheckSizeof instance} {...}   Check * {CheckSizeof}
▶   [20]    0x015577ec {cppcheck-core.dll!CheckString instance} {...}   Check * {CheckString}
▶   [21]    0x01557e98 {cppcheck-core.dll!CheckType instance} {...} Check * {CheckType}
▶   [22]    0x01557f00 {cppcheck-core.dll!CheckUninitVar instance} {...}    Check * {CheckUninitVar}
▶   [23]    0x01557f70 {cppcheck-core.dll!CheckUnusedFunctions CheckUnusedFunctions::instance} {mFunctions={ size=0 } ...}  Check * {CheckUnusedFunctions}
▶   [24]    0x01557ff8 {cppcheck-core.dll!CheckUnusedVar instance} {mIsRecordTypeWithoutSideEffectsMap={ size=0 } ...}  Check * {CheckUnusedVar}
▶   [25]    0x01557c64 {cppcheck-core.dll!CheckPostfixOperator instance} {...}  Check * {CheckPostfixOperator}
▶   [26]    0x01558070 {cppcheck-core.dll!CheckVaarg instance} {...}    Check * {CheckVaarg}

鉴于代码表明_instalces这是一个static变量,所以必然有代码调用了Check::instances().XXXX向它推送代码。

std::list<Check *> &Check::instances()
{
#ifdef __SVR4
    // Under Solaris, destructors are called in wrong order which causes a segmentation fault.
    // This fix ensures pointer remains valid and reachable until program terminates.
    static std::list<Check *> *_instances= new std::list<Check *>;
    return *_instances;
#else
    static std::list<Check *> _instances;
    return _instances;
#endif
}

查找所有的代码以后,只有构造函数有相关代码:

Check::Check(const std::string &aname)
    : mTokenizer(nullptr), mSettings(nullptr), mErrorLogger(nullptr), mName(aname)
{
    for (std::list<Check*>::iterator i = instances().begin(); i != instances().end(); ++i) {
        if ((*i)->name() > aname) {
            instances().insert(i, this);
            return;
        }
    }
    instances().push_back(this);
}

下断点,重新执行。

    cppcheck-core.dll!Check::Check(const std::basic_string<char,std::char_traits<char>,std::allocator<char> > & aname) 行 30 C++
    cppcheck-core.dll!Check64BitPortability::Check64BitPortability() 行 46   C++
>   cppcheck-core.dll!`anonymous namespace'::`dynamic initializer for 'instance''() 行 41    C++

可以看到这样的调用栈,再往下就是程序的初始化代码了,一层层看。

1:最上层可以看到一个类似全局变量的代码

// Register this check class (by creating a static instance of it)
namespace {
    Check64BitPortability instance;
}

2:可以看到检测的类都是公开继承Check的

class CPPCHECKLIB Check64BitPortability : public Check {
public:
    /** This constructor is used when registering the Check64BitPortability */
    Check64BitPortability() : Check(myName()) {
    }

3:随后代码走到Check中,该类被加入。

再保留断点继续执行,可以发现所有的Check都是这样加入的,因为这些Check类都是全局变量,所以程序一启动就会自动添加进去。等他们执行完了才会进入main。

好久没有写文章了

最近不是因为懒,而是因为确实太忙了,可能要等闲了以后再更新吧~

最近后台快被毛子的垃圾评论弄爆了,弄了个插件,现在会过滤所有非中文的评论,评论时请一定要带上一个中文符号。

黑名单列表:
所有西里尔字母
所有俄语网站URL
所有俄罗斯邮箱地址
所有超过3000字的评论
所有非中文评论

mmap地址随机化的问题

在团队进行漏洞利用的时候,发现对于mmap()返回的地址其实是处于一个可预测的状态的,mmap更偏向于选择一个最接近vma的地址,所以当只有攻击者能控制malloc而程序自身并不使用mmap分配时,vma会处于一个相对比较容易预测的位置,导致程序即使不知道malloc返回的地址,也可以有个相对高的可能性猜到某个位于mmap()之后区域的地址,这个ASLR绕过的问题就会比较麻烦。

而在lkml上也有相同的反馈,只不过在今年3月,这个问题已经有人提出来了,虽然还是在扯皮(到底是放在libc还是放在内核好),但是可以看一下思路。

From Ilya Smith
Subject [RFC PATCH v2 0/2] Randomization of address chosen by mmap.
Date Thu, 22 Mar 2018 19:36:36 +0300

当前实现不会将mmap返回的地址随机化。
所有熵的结尾都是基于在进程创建时选择mmap_base_addr。在此之后,mmap会产生非常可预测的地址空间布局。它允许在许多情况下绕过ASLR。此修补程序使mmap调用中的地址随机化。

v2:
改变了选择GAP的方式。现行的mmap版本中,没有试图得到所有可能的gap。在新版本中,将使用随机产生的地址,用作树的行走方向。
树采用回溯的方式遍历,直到找到合适的空隙(gap)时停止。当发现空隙时,地址从下一个VMA开始随机移动。

扩展了vm_unmapped_area_info结构,增加了新的字段random_shift ,可以用来在转移到下一个VMA开始时,设置与架构相关的限制值。
在x86-64体系结构中,32位应用程序的这种移动(shift)转换为256页,64位的为0x1000000页。

为了得到熵,代码采用了伪随机的方法。这是因为在英特尔x86-64处理器指令RDRAND在在大约10000次迭代之后(缓冲区被消耗)时工作非常缓慢。

这个特性可以通过设置randomize_va_space = 4来启用。(注:只是作者提议,似乎还没通过)

可以参看一下修改的具体内容:

Signed-off-by: Ilya Smith <blackzert@gmail.com>
---
 arch/alpha/kernel/osf_sys.c         | 1 +
 arch/arc/mm/mmap.c                  | 1 +
 arch/arm/mm/mmap.c                  | 2 ++
 arch/frv/mm/elf-fdpic.c             | 1 +
 arch/ia64/kernel/sys_ia64.c         | 1 +
 arch/ia64/mm/hugetlbpage.c          | 1 +
 arch/metag/mm/hugetlbpage.c         | 1 +
 arch/mips/mm/mmap.c                 | 1 +
 arch/parisc/kernel/sys_parisc.c     | 2 ++
 arch/powerpc/mm/hugetlbpage-radix.c | 1 +
 arch/powerpc/mm/mmap.c              | 2 ++
 arch/powerpc/mm/slice.c             | 2 ++
 arch/s390/mm/mmap.c                 | 2 ++
 arch/sh/mm/mmap.c                   | 2 ++
 arch/sparc/kernel/sys_sparc_32.c    | 1 +
 arch/sparc/kernel/sys_sparc_64.c    | 2 ++
 arch/sparc/mm/hugetlbpage.c         | 2 ++
 arch/tile/mm/hugetlbpage.c          | 2 ++
 arch/x86/kernel/sys_x86_64.c        | 4 ++++
 arch/x86/mm/hugetlbpage.c           | 4 ++++
 fs/hugetlbfs/inode.c                | 1 +
 include/linux/mm.h                  | 1 +
 mm/mmap.c                           | 3 ++-
 23 files changed, 39 insertions(+), 1 deletion(-)

+unsigned long unmapped_area_random(struct vm_unmapped_area_info *info)
+{
+   struct mm_struct *mm = current->mm;
+   struct vm_area_struct *vma = NULL;
+   struct vm_area_struct *visited_vma = NULL;
+   unsigned long entropy[2];
+   unsigned long length, low_limit, high_limit, gap_start, gap_end;
+   unsigned long addr = 0;
+
+   /* get entropy with prng */
+   prandom_bytes(&entropy, sizeof(entropy));
+   /* small hack to prevent EPERM result */
+   info->low_limit = max(info->low_limit, mmap_min_addr);
+
+   /* Adjust search length to account for worst case alignment overhead */
+   length = info->length + info->align_mask;
+   if (length < info->length)
+       return -ENOMEM;
+
+   /*
+    * Adjust search limits by the desired length.
+    * See implementation comment at top of unmapped_area().
+    */
+   gap_end = info->high_limit;
+   if (gap_end < length)
+       return -ENOMEM;
+   high_limit = gap_end - length;
+
+   low_limit = info->low_limit + info->align_mask;
+   if (low_limit >= high_limit)
+       return -ENOMEM;
+
+   /* Choose random addr in limit range */
+   addr = entropy[0] % ((high_limit - low_limit) >> PAGE_SHIFT);
+   addr = low_limit + (addr << PAGE_SHIFT);
+   addr += (info->align_offset - addr) & info->align_mask;
+
+   /* Check if rbtree root looks promising */
+   if (RB_EMPTY_ROOT(&mm->mm_rb))
+       return -ENOMEM;
+
+   vma = rb_entry(mm->mm_rb.rb_node, struct vm_area_struct, vm_rb);
+   if (vma->rb_subtree_gap < length)
+       return -ENOMEM;
+   /* use randomly chosen address to find closest suitable gap */
+   while (true) {
+       gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
+       gap_end = vm_start_gap(vma);
+       if (gap_end < low_limit)
+           break;
+       if (addr < vm_start_gap(vma)) {
+           /* random said check left */
+           if (vma->vm_rb.rb_left) {
+               struct vm_area_struct *left =
+                   rb_entry(vma->vm_rb.rb_left,
+                        struct vm_area_struct, vm_rb);
+               if (addr <= vm_start_gap(left) &&
+                   left->rb_subtree_gap >= length) {
+                   vma = left;
+                   continue;
+               }
+           }
+       } else if (addr >= vm_end_gap(vma)) {
+           /* random said check right */
+           if (vma->vm_rb.rb_right) {
+               struct vm_area_struct *right =
+               rb_entry(vma->vm_rb.rb_right,
+                    struct vm_area_struct, vm_rb);
+               /* it want go to the right */
+               if (right->rb_subtree_gap >= length) {
+                   vma = right;
+                   continue;
+               }
+           }
+       }
+       if (gap_start < low_limit) {
+           if (gap_end <= low_limit)
+               break;
+           gap_start = low_limit;
+       } else if (gap_end > info->high_limit) {
+           if (gap_start >= info->high_limit)
+               break;
+           gap_end = info->high_limit;
+       }
+       if (gap_end > gap_start &&
+           gap_end - gap_start >= length)
+           goto found;
+       visited_vma = vma;
+       break;
+   }
+   /* not found */
+   while (true) {
+       gap_start = vma->vm_prev ? vm_end_gap(vma->vm_prev) : 0;
+
+       if (gap_start <= high_limit && vma->vm_rb.rb_right) {
+           struct vm_area_struct *right =
+               rb_entry(vma->vm_rb.rb_right,
+                    struct vm_area_struct, vm_rb);
+           if (right->rb_subtree_gap >= length &&
+               right != visited_vma) {
+               vma = right;
+               continue;
+           }
+       }
+
+check_current:
+       /* Check if current node has a suitable gap */
+       gap_end = vm_start_gap(vma);
+       if (gap_end <= low_limit)
+           goto go_back;
+
+       if (gap_start < low_limit)
+           gap_start = low_limit;
+
+       if (gap_start <= high_limit &&
+           gap_end > gap_start && gap_end - gap_start >= length)
+           goto found;
+
+       /* Visit left subtree if it looks promising */
+       if (vma->vm_rb.rb_left) {
+           struct vm_area_struct *left =
+               rb_entry(vma->vm_rb.rb_left,
+                    struct vm_area_struct, vm_rb);
+           if (left->rb_subtree_gap >= length &&
+               vm_end_gap(left) > low_limit &&
+               left != visited_vma) {
+               vma = left;
+               continue;
+           }
+       }
+go_back:
+       /* Go back up the rbtree to find next candidate node */
+       while (true) {
+           struct rb_node *prev = &vma->vm_rb;
+
+           if (!rb_parent(prev))
+               return -ENOMEM;
+           visited_vma = vma;
+           vma = rb_entry(rb_parent(prev),
+                      struct vm_area_struct, vm_rb);
+           if (prev == vma->vm_rb.rb_right) {
+               gap_start = vma->vm_prev ?
+                   vm_end_gap(vma->vm_prev) : low_limit;
+               goto check_current;
+           }
+       }
+   }
+found:
+   /* We found a suitable gap. Clip it with the original high_limit. */
+   if (gap_end > info->high_limit)
+       gap_end = info->high_limit;
+   gap_end -= info->length;
+   gap_end -= (gap_end - info->align_offset) & info->align_mask;
+   /* only one suitable page */
+   if (gap_end ==  gap_start)
+       return gap_start;
+   addr = entropy[1] % (min((gap_end - gap_start) >> PAGE_SHIFT,
+                            0x10000UL));
+   addr = gap_end - (addr << PAGE_SHIFT);
+   addr += (info->align_offset - addr) & info->align_mask;
+   return addr;
+}
+
 unsigned long unmapped_area(struct vm_unmapped_area_info *info)
 {
    /*
-- 
2.7.4