[05.21 / week10]TIL

CHO WanGi·2025년 5월 20일

jungle

KRAFTON JUNGLE 8th

목록 보기

57/89

오늘 하루 요약

✏️ 오늘의 한 일

Args Passing 완료...?
프로그래머스 JS, 전력망을 둘로 나누기

🌈오늘의 성장!

Args Passing

int process_exec(void *f_name)
{
	char *file_name = f_name;
	bool success;

	/* We cannot use the intr_frame in the thread structure.
	 * This is because when current thread rescheduled,
	 * it stores the execution information to the member. */
	struct intr_frame _if;
	_if.ds = _if.es = _if.ss = SEL_UDSEG;
	_if.cs = SEL_UCSEG;
	_if.eflags = FLAG_IF | FLAG_MBS;

	/* We first kill the current context */
	process_cleanup();

	// 1.Break the command
	char *token;
	char *save_ptr;

	// file name에서 공백을 만나면 문자열 자르고 save_ptr에 다음 문자열 주소 저장
	// 첫번째 호출
	token = strtok_r(file_name, " ", &save_ptr); // args-single onearg 일경우 args-single

	char *argv[99];
	int argc = 0;

	while (token != NULL)
	{
		argv[argc] = token; // 자른 문자열 저장
		argc++;
		token = strtok_r(NULL, " ", &save_ptr); // args-single onearg 일경우 args-single
	}

	/* And then load the binary */
	success = load(file_name, &_if); // setup_stack 을 통해 rsp를 초기화 => argv 쌓기

	// 2. Place the words at the top of Stack
	// first push 전 8의 배수로 round 후 push => 더 좋은 성능보장 목적
	// argv의 마지먁 idx부터 들어가야함.

	char *arg_stack_addrs[64]; // 문자열의 스택 주소를 저장하기 위함

	for (int i = 0; i < argc; i++)
	{
		uint16_t length = strlen(argv[i]);
		_if.rsp = _if.rsp - (length + 1); // str의 길이 + \0 만큼 stack top pointer 이동(높은 주소 -> 낮은 주소)
		arg_stack_addrs[i] = _if.rsp;			// TOS 주소 저장
		// printf("addrval : %X\n", arg_stack_addrs[i]);
		// printf("argv : %s, %d\n", argv[i], i);

		memcpy(arg_stack_addrs[i], argv[i], length); // 주소에 argv 값 복사해서 저장(Stack에 push)
	}

	// Padding(8의 배수로 round up)
	uintptr_t addrval = _if.rsp; // 현재 rsp (TOS) 주소값
	// 8로 나눈 나머지가 0으로 채울 공간
	while (_if.rsp % 8 != 0)
	{
		_if.rsp--; // 낮은 주소로 1바이트씩 이동
		*((char *)_if.rsp) = 0;
	}

	// NULL 삽입
	_if.rsp -= sizeof(char *); // char * 사이즈 만큼 이동
	*((char **)_if.rsp) = 0;	 // NULL 로 채우기

	// 주소값 Push
	// 3. Push the address of each string + null pointer(\0)
	for (int i = argc - 1; i >= 0; i--)
	{
		_if.rsp -= sizeof(char *);
		*((char **)_if.rsp) = arg_stack_addrs[i];
	}

	// 4. %rsi가 argv(argv[0]) 가리키고, %rdi가 argc 가리키도록(Point)
	_if.R.rdi = argc;
	_if.R.rsi = _if.rsp;
	// 5. 가짜 return address push

	_if.rsp -= sizeof(void *);
	*((void **)_if.rsp) = 0;

	// hex_dump(_if.rsp, _if.rsp, USER_STACK - _if.rsp, true);
	/* If load failed, quit. */
	palloc_free_page(file_name);
	if (!success)
		return -1;

	/* Start switched process. */
	do_iret(&_if);
	NOT_REACHED();
}

Kernel Panic

Calibrating timer...  19,635,200 loops/s.
hd0:0: detected 313 sector (156 kB) disk, model "QEMU HARDDISK", serial "QM00001"
hd0:1: detected 20,160 sector (9 MB) disk, model "QEMU HARDDISK", serial "QM00002"
hd1:0: detected 102 sector (51 kB) disk, model "QEMU HARDDISK", serial "QM00003"
Formatting file system...done.
Boot complete.
Putting 'args-single' into the file system...
Executing 'args-single':
Page fault at 0x8025867b60: not present error writing page in kernel context.
Interrupt 0x0e (#PF Page-Fault Exception) at rip=800421b65c
 cr2=0000008025867b60 error=               2
rax 00000000042b6001 rbx 0000000000000000 rcx 0000000000000000 rdx 00000080042b6000
rsp 00000080042b7b40 rbp 00000080042b7fb0 rsi 0000000000000000 rdi 00000080042245fa
rip 000000800421b65c r8 0000000000000000  r9 0000000000000000 r10 0000000000000000
r11 0000000000000000 r12 0000000000000000 r13 0000000000000000 r14 0000000000000000
r15 0000000000000000 rflags 00000206
es: 0010 ds: 0010 cs: 0008 ss: 0010

이렇게 뜨길래 GDB를 찍었더니

(gdb) n
196             while (token != NULL)
(gdb) n
198                     argv[argc] = token; // 자른 문자열 저장
(gdb) n
199                     argc++;
(gdb) n
200                     token = strtok_r(file_name, " ", &save_ptr); // args-single onearg 일경우 args-single
(gdb) n
196             while (token != NULL)
(gdb) n
198                     argv[argc] = token; // 자른 문자열 저장
(gdb) p argc
$14 = 60

내가 넘긴건 args-single onearg 이라서 argc가 2가 되어야하는데
60까지 갔길래 뭔가 했더니
strtok_r 함수를 통해 token을 갱신하는 과정에서 계속해서 args-single onearg 원본 문자열을
넘긴 것.

이를 수정했더니 해결이... 되는줄 알았는데

# -*- perl -*-
use strict;
use warnings;
use tests::tests;
check_expected ([<<'EOF']);
(args) begin
(args) argc = 2
(args) argv[0] = 'args-single'
(args) argv[1] = 'onearg'
(args) argv[2] = null
(args) end
args-single: exit(0)
EOF
pass;

이렇게 테스트 결과가 떠야하는데 hex_dump로 봤을땐

이렇게 잘 들어갔음에도 저기 argv 프린트가 안나와서 테스트 통과를 못하고 있다...
낼 아침에 정신 맑을때 해결해보자...

프로그래머스 JS, 전력망을 둘로 나누기

-문제 조건 : 두 전력망의 개수 차이의 최소값
n : 송전탑 개수
wires : 전력망

https://school.programmers.co.kr/learn/courses/30/lessons/86971

GRAPH 생성 + BFS 탐색
그래프를 만들고 제외할 노드를 고른 뒤 그 제외한 노드를 만날때는 탐색을 하지 않는방식으로 거른다.
이게 양뱡향 연결이기에 마지막에 Math.abs(BFS(start, end) - BFS(end, start) 같이 계산

function solution(n, wires) {
    var answer = Number.MAX_SAFE_INTEGER;
//     Union-Find....?
//     1. 끊을 선 정하기 => 완전탐색
    const graph = Array.from(Array(n + 1), () => []);

    wires.forEach((elem) => {
        graph[elem[0]].push(elem[1])
        graph[elem[1]].push(elem[0])
    })
    console.log(graph);
    
    
    function BFS(start, exception){
        let visited = Array.from(Array(n + 1), () => false);
        let count = 0;
        visited[start] = true
        let queue = [start];
        
        while(queue.length != 0){
            let node = queue.shift();
            graph[node].forEach((elem) => {
                if (elem !== exception && visited[elem] === false) {
                  visited[elem] = true;
                  queue.push(elem);
                }
              });
            count++;
        }

        return count;
    }
    
    wires.forEach((elem) => {
        let[start, end] = elem;
        answer = Math.min(answer , Math.abs(BFS(start, end) - BFS(end, start)) );
    })
   
    
    return answer;
}

Union-Find
반면 Union_find는 공통 원소가 없는 집합들을 다루기 위한 알고리즘이다.
그래프에서 연결요소를 찾는데 활용가능하다.
즉 우리가 제외할 노드만 반복문을 통해 완전탐색으로 고르고
각 연결 요소를 이루는 노드의 개수 차이가 정답이 되겠다.

function solution(n, wires) {
    let minDifference = Number.MAX_SAFE_INTEGER;

    // Union-Find 헬퍼 함수들
    function find(parent, i) {
        if (parent[i] === i) return i;
        return parent[i] = find(parent, parent[i]); // 경로 압축
    }

    function union(parent, i, j) {
        const rootI = find(parent, i);
        const rootJ = find(parent, j);
        if (rootI !== rootJ) {
            parent[rootJ] = rootI; 
            return true;
        }
        return false;
    }

    for (let i = 0; i < wires.length; i++) {
        // 1. i번째 전선을 끊는다고 가정
        const cutWire = wires[i];

        // 2. Union-Find 초기화
        let parent = Array.from({ length: n + 1 }, (_, idx) => idx);

        // 3. 끊어진 전선을 제외한 나머지 전선들로 union 연산
        for (let j = 0; j < wires.length; j++) {
            if (i === j) continue; // 현재 끊기로 한 전선은 제외

            const [node1, node2] = wires[j];
            union(parent, node1, node2);
        }

        // 4. 컴포넌트 크기 계산
        let size1 = 0;
        const rootOfCutWireComponent = find(parent, cutWire[0]); // 끊어진 선의 한쪽 끝을 기준으로

        for (let k = 1; k <= n; k++) {
            if (find(parent, k) === rootOfCutWireComponent) {
                size1++;
            }
        }
        
        const size2 = n - size1;
        minDifference = Math.min(minDifference, Math.abs(size1 - size2));
    }

    return minDifference;
}