今天考试考了一道需要递归 $10^5$层的题目。。。

然后我就发现我爆栈了

然后我就手写模拟栈递归浪费了很多时间

虽然其实评测的时候带了编译开栈命令,但是那个命令是 Windows 底下的,所以我 Ubuntu 就没辙了。

然后去网上搜手动开栈,但都是很久以前的代码,目前的 G++编译器已经不能编译了 QvQ

最后找到一段报错还算比较少的代码,改了改就能用了。

Windows10 64 位版本和 Ubuntu 16.04 LTS 64 位版本下编译测试通过。

G++版本:

g++ --version
g++ (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609
Copyright (C) 2015 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

首先我们上一段会爆栈的代码

#include <bits/stdc++.h>

using namespace std;

void main2()
{
    int arr[10000000];
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    main2();
    return 0;
}

很显然不会输出”QvQ” 这三个字,而会直接爆栈 Segment Fault,因为在函数 main2() 内开了个 38MB 的数组,而 Ubuntu 下栈空间默认是 8MB。

我们再上一段扩栈后的代码

#include <bits/stdc++.h>

using namespace std;

extern void main2(void) __asm__ ("main2"); 

void main2()
{
    int arr[10000000];
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    int size = 128 << 20; // 128 MB
    char* p = new char[size] + size;
    __asm__ __volatile__(  
        "movq %0, %%rsp\n"
        "pushq $exit\n"
        "jmp main2\n"
        :: "r"(p));
    main2();
    return 0;
}

于是我们就愉♂快地发现它没有爆栈,而是输出了可爱的 “QvQ”

这是因为我们先申请了 128MB 的内存,并用指针 p 表示这段内存。

然后我们把 main2() 所申请的栈空间放在了 p 里面

实际上如果在 main2() 里调用函数,比如这样:

#include <bits/stdc++.h>

using namespace std;

extern void main2(void) __asm__ ("main2"); 

void boom()
{
    int arr[10000000];
}

void main2()
{
    boom();
    puts("QvQ"), exit(0);
}

int main(int argc, char const* argv[])
{
    int size = 128 << 20; // 128 MB
    char* p = new char[size] + size;
    __asm__ __volatile__(  
        "movq %0, %%rsp\n"
        "pushq $exit\n"
        "jmp main2\n"
        :: "r"(p));
    main2();
    return 0;
}

是依然能输出可爱的”QvQ” 的!

因为 boom() 函数也是在 main2() 内调用的!

所以栈空间也会存到 p 内

这就意味着我们可以用这个扩栈来防止递归爆栈。。。

真是有趣 QvQ

不过好像 BZOJ 上会 CE,估计是它的编译器实在是版本太老了

别的 OJ 没试过 QvQ

另外 32 位机也没试过,要是有同学试了 32 位机的请在底下留言告诉我情况吧哈哈= ̄ω ̄=

Update

有同学反馈代码在 32 位机上运行正常

(^-^)V

分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

13 条评论

masnn · 2019年8月23日 6:57 下午

/usr/bin/ld: /tmp/ccmZyElx.o: relocation R_X86_64_32S against symbol `exit@@GLIBC_2.2.5' can not be used when making a shared object; recompile with -fPIC
/usr/bin/ld: final link failed: Nonrepresentable section on output
collect2: error: ld returned 1 exit status

    masnn · 2019年8月23日 6:58 下午

    嗯。。加了-fPIC 并没有用

    Remmina · 2019年8月23日 11:30 下午

    啊,虽然我并不是这篇文章的作者,但也许能帮到您。
    您能告知一下您的:

    • 系统环境
    • g++版本

    吗?
    (实际上很可能我帮不到您因为我已经长年累月未使用 Linux 了)

    lyyQAQ · 2022年9月8日 9:53 上午

    可以加上 -no-pie

foreverpiano · 2018年3月2日 11:48 下午

#pragma comment(linker, "/STACK:102400000,102400000")

如果可以开编译选项的话这样也可以的吧

    konnyakuxzy · 2018年3月3日 8:34 上午

    Ubuntu 16.04 LTS 64 位下测试您那个命令并没有用
    并不知道为什么

juruo-oier · 2018年3月2日 8:01 下午

大佬 32 位可以

Cai · 2018年3月2日 7:42 下午

为什么不直接修改 Lemon 的代码文件?

为什么不直接修改 Ubuntu 里面关于 ulimit(limit) 的配置文件?

    konnyakuxzy · 2018年3月2日 8:56 下午

    OrzCai
    很显然这样的话可以强行开栈啊
    就算评测的人没开我们也不怕是不是
    至于修改 ulimit…
    这样我觉得不是很好吧。。。
    比如会不会出现出题人故意让您爆栈呢?

      Cai · 2018年3月2日 9:12 下午

      然而您内嵌汇编可是直接 GG 啊

      (好像 CC 并不查这东西

        konnyakuxzy · 2018年3月2日 9:41 下午

        Orz
        也许吧
        我太弱了不清楚
        其实一般不需要手动开栈的

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注