FAT 파일 시스템(File System)

원문 :  http://kkamagui.springnote.com/pages/345737

들어가기 전에...

1.FAT 파일 시스템 개요

 FAT 파일 시스템은 전통적으로 DOS 시절부터 사용되어 왔다. FAT 파일 시스템이 다른 파일 시스템과 구별되는 점은 파일 내용을 클러스터 단위로 구성하고 이것을 링크드 리스트(Linked List)의 형태로 보관하는 것이다.

 말로 하면 어려우므로, 일단 아래 그림을 보도록 하자.

<FAT의 간략한 구조>

 위 그림과 같이 파일은 고정된 크기의 클러스터(Cluster) 단위로 나누어져 있으며, 그 클러스터들은 클러스터 풀(Cluster Pool)에 존재하는 클러스터를 연결한 클러스터 채인(Cluster Chain)으로 되어있다. 실제 FAT 파일 시스템에서 클러스터 풀은 FAT(File Allocation Table)이라는 용어를 사용한다.

 클러스터(Cluster)란 별개 아니고 여러개의 섹터를 모아서 하나의 블럭 단위로 보는 것이다. 윈도우 포맷 프로그램을 이용해서 포맷을 하면 일반적으로 클러스터의 크기를 4Kbyte로 잡는데, 이 말은 한 섹터(Sector)의 크기가 512byte 이므로 8개의 섹터를 하나의 블럭으로 설정한다고 보면 된다.

 그럼 왜 클러스터라는 말을 쓰는 것일까? 그것은 섹터를 블럭으로 관리하면 얻는 이득이 있기때문이다. 아까 잠시 클러스터 풀에 대한 이야기를 했는데, 고용량일수록 클러스터 풀(FAT 영역)이 커지게 된다. 이것이 커질수록 파일을 읽고 쓸때 관리해야 하는 양이 늘어나게되고, 또한 디스크의 비어있는 공간이 줄어들게 된다. 이것을 블럭으로 관리하게 되면 이런 문제가 해결되며, 또한 블럭 단위로 읽기 쓰기를 수행함으로 얻는 효율로 인해 성능이 좋아지게 되는 것이다.

 특히 요즘처럼 파일의 크기가 큰 상황에서는 클러스터의 크기가 큰 것이 성능 향상에 도움이 된다. 하지만 클러스터의 크기가 무조건 크다고 좋은 것은 아니다. 아까 이야기 했듯이 클러스터의 단위로 작업을 하기 때문에, 작은 파일 같은 경우는 클러스터 하나를 할당받아서 대부분의 영역을 낭비하는 경우도 있으니 적당히 조절해야 한다.

 자 그럼 FAT 파일 시스템의 큰 특징을 알아봤으니 세부적인 내용을 알아보자

 FAT 파일 시스템은 총 3가지의 타입이 있다.

 세가지 타입 모두 내부 포맷은 비슷하며, 차이점은 클러스터 개수라고 볼 수 있다.(물론 그것만 차이나는 것은 아니다. ㅡ,.ㅡ;;; 오해하지 말자.). 클러스터의 개수에 따라 FAT 타입을 분류한다고 했는데, 이 클러스터 개수는 어떻게 구하는 것일까? 실제 데이터 영역을 구성하는 크기를 가지고 계산하는 것일까?

 실제 타입 구분에 사용되는 클러스터의 크기는 디스크 전체 크기를 범위로 한다. 즉 아래의 공식으로 클러스터의 크기를 구하고 그것으로 타입을 유추하는 것이다.

 이렇게 구한 클러스터의 개수는 실제로 사용가능한 데이터 영역의 클러스터의 개수와 비교하면 당연히 큰값을 가진다. 왜냐하면 디스크 또는 파티션 영역에 데이터만 들어가는 것이 아니고 FAT 파일 시스템을 관리하기위한 파일 시스템 메타 데이터(Meta Data)를 포함하기 때문이다.

 이제 파티션과 메타 데이터에 대해서 알아보자.

2.파티션(Partition)

 파티션에 대해서 익히 알고있고 들어봤을 것이다. 디스크 전체를 하나로 사용하는 것이 아니라 그 안에 C: D:와 같이 영역을 분할하여 사용하는 것이 파티션이다. 파티션을 나누면 디스크를 효율적으로 관리할 수 있는 장점 때문에 약간의 디스크 공간을 낭비하더라도 파티션을 해서 많이 사용한다(아래와 같이 나눌 수도 있다).

 그럼 어떻게해서 파티션이 나누어지는 것일까? 파티션을 나누게 되면 그 파티션에 대한 정보가 MBR(Master Boot Record)란 영역에 삽입되게 된다. MBR이란 디스크의 첫번째 섹터로 부트 코드와 여러가지를 정보를 포함하고 있다. MBR의 존재는 맨 마지막 510째부터 0x55 0xAA가 있는지 확인하여 이것이 있으면 MBR이 존재한다고 보면 된다(사실 다 있다. ㅡ_ㅡ;;; OS를 깔아 쓰면 저것 말고도 여러 정보가 MBR에 들어가 있다.)

 MBR의 세부구조를 한번 알아보자.

 헥사 에디터 프로그램으로 4개의 파티션으로 나누어진 USB 메모리의 MBR을  캡쳐한 화면이다. 좌측 상단에 0xEB 0x3C 0x90의 3Byte가 있는데, 이부분은 부트 코드의 시작으로 jmp 하라는 어셈블리어 명령이다. 굳이 필요한 것은 아니나 윈도우에서 MBR 인식을 위해서는 이 부분이 꼭 필요하다( 이부분이 0x00으로 비어져있는 경우에 윈도우가 MBR로 인식하지 못하는 것을 발견했다).

 우측 하단에 0x55 0xAA의 매직넘버가 보이고 그위에 붉은 색 줄이 쳐져있는 16byte의 라인이 보인다. 이부분이 파티션 데이터의 시작으로 그 앞부분은 모두 Boot Code의 용도로 사용되거나 아니면 사용되지 않는다. 파티션 정보는 16Byte씩 4개로 총 64Byte로 되어있으며 각 항목은 아래와 같은 구조체로 되어있다.

1. /**
       Partition에 대한 정보를 포함하는 구조체
   */
   typedef struct partitionStruct
   {
       BYTE bBootIndicator;
       BYTE bStartingHeader;
       WORD wStartingSectorAndCylinder;
       BYTE bSystemID;
       BYTE bEndingHeader;
       WORD wEndingSectorAndCylinder;
       DWORD dwRelativeSector;
       DWORD dwTotalSector;
   } PARTITION, * PPARTITION;

  여기서 중요하게 봐야할 부분은 위에서 파란색으로 표시된 부분인데, 그 외 부분들은 옛날 도스 시절에나 사용된 필드기 때문에 무시해도 된다. 각 필드는 아래와 같은 의미를 가진다.

  위 정도값만 제대로 설정하면 윈도우에서 정상적으로 파티션 된 것으로 인식한다. MBR에 파티션 필드는 총 4개가 있으므로 파티션은 최대 4개까지 만들 수 있다. 그럼 도스 시절에는 파티션이 4개 이상이 가능했는데, 이것은 어떻게 한 것일까? 옛날 도스에서는 확장 파티션(Extension Partition)이라는 기능을 사용했다. 즉 MBR 파티션에는 확장 파티션 영역을 표시해 놓고, 확장 파티션 영역의 첫번째 섹터로 이동하면 그 첫번째 섹터에 다시 파티션 정보 + 확장 파티션 정보를 기입하는 식으로 체인으로 연결했던 것이다(이렇게 하면 디스크 용량이 허락하는 한 거의 무한대의 파티션을 생성할 수 있다. ㅡ,.ㅡ;;;;). 도스 이후에는 별로 사용하지 않으므로 일단 넘어가자. 궁금한 사람은 http://www.nondot.org/sabre/os/articles에 가서 Partition 쪽을 보면 된다.

3.파일 시스템 메타 데이터(File System Meta Data)

 FAT 파일 시스템을 구성하는 메타 데이터는 위와 같은 순서로 구성된다. 각 항목에 대한 설명은 아래와 같다.

3.1 PBR(Partition Boot Record), BPB(BIOS Parmeter Block)

 PBR은 여러 이름으로 불리는데 다른 이름으로는 BPB라고도 한다. 옛날 도스 시절에 BIOS 콜을 통해 파티션에 대한 정보를 얻어오고 처리하고 했는데, 그 기본 정보가 되는 블럭이라서 저런 이름이 붙은 것 같다. 일단 여기서는 PBR이라고 하겠다.

 PBR과 MBR의 차이는 무엇일까? MBR은 하나만 존재하며 섹터 0에만 있고, PBR은 각 파티션의 시작에 존재하며 FAT에 대한 정보를 포함하고 있다는 것이 다르다. PBR에는 어떤 정보가 포함되어있을까? FAT Type에 따라 다르므로 각각 살펴보도록 하자.

 FAT16/32의 PBR에 포함된 데이터는 아래와 같다.

1. /**
       FAT16에 대한 구조체
   */
   typedef struct fat16Struct
   {
       BYTE vbJumpCode[ 3 ];
       char vcCreatingSystemIdentifier[ 8 ];
       WORD wSectorSize;
       BYTE bSectorsPerCluster;
       WORD wReservedSectorCount;
       BYTE bNumberOfFATs;
       WORD wNumberOfRootDirectoryEntries;
       WORD wTotalSectors;
       BYTE bMediumIdentifer;
       WORD wSectorsPerFAT;
       WORD wSectorsPerTrack;
       WORD wNumberOfSides;
       DWORD dwNumberOfHiddenSectors;
       DWORD dwTotalSectors;
2.     // 여기 위까지는 FAT16/32 공통
       BYTE bPhysicalDiskNumber;
       BYTE bReserved;
       BYTE bExtendedBootRecordSignature;
       char vcVolumeIDNumber[ 4 ];
       char vcVolumeLabel[ 11 ];
       char vcFileSystemType[ 8 ];
       BYTE vbReservedForSystemUse[ 448 ];
       BYTE vbSignatureWord[ 2 ];
   } FAT16, * PFAT16;
4. /**
       FAT32에 대한 구조체
   */
   typedef struct fat32Struct
   {
       BYTE vbJumpCode[ 3 ];
       char vcCreatingSystemIdentifier[ 8 ];
       WORD wSectorSize;
       BYTE bSectorsPerCluster;
       WORD wReservedSectorCount;
       BYTE bNumberOfFATs;
       WORD wNumberOfRootDirectoryEntries;
       WORD wTotalSectors;
       BYTE bMediumIdentifer;
       WORD wSectorsPerFAT;
       WORD wSectorsPerTrack;
       WORD wNumberOfSides;
       DWORD dwNumberOfHiddenSectors;
       DWORD dwTotalSectors;
5.     // 여기 위까지는 FAT16/32 공통
       DWORD dwSectorsPerFAT32;
       WORD wExtensionFlag;
       WORD wFSVersion;
       DWORD dwRootCluster;
       WORD wFSInfo;
       WORD wBackupBootSector;
       BYTE vbReserved[ 12 ];
       BYTE bPhysicalDiskNumber;
       BYTE bReserved;
       BYTE bExtendedBootRecordSignature;
       char vcVolumeIDNumber[ 4 ];
       char vcVolumeLabel[ 11 ];
       char vcFileSystemType[ 8 ];
       BYTE vbReservedForSystemUse[ 420 ];
       BYTE vbSignatureWord[ 2 ];
   } FAT32, * PFAT32;

 상당히 많은 데이터를 포함하고 있는데, 일단 FAT16/32에 공통인 부분부터 살펴보자.

 공통인 부분들에 대해 살펴봤으니, 이제 FAT32에 특화된 부분을 보자

  위의 필드 값을 FAT Type에 따라 PBR에 설정해 주면 반은 끝난 것이다. 약간 주의할 점은 Reserved Sector에 값을 설정했다면 파티션의 시작부터 Reserved Sector에 설정된 값만큼을 0으로 초기화해야한다(적극 권장). 위의 설명에도 나와있듯이 Reserved Sector의 값은 파티션의 시작부터 FAT1/2 이전까지의 섹터 수이므로, 절대 0이 될 수 없다. 왜? PBR이 있기 때문에 @0@)/~!!! 아무리 작아도 1 이상의 값을 가진다.

 이제 다음 메타 데이터를 살펴보자.

3.2File Allocation Table(FAT) 1/2 영역

 FAT 1/2 영역은 클러스터의 개수에 따라서 영역의 크기가 달라진다고 이야기 했다. 여기에서 말하는 클러스터의 개수는 실제 사용가능한 클러스터의 개수를 이야기하는데, 이 크기 이상만 된다면 얼마든지 좀 크게 잡아도 상관없다.

 FAT12의 경우 FAT를 구성하는 클러스터 링크의 비트수가 12bit가 이고, FAT16의 경우  16bit, FAT32의 경우 32bit이다. 따라서 한 섹터를 기준으로 FAT Type에 따라서 포함할 수 있는 클러스터 링크의 개수는 아래와 같이 된다.

 위에서 보는 것과 같이 FAT32로 갈수록 한 섹터에 담을 수 있는 클러스터 링크의 개수가 작아진다. 이것은 동일한 클러스터의 크기를 사용한다면 대용량일수록 FAT의 크기가 커진다는 것을 의미하고 FAT가 커지면 커질수록 실제로 사용가능한 클러스터의 크기가 줄어들게된다. 클러스터의 크기를 적당히 조절하여 FAT 크기를 너무 크지않게 하는 것이 좋다.

 FAT의 0번째 클러스터 링크와 1번째 클러스터 링크는 Signature의 용도 비슷하게 사용되는데, FAT Type에 따라 아래와 같이 설정해 준다.

 자 그럼 이제 FAT의 실제 크기를 한번 계산해 보자. 가장 간단하게 계산할 수 있는 방법은 파티션 전체의 크기를 클러스터의 크기로 나누어 구하는 방법이다. 실제로 이렇게 구하면 PBR + Rerserved Area + FAT1/2 영역의 크기도 사용가능한 것으로 인식하여 계산하기 때문에 낭비가 좀 있지만 계산은 편리하다. 특히 Root Directory의 시작 위치를 맞추거나 할때는 이렇게 계산하여 FAT의 크기를 구하고 여기에 Reserved Area의 값을 조절하여 맞출 수 있어 편리하다.

 또다른 방법은 전체 크기에서 PBR과 Reserved 영역을 제외하고 구하는 방법이다. 낭비가 좀 줄어들긴 한데, 식이 복잡해 진다. 아래는 그 계산 식이다(511은 올림을 위해 넣었다)

 이렇게 계산된 크기를 PBR에 wSectorsPerFAT나 dwSectorsPerFAT32 영역에 넣어주면 된다. 만약 wNumberOfFAT의 값을 2로 설정했으면 FAT1/2 영역을 연속해서 만들어줘야 하며 위의 FAT의 크기 * 2 만큼의 영역을 할당해 줘야 한다.

3.3 Root Directory Sector or Cluster 영역

  FAT16/32의 경우 위의 순서대로 PBR, FAT1/2 를 만들고 Root Directory Sector만 생성해 주면 정상적으로 윈도우에서 인식이 가능하다. 만약 Volume Label을 "NO NAME"으로 입력한 경우 Root Directory는 0으로 초기화 해주는 것으로 충분하다. 하지만 Volume Label을 사용한다면 Directory Entry Structure를 생성해서 Volume Label을 삽입해야 한다.

 Directory Entry Structure는 아래와 같이 구성되어있다.

1. typedef struct directoryStruct
   {
       char vcNameAndExtension[ 11 ];
       BYTE bAttribute;
       BYTE bReservedForNT;
       BYTE bCreatedTimeTenth;
       WORD wCreatedTime;
       WORD wCreatedDate;
       WORD wLastAccessDate;
       WORD wStartingClusterNumberHigh;
       WORD wTimeRecorded;
       WORD wDateRecorded;
       WORD wStartingClusterNumberLow;
       DWORD dwFileLength;
   } DIRECTORY, * PDIRECTORY;

 각 항목은 아래와 같은 의미를 가진다.

 조금 복잡한데, 일단 Attribute 부터 보면 아래와 같이 나와있다(첨부 항목에 White Paper 참조).

 일단 포맷 후에 Volume Label을 생성해야 하므로 ATTR_VOLUME_ID를 생성하면 된다. 이때 주의할 것은 Volume Label을 설정하는 Directory Entry의 경우 Name과 Attribute를 제외한 나머지는 모두 0으로 설정해야한다.

 위를 보면 낯 익은 값들도 있을 것이다. 만약 윈도우가 FAT Filesystem으로 포맷되어있다면 위의 항목들이 설정된 Directory Entry 구조체가 여기저기 널려있을 것이다. Hex Editor와 같은 프로그램을 이용해서 하드디스크를 열어서 확인해 보자 @0@)/~~!!!!. 각 항목에 대한 자세한 설명은 White Paper를 참조하자.

 Time과 Date 부분은 공통적인 포맷을 사용하는데, White Paper에 아래와 같이 나와있다(간단한 비트 연산으로 만들 수 있다).

 파일 시스템 분석을 하는 경우라면 ClusterNumber와 Name, 그리고 Attribute를 유심히 봐두는 것이 도움이 될 것이다. 다른 파일 시스템이 그러하듯이 Root Directory로부터 Sub Directory가 생성되고 트리 형태로 관리되기 때문에 Root Directory를 찾은 다음 Entry 구조만 안다면 전체를 Travel 하는 것은 어렵지 않으니까...

3.4 FSInfo

  FSInfo 영역은 FAT32에만 존재하는 영역이다. 역시 한 섹터 크기정도로 되어있고 별다른 정보를 포함하지 않는다. 단지 FAT32에 참고할만한 정보만 가지고 있다.

1. typedef struct fsInfoStruct
   {
       BYTE vbLeadSignature[ 4 ];
       BYTE vbReserved1[ 480 ];
       BYTE vbStructureSignature[ 4 ];
       DWORD dwFreeClusterCount;
       DWORD dwNextFreeCluster;
       BYTE vbReserved2[ 12 ];
       BYTE vbTrailSignature[ 4 ];
   } FSINFO, * PFSINFO;

  각 항목은 아래와 같은 의미를 가진다.

 위에서 보는 것과 같이 FAT32의 부가적인 정보가 포함된 영역이고 특히 클러스터 관련 필드는 권장값이므로 절대 100% 믿으면 안된다.

4.마치며...

 여기까지 간단하게 FAT Filesystem에 대해서 알아보았다. 원래 훨씬 일찍 마무리 되었어야 하는데... 과제하느라 정신이 조금 없어서 찔끔 찔끔 정리하다보니 이제야 마무리를... ㅜ_ㅜ... 다소 부족한 감이 있지만 Formatter를 개발하면서 알아낸 정보를 기반으로 작성하였다.

 다음에는 위 정보를 기반으로 실제 FAT Filesystem을 분석해 보도록 하자.

5.첨부

• FatFormat_Microsoft_WhitePaper.pdf : FAT File system에 대한 세세한 설명.
• FAT_파일_시스템.ppt : 위에 첨부된 그림 자료.

이 글은 스프링노트에서 작성되었습니다.

• 256 Mb (32 MB) of NOR Flash Memory. This type of memory is able to retain data without requiring uninterrupted power. Depending on data size, writing may take up to several minutes. One typical use includes copying over a GBA ROM, thereby allowing the 3-in-1 to act like a real GBA cartridge.
• 128 Mb (16 MB) of PSRAM. This memory does not retain data when the power is turned off. However it can be written at speeds much faster than NOR memory.
• 4 Mb (512 KB) of battery backed SRAM for save data. The battery is necessary to retain data.
• Programmable embedded "rumble pak" (haptic feedback) device

무려 16MByte @0@)/~!!!

NDS 자체의 램이 4MByte 정도니까 합이 20MByte @0@)/~!!!!!

두둥... PSP가 32MByte인 것을 감안할 때 굉장한 붐업이다...

ㅜ_ㅜ... 당장 질러서 테스트 프로그램이나 하나 만들어봐야겠다...

다들 기대하시라 ㅎㅎ

>ㅁ<)/~!!!

출처 : http://chishm.drunkencoders.com/libfat/

libfat

A FAT library for the Nintendo GBA and DS

This is the successor to GBA NDS FAT. It features better reentrancy support, cleaner source code and is built as a proper library.

LIBS	:= -lnds9

LIBS	:= -lfat -lnds9

#include <fat.h>

fatInitDefault();

fatInit(cache_size, set_as_default);

FILE* test = fopen ("fat2:/app_data/graphics.bin", "rb");

FILE* test = fopen ("/app_data/graphics.bin", "rb");

FILE* test = fopen ("graphics.bin", "rb");

DIR_ITER* dp = diropen ("/directory/path/");

dirnext (dp, filename, &filestat);

dirreset (dp);

dirclose (dp);

struct stat st;char filename[256]; // to hold a full filename and string terminator
DIR_ITER* dir;dir = diropen ("/"); 
if (dir == NULL) {	
iprintf ("Unable to open the directory.\n");
} 
else {	
while (dirnext(dir, filename, &st) == 0) {		// st.st_mode & S_IFDIR indicates a directory		
iprintf ("%s: %s\n", (st.st_mode & S_IFDIR ? " DIR" : "FILE"), 
filename);	
}
}