📝 배운 것들
🏷️ 1KB, 1MB 비트 연산 표시
1MB : (1 << 10) = 2의 10승
1KB : (1 << 20) = 2의 20승
🖥️ PintOS
🔷 Virtual Memory
📌 Stack Growth
User program은 스택 포인터 아래의 스택에 쓸 경우 버그가 발생하는데, 이는 일반적인 실제 OS가 스택의 데이터를 수정하는 시그널을 전달하기 위해 프로세스를 언제든지 중단할 수 있기 때문입니다.
이거 원문도 이상해서 번역본도 이상한데,
User programs are buggy if they write to the stack below the stack pointer, because typical real OSes may interrupt a process at any time to deliver a "signal," which modifies data on the stack.
원문 보면 대충 이해가 가긴 함.
실제 OS들은 스택 포인터 아래에 있는 스택에 쓰려고 하면
프로세스에 시그널 보내서 스택에 있는 데이터 수정한다고 함.
exception.c에 있는 page_fault에서
if (vm_try_handle_fault(f, fault_addr, user, write, not_present))
return;로 vm_try_handle_fault()에서 새로운 스택을 할당할지 말지 확인
8바이트 아래면 새롭게 스택을 할당하고 true 반환하고 그 밖이면 false 반환
테스트해보기 위해 무작정 8 더해줌
동기에게 물어보니 이렇게 하는게 맞다고 한다.
%p로 출력했으니 16진수로 출력되는 것.
그리고 왜 8바이트가 기준인건지 물어봤는데
push의 규약 때문이라는 얘기를 들음
8바이트 이내가 아니라 정확히 8바이트 아래를 요청하는거면
스택을 늘려줘야 하는거구나 생각하고 늘려주기
당신은 User Program의 스택 포인터의 현재 값을 얻을 수 있어야 합니다. System Call 또는 User Program에 의해 발생한 Page Fault 루틴에서 각각 syscall_handler()또는 page_fault()에 전달된 struct intr_frame의 rsp멤버에서 검색할 수 있습니다.
잘못된 메모리 접근을 감지하기 위해 Page Fault에 의존하는 경우, 커널에서 Page Fault가 발생하는 경우도 처리해야 합니다. 프로세스가 스택 포인터를 저장하는 것은 예외로 인해 유저 모드에서 커널 모드로 전환될 때 뿐이므로 page_fault()로 전달된 struct intr_frame 에서 rsp를 읽으면 유저 스택 포인터가 아닌 정의되지 않은 값을 얻을 수 있습니다. 유저 모드에서 커널 모드로 전환 시 rsp를 struct thread에 저장하는 것과 같은 다른 방법을 준비해야 합니다.
잘못된 메모리 접근을 감지하기 위해 Page Fault에 의존하는 경우, 부터는 안 해줘도 된다고 함.
일단 메모리 접근을 페이지 폴트에 의존 안 하고 있고, 그 다음에 설명하는 건 커널 모드에서 폴트 나는 건데 그런 상황이 안 일어날 것 같다고? 함
rsp는 페이지 폴트나 시스템 콜로 인해 유저 모드에서 커널 모드로 넘어갈 때 저장됨.
bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
struct page *page = NULL;
if (addr == NULL)
return false;
if (is_kernel_vaddr(addr))
return false;
if (addr == f->rsp - 8)
vm_stack_growth(addr);static void
vm_stack_growth(void *addr UNUSED)
{
vm_alloc_page(VM_ANON | VM_MARKER_0, pg_round_down(addr), 1);
}일단 깃북에서 하라는대로 함.
rsp의 8바이트 아래면 페이지 할당.
그 addr은 pg_round_down 먹여주기.
테스트 돌려봤더니 1개만 추가로 통과함.
뭐가 추가로 통과한지도 모르겠.
if (addr < (1 << 20) && addr == f->rsp - 8)
addr 1MB도 체크해줬는데 변화 x
/* Return true on success */
bool vm_try_handle_fault(struct intr_frame *f UNUSED, void *addr UNUSED,
bool user UNUSED, bool write UNUSED, bool not_present UNUSED)
{
struct supplemental_page_table *spt UNUSED = &thread_current()->spt;
struct page *page = NULL;
if (addr == NULL)
return false;
if (is_kernel_vaddr(addr))
return false;
if (not_present) // 접근한 메모리의 physical page가 존재하지 않은 경우
{
if (addr < (1 << 20) && addr == f->rsp - 8)
vm_stack_growth(addr);물어봤는데 stack_growth의 위치를 바꿔줘야 한다고 함.
바꿔줬는데도 안됨.
if ((USER_STACK - (1 << 20) < f->rsp) && addr == f->rsp - 8)
vm_stack_growth(addr);
else if ((USER_STACK - (1 << 20) < f->rsp) && addr >= f->rsp)
vm_stack_growth(addr);애초에 바보같이 이상한 조건문을 껴넣었던 거임.
rsp가 1MB 이하인지를 확인해야함.
addr가 rsp보다 작은지도 그냥 확인해준다고 함.
고쳤더니 grow 중 다른거 통과하는데
Differences in `diff -u' format:
(pt-grow-stk-sc) begin
(pt-grow-stk-sc) create "sample.txt"
(pt-grow-stk-sc) open "sample.txt"
(pt-grow-stk-sc) write "sample.txt"
(pt-grow-stk-sc) 2nd open "sample.txt"
(pt-grow-stk-sc) read "sample.txt"
- (pt-grow-stk-sc) compare written data against read data
- (pt-grow-stk-sc) end이것만 통과를 못함
FAIL tests/vm/pt-write-code2 run: survived reading data into code segment: FAILED
이것도 통과 못함
case SYS_READ:
if (pml4_get_page(thread_current()->pml4, f->R.rsi) && !spt_find_page(&thread_current()->spt, f->R.rsi)->writable)
{
f->R.rax = -1;
exit(-1);
}
f->R.rax = read(f->R.rdi, f->R.rsi, f->R.rdx);
break;syscall.c 돌아가서 이거 해줘야 한다고 함.
if문 앞 조건은 이미 프레임이 할당돼있는데 접근해서 써버리면 안되니까,
spt에 없으면 이상한 놈이니까 꺼버리기
read인데 왜 pml4에 할당돼있는지 없는지 확인? 라고 물어보니까
read도 결국 file에서 buffer에 쓰는거라
엄한데 접근해서 써버리게 되면 안된다고 함.
perl -I../.. ../../tests/vm/pt-write-code2.ck tests/vm/pt-write-code2 tests/vm/pt-write-code2.result
pass tests/vm/pt-write-code2write-code2는 통과했는데 pt-grow-stk-sc는 아직 통과 안됨.
if ((USER_STACK - (1 << 20) <= f->rsp - 8) && addr == f->rsp - 8)
vm_stack_growth(addr);
else if ((USER_STACK - (1 << 20) <= f->rsp - 8) && addr <= f->rsp)
vm_stack_growth(addr);addr <= f->rsp 부등호 방향 바꿔줬더니 pt-grow-stk-sc도 통과.
근데 다른게 터짐;
아니 분명 커널에서 rsp 쓰는 경우 없다고 들었는데 (이 사람이 제일 잘함)
다른 사람한테 들으니까 쓴다고 하는데 뭐지
일단 어떻게 하는지는 들어옴
- setup_stack에서 쓰레드에서 rsp를 저장해놓는다
- user비트 확인해서 시스템 콜에서 부른거면 rsp를 쓰레드에서 가져온다
setup_stack 말고 syscall_handler 시작할때도 rsp 저장해놓아야 함.
그랬더니 pt-grow-stk-sc 통과.
33개 남음.
📌 Memory Mapped Files
d로 열린 파일의 오프셋(offset) 바이트부터 length 바이트 만큼을 프로세스의 가상주소공간의 주소 addr 에 매핑 합니다.
전체 파일은 addr에서 시작하는 연속 가상 페이지에 매핑됩니다. 파일 길이(length)가 PGSIZE의 배수가 아닌 경우 최종 매핑된 페이지의 일부 바이트가 파일 끝을 넘어 "stick out"됩니다.
stick out의 의미 : 맨 마지막에 파일 아니고 페이지 정렬 맞춰주려고 할당된 용량들에 있는 것들은 스왑 인 아웃할 때 무시한다는 뜻
/* Do the mmap */
void *
do_mmap(void *addr, size_t length, int writable,
struct file *file, off_t offset)
{
if (file_length(file) == 0)
return NULL;
if ((uintptr_t)addr % (1 << 12) == 0)
return NULL;
if (pml4_get_page(thread_current()->pml4, addr))
return NULL;
if (addr = 0)
return NULL;
if (length == 0)
return NULL;
vm_alloc_page(VM_FILE | VM_MARKER_0, addr, 1);
}
/* Do the munmap */
void do_munmap(void *addr)
{
struct page *page = spt_find_page(&thread_current()->spt, addr);
spt_remove_page(&thread_current()->spt, page);
file_write_at(file,);
pml4_clear_page(thread_current()->pml4, addr);
}아쉽게도 여기까지.
내일 더 해볼 수 있으면 해볼 생각.
너무 주변 사람 의존을 늦게 했다.
진작에 물어보고 다녔어야 됐는데.
⚔️ 백준
📌 2098 외판원 순회
스터디 시간이 다가와서 답지 봄.
시간 더 준다고 해도 풀진 못했을듯.
재귀 dp 비트마스킹
import sys
imput=sys.stdin.readline
# 도시개수
n=int(input())
# 비용 행렬
w=[]
for i in range(n):
w.append([])
w[i]=list(map(int,input().split()))
d=[[0 for j in range(1<<16)] for i in range(16)] # n(1~16)
def tsp(c,v):
if v==(1<<n)-1: # 모든노드 방문
if w[c][0] ==0: # 시작도시로 들어갈 수 없음
return float('inf')
else:
return w[c][0]
if d[c][v]!=0: # 이미방문
return d[c][v]
res = float('inf')
for i in range(0,n):
if (v&(1<<i))==0 and w[c][i]!=0: # 방문한 적없고, 갈수 있는 도시
res = min(res, tsp(i, (1<<i))+w[c][i])
d[c][v] = res
return d[c][v]
print(tsp(0,1))이거 좀 안 좋은 코드긴 한듯 0을 2의 16승 개 선언해버림
아직 dp 어렵다 이해가 잘 안됨
