Hatena::ブログ(Diary)

ablog このページをアンテナに追加 RSSフィード Twitter

2014-03-08

ls のソースを読んでプログラマになりました

Linux

タイトルは釣りですw*1

とあるテキストファイルを加工してCSVファイルを出力する Perl スクリプトがあり、ディレクトリ内のファイルをリストアップしてCSVファイルに出力しているのだが、なぜファイル名でソートされていないのか聞かれたので調べてみた。

その Perl スクリプトは File::DosGlob::glob でファイルリストを取得していたので、

yazekats% mkdir tmp
yazekats% cd tmp
yazekats% ls
yazekats% touch 3
yazekats% touch 2
yazekats% touch 1
yazekats% ls
1  2  3
yazekats% perl -MFile::DosGlob -e 'map{print qq/$_\n/} File::DosGlob::glob(q/*/)';
1
3
2

試してみると確かにソートされない。File::DosGlob のソースを見てみると、

	opendir(D, $head) or next OUTER;
	my @leaves = readdir D;
	closedir D;

readdir を呼んでいる。

yazekats% perl -e 'opendir(DIR, q/./);map{print qq/$_\n/}readdir(DIR);'
1
.
3
2
..

readdir でファイルリストを取得するとやはりソートされない。strace でシステムコールを見てみると、

yazekats% strace perl -e 'opendir(DIR, q/./);map{print qq/$_\n/}readdir(DIR);'                        
execve("/usr/bin/perl", ["perl", "-e", "opendir(DIR, q/./);map{print qq/"...], [/* 50 vars */]) = 0

...

open(".", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 3
fcntl(3, F_GETFD)                       = 0x1 (flags FD_CLOEXEC)
getdents(3, /* 5 entries */, 32768)     = 120
getdents(3, /* 0 entries */, 32768)     = 0

getdents システムコールでファイルリストを取得しているようだ。strace で ls が呼んでいるシステムコールを見ると、

yazekats% strace ls
execve("/bin/ls", ["ls"], [/* 50 vars */]) = 0

...

getdents(3, /* 5 entries */, 32768)     = 120
getdents(3, /* 0 entries */, 32768)     = 0

こちらも getdents を呼んでいる。Perl の readdir も ls も getdents システムコールを呼んでるけど、ls はソートしていると思われる。ls の man を見ると、

yazekats% man ls
NAME
       ls - list directory contents

SYNOPSIS
       ls [OPTION]... [FILE]...

DESCRIPTION
       List information about the FILEs (the current directory by default).  Sort entries alphabetically if none of -cftuvSUX nor --sort.

...

       -f     do not sort, enable -aU, disable -ls --color

デフォルトでアルファベットでソートされ、-f オプションをつけるとソートされないと書かれている。

yazekats% ls -f
1  .  3  2  ..

ls に -f オプションをつけると Perl の readdir と同じ順になった。

そう言えば、

lsを読まずにプログラマを名乗るな!

lsを読まずにプログラマを名乗るな!

とかいう本も見かけるので ls のソースコードを読んでみることにした。ls が含まれるパッケージを調べると、

[root@yazekats-linux ~]# rpm -qf /bin/ls
coreutils-8.4-19.0.1.el6.x86_64

coreutils のようだ。

[root@yazekats-linux ~]# mkdir -p /usr/src/gnu
[root@yazekats-linux ~]# cd /usr/src/gnu
[root@yazekats-linux gnu]# wget http://ftp.gnu.org/gnu/coreutils/coreutils-8.4.tar.gz
[root@yazekats-linux gnu]# tar xvfz coreutils-8.4.tar.gz
[root@yazekats-linux src]# cd coreutils-8.4/src
[root@yazekats-linux src]# wc -l ls.c
4712 ls.c

436 /* The file characteristic to sort by.  Controlled by -t, -S, -U, -X, -v.
437    The values of each item of this enum are important since they are
438    used as indices in the sort functions array (see sort_files()).  */
439 
440 enum sort_type
441   {
442     sort_none = -1,             /* -U */
443     sort_name,                  /* default */
444     sort_extension,             /* -X */
445     sort_size,                  /* -S */
446     sort_version,               /* -v */
447     sort_time,                  /* -t */
448     sort_numtypes               /* the number of elements of this enum */
449   };

...

3370 sort_files (void)
3371 {
3372   bool use_strcmp;
3373 
3374   if (sorted_file_alloc < cwd_n_used + cwd_n_used / 2)
3375     {
3376       free (sorted_file);
3377       sorted_file = xnmalloc (cwd_n_used, 3 * sizeof *sorted_file);
3378       sorted_file_alloc = 3 * cwd_n_used;
3379     }
3380 
3381   initialize_ordering_vector ();
3382 
3383   if (sort_type == sort_none)
3384     return;
3385 
3386   /* Try strcoll.  If it fails, fall back on strcmp.  We can't safely
3387      ignore strcoll failures, as a failing strcoll might be a
3388      comparison function that is not a total order, and if we ignored
3389      the failure this might cause qsort to dump core.  */
3390 
3391   if (! setjmp (failed_strcoll))
3392     use_strcmp = false;      /* strcoll() succeeded */
3393   else
3394     {
3395       use_strcmp = true;
3396       assert (sort_type != sort_version);
3397       initialize_ordering_vector ();
3398     }
3399 
3400   /* When sort_type == sort_time, use time_type as subindex.  */
3401   mpsort ((void const **) sorted_file, cwd_n_used,
3402           sort_functions[sort_type + (sort_type == sort_time ? time_type : 0)]
3403                         [use_strcmp][sort_reverse]
3404                         [directories_first]);
3405 }

ソースコードからもデフォルトでソートしていることがわかる。コンパイルして、

[root@yazekats-linux coreutils-8.4]# pwd
/usr/src/gnu/coreutils-8.4
[root@yazekats-linux coreutils-8.4]# ./configure
[root@yazekats-linux coreutils-8.4]# make "CFLAGS= -g"

gdb でステップ実行してみると、

yazekats% gdb ls                                                                                                                      [/usr/src/gnu/coreutils-8.4/src]
GNU gdb (GDB) Red Hat Enterprise Linux (7.2-60.el6)
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /usr/src/gnu/coreutils-8.4/src/ls...done.
(gdb) 
yazekats% gdb ls                                                                                                                      [/usr/src/gnu/coreutils-8.4/src]
GNU gdb (GDB) Red Hat Enterprise Linux (7.2-60.el6)
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-redhat-linux-gnu".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from /usr/src/gnu/coreutils-8.4/src/ls...done.
(gdb) b sort_files
Breakpoint 1 at 0x40798d: file ls.c, line 3374.
(gdb) run
Starting program: /usr/src/gnu/coreutils-8.4/src/ls 
[Thread debugging using libthread_db enabled]

Breakpoint 1, sort_files () at ls.c:3374
3374	  if (sorted_file_alloc < cwd_n_used + cwd_n_used / 2)
Missing separate debuginfos, use: debuginfo-install glibc-2.12-1.132.el6.x86_64
(gdb) n
3376	      free (sorted_file);
(gdb) n
3377	      sorted_file = xnmalloc (cwd_n_used, 3 * sizeof *sorted_file);
(gdb) n
3378	      sorted_file_alloc = 3 * cwd_n_used;
(gdb) n
3381	  initialize_ordering_vector ();
(gdb) n
3383	  if (sort_type == sort_none)
(gdb) n
3391	  if (! setjmp (failed_strcoll))
(gdb) n
3392	    use_strcmp = false;      /* strcoll() succeeded */
(gdb) n
3402	          sort_functions[sort_type + (sort_type == sort_time ? time_type : 0)]
(gdb) n
3401	  mpsort ((void const **) sorted_file, cwd_n_used,
(gdb) n
3402	          sort_functions[sort_type + (sort_type == sort_time ? time_type : 0)]
(gdb) n
3401	  mpsort ((void const **) sorted_file, cwd_n_used,
(gdb) n
3405	}
(gdb) n
print_dir (name=0x623c40 ".", realname=0x0, command_line_arg=true) at ls.c:2572
2572	  if (recursive)
(gdb) n
2575	  if (format == long_format || print_block_size)
(gdb) n
2590	  if (cwd_n_used)
(gdb) n
2591	    print_current_files ();
(gdb) n
Makefile	 copy.o		env.o ...

ソート処理が実行されていることがわかる。

Permalink | コメント(0) | トラックバック(0) | 23:04 ls のソースを読んでプログラマになりましたを含むブックマーク ls のソースを読んでプログラマになりましたのブックマークコメント

*1：500万ページビュー突破記念で適当なタイトルにしますた

コメントを書く

スパム対策のためのダミーです。もし見えても何も入力しないでください
 ゲスト

画像認証

トラックバック - http://d.hatena.ne.jp/yohei-a/20140308/1394287447
idトラックバック
リンク元
プロフィール

yohei-a

yohei-a

不器用で落着きのない技術者のメモ。

ページビュー
5004903
最新タイトル
最近言及したキーワード
yohei-aのアンテナ
最近のトラックバック
最近のコメント
最近書いたコメント

follow yoheia at http://twitter.com
TopHatenar
Amazonで購入