貓の中秋’s blog~

昨天跟骨头因为某些原因谈到了 linux 中进程的栈有多大的问题。从 ulimit -a 中可以看出，栈大小是 8M ，但经过试验，发现并非如此。看来唯有用实验的方法找了。

这是测试程序的代码

int main()
{
        char a[S_SIZE];
        a[0] = '\1';
        return 0;
}

通过控制 S_SIZE 的值，观测程序是否因段错误崩溃，就可以大致知道栈空间有多大。至于寻找 S_SIZE，我使用了二分的方法。

但奇怪的是，寻找出来的 S_SIZE 的值竟然每次都不同，骨头他也发现当 a 的大小在某个区域（大约在 8380000 字节附近）时，程序段错误出现了随机性。实在太奇怪了。

既然出现了随机性，于是便统计了成功运行（即没有出现段错误）的概率和 a 大小的关系：(骨头供图，横坐标是 a 的大小，单位字节，纵坐标是成功概率，单位 %)

噢，看来是线性相关哦。根据老狼的解释，程序进入 main() 之前，先进入了 glibc 里的 _start()，并占用了部分的栈。如果是这样的话，留给 main() 的栈空间大小大概为 8376000Byte ~ 8384200Byte，且呈均匀分布（即栈大小为在此区间内各值的机率是均等的）。至于为什么会这样，可能跟 _start 的实现有关，就不清楚了。

附一篇 Before main() 分析。貌似很复杂，我没深入看。

昨天跟骨头研究栈大小的问题时，发现在栈上分配同样大小的数组，我的程序段错误了，骨头的竟然没事！怎么回事呢？我把他的程序拿来对比：

我的版本

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

骨头的版本

int main ()
{
        char a[8*1024*1024];
        return 0;
}

看来只有 main 的声明方式不同。但为什么我的就会崩溃呢，通过看汇编代码终于找到了原因。

先看骨头的版本

main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        subq    $8388488, %rsp
.LCFI2:
        movl    $0, %eax
        leave
        ret

然后是我的

main:
.LFB2:
        pushq   %rbp
.LCFI0:
        movq    %rsp, %rbp
.LCFI1:
        subq    $8388504, %rsp
.LCFI2:
        movl    %edi, -8388612(%rbp)
        movq    %rsi, -8388624(%rbp)
        movl    $0, %eax
        leave
        ret

看来那句数组声明并没有实际的“分配”空间，而只是简单的移动栈顶（%rsp）。而 gcc 又可能使用了某种调用协议，使用 %edi 和 %rsi 传递前两个参数，于是在把寄存器参数压到栈上时，就段错误了。

昨天无意发现 ctags 竟然没有生成标准库中 fopen 的 tag。太诡异了，多方询问未果只好问 ctags 的 mailing list：

On Sun, August 17, 2008 03:37, AutumnCat wrote:
> > ctags /usr/include/stdio.h grep fopen tags (Found nothing)
> >
> > ctags –c-kinds=+x /usr/include/stdio.h grep fopen tags (Found nothing)

+x asks for variable declarations, not function declarations. you want +p.

–verbose will probably show that your .h file is being interpreted as C++
(though that won’t matter in this case).

depending on the actual contents of your stdio.h (you don’t say what
system you’re on), you may have extra stuff in your declarations. for
example. glibc on Ubuntu 8.04 has something like "fopen1" here:

extern FILE *fopen1 (__const char *__restrict __filename, __const char
*__restrict __modes) __wur;
extern FILE *fopen2 (__const char *__restrict __filename, __const char
*__restrict __modes) ;
extern FILE *fopen3 (__const char * __filename, __const char * __modes)
__wur;
extern FILE *fopen4 (__const char * __filename, __const char * __modes) ;
extern FILE *fopen5 ( char * __filename,  char * __modes) ;
extern void f ( char * __filename,  char * __modes) ;
extern void f_wur ( char * __filename,  char * __modes) __wur ;

but you can see that ctags only copes with a subset of these:

lithium:/tmp$ ctags -o – –c++-kinds=+xp –verbose /tmp/stdio.h
Reading command line arguments
OPENING /tmp/stdio.h as C++ language include file
sorting tag file
f       /tmp/stdio.h    /^extern void f ( char * __filename,  char * __modes) ;$/;"     p
fopen2  /tmp/stdio.h    /^extern FILE *fopen2 (__const char *__restrict
__filename, __const char *__restrict __modes) ;$/;"     p
fopen4  /tmp/stdio.h    /^extern FILE *fopen4 (__const char * __filename,
__const char * __modes) ;$/;"   p
fopen5  /tmp/stdio.h    /^extern FILE *fopen5 ( char * __filename,  char *
__modes) ;$/;"  p
lithium:/tmp$

adding -I_wur works around this:

lithium:/tmp$ ctags -o – –c++-kinds=+xp -I__wur –verbose /tmp/stdio.h
Reading command line arguments
OPENING /tmp/stdio.h as C++ language include file
sorting tag file
f       /tmp/stdio.h    /^extern void f ( char * __filename,  char * __modes) ;$/;"     p
f_wur   /tmp/stdio.h    /^extern void f_wur ( char * __filename,  char *
__modes) __wur ;$/;"    p
fopen1  /tmp/stdio.h    /^extern FILE *fopen1 (__const char *__restrict
__filename, __const char *__restrict __modes) __wur;$/;"        p
fopen2  /tmp/stdio.h    /^extern FILE *fopen2 (__const char *__restrict
__filename, __const char *__restrict __modes) ;$/;"     p
fopen3  /tmp/stdio.h    /^extern FILE *fopen3 (__const char * __filename,
__const char * __modes) __wur;$/;"      p
fopen4  /tmp/stdio.h    /^extern FILE *fopen4 (__const char * __filename,
__const char * __modes) ;$/;"   p
fopen5  /tmp/stdio.h    /^extern FILE *fopen5 ( char * __filename,  char *
__modes) ;$/;"  p
lithium:/tmp$

_wur, since you ask, is a glibc macro for the GCC 3.4 or later
__attribute__ ((__warn_unused_result__)).

 –elliott

> > but
> >
> > grep fopen /usr/include/stdio.h extern FILE *fopen (__const char
> > *__restrict __filename,
> > extern FILE *__REDIRECT (fopen, (__const char *__restrict __filename,
> > __const char *__restrict __modes), fopen64)
> > # define fopen fopen64
> > extern FILE *fopen64 (__const char *__restrict __filename, extern FILE
> > *fopencookie (void *__restrict __magic_cookie,
> >
> >
> > Why ?
> >
> >
> > ————————————————————————-
> >  This SF.Net email is sponsored by the Moblin Your Move Developer’s
> > challenge Build the coolest Linux based applications with Moblin SDK & win
> > great prizes Grand prize is a trip for two to an Open Source event
> > anywhere in the world
> > http://moblin-contest.org/redirect.php?banner_id=100&url=/_______________
> > ________________________________
> > Ctags-users mailing list
> > Ctags-users@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/ctags-users
> >
> >

– Elliott Hughes, http://www.jessies.org/~enh/

换句话说，就是个 gcc 的扩展在作怪，__wur 干扰了 ctags 的解析。

经 hellwolf，manphiz 指导，终于发现问题所在。

举一个例子：

/* a.h */
#define foobar

/* a.c */
#include "a.h"

void foo(void) foobar
{
        ;
}

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

看这个：

$ ctags --language-force=c --c-kinds=+xp -o - -R .
foobar  a.h     1;"     d
main    a.c     /^int main (int argc, char const* argv[])$/;"   f

噢？void foo(void) 到哪去了呢？加上 -I 参数试试：

$ ctags --language-force=c --c-kinds=+xp -o - -I foobar  -R .                                                             
foo     a.c     /^void foo(void) foobar$/;"     f
foobar  a.h     1;"     d
main    a.c     /^int main (int argc, char const* argv[])$/;"   f

由此看出，ctags 并不展开宏。由于宏 foobar 没有被展开，造成了错误的语法。其实 ctags 的 man 中早有提及（果然还是要RTFM……）：

Because ctags is neither a preprocessor nor a compiler, use of preprocessor macros can fool ctags into either missing tags or improperly generating inappropriate tags. Although ctags has been designed to handle certain common cases, this is the single biggest cause of reported problems. In particular, the use of preprocessor constructs which alter the textual syntax of C can fool ctags. You can work around many such problems by using the -I option.

参考《算法艺术与信息学竞赛》219页
令 (a,b)=d, 且 a<=b, 存在 ax+by=d, 求 x,y 可以用扩展的欧几里得辗转相除法.

function extended_gcd(a,b : longint; var x,y:longint):longint;
var
        t : longint;
begin
        if b=0 then begin
                extended_gcd:=a;
                x:=1;
                y:=0;
        end
        else begin
                extended_gcd:=extended_gcd(b, a mod b, x,y);
                t:=x;
                x:=y;
                y:=t-(a div b)*y;
        end;
end;

原书第9行代码有误, 原书为 extended_gcd:=extended_gcd(b, a mod b); , 应为 extended_gcd:=extended_gcd(b, a mod b, x,y);

下面给出推导过程:

若
ax+by=d
(a,b)=d
令
a’=b
b’=a mod b
则
(a’,b’)=d
假设已求出
a’x'+b’y'=d 有解 x’, y’
设 k=a div b, 则
a=ka’+b’, b=a’
所以
(ka’+b’)x+a’y=d
=> a’(kx+y)+b’x=d
所以可有
kx+y=x’
x=y’
即
x=y’
y=x’-kx=x’-(a’ div b’)y’

故算法正确

RT, 发现多个 session 时可以自己选择

#!/usr/bin/perl -w
#
# A wrapper for screen.
#

use strict ;

if (system("which screen > /dev/null") == 0) {
    # screen is found
    my $screen_command = `which screen` ;
    chomp $screen_command ;

    if ($#ARGV != -1) {
        exec "$screen_command" , @ARGV ;
    } else {
        my @sock_list = `$screen_command -ls` ;
        @sock_list = grep { s/^\s*// ; m/tached/ } @sock_list ;
        if ($#sock_list == -1) {
            exec "$screen_command"
        } elsif ($#sock_list == 0) {
            exec "$screen_command -x"
        } else {
            print "There are ",$#sock_list+1," screens. Please choose one to attache.\n\n";
            for(my $i=0; $i <= $#sock_list; $i++) {
                print " ",$i+1,"\t",$sock_list[$i];
            }
            print "\nPress ENTER to choose the first one for default.\n" ;
            print "Your choice: ";
            while (my $choice = <STDIN>) {
                chomp $choice;
                if ($choice eq '') {$choice = 1};
                if (($choice =~ m/\d+/) && ($choice >=1 ) && ($choice <= $#sock_list+1)) {
                    $sock_list[$choice-1] =~ m/^(\S+).*$/ ;
                    exec $screen_command." -x $1";
                } else {
                    print "Please choose from [1-",$#sock_list+1,"] : ";
                }
            }
        }
    }
}
else {
    print STDERR "Error: screen not found. Have you installed screen?\n" ;
    exit -1;
}