私が知っている限り、ファイルのinodeが見つかったらデータを見つけるのは簡単です。 inodeに保存されているディスクの特定の場所にアクセスするだけです。
しかし、問題は、システムにファイルパスが与えられたら、一体どのようにインデックスノードを見つけるのでしょうか?
私の質問の目的は、主にBツリーが実際の生活でどのように実装されているかを理解することです。私はその一般的なアイデアを理解していますが、それがUnixファイルシステムで正確にどのように実装されているのか(もしあれば)知りたいです。
ツリーの各ノードはinode番号を格納し、リーフもinode自体のディスクアドレスを保存しますか?それともファイルパスの連続部分ですか?
ディスクがハードドライブかSSDかによって実装が異なりますか?
答え1
IMHO:2つの質問があります:
システムにファイルパスを提供するときにインデックスノードを正確に見つける方法
そして
Bツリーが実際の生活でどのように実装されているかを知りたいです。
おそらくあなたの質問は、inodeがどのように保存されるか(b-tree)、またはinodeが参照するデータです。もしそうなら、私は答えることができません。
最初の文字通りの質問に対する回答は、オペレーティングシステムによって異なり、範囲not difficult
はopaque
。古典的なシステムコール(open、unlink)は、ファイル名エントリを探すディレクトリを読み込み(現代ではopendir()を呼び出すことによって)開始されます。
クラシックUNIXでは、ファイル名の最大長は14文字です。つまり、inode用に2バイト(ディレクトリエントリ用に16バイト)が残ります。ファイル名とinodeのbツリー構成はありませんでした(そしてまだそうです)。検索はディレクトリの連続読み込みでした(そして今もそうです)。これはsimple
必ず確認する必要があります。
長いファイル名を受け入れる今日のシステムでも、ディレクトリエントリのデフォルトの外観は変わらない可能性があります(2バイト(インデックスノード)、14バイト(初期ファイル名/フルファイル名))。 (少なくともAIXでは、すべて、ディレクトリもUNIX慣用語に従います。すべてがファイルであり、一部は特別です。)
michael@x071:[/home/michael]ls -lia /tmp | head
total 287464
2 drwxrwxrwt 54 bin bin 36864 Jan 22 13:35 .
2 drwxr-xr-x 39 root system 4096 Jan 5 12:27 ..
5 drwxrwxrwt 2 root system 256 May 8 2013 .X11-unix
6 -rw-r----- 1 root system 0 May 23 2014 .ahafs.out.michael.10223652
7 -rw-r----- 1 root system 0 May 23 2014 .ahafs.out.michael.9502870
8 -r--r--r-- 1 root system 25 Jun 9 2013 .aix_ISMP_lock____.save
9 drwxrwxrwt 3 root system 4096 Dec 27 12:15 .com_ibm_tools_attach
62 -rw-r--r-- 1 root system 3124 Dec 27 11:21 .ctinst.log
63 -rw-r----- 1 michael felt 2578 Aug 16 2013 .htaccess
michael@x071:[/home/michael]od -dc /tmp | head -20
0000000 2 11776 0 0 0 0 0 0
\0 002 . \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
0000020 2 11822 0 0 0 0 0 0
\0 002 . . \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0 \0
0000040 32848 11895 28530 27492 26994 11825 13109 13878
200 P . w o r k d i r . 1 3 5 6 6
0000060 5 11864 12593 11637 28265 30720 0 0
\0 005 . X 1 1 - u n i x \0 \0 \0 \0 \0
0000100 6 11873 26721 26227 11887 30068 11885 26979
\0 006 . a h a f s . o u t . m i c
0000120 7 11873 26721 26227 11887 30068 11885 26979
\0 \a . a h a f s . o u t . m i c
0000140 8 11873 27000 24393 21325 20575 27759 25451
\0 \b . a i x _ I S M P _ l o c k
0000160 9 11875 28525 24425 25197 24436 28527 27763
\0 \t . c o m _ i b m _ t o o l s
0000200 62 11875 29801 28275 29742 27759 26368 0
\0 > . c t i n s t . l o g \0 \0 \0
0000220 63 11880 29793 25443 25971 29440 0 0
\0 ? . h t a c c e s s \0 \0 \0 \0 \0
注:上記はLinuxシステムで試行されました。おそらく今Bツリーで構成されているでしょう。わかりません。次のような結果が出ます。
michael@x067:~$ od -dc /tmp|head
od: /tmp: read error: Is a directory
0000000
したがって、伝統的に(特殊)ファイルのinode "照会/マッピング"は、ディレクトリエントリの最初の2バイトにすぎません。インデックスノードはディスクに配置されるか、Bツリーなどのメモリに保存されます。
AIXでは、「dirent」構造は次の形式で「簡単に見つけることができます」。
#define _D_NAME_MAX 255
struct dirent {
__ulong64_t d_offset; /* real off after this entry */
ino_t d_ino; /* inode number of entry */
ushort_t d_reclen; /* length of this record */
ushort_t d_namlen; /* length of string in d_name */
char d_name[_D_NAME_MAX+1]; /* name must be no longer than this */
/* redefine w/#define when name decided */
};
Linux(3.2.XYカーネル)の場合、インクルードファイルには次の構造が含まれています。
struct dirent
{
#ifndef __USE_FILE_OFFSET64
__ino_t d_ino;
__off_t d_off;
#else
__ino64_t d_ino;
__off64_t d_off;
#endif
unsigned short int d_reclen;
unsigned char d_type;
char d_name[256]; /* We must not include limits.h! */
};
両方(IMHO)はデフォルトで同じです。戻り時にreaddir()を呼び出すと、違いを取り除くことができます。
Linux/GNU メソッド:
/usr/include/dirent.h:
/* This is the data type of directory stream objects.
The actual structure is opaque to users. */
typedef struct __dirstream DIR;
注:__dirstreamについて何も見つからなかったため、これに「説明」を追加しました。
opaque
extern DIR *opendir (__const char *__name) __nonnull ((1));
...
/* Read a directory entry from DIRP. Return a pointer to a `struct
dirent' describing the entry, or NULL for EOF or error. The
storage returned may be overwritten by a later readdir call on the
same DIR stream.
If the Large File Support API is selected we have to use the
appropriate interface.
This function is a possible cancellation point and therefore not
marked with __THROW. */
#ifndef __USE_FILE_OFFSET64
extern struct dirent *readdir (DIR *__dirp) __nonnull ((1));
#else
# ifdef __REDIRECT
extern struct dirent *__REDIRECT (readdir, (DIR *__dirp), readdir64)
__nonnull ((1));
# else
# define readdir readdir64
# endif
#endif
#ifdef __USE_LARGEFILE64
extern struct dirent64 *readdir64 (DIR *__dirp) __nonnull ((1));
#endif
AIXの場合:
/*
* Definitions for library routines operating on directories.
*/
typedef struct _dirdesc {
#ifdef _ALL_SOURCE
int dd_fd; /* file descriptor of directory */
blksize_t dd_blksize; /* this filesystem's block size */
char *dd_buf; /* malloc'd buffer depending of fs bsize */
long dd_size; /* size of buffer */
long dd_flag; /* private flags for readdir, unused */
off_t dd_loc; /* logical(dirent) offset in directory */
off_t dd_curoff; /* real offset in directory corresponding
* to dd_loc */
#else
int __dd_fd; /* file descriptor of directory */
blksize_t __dd_blksize; /* this filesystem's block size */
char *__dd_buf; /* malloc'd buffer depending of fs bsize */
long __dd_size; /* size of buffer */
long __dd_flag; /* private flags for readdir, unused */
off_t __dd_loc; /* logical(dirent) offset in directory */
off_t __dd_curoff; /* real offset in directory corresponding
* to dd_loc */
#endif
#if defined(_THREAD_SAFE) && defined(_ALL_SOURCE)
void *dd_lock; /* for inter-thread locking */
#endif
} DIR;
...
extern DIR *opendir(const char *);
extern struct dirent *readdir(DIR *);
つまり、IMHOは、OSに応じて構造がon disk
非常に簡単かopaque
。カーネルでは、opaque
アプリケーションコードを変更せずに組織を変更できる組織であれば驚かないでしょう。