리눅스 커널 내부구조 10장 #4 FAT File System (data structure)

문연수·2022년 3월 1일
FATFile SystemKernellinked listlinux
1

iamroot (Linux Internal)

목록 보기
18/24

여기에서는 이후 FAT 와 File System 코드에서 사용하게 될 자료구조인 Doubly Linked List ,Shell Entry 와 Shell Entry List, cluster_list 마지막으로 disksim 자료구조에 대해 소개하려 한다.

1. Doubly Linked List

Linux Kernel 의 linked list 와 거의 동일하다.

- list.h

#ifndef LIST_H__
#define LIST_H__

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

struct list_head {
	struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(HEAD) { .next = &(HEAD), .prev = &(HEAD) }

#define container_of(PTR, TYPE, MEMBER)						\
		((TYPE *) ((char *) (PTR) - offsetof(TYPE, MEMBER)))

#define LIST_ENTRY container_of

#define LIST_ITERATOR_WITH_ENTRY(HEAD, ENTRY, TYPE, MEMBER)			\
	do {	if (HEAD == NULL)						\
			break;							\
										\
		struct list_head *__LIST_START = HEAD,				\
		                 *__LIST_END   = HEAD;				\
		do {								\
			TYPE *ENTRY = container_of(__LIST_START, TYPE, MEMBER);
			/*
			 * ...
			 */
#define LIST_ITERATOR_END							\
		} while ( __LIST_START = __LIST_START->next,			\
			  __LIST_START != __LIST_END         ) ;		\
	} while (false);

#define LIST_ITERATOR_DELETE_ENTRY	list_del(__LIST_START)
#define LIST_ITERATOR_BREAK		break
#define LIST_ITERATOR_CONTINUE		continue

void list_init(struct list_head *head);

void list_add(struct list_head *head, struct list_head *new);
void list_del(struct list_head *head);

void list_add_tail(struct list_head *, struct list_head *);

#endif

- list.c

#include "list.h"

static void __list_add(
		struct list_head *, struct list_head *, struct list_head *
);

void list_init(struct list_head *head)
{
	head->next = head;
	head->prev = head;
}

void list_add(struct list_head *head, struct list_head *new)
{
	__list_add(head, new, head->next);
}

void list_del(struct list_head *entry)
{
	entry->next->prev = entry->prev;
	entry->prev->next = entry->next;

	entry->next = entry->prev = NULL;
}

void list_add_tail(struct list_head *head, struct list_head *new)
{
	__list_add(head->prev, new, head);
}

static void __list_add(
		struct list_head *prev,
		struct list_head *new,
		struct list_head *next
) {
	/*
	 * prev <-> new <-> next
	 */
	next->prev = new;
	new->next = next;
	new->prev = prev;
	prev->next = new;
}

2. shell entry

shell entry 는 shell 의 관점에서 바라본 파일 데이터 정보이다.

- shell_entry.h

#ifndef SHELL_ENTRY_H_
#define SHELL_ENTRY_H_

#include "list.h"

#include <stdint.h>
#include <stdbool.h>

struct shell_filetime {
	uint16_t year;
	uint8_t month;
	uint8_t day;

	uint8_t hour;
	uint8_t minute;
	uint8_t second;
} ;

struct shell_permission {
	uint8_t owner;
	uint8_t group;
	uint8_t other;
};

struct shell_entry {
	struct shell_entry *parent;

	char name[256];
	bool is_dir;
	unsigned int size;

	struct shell_permission permission;
	struct shell_filetime create_time,
			      modify_time;

	uint8_t pdata[1024];

	struct list_head list;
};

struct shell_entry_list {
	unsigned int count;
	struct list_head *head, *tail;
};

int shell_entry_list_init(struct shell_entry_list *);
int shell_entry_list_add(struct shell_entry_list *, struct shell_entry *);
void shell_entry_list_release(struct shell_entry_list *);

#endif

struct shell_entry 에는 아래에 정보가 포함된다:

  1. 부모 파일 (상위 디렉터리 정보)
  2. 파일 이름
  3. 디렉터리 여부
  4. 파일 크기
  5. 파일 퍼미션
  6. 생성 시간, 수정 시간
  7. 파일 시스템을 위한 데이터 공간 (이후 설명함)
  8. 연결 리스트

- shell_entry.c

shell_cmd_ls() 함수가 호출했던 shell_entry_list_init() 과 shell_entry_list_release() 는 아래의 구조를 가진다. shell_entry_list_add() 함수는 FAT 와 file system 을 거쳐 호출된다.

#include "shell_entry.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "list.h"

int shell_entry_list_init(struct shell_entry_list *list)
{
	list->head = list->tail = NULL;
	list->count = 0;

	return 0;
}

int shell_entry_list_add(
		struct shell_entry_list *list, struct shell_entry *entry
) {
	struct shell_entry *copy;

	copy = malloc(sizeof(struct shell_entry));
	if (copy == NULL)
		return -1;

	memcpy(copy, entry, sizeof(struct shell_entry));
	list_init(&copy->list);
	list->count++;

	if (list->head == NULL) {
		list->tail = list->head = &copy->list;
		return 0;
	}

	list_add(list->head, &copy->list);

	return 0;
}

void shell_entry_list_release(struct shell_entry_list *list)
{
	if (list->head == NULL)
		return ;

	if (list->head == list->tail) {
		list_del(list->head);
		return ;
	}

	for (struct list_head *first = list->head, *last = list->tail, *backup;
	     first != last;
	     first = backup)
	{
		backup = first->next;
		free(first);
		list_del(first);
	}

	list->head = list->tail = NULL;
	list->count = 0;
}

3. cluster_list

cluster_list 는 sector 들의 모음인 cluster 의 연결 리스트 이다. fat_read_superblock() 함수의 search_free_clusters() 함수에 의해 최초로 초기화되어 이후 FAT 에서 cluster 의 할당을 위해 사용된다.

- cluster_list.h

#ifndef CLUSTER_LIST_H__
#define CLUSTER_LIST_H__

#include <stdint.h>

#include "list.h"

typedef uint32_t sector_t;

#define CLUSTER_LIST_CLUSTER_PER_ELEMENT	1023

struct cluster_list_element {
	sector_t clusters[CLUSTER_LIST_CLUSTER_PER_ELEMENT];

	struct list_head list;
};

struct cluster_list {
	uint32_t	count;
	uint32_t	push_offset;
	uint32_t	pop_offset;

	struct list_head *head, *tail;
};

int cluster_list_init(struct cluster_list *);
int cluster_list_push(struct cluster_list *, sector_t );
int cluster_list_pop(struct cluster_list *, sector_t *);
void cluster_list_release(struct cluster_list *);

#endif

- cluster_list.c

#include "cluster_list.h"

#include <stdio.h>	// for NULL
#include <stdlib.h>	// for malloc(), free()
#include <string.h>	// for memset()

int cluster_list_init(struct cluster_list *clist)
{
	if (clist == NULL)
		return -1;

	clist->count = 0;
	clist->pop_offset = clist->push_offset = 0;
	clist->head = NULL;

	return 0;
}

int cluster_list_push(struct cluster_list *clist, sector_t cluster)
{
	struct cluster_list_element *entry;

	if (clist == NULL)
		return -1;

	if (clist->push_offset == CLUSTER_LIST_CLUSTER_PER_ELEMENT 
	||  clist->head == NULL)
	{
		entry = (struct cluster_list_element *) malloc (
			sizeof(struct cluster_list_element)
		);

		if (entry == NULL)
			return -1;

		list_init(&entry->list);

		if (clist->head == NULL) {
			clist->tail = clist->head = &entry->list;
		} else {
			list_add(clist->tail, &entry->list);
			clist->tail = &entry->list;
		}

		clist->push_offset = 0;
	}

	entry = LIST_ENTRY(
		clist->tail,
		struct cluster_list_element,
		list
	);

	entry->clusters[clist->push_offset++] = cluster;
	clist->count++;

	return 0;
}

int cluster_list_pop(struct cluster_list *clist, sector_t *cluster)
{
	struct cluster_list_element *entry;

	if (clist == NULL || clist->count == 0)
		return -1;

	entry = LIST_ENTRY(
		clist->head,
		struct cluster_list_element,
		list
	);

	*cluster = entry->clusters[clist->pop_offset++];
	clist->count--;
	
	if (clist->pop_offset == CLUSTER_LIST_CLUSTER_PER_ELEMENT) {	
		list_del(&entry->list);
		if (clist->head == clist->tail)
			clist->tail = clist->head = NULL;
		else
			clist->head = clist->head->next;

		clist->pop_offset = 0;
		free(entry);
	}	

	return 0;
}

void cluster_list_release(struct cluster_list *clist)
{
	if (clist == NULL)
		return ;

	LIST_ITERATOR_WITH_ENTRY(clist->head, entry,
			         struct cluster_list_element, list)
		free(entry);
	LIST_ITERATOR_END

	clist->head = NULL;
	clist->count = 0;
}

disksim.c 와 disksim.h 코드가 실제 물리적 하드웨어를 표현한 것이다. 이를 통해 디스크의 데이터를 읽고 쓰는 작업을 수행할 수 있다.

4. disksim

디스크를 읽고 쓰는 작업을 시뮬레이션해주는 disksim 이다. 코드 내용이 어렵지 않으므로 큰 흐름만 보면 좋을 것 같다.

- disksim.h

#ifndef DISK_H__
#define DISK_H__

#include <stdint.h>

typedef uint32_t sector_t;

struct disk_operations {
	int (*read_sector) (struct disk_operations *, sector_t , void *);
	int (*write_sector) (struct disk_operations *, sector_t , const void *);

	sector_t number_of_sectors;
	int bytes_per_sector;
	void *pdata;
};

int disksim_init(sector_t , unsigned int, struct disk_operations* );
void disksim_uninit(struct disk_operations );

#endif

- disksim.c

#include "disksim.h"

#include <stdlib.h>	// for malloc(), free()
#include <string.h>	// for memcpy()

struct disk_memory {
	void *address;
};

int disksim_read(struct disk_operations *ops, sector_t sector, void *data);
int disksim_write(struct disk_operations *ops, sector_t sector, const void *data);

int disksim_init(
	sector_t number_of_sectors,
	unsigned int bytes_per_sector,
	struct disk_operations *disk)
{
	if (disk == NULL)
		goto RETURN_ERR;

	disk->pdata = malloc(sizeof(struct disk_memory));
	if (disk->pdata == NULL)
		goto DISKSIM_UNINIT;

	((struct disk_memory *) disk->pdata) -> address = malloc(
		bytes_per_sector * number_of_sectors
	);

	if (((struct disk_memory *) disk->pdata) -> address == NULL)
		goto FREE_DISK_PDATA;

	disk->read_sector = disksim_read;
	disk->write_sector = disksim_write;
	disk->number_of_sectors = number_of_sectors;
	disk->bytes_per_sector = bytes_per_sector;

	return 0;

FREE_DISK_PDATA:free(disk->pdata);
DISKSIM_UNINIT:	disksim_uninit(*disk);
RETURN_ERR:	return -1;
}

int disksim_read(struct disk_operations *disk, sector_t sector, void *data)
{
	char *disk_addr;
	int index;

	if (sector < 0 || sector >= disk->number_of_sectors)
		return -1;

	disk_addr = ((struct disk_memory *) disk->pdata ) -> address;
	index = sector * disk->bytes_per_sector;

	memcpy(data, &disk_addr[index], disk->bytes_per_sector);

	return 0;
}

int disksim_write(
		struct disk_operations *disk,
		sector_t sector,
		const void *data
) {
	char *disk_addr;
	int index;

	if (sector < 0 || sector >= disk->number_of_sectors)
		return -1;

	disk_addr = ((struct disk_memory *) disk->pdata ) -> address;
	index = sector * disk->bytes_per_sector;

	memcpy(&disk_addr[index], data, disk->bytes_per_sector);

	return 0;
}

void disksim_uninit(struct disk_operations ops)
{
	if (ops.pdata) {
		free ( ((struct disk_memory *) ops.pdata)->address );
		free(ops.pdata);
	}
}

 설명할 부분이 많진 않다. disksim_init 는 shell_create() 함수와 함께 호출되므로 shell 시작 시에 디스크를 초기화(???) 한다고 이해하면 될 것 같다. 뭐가 됐든 시뮬레이션이기 때문에 호출 순서는 대충 그러려니 하고 넘어가도록 하자.
위 디스크 오퍼레이션은 이후 fat 시스템에서 cluster 와 함께 사용하게 된다.

profile
문연수
2000.11.30
이전 포스트

리눅스 커널 내부구조 10장 #4 FAT File System (shell)

다음 포스트

리눅스 커널 내부구조 10장 #4 FAT File System (filesystem)

0개의 댓글