본문 바로가기

정글캠프-WIL/핀토스

pintos - vm [lazy_load_segment]

지금까지 VM 구현에선 각 프로세스마다 Supplemental Page Table(SPT) 해시 테이블을 생성하도록 구성하고 이후 아직 물리 프레임이 할당되지 않은 uninit 페이지를 SPT에 등록해두고, 실제로 해당 가상 주소에 접근하여 page fault가 발생했을 때 SPT에서 페이지 정보를 찾도록 했다.

page fault 처리 과정에서는 해당 페이지가 유효한 접근인지 확인한 뒤, 물리 프레임을 할당하고, 필요하다면 전역 물리 프레임 테이블을 생성해 eviction 정책(Clock Algorithm - Second Change)에 따라 기존 프레임을 교체하도록 구현했다. 이후 가상 페이지와 물리 프레임을 연결하고 pml4 매핑을 생성하여 프로세스가 해당 페이지를 사용할 수 있게 만들었다.

여기까지의 흐름을 바탕으로, 현재는 초기 스택 페이지 한 프레임을 실제 메모리에 올리는 작업까지 마무리한 상태이다. 다음 단계는 실행 파일의 segment를 페이지 단위로 SPT에 등록하고, 각 페이지가 처음 접근될 때 파일에서 해당 내용만 읽어와 물리 프레임에 적재하는 lazy loading을 구현하는 것이다.

1. lazy_load_segment 구현 전 load_segment

위 함수를 구현하기 전 현재 파일의 읽을 바이트 크기와 zero로 채울 바이트 크기와 페이지 offset을 담아둘 구조체를 만들어 둬야 한다.

예를 들어 실행 파일의 segment를 아래와 같이 가정

파일 offset 0부터 6000바이트를 가상주소 0x8048000에 올려야 함
페이지 크기 = 4096
                          ↓
그러면 lazy loading에서는 당장 파일을 읽지 않고 SPT에 아래와 같이 등록만 해둠
                          ↓
                가상 페이지 0x8048000:
                  file = 실행파일
                  ofs = 0
                  read_bytes = 4096
                  zero_bytes = 0

                가상 페이지 0x8049000:
                  file = 실행파일
                  ofs = 4096
                  read_bytes = 1904
                  zero_bytes = 2192

나중에 프로세스가 0x8049000에 접근해서 page fault가 나면 lazy_load_segment()는 aux로 받은 lazy_load_info를 보고 페이지를 설정

이때 여기서 해결되지 않은 문제가 해결된다.

https://gyumingomin.tistory.com/92

 

Pintos - vm [페이지 할당 초기화 과정을 위한 흐름도]

https://gyumingomin.tistory.com/91 Pintos - SPT(Supplemental Page Table)와 Hash TableSPT(Supplemental Page Table)에서 hash table을 왜 쓸까?Pintos VM에서 핵심page fault가 발생했을 때, 이 가상주소에 대한 정보를 빠르게 찾아야

gyumingomin.tistory.com

이때 초반에 load_segment를 제쳐두고 넘어갔었다.

아래 코드는 이때 당시의 코드이고

아래 코드는 현재 구현된 코드이다.

접은글: load_segment 구현

1. 각 페이지마다 lazy_load_segment()에 넘겨줄 lazy_load_info 구조체를 힙에 할당한다. 이 구조체에는 나중에 파일에서 어떤 위치를 읽어야 하는지에 대한 정보가 들어간다.
2. file_reopen(file)을 통해 같은 파일을 참조할 수 있는 file 객체를 만든다. 이때 inode의 open_cnt가 증가한다. 즉, 디스크 sector를 직접 가져온다기보단 나중에 page fault시 파일을 다시 읽을 수 있도록 file 참조를 유지하는 것이다.
3. aux에는 다음 정보를 저장한다.
    ㄴ file
    ㄴ ofs
    ㄴ page_read_bytes
    ㄴ page_zero_bytes
4. vm_alloc_page_with_initializer()를 호출해서 upage에 해당하는 가상 페이지를 SPT에 등록한다.
5. 한 페이지 등록이 끝나면, 다음 페이지를 위해 read_bytes, zero_bytes, upage, ofs를 갱신한다.

ⓐ. file_reopen

ⓐ-⑴. inode_reopen

ⓐ-⑴_1. struct inode

struct list_elem elem; → 현재 메모리에 올라와 있는 inode들을 전역 inode 리스트(inode_list)로 연결하기 위한 노드
disk_sector_t sector; → 이 inode 정보가 디스크의 어느 sector에 저장되어 있는지 나타냄
int open_cnt; → 현재 이 inode를 몇 명이 사용중인지(reference count)관리
bool removed; → 파일이 삭제(removed) 요청 되었는지 표시 [삭제 예약 상태 표시]
int deny_write_cnt; → 현재 이 inode에 대해 쓰기를 막고 있는 횟수 (주로 실행 파일 보호에 사용)
struct inode_disk data; → 디스크에 저장되는 inode 메타 데이터
  •  struct list_elem elem
inode_list
 ├── inode A
 ├── inode B
 └── inode C
 이렇게 커널이 "이미 열린 inode"들을 관리할 수 있게 해준다.
  • 같은 파일을 여러 번 열어도 inode를 중복 생성하지 않기 위해
  • 이미 열린 inode를 재사용하기 위해
  • close 시점 관리를 위해
  • disk_sector_t sector
    • inode 자체도 디스크에 저장되므로, 다시 열 때 이 sector를 이용해 inode_disk를 읽어온다.
    • inode 메타데이터가 저장된 디스크 위치
  • int open_cnt
    • 마지막 사용자가 close 할 때만 실제 inode를 메모리에서 제거해야 하기 때문
  • bool removed
    • Linux/Pintos는 remove()했다고 즉시 파일 삭제 X
    • 왜냐하면 열려 있는 프로세스가 아직 사용 중일 수 있기 때문에 (이 경우 디렉토리에서는 사라지지만, 실제 데이터는 유지)
  • int deny_write_cnt
    • 프로그램 실행 도중 executable이 수정되면 위험하기 때문에
  • struct inode_disk data
    • 파일크기, 데이터 위치, magic number 등등 (실제 파일 자체의 핵심 정보)

ⓐ-⑴_2. struct inode_disk

disk_sector_t start; → 파일 데이터가 저장된 첫 번째 디스크 sector (파일 내용이 어디서부터 시작되는가)
off_t length; → 파일의 실제 크기(Byte 단위)
unsigned magic; → 이 inode 구조체가 정상적인 inode인지 검증하기 위한 값 (디스크 손상 여부 확인)
uint32_t unused[125]; → 현재는 사용하지 않는 공간이지만, "미래 확장용 - 향후 파일 블록 인덱싱 확장을 위한 예약공간"

ⓐ-⑵. file_open

1. calloc으로 커널힙에 struct file 크기의 메모리를 할당하고, 그 내용을 전부 0으로 초기화
2. inode와 file이 모두 정상이라면 file 객체를 초기화
    ㄴ file 객체가 어떤 inode를 가리키는지 연결
    ㄴ 파일 읽기/쓰기 위치를 파일의 처음으로 설정
    ㄴ 이 file 객체는 아직 write 금지 요청을 하지 않은 상태
3. inode가 존재하지 않거나, file이 할당되지 않으면 inode_close로 inode의 open_cnt를 감소시키고, open_cnt가 0 이고 removed 상태라면 실제 삭제/해제까지 진행

ⓐ-⑵_1. inode_close

이 내용은 너무 공부하고 싶은데, 설명은 담에..
그래도 공부 해보고 싶은 분이 계실 수 있으니 코드만 따로 접은글에 추가

접은글 : inode_close -> free_map_release, bytes_to_sectors etc...

더보기
/* Closes INODE and writes it to disk.
 * If this was the last reference to INODE, frees its memory.
 * If INODE was also a removed inode, frees its blocks. */
void
inode_close (struct inode *inode) {
	/* Ignore null pointer. */
	if (inode == NULL)
		return;

	/* Release resources if this was the last opener. */
	if (--inode->open_cnt == 0) {
		/* Remove from inode list and release lock. */
		list_remove (&inode->elem);

		/* Deallocate blocks if removed. */
		if (inode->removed) {
			free_map_release (inode->sector, 1);
			free_map_release (inode->data.start,
					bytes_to_sectors (inode->data.length)); 
		}

		free (inode); 
	}
}
/* Makes CNT sectors starting at SECTOR available for use. */
void
free_map_release (disk_sector_t sector, size_t cnt) {
	ASSERT (bitmap_all (free_map, sector, cnt));
	bitmap_set_multiple (free_map, sector, cnt, false);
	bitmap_write (free_map, free_map_file);
}

- bitmap_all

/* Returns true if every bit in B between START and START + CNT,
   exclusive, is set to true, and false otherwise. */
bool
bitmap_all (const struct bitmap *b, size_t start, size_t cnt) {
	return !bitmap_contains (b, start, cnt, false);
}
/* Returns true if any bits in B between START and START + CNT,
   exclusive, are set to VALUE, and false otherwise. */
bool
bitmap_contains (const struct bitmap *b, size_t start, size_t cnt, bool value) {
	size_t i;

	ASSERT (b != NULL);
	ASSERT (start <= b->bit_cnt);
	ASSERT (start + cnt <= b->bit_cnt);

	for (i = 0; i < cnt; i++)
		if (bitmap_test (b, start + i) == value)
			return true;
	return false;
}
/* Returns the value of the bit numbered IDX in B. */
bool
bitmap_test (const struct bitmap *b, size_t idx) {
	ASSERT (b != NULL);
	ASSERT (idx < b->bit_cnt);
	return (b->bits[elem_idx (idx)] & bit_mask (idx)) != 0;
}
/* Returns the index of the element that contains the bit
   numbered BIT_IDX. */
static inline size_t
elem_idx (size_t bit_idx) {
	return bit_idx / ELEM_BITS;
}
/* Returns an elem_type where only the bit corresponding to
   BIT_IDX is turned on. */
static inline elem_type
bit_mask (size_t bit_idx) {
	return (elem_type) 1 << (bit_idx % ELEM_BITS);
}
/* Element type.

   This must be an unsigned integer type at least as wide as int.

   Each bit represents one bit in the bitmap.
   If bit 0 in an element represents bit K in the bitmap,
   then bit 1 in the element represents bit K+1 in the bitmap,
   and so on. */
typedef unsigned long elem_type;

/* Number of bits in an element. */
#define ELEM_BITS (sizeof (elem_type) * CHAR_BIT)

- bitmap_set_multiple

/* Sets the CNT bits starting at START in B to VALUE. */
void
bitmap_set_multiple (struct bitmap *b, size_t start, size_t cnt, bool value) {
	size_t i;

	ASSERT (b != NULL);
	ASSERT (start <= b->bit_cnt);
	ASSERT (start + cnt <= b->bit_cnt);

	for (i = 0; i < cnt; i++)
		bitmap_set (b, start + i, value);
}
/* Atomically sets the bit numbered IDX in B to VALUE. */
void
bitmap_set (struct bitmap *b, size_t idx, bool value) {
	ASSERT (b != NULL);
	ASSERT (idx < b->bit_cnt);
	if (value)
		bitmap_mark (b, idx);
	else
		bitmap_reset (b, idx);
}
/* Atomically sets the bit numbered BIT_IDX in B to true. */
void
bitmap_mark (struct bitmap *b, size_t bit_idx) {
	size_t idx = elem_idx (bit_idx);
	elem_type mask = bit_mask (bit_idx);

	/* This is equivalent to `b->bits[idx] |= mask' except that it
	   is guaranteed to be atomic on a uniprocessor machine.  See
	   the description of the OR instruction in [IA32-v2b]. */
	asm ("lock orq %1, %0" : "=m" (b->bits[idx]) : "r" (mask) : "cc");
}
/* Atomically sets the bit numbered BIT_IDX in B to false. */
void
bitmap_reset (struct bitmap *b, size_t bit_idx) {
	size_t idx = elem_idx (bit_idx);
	elem_type mask = bit_mask (bit_idx);

	/* This is equivalent to `b->bits[idx] &= ~mask' except that it
	   is guaranteed to be atomic on a uniprocessor machine.  See
	   the description of the AND instruction in [IA32-v2a]. */
	asm ("lock andq %1, %0" : "=m" (b->bits[idx]) : "r" (~mask) : "cc");
}

- bitmap_write

/* Writes B to FILE.  Return true if successful, false
   otherwise. */
bool
bitmap_write (const struct bitmap *b, struct file *file) {
	off_t size = byte_cnt (b->bit_cnt);
	return file_write_at (file, b->bits, size, 0) == size;
}

-bytes_to_sector

/* Returns the number of sectors to allocate for an inode SIZE
 * bytes long. */
static inline size_t
bytes_to_sectors (off_t size) {
	return DIV_ROUND_UP (size, DISK_SECTOR_SIZE);
}
/* Yields X divided by STEP, rounded up.
 * For X >= 0, STEP >= 1 only. */
#define DIV_ROUND_UP(X, STEP) (((X) + (STEP) - 1) / (STEP))
file_open
이미 열린 inode를 기반으로, 프로세스가 사용하는 file 객체를 새로 만드는 함수
struct file은 파일을 읽고 쓰는 현재 위치(pos)와 쓰기 금지 여부(deny_write)를 file 객체 단위로 관리
inode는 파일의 실제 메타데이터를 나타내고, file은 그 inode를 사용하는 하나의 open 객체에 가깝다.
따라서 같은 inode라도 여러 번 open 하면 여러 개의 file 객체가 만들어질 수 있고, 각 file 객체는 서로 다른 pos 값을 가질 수 있다.

 

2. lazy_load_segment

접은글 : lazy_load_segment 구현

이 함수는 "나중에 필요해진 실행 파일의 한 페이지를 실제 메모리에 채우는 함수"다.
처음부터 모든 ELF segment를 메모리에 올리지 않고, 해당 주소에 처음 접근해서 page fault가 났을 때 프레임을 하나 잡고, 그 프레임의 커널 주소 kva에 파일 내용을 읽어 넣는다. 그리고 파일에서 온 데이터가 페이지 전체를 채우지 못하면 남는 공간은 0으로 채우는 함수이다.

ⓐ. file_read_at

ⓐ-⑴. inode_read_at

하나하나 함수를 파 보면서 확인하는 건 정말 힘들고 지치는 작업이기에
실제로 aux를 통해 lazy_load_segment에 전달되는 값을 기반으로 예시를 보여주고자 한다.
만약 사용자 프로그램이 6000bytes의 파일 크기를 갖고 있다고 가정 0x8000 kva가 버퍼 시작 지점
<1 page>
파일 크기 = 6000 bytes
1 page = 4096 bytes
DISK_SECTOR_SIZE = 512 bytes
kva 첫 위치 = 0x8000

1번째 page lazy load
inode_read_at(inode, 0x8000, 4096, 0);​
초기 값
buffer = 0x8000
size = 4096
offset = 0
bytes_read = 0​
읽는 흐름
offset 0      -> 512 bytes 읽음
offset 512    -> 512 bytes 읽음
offset 1024   -> 512 bytes 읽음
offset 1536   -> 512 bytes 읽음
offset 2048   -> 512 bytes 읽음
offset 2560   -> 512 bytes 읽음
offset 3072   -> 512 bytes 읽음
offset 3584   -> 512 bytes 읽음​
<1 page: kva 0x8000>

0x8000                                      0x8FFF
|----------------------------------------------|
| file data 4092 bytes                  
|----------------------------------------------|

2번째 page lazy load

inode_read_at(inode, 0x9000, 1904, 4096);

초기값

buffer = 0x9000
size = 1904
offset = 4096
bytes_read = 0

 

여기서 핵심은 4096 % 512 = 0
두 번째 page 내부 흐름
offset 4096   -> 512 bytes
offset 4608   -> 512 bytes
offset 5120   -> 512 bytes
offset 5632   -> 368 bytes

 

마지막에 368 bytes에서

offset 5632
sector_ofs = 0
sector_left = 512 - 0 = 512
size = 368
chunk_size = 368​

 

마지막엔 368 바이트를 읽고 종료함
위 내용의 예시를 설명한 이유
VM의 lazy loading에서는 페이지 단위로 inode_read_at()을 호출하기 때문에, 겉으로 보면 단순히 한 페이지에 필요한 read_bytes만 읽어오는 것처럼 보인다.

하지만 실제 inode_read_at()은 페이지 단위 함수가 아니라, 파일의 특정 offset부터 원하는 size만큼 읽는 범용 파일 읽기 함수이다.

그리고 디스크는 sector 단위로만 읽을 수 있기 때문에, 이 함수 내부에서는 offset이 sector 안에서 몇 번째 위치인지 계산하고, 필요한 만큼 chunk_size를 나누어 읽는다.

따라서 VM 구현만 볼 때는 깊게 의식하지 않아도 되지만, inode_read_at()을 제대로 이해하려면
"페이지 단위 요청을 받아도 내부에서는 sector 단위로 쪼개 읽는다"는 점이 중요하다.

참고 : 주석 달린 inode_read_at()

더보기
/* Reads SIZE bytes from INODE into BUFFER, starting at position OFFSET.
 * Returns the number of bytes actually read, which may be less
 * than SIZE if an error occurs or end of file is reached. */
off_t
inode_read_at (struct inode *inode, void *buffer_, off_t size, off_t offset) {
	/**
	 * 사용자가 넘긴 void* 버퍼를 바이트 단위로 다루기 위해 utin8_t로 변환
	 * uint8_t는 1바이트짜리 타입이라 buffer + n 같은 계산이 편하다.
	 */
	uint8_t *buffer = buffer_;
	/**
	 * 지금까지 실제로 읽은 byte 수
	 */
	off_t bytes_read = 0;
	/**
	 * 부분 섹터를 읽을 때 사용할 임시 버퍼
	 * disk_read()는 섹터 단위, 즉 보통 512 바이트 단위로만 읽을 수 있기 때문에
	 * 파일의 일부 바이트만 필요해도 일단 섹터 전체를 읽어야 한다.
	 */
	uint8_t *bounce = NULL;

	/**
	 * 아직 읽어야 할 바이트가 남아 있는 동안 반복
	 */
	while (size > 0) {
		/* Disk sector to read, starting byte offset within sector. */
		/**
		 * offset 위치의 파일 바이트가 실제 디스크의 어느 섹터에 있는지 구한다.
		 * 
		 * offset은 "파일 내부에서 몇 번째 바이트인가"이고,
		 * sector_idx는 "그 바이트가 저장된 실제 디스크 섹터 번호"다.
		 * 
		 * 단순히 offset / 512가 아닌 이유는,
		 * 파일의 논리적 위치와 디스크의 실제 섹터 번호가 꼭 연속적이지 않을 수 있기 때문이다.
		 * 그래서 inode의 블록 포인터 정보를 보고 byte_to_sector()가 실제 섹터를 찾아준다.
		 */
		disk_sector_t sector_idx = byte_to_sector (inode, offset);
		/**
		 * 해당 섹터 안에서 offset이 몇 번째 바이트 위치인지 계산한다.
		 * 
		 * DISK_SECTOR_SIZE는 보통 512다.
		 * 디스크가 데이터를 읽고 쓰는 기본 단위가 섹터이고,
		 * Pintos에서는 섹터 크기를 512바이트로 정의해서 사용한다.
		 * 
		 * 예를 들어 offset이 1000이면
		 * 1000 % 512 = 488
		 * 즉, 해당 섹터 안의 488번째 바이트부터 읽기 시작한다.
		 */
		int sector_ofs = offset % DISK_SECTOR_SIZE;

		/* Bytes left in inode, bytes left in sector, lesser of the two. */
		/**
		 * 현재 offset부터 파일 끝까지 남은 바이트 수
		 * 
		 * inode_length(inode)는 파일 전체 길이다.
		 * offset이 파일 끝에 가까우면 읽을 수 있는 양이 줄어든다.
		 */
		off_t inode_left = inode_length (inode) - offset;
		/**
		 * 현재 섹터 안에서 읽을 수 있는 남은 바이트 수
		 * 
		 * 섹터 크기가 512이고 sector_ofs가 100이면,
		 * 이 섹터에서 남은 공간은 512 - 100 = 412바이트다.
		 */
		int sector_left = DISK_SECTOR_SIZE - sector_ofs;
		/**
		 * 파일 끝까지 남은 양과 현재 섹터 끝까지 남은 양 중 더 작은 값
		 * 
		 * 즉, 이번 섹터에서 안전하게 읽을 수 있는 최대 바이트 수
		 * 파일 끝을 넘어 읽으면 안 되고, 한 번에 현재 섹터 경계를 넘어 읽지도 않는다.
		 */
		int min_left = inode_left < sector_left ? inode_left : sector_left;

		/* Number of bytes to actually copy out of this sector. */
		/**
		 * 이번 반복에서 실제로 읽을 바이트 수
		 * 
		 * 사용자가 아직 요청한 size와
		 * 이번 섹터에서 읽을 수 있는 min_left 중 작은 값
		 * 
		 * 읽을 수 있는 양이 0 이하라면 중단 (보통 offset이 파일 끝에 도달했거나 넘어간 경우)
		 */
		int chunk_size = size < min_left ? size : min_left;
		if (chunk_size <= 0)
			break;

		/**
		 * sector_ofs가 0이고 chunk_size가 섹터 크기와 같다는 것은
		 * 현재 offset이 섹터 시작점에 딱 맞고, 읽을 양도 정확히 512바이트라는 뜻
		 * 
		 * 이 경우 섹터 전체를 그대로 사용자 버퍼에 읽어도 된다. 임시 버퍼가 필요 없음
		 */
		if (sector_ofs == 0 && chunk_size == DISK_SECTOR_SIZE) {
			/* Read full sector directly into caller's buffer. */
			/**
			 * 디스크에서 sector_idx 섹터 하나를 읽어서
			 * buffer + bytes_read 위치에 바로 저장한다.
			 */
			disk_read (filesys_disk, sector_idx, buffer + bytes_read); 
		} else {
			/* Read sector into bounce buffer, then partially copy
			 * into caller's buffer. */
			/**
			 * 부분 섹터 읽기
			 * 
			 * disk_read()는 섹터 전체를 읽기 때문에,
			 * 필요한 부분만 바로 읽을 수 없다.
			 * 
			 * 그래서 먼저 bounce에 섹터 전체 512바이트를 읽고,
			 * 그중 필요한 부분만 사용자 버퍼로 memcpy한다.
			 * 
			 * 만약 bounce 버퍼가 아직 없다면 512바이트짜리 임시 버퍼를 할당한다.
			 */
			if (bounce == NULL) {
				bounce = malloc (DISK_SECTOR_SIZE);
				/**
				 * 메모리 할당 실패 시 더 읽을 수 없으므로 중단
				 */
				if (bounce == NULL)
					break;
			}
			/**
			 * 디스크에서 섹터 전체를 bounce 버퍼로 읽는다.
			 */
			disk_read (filesys_disk, sector_idx, bounce);
			/**
			 * bounce 안에서 sector_ofs 위치부터 chunk_size 바이트만큼
			 * 사용자 버퍼의 현재 위치로 복사한다.
			 */
			memcpy (buffer + bytes_read, bounce + sector_ofs, chunk_size);
		}

		/* Advance. */
		/**
		 * 이번에 chunk_size만큼 읽었으므로 앞으로 읽어야 할 크기를 줄인다.
		 */
		size -= chunk_size;
		/**
		 * 파일 내 읽기 위치를 chunk_size만큼 앞으로 이동시킨다.
		 */
		offset += chunk_size;
		/**
		 * 실제로 읽은 총 바이트 수를 증가시킨다.
		 */
		bytes_read += chunk_size;
	}
	/**
	 * 부분 섹터 읽기에 사용했던 임시 버퍼를 해제한다.
	 * bounce가 NULL이어도 free(NULL)은 안전하다.
	 */
	free (bounce);

	/**
	 * 최종적으로 실제 읽은 바이트 수를 반환한다.
	 * 요청한 size보다 작을 수 있다.
	 * ex: 파일 끝에 도달했거나, malloc 실패 등
	 */
	return bytes_read;
}