(2022.03.28) Indexed & Extensible 구현 (1)

1. 서론 및 필요 내용 설명

구체적인 설명은 가이드라인에서 거의 다 한 것 같으니 한 가지만 다시 짚고 넘어가도록 하자. disk에 저장되는 섹터의 구조를 살펴보면, 0번 섹터는 boot sector로 활용이 되며, 1 ~ f는 FAT를 저장하는 용도로, f + 1부터 n - 1까지의 섹터는 데이터를 저장하는 용도로 사용된다. 이제 cluster를 어떻게 할당할지를 생각해보자. f + 1번 섹터가 1번 cluster라고 한다면 n - 1번 섹터는 (n - f - 1)번 cluster가 된다. 이러한 매핑은 임의로 정한 것이지만, 가장 단순한 형태이며, 역산도 간단하기 때문에 이렇게 결정하였다. 번외로 0번 섹터는 0번 cluster에 그대로 매핑이 되지만, FAT에서는 0번 cluster를 다루지 않을 것이다. 그림으로 정리하면 다음과 같다.

 

이제 구현을 시작하자.

 

---

2. 구현해야 하는 것

• FAT 관련 함수들

 

---

3. 구현 과정

구현에 앞서, 어떻게 비어있는 cluster 및 섹터를 찾을 수 있을지 생각해보았다. FAT 만으로 cluster 및 섹터가 할당된 상태를 알 수 있을까? 알 수 있다. cluster 0번은 boot sector를 위해 마련된 것으로, 어떠한 cluster 및 섹터도 해당 cluster로는 연결되지 않는다. FAT 자체도 처음 생성될 때 calloc으로 생성되기 때문에 할당되지 않은 cluster의 경우 해당 엔트리 값으로 0을 가지고 있을 것이다. 따라서 할당되지 않은 cluster를 찾고자 할 때, FAT를 순회하면서 엔트리 값이 0인 인덱스를 찾으면 된다. 이를 기반으로 빠르게 FAT 기반 함수들을 만들어보자. 

 

fat_fs_init에서는 일단 필요할 것이라 생각한 변수를 fat_fs->bs에서 가져온 수를 이용해 초기화하였다. fat_length에는 총 cluster의 개수인 N - f가, data_start에는 일단 조금 애매하지만 f + 1을, last_clst로는 N - f - 1을 넣어주었다.

void
fat_fs_init (void) {
	/* TODO: Your code goes here. */

	fat_fs->fat_length = fat_fs->bs.total_sectors - fat_fs->bs.fat_sectors;
	fat_fs->data_start = fat_fs->bs.fat_sectors + 1;
	fat_fs->last_clst = (cluster_t) (fat_fs->bs.total_sectors - fat_fs->bs.fat_sectors - 1);
}

fat_create_chain은 위에서 생각한 방식대로 빈 FAT 엔트리를 찾아서 해당 cluster를 반환하도록 구현한다.

cluster_t
fat_create_chain (cluster_t clst) {
	/* TODO: Your code goes here. */
	cluster_t alloc_clst;
	bool found = false;

	// find empty slot in table, will not return boot sector cluster 0
	for (alloc_clst = 1; alloc_clst != fat_fs->last_clst; alloc_clst += 1) {
		if (fat_fs->fat[alloc_clst] == 0) {
			found = true;
			break;
		}
	}

	if (!found) {
		return 0;
	}

	if (clst == 0) {
		fat_fs->fat[alloc_clst] = EOChain;
	}

	else {
		if (fat_fs->fat[clst] != EOChain) {
			return 0;
		}

		fat_fs->fat[clst] = alloc_clst;
		fat_fs->fat[alloc_clst] = EOChain;
	}
	
	return alloc_clst;
}

반대로 fat_remove_chain은 지정해준 clst부터 순차적으로 chain을 따라가면서 각 엔트리를 0으로 만들어주면 된다. 해당 clst 직전의 cluster인 pclst가 가리키고 있는 엔트리는 이제 없으므로, EOChain으로 값을 바꿔주는 것을 잊지 않는다.

void
fat_remove_chain (cluster_t clst, cluster_t pclst) {
	/* TODO: Your code goes here. */

	cluster_t cur_clst = clst, nxt_clst;

	while (cur_clst != EOChain) {
		nxt_clst = fat_fs->fat[cur_clst];
		fat_fs->fat[cur_clst] = 0; // now it's not being used
		cur_clst = nxt_clst;
	}

	if (pclst != 0) {
		fat_fs->fat[pclst] = EOChain;	
	}
}

fat_put과 fat_get은 간단히 다음과 같이 구현하고,

void
fat_put (cluster_t clst, cluster_t val) {
	/* TODO: Your code goes here. */
	fat_fs->fat[clst] = val;
}

cluster_t
fat_get (cluster_t clst) {
	/* TODO: Your code goes here. */
	return fat_fs->fat[clst];
}

cluster_to_sector는 서론에서 설명한 방식에 따라 다음의 반환 함수를 만들 수 있다.

disk_sector_t
cluster_to_sector (cluster_t clst) {
	/* TODO: Your code goes here. */

	if (clst == 0) // refers boot sector
		return FAT_BOOT_SECTOR;

	return fat_fs->data_start + (clst - 1);
}

이로서 FAT 관련 함수들은 빠르게 구현했다. 구현을 마치면서 문득 궁금해진건, sector에서 cluster로 변환하는 기능이 필요 없을까이다. 만약 필요해진다면 해당 함수도 간단히 만들 수 있으므로 구현하도록 하자.

 

---

4. 디버깅

아직 실행할 수 있는 단계가 아니다.

 

---

5. 후기

대부분의 내용이 잠이 안 와서 새벽 4시에 강제 기상해서 코딩한 거라 상태가 좋지 않을 수 있다. 이 포스트를 쓴 건 또 그 이후에 잠을 안 자고 한 것이라 내용이 굉장히 불친절할 수 있다. 간단간단한 코드들이지만 미래의 나는 버그가 터진다면 이 부분을 유심히 볼 것...