현재 영문 번역이 진행중입니다.... (English translation is under construction.)
Big Picture
-----------
0 +-----------------------+ Block group details
| | /
1024 +-----------------------+ / +-------------------------------+
| super block | / | Super block copy |
2048 +-----------------------+ / +-------------------------------+
| | / | Group Descriptor Table |
+-----------------------+/ +-------------------------------+
| Block group 0 | | Block Bitmap |
+-----------------------+ +-------------------------------+
| Block group 1 | | Inode Bitmap |
+-----------------------+ +-------------------------------+
| ... | | Inode Record |
+-----------------------+ +-------------------------------+
| Block group n | +---+--| |-----+
+-----------------------+ | | | Inode Table | |
| | | |<-+ |
| | +-------------------------------+ | |
| | | .... | | |
| | +-------------------------------+ | |
| +->| File Content | | |
| +-------------------------------+ | |
| | ... | | |
| +-------------------------------+ | |
+----->| Directory entries |--+ |
+-------------------------------+ |
| ... | |
+-------------------------------+ |
| File Content |<----+
+-------------------------------+
ext4 raw block에 대해서 분석해 놓은 자료를 찾기 힘든관계로, kernel source를 분석한 내용을 바탕으로 정리해 본다.
(특히 directory쪽에 집중했다.)
==> 개인적인 분석에 근거한 것이므로 정확도는 보장할 수 없다는... -_-;
In my case, it's very difficult to find documents regarding ext4 raw block. So, I described some parts of them based on Linux kernel source codes. (especially, focusing on directory part).
==> This is just personal analysis. So, I can't guarantee correctness.. :-)
File system의 기본 정보는 super block에 저장되어 있다. ext4 super block에 대한 detail은 Linux kernel에서 "struct ext4_super_block"을 참고하면되고 여기서는 몇몇개만 언급해 보면
s_log_block_size : file system block size (단위 KB). 보통 4. 즉 4KB
s_blocks_per_group : 하나의 block group을 이루는 block 개수
s_inodes_per_group :
s_inode_size : ext4의 경우 256
s_inodes_count : total inode count
Super block contains basic information of file system. For ext4 super block, struct ext4_super_block of Linux kernel source, is good reference for details. Let me describe some of them.
s_log_block_size : size of file system block size (KB). usually 4 - 4KB
s_blocks_per_group : number of blocks in a 'block group'
s_inodes_per_group :
s_inode_size : 256 in case of ext4
s_inodes_count : total inode count
ext4의 경우 기존의 indirect block의 개념 + extent라는 개념을 사용하고 있다.
ext4 uses existing indirect-block + extent.
(details for indirect block : http://computer-forensics.sans.org/blog/2008/12/24/understanding-indirect-blocks-in-unix-file-systems/)
먼저 http://computer-forensics.sans.org/blog/2010/12/20/digital-forensics-understanding-ext4-part-1-extents <= 이곳의 내용을 읽어보도록 하자.
Please read above link before moving forward.
아래는 ext4.h 에서 발췌한 내용이다.
Followings comes from ext4.h
... (생략 skip) ...
/*
* Constants relative to the data blocks
*/
#define EXT4_NDIR_BLOCKS 12
#define EXT4_IND_BLOCK EXT4_NDIR_BLOCKS
#define EXT4_DIND_BLOCK (EXT4_IND_BLOCK + 1)
#define EXT4_TIND_BLOCK (EXT4_DIND_BLOCK + 1)
#define EXT4_N_BLOCKS (EXT4_TIND_BLOCK + 1)
struct ext4_inode {
... (생략 skip) ...
__le32 i_blocks_lo; /* Blocks count */
... (생략 skip) ...
__le32 i_block[EXT4_N_BLOCKS]; /* pointers to blocks */
... (생략 skip) ...
}
ext4의 inode에서 실제 block을 나타내기 위해서 60 bytes (sizeof i_block)를 사용하고 있는다.
전통적인 direct/indirect block을 위해서라면, 15 index를 사용할 수 있다.
60 bytes (sizeof i_block) is used to represent real block at ext4-inode.
EXT4_N_BLOCKS == 15. Therefore 15 * 4 = 60 is used as pointers indicating real block.
For direct/indirect block, 15 indexes are available.
i_blocks_lo 의 경우 i_blocks_high와 함께 이 inode에 할당된 block의 count를 가지고 있다.
여기서 주의할 점의 여기서 사용되는 block의 size는 일반적인 super block에 저장된 그 block size(보통 4KB)가 아니라, 512 bytes라는 점이다. ext4/inode.c를 보면, "<< 9" 혹은 ">> 9"등의 표현을 종종 볼 수 있는데, 이것이 바로 512 bytes 단위를 표현하기 위한 것이다. 추가적으로 아래를 참고하자.
inode_add_bytes() : fs/stat.c ==> 512라는 숫자가 직접적으로 등장하기도 한다.
reserve_backup_gdb() : ext4/resize.c ==> "inode->i_blocks += reserved_gdb * sb->s_blocksize >> 9;"
i_blocks_lo and i_blocks_high has count of blocks allocated for the inode.
One thing to note, is block size here is NOT 4KB - usually mentioned at super block - but 512 bytes.
Expressions like "<< 9" and ">> 9" are often shown at ext4/inode.c, and this represents 512 bytes block size.
For additional information, please see
inode_add_bytes() : fs/stat.c ==> number '512' is shown up explicitly.
reserve_backup_gdb() : ext4/resize.c ==> "inode->i_blocks += reserved_gdb * sb->s_blocksize >> 9;"
한가지 더 짚고 넘어갈 내용은, i_blocks_lo가 meta data를 위한 block까지 포함하느냐? 의 문제이다.
ext4_ext_swap_inode_data : ext4/migrate.c를 보면, 아래의 코드라인이 보인다.
One more thing to consider is whether i_blocks_lo includes block for meta data or not?
Following lines of codes are observed at ext4_ext_swap_inode_data : ext4/migrate.c
/*
* Update i_blocks with the new blocks that got
* allocated while adding extents for extent index
* blocks.
*
* While converting to extents we need not
* update the orignal inode i_blocks for extent blocks
* via quota APIs. The quota update happened via tmp_inode already.
*/
spin_lock(&inode->i_lock);
inode->i_blocks += tmp_inode->i_blocks;
즉 meta data를 위한 block역시 i_blocks_lo에 count된다는 뜻이다.
Note : But, meta data is NOT real data of file. So, it doesn't have logical block index.
inode의 extent의 경우 60 bytes를 아래와 같은 format으로 사용한다.
Extent for inode uses 60 bytes as following format.
|<- 12 bytes ->|<- 12 bytes ->|<- 12 bytes ->|<- 12 bytes ->|<- 12 bytes ->|
+--------------+--------------+--------------+--------------+--------------+
| header | extent0 | extent1 | extent2 | extent3 |
+--------------+--------------+--------------+--------------+--------------+
관련 code는 아래와 같다 (from ext4_extents.h)
Here are related code (from ext4_extents.h)
/*
* ext4_inode has i_block array (60 bytes total).
* The first 12 bytes store ext4_extent_header;
* the remainder stores an array of ext4_extent.
*/
/*
* This is the extent on-disk structure.
* It's used at the bottom of the tree.
*/
struct ext4_extent {
__le32 ee_block; /* first logical block extent covers */
__le16 ee_len; /* number of blocks covered by extent */
__le16 ee_start_hi; /* high 16 bits of physical block */
__le32 ee_start_lo; /* low 32 bits of physical block */
};
/*
* This is index on-disk structure.
* It's used at all the levels except the bottom.
*/
struct ext4_extent_idx {
__le32 ei_block; /* index covers logical blocks from 'block' */
__le32 ei_leaf_lo; /* pointer to the physical block of the next *
* level. leaf or next index could be there */
__le16 ei_leaf_hi; /* high 16 bits of physical block */
__u16 ei_unused;
};
/*
* Each block (leaves and indexes), even inode-stored has header.
*/
struct ext4_extent_header {
__le16 eh_magic; /* probably will support different formats */
__le16 eh_entries; /* number of valid entries */
__le16 eh_max; /* capacity of store in entries */
__le16 eh_depth; /* has tree real underlying blocks? */
__le32 eh_generation; /* generation of the tree */
};
하나의 extent는 연속된 physical block을 나타낸다.
ee_start_hi / ee_start_lo
start block index. ext4는 48bit block index를 사용하고 있다는 것을 상기하자.
sizeof(ee_start_hi) == 2, sizeof(ee_start_lo) == 4
ee_len
length of continous block. __le16 type이므로, 최대 32768개의 연속 block을 나타낼 수 있고, 4KB block size일 경우, 최대 4K * 32768 = 128M 를 표시할 수 있다.
eh_max
현재 block에서 가질 수 있는 max entry 수. entry 수가 이 값을 넘어가면 extent/index 를 split해야 한다.
size = (inode->i_sb->s_blocksize - sizeof(struct ext4_extent_header))
/ sizeof(struct ext4_extent);
--- or ---
size = sizeof(EXT4_I(inode)->i_data);
size -= sizeof(struct ext4_extent_header);
size /= sizeof(struct ext4_extent_idx);
--- or ---
size = sizeof(EXT4_I(inode)->i_data);
size -= sizeof(struct ext4_extent_header);
size /= sizeof(struct ext4_extent);
One extent represents continuous physical blocks.
ee_start_hi / ee_start_lo
start block index. remind that ext4 uses 48bit for block index.
sizeof(ee_start_hi) == 2, sizeof(ee_start_lo) == 4
ee_len
length of continuous block. It's type is __le16. Therefore it can represent maximum 32768 continuous blocks. And in case that block size is 4KB, it can represent maximum 4K * 32768 = 128MB.
eh_max
maximum number of entries in current block. extent/index should be splitted if number of entries exceeded this value.
따라서, 4KB block size를 가정하면, ext4_inode의 i_block array는
최악의 경우 : continuous한 block이 없을 경우 (즉 하나의 extent가 오직 한 block만 가리킨다. ee_len = 1)
4K * 4 = 16KB
최상의 겨우 : ee_len = 32768
128M * 4 = 512M
까지 나타낼 수 있다.
So, assuming 4KB block size, i_block array of ext4_inode can represent
worst case : There is no continuous block. (That is, one extent can indicate only one block. ee_len = 1)
4K * 4 = 16KB
best case : ee_len = 32768
128M * 4 = 512M
이 한계를 극복하기 위해서 HTree방식의 extent tree가 사용된다.
아래는 ext4의 extent tree의 layout이다.(출처 : ols2007v2-pages-21-34.pdf from kernel.org)
To win over this limitation, HTree algorithm is used for extent tree.
Following picture is layout of ext4 extent tree.(The source : ols2007v2-pages-21-34.pdf from kernel.org)
(http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&sqi=2&ved=0CEwQFjAA&url=http%3A%2F%2Fkernel.org%2Fdoc%2Fols%2F2007%2Fols2007v2-pages-21-34.pdf&ei=PLHWT_rUOayUiAew86mSAw&usg=AFQjCNF8Yzcg4Z5VRsEGWLMCEWNEJGx2sw&sig2=SDilL5_ETwCMRA9--mQ8lA)
이런 방식의 위의 한계를 극복하고 있다.
This is the way to recover above limitation.
inode의 extent는 60 bytes만 사용가능하지만, leaf nodes의 extent의 경우는 한 block전체를 사용하므로, 처음 12 bytes header를 제외하면, 그 뒤는 쭉~ "struct ext4_extent"의 array이다. array의 크기는 header->eh_entries에 저장되어 있다.
따라서, visit algorithm은
Only 60 bytes are available for inode extent. But, one entire block can be used for leaf node extent. Therefore, excluding first 12 bytes header, all are array of struct ext4_extent.
Length of array is stored at header->eh_entries.
Therefore, visiting algorithm is
struct ext4_extent_header *eh = (struct ext4_extent_header *)block;
struct ext4_extent *e = (struct ext4_extent *)((char *)block + sizeof(*eh))
struct ext4_extent *eend = e + eh->eh_entries;
while (e < eend) {
... do something ..
e++;
}
index node block의 경우 leaf node와 마찬가지로 12 bytes header가 처음에 오고, 그 뒤로 "struct ext4_extent_idx"의 array가 나타난다.
따라서 visit algorithm은
In case of index node block, like leaf node, 12 bytes header follows by array of struct ext4_extent_idx.
Therefore visiting algorithm is
struct ext4_extent_header *eh = (struct ext4_extent_header *)block;
struct ext4_extent_idx *ei = (struct ext4_extent_idx *)((char *)block + sizeof(*eh))
struct ext4_extent *eiend = ei + eh->eh_entries;
while (ei < eiend) {
... do something ..
/* "(ei->ei_leaf_hi << 32) | ei->ei_leaf_lo" 는 child block을 가리킨다. */
/* ei->ei_leaf_hi << 32 | ei->ei_leaf_lo means child block. */
ei++;
}
그렇다면, 현재 extent block이 leaf node인지 아니면 index node인지는 어떻게 판단할 수 있는가?
Then, how can we know a certain extent block is whether leaf node or index node?
if "header->eh_depth > 0" than "index node"
else if "header->eh_depth == 0" than "leaf node"
따라서, extent tree를 따라가는 algorithm은
So, algorithm for visiting extent tree is
struct ext4_extent_header *eh = (struct ext4_extent_header *)block;
if (eh->depth)
do_index_node(eh, block)
else
do_leaf_node(eh, block)
본격적으로 directory의 구조로 들어가 보자 (extent를 사용하는 경우를 가정하자.)
directory 역시 file이므로 위의 기본 구조를 따른다.
file의 block은 file의 content를 담고 있고, directory 역시 directory content를 담고 있는데, 다음과 같은 format을 따른다.
Now it's time for talking about directory structure (assuming the case using extent).
directory is also file. So, basic structure is same with the one we mentioned so far.
file block has file content, and directory also has directory content. Format is like below.
Structure across 2 blocks
-------------------------
|<------------------------- block 0 ------------------------->|<------------------ block 1--------------------->|
+----+-----------+--------+-----------------------------------+-----------+--------+----------------------------+
|... | struct DE | <name> | padding | struct DE | <name> | ... |
+----+-----------+--------+-----------------------------------+-----------+--------+----------------------------+
|... | rec_len = 8 + name + 4 byte align + "len of padding" | same as normal (see above) |
+----+-----------+--------+-----------------------------------+-------------------------------------------------+
< NOTE : 여기서 '8'은 'name' field를 제외한 sizeof(struct ext4_dir_entry_2)를 나타낸다.) >
< NOTE : 8 means sizeof(struct ext4_dir_entry_2) excluding name field. >
대부분의 경우 struct DE == struct ext4_dir_entry_2 를 나타낸다.
Most cases, struct DE means struct ext4_dir_entry_2.
#define EXT4_NAME_LEN 255
struct ext4_dir_entry_2 {
__le32 inode; /* Inode number */
__le16 rec_len; /* Directory entry length */
__u8 name_len; /* Name length */
__u8 file_type;
char name[EXT4_NAME_LEN]; /* File name */
};
As you can see above, maximum length of file name at ext4 is 255.
In case of directory block, ext4_dir_entry_2 structures are stored in sequence. So, we can move to next DE(directory entry) by adding rec_len to current DE.
The last DE of a certain block always means "end of current block / begin of next block".
One important thing to know is meaning of inode value. 0 inode value means invalid directory entry.
Especially, you can observe that below algorithm is used to delete file (for details : ext4_delete_entry() at ext4/namei.c from kernel)
< Case : Entry in the middle of block - DE1 - is deleted >
--> In this case, DE0->rec_len += DE1->rec_len.
< Case : The first entry of block - DE0 - is deleted >
--> DE0 is marked as invalid by "DE0->inode = 0" statement.
In summary, rough algorithm for reading directory is
.... 음 .... 일단 여기까지... 나중에 좀더 정리해야겠당....
... to be continued...
'Domain > Kernel' 카테고리의 다른 글
| Compile linux kernel module for ARM - "unknown relocation: 27" (0) | 2014.01.24 |
|---|---|
| [Kernel] How to know KBUILD_MODNAME of each files. (0) | 2012.01.09 |
| [Kernel] Analyzing linux kernel Oops report easily... (0) | 2011.12.15 |
| [Kernel] SMP and IRQ - case (2011-Sep) (0) | 2011.09.23 |
| [Kernel] Potential bug for using jiffies - ex. schedule_timeout() - at Linux kernel. (0) | 2011.08.18 |