Ext 파일 시스템

섹터는 운영체제가 하드 디스크를 읽는 최소 단위이다. 실제 파일 시스템은 입출력을 처리하기 위해 여러 개 섹터를 묶은 기본 입출력 단위로 하드 디스크를 읽는다. EXT 파일 시스템에서는 이러한 기본 입출력 처리 단위를 블록이라고 한다. 블록의 크기는 EXT 파일 시스템을 생성할 때 설정한다.

블록은 일정하게 나누어져 블록 그룹을 구성하고, EXT 파일 시스템은 여러 개의 블록 그룹으로 구성된다. 각 블록 그룹은 같은 개수의 블록과 아이노드를 가진다. 그리고 EXT는 그룹 단위로 블록과 아이노드를 관리한다.

 

아이노드는 타임스탬프, 사용자와 그룹의 권한, 데이터를 저장한 블록의 주소 등 파일 메타 데이터를 저장하는 자료구조이다. 파일 시스템의 모든 파일은 고유한 아이노드를 가진다. 때문에, 파일 시스템이 만들 수 있는 파일의 총개수는 현재 사용 중이 아닌 블록뿐만 아니라, 아이노드 개수에 의해서도 제한된다.

 

블록이 저장하는 내용은 블록의 종류에 따라 다르다. 블록의 종류는 슈퍼 블록, 그룹 디스크립터, 블록 비트맵, 아이노드 비트맵, 아이노드 테이블, 데이터 블록으로 나눈다.

 

Block Group 0는 EXT 파일 시스템의 첫 번째 블록 그룹이다. Group 0에는 특별히 부팅을 위한 1024 바이트 오프셋이 있다. Group 0 Offset(또는 Boot Sector, Boot Block)은 LILO, GRUB 등 부트로더를 저장한다.

 

Group 0의 첫 번째 블록은 슈퍼 블록이다. 슈퍼 블록은 파티션의 블록과 아이노드의 총개수, 각 블록 그룹의 블록 개수, 현재 사용 중이 아닌 블록의 개수 등 파일 시스템의 메타 데이터를 저장한다.

 

Group 0의 두 번째 블록은 그룹 디스크립터이다. 그룹 디스크립터는 특정 그룹의 아이노드 범위, 특정 그룹을 시작하는 블록의 주소 등 블록 그룹의 메타 데이터를 저장한다.

 

슈퍼 블록과 그룹 디스크립터가 저장하는 데이터는 파일 시스템이 마운트될 때 참조하는 내용이다. 때문에 블록이 손상되면 시스템 오류가 발생한다. 이로 인한 오류를 방지하기 위해, 슈퍼 블록과 그룹 디스크립터는 group 0의 원본 블록을 다른 블록 그룹에 백업한다. 기존에는 모든 블록 그룹에 블록 사본을 저장했다. 하지만 현재는 자원을 절약하기 위해 그룹 0,1과 3,5,7 거듭제곱 그룹에 사본을 저장한다.

 

때문에 슈퍼 블록과 블록 디스크립터의 복사본을 저장하는지에 따라서, 각 블록 그룹의 형태가 달라진다.

 

모든 블록 그룹에는 블록 비트맵과 아이노드 비트맵이 있다. 비트맵 블록은 비트와 객체를 매칭하고 비트를 통해 각 객체가 사용 중인지 아닌지를 표시한다. 블록 비트맵은 비트와 그룹에 있는 블록을 순서대로 매칭하여, 사용 중인 블록의 비트를 1, 사용 중이 아닌 블록의 비트를 0으로 표현한다. 아이노드 비트맵은 아이노드 테이블의 아이노드를 순서대로 매칭하여 사용 중인 아이노드의 비트를 1, 사용중이 아닌 아이노드의 비트를 0으로 표현한다.

 

각 비트맵 블록은 하나의 블록을 사용한다. 때문에 블록의 크기에 따라 비트맵 블록이 표현하는 비트의 개수가 달라지고, 비트의 개수는 곧 객체의 개수를 제한한다. 예를 들어, 블록의 크기가 4096바이트일 때, 블록 그룹이 가질 수 있는 블록과 아이노드의 최대 개수는 32,768(8*4096)개이다.

 

아이노드 테이블은 블록 그룹의 아이노드를 순서대로 저장한다. EXT2/EXT3의 아이노드 기본 사이즈는 128바이트이다. EXT2/EXT3 파일 시스템은 파일 데이터를 추적하기 위해, 아이노드에 데이터 블록의 직간접 주소를 저장하는 Block Addressing방법을 사용한다.

 

아이노드의 오프셋 40에는 파일 데이터를 저장한 블록의 주소를 저장하는 블록 필드가 있다. EXT2/EXT3 파일 시스템은 32비트 주소체계를 사용한다. 블록 필드는 총 60바이트이며, 블록 주소를 15개 저장한다. 블록 주소 중, 처음 12개는 데이터 블록을 직접 가리키는 direct 주소이다. 15개의 블록 주소가 모두 direct 주소이면 블록 하나의 크기가 4096바이트 일 때, 아이노드가 표현할 수 있는 파일 크기는 최대 60KB(15*4096)이다. EXT 파일 시스템의 최대 파일 크기는 4GB이다. 때문에 더 큰 파일을 표현하기 위해서 13,14,15번째 블록 주소는 각각 indirect, double indirect, triple indirect 주소를 사용한다.

 

indirect 주소는 direct block 주소를 가리킨다. direct block은 direct 주소를 저장하는 블록이다. direct block이 가지는 direct 주소의 최대 개수는 1024(4096/4)개 이다. 즉, indirect 주소 한 개는 4MB(1024*4096)를 표현할 수 있다.

 

double indirect 주소는 indirect block을 가리킨다. indirect block은 1024개의 indirect 주소를 저장하고 각각 indirect는 다시 direct block을 가리킨다. double indirect 주소 한 개는 4GB(1024*1024*4096)를 표현할 수 있다.

 

triple indirect 주소도 마찬가지로 double indirect block을 가리킨다. triple indirect 주소 한 개는 4TB(1024*1024*1024*4096)를 표현할 수 있다.

 

Ext2 파일 시스템은 파일을 삭제하면, 아이노드 비트맵과 데이터 블록 비트맵을 0으로 설정하여 해당 파일의 아이노드와 블록을 다른 파일이 사용하도록 한다. 이때 아이노드 테이블은 변경하지 않기 때문에 기존 데이터가 덮어씌워지지 않았다면 아이노드의 block addressing 주소를 통해 해당 파일을 복구할 수 있다.

 

Ext3 시스템은 파일을 삭제할 때 아이노드도 함께 삭제한다. 때문에 파일 복구가 더욱 어렵다. Ext3의 삭제 파일은 데이터 카빙으로 복구할 수 있다.

 

아이노드가 가리키는 데이터 블록은 파일 타입에 따라 저장하는 내용이 다르다. 일반 파일은 파일 데이터를 저장하고, 디렉터리는 해당 디렉터리에 속한 파일의 디렉터리 엔트리를 저장한다.

 

디렉터리 엔트리는 파일 시스템에서 파일 이름을 저장하는 유일한 자료구조이다. 아이노드는 파일 이름을 저장하지 않는다. 디렉터리 엔트리가 파일 이름과 아이노드 넘버를 연결한다.

 

디렉터리는 디렉터리 엔트리를 파일 생성 순서대로 저장한다. 모든 디렉터리는 "."의 디렉터리 엔트리와, ".."의 디렉터리 엔트리로 시작한다. 각각 디렉터리 엔트리는 자신 디렉터리와("."), 부모 디렉터리("..")를 가리킨다.

 

디렉터리 엔트리의 크기는 가변적이다. 엔트리의 두 번째 필드인 record length가 디렉터리 엔트리 전체의 크기를 표현한다. 이때 엔트리의 크기를 4의 배수로만 표현하기 때문에, 엔트리의 마지막 필드인 file name이 파일 이름을 저장하고, 나머지 바이트를 NULL로 채운다. "." 엔트리의 경우, 전체 크기는 9바이트로 충분하다. 하지만 record length필드가 표현하는 엔트리 크기는 0x000C(12)바이트이다. file name필드를 확인하면 파일이름인 "."를 저장하고 나머지 3바이트를 00으로 채웠다.

 

또한 마지막 디렉터리의 record length값은 0x0FDC(4060)이다. 이는 디렉터리 블록의 남은 공간을 표현하는 값이다. 디렉터리의 마지막 디렉터리 엔트리는 데이터 블록에 남아 있는 공간을 모두 차지한다. 디렉터리 블록은 언제나 한 개 블록 이상을 차지하지 않는다.

 

사용자가 파일을 삭제하면, 삭제 파일의 바로 이전 디렉터리 엔트리가 엔트리 크기를 삭제 파일의 디렉터리 엔트리 범위까지 키운다. 이후 삭제 파일의 디렉터리 엔트리가 파일과 함께 삭제하거나, 또는 데이터가 특별히 변경하지 않기 때문에 기존 엔트리 데이터를 확인할 수 있다.

 

그러나 새로운 파일이 생성되고 새로운 파일의 엔트리가 기존 엔트리를 사용할 수 있는 크기라면, 새로운 파일의 디렉터리 엔트리가 삭제 파일의 엔트리 범위를 재사용할 수 있다. 엔트리가 재사용되면 기존 데이터는 덮어씌워진다.

 

앞서 언급한 바와 같이, 디렉터리는 디렉터리 엔트리를 링크드 리스트로 저장한다. 이러한 단순 리스팅 방식은 디렉터리 엔트리가 증가하면 성능이 떨어지는 문제점이 있다. 엔트리가 아무런 구분 없이 순서대로 저장되기 때문에, 특정 엔트리를 찾기 위해서 모든 엔트리를 읽어야 하기 때문이다. 결국 디렉터리가 커질수록 엔트리 검색 시간이 증가하고 성능이 떨어진다.

 

파일 시스템은 이러한 문제를 해결하기 위해, 디렉터리 엔트리를 검색 가능한 형태로 저장한다. EXT3부터는 디렉터리가 블록 한 개 크기보다 커지면 htree(hashed tree system) 방식으로 엔트리를 저장한다. htree를 생성하기 위해 study 디렉터리에 파일을 추가하여 디렉터리 블록을 마지막까지 사용했다.

 

 

htree를 사용하는 디렉터리의 첫 번째 블록은 dx_root를 저장한다. dx_root의 첫 24바이트는 "."과 ".."의 디렉터리 엔트리를 저장한다. reserved 영역의 NULL바이트 4개 이후, 다음 1 바이트는 htree가 사용하는 해시 알고리즘을 표현한다. 기본적으로 0x01(MD4 기반 알고리즘)을 사용한다.

 

다음 entry size필드는 dx_entry의 사이즈이다. 엔트리 크기는 언제나 0x08(8) 바이트이다.

 

32-33 오프셋의 record number possible 필드는 디렉터리가 저장하는 dx_entry의 개수를 표현한다. dx_entry의 최대 개수는 한 블록에서 dx_root 헤더의 크기를 뺀 뒤, dx_entry로 나누어 구한다. 블록 하나의 크기가 4096바이트 일 때 record number possible 필드 값은 0x01FB(507)이다. 계산 값 역시 507((4096-40)/8)이다.

 

htree는 중첩 트리를 제공한다. 오프셋 30 tree depth 필드는 트리의 중첩 단계를 표현한다. 하지만 대부분의 경우 단일 트리를 사용한다. dx_root 블록 한 개가 500개 이상 인덱스를 저장하고, 각 인덱스는 수 백 개의 블록을 포함할 수 있기 때문이다.

 

34-35 오프셋 record number actual 필드는 디렉토리가 사용하는 dx_entry의 실제 개수를 표현한다. 실제 개수는 36-39 필드의 "zero hash"를 추가 엔트리로 포함한 개수이다. 때문에 현재 dx_root의 dx_entry는 한 개지만, record number actual 필드값은 0x0002(2)이다.

 

dx_entry는 4바이트 hash value와 4바이트 block offset을 저장한다. 해쉬 값은 파일의 이름을 해쉬로 표현한 값이다. 오프셋 값은 디렉터리 엔트리를 저장하는 리프 블록, 또는 다음 중첩 단계의 인덱스 블록의 위치를 디렉터리 블록을 기준으로 표현하는 블록 오프셋이다.

 

각 dx_entry는 해쉬 값으로 순서를 정렬한다. zero hash는 파일 이름 해시가 첫 번째 dx_entry의 해시값인 0x558F04D8보다 작은 파일들이 블록 오프셋 1 블록에 저장된다는 것을 의미한다. 첫 번째 dx_entry는 파일 이름 해시가 0x558F04D8보다 크거나 같고, 두 번째 dx_entry의 해시 보다 작은 파일들은 블록 오프셋 2 블록에 저장된다는 것을 의미한다. 이후 dx_entry도 마찬가지로 4바이트 해시값으로 범위를 표현하고, 오프셋 값으로 해당 범위에 속하는 파일의 디렉터리 엔트리가 있는 블록의 위치를 표현한다. dx_entry가 해쉬 순서로 정렬됨으로써 파일 시스템은 특정 파일 엔트리를 빠르게 찾을 수 있다.

 

마지막 dx_entry 이후 공간은, 블록의 슬랙이다. 보통 파일 시스템은 기존의 데이터를 사용하지 않아도 NULL로 초기화하지 않는다. 때문에 dx_root의 슬랙 공간에는 디렉터리가 블록 한 개보다 작을 때 저장했던 디렉터리 엔트리 데이터가 남아있다. 예를 들어 아이노드 넘버가 0x00083CDA인 "file3.txt"파일의 데이터가 남아있다. 일반적으로 슬랙 데이터의 디렉터리 엔트리를 htree에서 찾을 수 있다. 다만, 이후 파일이 삭제되고 디렉터리 엔트리 또한 덮어씌워진 경우, 슬랙 공간에 남아있는 데이터는 삭제된 파일의 유일한 흔적이 된다.

 

htree 마지막 단계의 블록은 리프 블록(leaf block)이다. 리프 블록은 dx_root가 정의한 해시 범위에 해당하는 파일의 디렉터리 엔트리를 순서대로 저장한다. htree를 지원하지 않는 파일 시스템은 리프 블록의 디렉토리 엔트리를 검색하여 호환성을 유지한다.